黨宏社， 劉 勇， 萇 瑤， 黃梓岳

(陜西科技大學 電氣與信息工程學院， 陜西 西安 710021)

?

基于距離虛擬補償?shù)腄V-Hop定位算法

黨宏社， 劉 勇， 萇 瑤， 黃梓岳

(陜西科技大學 電氣與信息工程學院， 陜西 西安 710021)

針對DV-Hop(Distance Vector-Hop)定位算法中的未知節(jié)點到信標節(jié)點的距離計算存在較大的誤差，從而降低了未知節(jié)點的定位精度這一問題，提出了基于距離虛擬補償?shù)腄V-Hop定位算法.該算法從兩個方面進行改進,首先根據(jù)跳數(shù)對信標節(jié)點之間的距離進行虛擬補償；然后對與未知節(jié)點距離相等的多個信標節(jié)點求平均距離，從而使得未知節(jié)點到信標節(jié)點的距離更加接近實際距離.通過與傳統(tǒng)算法和改進算法的性能進行仿真對比，結果表明改進的算法有效的提高了未知節(jié)點的定位精度.

無線傳感器網絡； DV-Hop定位算法； 距離虛擬補償； 均值處理，定位精度

0 引言

無線傳感器網絡定位是無線傳感器網絡應用的一個重要前提條件，只有知道數(shù)據(jù)采集節(jié)點采集到的數(shù)據(jù)的具體位置，采集到的數(shù)據(jù)才有意義[1].所以如何準確獲得每一個數(shù)據(jù)采集節(jié)點所在區(qū)域的具體位置，成為了國內外研究人員關注的重點[2,3].現(xiàn)今的定位算法按定位機制來分可以將定位算法分為基于測距的定位算法和無需測距的定位算法.基于測距的定位算法的定位精度比基于非測距的定位算法的定位精度高，但是前者對網絡的硬件設施要求較高，而后者只需知道網絡的連通性等信息就可以實現(xiàn)對未知節(jié)點的定位.這種優(yōu)勢使得無需測距定位算法受到了國內外研究人員的廣泛關注.

無需測距的定位算法包括質心算法[4,5]，DV-Hop算法[6]，APIT算法[7]等.其中DV-Hop算法簡單、容易實現(xiàn)并且具有較好的擴展性等優(yōu)勢，使其成為當今使用最廣的一種非測距定位算法.文獻[8-12]分別對DV-Hop算法進行了不同程度的改進，但是定位效果仍然不是很理想，因此本文提出了距離虛擬補償?shù)亩ㄎ凰惴?

1 DV-Hop定位算法

1.1 DV-Hop算法的描述

DV-Hop定位算法首先是由美國路特格斯大學的Niculescu D.等[8]提出.該算法主要分為三個階段.

(1)第1階段

信標節(jié)點利用泛洪的方式向整個網絡發(fā)送一個包含自身ID、坐標和跳數(shù)信息的一個數(shù)據(jù)包.當未知節(jié)點是第一次接收到該數(shù)據(jù)包時，它將會保存該數(shù)據(jù)包并將該數(shù)據(jù)包的跳數(shù)值加1廣播到鄰居節(jié)點；如果不是第一接收該類型的數(shù)據(jù)包時，那么它會將新收到的數(shù)據(jù)包的跳數(shù)值與先前接收的數(shù)據(jù)包的跳數(shù)值進行比較，如果新接收到數(shù)據(jù)包的跳數(shù)值小于原先保存的數(shù)據(jù)包中的跳數(shù)值，那么它會保存新接收到的數(shù)據(jù)包并將該數(shù)據(jù)包的跳數(shù)值加1廣播到鄰居節(jié)點，否則丟棄新接收到的數(shù)據(jù)包.通過這一機制所有的未知節(jié)點獲得距離信標節(jié)點最小跳數(shù)信息.

(2)第2階段

每個信標節(jié)點在獲得其它信標節(jié)點的位置以及之間的最小跳數(shù)信息后，根據(jù)式(1)計算出信標節(jié)點i的平均跳距HopSizei：

(1)

式(1)中：(xi,yi)與(xj,yj)分別表示的是信標節(jié)點i與j的坐標；Hopij是信標節(jié)點i與j之間的最小跳數(shù).

在計算出跳距后，每個信標節(jié)點通過泛洪的方式向網絡廣播平均跳距，當未知節(jié)點接收到平均跳距信息時，其只保存第一次接收到的平均跳距，并將其廣播到鄰居節(jié)點.通過這種方法，大部分的未知節(jié)點收到來自信標節(jié)點的平均跳距.當未知節(jié)點收到了信標節(jié)點的平均跳距，就可以通過式(2)計算出該未知節(jié)點u與信標節(jié)點i之間的距離：

