基于DV-Hop的大規模WSN定位方法研究

摘 要：DV-Hop是大規模無線傳感器網絡（WSN）典型定位算法，通過測量節點之間的信號傳輸距離和經過的中繼節點數，實現節點的位置估計。針對傳統DV-Hop算法中存在的平均跳距誤差較大和最小跳數難以確定等問題，通過引入加權平均跳距和基于節點分布的最小跳數，改進了傳統DV-Hop算法。仿真結果表明，改進的DV-Hop算法在提高定位精度方面優于傳統DV-Hop算法。

關鍵詞：無線傳感器網絡；節點定位；DV-Hop；平均跳距；最小跳數；定位誤差

中圖分類號：TP393 文獻標識碼：A 文章編號：2095-1302（2024）03-00-04

0 引 言

隨著傳感器技術的快速發展，無線傳感器網絡已經廣泛應用于農業數據采集、工業控制、森林火災控制和醫療等領域[1]。在無線傳感器網絡中，節點的位置信息對于網絡性能和應用效果具有至關重要的作用。因此，無線傳感器網絡的定位問題一直是研究熱點之一。

目前，無線傳感器網絡定位算法主要分為基于距離測量和無需距離測量兩類。基于距離測量的算法主要包括接收信號強度（RSSI）、到達時間（TOA）、到達時差（TDOA）和到達角測量（AOA）。無需距離測量的算法主要包括質心定位算法（CL）、凸規劃方法、近似三角形內點算法（APIT）、網絡多跳路由算法（DV-Hop）等[2]。其中DV-Hop算法是一種典型的基于節點距離的定位算法，其利用節點間的跳數和跳距信息進行節點的定位。因其簡單易實現、適用于大規模網絡和低成本等優點，被廣泛應用于無線傳感器網絡中。因此有許多國內外學者對DV-Hop算法進行研究與改進。文獻[3]提出了一種細化半徑的節點通信思路，進而細化最小跳數值，大幅降低了傳感器的定位誤差。文獻[4]利用改進鯨魚優化算法替代最小二乘法求未知節點坐標，以提高定位精度。文獻[5]提出了一種質心和DV-Hop混合定位算法MCDA，通過設置TTL值來限制信標節點廣播數據的范圍以及提高鄰居信標節點的比例來改進質心定位算法。

然而，傳統的DV-Hop算法存在平均跳距誤差較大和最小跳數難以確定等問題，這些問題嚴重影響了算法的定位精度和魯棒性。因此本文針對傳統DV-Hop算法存在的問題，提出了改進的DV-Hop算法。該算法通過引入加權平均跳距和基于節點分布的最小跳數，能夠有效地提高定位精度和魯棒性[6]。

1 DV-Hop算法概述

1.1 算法原理

DV-Hop算法是由Niculescu提出的一種定位方法，是一種基于跳數的無線傳感器網絡定位算法，其基本思想是通過節點之間的跳數關系來計算節點之間的距離，從而實現節點的定位。具體來說，DV-Hop算法分為三個階段，分別是跳數計算階段、距離計算階段和未知節點計算階段[7]。

（1）跳數計算階段：信標節點An通過網絡廣播包含An位置和跳數字段hn初始值0的消息。節點記錄跳數計數值表示未知節點u和An之間的最小跳數hun。重復接收到消息時，節點更新跳數計數值，停止信息獲取。該機制使得所有節點都能獲得每個信標節點中的最小跳數。

（2）距離計算階段：根據在跳數計算階段得到的每個信標節點的最小跳數計算每個跳躍的平均實際距離，如式（1）所示：

（1）

式中：HSizen表示信標節點An的平均跳距；（xn， yn）、（xm， ym）是信標節點An、Am的坐標；hnm是兩個信標節點n與m（n≠m）之間的最小跳數。該算法保證了大部分的未知節點都能得到最近的信標節點之間的平均距離。

（3）未知節點計算階段：通過三方測量或最大似然估計方法，對每個信標節點采用距離計算階段的固定間隔計算其坐標。

1.2 算法的不足

雖然傳統DV-Hop算法具有一定的定位精度和可靠性，但其也存在一些局限性。主要包括以下幾點：

（1）定位精度受到節點部署密度和網絡拓撲結構的影響。當節點部署密度不足或網絡拓撲結構較為復雜時，DV-Hop算法的定位精度會受到較大的影響。

（2）DV-Hop算法的準確度受到節點測距誤差的影響。在實際應用中，由于環境干擾等因素的存在，節點之間的跳距測量誤差較大，從而影響了DV-Hop算法的準確度。

（3）算法的計算復雜度較高。由于DV-Hop算法需要計算每個節點到已知節點的跳數和跳距信息，因此其計算復雜度較高，對于大規模的無線傳感器網絡，計算時間較長，從而影響了算法的實用性。

2 DV-Hop定位算法的改進

針對DV-Hop算法的不足，為了進一步提高DV-Hop算法的定位精度，本文主要從兩個方面進行改進：基于加權平均跳距和基于節點分布的最小跳數。

