基于多通信半徑的加權DV-Hop改進算法

邴曉瑛　徐保國

1(江南大學輕工過程先進控制教育部重點實驗室　江蘇 無錫 214122)2(江南大學物聯網工程學院　江蘇 無錫 214122)

?

基于多通信半徑的加權DV-Hop改進算法

邴曉瑛1徐保國2

1(江南大學輕工過程先進控制教育部重點實驗室江蘇 無錫 214122)2(江南大學物聯網工程學院江蘇 無錫 214122)

摘要針對網絡拓撲結構不規則的無線傳感器網絡中經典DV-Hop定位算法計算未知節點位置存在較大誤差的問題，提出一種基于多通信半徑修正跳數，加權修正未知節點平均跳距的改進算法。首先對通信半徑進行分級細化，利用多級通信半徑修正信標節點到信鄰節點的跳數信息。再根據信標節點與未知節點的距離，對能與未知節點通信的每個信標節點進行平均跳距加權處理，并將每個加權后的平均跳距參與未知節點平均跳距的計算，使未知節點的平均跳距更符合實際網絡情況。仿真結果表明，在相同的網絡拓撲結構下，改進的定位算法有效提高了傳感器節點的定位精度。

關鍵詞DV-Hop定位多通信半徑加權平均跳距定位精度

0引言

無線傳感器網絡WSN(Wireless Sensor Network)現已在國防軍事、智能交通、環境監控等很多領域，都得到了廣泛的應用。而傳感器節點的位置特別重要，是WSN應用的基礎[1]。現階段定位算法主要分為兩類，基于測距[2]和基于非測距[3]。其中DV-Hop[4]算法、質心算法、凸規劃算法等是典型的基于非測距的定位算法。Range-free定位算法硬件成本較低、能耗較小，傳輸的信號受外界影響較小，并且能滿足大部分實際應用對定位精度要求。

美國Rutgers University的Dragos Niculescu等利用GPS和距離矢量路由思想提出了DV-Hop算法[5]。DV-Hop算法不需要直接測量距離，而是通過交換距離矢量信息和網絡連通度來估算距離，導致了該算法定位精度較低。隨著社會的發展的需要，對許多實際應用的定位精度要求愈來愈高。許多學者對經典的DV-Hop算法進行了深入研究并改進，文獻[6] 采用雙通信半徑細化節點間的跳數信息，提高定位精度；文獻[7] 利用RSSI修正節點間的跳數信息，使跳數值更精確；文獻 [8]分別用信標節點修正未知節點平均跳距，并對未知節點估算位置迭代求精。

本文深入分析了傳統DV-Hop定位算法定位誤差大的原因，在不改變傳統算法框架的基礎上，利用多通信半徑來修正傳統算法第一階段得到的未知節點與信標節點間的最小跳數，并對第二階段中得到的平均每跳距離進行加權修正，使未知節點與信標節點間的距離更接近真實值。實驗結果表明，改進的算法能有效地減小定位誤差，提高定位精度。

1問題分析

1.1DV-Hop定位算法

DV-Hop算法可分為以下三個階段[9]。

(1) 計算信標節點與未知節點間最小跳數

每個信標節點都在網絡中廣播含自身信息分組{ID,(x,y),hop}給鄰居節點，初始化hop=0，接收節點每接收到一個分組信息，保存該信標節點的最小跳數并將hop=hop+1轉發給鄰居節點，若該分組來自同一信標節點，則忽略；以確保所有節點都能保存到網絡中任一信標節點間的最小跳數。

(2) 估算未知節點的平均每跳距離

網絡中任一信標節點的實際平均跳距：

(1)

信標節點i、j的坐標分別為(xi,yi)，(xj,yj)，i與j之間的最小跳段數為hopij。

未知節點接收并記錄信標節點在網絡中廣播的自身平均每跳距離，且僅記錄其接收到的第1個數值，繼續轉發該平均跳距，以保證盡可能多的未知節點記錄的平均跳距是從離其最近的信標節點處獲得。

(3) 計算未知節點位置

設未知節點D(x,y)能直接進行通信的信標節點為(x1,y1),(x2,y2),…,(xn,yn)，并假設步驟2中計算的D(x,y)到相應信標節點距離為d1,d2,…,dn，則:

(2)

可表示為線性方程組AL+ε=b，ε為n-1維隨機誤差向量，其中L=(x,y)T，則:

最小二乘法求得方程的解為:

L=(ATA)-1ATb

(3)

1.2誤差分析

在經典DV-Hop定位算法中，利用到未知節點最近的信標節點的估算平均跳距與最小跳數乘積等效替代其直線距離，精確度受網絡連通度影響較大[10]。經過深入分析，造成誤差原因如下：

