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

摘要：在無線傳感器網絡中，節點定位占有極其重要的一席之地。無需測距方案中的DV-Hop算法因其計算簡單易于實現得到廣泛應用。傳統DV-Hop算法不能夠提供相對好的定位精度，為了保證定位的準確性，文章對DV-Hop算法進行了優化。在優化算法中，采用加權誤差修正錨節點的估計平均跳距使其更加接近實際值，之后采用二維雙曲線算法代替三邊法或最小二乘算法確定接近實際位置的待測節點坐標。仿真結果驗證了文章提出算法在無線傳感器網絡中定位的準確性。

關鍵詞：無線傳感器網絡；節點定位；DV-Hop算法；加權誤差；平均跳距

中圖分類號：TN929.5" 文獻標志碼： A

作者簡介：董晶（1993— ），女，助教，碩士；研究方向：物聯網。

*通信作者：陳智（1983— ），男，副教授，碩士；研究方向：電子信息科學與技術。

0" 引言

無線傳感器網絡（Wireless Sensor Networks，WSN）是一種具備自組織和通信能力的分布式傳感網絡系統，由分布在監測區域內具備低能耗收發器及有限處理數據能力的小型感知節點組合而成［1］。無線傳感器網絡能夠對監測范圍內的監測物體進行實時監測、感知及數據采集，并將收集到的數據信息處理后發送給觀察者。傳感器、探測目標以及觀測者是構成WSN的重要組成元素［2］。WSN能夠通過相互協作的方式來探測、管理以及發送網絡覆蓋范圍內監測目標的數據信息，并且將所監測到的有用數據報告給監測者。WSN主要承擔數據信息的收集、管理以及發送任務。WSN是采用無線網絡的途徑在傳感器和用戶之間進行通信的，利用創建的通信鏈路通過節點間的相互配合來探測、管理以及發送網絡覆蓋范圍內監測目標的數據信息。

節點定位技術是WSN的關鍵技術之一，根據是否需要測量節點間的距離，定位技術可分為基于測距（Range-based）算法和無需測距（Range-free）算法［3-5］。在無需測距的算法中，DV-Hop算法因其過程簡單、便于計算、易于實現等優點得到了廣泛應用，但它不能滿足高精度定位的要求。早在2001年，Niculescu和Nath提出這個算法之后，很多領域的研究人員對此算法做了改進，例如對平均跳距和最小跳數的修正以及算法的迭代優化［6］等。劉鋒等［7］將待測目標節點收到的錨節點單跳大小值按照距離遠近程度賦予權重值，最終得到所有平均單跳距離的加權和，使估計出的單跳距離值更符合實際值，減小出現的定位誤差，確保了定位的精確度。趙曉青等［8］通過節點間距離差值和跳數取權值的方法對單跳距離值進行修正，然后通過錨節點與待測目標節點遠離程度的不同，對兩者間估算的距離值進行修正。祝宇鴻等［9］根據不同錨節點之間的距離估算出平均單跳距離值，通過最大值與最小值求均值來修正網絡中的平均單跳距離，得到更精準的定位。秦鵬程等［10］將監測區域進行劃分，針對節點部署不均勻的情況，通過引進可移動的錨節點對監測區域內的錨節點進行二次部署，避免由錨節點部署過于集中而引起的定位不準確。本文在原DV-Hop算法的基礎上，通過對平均誤差取權值來修正網絡的單跳距離值，然后用二維雙曲線算法代替最小二乘算法，對算法進行優化，對待測目標節點進行更精準的定位。

1" DV-Hop算法

DV-Hop算法是以距離矢量路由和GPS定位為核心思想的一種分布式定位方法，主要分為3步。

1.1" 第1階段 數據信息交換

這一階段，網絡中的每個錨節點將帶有自身位置信息分組的數據包通過泛洪的方式進行廣播，其中數據包包含錨節點自己的位置信息、節點ID號以及自身到接收節點之間的跳數值（初值設為0），若接收節點接收到的信息包含至錨節點的最小跳數，則將跳數遞加1后的新跳數值傳遞到網絡中，并繼續轉發到下一個相鄰節點。此階段結束后，記錄所有節點相隔錨節點的最小跳數值。

1.2" 第2階段 距離計算

這一步，每個錨節點根據其他錨節點的位置信息及相隔最小跳數值，利用公式（1）估算平均單跳距離值。

HopSizei=∑i≠j（xi-xj）2+（yi-yj）2∑i≠jhij（1）

式中：（xi，yi）（xj，yj）是錨節點i、j的坐標，hij是錨節點i和j（i≠j）之間的最小跳數。

得到出錨節點的平均單跳值之后，將該值作為一個校正值在網絡中進行二次泛洪廣播。當接收到校正值后，待測目標節點僅僅只記錄收到的第一個單跳距離值，并將其作自己的平均跳距，由此確保很大一部分節點獲得的跳距值是從最靠近自己的錨節點得到的。由式（2）計算估計距離：

duv=HopSizei×hopuv（2）

式中，HopSizei是待測目標節點u從最靠近自己的錨節點i獲得的跳距值，hopuv是未知節點u和錨節點v之間的最小跳距。

