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

楊 鵑/Yang Juan

（承德石油高等專科學校 承德 067000）

1 引言

無線傳感網(wǎng)絡利用微電子技術、嵌入式技術和無線通信技術等多種技術，依賴節(jié)點間射頻信號的發(fā)送和接收實現(xiàn)數(shù)據(jù)分組的傳輸，可實現(xiàn)數(shù)據(jù)采集、數(shù)據(jù)處理和網(wǎng)絡通信等功能，目前被廣泛應用在工業(yè)、農(nóng)業(yè)、交通和智能建筑等多種行業(yè)。

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

2 傳統(tǒng)DV-Hop 定位算法

2.1 定位過程

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

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

2.2 誤差產(chǎn)生的主要原因

（1）多跳轉(zhuǎn)發(fā)的定位誤差

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

圖1 DV-Hop算法的定位過程

（2）錨節(jié)點密度不均造成的誤差

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

（3）錨節(jié)點密度過低

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

2.3 研究情況

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

3 改進的DV-Hop算法

3.1 改進的基本思想

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

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

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

3.2 DV-Hop算法的具體改進方法

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

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

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

4 仿真實驗與分析

為了驗證改進算法的有效性，本文基于Matlab軟件搭建仿真環(huán)境，模擬和計算未知節(jié)點的定位效果，研究在不同錨節(jié)點密度和通信半徑的條件下平均定位誤差的大小。仿真環(huán)境設定在100 m×100 m的范圍內(nèi)，初始錨節(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 為例，2 種算法對比如圖3所示，平均定位誤差相差很大，基于傳統(tǒng)DV-Hop算法的平均定位誤差在35.28%～38.8%，改進后的算法平均定位誤差在25.1%～28.8%，改進后相比于改進前大約提高了10%的精度，達到了預期的目的。

圖2 通信半徑對定位誤差的影響

圖3 兩種算法對比

5 結(jié)束語

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

1 夏少波，周建梅，朱曉麗等.基于跳數(shù)區(qū)域劃分的DV-Hop 改進算法.傳感技術學報，2014，27(7)：964~969

2 李雪梅.基于DV-Hop算法的無線傳感器網(wǎng)絡節(jié)點定位技術的研究.太原理工大學學位論文，2012

3 李冬.基于DV-Hop的無線傳感器網(wǎng)絡定位算法研究與改進.南京理工大學學位論文，2013

4 譚志，張卉.基于節(jié)點間覆蓋關系的改進DV-Hop算法.北京郵電大學學報，2014，37(1)：35~38

5 Liu Ying，Qian Zhihong，Liu Dan，et al.A DV-Hop positioning algorithm for wireless sensor network based on detection.2009 Fifth International Joint Conference on INC,IMS and IDC.Seoul：International joint conferences,2009:453~456

6 張亞麗，陳名松，劉瀟憶.基于DV-Hop的WSN 節(jié)點定位改進算法的研究.電子測量技術，2013，36(5)：49~53

7 方旺盛，吳勝寶.基于井下異構(gòu)無線傳感器網(wǎng)絡DV-Hop 定位算法的改進.傳感器與微系統(tǒng)，2014，33(5)：125~128

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

9 李娟，劉禹，錢志鴻等.基于雙通信半徑的傳感器網(wǎng)絡DV-Hop 定位算法.吉林大學學報（工學版），2014，44(2)：502~507

10 張亞麗，陳名松，劉瀟憶.基于DV-Hop的WSN 節(jié)點定位改進算法的研究.電子測量技術，2013，36(5)：49~54