(1) 最小跳數信息

DV-Hop定位算法中，選擇具有最少折點的幾個跳段等效為未知節點與信標節點之間的直線段，那么該折線段中各點越接近共線，誤差越小。由于網絡中節點隨機分布，共線概率較低，誤差必然存在[11,12]。未知節點與信標節點間的跳數越多，與其相關的測量距離dn誤差越大，式(3)中向量b的每個元素均包含測量距離dn，導致誤差累加。

(2) 平均跳距信息

DV-Hop定位算法中，未知節點將離其最近的信標節點的平均跳距作為自身平均跳距，并以此來計算該未知節點與網絡中其他信標節點間的距離[13-15]。由于實際網絡拓撲結構部規則，各處平均跳距信息并不相同，上述做法必然會造成誤差。信標節點平均跳距的精確度直接關系著與其相關的測量距離dn的精確性，亦會造成定位誤差的累加。

針對上述DV-Hop定位誤差的產生的原因，本文分別對未知節點與信標節點間的最小跳數與未知節點的平均跳距做出相應的改進研究。

2多通信半徑改進跳數信息

2.1基本思想

圖1　多通信半徑跳數計算

在DV-Hop定位算法中，兩點之間的直線距離小于通信半徑，即將其記為1跳。若網絡中節點分布如圖1所示，設通信半徑R=30 m，從圖中可以看出，信標節點O可以與節點A、B、C進行通信，那么HopOA=1,HopOB=1,HopOC=1，HopOD=2，但是OA與OC的距離相差較大，OD間跳數記為2跳時，對計算信標節點O平均跳距影響比較大。在計算未知節點與信標節點最小距離時，這種計算節點間最小跳數的機制也會導致誤差的產生，并在定位過程中繼續累加誤差。若能將信標節點到信鄰節點間的跳數分級細化，必然能減小誤差，提高定位精度。本文提出了一種利用多通信半徑來精確信標節點與信鄰節點間的跳數，減小定位誤差。

2.2具體步驟

設網絡通信半徑為R，將信標節點與信鄰節點間分為m級，網絡中各信標節點與其鄰居節點的實際距離為d，跳數記為H1,i∈[1,m]且為正整數，則:

(4)

具體步驟如下：

(1) 設定m,R值，首先取i=1；

(2) 若i

(4) 間隔時間t，令i=i+1，轉向步驟(2)；

(5) 信標節點以通信半徑R在網絡中廣播自身信息分組，接收節點每接收到一個分組信息，判斷是否為記錄的最小跳數值。若是，保存該信標節點的最小跳數并將hop=hop+1轉發給鄰居節點；若不是，將原來已保存的最小跳數值加1轉發給鄰居節點。若該分組來自同一信標節點，則忽略。

由于信標節點每次在網絡中泛洪廣播耗能較大，因此以小于R的通信半徑向網絡中廣播信息分組時，接收節點不將接收到的信息分組轉發，節約網絡能量開銷。

3加權修正平均跳距信息

3.1基本思想

設未知節點坐標為D(x,y)，能與該未知節點通信的信標節點為A1(x1,y1),A2(x2,y2),…,An(xn,yn)，這些信標節點的平均每跳距離為hopsize1,hopsize2,…,hopsizen，到D(x,y)的跳數為hop1,hop2,…,hopn,D(x,y)到信標節點Ai(xi,yi)的距離ri為：

ri=hopi×hopsize

(5)

由于hopsize是取離未知節點最近的信標節點的平均跳距作為未知節點到所有信標節點的平均跳距，但是實際網絡中節點在不同區域的分布狀況是不同的，平均每跳距離也是不同的，經典DV-Hop算法用單一的平均跳距不能正確反應網絡狀況，誤差較大。由式(5)可以看出，距離未知節點較近的信標節點，節點間距離計算更精確。

3.2具體步驟

本文用下式修正未知節點平均跳距：

(6)

hopsizei=(1-ωi)×hopsizei

(7)

(8)

由式(6)可知，距離未知節點越近的信標及誒單，hopi越小，權值ωi越小，由式(7)得出的hopsizei值對原平均跳距修正得越少，在式(8)中求平均跳距時貢獻的越多。

通過式(6)-式(8)的處理，每個能與未知節點通信的信標節點的平均跳距都參與計算未知節點平均跳距，每個信標節點平均跳距都根據與未知節點的距離遠近進行了加權處理，使得每個未知節點根據平均跳距計算自身坐標時更接近網絡的真實情況。

3.3改進DV-Hop具體實現步驟

基于多通信半徑與加權修正未知節點平均跳距的改進DV-Hop定位算法流程如圖2所示。

