孫利娟　胡鳳啟

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

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

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

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

1.1 DV?Hop 定位算法

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

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

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

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

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

[duj=HopSizei*hj] （2）

Step3： 估計未知節(jié)點坐標(biāo)。采用各信標(biāo)節(jié)點提供的跳數(shù)和平均跳距信息估計未知節(jié)點的位置。最為常用的估計方法為極大似然法[11]。該算法的計算過程如下：假設(shè)未知節(jié)點處于[（xu，yu），]根據(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é)點的位置信息，實現(xiàn)定位。

1.2 誤差分析

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

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

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

2 算法的改進

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

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

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

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

[lij=hij-Hijhij] （4）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[ea=i=1nein] （10）

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

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

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

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

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

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

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

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

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

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

4 結(jié) 語

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

參考文獻

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

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

[3] 王景琿.一種基于DV?Hop的無線傳感器網(wǎng)絡(luò)節(jié)點定位算法[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é)報，2015，37（10）：2418?2423.

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

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

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

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

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

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

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