無線傳感器網絡DV-HOP定位算法的改進*

李 輝，熊盛武，劉 毅，段鵬飛

(武漢理工大學計算機科學與技術學院，武漢430070)

無線傳感器網絡［1－4］集傳感器技術、微機電系統技術、無線通信技術、嵌入式計算技術和分布式信息處理技術于一體，通過傳感器與外界交互，并完成數據采集、處理及通信等功能，廣泛應用于環境、交通、軍事、航空、醫療衛生等多方面。而對于大多數應用來說，沒有時空標識的數據用處有限，因此，節點的準確定位在傳感器網絡的應用中起關鍵作用［5］。

現有的定位算法大致可分為兩類:距離相關定位算法 (Range-based)［6］和距離無關定位算法(Range-free)［7］。距離相關定位算法通過測量距離角度等信息來進行定位，對硬件要求較高且成本較高，這與無線傳感器網絡的硬件要求簡單和能量消耗受限不相適應.。而距離無關算法不需要使用測距技術，只利用節點間的估計距離來計算未知節點的位置，因此由于傳感器節點能源、成本、體積等因素的限制，距離無關定位算法具有更高的實用性。

文中首先描述DV-Hop定位算法的基本原理和誤差產生的原因，然后針對DV-Hop算法和目前已有的改進算法的不足，提出了改進的無線傳感器網絡DV-Hop定位算法(IDV-Hop定位算法)，最后將IDV-Hop與傳統的DV-Hop算法和已有改進算法進行分析比較，仿真結果表明，本文提出的IDV-Hop定位算法進一步提高了定位精度。

1 DV-Hop定位算法誤差分析

DV-Hop定位算法［8－9］是一種基于距離矢量計算跳數的算法，其基本思想是將未知節點到信標節點之間的距離用平均每跳距離和兩者之間跳數的乘積表示，使用三邊定位法或最大似然估計法獲得未知節點位置信息。

1.1 誤差分析

由DV-Hop定位算法的原理可知，該算法的主要誤差在于計算未知節點與信標節點之間的估計距離時，是用跳數乘以平均每跳距離來表示，而當網絡中的跳數大于或等于2跳時，未知節點和信標節點之間的實際距離與平均每跳距離所得的值存在較大的誤差，會使定位精度下降。

圖1 信標節點與未知節點距離示意圖

信標節點L1與未知節點A的實際距離(粗虛線)用跳數乘以平均每跳距離(細虛線)代替，此時，會產生較大誤差。因此，針對傳統DV-Hop算法的缺點，文獻［10］對算法的改進主要是在第2階段，當每個信標節點計算出自已的平均每跳距離以后，將自已的平均每跳距離作為一個校正值廣播至網絡中。廣播的數據分組格式為{idi，Ci}，Ci是第i信標節點計算出的平均每跳距離。每個接收到此數據分組的節點將該信息添加到自已的數據表中，然后繼續向其鄰居廣播，重復id的信息分組將被丟棄。經過此階段的廣播后，所有節點都已知所有信標節點的平均每跳距離，然后再將所有的平均每跳距離相加取平均，得到整個網絡的平均每跳距離為:

其中:Ci是第i個信標節點計算的平均每跳距離;n為網絡中的信標節點總數。

之后，每個未知節點計算到自已數據表中的各信標節點的距離為:

2 IDV-Hop定位算法

在文獻［10］中，利用整個網絡信標節點的平均每跳距離代替原始算法中最近信標節點的平均每跳距離，從而使未知節點計算到各信標節點之間的估計距離更接近實際距離，使得改進算法的平均定位精度得到提高，但是所有未知節點都用一個全網平均每跳距離，這樣計算出的未知節點到信標節點的距離與實際距離仍存在誤差。針對此問題，本文對未知節點計算到信標節點距離時，所用到的平均每跳距離做了進一步改進。

2.1 前提假設

為了討論方便，本文做出如下假設:

(1)每個傳感器節點有唯一的ID，傳感器節點被隨機部署;

(2)空間信號傳輸模型為理想的球體;

(3)所有傳感器節點都是一樣的，電量和計算能力有限;

(4)信標節點能夠通過GPS接受裝置或其他手段［11－12］即時地獲取二維坐標信息;

(5)所有傳感器節點和錨節點是時間同步的。

2.2 IDV-Hop定位算法描述

2.2.1 計算最小跳數

首先，所有信標節點向網絡廣播消息，消息中包括表{Xi，Yi，HopCount}，信標節點只與網絡中鄰近的節點交換信息。Xi，Yi是信標節點的坐標，HopCount是節點接收到廣播消息信標節點的跳數，初始值設為0。當某個節點接收到這個表的消息，將HopCount值加1后繼續向它的鄰居廣播(除了來源方向)，如果某節點接收到來自相同信標節點的多個消息，則表明它到該信標節點有多條路徑。此時，節點將保留含有最小跳數值的信標，而忽略其他信標，這就保證了所得到的跳數值是它到信標節點的最短路徑。最終，經過這個過程，只要整個網絡是連通圖，網絡中的所有節點都能獲得各信標節點的坐標以及它到各信標節點的最短距離，也就是跳數。

