武雪姣 李雪晴 丁佳靜

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

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

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

中圖分類號(hào)：TP312 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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é)院碩士研究生，研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)定位。

0 引 言

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

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

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

1 DV-HOP算法

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

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

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

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

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

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

2 改進(jìn)DV-HOP算法描述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[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)則估計(jì)出C。

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

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

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

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

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

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

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

3 實(shí)驗(yàn)仿真分析

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

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

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

3.1 錨節(jié)點(diǎn)比例對(duì)定位誤差的影響

圖1為R=35m時(shí)定位誤差與錨節(jié)點(diǎn)比例的關(guān)系，可以看出，定位誤差隨錨節(jié)點(diǎn)比例的增大而不斷降低，當(dāng)錨節(jié)點(diǎn)比例超過0.2后，定位誤差則下降緩慢。在R=35m，錨節(jié)點(diǎn)比例為0.2時(shí)，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算法定位精度遠(yuǎn)高于DV-Hop與RWDV-HOP算法。

圖1 R=35m時(shí)錨節(jié)點(diǎn)比例與定位誤差

3.2 通信半徑對(duì)定位誤差的影響

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

圖2 通信半徑與定位誤差 錨節(jié)點(diǎn)=15

4 結(jié)語

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

參考文獻(xiàn)：

[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é)報(bào)：工學(xué)版，2014，44（2）：502-507.

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

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

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

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

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

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

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