跳數(shù)和跳距修正的距離向量跳段定位改進(jìn)算法

孫利娟　胡鳳啟

摘 要： 由于在無線傳感網(wǎng)絡(luò)中傳感節(jié)點(diǎn)隨機(jī)分布，致使距離向量跳段（DV?Hop）定位算法的定位誤差偏大，為此，采用跳數(shù)和跳距修正的方法對(duì)距離向量跳段定位算法進(jìn)行改進(jìn)。在計(jì)算信標(biāo)節(jié)點(diǎn)和未知節(jié)點(diǎn)跳數(shù)的過程中引入節(jié)點(diǎn)通信距離的影響，使得節(jié)點(diǎn)之間的實(shí)際跳數(shù)計(jì)算更加準(zhǔn)確；再利用線性搜索算法獲取最優(yōu)信標(biāo)節(jié)點(diǎn)間的平均跳距，使信標(biāo)節(jié)點(diǎn)的平均跳距更加精確。對(duì)比仿真實(shí)驗(yàn)結(jié)果表明，改進(jìn)算法大大提升了定位的精度，提升幅度高達(dá)15%。

關(guān)鍵詞： DV?Hop算法； 無線傳感器網(wǎng)絡(luò)； 跳數(shù)； 平均跳距； 定位精度

中圖分類號(hào)： TN711?34； TP393 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2017）07?0001?04

Improved DV?Hop localization algorithm based on hop count and hop distance modification

SUN Lijuan1， 2， HU Fengqi3

（1. School of Computer Science， Wuhan University， Wuhan 430072， China；

2. Department of Information and Electronics， Kaifeng Vocational College of Culture and Arts， Kaifeng 475000， China；

3. Hydrology and Water Resources Bureau of Henan Province， Zhengzhou 450003， China）

Abstract： The positioning error of the DV?Hop localization algorithm is big due to the sensing node′s random distribution existing in the wireless sensor network. Therefore the hop count and hop distance modification method is used to improve the DV?Hop localization algorithm. The node communication distance is introduced in the process of calculating the hop count of the beacon node and unknown node to make the actual hop count between the nodes more accurate. The linear search algorithm is used to obtain the average hop distance of the optimal beacon node to make the average hop distance of the beacon node more accurate. The comparative simulation results show that the algorithm has improved the positional accuracy greatly， and its accuracy is increased by 15%.

Keywords： DV?Hop algorithm； wireless sensor network； hop count； average hop distance； positional accuracy

0 引 言

無線傳感器網(wǎng)絡(luò)（WSN）是由大量節(jié)點(diǎn)形成的一種具有無線自組織能力的動(dòng)態(tài)網(wǎng)絡(luò)[1?2]。如何獲取無線傳感節(jié)點(diǎn)的位置信息是實(shí)現(xiàn)無線傳感網(wǎng)絡(luò)監(jiān)控、跟蹤和目標(biāo)識(shí)別等應(yīng)用的難點(diǎn)。節(jié)點(diǎn)位置信息可以在網(wǎng)絡(luò)中進(jìn)行規(guī)劃，動(dòng)態(tài)的節(jié)點(diǎn)大多采用定位模塊獲取[3?4]。但上述方法會(huì)嚴(yán)重消耗節(jié)點(diǎn)有限的能量，降低整體網(wǎng)絡(luò)壽命。因此，通常在部分節(jié)點(diǎn)中安裝定位模塊并將它們視為信標(biāo)節(jié)點(diǎn)，其他未知節(jié)點(diǎn)根據(jù)相應(yīng)的節(jié)點(diǎn)定位算法來估計(jì)其位置[5?7]。DV?Hop（Distance Vector?Hop）算法是一種距離無關(guān)算法，但存在定位誤差大的問題，文獻(xiàn)[8]提出使用RSSI（Received Signal Strength Indicator）技術(shù)對(duì)節(jié)點(diǎn)間的跳數(shù)進(jìn)行優(yōu)化，但引入了RSSI測(cè)量模塊，復(fù)雜度過高，不利于無線傳感網(wǎng)廣泛部署；文獻(xiàn)[9]分析了無線傳感器網(wǎng)絡(luò)中DV?Hop算法存在的缺陷，并利用量化模型表示誤差，最后利用加權(quán)修正節(jié)點(diǎn)位置。然而這些改進(jìn)算法依然存在算法復(fù)雜度較高，不利于資源受限的節(jié)點(diǎn)部署。本文通過對(duì)DV?Hop算法同時(shí)進(jìn)行跳數(shù)和平均跳距的修正，之后對(duì)信標(biāo)節(jié)點(diǎn)利用線性搜索算法獲得準(zhǔn)確的最佳平均跳距。實(shí)驗(yàn)結(jié)果表明，本文改進(jìn)算法在定位精度和性能上都有了較大的提高。

