基于信標節(jié)點密度的DV-Hop改進算法

黃文永，王亞民，盧源遠，解 憂

(西安科技大學 理學院，陜西 西安 710054)

0 引 言

按是否測距，WSN的定位可分為兩種：與距離有關和無關。雖然基于測距的定位算法能達到相當高的定位精度，但其對節(jié)點硬件要求高、成本大、功耗多。相比之下，無需測距的定位要求不高，節(jié)點條件簡易，能耗少，因此更具實用性。DV-Hop算法為比較典型的無需測距算法[1-3]。

DV-Hop算法也存在定位誤差大的問題。針對于此，文獻[4]提出基于RSSI的DV-Hop改進算法，在對第1跳細級劃分基礎上，以距離比權值對跳數(shù)進行修正；文獻[5]采用共線度低的信標節(jié)點作參考，以可信度加權計算未知節(jié)點平均跳距與定位誤差，并把低誤差點化為信標節(jié)點從而增加信標節(jié)點數(shù)；文獻[6]基于誤差距離權重對信標節(jié)點平均每跳距離進行處理，利用改進遺傳算法對未知節(jié)點坐標進行優(yōu)化；文獻[7,8]采用多通信半徑對跳數(shù)細化或校正坐標來提高定位精度；文獻[9]提出利用偏離度小的優(yōu)良信標節(jié)點對未知節(jié)點進行定位，并對定位的坐標再次修正；文獻[10]先利用RSSI測距定位技術選取誤差比較小的數(shù)據(jù)組，再為DV-Hop構建最小二乘法。以上改進對DV-Hop定位精度都有所提高，但也存在硬件要求高或計算復雜等不足。本文將以信標節(jié)點密度為基礎，提出一種有效簡易的DV-Hop改進算法，在對信標節(jié)點密度三維圖形化的基礎上，修正補償信標節(jié)點的平均每跳距離，重新定位未知節(jié)點坐標。該改進算法不僅有效提高定位精度，還能減少網(wǎng)絡節(jié)點計算復雜度及計算過程中的高能損耗。

1 DV-Hop算法與誤差分析

1.1 DV-Hop算法

DV-Hop算法是由美國Dragos Niculescu等提出的一種無需測距定位技術[11]。其步驟為：

(1)信標節(jié)點以距離矢量交換協(xié)議轉(zhuǎn)發(fā)各自的位置和最小跳數(shù)信息。

(2)信標節(jié)點通過接受到的其它信標節(jié)點位置與跳數(shù),計算其平均每跳距離,并廣播到網(wǎng)絡的未知節(jié)點中

(1)

式中：(xi，yi)、(xj，yj)——信標節(jié)點i，j的位置坐標。hij——其最小跳數(shù)。未知節(jié)點對接受到的平均每跳距離與其到信標節(jié)點的最小跳數(shù)進行運算，得出其與各信標節(jié)點的距離

diq=hopi×hiq

(2)

其中，hopi表示最近信標節(jié)點的平均每跳距離，hiq代表該未知節(jié)點與信標節(jié)點的最小跳數(shù)。

(3)通過極大似然估計或三邊定位估算求出未知節(jié)點的坐標。

1.2 誤差分析

對DV-Hop算法進行分析，可以看出誤差的產(chǎn)生存在多方面的因素。例如，信標節(jié)點A，B之間的通信路徑為A-a-c-d-b-B，如圖1所示。信標節(jié)點的平均每跳距離采用該信標節(jié)點到其它信標節(jié)點的總距離與總跳數(shù)之比，由此求出的平均每跳距離總是小于實際的平均每跳距離，使得信標節(jié)點的平均每跳誤差很大。用該誤差大的平均每跳距離定位隨機不均勻的未知節(jié)點，使誤差不斷積累，從而導致未知節(jié)點的定位精度變得更低。本文提出一種基于信標節(jié)點密度來修正定位誤差的方法。由于節(jié)點隨機分布性，采用通信半徑作為衡量尺度。理想情況下A-B之間的平均每跳距離應為R，若hopi偏離R越大，即使各節(jié)點在A-B之間的直線上，也會因在定位中沒有衡量尺度及各節(jié)點間距不同等原因，而使對未知節(jié)點定位產(chǎn)生較大的誤差。

