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

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

?

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

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

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

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

無線傳感器網(wǎng)絡(luò)； DV-Hop定位算法； 距離虛擬補(bǔ)償； 均值處理，定位精度

0 引言

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

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

1 DV-Hop定位算法

1.1 DV-Hop算法的描述

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

(1)第1階段

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

(2)第2階段

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

(1)

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

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

dui=HopSizei×hopui

(2)

(3)第3階段

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

(3)

通過下面的公式即可計(jì)算出未知節(jié)點(diǎn)u的坐標(biāo)：

(4)

(5)

(6)

則有P=(ATA)-1ATB.

1.2DV-Hop誤差分析

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

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

圖1 傳感器網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖

2 改進(jìn)的DV-Hop算法

2.1 已有的改進(jìn)算法

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

2.2 本文改進(jìn)的DV-Hop算法

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

2.2.1 信標(biāo)節(jié)點(diǎn)間的距離補(bǔ)償

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

(7)

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

2.2.2 調(diào)整未知節(jié)點(diǎn)到信標(biāo)之間的距離

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

(8)

3 實(shí)驗(yàn)仿真和結(jié)果分析

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

在無線傳感器網(wǎng)絡(luò)中，平均定位誤差er為網(wǎng)絡(luò)中所有未知節(jié)點(diǎn)的估計(jì)值和實(shí)際值的差值的平均值[14]：

(9)

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

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

(10)

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

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

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

圖3 信標(biāo)節(jié)點(diǎn)比例與歸一化定位誤差關(guān)系圖

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

圖4 總節(jié)點(diǎn)個(gè)數(shù)與歸一化平均定位誤差關(guān)系圖

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

圖5 通信半徑與平均定位誤差關(guān)系圖

4 結(jié)論

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

[1] 達(dá)爾吉(德)，玻爾拉伯爾(美).無線傳感器網(wǎng)絡(luò)基礎(chǔ)理論與實(shí)踐[M].孫利民.北京：清華大學(xué)出版社，2014．

[2] 夏少波,鄒建梅,朱曉麗,等.無線傳感器網(wǎng)絡(luò)DV-Hop定位算法的改進(jìn)[J].計(jì)算機(jī)應(yīng)用,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,等.無線傳感器網(wǎng)絡(luò)加權(quán)質(zhì)心定位算法研究[J].計(jì)算機(jī)仿真,2013,30(2):191-194.

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

[7] 冀常鵬,陳美玲,劉 巧.無線傳感網(wǎng)絡(luò)APIT定位算法的改進(jìn)[J].儀表技術(shù)與傳感器,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每跳分級(jí)和跳距修正的DV-HOP改進(jìn)算法[J].儀器儀表學(xué)報(bào),2012,33(11):2 552-2 559..

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

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

[15] 鄔春明,楊 濤,馬冬梅,等.一種改進(jìn)DV-Hop無線傳感器網(wǎng)絡(luò)定位算法[J].河南科技大學(xué)學(xué)報(bào)(自然科學(xué)版),2016,37(6):55-60.

【責(zé)任編輯：蔣亞儒】

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

陜西省科技廳社會(huì)發(fā)展科技攻關(guān)計(jì)劃項(xiàng)目(2015SF275)

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

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

TP393

A