dui=HopSizei×hopui

(2)

(3)第3階段

利用最小二乘法對未知節(jié)點的坐標進行估算.假設(x,y)為未知節(jié)點u的坐標，(xi,yi)為第i個信標節(jié)點的坐標，未知節(jié)點與信標節(jié)點的距離分別為d1,d2,…,dn，則有：

(3)

通過下面的公式即可計算出未知節(jié)點u的坐標：

(4)

(5)

(6)

則有P=(ATA)-1ATB.

1.2DV-Hop誤差分析

在實際應用中，考慮到成本和能耗的問題，不可能在某一監(jiān)測區(qū)域部署大量的信標節(jié)點.另外，節(jié)點通常是以飛機投放的方式將節(jié)點撒在監(jiān)控區(qū)域內，所以節(jié)點的位置分布并不均勻.在這種情況下，利用少數(shù)的信標節(jié)點來估算大量未知節(jié)點的位置，勢必會產生較大的誤差.圖1為傳感器網絡的拓撲結構圖.下面對DV-Hop算法在計算平均跳距時所產生的誤差進行具體分析.

在圖1中，A,B,C為信標節(jié)點，u0,u1,…,u5為未知節(jié)點.①對于信標節(jié)點A與B而言，由于它們之間的跳數(shù)較多，使得計算出來的平均跳距小于未知節(jié)點到信標節(jié)點每跳的距離，因此計算出來的估計距離小于未知節(jié)點到信標節(jié)點的歐式距離；②對于未知節(jié)點u4而言，其與信標節(jié)點B和C的跳數(shù)一樣，如果只選擇其中的一個信標節(jié)點的平均跳距來計算，那將無法反映實際情況，所以也會產生誤差.

圖1 傳感器網絡拓撲結構圖

2 改進的DV-Hop算法

2.1 已有的改進算法

針對傳統(tǒng)的DV-Hop定位算法在隨機分布的網絡環(huán)境下定位誤差較大這一問題，國內外一些專家和學者對此進行了大量的改進研究.文獻[9]通過最小均方差獲得平均每跳距離，然后利用未知節(jié)點到信標節(jié)點的最小跳數(shù)與該未知節(jié)點到所有的信標節(jié)點跳數(shù)之和的比值作為加權，最后使用粒子群優(yōu)化算法來糾正雙曲線定位算法來計算未知節(jié)點的位置.文獻[10]采用曲線擬合的最小二乘法求解未知節(jié)點的坐標，并對未知節(jié)點的坐標進行優(yōu)化處理.文獻[11]首先借助信標節(jié)點之間的估計距離與實際距離的偏差來修正平均每跳距離，然后利用二維雙曲線定位算法代替三邊測量定位算法來估計未知節(jié)點的位置.文獻[12]通過引入信號強度對每跳進行分級來修正節(jié)點間的跳數(shù)，接著利用最小均方差準則來獲得信標節(jié)點距離估計誤差最小的平均跳距.文獻[13]首先對信標節(jié)點的跳數(shù)進行修正，其次對未知節(jié)點到信標節(jié)點間的跳數(shù)進行修正，修正后的跳數(shù)都不再是整數(shù).上述的幾種改進算法雖然在不同程度上都提高了對未知節(jié)點的定位精度，但也有考慮不周全、定位精度的提高不明顯、可操作性不強等一系列問題.

2.2 本文改進的DV-Hop算法

傳統(tǒng)的DV-Hop定位算法在統(tǒng)計兩信標節(jié)點間的跳數(shù)時,當信標節(jié)點之間的距離在通信半徑范圍內，信標節(jié)點之間跳數(shù)為1，然而當信標節(jié)點之間的距離大于通信半徑時，這時借助未知節(jié)點來獲得信標節(jié)點之間的最小跳數(shù)，這就會出現(xiàn)圖2信標節(jié)點A和B的情況:信標節(jié)點之間的距離不是很長，但跳數(shù)較多，使得信標節(jié)點計算出來的平均跳距小于未知節(jié)點與信標節(jié)點實際每跳的距離.針對這一問題，很多改進的DV-Hop算法都是通過減少跳數(shù)來增加平均每跳跳距，那么也可從另外一個角度來解決這個問題，即通過虛擬補償信標節(jié)點間的距離.因為節(jié)點部署完成后，任意兩信標節(jié)點之間的距離也就確定了，本文只是在計算的時候對其進行補償，所以稱之為距離虛擬補償.

2.2.1 信標節(jié)點間的距離補償

針對誤差分析中的情況①，根據(jù)信標節(jié)點之間的跳數(shù)，提出了式(7)的距離補償公式：

(7)