圖1 節(jié)點隨機分布

2 算法的改進思想

本文的改進算法分為兩個部分。第一部分是對信標節(jié)點的平均每跳距離進行修正補償，然后對求出的未知節(jié)點坐標進行重新定位。結果表明本文采用的算法不僅有效提高未知節(jié)點的定位精度而且定位方法簡易，能夠減少傳感器節(jié)點復雜運算帶來的功耗損失。

2.1 信標節(jié)點密度定義

通過節(jié)點的平均每跳距離偏離通信半徑的大小定義為該信標節(jié)點的節(jié)點密度，其公式為

ρi=(R-hopi)/R

(3)

從式(3)可以看出，hopi越小，說明該信標節(jié)點與各信標節(jié)點之間在通信路徑附近的節(jié)點數(shù)越多，其節(jié)點密度越大。為形象地表示信標節(jié)點的定義，把信標節(jié)點密度化為空間坐標的z軸，而平面區(qū)域仍為x，y坐標，如圖2所示。

圖2 信標節(jié)點密度三維化

在使用信標節(jié)點密度下，可以把整個區(qū)域信標節(jié)點密度分布化為空間曲面，各節(jié)點間距因信標節(jié)點密度不同擴展為間距相差不大的起伏面。其中信標節(jié)點所在山峰的高度由信標節(jié)點密度決定，即信標節(jié)點的節(jié)點密度越大，說明信標節(jié)點附近的節(jié)點越密集，而越密集區(qū)域，其對應第三維上的高度越高。

2.2 信標節(jié)點平均跳距補償

為使信標節(jié)點的平均每跳距離更接近于理想的跳距R，本文采用節(jié)點密度ρ作為信標節(jié)點平均每跳距離的修正因子，其含義為節(jié)點原平均每跳距離越小，其節(jié)點密度越大，則需要修正的量越大，反之越小。由于信標節(jié)點的平均每跳總比通信半徑小，所以補償方法應使信標節(jié)點在其原有的長度上增加修正量。即信標節(jié)點的補償公式為

(4)

經(jīng)補償后的信標節(jié)點平均每跳距離為

Chopi=hopi×ci

(5)

其中，hopi為第i個信標節(jié)點的平均每跳距離，ci為其補償因子。ρ對平均每跳距離的直接修正并不明顯，因此對k的取值進行實驗，當k=2時，對信標節(jié)點的平均每跳距離修正最優(yōu)，具體參數(shù)請參考實驗仿真與分析中的圖7。最終修正的信標節(jié)點的平均每跳距離為

(6)

2.3 未知節(jié)點坐標重新定位

導致未知節(jié)點定位誤差大的原因有很多，如果僅對信標節(jié)點的平均每跳距離進行補償，則對未知節(jié)點的定位精度起不到太大作用，因此要對求出的未知節(jié)點的坐標進行重新定位。

利用信標節(jié)點密度，對未知節(jié)點的坐標修正的方法為：以最近的信標節(jié)點A’為中心，壓縮A’與a’之間的距離，其曲面圖如圖2所示。用修正后的最近信標節(jié)點的平均每跳距離求出的未知節(jié)點位置的擴展性如圖2中的a’，而未知節(jié)點a的實際坐標應是a’投影平面區(qū)域的a，對應圖2中的a。在對未知節(jié)點的坐標修正過程中，認為壓縮A(A’)與a’之間距離到1-ρ倍時約等于A與a之間的平面距離，其坐標如圖3所示。在以A為中心對A-a’之間進行壓縮中，設A的坐標為(xi，yi)，a’為經(jīng)過最小二乘法求出的坐標(xa’,ya’)，a的坐標為(xa,ya)。假設A為坐標原點，則a’到A之間在x方向上的距離為

