改進的DV-Hop算法在節點定位中的應用

韓雪松，楊鵑

(承德石油高等專科學校計算機與信息工程系，河北承德067000)

改進的DV-Hop算法在節點定位中的應用

韓雪松，楊鵑

(承德石油高等專科學校計算機與信息工程系，河北承德067000)

基于傳統DV-Hop算法的定位技術，通過分析該算法誤差產生的主要原因，提出了節點間跳數的修正方法。通過在廣播通信中采用雙通信頻率，將節點間的跳數縮減為0．5R，減少了平均跳距的誤差。通過matlab軟件的實驗驗證，本算法可以提高節點定位精度，且提高網絡通信頻率，可進一步提高定位精度，定位結果達到了預期的目的。

DV-Hop算法;節點定位;zigbee

節點定位通過節點間的數據和定位算法確定未知節點的具體位置，標識網絡節點的空間位置，是無線傳感網絡研究的重點內容之一。目前應用較多的定位算法有RSSI測距算法、AOA算法、TOA算法、DV-Hop算法、質心定位算法、APIT算法等［1］。本文研究使用的DV-Hop算法基于距離矢量，根據錨節點的平均跳距和未知節點到錨節點的跳數估算未知節點到錨節點的距離值，建立坐標與距離的方程組，通過求解方程組獲得未知節點的估計坐標。

1　傳統DV-HOP定位算法

1．1定位過程

DV-HOP算法的定位過程如圖1所示。

錨節點通過廣播方式通告自身的位置和跳數信息，鄰居節點接收到該數據分組后，首先判定是否是首次接收到該錨節點的數據包，如果是首次，則保留記錄，否則，比較跳數大小，保存跳數小的記錄。洪泛結束后，根據記錄保存的錨節點信息、跳數信息和自身坐標，求取平均跳距。平均跳距與跳數的乘積就是未知節點與該錨節點間的距離，求解距離方程組即可獲得未知節點的坐標值。

1．2誤差產生的主要原因

1)多跳轉發的定位誤差。在DV-HOP算法計算過程中，未知節點與錨節點之間的距離值是由錨節點的平均跳距和跳數的乘積確定的，實際網絡拓撲中，未知節點到錨節點的轉發路徑是一系列折線段，而錨節點間的實際距離是直線段，轉發的跳數越多，累計的誤差越大，定位誤差也越大［2］。

2)錨節點密度不均造成的誤差。錨節點的布局由于實際空間的限制，不能實現節點的均勻布局，會出現錨節點密度不均的現象。當密度不均勻布局時，估算的平均跳距誤差較大，因而造成定位誤差較大［3］。

3)錨節點密度過低。如果錨節點密度過低，則錨節點周圍的多跳錨節點的數目越少，與之建立路徑轉發的錨節點位置對平均跳距的求取影響越大，因而造成定位誤差值較大。并且錨節點密度過低，網絡內不良節點數目的增加［4］，降低了網絡的定位效果。

1．3研究情況

傳統的DV-Hop算法定位誤差較大，不適合于網絡稀疏的復雜工作環境，很多研究者在本算法的改進中取得了較大的成果，提高了算法的適用性。文獻［5］根據兩節點間的通信覆蓋率在跳數計算過程中，添加跳數系數，降低了每跳距產生的距離誤差。文獻［6］將錨節點劃分兩類，一跳內的節點采用RSSI定位算法，一跳以上采用DV-Hop算法，該方法簡單易行，但不適用于復雜環境中使用。文獻［7］針對于礦井復雜環境，在DV-Hop定位算法應用的基礎上，對跳數和跳距進行了優化處理，提高了定位的精度。文獻［8］添加錨節點的自定位過程，將定位結果與實際值相比較，得到計算的修正值，以提高定位的精度。改進的定位效果從多個角度進行了算法的優化，提高了定位精度，但也附加了一些其他技術問題，需要進一步的完善。

2　改進的DV-Hop算法

2．1改進的基本思想

DV-Hop算法的主要誤差集中在平均跳距和跳數的問題，基于通信半徑、節點間距離和跳數三者之間的關系，本文采用雙通信半徑的思想，減少平均跳距誤差。文獻［9］中采用雙通信半徑用于改善DVHop算法，但通信半徑設定為R和R/2，在實際使用中由于網絡通信環境不同，很難確定R/2的射頻信號大小，需進行節點網絡測試。

無線網絡通信信號模型公式如下式所示。

其中:λ—路徑損耗系數，一般取2～5;ξ—隨機數，符合高斯分布，平均值為0，其標準差一般取4～10; d0—參考距離，m;d—估計距離，m;Pr(d0)—參考距離的接收信號強度，dbm;Pr(d)—估計距離的接收信號強度，dbm。

2．2DV-Hop算法的具體改進方法