2.2.2 計算未知節點和信標節點的距離

按照DV-Hop算法中第二階段，每個信標節點計算出自已的平均每跳距離，即校正值，然后未知節點首先按文獻［10］的方法計算出全網平均每跳距離Average(如式1所示)，之后得出信標節點i的平均每跳距離誤差，如式(3):

其中，節點j為信標節點i數據表中的其他信標節點;|dtrueij－destimatedij|表示信標節點 i、j之間實際距離與計算距離之差的絕對值;anchor_to_anchorij表示信標節點i到信標節點j的最小跳數

最終，信標節點i的平均每跳距離，即校正值為:

其中，k為變量參數，k的取值根據具體的網絡環境而定。

這樣，各信標節點將自已按式5計算出的平均每跳距離anchor(i)作為一個校正值廣播至網絡中，校正值采用可控洪泛法在網絡中傳播，這意味著未知節點僅接受獲得的第1個校正值，而丟棄所有后來者，這個策略確保了絕大多數未知節點可從最近的信標節點接收校正值。

最終，每個未知節點計算到自已數據表中的各個信標節點的估計距離為:

其中，anchor(i)為未知節點i獲得的最近的信標節點校正值，hopij為未知節點i到信標節點j的最小跳數。

2.2.3 計算未知節點坐標

在傳統DV-Hop定位算法中，未知節點利用記錄3個以上到各個信標節點的距離值，通過三邊測量法或極大似然估計法計算未知節點的坐標，而對于在其通信范圍內少于3個信標節點的未知節點沒有進行處理，從而造成有些節點無法定位。在IDV-Hop定位算法中對出現的這些節點也進行了處理，方法如下:

(1)當k大于或等于3時，設某未知節點在其通信范圍內可參考的信標節點數為k，未知節點A通信范圍內的信標節點為P1、P2、P3…Pk，取離未知節點A最近的3個信標節點P1、P2、P3。則:

①當向量P1P2和向量P2P3的笛卡爾乘積為0時，說明3個信標節點在同一直線，此時去掉信標節點P1、P2、P3中離節點A最遠的一個，重新選取除節點P1、P2、P3以外距離節點 A較近的信標節點 P4，然后返回①中重新判斷，直到未知節點參考的3個信標節點不在同一直線。

②當向量P1P2和向量P2P3的笛卡爾乘積不為0時，利用二維定位算法中的最小二乘法來求出未知節點的近似坐標，方法如下:設3個信標節點坐標P1(x1，y1)，P2(x2，y2)，P3(x3，y3)，未知節點離各錨節點的距離分別是 d1，d2，d3，建立方程組:

因為未知節點與信標節點的距離，避免不了和實際距離di有一定的誤差，設ξ是距離測量誤差，整理可得是 k－1維隨機誤差向量。由矩陣方程可得ξ=b－Ax，ξ越小，定位越準確，利用最小二乘法原理可以求出待測節點坐標的估計式:

(2)當K等于2時，未知節點與兩個錨節點在一個平面上(設未知節點為P，兩個錨節點為N0，N1)，則分別以N0，N1為圓心，以N0P，N1P為半徑的兩圓相交，如果交于一點時，則為所求的P點;如果交于兩點(x1，y1)和(x2，y2)，則取為P點。

2.3 算法分析

根據IDV-Hop算法的實現過程，對其通信開銷能耗進行分析，結果如下:

算法采取可控的洪泛過程，每個節點只轉發相同的消息一次，每個錨節點共發3次消息，其中包括(1)錨節點向鄰居節點廣播自身位置信息;(2)各錨節點將自已的平均每跳距離作為一個校正值廣播至網絡;(3)各錨節點將自已修正后的校正值廣播至網絡中。這些消息被所有節點轉發一次，假設一共有m個錨節點，n個未知節點，則網內的消息量為(3·m·n)packets。

3 實驗仿真及分析

為了驗證本文IDV-Hop定位算法的可行性和有效性，對算法進行仿真實驗，并將DV-Hop算法、已有改進算法和本文IDV-Hop定位算法的仿真結果進行了對比分析。

3.1 仿真環境和參數

實驗在 MATLAB 2009 的環境下進行［13－14］，網絡中共有300個傳感器節點隨機地布設在1 000 m×1 000 m的二維區域內，錨節點比例為20%，采用隨機布撒的方式，所有節點的分布如圖2所示，此時網絡的平均連通度為31.893 3，網絡的鄰居信標節點平均數目為6.553 3。在實驗中，假定所有未知節點和錨節點的通信半徑為200 m，信道衰減指數為4，運行50次。

圖2 節點隨機分布圖

3.2 性能分析與比較

