克服傳統DV-Hop局限：基于最小跳數優化與動態跳距加權的精準定位

原文發表于《科技導報》2025 年第16 期 《 基于多通信半徑最小跳數優化與跳距加權修正的 DV?Hop 定位算法》

針對無線傳感器網絡節點應用傳統 DV?Hop 定位算法時存在最小跳數值誤差和平均跳距誤差較大的問題，提出了基于多通信半徑最小跳數優化與跳距加權修正的 DV?Hop 定位算法。采用錨節點通信半徑多級數分層的方法，減少了未知節點最小跳數選取的誤差。通過加權平均跳距的方式進一步降低了因不規則網絡拓撲結構導致的錨節點與未知節點之間距離計算的誤差。最后，未知節點通過最小二乘法計算自身坐標。MATLAB 仿真結果表明，通過對上述 2 個步驟的改進，在多種模擬環境中提出的 DV?Hop 定位算法相較傳統 DV?Hop 算法及有關文獻算法具有更高的定位精度。

DV?Hop 定位算法基于距離矢量路由原理，是非測距的定位算法，也稱為距離向量跳段定位算法。DV?Hop 定位算法的優化策略主要針對算法本身的 3 個步驟進行改進，即最小跳數的選取、平均跳距的計算和未知節點坐標的計算。

國內外學者在此基礎上提出了大量的改進方案。Kumari 等通過將工作區域分為等大小球形帶以修正最小跳數，提高了定位精確度。劉川洲等采用了多種方法對經典 DV?Hop 算法的 3 個步驟分別進行了優化，提高了定位精度。隨著人工智能算法的不斷涌現，出現了將智能算法引入到 DV?Hop 算法中的改進方案。劉燕等在 DV?Hop 算法中引入了人工蜂群算法，并在多邊定位階段引入數學優化模型，以解決 DV?Hop 算法定位誤差較大的問題。孫博文等將改進的灰狼優化算法與 DV?Hop 算法融合，在一定程度上解決了基于群智能的 DV?Hop 算法性能不理想的問題。Liu 等設計了一種基于多目標樽海鞘群優化的 DV?Hop 算法，利用改進的多目標樽海鞘算法估計節點坐標。

目前基于 DV?Hop 算法的改進，雖然在某種程度上能夠取得較好的定位效果，但很多算法的改進都是在原算法的基礎上引入其他更加復雜的算法。無線傳感器網絡節點硬件資源通常有限，若將最小二乘法替換為智能優化算法，在實際應用中對節點的計算開銷提出了更高的要求。因此，基于輕量化、低復雜度的優化思路，從多通信半徑最小跳數優化與跳距加權修正 2 個方面對傳統 DV?Hop 定位算法進行改進，并通過仿真實驗驗證其有效性。

01

傳統 DV?Hop 定位算法

傳統 DV?Hop 算法是非測距的定位算法，它利用包含最小跳數等位置信息的廣播數據包，來計算節點間的距離估計值，并進一步求解未知節點的坐標。在 DV?Hop 算法中，錨節點首先在網絡中廣播自身的位置信息。當其他節點接收到這些信息時，會以此來更新自身最小跳數、跳距等信息，并將新數據再次廣播。通過這種機制，所有未知節點都可以獲得錨節點包含最小跳數的數據包。DV?Hop 算法的具體步驟如下。

步驟 1：網絡初始化，跳數初始化為 0。

步驟 2：錨節點計算平均跳距。計算如式 （1）

式中，錨節點

i

與錨節點

j

的坐標值分別為（

i

, y

i

）和（

j

,y

j

），兩者之間的最小跳數為

Hop

ij

i

j

）。

步驟 3：錨節點向通信半徑 R 內的未知節點廣播自身的數據。

步驟 4：若未知節點接收到數據，判斷其是否為記錄過的數據包，若未記錄過，保存該數據包，將到該錨節點的最小跳數設為 1；若記錄過，則將該跳數加 1 后轉發給鄰居節點。

步驟 5：若鄰居節點接收到的轉發數據包來自相同錨節點，則只保存到該錨節點最小的跳數值與對應的平均跳距。

步驟 6：未知節點計算與錨節點的距離，如式 （2）和式 （3） 所示