1 距離向量跳段算法及誤差分析

1.1 DV?Hop 定位算法

DV?Hop定位算法首先由節(jié)點(diǎn)的通信半徑獲得節(jié)點(diǎn)間的跳數(shù)；然后每個(gè)節(jié)點(diǎn)記錄其毗鄰的信標(biāo)節(jié)點(diǎn)的平均跳距；最后每個(gè)節(jié)點(diǎn)根據(jù)以上信息分布式地計(jì)算各自的位置信息。DV?Hop定位算法過程主要有以下三步：

Step1： 利用網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)在網(wǎng)絡(luò)中廣播一條距離矢量消息。這樣網(wǎng)絡(luò)中任意兩個(gè)信標(biāo)節(jié)點(diǎn)之間的最小跳數(shù)（節(jié)點(diǎn)間的平均跳數(shù)）就能夠被記錄下來，簡(jiǎn)略地估計(jì)了節(jié)點(diǎn)之間的空間關(guān)系。

Step2： 計(jì)算節(jié)點(diǎn)平均跳距。由于信標(biāo)節(jié)點(diǎn)的坐標(biāo)已知，利用信標(biāo)節(jié)點(diǎn)之間的跳數(shù)和距離計(jì)算信標(biāo)節(jié)點(diǎn)的平均跳距。該平均跳距通過廣播協(xié)議在網(wǎng)絡(luò)中傳播，以使每個(gè)未知節(jié)點(diǎn)都能夠近似地估計(jì)其與其他節(jié)點(diǎn)之間的距離[10]。設(shè)信標(biāo)節(jié)點(diǎn)[i]和[j]的坐標(biāo)分別為[（xi，yi）]和[（xj，yj），]之間的最小跳數(shù)為[hj。]信標(biāo)節(jié)點(diǎn)[i]的平均跳距公式表示為：

[HopSizei=j≠i（xi-xj）2+（yi-yj）2j≠ihj] （1）

在平均跳距的傳播過程中，為使得未知節(jié)點(diǎn)所存儲(chǔ)的跳距信息來自距離其最近的信標(biāo)節(jié)點(diǎn)[i，]各未知節(jié)點(diǎn)僅存儲(chǔ)初次收到的平均跳距。由于是廣播方式傳輸平均跳距信息，距未知節(jié)點(diǎn)遠(yuǎn)的平均跳距信息必定延遲于較近的。因此，未知節(jié)點(diǎn)所存儲(chǔ)的平均跳距信息必定來自其毗鄰的信標(biāo)節(jié)點(diǎn)。此時(shí)，未知節(jié)點(diǎn)[u]到任意信標(biāo)節(jié)點(diǎn)[j]的距離可以通過下式獲得：

[duj=HopSizei*hj] （2）

Step3： 估計(jì)未知節(jié)點(diǎn)坐標(biāo)。采用各信標(biāo)節(jié)點(diǎn)提供的跳數(shù)和平均跳距信息估計(jì)未知節(jié)點(diǎn)的位置。最為常用的估計(jì)方法為極大似然法[11]。該算法的計(jì)算過程如下：假設(shè)未知節(jié)點(diǎn)處于[（xu，yu），]根據(jù)估計(jì)距離可得如下的系統(tǒng)方程：

[（x1-xu）2-（y1-yu）2=d2u1（x2-xu）2-（y2-yu）2=d2u2…（xn-xu）2-（yn-yu）2=d2un] （3）

通過式（3），利用最小二乘法可以獲得未知節(jié)點(diǎn)的位置信息，實(shí)現(xiàn)定位。

1.2 誤差分析

通過對(duì)DV?Hop算法的原理分析可知，該算法的定位精度受很多因素的影響。

首先，該方法假定節(jié)點(diǎn)間的通信距離均為1跳，如圖1所示。未知節(jié)點(diǎn)1，2到信標(biāo)節(jié)點(diǎn)A的跳數(shù)都是1跳，實(shí)際上它們到信標(biāo)節(jié)點(diǎn)的實(shí)際距離相差很大，這就不能較好地反應(yīng)出節(jié)點(diǎn)之間的實(shí)際距離關(guān)系。由此獲取的最小跳數(shù)信息對(duì)實(shí)際平均跳距產(chǎn)生誤差，最終會(huì)對(duì)未知節(jié)點(diǎn)的定位精度產(chǎn)生影響。