1.3" 第3階段 位置估計

當待測每目標節點獲得3個或更多至錨節點的估計距離值時，采用最小二乘算法求出待測目標節點估計坐標值。

未知節點p（x，y）到所有錨節點距離如下：

（x1-x）2+（y1-y）2=d21

（xn-x）2+（yn-y）2=d2n（3）

x21-x2n+2（x1-xn）x+y21-y2n-2（y1-yn）y=d21-d2n

（4）

x2n-1-x2n+2（xn-1-xn）x+y2n-1-y2n-2（yn-1-yn）y=d2n-1-d2n

式（4）可寫為：

AX=B（5）

這里，

A=2（x1-xn）2（y1-yn）

2（xn-1-xn）2（yn-1-yn）

B=x21-x2n+y21-y2n+d21-d2n

x2n-1-x2n+y2n-1-y2n+d2n-1-d2n（6）

X=xy

根據最小二乘算法，通過公式（7）可求出待測目標節點P的估計坐標值。

P=（ATA）-1ATB（7）

DV-Hop算法主要發生了2次泛洪機制，第一次產生泛洪是節點記錄錨節點坐標信息以及確定到錨節點的最小跳數值，第二次泛洪是把節點跳數轉化為距離值方便進行定位。網絡中的錨節點利用第一次泛洪獲得的最小跳數值和節點距離得到節點平均跳距。在錨節點計算出平均單跳值之后，通過具有生存周期字段的消息分組再次泛洪廣播到網絡中，待定位節點只收錄首次收到的校正數據，忽略隨后收到的數據以確保節點的數據是從距自己最近的錨節點發出的。當廣播結束后，待定位節點把收到距自己最近的錨節點平均單跳距離值當做自身校正信息，然后與得到的跳數值進行求積運算得出距錨節點間的物理距離值。

2" 改進的DV-Hop算法

在DV-Hop算法中，待測目標節點將首次收到錨節點的單跳距離值作為自身跳距值，且假設節點間的通信路徑是一條直線，但是在實際情況中，由于網絡拓撲結構的不同，節點之間的距離可能不在同一條直線上，這就導致計算出來的平均跳距與實際跳距有偏差，進而未知節點的位置坐標估計不準確。針對以上問題，本文主要從錨節點的平均單跳距離值及待測目標節點位置估計方法2個方面對DV-Hop算法進行優化，使優化之后的方法比原算法具有更優越的性能。

2.1" 加權誤差修正平均跳距

DV-Hop算法在計算待測目標節點與錨節點間距離時，采用首次收到的錨節點的跳段距離值進行距離估計運算，但在一般情況下，2個通信節點之間的路徑是非直線的，采用平均跳距值乘以最小跳數值來估算待測目標節點坐標就會出現很的大誤差，這里用錨節點到不同錨節點的單跳距離取均值［5］：

HopSizeavg=∑HopSizein（8）

這里n為網絡中錨節點個數。

定義Errori為平均每跳誤差，即：

Errori=HopSizeavg-HopSizei（9）

定義誤差權重為：

Weightedi=1Ni∑nj=11Nj（10）

這里Ni是錨節點之間的跳數。

定義加權誤差W_errori為：

W_errori=∑（Errori×Weightedi）（11）

重新計算跳距：

HopSizenewi=HopSizei+W_errori（12）

由此得到待測目標節點到錨節點之間的近似距離值：

di=HopSizenewi×hopi（13）

2.2" 二維雙曲線算法

在估算坐標位置方法中，本文將其中的二維雙曲線法替代最小二乘算法，對待測目標節點的位置進行估計運算。

假設待測目標節點位置坐標為（x，y），錨節點位置坐標為（xi，yi），di為待測目標節點與錨節點之間的距離，顯然di的計算公式為：

di=（xi-x）2+（yi-y）2（14）

對（14）式兩邊求平方，得到下面方程式：

x2i+y2i-2xix-2yiy+x2+y2=d2i（15）

d2i-Ei=-2xix-2yiy+K（16）

其中Ei=x2i+y2i，K=x2+y2。

令Zc=［x，y，K］T，Gc=-2x1-2y11-2x2-2y21-2xi-2yi1，

Hc=d21-E1

d22-E2

d2i-Ei，

根據最小二乘算法，有：

Zc=（GTcGc）-1GTcHc（17）

待定位節點坐標為：

x=Zc（1）

y=Zc（2）（18）

3" 實驗仿真與結果分析

本文采用MATLAB仿真平臺對所提算法進行性能評估，用MATLAB2016a作為模擬器來模擬實現網絡場景，選取邊長為100 m的正方形作為仿真區域，節點分布如圖1所示，且每個實驗在參數不變的情況下模擬實驗進行100次，求其平均值并繪制出對應的誤差曲線圖，通過定位誤差分析該算法的性能，計算公式如下：

LocalizationError=∑ni=1（xesti-xtri）2+（yesti-ytri）2n×R（19）

其中，（xesti，yesti）是待測目標節點估計坐標值，（xtri，ytri）是待測目標節點真實坐標值，R為通信半徑，n為待測目標節點總數。

