一種改進的無線傳感器網(wǎng)絡(luò)DV-HOP定位算法

武雪姣 李雪晴 丁佳靜

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

關(guān)鍵詞：多通信半徑;無線傳感器網(wǎng)絡(luò);跳距優(yōu)化;定位精度;加權(quán)雙曲線算法

DOI：10. 11907/rjdk. 191540 開放科學(xué)（資源服務(wù)）標(biāo)識碼（OSID）：

中圖分類號：TP312 文獻標(biāo)識碼：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-），女，河北地質(zhì)大學(xué)信息工程學(xué)院碩士研究生，研究方向為無線傳感器網(wǎng)絡(luò)定位。

0 引 言

節(jié)點自定位技術(shù)是無線傳感器網(wǎng)絡(luò)領(lǐng)域的重要技術(shù)之一[1-2]。目前大多數(shù)定位系統(tǒng)采用距離無關(guān)的定位算法[3]，DV-HOP算法是其中一種應(yīng)用較為廣泛的算法。

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

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

1 DV-HOP算法

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

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

為了將跳數(shù)轉(zhuǎn)換成距離，需要估計網(wǎng)絡(luò)中平均每跳距離。通過式（1）計算各錨節(jié)點平均跳距。

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

其中，（xi，yi）、（xj，yj）是錨節(jié)點i和j的坐標(biāo)，hij表示錨節(jié)點i和j的最小跳數(shù)，N表示錨節(jié)點數(shù)量，Hopsizei是每個錨節(jié)點的全網(wǎng)平均跳距。

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

2 改進DV-HOP算法描述

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

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

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

第二階段：傳統(tǒng)DV-HOP算法計算錨節(jié)點平均跳距時忽視了錨節(jié)點共線情況，導(dǎo)致跳數(shù)越多，誤差越大。文獻[19]通過跳數(shù)加權(quán)方法對錨節(jié)點平均跳距進行改進，但只考慮了跳數(shù)越多、偏差越大的問題，而沒有從節(jié)點共線度的本質(zhì)上解決問題;文獻[20]通過共線度檢測方式優(yōu)化跳距。

首先計算錨節(jié)點與矩形區(qū)域內(nèi)4個頂點的距離，求出第i個錨節(jié)點在網(wǎng)絡(luò)中理論上的最大跳數(shù)[ki]，去掉與其共線度低的錨節(jié)點，通過將實際跳數(shù)與理想跳數(shù)作差進行權(quán)重計算，最后加權(quán)計算錨節(jié)點跳距[20]。

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

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

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

其中，R表示通信半徑，[wij]表示錨節(jié)點j對錨節(jié)點i的權(quán)重。

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

第三階段：計算未知節(jié)點到錨節(jié)點距離時，將對應(yīng)錨節(jié)點跳距考慮在內(nèi)。

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

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

其中i為未知節(jié)點，j為錨節(jié)點，Hopsizei是距離未知節(jié)點最近的錨節(jié)點跳距，可以由式（7）或式（8）計算未知節(jié)點到錨節(jié)點的距離。綜合考慮網(wǎng)絡(luò)連通情況，將未知節(jié)點到相應(yīng)錨節(jié)點的距離計算公式優(yōu)化為：

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

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

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

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

則公式（9）可以轉(zhuǎn)化為：

[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）

由最小二乘準(zhǔn)則估計出C。

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

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

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

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

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

結(jié)合式（11）、式（13）可得未知節(jié)點坐標(biāo)為：

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

3 實驗仿真分析

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

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

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

3.1 錨節(jié)點比例對定位誤差的影響

圖1為R=35m時定位誤差與錨節(jié)點比例的關(guān)系，可以看出，定位誤差隨錨節(jié)點比例的增大而不斷降低，當(dāng)錨節(jié)點比例超過0.2后，定位誤差則下降緩慢。在R=35m，錨節(jié)點比例為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時錨節(jié)點比例與定位誤差

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

圖2為錨節(jié)點n=15時定位誤差與錨節(jié)點比例的關(guān)系，由圖中可以清楚地看出，隨著通信半徑不斷增大，定位誤差也不斷降低。當(dāng)通信半徑超過50m后，定位誤差則下降緩慢。在R=50m，錨節(jié)點比例為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 通信半徑與定位誤差 錨節(jié)點=15

4 結(jié)語

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

參考文獻：

[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] 李娟，劉禹，錢志鴻. 基于雙通信半徑的傳感器網(wǎng)DV-Hop定位算法[J]. 吉林大學(xué)學(xué)報：工學(xué)版，2014，44（2）：502-507.

[5] 黃炎炎，陳向東，倪進權(quán)，等. 改進的DV-Hop無線傳感器網(wǎng)絡(luò)定位算法[J]. 通信技術(shù)，2014，47（7）：765-769.

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

[7] 趙菊敏，李燈熬，武健. 基于DV-hop定位的誤差加權(quán)改進算法[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] 黃艷，臧傳治，于海斌. 基于改進粒子群優(yōu)化的無線傳感器網(wǎng)絡(luò)定位算法[J]. 控制與決策，2012，27（1）：156-160.

[11] 林雯，張烈平，王守峰. 基于差分進化算法的無線傳感器網(wǎng)絡(luò)節(jié)點定位方法研究[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] 譚博，車進，張成. 基于最小二乘優(yōu)化的加權(quán)DV-Hop改進算法[J]. 計算機工程與應(yīng)用， 2015， 51（2）：82-86.

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

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

（責(zé)任編輯：黃 健）