一種改進的無線傳感器網絡DV-HOP定位算法

武雪姣 李雪晴 丁佳靜

摘 要：為了解決DV-HOP算法在節點隨機部署環境下定位誤差較大的缺點，提出一種基于DV-HOP多通信半徑的加權雙曲線定位算法RWHDV-HOP。該算法通過理想跳數與實際跳數的差值修正平均跳距，結合多通信半徑使跳數小數化，利用基于跳數加權的雙曲線算法估算未知節點坐標。仿真結果表明，在相同條件設置下，RWHDV-HOP算法定位精度比傳統DV-HOP算法提高了25%，比RWDV-HOP算法提高了10%。因此，基于DV-HOP多通信半徑的加權雙曲線定位算法RWHDV-HOP在節點隨機部署環境下能夠較大程度上提高節點定位精度。

關鍵詞：多通信半徑;無線傳感器網絡;跳距優化;定位精度;加權雙曲線算法

DOI：10. 11907/rjdk. 191540 開放科學（資源服務）標識碼（OSID）：

中圖分類號：TP312 文獻標識碼：A 文章編號：1672-7800（2019）008-0052-04

An Improved Wireless Sensor Network DV-HOP Positioning Algorithm

WU Xue-jiao，LI Xue-qing，DING Jia-jing

（School of Information Engineering，Heibei GEO University，Shijiazhuang 050031，China）

Abstract：Aiming at the large positioning error of DV-HOP algorithm in the environment of node random deployment， a multi-communication radius weighted hyperbolic localization algorithm RWHDV-HOP based on DV-HOP algorithm is proposed. The algorithm corrects the average hop distance by the difference between the ideal hop count and the actual hop count. The multi-communication radius refines the number of hops between nodes， and uses the hyperbolic algorithm based on hop weight to estimate the coordinates of unknown nodes. The simulation results show that in the same experimental environment， the RWHDV-HOP algorithm has a 25% higher positioning accuracy than the traditional DV-HOP algorithm and a 10% higher accuracy than the RWDV-HOP algorithm. The RWHDV-HOP algorithm based on DV-HOP multi-communication radius weighted hyperbolic positioning algorithm can improve the node positioning accuracy to a large extent in the environment of node random deployment.

Key Words：multiple communication radius; wireless sensor network;hop distance optimization;positioning accuracy;weighted hyperbolic algorithm

作者簡介：武雪姣（1992-），女，河北地質大學信息工程學院碩士研究生，研究方向為無線傳感器網絡定位。

0 引 言

節點自定位技術是無線傳感器網絡領域的重要技術之一[1-2]。目前大多數定位系統采用距離無關的定位算法[3]，DV-HOP算法是其中一種應用較為廣泛的算法。

傳統DV-HOP定位算法在節點隨機部署情況下存在較大定位誤差，綜合文獻分析，對其誤差的改進研究主要分為3類：①跳數改進。文獻[4]提出基于雙通信半徑的DV-HOP算法，文獻[5]在其基礎上提出一種三通信半徑改進方法，以細化錨節點與鄰居節點的跳數，使節點跳數小數化，從而提高定位精度;②跳距改進。文獻[6]提出一種基于RSSI優化跳數與平均跳距的DV-HOP改進算法，文獻[7]提出一種基于跳距誤差加權的改進算法，文獻[8]通過控制功率大小修正每跳距離以提高定位精度，文獻[9]研究節點間距離與跳數的關系計算平均每跳距離。這些文獻主要對算法的第二階段跳距進行修正，以進一步提高定位精度，但增加了計算量;③節點估算方法改進。文獻[10]利用粒子群算法替換最大似然估計法，提高了定位精度，文獻[11]提出基于差分進化的定位算法估計未知節點最優位置。但這些算法需要的參數較多，容易陷入局部最優解。

本文針對DV-HOP算法在跳數、跳距、估算方法方面存在誤差的問題，對算法的每一階段進行改進，通過理想跳數與實際跳數的差值修正平均跳距，結合多通信半徑使跳數小數化，并利用基于跳數加權的雙曲線算法估算未知節點坐標。

1 DV-HOP算法

DV-HOP定位算法原理與經典的距離矢量路由算法比較相似，是由Niculescu等[12-14]學者提出的非測距算法。