將DV-Hop算法、Hadir等［11］算法、二維雙曲線算法及WEDV-Hop算法分別在算法參數改變的情況下進行仿真對比與結果分析。

3.1" 通信半徑改變

由圖2可知，錨節點總數固定不變，隨著通信半徑逐的漸增大，DV-Hop算法、Hadir等［11］算法、二維雙曲線算法及WEDV-Hop算法的定位誤差波動較明顯。這是因為當通信半徑增大，網絡的聯通性逐漸增強，定位精度明顯提高，當通信半徑達到一定數值后，最終定位誤差趨于平穩。通過比較，改進后算法性能有所提升，平均誤差值有所下降，比原DV- Hop算法降低7%～15%，比Hadir等［11］算法降低5%～12%，比二維雙曲線算法降低3%～8%。

3.2" 錨節點數改變

在通信半徑相同情況下，錨節點數N分別為8、10、12、14、16、18、20時，4種算法的平均定位誤差波動比較平緩，都趨于穩定減小狀態。仿真結果如圖3所示，當通信半徑為R=30 m時，WEDV-Hop算法比原DV-Hop算法有8%～10%的誤差降低趨勢。隨著錨節點數量的增加，誤差趨于穩定狀態。

3.3" 節點總數改變

如圖4所示，通信半徑為30 m，錨節點總數不變的情況下，隨著網絡節點總數的增加，原DV-Hop算法、Hadir等［11］算法與雙曲線算法的定位誤差均有穩定遞增趨勢。這由于網絡節點總數增加，待定位目標節點數增多，網絡的聯通性變差，導致網絡中孤立節點增加，使整體定位準確性下降。相較于其他3種算法，WEDV-Hop算法定位誤差略有增加。

4" 結語

本文提出的WEDV- Hop算法優化了傳統的DV-Hop算法，考慮到多個錨節點平均跳距對定位誤差的影響，利用加權誤差來校正網絡平均跳離，通過" 二維雙曲線算法估計待定位目標節點位置。仿真結果表明，在無須額外增加硬件設施的條件下，該算法有效地提高了節點定位的準確性。

參考文獻

［1］OZDEMIR O，NIU R.Channel aware target localization with quantized data in wireless sensor networks signal processing［J］.IEEE Transactions，2009（3）：1190-1202.

［2］KUMAR S，LOBIYAL K．An advanced DV-Hop ocalization algorithm for wireless sensor networks［J］.Wireless Personal Communications，2013，71： 1365-1385.

［3］孫立明，李建中，陳瑜，等.無線傳感器網絡［M］.北京：清華大學出版社，2005.

［4］GAYAN S，DIAS D.Improved DV-HOP algorithm through anchor position re-estimation［C］//IEEE Asia Pacific Conference on Wireless and Mobile，August：28-30，2014.Piscataway，New Jersey，C2014：126-131.

［5］趙芝璞，吳棟，王艷，等.基于平均跳距和位置優化的改進DV-Hop定位算法［J］.系統仿真學報，2016（6）：1273-1280.

［6］許毅，陳立家，甘浪雄，等.無線傳感器網絡技術原理及應用［M］.北京：清華大學出版社，2015.

［7］劉鋒，張翰，楊驥.一種基于加權處理的無線傳感器網絡平均跳距離估計算法［J］.電子與信息學報，2008（5）：1222-1225.

［8］趙曉青，毛永毅．基于誤差加權和距離修正的改進DV-Hop算法［J］．計算機工程與應用，2016（18）：117-121.

［9］祝宇鴻，歷彥愷，胡俊，等.基于跳數閾值和節點分類的DV-Hop改進算法［J］.吉林大學學報（信息科學版），2014（4）：407-412.

［10］秦鵬程，顏文，解培中.基于區域劃分錨節點移動的DV-Hop定位算法：CN105848283A［P］.2016-08-10.

［11］HADIR A，ZINE-DINE K，BAKHOUYA M，et al.An improved DV-Hop localization algorithm for wireless sensor networks［C］.International Conference on Next Generation Networks and Services（NGNS），May 28-30，2014.Casablanca，2014.

（編輯" 王雪芬）

Improvement of DV-Hop positioning algorithm in wireless sensor networks

DONG" Jing， CHEN" Zhi*

（School of Computing and Artificial Intelligence，Lanzhou University of Information Science and Technology， Lanzhou 730300，China）

Abstract：" Node localization plays an signicant importance role in wireless sensor network. DV-Hop algorithm is a range free algorithm that is widely used of its simple calculation and easy implementation. Traditional DV-Hop algorithm cannot provide relatively better localization accuracy. To ensure the accuracy of localization， an improved DV-Hop localization algorithm is proposed. Under this localization algorithm， using a novel weighted error corrected the average jump distance of the anchor node， and then adopt two-dimensional hyperbolic function instead of the classic trilateration＼＼least square method to determine the locations of unknown nodes， which are very close to their actual locations. Simulations are conducted to validate the accuracy of our proposed localization algorithm in wireless sensor networks.

Key words： wireless sensor network; node location; DV-Hop algorithm; weighted error; average hop distance