跳數和跳距修正的距離向量跳段定位改進算法

孫利娟　胡鳳啟

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

關鍵詞： DV?Hop算法； 無線傳感器網絡； 跳數； 平均跳距； 定位精度

中圖分類號： TN711?34； TP393 文獻標識碼： 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 引 言

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

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

1.1 DV?Hop 定位算法

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

Step1： 利用網絡的拓撲結構在網絡中廣播一條距離矢量消息。這樣網絡中任意兩個信標節點之間的最小跳數（節點間的平均跳數）就能夠被記錄下來，簡略地估計了節點之間的空間關系。

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

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

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

[duj=HopSizei*hj] （2）

Step3： 估計未知節點坐標。采用各信標節點提供的跳數和平均跳距信息估計未知節點的位置。最為常用的估計方法為極大似然法[11]。該算法的計算過程如下：假設未知節點處于[（xu，yu），]根據估計距離可得如下的系統方程：

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

通過式（3），利用最小二乘法可以獲得未知節點的位置信息，實現定位。

1.2 誤差分析

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

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

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

2 算法的改進

2.1 修正信標節點之間的跳數

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

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

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

[lij=hij-Hijhij] （4）

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

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

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

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

2.2 修正未知節點與信標節點間的跳數

（1） 未知節點[u]距其最近信標節點[i]的跳數：

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

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

（2） 未知節點[u]到信標節點[j]的跳數：

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

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

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

2.3 修正信標節點的平均跳距

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

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

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

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

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

所有信標節點的平均定位誤差為：

[ea=i=1nein] （10）

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

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

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

采用式（2）計算出未知節點與信標節點之間的位置關系，聯立求解方程（3）即可得出未知節點的位置。

3 改進算法仿真結果及分析

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

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

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

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

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

4 結 語

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

參考文獻

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

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

[3] 王景琿.一種基于DV?Hop的無線傳感器網絡節點定位算法[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] 程超，錢志鴻，付彩欣，等.一種基于誤差距離加權與跳段算法選擇的遺傳優化DV?Hop定位算法[J].電子與信息學報，2015，37（10）：2418?2423.

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

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

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

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

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

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

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