在DV-HOP算法中，錨節點在網絡中廣播該錨節點位置和一個初始值為0的表示跳數的信息。該數據在網絡中以泛洪方式傳播出去，每次被轉發時跳數都增加1。接收節點在其收到的關于某個錨節點所有數據中保存具有最小跳數值的信息。通過該機制，所有節點都獲得了到其它節點的最小跳數值[15]。

為了將跳數轉換成距離，需要估計網絡中平均每跳距離。通過式（1）計算各錨節點平均跳距。

[Hopsizei=j=1，j≠iN（xi-xj）2+（yi-yj）2j=1，j≠iNhij]? （1）

其中，（xi，yi）、（xj，yj）是錨節點i和j的坐標，hij表示錨節點i和j的最小跳數，N表示錨節點數量，Hopsizei是每個錨節點的全網平均跳距。

將各個錨節點的平均跳距廣播到網絡中，未知節點將接收到距離自己最近的錨節點跳距作為自身跳距，并計算到其它錨節點的距離，最后通過最大似然估計法估算自身位置[16-17]。

2 改進DV-HOP算法描述

DV-HOP算法誤差來源于以下幾點：①錨節點在通信半徑內廣播數據包信息，受通信半徑限制，在與其它節點通信過程中，即使同為一跳，跳距也相差很大;②錨節點在計算平均跳距時，受到網絡連通的影響，錨節點并非全部進行共線式排列，導致錨節點跳距與真實值相比有一定差距;③未知節點在第三階段估算自身跳距時，選擇最近錨節點的平均跳距，不能反映出該未知節點局部范圍內的網絡分布情況;④最大似然估計法減少了數據使用量，降低了算法精度[18]。

本文針對DV-HOP算法存在的不足，對算法的每一階段進行改進，提出基于多通信半徑的加權雙曲線定位算法RWHDV-HOP算法。

第一階段中對錨節點引入多通信半徑播送數據。具體過程如下：網絡初始化，錨節點首先以通信半徑R/n向網絡播送數據包信息，同時將相鄰節點與錨節點之間的跳數記為1/n跳[19];經過時間T，錨節點再以通信半徑2R/n向網絡傳播數據包信息;接收到錨節點信息的節點若沒有該錨節點的跳數信息，則將跳數記為2/n，如果有跳數信息，則將原跳數信息進行轉發[19]。通過上述轉發過程，每個節點都能獲得與錨節點之間的最小跳數[19]。

第二階段：傳統DV-HOP算法計算錨節點平均跳距時忽視了錨節點共線情況，導致跳數越多，誤差越大。文獻[19]通過跳數加權方法對錨節點平均跳距進行改進，但只考慮了跳數越多、偏差越大的問題，而沒有從節點共線度的本質上解決問題;文獻[20]通過共線度檢測方式優化跳距。

首先計算錨節點與矩形區域內4個頂點的距離，求出第i個錨節點在網絡中理論上的最大跳數[ki]，去掉與其共線度低的錨節點，通過將實際跳數與理想跳數作差進行權重計算，最后加權計算錨節點跳距[20]。

[ki=max（di1R，di2R，di3R，di4R）]? ? ? ? ? ? ? ?（2）

[cij=1dij/R-hij]? ? ? ? ?（3）

[wij=cijj≠imcij]? ? ? ? ? ? ?（4）

其中，R表示通信半徑，[wij]表示錨節點j對錨節點i的權重。

[Hopsizei=j≠imwij×dijhopij]? ? ? ? （5）

第三階段：計算未知節點到錨節點距離時，將對應錨節點跳距考慮在內。

[dij=Hopsizei×hij]? ? ? ? ? ? （6）

[dij=Hopsizej×hij]? ? ? ? ? ?（7）

其中i為未知節點，j為錨節點，Hopsizei是距離未知節點最近的錨節點跳距，可以由式（7）或式（8）計算未知節點到錨節點的距離。綜合考慮網絡連通情況，將未知節點到相應錨節點的距離計算公式優化為：

[dij=1/2×（Hopsizei+Hopsizej）×hij]? ?（8）

第四階段：使用加權的雙曲線定位算法替換最大似然估計法。