圖2　改進DV-Hop算法流程圖

4仿真實驗及結果分析

4.1仿真環境及參數設定

本文采用MATLAB仿真軟件實現傳感器節點定位算法。假設所有傳感器節點均勻隨機分布在100 m×100 m的正方形區域內。

為了能更直觀地評價PD-DV-Hop算法的性能，將其分別與傳統的DV-Hop算法，PSO改進的DV-Hop算法(PSO-DV-Hop)，DE改進的DV-Hop算法(DE-DV-Hop)進行對比仿真實驗，并比較分析實驗數據。為確保結果的準確性，在每種測試條件下，對上述4種算法分別進行50次隨機分布測試，取算術平均值。定位算法性能評價標準為歸一化定位誤差，其計算公式為：

(9)

其中，(xir,yir)、(xie,yie)代表第i個未知節點的實際坐標和通過定位算法得出的估計坐標，R為網絡通信半徑，N為未知節點總數。

4.2仿真結果分析

4.2.1多通信半徑下信標節點比例對定位精度的影響

圖3表示了節點總數N=100，通信半徑R=30m，信標節點比例在5%～35%變化時，通信半徑分級m不同時節點定位誤差圖。由圖可知，m=1,2,3,4,5時定位誤差與信標節點比例整體上成反比。在信標節點比例為5%～15%時，定位誤差受信標節點比例影響較大，當信標節點比例超過15%后，定位誤差變化均趨于穩定。由圖可知，m=1,2,3時定位誤差減小效果較明顯，m=4,5時定位誤差減小的較少，m=2較m=1即DV-Hop定位算法定位誤差平均減小了約17%；m=3較m=2定位算法定位誤差平均減小了約12%；m=4較m=3定位算法定位誤差平均減小了約8%；m=5較m=4定位算法定位誤差平均減小了約5%。

圖3　信標節點比例不同時定位誤差

4.2.2多通信半徑下通信半徑對定位精度的影響

圖4表示了節點總數N=100，信標節點數為30，通信半徑在20m～50m變化時，通信半徑分級m不同時節點定位誤差圖。由圖可知，m=1,2,3,4,5時定位誤差與通信半徑變化整體上成反比。這是由于通信半徑越大，每個節點的鄰居節點越多，網絡連通度越高，節點的平均跳距和跳數信息越準確。由圖可知，m=1,2,3時定位誤差減小效果較明顯，m=4,5時定位誤差減小的較少。m=2較m=1即DV-Hop定位算法定位誤差平均減小了約15%；m=3較m=2定位算法定位誤差平均減小了約10%；m=4較m=3定位算法定位誤差平均減小了約6%；m=5較m=4定位算法定位誤差平均減小了約4%。

圖4　通信半徑不同時定位誤差

根據圖3、圖4，通信半徑分為m=3級時節點定位誤差較經典DV-Hop減小的較明顯，由于信標節點每廣播一次自身信息分組，都要有一定的能量消耗。綜合考慮，本文選擇將通信半徑分為3級，細化精確節點間的跳數信息，并與本文改進的加權平均跳距結合進行改進DV-Hop定位算法的仿真研究。

4.2.3改進DV-Hop算法中信標節點數對定位精度的影響

圖5表示了節點總數為100，通信半徑R=30m，信標節點比例在5%～30%變化時，改進DV-Hop算法與經典DV-Hop算法節點定位誤差圖。由圖5可知，在通信半徑一定的情況下，2種算法定位誤差與信標節點比例整體上成反比。改進DV-Hop定位算法比經典DV-Hop定位算法定位誤差平均減小了約20%，且改進的定位算法更穩定。

圖5　改進DV-Hop信標節點比例不同時的定位誤差

4.2.4改進DV-Hop算法中通信半徑對定位精度的影響

圖6表示了節點總數為100，信標節點數為30，通信半徑在20m～50m變化時，改進DV-Hop算法與經典DV-Hop算法節點定位誤差圖。由圖5可知，在節點總數與信標節點數一定的情況下，2種算法定位誤差與通信半徑整體上成反比。改進DV-Hop定位算法比經典DV-Hop定位算法定位誤差平均減小了約18%，且改進的定位算法更穩定。

圖6　改進DV-Hop通信半徑不同時的定位誤差

5結語

本文提出了一種基于多通信半徑分級細化節點間跳數和加權修正未知節點平均跳距的改進DV-Hop定位算法。通過多通信半徑精確節點間跳數信息，并通過加權平均跳距修正未知節點到信標節點的平均跳距，使求得的未知節點坐標更接近實際坐標，提高定位精度。仿真實驗結果表明，本文改進算法在相同的網絡拓撲結構下，有效地提高了傳感器節點的定位精度。如何更有效地節約網絡能量開銷，也是未來的一個研究方向。