2.1 改進平均跳距

加權平均跳距的改進是針對DV-Hop算法中平均跳距的問題而提出的。在DV-Hop算法中，平均跳距的計算沒有考慮到節點之間跳數關系的不同，導致了節點的平均跳距具有一定的偏差，從而影響了定位精度。因此，本文研究了一種加權平均跳距的改進方法，通過對節點之間跳數關系進行加權，以降低平均跳距求值中造成的誤差，優化節點之間的距離估計。

如圖1所示，實心圓u表示未知節點，空心圓表示信標節點。在傳感器網絡中，假設信標節點An與信標節點Am之間的最小跳數為hnm，信標節點An的平均跳距為HSizen，這樣可以求得信標節點An與信標節點Am之間的理論距離如

式（2）所示：

（2）

在計算信標節點An的平均跳距時，考慮信標節點的真實距離和估計距離之間的誤差，實際平均跳距也可能與估計值略有偏差，其誤差εn如式（3）所示：

（3）

式中，εn表示信標節點An的平均跳距誤差。求得誤差值后就可以利用對誤差εn的優化來達到對信標節點An的平均跳距進行優化的目的，如式（4）所示：

（4）

式中，DHSizen為修正之后的信標節點An的平均跳距[8]。

2.2 改進最小跳數

基于節點分布的最小跳數的改進是針對DV-Hop算法中基于平均跳距的最小跳數問題而提出的。在DV-Hop算法中，由于節點的分布不均勻，可能會存在距離相近但跳數較大的節點，從而影響距離估計的精度。因此，本文提出了一種基于節點分布的最小跳數的改進方法。通過考慮節點分布的情況，尋找距離最近且分布相近的鄰居節點，進一步優化節點之間的距離估計，進而根據信標節點之間的實際距離，對最小跳躍次數進行修正，也就是理論上的信標節點Ai的跳躍次數hμnm，如式（5）所示：

（5）

信標節點之間估算跳數和實際跳數之間存在較大差異，為了解決這一問題，可以定義一個差異系數θn，用于計算未知節點到信標節點的最小跳數，如式（6）所示：

（6）

通過差異系數可以直觀體現出實際跳數hnm和理論跳數hμnm之間的偏差。差異系數越大，則說明兩者之間存在的偏差越大，于是，可以定義一個優化系數wn，用于減少誤差以優化節點之間的最小跳數，如式（7）所示：

（7）

式中，wn代表信標節點An的優化系數。利用所定義的系數wn來優化未知節點u到信標節點An的最小跳數hunmin，如式（8）所示：

（8）

式中，hun為未知節點u到信標節點An的實際最小跳數。通過建立權重系數來優化未知節點到信標節點的距離位置，并可以根據最小跳數和平均跳距求出在未知節點u到信標節點An的距離dun，如式（9）所示[9]：

（9）

2.3 算法流程

通過基于加權平均跳距和節點分布的最小跳數的改進，可以有效減小節點之間距離估計的誤差，提高定位精度。其算法流程如圖2所示。

3 仿真實驗與性能分析

為驗證改進的DV-Hop算法的性能，本文在MATLAB平臺上進行了一系列仿真實驗，并與傳統DV-Hop算法進行比較。

3.1 仿真環境

仿真中使用的無線傳感器網絡由100個隨機部署的節點組成，節點部署范圍為100×100的矩形區域，其中有8個信標節點，節點通信半徑值選取50 m，節點部署如圖3所示。

為了驗證該算法的性能，引入平均定位誤差Error如式（10）所示，主要是通過定位誤差進行分析，運行10次取平均值[10]。

（10）

式中：（xt， yt）是信標節點An的計算坐標值；（xn， yn）是信標節點An的真實坐標值；N為信標節點數量；K為節點總數；R為通信半徑。

3.2 仿真結果

3.2.1 只改進平均跳距

理論距離為數學估計距離，不可能百分之百等同于實際距離，所以有必要對算法進行軟件仿真，繪出測距誤差圖，以展示算法的精確性。測距誤差是指未知節點間的理論距離和實際距離的相差值。

如圖4所示，我們繪制了改進傳統算法平均跳距的測距誤差仿真圖。實驗結果表明，算法能夠準確地估算未知節點的位置，其中最大誤差為57.75 m，最小誤差為2.27 m，平均誤差為21.75 m。

3.2.2 只改進最小跳數

如圖5所示，我們在其他條件相同的情況下進行了只改進傳統算法最小跳數的誤差仿真。實驗結果表明，該算法能夠準確地估算未知節點的位置，其中最大誤差為57.75 m，最小誤差為2.96 m，平均誤差為21.83 m。

3.2.3 同時改進平均跳距和最小跳數

如圖6所示為在其他條件都相同的情況下，對傳統算法的平均跳距和最小跳數都進行優化后的誤差仿真圖。從實驗結果中可知，算法能夠準確地估算未知節點的位置，其中最大誤差為48.73 m，最小定位誤差為0.97 m，平均誤差為19.27 m。