雙曲線估計算法[18]通過將第i個未知節點（xi，yi）到各個錨節點的距離公式展開，不需要方程求差，將含有未知量的項移到等式左側得到。其中，di1，di2，…din分別表示未知節點到各個錨節點的距離。

[xi2+yi2-2x1xi-2y1yi=di12-x12-y12xi2+yi2-2x2xi-2y2yi=di22-x22-y22？xi2+yi2-2xnxi-2ynyi=din2-xn2-yn2]? ? （9）

則公式（9）可以轉化為：

[AC=B]? ? ? ? ? （10）

[A=1-2x1-2y11-2x2-2y2？？？1-2xn-2yn]? ? ? ? ?（11）

[C=xi2+yi2xiyi]? ? ? ? ? （12）

[B=di12-x12-y12di22-x22-y22？din2-xn2-yn2]? ? ? ? ? （13）

由最小二乘準則估計出C。

[C=（ATA）-1ATB]? ? ? ? ? ? ? ? ? ? ? ?（14）

為了使定位更加準確，在定位階段引入基于跳數的權重。首先計算跳數因子[Vij]，使得錨節點距離未知節點跳數越小，V值越大，然后通過跳數因子計算權值[Wij]，最后得到加權系數矩陣W。

[Vij=j=1khopijhopij]? ? ? ? ? （15）

[Wij=Viji=1kVij]? ? ? （16）

[Wi=Wi10000Wi200？？？？000WiK]? ? （17）

結合式（11）、式（13）可得未知節點坐標為：

[C=（ATWA）-1ATWB]? ? ? ? （18）

3 實驗仿真分析

為了驗證本文提出的改進RWHDV-HOP算法在精確度和穩定性上是否得到提高，利用MATLAB R2016a仿真軟件模擬網絡測試環境，將改進RWHDV-HOP算法與傳統DV-HOP算法及文獻[19]中的RWDV-HOP算法進行比較。無線傳感器網絡區域面積為100*100m2，節點個數為100，節點隨機分布，錨節點通信半徑個數分別選取2、3、4。實驗主要由兩部分組成，分別變換錨節點比例及通信半徑大小，每次實驗重復200次，取平均值作為最后定位誤差。為評估算法的精確度和穩定性，將定位誤差Error作為評估標準。

[Error=i=1N（xi-xi）2+（yi-yi）2NR]? ? ? （19）

式（19）中，N為未知節點數目，[（xi，yi）]為未知節點估計位置，[（xi，yi）]是未知節點真實位置。

3.1 錨節點比例對定位誤差的影響

圖1為R=35m時定位誤差與錨節點比例的關系，可以看出，定位誤差隨錨節點比例的增大而不斷降低，當錨節點比例超過0.2后，定位誤差則下降緩慢。在R=35m，錨節點比例為0.2時，DV-Hop算法定位誤差為30.96%，RWDV-HOP2、RWDV-HOP3、RWDV-HOP4算法定位誤差分別為25.80%、19.77%、17.66%，RWHDV-HOP2、RWHDV-HOP3、RWHDV-HOP4算法定位誤差分別為12.71%、8.93%、7.32%。RWHDV-HOP算法定位精度遠高于DV-Hop與RWDV-HOP算法。

圖1 R=35m時錨節點比例與定位誤差

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

圖2為錨節點n=15時定位誤差與錨節點比例的關系，由圖中可以清楚地看出，隨著通信半徑不斷增大，定位誤差也不斷降低。當通信半徑超過50m后，定位誤差則下降緩慢。在R=50m，錨節點比例為0.15時，DV-HOP算法定位誤差為29.52%，RWDV-HOP2、RWDV-HOP3、RWDV-HOP4算法定位誤差分別為19.07%、13.35%、11.05%，RWHDV-HOP2、RWHDV-HOP3、RWHDV-HOP4算法定位誤差分別為11.00%、7.77%、6.25%。RWHDV-HOP算法定位精度遠高于DV-HOP和RWDV-HOP算法。

圖2 通信半徑與定位誤差 錨節點=15

4 結語