參考文獻

[1] 張西紅,周順,陳立云.無線傳感網技術及其軍事應用[M].北京:國防工業出版社，2010.

[2] Yan Ling Chu, Jau Rong Tzeng, YungPin Cheng,et al.Density-Adaptive Range-free Localization in Large-Scale Sensor Networks[C]//Parallel Processing Workshops (ICPPW),2012 41st International Conference on,2012:488 - 495,1249-1250.

[3] Maung N A M,Kawai M.Experimental Evaluations of RSS threshold-based optimized DV-Hop localization for wireless ad-hoc networks [J].2014,50(17):1246-1248.

[4] Gayan S,Dias D.Improved DV-Hop algorithm through anchor poition re-estimation [C]//Wireless and Mobile,2014 IEEE Asia Pacific Conference on.2014:126-131.

[5] Niculescu D,Nath B.DV Based Positioning in Ad Hoc Networks[C]//Telecommunication Systems,2003:22(1/2/3/4):267-280.

[6] 李娟,劉禹,錢志鴻.基于雙通信半徑的傳感器網絡DV-Hop定位算法[J].吉林大學學報,2014,44 (2):502-507.

[7] 溫江濤,范學敏,吳希軍.基于RSSI跳數修正的DV-Hop改進算法[J].傳感技術學報,2014,27(1):113-117.

[8] 劉紅慶.一種針對無線傳感器網絡的WNDV-HOP算法[J].計算機應用與軟件,2013,30(12):288-290,302.

[9] 楊祥,潘瑋.基于RSSI比值修正的無線傳感器網絡DV-Hop定位算法[J].傳感器與微系統,2013,32(7):126-135.

[10] 夏少波,連麗君,王魯娜.基于DV-Hop定位算法的改進[J].計算機應用,2014,34(5):1247-1250.

[11] Munsuck Jang,Inseong Song.A study on Localization Algorithm using Hop Count and RSSI[J].International Journal of Control and Automation,2013:6(3):267-280.

[12] 羅維,姜秀柱,盛蒙蒙.無線傳感器網絡選擇性DV-Hop定位算法[J].傳感器與微系統,2012,31(3):71-77.

[13] Yu Weiqi,Li Hao.An improved DV-Hop localization method in wireless sensor networks [C]//2012 IEEE International Conference on Computer Science and Automatic Engineering.Zhangjiajie:IEEE Press,2012:25-27.

[14] 譚志，張卉.基于節點間覆蓋關系的改進DV-Hop定位算法[J].北京郵電大學學報,2014,37 (1):35-38.

[15] 賈琦，周新志.基于無線傳感器網絡DV-Hop定位算法的改進和研究 [J].計算測量與控制,2013,21(11):3043-3046.

收稿日期：2015-02-16。國家自然科學基金面上項目(21276111)；國家自然科學基金青年基金項目(21206053);浙江省自然科學基金重大專項(2011C12033)。邴曉瑛，碩士生，主研領域：無線傳感網定位算法。徐保國，教授。

中圖分類號TP393

文獻標識碼A

DOI:10.3969/j.issn.1000-386x.2016.07.030

IMPROVED DV-HOP ALGORITHM WITH WEIGHTING BASED ON MULTIPLE COMMUNICATION RADIUS

Bing Xiaoying1Xu Baoguo2

1(KeyLaboratoryofIndustrialAdvancedProcessControlforLightIndustry,MinistryofEducation,JiangnanUniversity,Wuxi214122,Jiangsu,China)2(SchoolofInternetofThingsEngineering,JiangnanUniversity,Wuxi214122,Jiangsu,China)

AbstractTo solve the problem that in wireless sensor networks with irregular network topology rule,there is the rather bigger error in traditional DV-Hop localisation algorithm when calculating the location of unknown nodes,we proposed an improved algorithm which corrects the hop numbers based on multiple communication radius and corrects the average hop sizes of unknown nodes with weighting.First,we graded and refined the communication radius,and used multi-level communication radius to modify the information of hop numbers between beacon nodes and their neighbouring nodes.Secondly,according to the distance from unknown nodes to beacon nodes,we processed the average hop sizes of every beacon node capable of communicating with unknown nodes by weighting them,and made every weighted average hop size be involved in calculating the average hop sizes of unknown nodes,thus the average hop sizes of unknown nodes were more conformable to actual network situation.Simulation results showed that for the same network topology structure,the improved localisation algorithm effectively raised the localising precision of sensor nodes.

KeywordsDV-Hop localisationMultiple communication radiusWeightingAverage hop sizeLocalisation precision