式(7)中：dcij表示的信標節(jié)點i與j補償距離；Hopij表示的信標節(jié)點i與信標節(jié)點j之間的跳數(shù)；R表示的是通信半徑；dij表示的是信標i與j之間實際距離；dij/R表示兩信標節(jié)點i與j之間理想跳數(shù)，那么(R/dij)dij表示的是理想狀態(tài)下的每跳的實際距離；(R/dij)ndij中的n是用來尋找每跳補償距離的最優(yōu)值；將(R/dij)ndij值乘以Hopij作為信標i與j節(jié)點之間的補償距離.

2.2.2 調整未知節(jié)點到信標之間的距離

針對誤差分析中的情況②，假設未知節(jié)點u到信標節(jié)點i1,i2,…,ik之間平均跳距分別為dui1,dui2,…,duik且跳數(shù)分別為Hopui1,Hopui2,…,Hopuik，則未知節(jié)點到信標節(jié)點的距離為：

(8)

3 實驗仿真和結果分析

為了驗證改進算法，本文首先對n和R取不同值時的性能進行了仿真,并對傳統(tǒng)的DV-Hop算法、文獻[13]和本文改進的算法進行了仿真對比.仿真環(huán)境設置：選用的是MATLAB7.12作為仿真測試平臺.測試區(qū)域為100 m×100 m，為了獲得更加客觀準確的測試數(shù)據(jù)，對所有的數(shù)據(jù)都采集100次求平均值，假設所有節(jié)點的通信半徑都相同.主要測試的是信標節(jié)點比例、節(jié)點個數(shù)等參數(shù)對定位誤差的影響.

在無線傳感器網絡中，平均定位誤差er為網絡中所有未知節(jié)點的估計值和實際值的差值的平均值[14]：

(9)

式(9)中：(x,y)和(xi,yi)分別為未知節(jié)點的估計位置和實際位置；k表示仿真次數(shù)；un表示未知節(jié)點的個數(shù).

歸一化定位誤差為平均定位誤差er與通信半徑R的比值[15]：

(10)

圖2給出的是信標節(jié)點比例為10%，不同通信半徑下，n取值從1～5的仿真圖.從圖2可以看出，當n的取值在1到3這個區(qū)間段時，未知節(jié)點的平均定位誤差降低的幅度最大，隨著n的逐漸增大平均定位誤差變得越來越平穩(wěn)，尤其當n的取值為4到5這一區(qū)段時，平均定位誤差基本上沒有變化，這說明當n取值達到某一值時定位誤差基本上就處于一個穩(wěn)定階段.對于n取值在3到5這一區(qū)段，半徑大的平均定位誤差要比半徑小的平均定位誤差大.這是因為R值增大使得dij/R值變小，進而使得(dij/R)n值更小，這就使得距離補償小于其實際需要的補償距離，從而使得平均定位誤差增大.為了在獲得較好的定位精度的同時不讓運算開銷增加的特別大，將n取值為4.

圖2 n和R取不同值的平均定位誤差關系圖

圖3給出的是節(jié)點總數(shù)為100，通信半徑為50 m，n取值為4的情況下節(jié)點歸一化平均定位誤差與信標節(jié)點比例仿真圖.從圖3可以看出，3種定位算法的歸一化平均定位誤差隨著信標節(jié)點比例的增加而逐漸減小，當信標節(jié)點的比例增加到一定的程度，歸一化定位誤差逐漸趨于穩(wěn)定.本文改進算法的歸一化定位誤差比傳統(tǒng)的DV-Hop算法降低了約18%～25%，較文獻[13]降低了7%～10%.

圖3 信標節(jié)點比例與歸一化定位誤差關系圖

圖4給出了信標節(jié)點比例為10%，通信半徑為50 m，n取值為4的情況下節(jié)點歸一化平均定點定位誤差與節(jié)點總數(shù)的仿真圖.從圖4可以看出，隨著總節(jié)點數(shù)目增加，3條曲線都逐漸下降，并趨向穩(wěn)定.這是因為在區(qū)域環(huán)境一定的情況下隨著節(jié)點數(shù)據(jù)增加相當于網絡中的節(jié)點密度增加，從而使得定位誤差減小.本文改進算法的歸一定位誤差比傳統(tǒng)的DV-Hop算法降低了約25%～35%，較文獻[13]降低了約8%～12%.

圖4 總節(jié)點個數(shù)與歸一化平均定位誤差關系圖

圖5給出的是信標節(jié)點的比例為10%,n的取值為4時平均定位誤差與節(jié)點之間的通信半徑仿真圖.從圖5可以看出，隨著通信半徑的增大，平均定位誤差也增大，這是因為隨著通信半徑的增大使得節(jié)點之間的跳數(shù)誤差也隨之增大，從而造成了平均跳距誤差的增大，這就使得通過跳數(shù)和平均跳距的乘積來估算未知節(jié)點的位置比實際的位置相差較大，在相同的條件下，本文的算法比文獻[13]中的平均定位誤差都要小.