(7)

圖3 壓縮A-a’坐標

壓縮后的長度為原長度的1-ρ倍，則壓縮后的長度為

(8)

其中，ρi為信標節(jié)點i的節(jié)點密度。以信標節(jié)點A為中心(原點)，所求a在x方向上的修正坐標為

(9)

同理可求得a’到A之間在y方向上的距離為

(10)

壓縮1-ρ倍后的長度為

(11)

a在y方向的修正坐標為

(12)

3 實驗仿真與分析

本文采用MATLAB仿真平臺對所提出的改進算法進行實驗，并與原DV-Hop算法對比。實驗中，在100×100的區(qū)域內(nèi)隨機產(chǎn)生節(jié)點坐標。在運算中采用的相對誤差為

(13)

其中，N為未知節(jié)點的數(shù)量，Uje為經(jīng)修正后未知節(jié)點j的坐標，Uj0為其實際坐標，R為通信半徑。并且每個實驗數(shù)據(jù)點都進行100次實驗運算，求取平均值。實驗結果表明，本文提出的改進算法能有效提高對未知節(jié)點的定位精度。

圖4為節(jié)點總數(shù)對相對誤差的影響。設置信標節(jié)點數(shù)為20，分別對節(jié)點總數(shù)為100，125，150，175，200，225，250，275及300進行實驗。

圖4 節(jié)點總數(shù)對相對誤差的影響

圖4(a)為通信半徑R=25 m時的實驗結果。可以看出，當節(jié)點數(shù)超過175時，節(jié)點的增加對提高定位精度作用不大，改進算法基本維持在0.25-0.26的定位誤差，總體定位精度優(yōu)化6%-7%。而當通信半徑為50 m時，實驗結果如圖4(b)所示，改進算法比原DV-Hop算法的優(yōu)化8%-9%。

圖5為通信半徑對相對誤差的影響。實驗中，節(jié)點數(shù)量為100，信標節(jié)點數(shù)為20，對通信半徑為20,25,30,35,40,45,50,55分別進行仿真。

圖5 通信半徑對相對誤差的影響

由圖5可以看出，本文提出的改進算法，定位精度隨著通信半徑的增大而提高。在通信半徑為55時，原DV-Hop算法的定位誤差為27%左右，而經(jīng)本文對算法改進后，定位誤差下降到19%左右。從總體上來看，改進算法比原DV-Hop算法優(yōu)化6%-8%。

圖6為信標節(jié)點數(shù)對相對誤差的影響。實驗中，設置節(jié)點總數(shù)為100，在通信半徑為R=25m和R=50m時，分別對信標數(shù)為15，20，25，30，35，40，45，50進行仿真，實驗結果如圖6所示。

圖6 信標節(jié)點數(shù)對相對誤差的影響

從圖6(a)中可以看出，當通信半徑R=25m時，在信標節(jié)點大于30時，原DV-Hop算法定位誤差在33%-32%，改進的算法的定位誤差在26%-24%，總體上改進算法比原DV-Hop算法優(yōu)化6%-8%左右。而當通信半徑R=50 m時，實驗結果如圖6(b)所示，改進算法比原DV-Hop算法優(yōu)化8%-10%。說明通信半徑的增大，改進算法的優(yōu)化程度越好。

圖7為ρ的次方k值的實驗仿真，從圖中可以看出，當k為2時，對信標節(jié)點的平均每跳距離修正起到最佳的效果，從而驗證了在2.2中補償因子中ρ的次方的合理性。

圖7 k值對相對誤差的影響

4 結束語

本文提出一種基于信標節(jié)點密度的DV-Hop改進算法，該算法以通信半徑為衡量尺度，對信標節(jié)點平均每跳距離進行補償，同時利用最近的信標節(jié)點坐標及其節(jié)點密度對未知節(jié)點的坐標進行重新定位。實驗結果表明，與原DV-Hop算法相比，改進的算法在定位精度上有6%-10%的提高。在修正及重新定位的過程中，對信標節(jié)點密度三維圖形化，不但直觀明了，且改進方法簡易。此外，該算法還能減少網(wǎng)絡節(jié)點計算復雜度及計算過程中的高能損耗。