1)網絡錨節點首先以RF2廣播數據包分組，其中包括節點ID、節點坐標、初始跳數、轉發時間等信息，數據包分組的初始跳數值設定為0．5。收到數據包分組的錨節點保存記錄，轉發時間為0后，首次廣播結束。

2)網絡錨節點以RF1廣播數據包分組，數據包格式與步驟1相同，但初始跳數為1。如果網絡節點首次接收到該數據包分組，則保存記錄，否則判定跳數大小，保存跳數小的記錄。將跳數加后，數據包分組轉發給其他鄰居節點。轉發時間為0后，廣播結束。

3)與傳統的DV-Hop算法計算一致，求取平均跳數，計算距離值，求解方程組。

3　仿真實驗與分析

為了驗證改進算法的有效性，本文基于matlab軟件搭建仿真環境模擬和計算未知節點的定位效果，研究在不同錨節點密度和通信半徑的條件下，平均定位誤差的大小。仿真環境設定在100 m×100 m的范圍內，初始錨節點個數12個，通信半徑30 m，網絡環境中假定路徑損耗系數為4，信號的干擾用均值為5的高斯白噪聲表示，采用最小二乘法求解方程組。實驗中隨機生成100個未知節點，計算節點定位的平均誤差值。

通信半徑對定位誤差的影響如圖2所示。網絡通信半徑增加，則平均定位誤差相對減小，這也說明在網絡情況允許的情況下，應盡量采用大功率的射頻信號發射，可降低網絡的平均定位誤差。錨節點個數初始增加可明顯減小平均定位誤差，但當節點密度達到一定程度，平均定位誤差基本保持不變。

以通信半徑30 m為例，兩種算法對比圖如圖3所示。平均定位誤差相差很大，基于傳統DV-Hop算法的平均定位誤差在35．28%～38．8%，改進后的算法平均定位誤差在25．1%～28．8%，改進后相比于改進前大約提高了10%個精度，達到了預期的目的。

4　結束語

本文在傳統的DV-Hop基礎上采用雙通信半徑方法，將節點間距離的求取誤差降低了0．5R的誤差，通過仿真實驗看出，通信半徑對于定位結果影響較大，錨節點密度在達到一定程度后對定位結果影響不大。本文只是針對于節點間距離的計算進行了改進，后續研究中應考慮求解方程組最優解的方法，更進一步提高定位精度。

［1］楊鵑，韓雪松．無線傳感網絡節點定位技術［J］．承德石油高等專科學校學報，2013，15(6):39－43．

［2］夏少波，周建梅，朱曉麗，等．基于跳數區域劃分的DV－Hop改進算法［J］．傳感技術學報，2014，27(7):964－969．

［3］李雪梅．基于DV-HOP算法的無線傳感器網絡節點定位技術的研究［D］．太原:太原理工大學，2012．

［4］李冬．基于DV-Hop的無線傳感器網絡定位算法研究與改進［D］．南京:南京理工大學，2013．

［5］譚志，張卉．基于節點間覆蓋關系的改進DV-Hop算法［J］．北京郵電大學學報，2014，37(1):35－38．

［6］Liu Y，Qian ZH，Liu D，et al．A DV-hop positioning algorithm for wireless sensor network based on detection［A］//2009 Fifth International Joint Conference on INC，IMS and IDC［C］．Seoul:International joint conferences，2009．

［7］方旺盛，吳勝寶．基于井下異構無線傳感器網絡DV-Hop定位算法的改進［J］．傳感器與微系統，2014，33(5):125－128．

［8］黃浩，盧文科．無線傳感器網絡中基于信標節點反饋的多跳測距定位算法改進［J］．傳感技術學報，2009，22(2): 269－272．

［9］李娟，劉禹，錢志鴻，等．基于雙通信半徑的傳感器網絡DV-Hop定位算法［J］．吉林大學學報(工學版)，2014，44 (2):502－507．

Improvement of DV-Hop Algorithm in Application of Node Localization

HAN Xue-song，YANG Juan
(Department of Computer and Information Engineering，Chengde Petroleum College，Chengde 067000，Hebei，China)

Based on the traditional positioning technology of DV-Hop algorithm，through analysis of the main reason for the error occurring in the algorithm，this paper proposes the correction method of Hop count between nodes．Double frequency is used in radio communication．The hop count between nodes can be reduced to 0．5R，which can reduce the average jump distance error．Through matlab software experimental verification，this algorithm can improve the node location accuracy．The higher frequency of network communication can further make the positioning accuracy lower．Positioning results reached the expected purpose．

DV－Hop algorithm;node localization;zigbee

TP393

B

1008-9446(2015)02-0047-03

2014-11-12

韓雪松(1980－)，男，吉林省吉林市人，承德石油高等專科學校計算機與信息工程系講師，主要研究方向為無線網絡通信和數據融合技術等。