圖3比較了改進算法中變量k的不同取值對算法定位精度的影響。從圖可以看出，當節點總數和信標節點數均恒定的情況下，定位精度取決于變量參數k的值;當變量參數k的值為定值的情況下，定位精度取決于網絡中信標節點的比例。從三條曲線可以看出，k的取值區間為［0.5 0.9］時，定位精度較小，尤其是當k取值在0.7左右。

圖3 不同k值對定位精度的影響

改進后定位算法的定位結果如圖4所示，其中線段連接的是未知節點實際位置與估計位置，圓代表未知節點實際位置，線段越長表示估計出的未知節點誤差越大，從圖中整體可以看出，改進后估計出的未知節點坐標與實際位置誤差較小。

圖4 IDV-Hop定位算法中未知節點實際位置與估計位置

圖5出示了改進后定位算法在節點數為300，信標節點比例為20%，k值為0.7時，每個未知節點的定位精度，從圖中可以看出，大部分未知節點的定位精度都在30%以內，部分未知節點的定位精度達到10%以內。

圖5 IDV-Hop定位算法中各個未知節點的定位精度

將本文改進算法中變量k取值為0.7，與原DVHop算法、已有改進算法的定位精度進行比較。圖6中網絡節點為300，信標節點比例分別為5%、10%、15%、20%、25%、30%、35%時三種算法定位精度的比較情況，從仿真結果可知，在節點總數不變的情況下，三種定位算法的定位精度總體上都隨信標節點的增加而提高，本文改進算法的定位精度比已有DV-Hop改進算法平均提高了3.6%，比DVHop算法平均提高了5.9%。

圖6 錨節點數量對定位誤差的影響

4 總結

節點定位在無線傳感器網絡的應用中起著重要作用，文中對DV-Hop算法原理以及產生誤差的原因進行了分析，并針對原算法以及已有改進算法在未知節點到信標節點距離計算中的不足，對信標節點的平均每跳距離做出了改進，并消除了因拓撲結構而造成的不可定位節點，通過仿真實驗結果可以看出，改進后的算法優于原算法和已有改進算法，提高了定位精度。由于該算法仍需要布設一定數量的錨節點來計算校正值，雖然數量不大但增加了成本，下一步將致力于研究采用單個移動錨節點來對三維空間中未知節點進行定位，使算法更加優化。

［1］杜治高，錢德沛，劉鐵.無線傳感器網絡中的地址分配協議［J］.軟件學報，2009，20(10):2787－2798.

［2］王福豹，史龍，任豐原.無線傳感器網絡中的自身定位系統和算法［J］.軟件學報，2003，16(05):857－868.

［3］Arampatzis T，Lygeros J，Manesis S.A Survey of Applications of Wireless Sensors and Wireless Sensor Networks［C］//Proceedings of the IEEE International Symposium on Mediterrean Conference on Control and Automation，Limassol，Cyprus，2005:719－724.

［4］Demirkol I，Ersoy C，Alagoz F.MAC Protocols for Wireless Sensor Networks:A Survey［J］.IEEE Communications Magazine，2006，44(4):115－121.

［5］Jun Xiao，Hong Chen，Shi Zhang.Research of Range-Based Synergetic Localization Algorithm in Wireless Sensor Networks［C］//Chinese Control and Decision Conference 2008.Shandong.China:IEEE，2008:2040－2044.

［6］楊鳳，史浩山，朱靈波，等.一種基于測距的無線傳感器網絡智能定位算法［J］.傳感技術學報，2008，21(1):135－140.

［7］Basagni S，Carosi A，Melachrinoudis E，et al.Protocols and Model for Sink Mobility in Wireless Sensor Networks［J］.ACM SIGMOBILE Mobile Computing and Communications Review，2006(10):28－30.

［8］王新生，趙衍靜，李海濤.基于DV-Hop定位算法的改進研究［J］.計算機科學，2011，38(02):76－78.

［9］劉少強，龐新苗，樊曉平，等.一種有效提高節點定位精度的改進 DV-Hop算法［J］.傳感技術學報，2010，23(8):1179－1183.

［10］彭剛，曹元大，孫利民.無線傳感器網絡節點定位機制的研究［J］.計算機工程與應用，2004，40(35):27－29，83.

［11］Shen X，Wang Z，Jiang P，et al.Connectivity and RSSI Based Localization Scheme for Wireless Sensor Networks［C］//2005 International Conference on Intelligent Computing，Lecture Notes on Computer Science.Vol.3645，p.578－587，Aug.2005.

［12］張品秀，黃操軍，喬相偉.基于自適應擴展Kalman濾波的SINS/GPS 深組合研究［J］.傳感技術學報，2010，23(3):408－412.

［13］張葛樣，李娜.MTLAB仿真技術與應用［M］.北京:清華大學出版社，2003.

［14］邱曉林.基于MATLAB的動態模型與系統仿真工具［M］.西安:西安交通大學出版社.2003.