本文針對經典DV-HOP算法存在的不足進行分析，并針對算法的每個階段進行優化，首先利用多通信半徑進行跳數小數化，優化跳距使其更接近真實值。計算未知節點到錨節點距離時，不再只考慮距離最近錨節點的影響，而是將對應的錨節點跳距考慮進去，最后通過基于跳數加權的雙曲線算法進行未知節點定位，從而使定位精度得到了很大提高。但使用多通信半徑在一定程度上會造成通信損耗，下一階段考慮將RSSI算法與DV-HOP算法相結合，以克服跳數引起的誤差。

參考文獻：

[1] LI J，ZHANG J，XIANDE L. A weighted DV-Hop localization scheme for wireless sensor networks[C]. Dalian：International Conference on Scalable Computing & Communications/Eighth International Conference on Embedded Computing，2009.

[2] LEE S W，LEE D Y，LEE C W. Enhanced DV-Hop algorithm with reduced hop-size error in ad hoc networks[J].? IEICE Transactions on Communications， 2011 （7）：2130-2132.

[3] TOMIC S，MEZEI I. Improvements of DV-Hop localization algorithm for wireless sensor networks[J].? Telecommunication Systems， 2016， 61（1）：93-106.

[4] 李娟，劉禹，錢志鴻. 基于雙通信半徑的傳感器網DV-Hop定位算法[J]. 吉林大學學報：工學版，2014，44（2）：502-507.

[5] 黃炎炎，陳向東，倪進權，等. 改進的DV-Hop無線傳感器網絡定位算法[J]. 通信技術，2014，47（7）：765-769.

[6] 張愛清，葉新榮，胡海峰，等. 基于RSSI每跳分級和跳距修正的DV-HOP改進算法[J]. 儀器儀表學報，2012，33（11）：2552-2559.

[7] 趙菊敏，李燈熬，武健. 基于DV-hop定位的誤差加權改進算法[J]. 自動化儀表，2014，35（7）：1-4.

[8] LIAO W H，SHIH K P，LEE Y C. A localization protocol with adaptive power control in wireless sensor networks[J]. Computer Communications，2008，31：2496-2504.

[9] WU H，GAO R. An improved method of DV-Hop localization algorithm[J]. Journal of Computational Information Systems，2011：2293-2298.

[10] 黃艷，臧傳治，于海斌. 基于改進粒子群優化的無線傳感器網絡定位算法[J]. 控制與決策，2012，27（1）：156-160.

[11] 林雯，張烈平，王守峰. 基于差分進化算法的無線傳感器網絡節點定位方法研究[J]. 計算機測量與控制，2013，21（7）：2023-2026.

[12] CUI L，CHONG X，LI G，et al. A high accurate localization algorithm with DV-Hop and differential evolution for wireless sensor network[J].? Applied Soft Computing，2018， 68：S1568494618301595.

[13] CHEIKHROUHOU O，G M B，ALROOBAEA R. A hybrid DV-Hop algorithm using RSSI for localization in large-scale wireless sensor networks[J].? Sensors， 2018， 18（5）：1469.

[14] YAN X，SUN L，ZHOU J，et al. DV-hop localisation algorithm based on optimal weighted least square in irregular areas[J]. Electronics Letters， 2018， 54（21）：1243-1245.

[15] GUI L， VAL T， WEI A， et al. Improvement of range-free localization technology by a novel DV-hop protocol in wireless sensor networks[J]. Ad Hoc Networks， 2015， 24：55-73.

[16] LI X， YAN L， WEI P， et al. Optimization of DV-hop localization algorithm in hybrid optical wireless sensor networks[J].? Journal of Heuristics， 2015， 21（2）：177-195.

[17] MAUNG N，KAWAI M. Experimental evaluationsof RSSI threshold-based optimised DV-HOP localisation for wireless ad-hoc networks[J].? Electronics Letters， 2014， 50（17）：1246-1248.

[18] 譚博，車進，張成. 基于最小二乘優化的加權DV-Hop改進算法[J]. 計算機工程與應用， 2015， 51（2）：82-86.

[19] 劉士興，黃俊杰，劉宏銀，等. 基于多通信半徑的加權DV-Hop定位算法[J]. 傳感技術學報，2015，28（6）：883-887.

[20] 高美鳳，李鳳超. 遺傳粒子群優化的DV-Hop定位算法[J]. 傳感技術學報，2017，30（7）：1084-1088.

（責任編輯：黃 健）