邴曉瑛　徐保國

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

?

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

邴曉瑛1徐保國2

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

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

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

0引言

無線傳感器網(wǎng)絡WSN(Wireless Sensor Network)現(xiàn)已在國防軍事、智能交通、環(huán)境監(jiān)控等很多領域，都得到了廣泛的應用。而傳感器節(jié)點的位置特別重要，是WSN應用的基礎[1]?，F(xiàn)階段定位算法主要分為兩類，基于測距[2]和基于非測距[3]。其中DV-Hop[4]算法、質心算法、凸規(guī)劃算法等是典型的基于非測距的定位算法。Range-free定位算法硬件成本較低、能耗較小，傳輸?shù)男盘柺芡饨缬绊戄^小，并且能滿足大部分實際應用對定位精度要求。

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

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

1問題分析

1.1DV-Hop定位算法

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

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

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

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

網(wǎng)絡中任一信標節(jié)點的實際平均跳距：

(1)

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

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

(3) 計算未知節(jié)點位置

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

(2)

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

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

L=(ATA)-1ATb

(3)

1.2誤差分析

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

(1) 最小跳數(shù)信息

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

(2) 平均跳距信息

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

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

2多通信半徑改進跳數(shù)信息

2.1基本思想

圖1　多通信半徑跳數(shù)計算

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

2.2具體步驟

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

(4)

具體步驟如下：

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

(2) 若i

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

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

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

3加權修正平均跳距信息

3.1基本思想

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

ri=hopi×hopsize

(5)

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

3.2具體步驟

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

(6)

hopsizei=(1-ωi)×hopsizei

(7)

(8)

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

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

3.3改進DV-Hop具體實現(xiàn)步驟

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

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

4仿真實驗及結果分析

4.1仿真環(huán)境及參數(shù)設定

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

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

(9)

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

4.2仿真結果分析

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

圖3表示了節(jié)點總數(shù)N=100，通信半徑R=30m，信標節(jié)點比例在5%～35%變化時，通信半徑分級m不同時節(jié)點定位誤差圖。由圖可知，m=1,2,3,4,5時定位誤差與信標節(jié)點比例整體上成反比。在信標節(jié)點比例為5%～15%時，定位誤差受信標節(jié)點比例影響較大，當信標節(jié)點比例超過15%后，定位誤差變化均趨于穩(wěn)定。由圖可知，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　信標節(jié)點比例不同時定位誤差

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

圖4表示了節(jié)點總數(shù)N=100，信標節(jié)點數(shù)為30，通信半徑在20m～50m變化時，通信半徑分級m不同時節(jié)點定位誤差圖。由圖可知，m=1,2,3,4,5時定位誤差與通信半徑變化整體上成反比。這是由于通信半徑越大，每個節(jié)點的鄰居節(jié)點越多，網(wǎng)絡連通度越高，節(jié)點的平均跳距和跳數(shù)信息越準確。由圖可知，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　通信半徑不同時定位誤差

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

4.2.3改進DV-Hop算法中信標節(jié)點數(shù)對定位精度的影響

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

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

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

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

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

5結語

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

參考文獻

[1] 張西紅,周順,陳立云.無線傳感網(wǎng)技術及其軍事應用[M].北京:國防工業(yè)出版社，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] 李娟,劉禹,錢志鴻.基于雙通信半徑的傳感器網(wǎng)絡DV-Hop定位算法[J].吉林大學學報,2014,44 (2):502-507.

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

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

[9] 楊祥,潘瑋.基于RSSI比值修正的無線傳感器網(wǎng)絡DV-Hop定位算法[J].傳感器與微系統(tǒng),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] 羅維,姜秀柱,盛蒙蒙.無線傳感器網(wǎng)絡選擇性DV-Hop定位算法[J].傳感器與微系統(tǒng),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] 譚志，張卉.基于節(jié)點間覆蓋關系的改進DV-Hop定位算法[J].北京郵電大學學報,2014,37 (1):35-38.

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

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

中圖分類號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