其次，該算法中平均跳距信息的來源過于單一。由于無線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)的分布是隨機(jī)、不均勻的，原始算法中使用的毗鄰未知節(jié)點(diǎn)的信標(biāo)節(jié)點(diǎn)不能表征節(jié)點(diǎn)分布的隨機(jī)性和不均勻性。因此，本文首先對(duì)未知節(jié)點(diǎn)間的跳數(shù)信息進(jìn)行修正，使之更接近實(shí)際跳數(shù)值；再對(duì)信標(biāo)節(jié)點(diǎn)進(jìn)行重新定位，并運(yùn)用線性搜索算法對(duì)信標(biāo)節(jié)點(diǎn)的平均跳距進(jìn)行修正，獲得信標(biāo)節(jié)點(diǎn)的最佳平均跳距。

2 算法的改進(jìn)

2.1 修正信標(biāo)節(jié)點(diǎn)之間的跳數(shù)

DV?Hop 定位算法在計(jì)算兩個(gè)節(jié)點(diǎn)之間的跳數(shù)時(shí)，并未考慮每跳的通信距離[9]，如圖2所示。

假設(shè)所有節(jié)點(diǎn)的通信距離為信標(biāo)節(jié)點(diǎn)3和4之間的距離。信標(biāo)節(jié)點(diǎn)1和4之間由于節(jié)點(diǎn)分布的不均勻性，其每條距離與通信距離相差較大。其中，第1跳遠(yuǎn)小于通信距離。DV?Hop算法定位時(shí)仍將兩信標(biāo)節(jié)點(diǎn)之間的最小跳數(shù)記為3跳，并據(jù)此進(jìn)行位置估計(jì)，其估計(jì)結(jié)果受到每條距離不同的影響，偏差較大。

本文使用通信距離信息對(duì)跳數(shù)信息進(jìn)行修正。記信標(biāo)節(jié)點(diǎn)之間的理想跳數(shù)為[Hij=dijR，]其為信標(biāo)節(jié)點(diǎn)之間實(shí)際距離與節(jié)點(diǎn)的通信距離之比。引入偏離因子對(duì)跳數(shù)進(jìn)行修正，其表達(dá)式為：

[lij=hij-Hijhij] （4）

式中：[lij]越小，表示信標(biāo)節(jié)點(diǎn)[i]和[j]之間的實(shí)際跳數(shù)越接近于理想跳數(shù)；跳數(shù)修正系數(shù)表示為[θij=1-lnij，][n]取正整數(shù)。

在DV?Hop算法中，由于在根據(jù)跳數(shù)和平均跳距信息計(jì)算未知節(jié)點(diǎn)的位置時(shí)，所得結(jié)果均存在約為0.5倍通信距離的誤差。因此，在基于通信距離進(jìn)行跳數(shù)修正時(shí)，要考慮0.5倍的通信距離誤差，最終修正的信標(biāo)節(jié)點(diǎn)之間的跳數(shù)計(jì)算公式為：

[h′ij=θij*hij-0.5] （5）

通過實(shí)驗(yàn)結(jié)果表明，修正系數(shù)在[n=2]時(shí)定位誤差最小。

2.2 修正未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)間的跳數(shù)

（1） 未知節(jié)點(diǎn)[u]距其最近信標(biāo)節(jié)點(diǎn)[i]的跳數(shù)：

[h′ui=huin-1i≠jnθij-0.5] （6）

式中：[n]為信標(biāo)節(jié)點(diǎn)總數(shù)，[qij]為上一節(jié)設(shè)計(jì)的修正系數(shù)；[hui]為由式（2）估計(jì)的未知節(jié)點(diǎn)的跳數(shù)信息。此外，考慮了通信距離對(duì)跳數(shù)信息估計(jì)的影響，引入了0.5倍通信距離的修正系數(shù)。

（2） 未知節(jié)點(diǎn)[u]到信標(biāo)節(jié)點(diǎn)[j]的跳數(shù)：

[h′uj=θij*huj-0.5] （7）

式中：[θij]為上一節(jié)設(shè)計(jì)的修正系數(shù)；[huj]為DV?Hop算法中使用的實(shí)際跳數(shù)。

在式（7）中引入0.5倍通信距離來改進(jìn)跳數(shù)估計(jì)。由式（6）和式（7）可以看出，用偏離因子和0.5倍的通信距離來修正跳數(shù)，能夠充分利用所有信標(biāo)節(jié)點(diǎn)的跳數(shù)信息和節(jié)點(diǎn)通信能力，更能反映整個(gè)網(wǎng)絡(luò)的節(jié)點(diǎn)分布情況。