式 （2）、式 （3） 中，

Hopsize

j

為未知節點

j

的平均跳距，

Hopsize

i 為未知節點

j

第一次接收到的錨節點

i

的平均跳距，未知節點

j

和錨節點

i

之間的計算距離為

i

j

，未知節點

j

和錨節點

i

之間的最小跳數為

Hop

ij

步驟 7：當未知節點接收到 3 個或以上的錨節點數據時，計算位置坐標。由式 （3） 得到錨節點與未知節點之間的估計距離

k

后，根據式（4） 求解估計坐標

式中，未知節點的坐標為（

x, y

），錨節點的坐標為（

k

, y

k

）,

k

1,2,…N

。式 （4） 可通過式 （5） 表示

式中，

如式 （9），坐標

X

通過最小二乘法求解

式中，

T

為矩陣的轉置。

02

基于多通信半徑最小跳數優化與跳距加權修正的 DV?Hop 定位算法

2.1 多通信半徑最小跳數的優化

在傳統 DV?Hop 算法中，會出現節點實際距離相差很大，但最小跳數值卻相同的情況。若 2 個節點之間的距離小于或等于錨節點的通信半徑，2 個節點與錨節點之間的最小跳數值均為 1。而在實際網絡中，這 2 個節點到該錨節點的實際距離卻可能相差很大。這即是最小跳數值引起的誤差。

對于錨節點通信半徑內的多個未知節點之間因最小跳數選取而引起的誤差，采取通信半徑分層的方法進行優化。提出的錨節點通信半徑分層示意圖如圖 1 所示。

圖 1 節點通信半徑分層示意圖

設錨節點的通信半徑為

R

，將其分為

m

個層級，錨節點可按劃分的層級數依次廣播。此時位于不同廣播半徑內的未知節點與錨節點之間的距離為

i

為正整數，滿足

i

∈[1, m]

根據式 （10），若取

R

=30，

m

=3，則圖 1 中的節點

A、B、C、D

與錨節點之間的最小跳數值分別為 1/3、2/3、1、4/3。顯然，通過改進，錨節點和未知節點之間的最小跳數不再是整數值，而是與距離更接近正比例關系的小數值，從而達到減小定位誤差的目的。

2.2 跳距的加權修正

在傳統 DV?Hop 算法中，未知節點使用與其最近的錨節點平均跳距作為自身的平均跳距，并通過最小跳數和平均跳距相乘計算與其他節點的距離。然而節點不規則分布導致的網絡拓撲不規則，產生了大量由折線路徑組合的通信路徑。通過平均跳距計算的距離與實際距離不符，使誤差累積，降低了定位精度。本文采用跳距加權的方法對誤差進行修正。

設未知節點坐標為 D（

x,y

），與該未知節點通信的錨 節 點 的 坐 標 分 別設為

A

1 （

1

,y

A

2 （

2

,y

A

n

n

,y

n

）。這些錨節點的平均跳距分別為

hopsize

1 ，

hopsize

hopsize

n

。各個錨節點到未知節點

D

x,y

）的跳數分別為

hop

1 ，

hop

hop

n

。未知節點

D

x,y

）到錨節點

A

1 （

i

, y

i

）的距離

r

i

如式 （11） 所示

對于未知節點與其他節點間的距離估算，基于其最小跳數與其平均跳距的乘積。通過對未知節點平均跳距加權處理，可以減少誤差。平均跳距修正公式如式 （12）~（14） 所示

由式 （12） 可知，若錨節點距離未知節點越近，其

hop

i

越小，得到的權值

i

就會越小，由式 （13） 得出修正后的

hopsize

i

值與原來的值相差就會越小，從而在式（14） 中求平均跳距時的占比會越大。通過對每個與未知節點通信的錨節點平均跳距進行加權，能有效提高定位精度。

綜合以上 2 個方面的改進，本文提出的基于多通信半徑最小跳數優化與跳距加權修正的 DV?Hop 定位算法流程圖如圖 2 所示。

圖 2 基于多通信半徑最小跳數優化與跳距加權修正的 DV?Hop 定位算法流程

03

實驗仿真與分析

3.1 仿真環境及參數

