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

韓雪松，楊鵑

(承德石油高等?？茖W校計算機與信息工程系，河北承德067000)

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

韓雪松，楊鵑

(承德石油高等?？茖W校計算機與信息工程系，河北承德067000)

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

DV-Hop算法;節(jié)點定位;zigbee

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

1　傳統(tǒng)DV-HOP定位算法

1．1定位過程

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

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

1．2誤差產(chǎn)生的主要原因

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

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

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

1．3研究情況

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

2　改進的DV-Hop算法

2．1改進的基本思想

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

無線網(wǎng)絡通信信號模型公式如下式所示。

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

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

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

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

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

3　仿真實驗與分析

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

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

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

4　結束語

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

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

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

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

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

［5］譚志，張卉．基于節(jié)點間覆蓋關系的改進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］方旺盛，吳勝寶．基于井下異構無線傳感器網(wǎng)絡DV-Hop定位算法的改進［J］．傳感器與微系統(tǒng)，2014，33(5):125－128．

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

［9］李娟，劉禹，錢志鴻，等．基于雙通信半徑的傳感器網(wǎng)絡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－)，男，吉林省吉林市人，承德石油高等?？茖W校計算機與信息工程系講師，主要研究方向為無線網(wǎng)絡通信和數(shù)據(jù)融合技術等。