2.3 修正信標(biāo)節(jié)點(diǎn)的平均跳距

為了使信標(biāo)節(jié)點(diǎn)的平均跳距計(jì)算的更加精確，把所有的信標(biāo)節(jié)點(diǎn)當(dāng)作未知節(jié)點(diǎn)進(jìn)行重新定位。信標(biāo)節(jié)點(diǎn)[i]的平均每跳跳距（AHS）定義如下：

[AHSi=i≠jnHopsizein-1] （8）

式中：[n]為信標(biāo)節(jié)點(diǎn)總數(shù)；[Hopsizei]為原始DV?Hop算法Step2中計(jì)算的到各個(gè)信標(biāo)節(jié)點(diǎn)的平均每跳距離；信標(biāo)節(jié)點(diǎn)[i]和[j]之間的估計(jì)距離[dij=AHS*h′ij，]其中[h′ij]是信標(biāo)節(jié)點(diǎn)[i]和[j]之間修正后的跳數(shù)。

最后用最大似然法計(jì)算出信標(biāo)節(jié)點(diǎn)[i]的估計(jì)位置。設(shè)信標(biāo)節(jié)點(diǎn)[i]的位置為[（xi，yi），]利用改進(jìn)算法得未知節(jié)點(diǎn)坐標(biāo)為[（xi，yi），]信標(biāo)節(jié)點(diǎn)[i]的定位誤差為：

[ei=（xi-xi）2+（yi-yi）2] （9）

所有信標(biāo)節(jié)點(diǎn)的平均定位誤差為：

[ea=i=1nein] （10）

利用線性搜索算法對(duì)信標(biāo)節(jié)點(diǎn)的平均跳距進(jìn)行修正，獲取信標(biāo)節(jié)點(diǎn)的最佳平均跳距修正量，如圖3所示。

在最低點(diǎn)時(shí)所有信標(biāo)節(jié)點(diǎn)的平均定位誤差最小，此時(shí)的ΔAHS就是最佳跳距修正量。信標(biāo)節(jié)點(diǎn)[i]的最佳平均每跳距離為：

式中：ΔAHSoptimum為最佳的跳距修正量。

采用式（2）計(jì)算出未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)之間的位置關(guān)系，聯(lián)立求解方程（3）即可得出未知節(jié)點(diǎn)的位置。

3 改進(jìn)算法仿真結(jié)果及分析

為了檢驗(yàn)改進(jìn)算法的性能，本文對(duì)改進(jìn)算法、文獻(xiàn)[10]的改進(jìn)算法和原始DV?Hop算法進(jìn)行實(shí)驗(yàn)比較?？疾斓膮^(qū)域?yàn)?00 m的正方形區(qū)域，無線傳感節(jié)點(diǎn)均勻分布。記無線傳感網(wǎng)中未知節(jié)點(diǎn)數(shù)為[N，]信標(biāo)節(jié)點(diǎn)數(shù)為[n，]每個(gè)節(jié)點(diǎn)通信距離均為[R。]每次結(jié)果統(tǒng)計(jì)在相同節(jié)點(diǎn)分布下進(jìn)行[K=100]次獲得。為對(duì)比三種算法的性能，分別從信標(biāo)節(jié)點(diǎn)個(gè)數(shù)、總節(jié)點(diǎn)個(gè)數(shù)和通信半徑這三個(gè)方面對(duì)歸一化后的定位誤差影響進(jìn)行仿真。圖4給出了[N=100，][R=20，][n]依次從10增加到50時(shí)，平均定位誤差同信標(biāo)節(jié)點(diǎn)數(shù)之間的變化曲線。

從圖4中可以看出，本文改進(jìn)算法與對(duì)比算法的平均定位誤差均隨著信標(biāo)節(jié)點(diǎn)個(gè)數(shù)的增加而減少，這是由于較多的信標(biāo)節(jié)點(diǎn)使得跳數(shù)和平均跳距計(jì)算更加準(zhǔn)確。而本文改進(jìn)算法對(duì)定位誤差的減少更加明顯。相比于原始DV?Hop算法和文獻(xiàn)[10]中的方法，本文方法分別能減少約12%～15%和2%～3%左右。

假設(shè)信標(biāo)節(jié)點(diǎn)數(shù)目站總節(jié)點(diǎn)數(shù)目固定為[15，][R=]20，圖5給出了[n]從100增加到200三種算法的估計(jì)誤差率。