圖5 通信半徑與平均定位誤差關系圖

4 結論

針對傳統(tǒng)的平均跳距計算出未知節(jié)點到信標節(jié)點距離存在較大的誤差，提出了一種改進的DV-Hop算法,通過對信標節(jié)點間的距離進行虛擬補償，并且對未知節(jié)點到多個信標節(jié)點之間的距離相等進行均值化處理，從而修正了累計跳段距離.經仿真對比，本文改進算法較傳統(tǒng)的DV-Hop算法在性能指標上有較大提升.

[1] 達爾吉(德)，玻爾拉伯爾(美).無線傳感器網絡基礎理論與實踐[M].孫利民.北京：清華大學出版社，2014．

[2] 夏少波,鄒建梅,朱曉麗,等.無線傳感器網絡DV-Hop定位算法的改進[J].計算機應用,2015,35(2):340-344.

[3] Maung N A M,Kawai M.Experimental evaluations of RSS threshold-based optimised DV-HOP localisation for wireless ad-hoc networks[J].Electronics Letters,2014,50(17):1 246-1 248.

[4] Xing T,Zhang S,Zhang F.RSSI enhanced microkernel-based LBS design[J].Journal of Geographic Information System,2013,6(2):109-114.

[5] 李文辰,張 雷,Li Wen-chen,等.無線傳感器網絡加權質心定位算法研究[J].計算機仿真,2013,30(2):191-194.

[6] 曹廣華,張紅杰.一種改進的無線傳感器網絡DV-Hop定位算法[J].化工自動化及儀表,2015,42(6):641-644,718.

[7] 冀常鵬,陳美玲,劉 巧.無線傳感網絡APIT定位算法的改進[J].儀表技術與傳感器,2012(8):84-86.

[8] Niculescu D,Nath B.DV based positioning in ad hoc networks[J].Telecommunication Systems,2003,22(1):267-280.

[9] Shrawan Kumar,D K Lobiyal.An advanced DV-Hop localization algorithm for wireless sensor networks[J].Wireless Personal Communications,2013,71(2):1 365-1 368.

[10] Shrawan Kumar, D K Lobiyal.Power efficient range-free localization algorithm for wireless sensor networks[J].Wireless Networks,2014,20(4):681-694.

[11] Chen X,Zhang B.Improved DV-Hop node localization algorithm in wireless sensor networks[J].International Journal of Distributed Sensor Networks,2012(6):1 018-1 020.

[12] 張愛清,葉新榮,胡海峰,等.基于RSSI每跳分級和跳距修正的DV-HOP改進算法[J].儀器儀表學報,2012,33(11):2 552-2 559..

[13] 肖麗萍,劉曉紅.一種基于跳數(shù)修正的DV-Hop定位算法[J].傳感技術學報,2012,25(12):1 726-1 730.

[14] 潘琢金,劉文春,羅 振,等.無線傳感器網絡DV-Hop定位算法的改進[J].計算機工程與設計,2016,37(7):1 701-1 704,1 740.

[15] 鄔春明,楊 濤,馬冬梅,等.一種改進DV-Hop無線傳感器網絡定位算法[J].河南科技大學學報(自然科學版),2016,37(6):55-60.

【責任編輯：蔣亞儒】

DV-Hop localization algorithm based on distance virtual compensation

DANG Hong-she, LIU Yong, CHANG Yao, HUANG Zi-yue

(College of Electrical and Information Engineering, Shaanxi University of Science & Technology, Xi′an 710021, China)

The distance calculation between the unknown node and the beacon node has a large error,which reduces the positioning accuracy of the unknown nodes in the DV-Hop (Vector-Hop Distance) localization algorithm. Hence,DV-Hop localization algorithm based on the Distance virtual compensation is proposed.The improved algorithm from two aspects,Firstly,the distance between the beacon nodes is compensated according to the number of hops;Secondly,the average distance of multiple beacon nodes which are equal to the unknown nodes is obtaind,So that the distance from the unknown node to the beacon node is more close to the actual value.The simulation results show that the improved algorithm performs better in positioning accuracy than t that of the aditional .localiazation algorithm.

wireless sensor networks; DV-Hop localization algorithm; distance virtual compensation; mean processing; positioning accuracy

2017-01-08

陜西省科技廳社會發(fā)展科技攻關計劃項目(2015SF275)

黨宏社(1962-)，男，陜西武功人，教授，博士，研究方向：工業(yè)過程智能控制、數(shù)字圖像處理

2096-398X(2017)03-0171-05

TP393

A