參考文獻：

[1]FU Caixin.WCGDV-Hop localization algorithm for wireless sensor networks[D].Changchun:Jilin University,2014(in Chinese).[付彩欣.WCGDV-Hop無線傳感器網(wǎng)絡定位算法研究[D].長春:吉林大學,2014.]

[2]Gopakumar A,Jacob L.Power-aware range-free wireless sensor network localization using neighbor distance distribution[J].Wireless Communications & Mobile Computing,2013,13(5):460-482.

[3]Gui L,Val T,Wei A,et al.Improvement of range-free loca-lization technology by a novel DV-Hop protocol in wireless sensor networks[J].Ad Hoc Networks,2015,24:55-73.

[4]WEN Jiangtao,FAN Xuemin,WU Xijun.Improved DV-Hop location algorithm based on hop correction[J].Chinese Journal of Sensors and Actuators,2014,27(1):113-117(in Chinese).[溫江濤,范學敏,吳希軍.基于RSSI跳數(shù)修正的DV-Hop改進算法[J].傳感技術學報,2014,27(1):113-117.]

[5]WANG Jinghui.A node location algorithm in wireless sensor network based on DV-Hop[J].Computer Engineering,2015,41(1):82-86(in Chinese).[王景琿.一種基于DV-Hop的無線傳感器網(wǎng)絡節(jié)點定位算法[J].計算機工程,2015,41(1):82-86.]

[6]CHENG Chao,QIAN Zhihong,FU Caixin,et al.Genetic optimization DV-Hop localization algorithm based on error distance weighted and hop algorithm selection[J].Journal of Electronics & Information Technology,2015,37(10):2418-2423(in Chinese).[程超,錢志鴻,付彩欣,等.一種基于誤差距離加權與跳段算法選擇的遺傳優(yōu)化DV-Hop定位算法[J].電子與信息學報,2015,37(10):2418-2423.]

[7]LIU Shixing,HUANG Junjie,LIU Hongyin,et al.An improving DV-Hop algorithm based on multi communication radius[J].Chinese Journal of Sensors and Actuators,2015,28(6):883-887(in Chinese).[劉士興,黃俊杰,劉宏銀,等.基于多通信半徑的加權DV-Hop定位算法[J].傳感技術學報,2015,28(6):883-887.]

[8]MA Shuli,ZHAO Jianping.Multi communication ranges DV-Hop localization algorithm for wireless sensor network[J].Chinese Journal of Sensors and Actuators,2016,29(4):593-600(in Chinese).[馬淑麗,趙建平.多通信半徑的無線傳感器網(wǎng)絡DV-Hop定位算法[J].傳感技術學報,2016,29(4):593-600.]

[9]LIU Yuzhen,WANG Zhaofeng.Wireless sensor network localization algorithm based on DV-HOP improvement[J].Compu-ter Engineering and Applications,2016,52(4):79-83(in Chinese).[劉玉珍,王兆鋒.基于DV-HOP改進的無線傳感器網(wǎng)絡定位算法[J].計算機工程與應用,2016,52(4):79-83.]

[10]JIN Chun,YE Cheng,HAN Zhibin,et al.Dv-Hop localization algorithm improvements in wireless sensor networks[J].Computer Engineering and Design,2013,34(2):401-404(in Chinese).[金純,葉誠,韓志斌,等.無線傳感器網(wǎng)絡中Dv-Hop定位算法的改進[J].計算機工程與設計,2013,34(2):401-404.]

[11]SHANG Xiaohang.Research on wireless sensor networks localization algorithm based on DV-Hop[D].Changchun:Jilin University,2012(in Chinese).[尚小航.基于DV-Hop的無線傳感器網(wǎng)絡定位算法研究[D].長春:吉林大學,2012.]