從圖5中得出：隨著總節(jié)點(diǎn)數(shù)量的不斷增大，平均定位誤差會(huì)逐漸減小，這是由于總節(jié)點(diǎn)數(shù)目增多，通信距離在跳數(shù)和平均估計(jì)中的影響減小。但本文改進(jìn)算法相比于原始DV?Hop算法和文獻(xiàn)[10]的改進(jìn)方案額外分別獲得了約14%～18%和2.5%的估計(jì)精度。圖6則考察了通信距離對(duì)估計(jì)精度的影響。仿真條件為[N=100，][n=20。]

從圖6中可以看出：三種歸一化算法的定位誤差均隨著通信距離[R]的增大而減少。而本文的算法在進(jìn)行跳數(shù)和平均跳距的估計(jì)時(shí)，采用0.5倍通信距離進(jìn)行修正。改進(jìn)算法的定位性能相比于文獻(xiàn)[10]中的方法有了明顯的提升，提升比例約為4%左右。

4 結(jié) 語

本文通過對(duì)跳數(shù)和平均跳距進(jìn)行修正來減小定位誤差。針對(duì)通信范圍內(nèi)節(jié)點(diǎn)間的跳數(shù)為1跳并且都是整數(shù)的現(xiàn)象，提出基于通信半徑并綜合考慮0.5倍的通信距離誤差來對(duì)跳數(shù)進(jìn)行修正，使得節(jié)點(diǎn)間的跳數(shù)估計(jì)更加準(zhǔn)確。對(duì)于信標(biāo)節(jié)點(diǎn)，提出了把信標(biāo)節(jié)點(diǎn)當(dāng)作未知節(jié)點(diǎn)進(jìn)行重新定位并且運(yùn)用線性搜索算法查找信標(biāo)節(jié)點(diǎn)的最佳平均跳距修正量，使信標(biāo)節(jié)點(diǎn)的總平均跳距誤差最小。通過對(duì)比仿真實(shí)驗(yàn)，結(jié)果表明提出的改進(jìn)算法定位精度得到了明顯提升，相比于原始DV?Hop算法精度提升高達(dá)15%。

參考文獻(xiàn)

[1] 陳輝，熊輝，殷昌盛，等.基于無線傳感器網(wǎng)絡(luò)時(shí)鐘同步的定位算法研究[J].現(xiàn)代電子技術(shù)，2015，38（7）：23?27.

[2] 李云飛，江明，婁柯，等.無線傳感器網(wǎng)絡(luò)中DV?Hop定位算法的改進(jìn)[J].計(jì)算機(jī)工程與應(yīng)用，2014，50（3）：79?81.

[3] 王景琿.一種基于DV?Hop的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法[J].計(jì)算機(jī)工程，2015，41（1）：82?86.

[4] ZHANG Y， XIANG S， FU W， et al. Improved normalized collinearity DV?Hop algorithm for node localization in wireless sensor network [J]. International journal of distributed sensor networks， 2014（11）： 1?14.

[5] 程超，錢志鴻，付彩欣，等.一種基于誤差距離加權(quán)與跳段算法選擇的遺傳優(yōu)化DV?Hop定位算法[J].電子與信息學(xué)報(bào)，2015，37（10）：2418?2423.

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

[7] 趙雁航，錢志鴻，尚小航，等.基于跳距修正粒子群優(yōu)化的WSN定位算法[J].通信學(xué)報(bào)，2013，34（9）：105?114.

[8] 溫江濤，范學(xué)敏，吳希軍.基于RSSI跳數(shù)修正的DV?Hop改進(jìn)算法[J].傳感技術(shù)學(xué)報(bào)，2014，27（1）：113?117.

[9] 肖麗萍，劉曉紅.一種基于跳數(shù)修正的DV?Hop定位算法[J].傳感技術(shù)學(xué)報(bào)，2012，25（12）：1726?1730.

[10] 夏少波，鄒建梅，朱曉麗，等.無線傳感器網(wǎng)絡(luò)DV?Hop定位算法的改進(jìn)[J].計(jì)算機(jī)應(yīng)用，2015， 35（2）：340?344.

[11] 李長(zhǎng)庚，劉孟思，孫克輝.基于加權(quán)最小平方法的DV?Hop改進(jìn)算法[J].微電子學(xué)與計(jì)算機(jī)，2016（1）：24?27.

[12] 趙吉，傅毅，王瀚波.改進(jìn)的DV?Hop無線傳感器網(wǎng)絡(luò)定位算法[J].儀表技術(shù)與傳感器，2013（6）：111?114.