黃文永，王亞民，盧源遠(yuǎn)，解 憂(yōu)

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

0 引 言

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

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

1 DV-Hop算法與誤差分析

1.1 DV-Hop算法

DV-Hop算法是由美國(guó)Dragos Niculescu等提出的一種無(wú)需測(cè)距定位技術(shù)[11]。其步驟為：

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

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

(1)

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

diq=hopi×hiq

(2)

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

(3)通過(guò)極大似然估計(jì)或三邊定位估算求出未知節(jié)點(diǎn)的坐標(biāo)。

1.2 誤差分析

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

圖1 節(jié)點(diǎn)隨機(jī)分布

2 算法的改進(jìn)思想

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

2.1 信標(biāo)節(jié)點(diǎn)密度定義

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

ρi=(R-hopi)/R

(3)

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

圖2 信標(biāo)節(jié)點(diǎn)密度三維化

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

2.2 信標(biāo)節(jié)點(diǎn)平均跳距補(bǔ)償

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

(4)

經(jīng)補(bǔ)償后的信標(biāo)節(jié)點(diǎn)平均每跳距離為

Chopi=hopi×ci

(5)

其中，hopi為第i個(gè)信標(biāo)節(jié)點(diǎn)的平均每跳距離，ci為其補(bǔ)償因子。ρ對(duì)平均每跳距離的直接修正并不明顯，因此對(duì)k的取值進(jìn)行實(shí)驗(yàn)，當(dāng)k=2時(shí)，對(duì)信標(biāo)節(jié)點(diǎn)的平均每跳距離修正最優(yōu)，具體參數(shù)請(qǐng)參考實(shí)驗(yàn)仿真與分析中的圖7。最終修正的信標(biāo)節(jié)點(diǎn)的平均每跳距離為

(6)

2.3 未知節(jié)點(diǎn)坐標(biāo)重新定位

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

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

(7)

圖3 壓縮A-a’坐標(biāo)

壓縮后的長(zhǎng)度為原長(zhǎng)度的1-ρ倍，則壓縮后的長(zhǎng)度為

(8)

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

(9)

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

(10)

壓縮1-ρ倍后的長(zhǎng)度為

(11)

a在y方向的修正坐標(biāo)為

(12)

3 實(shí)驗(yàn)仿真與分析

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

(13)

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

圖4為節(jié)點(diǎn)總數(shù)對(duì)相對(duì)誤差的影響。設(shè)置信標(biāo)節(jié)點(diǎn)數(shù)為20，分別對(duì)節(jié)點(diǎn)總數(shù)為100，125，150，175，200，225，250，275及300進(jìn)行實(shí)驗(yàn)。

圖4 節(jié)點(diǎn)總數(shù)對(duì)相對(duì)誤差的影響

圖4(a)為通信半徑R=25 m時(shí)的實(shí)驗(yàn)結(jié)果?？梢钥闯觯?dāng)節(jié)點(diǎn)數(shù)超過(guò)175時(shí)，節(jié)點(diǎn)的增加對(duì)提高定位精度作用不大，改進(jìn)算法基本維持在0.25-0.26的定位誤差，總體定位精度優(yōu)化6%-7%。而當(dāng)通信半徑為50 m時(shí)，實(shí)驗(yàn)結(jié)果如圖4(b)所示，改進(jìn)算法比原DV-Hop算法的優(yōu)化8%-9%。

圖5為通信半徑對(duì)相對(duì)誤差的影響。實(shí)驗(yàn)中，節(jié)點(diǎn)數(shù)量為100，信標(biāo)節(jié)點(diǎn)數(shù)為20，對(duì)通信半徑為20,25,30,35,40,45,50,55分別進(jìn)行仿真。

圖5 通信半徑對(duì)相對(duì)誤差的影響

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

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

圖6 信標(biāo)節(jié)點(diǎn)數(shù)對(duì)相對(duì)誤差的影響

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

圖7為ρ的次方k值的實(shí)驗(yàn)仿真，從圖中可以看出，當(dāng)k為2時(shí)，對(duì)信標(biāo)節(jié)點(diǎn)的平均每跳距離修正起到最佳的效果，從而驗(yàn)證了在2.2中補(bǔ)償因子中ρ的次方的合理性。

圖7 k值對(duì)相對(duì)誤差的影響

4 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

[1]FU Caixin.WCGDV-Hop localization algorithm for wireless sensor networks[D].Changchun:Jilin University,2014(in Chinese).[付彩欣.WCGDV-Hop無(wú)線傳感器網(wǎng)絡(luò)定位算法研究[D].長(zhǎng)春:吉林大學(xué),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).[溫江濤,范學(xué)敏,吳希軍.基于RSSI跳數(shù)修正的DV-Hop改進(jìn)算法[J].傳感技術(shù)學(xué)報(bào),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ú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法[J].計(jì)算機(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).[程超,錢(qián)志鴻,付彩欣,等.一種基于誤差距離加權(quán)與跳段算法選擇的遺傳優(yōu)化DV-Hop定位算法[J].電子與信息學(xué)報(bào),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).[劉士興,黃俊杰,劉宏銀,等.基于多通信半徑的加權(quán)DV-Hop定位算法[J].傳感技術(shù)學(xué)報(bào),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ú)線傳感器網(wǎng)絡(luò)DV-Hop定位算法[J].傳感技術(shù)學(xué)報(bào),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改進(jìn)的無(wú)線傳感器網(wǎng)絡(luò)定位算法[J].計(jì)算機(jī)工程與應(yīng)用,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).[金純,葉誠(chéng),韓志斌,等.無(wú)線傳感器網(wǎng)絡(luò)中Dv-Hop定位算法的改進(jìn)[J].計(jì)算機(jī)工程與設(shè)計(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ú)線傳感器網(wǎng)絡(luò)定位算法研究[D].長(zhǎng)春:吉林大學(xué),2012.]