采用 Matlab2016B 對改進 DV?Hop 算法進行驗證。環境為100 m×100 m 的二維區域，仿真次數為100，求取平均值作為最終結果以減少隨機性帶來的影響。仿真環境中的參數設置如表 1 所示。

評估算法性能的標準是歸一化定位誤差，如式（15） 所示

式中，

R

為網絡通信半徑，

N

為未知節點總數，（

ir

,y

ir

）和（

ie

,y

ie

）分別代表第

i

個未知節點的實際位置坐標和預測位置坐標。

表 1 仿真環境參數設置

3.2 算法性能仿真與結果分析

為了驗證算法的性能，采用改進的 DV?Hop 算法與傳統 DV?Hop 算法、文獻的算法進行對比分析。節點總數、錨節點占比和節點通信半徑對 2 種算法的定位精度有著很大的影響。其中增加節點數量可以提高網絡拓撲中未知節點接收到數據的概率，從而提高定位精度，提高錨節點占比可以讓未知節點接收到更多錨節點數據，從而提高定位精度，而增加節點通信半徑可以減少網絡拓撲中折線段的數量，從而提高定位精度。在后續的仿真中將通過這 3 個變量對實驗結果進行分析。

1）節點總數對定位精度的影響。選定節點總數作為變量，從初始值 50 開始以步長 5 升至 100，改進DV?Hop 算法的通信半徑分級層數分別設置為

m

m

m

m

=5，錨節點占比統一確定設置為 30%，通信半徑設為 50 m，仿真結果如圖 3 所示。

圖 3 不同節點總數的定位誤差

由圖 3 可知，定位誤差與節點總數在整體上成反比，且不斷趨于穩定。這是因為在固定的有限區域內，節點的總數越多，單位面積內的節點密度越大，節點間的多跳折線段就越逼近直線。同時，通信半徑的分層級數也與定位誤差成反比。當

m

=2 和

m

=3 時，定位誤差明顯減小，當

m

=4 和

m

=5 時，定位誤差減小較少。

m

=2 時改進算法較傳統 DV?Hop 算法的平均定位誤差減小了約 27%；

m

=2 較

m

=3 時算法平均定位誤差減小了約 12%；

m

=4 較

m

=3 時算法定位誤差減小幅度小于其他情況，這是因為通信半徑分層級數越 多， 跳 數 選 擇 產 生 的 誤 差 會 越 來 越 小 。 其 中

m

=5 時總體的歸一化誤差較文獻的算法減小了22%。

2）錨節點占比對定位精度的影響。選定錨節點占比為變量，從初始值 5% 開始以步長 5% 升至 50%，改進 DV?Hop 算法的通信半徑分級層數分別設置為

m

m

m

m

=5，節點總數統一設置為 100 個，通信半徑設為 50 m，仿真結果如圖 4 所示。

圖 4 不同錨節點占比的定位誤差

由圖 4 可知，隨著錨節點占比的增加，改進算法與傳統 DV?Hop 算法的平均定位誤差均會逐漸降低。在固定有限區域內，錨節點數量越多，未知節點接收到的錨節點數據就會越多，位置求解越精確。通信半徑的分層級數也極大降低了定位誤差。在錨節點占比為 5%~15% 時，定位誤差受錨節點占比影響較大，當錨節點占比超過 15% 后，定位誤差變化均趨于穩定。同樣，通信半徑分級層數

m

=2 和

m

=3 時，定位誤差減小效果較明顯；當

m

=2 時改進算法平均定位誤差較傳統 DV?Hop 算法減小了約 33%；

m

=3 較

m

=2 時 改 進 算 法 平 均 定 位 誤 差 減 小 了 約 11%；

m

=4 與

m

=5 時平均定位誤差的減小幅度較小，這是因為通信半徑分層級數越多，跳數選擇產生的誤差會越來越小。其中

m

=5 時總體的歸一化誤差較文獻的算法減小了 14.37%。

3）通信半徑對定位精度的影響。選定通信半徑作為變量，從初始值 20 m 開始以步長 5 m 升至 50 m，改進 DV?Hop 算法的通信半徑分級層數分別設置為

m

=2、m=3、

m

m