實驗結果表明，在通信半徑為50 m、信標節點比例為8%的仿真環境中，無論是僅優化平均跳距、僅優化最小跳數，還是同時優化平均跳距和最小跳數，實際位置與理想位置之間的差異都不大。這說明三種優化算法在該仿真環境下的實際定位效果差別不大。因此，在實際應用中我們可以根據具體情況選取運行消耗低且計算相對簡單的算法。

3.2.4 不同通信半徑對定位誤差的影響

為了更全面地評估四種算法的性能，本文進行了另一組誤差仿真實驗，分別改變通信半徑和信標節點比例，選取不同參數值進行仿真并記錄實驗數據。在信標節點比例為8%的情況下，選取通信半徑的值分別為20 m、25 m、30 m、35 m、40 m、45 m、50 m、55 m、60 m、65 m進行仿真，得出平均誤差數據，并繪制誤差對比折線圖，如圖7所示。實驗結果表明，隨著通信半徑的增加，四種算法的誤差逐漸減小，但是減小的幅度逐漸趨于平穩。在通信半徑為65 m時，部分算法的誤差略有增加，可能是由于節點隨機分布所導致的。總體而言，改進算法的定位性能明顯優于傳統算法。

通過對比曲線圖可以直觀看出，在同一信標節點比例條件下，三種改進算法與傳統算法的定位誤差隨通信半徑增大而減小。三種優化算法定位精度明顯更高，例如當通信半徑為55 m時，傳統算法定位精度誤差為24.73%，改進算法定位精度誤差都在20%以下。當通信半徑大于50 m時，四種算法定位誤差下降趨勢減緩，但總體來說，三種優化算法定位性能明顯優于傳統算法。

3.2.5 不同信標節點比例對定位誤差的影響

在總節點數相同的情況下，通過改變信標節點數量來控制不同的信標節點密度，以評估其對算法性能的影響。選取通信半徑為20 m不變，信標節點比例從5%到50%進行實驗，并得到平均誤差數據圖如圖8所示。實驗結果顯示，隨著信標節點比例的增加，所有算法的誤差逐漸減小，但下降速率逐漸趨于平穩。當信標節點比例達到一定程度時，傳統算法和改進算法的誤差減小幅度明顯變小，趨于穩定。只有最小跳數改進和平均跳距與最小跳數同時改進的算法在信標節點比例為50%時誤差略有增加，這可能是由于隨機分布引起的個別數據誤差較大。

通過對比曲線圖可以更加清晰地觀察到第二種關系，即在相同的通信半徑下，隨著信標節點比例的增加，三種改進算法和傳統算法的定位誤差都在逐漸減少。顯然，相對于傳統的DV-Hop方法，本文提出的三種優化算法能夠顯著降低定位誤差，提高定位精度。在信標節點比例超過40%時，四種算法的定位誤差下降趨勢逐漸變緩，但是相較于傳統算法，本文提出的三種優化算法依然表現出了更好的定位性能。

4 結 語

本文針對DV-Hop算法存在的問題，提出了基于加權平均跳距和節點分布的最小跳數的方法。仿真實驗研究表明，改進算法相比傳統的DV-Hop算法，在定位精度和計算復雜度方面均有明顯的提高，而且改進算法適用于大規模無線傳感器網絡的定位應用。

注：本文通訊作者為蔡立濤。

參考文獻

[1]王慧.無線傳感器網絡DV-Hop定位算法的研究與改進[D].南京：南京郵電大學，2020.

[2] GAYANA S，DIAS D. Improved DV-Hop algorithm through anchor position re-estimation [C]// 2014 IEEE Asia Pacific Conference on Wireless and Mobile. Bali， Indonesia：IEEE，2020：126-131.

[3]劉超，李海鵬. DV-Hop定位算法的研究與改進[J].火控雷達技術，2021，50（1）：20-25.

[4]王磊，劉晶晶，齊俊艷，等.基于測距修正及改進鯨魚優化的DV-HOP定位算法[J].儀表技術與傳感器，2022，59（2）：116-121.

[5]張悅，梁建國，張浩，等.無線傳感器網絡質心和DV-Hop混合定位算法研究[J].儀表技術與傳感器，2021，58（4）：122-126.

[6]劉芷珺，張玲華.基于鄰域搜索粒子群算法的節點定位算法研究[J].電子技術應用，2022，48（9）：97-102.

[7]周凱，周培釗，付文涵，等.無線傳感器網絡的改進DV-hop定位算法研究[J].東北師大學報（自然科學版），2021，53（4）：137-143.

[8]劉川洲，張玲華.基于DV-Hop算法的無線傳感器網絡定位精度優化[J].激光與光電子學進展，2021，58（22）：498-504.

[9]祁祺.無線傳感器網絡中DV-Hop定位算法的研究與改進[D].南京：南京郵電大學，2021.

[10]何少尉.無線傳感器網絡中一種改進的DV-Hop定位算法研究[J].通信技術，2020，53（3）：648-653.