=5，節點總數統一確定設置為100 個，錨節點占比設為 30%，仿真結果如圖 5 所示。

圖 5 不同通信半徑的定位誤差

由圖 5 可知，隨著通信半徑的增加，2 種算法的平均定位誤差都顯著降低。當通信半徑接近 30 m 時，定位誤差趨于平緩；當通信半徑接近 40 m 時，不同層級數的平均定位誤差都趨于 10%。同樣，

m

=2 時改進算法較傳統 DV?Hop 算法平均定位誤差減小了約27%；通信半徑分級層數

m

=2 和

m

=3 時，平均定位誤差顯著減小，約為 19.4%。

m

=3 較

m

=2 時平均定位誤差減小了約 10.5%；

m

=4 和

m

=5 時定位誤差相差

無幾，這是因為通信半徑分層級數越多，跳數選擇產生的誤差會越來越小。其中

m

=5 時總體的歸一化誤差較文獻的算法減小了 27.25%。

4）節點定位誤差。根據上述實驗分析可知，節點總數、錨節點占比和通信半徑對改進 DV?Hop 算法和傳統 DV?Hop 算法的定位精度都有著很大的影響。為對比改進前后定位算法的不同效果，在相同環境下，通過 2 種算法對未知節點進行定位。設置二維平面 100 m×100 m，節點總數 100 個，錨節點占比為20%，通信半徑 30 m，求取平均位置誤差進行對比，定位結果如圖 6 所示。

由圖 6 可知，80 個未知節點的平均定位誤差在一定范圍內呈現不規則的變化。其中，改進 DV?Hop 算法、傳統 DV?Hop 算法、文獻算法的定位誤差均值分別為 3.8971、9.1843、4.6654 m。因此，所提出的算法具有最高的定位精度。

圖 6 節點定位誤差對比

04

結論

針對傳統 DV?Hop 定位算法存在較大定位誤差的問題，提出了基于多通信半徑最小跳數優化與跳距加權修正的 DV?Hop 定位算法。

1）為改善 DV?Hop 算法中最小跳數選取造成的誤差，提出了錨節點通信半徑分層的方法來修正節點間的最小跳數。仿真結果表明，當分層級數

m

=2 時，對比 DV?Hop 算法，改進 DV?Hop 算法的平均定位誤差有顯著降低。然而隨著分層級數的增加，因跳數選擇產生的誤差越來越小，改善效果會逐漸減小。

2） 在 DV?Hop 算法中，未知節點采用與其最近錨節點的平均跳距作為自身跳距進行距離計算，為改善該步驟產生的誤差，提出了加權平均跳距的方法修正未知節點的平均跳距。仿真結果表明，結合了多通信半徑最小跳數優化與跳距加權修正的 DV?Hop 算法有效降低了節點的平均定位誤差。

3） 在改進 DV?Hop 算法中，要求錨節點按層級數多次發送數據包，這增加了硬件的能量開銷，而仿真結果表明，隨著層級數的增加，定位誤差的減小幅度會逐漸降低。同時，為了實現平均跳距的加權，要求未知節點進行多次較復雜的計算。因此，如何進一步平衡無線傳感器網絡的能耗與定位精度將是未來研究的重點。

本文作者：張烈平，黃自晨，尹亞夢，譚銘揚，王守峰

作者簡介：張烈平，桂林航天工業學院機電工程學院，教授，研究方向為傳感器與智能信息處理技術。

文章來 源 ： 張烈平, 黃自晨, 尹亞夢，等. 2024年4月 基于多通信半徑最小跳數優化與跳距加權修正的 DV?Hop 定位算法[J] . 科技導報, 2025, 43(16): 114-119.

內容為【科技導報】公眾號原創，歡迎轉載
白名單回復后臺「轉載」

《科技導報》創刊于1980年，中國科協學術會刊，主要刊登科學前沿和技術熱點領域突破性的研究成果、權威性的科學評論、引領性的高端綜述，發表促進經濟社會發展、完善科技管理、優化科研環境、培育科學文化、促進科技創新和科技成果轉化的決策咨詢建議。常設欄目有院士卷首語、科技新聞、科技評論、專稿專題、綜述、論文、政策建議、科技人文等。