孟雯雯，趙建平，王 蒙，楊恒耀，張 浩

（曲阜師范大學(xué) 物理工程學(xué)院，山東 曲阜 273165）

基于DV-HOP的改進(jìn)定位算法*

孟雯雯，趙建平，王 蒙，楊恒耀，張 浩

（曲阜師范大學(xué) 物理工程學(xué)院，山東 曲阜 273165）

節(jié)點(diǎn)定位技術(shù)是無線傳感器網(wǎng)絡(luò)的關(guān)鍵技術(shù)之一。基于雙通信半徑的DV-Hop定位算法，比傳統(tǒng)DV-Hop算法大大提高了定位精度，但是還可以進(jìn)一步改進(jìn)。在雙通信半徑定位算法基礎(chǔ)上，用跳數(shù)值變換概念改進(jìn)錨節(jié)點(diǎn)計算平均每一跳距離的公式，并結(jié)合平均每跳距離進(jìn)行加權(quán)處理。MATALB仿真實驗證明，提出的基于雙通信半徑的跳數(shù)變換加權(quán)DV-Hop算法能提高基于雙通信半徑算法的定位精度，且不會增加節(jié)點(diǎn)的硬件成本。

無線傳感器網(wǎng)絡(luò)；節(jié)點(diǎn)定位；雙通信半徑DV-Hop；加權(quán)DV-HOP

0 引 言

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN）有大量微型﹑低成本的節(jié)點(diǎn)，在無人值守的應(yīng)用環(huán)境中，節(jié)點(diǎn)一般由飛機(jī)等隨機(jī)拋撒[1]。在無線傳感器網(wǎng)絡(luò)定位技術(shù)中，節(jié)點(diǎn)分兩類：錨節(jié)點(diǎn)和未知節(jié)點(diǎn)。錨節(jié)點(diǎn)可以知道自己位置信息，但是成本比未知節(jié)點(diǎn)高，在網(wǎng)絡(luò)中一般占少數(shù)。未知節(jié)點(diǎn)靠錨節(jié)點(diǎn)計算自身的位置信息，成本低，占網(wǎng)絡(luò)中節(jié)點(diǎn)的大多數(shù)。網(wǎng)絡(luò)中每個節(jié)點(diǎn)都需要知道自身位置，否則采集的信息毫無意義。定位技術(shù)有多種，其中無需測距定位算法因成本低﹑定位過程簡單而得到了廣泛應(yīng)用[2]。在精度要求不是過高的定位應(yīng)用中，DV-Hop算法是應(yīng)用較為廣泛的無需測距定位算法之一。

DV-Hop算法[3-6]只是用節(jié)點(diǎn)間廣播的信息和跳數(shù)值計算坐標(biāo)，誤差很大。影響節(jié)點(diǎn)定位精度大的原因很多，如通信半徑﹑錨節(jié)點(diǎn)平均每一跳距離﹑未知節(jié)點(diǎn)校正值的選取﹑錨節(jié)點(diǎn)部署方式等。許多文獻(xiàn)為了提高定位精度，不斷改進(jìn)算法。本文結(jié)合文獻(xiàn)[6]提出的基于多通信半徑的DV-Hop改進(jìn)算法，在求錨節(jié)點(diǎn)平均每一跳距離﹑未知節(jié)點(diǎn)校正值的選取上進(jìn)一步改進(jìn)算法，提出一種基于多通信半徑最佳指數(shù)值下多跳數(shù)變換加權(quán)的DV-Hop算法。最后，通過仿真實驗驗證了算法的精度和穩(wěn)定性。

1 基礎(chǔ)概述

1.1 DV-Hop定位算法

DV-Hop定位算法是由美國羅格斯大學(xué)（Rutgers University）Dragos Niculescu等人提出的6種分布式定位算法之一[2]。

DV-Hop定位算法只是利用節(jié)點(diǎn)間的傳輸跳數(shù)值信息和錨節(jié)點(diǎn)的坐標(biāo)值進(jìn)行未知節(jié)點(diǎn)的坐標(biāo)計算。假設(shè)網(wǎng)絡(luò)中所有節(jié)點(diǎn)都可以進(jìn)行雙通信，且通信過程無障礙，每個節(jié)點(diǎn)都有自己的通信范圍即通信半徑，自帶GPS導(dǎo)航設(shè)備的錨節(jié)點(diǎn)有n個。

DV-Hop算法步驟[3-6]如下：

第一步：錨節(jié)點(diǎn)向網(wǎng)絡(luò)廣播信息，包括自身位置信息﹑初始跳數(shù)值﹑節(jié)點(diǎn)編號等。路由方式為泛洪方式。設(shè)定一個較大的跳數(shù)值閾值，轉(zhuǎn)播過程中如果跳數(shù)值超過閾值則轉(zhuǎn)發(fā)停止。接收節(jié)點(diǎn)接到信息后，比較接收跳數(shù)值的大小。如果比自己保留的跳數(shù)值大，則拋棄信息；如果較小，則保留信息，并將跳數(shù)值加1后，轉(zhuǎn)發(fā)出去。

第二步：錨節(jié)點(diǎn)根據(jù)第一步得知的其他錨節(jié)點(diǎn)的位置信息等，計算自己的平均每一跳距離：

其中，錨節(jié)點(diǎn)i到其他錨節(jié)點(diǎn)的平均每一跳距離是dHopi，錨節(jié)點(diǎn)i﹑j間的最小跳數(shù)是hij。

第三步：錨節(jié)點(diǎn)再次向網(wǎng)絡(luò)廣播信息，包括自己的平均每一跳距離信息﹑節(jié)點(diǎn)編號。未知節(jié)點(diǎn)按照就近原則只接收一個錨節(jié)點(diǎn)的信息，并將其作為自己計算平均每一跳距離時的校正值。假設(shè)未知節(jié)點(diǎn)l的校正值為dHopp（即錨節(jié)點(diǎn)p為向該未知節(jié)點(diǎn)第一個送達(dá)信息），未知節(jié)點(diǎn)l與錨節(jié)點(diǎn)j間的跳數(shù)為hlj，則未知節(jié)點(diǎn)估算自己與其他錨節(jié)點(diǎn)間的距離為：

第四步：未知節(jié)點(diǎn)得到所有錨節(jié)點(diǎn)間的估算距離后，用三邊測量法﹑極大似然法等計算自身坐標(biāo)。假設(shè)未知節(jié)點(diǎn)坐標(biāo)(x,y)，未知節(jié)點(diǎn)與錨節(jié)點(diǎn)i間的估算距離di，則極大似然估計法如下：

算法的性能指標(biāo)用定位精度判定。定位精度值越小，定位精度越高，如式（8）：

其中，網(wǎng)絡(luò)中節(jié)點(diǎn)個數(shù)為N，節(jié)點(diǎn)通信半徑為R，節(jié)點(diǎn)i的真實坐標(biāo)與估算坐標(biāo)則分別為(x0i, y0i)﹑(xi,yi)。

1.2 DV-HOP算法存在的不足

第一，利用傳統(tǒng)DV-HOP算法，每個節(jié)點(diǎn)要接收和轉(zhuǎn)發(fā)所有錨節(jié)點(diǎn)的數(shù)據(jù)包結(jié)構(gòu)。這些節(jié)點(diǎn)處于活動狀態(tài)，需要較長時間等待數(shù)據(jù)包，導(dǎo)致網(wǎng)絡(luò)中的通信開銷和能量消耗隨之增加。

第二，錨節(jié)點(diǎn)所占的比例不同，平均跳段距離也就不同。比例越高，平均跳段距離越精確。當(dāng)比例增加到一定程度時，距離保持穩(wěn)定。但是，當(dāng)錨節(jié)點(diǎn)所占比例過高時，則將增加所需費(fèi)用。

第三，只是利用錨節(jié)點(diǎn)坐標(biāo)信息和信息傳輸?shù)奶鴶?shù)值定位，節(jié)點(diǎn)真實坐標(biāo)與定位坐標(biāo)之間誤差很大。如圖1所示，網(wǎng)絡(luò)中分布著A﹑B﹑C三個錨節(jié)點(diǎn)，其他為未知節(jié)點(diǎn)。錨節(jié)點(diǎn)B的平均每一跳距離為，而計算的錨節(jié)點(diǎn)B的平均每跳距離要小于實際平均每跳距離，誤差較大。此外，錨節(jié)點(diǎn)B到錨節(jié)點(diǎn)A﹑C的每一跳距離長短不一樣，每兩跳段間都有角度（三個錨節(jié)點(diǎn)不共線），所以用直線距離代替折段距離，求得校正值，誤差很大。未知節(jié)點(diǎn)用校正值乘以最小跳數(shù)值估算與錨節(jié)點(diǎn)間的距離，導(dǎo)致較大的估算距離誤差，最終影響定位結(jié)果的精確度。

圖1 網(wǎng)絡(luò)節(jié)點(diǎn)分布

2 改進(jìn)算法

2.1 改進(jìn)錨節(jié)點(diǎn)每一條距離公式

文獻(xiàn)[11]利用最小均方差準(zhǔn)則，錨節(jié)點(diǎn)平均每一跳距離滿足：

對函數(shù)f求關(guān)于dHopi的偏導(dǎo)并取零，得到最小均方誤差下的平均每跳距離公式：

文獻(xiàn)[12]用式（10）求錨節(jié)點(diǎn)平均每一跳距離，然后未知節(jié)點(diǎn)接收所有錨節(jié)點(diǎn)的平均每一跳距離。計算與錨節(jié)點(diǎn)間估算距離時，求到哪個節(jié)點(diǎn)的距離用它自己的平均每一跳距離，即求未知節(jié)點(diǎn)i與錨節(jié)點(diǎn)j的估算距離為：

文獻(xiàn)[4]改進(jìn)式（10），提出最佳指數(shù)值概念，在最佳值下求錨節(jié)點(diǎn)平均每一跳距離。經(jīng)過多次仿真發(fā)現(xiàn)，指數(shù)在取非2即取1.9～2.0間的數(shù)時，能提高定位精度，公式如下：

未知節(jié)點(diǎn)只接收離自己最近的錨節(jié)點(diǎn)發(fā)過來的平均每一跳距離信息。文獻(xiàn)[6]將最佳指數(shù)的基應(yīng)用到雙通信半徑中，提高了精度。文獻(xiàn)[5]及文獻(xiàn)[6]在給定節(jié)點(diǎn)每跳距離賦值時，都默認(rèn)節(jié)點(diǎn)分布在以使用的錨節(jié)點(diǎn)為圓心，以R/2或R為半徑的圓上，在節(jié)點(diǎn)隨機(jī)分布的環(huán)境中，這種情況幾乎不可能出現(xiàn)。鑒于此，本文就跳數(shù)變換給予。下文給出了求出最佳跳數(shù)值的具體方法。

2.2 改進(jìn)未知節(jié)點(diǎn)選擇校正值的方法

在未知節(jié)點(diǎn)選擇和計算校正值時，文獻(xiàn)[7]提出改進(jìn)未知節(jié)點(diǎn)選擇校正值的方法。求未知節(jié)點(diǎn)i校正值時，首先將錨節(jié)點(diǎn)p通過式（10）求得的平均每一跳距離乘以一個加權(quán)系數(shù)XSip。這個系數(shù)能體現(xiàn)未知節(jié)點(diǎn)i與錨節(jié)點(diǎn)p間的跳數(shù)值大?。?/p>

將所有錨節(jié)點(diǎn)乘以加權(quán)系數(shù)的平均每一跳距離累加，并將累加值作為該未知節(jié)點(diǎn)的校正值JZi：

最后，將未知節(jié)點(diǎn)i的校正值乘以與其他錨節(jié)點(diǎn)間的跳數(shù)值，求得該未知節(jié)點(diǎn)與其他錨節(jié)點(diǎn)間的估算距離：

2.3 改進(jìn)節(jié)點(diǎn)間通信半徑的方法

為了得到更精確的跳數(shù)值，文獻(xiàn)[5]提出在計算平均每一跳距離時，提出可以考慮錨節(jié)點(diǎn)用多個通信半徑的方法。以2通信半徑為例，如圖2所示。D﹑E﹑F為錨節(jié)點(diǎn)，a﹑b﹑c﹑d﹑e為未知節(jié)點(diǎn)，通信半徑為R。錨節(jié)點(diǎn)D與未知節(jié)點(diǎn)a﹑b的距離分別為R﹑0.5R，錨節(jié)點(diǎn)E與未知節(jié)點(diǎn)b﹑c的距離都為0.5R。如果用一般的DV-Hop算法，錨節(jié)點(diǎn)D向未知節(jié)點(diǎn)a﹑b發(fā)送信息時，跳數(shù)值都加1；錨節(jié)點(diǎn)E向未知節(jié)點(diǎn)b﹑c發(fā)信息時，跳數(shù)值是1。假如錨節(jié)點(diǎn)有兩個通信半徑，分別為R﹑R/2，則當(dāng)使用R/2通信半徑時，節(jié)點(diǎn)D與b間的跳數(shù)值可以為0.5，節(jié)點(diǎn)E與b﹑c間跳數(shù)值可以為0.5?？梢?，這樣基于2通信半徑的DV-Hop算法得到的跳數(shù)值很精確。

圖2 網(wǎng)絡(luò)分布

但是，多通信半徑算法也存在不足。在第二次及以后的泛洪中，若發(fā)送節(jié)點(diǎn)為未知節(jié)點(diǎn)，接收節(jié)點(diǎn)為錨節(jié)點(diǎn)，則未知節(jié)點(diǎn)到其一跳范圍內(nèi)的錨節(jié)點(diǎn)間的跳數(shù)值記為1。如果未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的距離在R/2范圍內(nèi)，跳數(shù)值仍記1，則導(dǎo)致計算平均每一跳距離時的誤差很大。如圖2所示，未知節(jié)點(diǎn)d﹑e向錨節(jié)點(diǎn)F發(fā)送信息，若按文獻(xiàn)[5]算法，則跳數(shù)值都加1，而未知節(jié)點(diǎn)d﹑e與錨節(jié)點(diǎn)F間距離分別為R﹑R/2。所以，文獻(xiàn)[5]算法只是將第一次泛洪時錨節(jié)點(diǎn)到未知節(jié)點(diǎn)的跳數(shù)值記為0.5或1，沒有考慮轉(zhuǎn)播過程中的精化跳數(shù)值。

因此，本文在雙通信半徑基礎(chǔ)上將跳數(shù)值精化，求出閾值內(nèi)最佳跳數(shù)值u。仿真結(jié)果表明，本文方案極大提高了定位精度。

3 MATLAB實驗

3.1 仿真環(huán)境驗證

在邊長為100 m的正方形區(qū)域分布109個節(jié)點(diǎn)，其中9個錨節(jié)點(diǎn)。節(jié)點(diǎn)分布環(huán)境，如圖3所示。

圖3 仿真環(huán)境節(jié)點(diǎn)分布

在相同錨節(jié)點(diǎn)覆蓋率和不同通信半徑下，仿真原DV-Hop算法﹑文獻(xiàn)[4]DV-Hop算法﹑文獻(xiàn)[5]雙通信半徑的DV-Hop算法﹑文獻(xiàn)[6]雙通信半徑的DV-Hop算法以及本文改進(jìn)的DV-Hop算法的定位精度。由于節(jié)點(diǎn)分布的隨機(jī)性，程序仿真100次，結(jié)果如圖4所示。

定位精度是評判一個定位算法的重要指標(biāo)，值越小說明定位誤差越小，定位性能越好。由仿真可見，本文改進(jìn)算法比文獻(xiàn)[5]及文獻(xiàn)[6]算法，定位精度大大提高。通信半徑50 m時，由實驗數(shù)據(jù)可得本文比文獻(xiàn)[6]算法提高定位精度15%。

圖4 五種算法對比

3.2 基于雙通信半徑的最佳跳數(shù)加權(quán)算法性能比較

由于在雙通信半徑算法中，如果未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的距離在R/2到R范圍內(nèi)，跳數(shù)值均記1，導(dǎo)致節(jié)點(diǎn)距離在R/2到R范圍內(nèi)的節(jié)點(diǎn)均被認(rèn)為其分布在以該錨節(jié)點(diǎn)為圓心R/2為半徑的圓上。由錨節(jié)點(diǎn)和未知節(jié)點(diǎn)的分布可以觀察到，在隨機(jī)分布的環(huán)境中，這種分布的幾率幾乎為零。所以，原有雙通信算法存在較大誤差。因此，本文將跳數(shù)變換給定，經(jīng)過多次仿真得出圖5，求出雙通信半徑中的最佳跳數(shù)給定值。

圖5 求最佳跳數(shù)

經(jīng)過多次仿真實驗發(fā)現(xiàn)，錨節(jié)點(diǎn)覆蓋率9%。例如，文獻(xiàn)[6]跳數(shù)值取1時，誤差較大，當(dāng)精度精確到0.01時，可以得到更佳的u值。多次試驗發(fā)現(xiàn)，不同的錨節(jié)點(diǎn)覆蓋率和通信半徑都會影響u的取值，但最佳跳數(shù)取值均在0.94～0.96之間。由于節(jié)點(diǎn)分布的隨機(jī)性，程序仿真100次。如圖6所示，在不同的通信半徑下，本文算法比文獻(xiàn)[6]算法定位精度高約3%。

圖6 三種算法對比

為了進(jìn)一步驗證本文改進(jìn)算法的定位性能，仿真不同錨節(jié)點(diǎn)覆蓋率和不同通信半徑下的改進(jìn)。由于文獻(xiàn)[6]中已經(jīng)給出文獻(xiàn)[5]與文獻(xiàn)[6]的精度比較，本文不再贅述，這里只給出兩種精度更高的算法比較，結(jié)果如圖7所示。可見，本文算法精度較文獻(xiàn)[6]進(jìn)一步提高。

圖7 兩種算法對比

4 結(jié) 語

本文針對DV-Hop算法的不足，提出了一種多跳數(shù)變換的雙通信算法。仿真實驗表明，基于該方法改進(jìn)的DV-Hop算法能減小定位誤差，具有有效性。但是，由于該方法存在累積定位誤差以及能耗增多方面的影響，因此需進(jìn)一步研究改進(jìn)。

[1] 彭力.無線傳感器網(wǎng)絡(luò)技術(shù)[M].北京:冶金工業(yè)出版社,2011:2.

PENG Li.W ireless Sensor Network Technology[M]. Beijing:Metallurgical Industry Press,2011:2.

[2] HU Juan,JIANG M in-lan.An Im p roved Node Localization Algorithm in Wireless Sensor Network[C]. Advanced Research and Technology in Industry App lications(WARTIA),2014 IEEE W orkshop on,2014:398-401.

[3] WANG Chen.An Improved DV-distance Localization Algorithm for Wireless Sensor Networks[C].Advanced Computer Control(ICACC),2010:472-476.

[4] 馬淑麗,趙建平.WSN中基于最佳指數(shù)的加權(quán)DVHop算法[J].通信技術(shù),2015,48(10):1147-1151.

MA Shu-li,ZHAO Jian-ping.W eighted DV-Hop A lgorithm based on Op timal Index in WSN[J]. Communications Technology,2015,48(10):1147-1151.

[5] 李娟,劉禹,錢志鴻.基于雙通信半徑的傳感器網(wǎng)DV-Hop定位算法[J].吉林大學(xué)學(xué)報:工學(xué)版,2014,44(02):502-507.

LI Juan,LIU Yu,QIAN Zhi-hong.Improved DV-Hop Localization Algorithm based on Two Communication Ranges for W ireless Sensor Network[J].Journal of Jilin University(Engineering and Technology Edition),2014,44(02):502-507.

[6] 趙建平,馬淑麗.基于雙通信半徑的DV-Hop改進(jìn)算法[J].通信技術(shù),2015,48(12):1406-1410.

ZHAO Jian-p ing,MA Shu-li.The Best Index Weigh ted DV-Hop A lgorithm based on Doub le Communication Radius[J].Communications Technolo gy,2015,48(12):1406-1410.

[7] 馮江,朱強(qiáng),吳春春.改進(jìn)的DV-Hop定位算法研究[J].計算機(jī)工程,2012,38(19):74-81.

FENG Jiang,ZHU Qiang,WU Chun-chun.Research on Improved DV-Hop Localization Algorithm[J].Computer Engineering,2012,38(19):74-81.

[8] 黃炎炎,陳向東,倪進(jìn)權(quán)等.改進(jìn)的DV-Hop無線傳感器網(wǎng)絡(luò)定位算法[J].通信技術(shù),2014,47(07):765-769.

HUANG Yan-yan,CHEN Xiang-dong,NI Jin-quan,et al.An Imp roved DV-Hop Localization A lgorithm for W ireless Sensor Networks[J].Communications Technology,2014,47(07):765-769.

[9] 劉士興,黃俊杰,劉宏銀等.基于多通信半徑的加權(quán)DV-Hop定位算法[J].傳感技術(shù)學(xué)報,2015,28(06):883-887.

LIU Shi-xing,HUANG Jun-jie,LIU Hong-yin.An Improving DV-Hop A lgorithm based on Multi Communication Radius[J].Chinese Journal of Sensors and Actuators,2015,28(06):883-887.

[10] Savarese C,Langendoen K,Rabaey J M.Robust Positioning Algo-rithms for Distributed Ad-Hoc Wireless Sensor Networks[C].Monterey:USENIX Technical Annual Conference,2001.

[11] 魏全瑞,劉俊,韓九強(qiáng).改進(jìn)的無線傳感器網(wǎng)絡(luò)無偏距離估計與節(jié)點(diǎn)定位算法[J].西安交通大學(xué)學(xué)報,2014,48(06):1-6.

WEI Quan-rui,LIU Jun,HAN Jiu-qiang.An Improved DV-hop Node Localization Algorithm based on Unbiased Estimation for W ireless Sensor Networks [J].Journal of Xi’an Jiaotong Unibersity,2014,48(06):1-6.

[12] 嵇瑋瑋,劉中.DV-Hop定位算法在隨機(jī)傳感器網(wǎng)絡(luò)中的應(yīng)用研究[J].電子與信息學(xué)報,2008,30(04):970-974.

JI Wei-wei,LIU Zhong.Study on the Application of DV-Hop Localization Algorithms to Random Sensor Networks[J].Journal of Electronics & In formation Technology,2008,30(04):970-974.

M odified Localization Algorithm based on DV-hop

MENG Wen-wen, ZHAO Jian-ping, WANG Meng, YANG Heng-yao, ZHANG Hao

(College of Physics Engineering, Qufu Normal University, Qufu Shandong 273165, China)

Node localization technology is one of the key technologies in wireless sensor networks. DVHop localization algorithm based on the double communication radius, as compared with the traditional algorithms, could fairly improve the positioning accuracy, and however, this accuracy still has the space to be further improved. Based on the double communication radius location algorithm, the formula for calculating the average hop distance of anchor nodes is improved by using the concept of hop value transformation, and in combination with the weighted average per hop distance. MATALB simulation indicates that the proposed algorithm based on the double communication radius algorithm of DV-Hop algorithm, can improve the positioning accuracy. In addition, this modified algorithm could not increase hardware cost of the node.

WSN; node localization; double communication radius DV-Hop; weighted DV-Hop

TP212.9；TN929.5

A

1002-0802(2016)-11-1447-06

10.3969/j.issn.1002-0802.2016.11.007

孟雯雯（1990—），女，碩士研究生，主要研究方向為無線傳感器網(wǎng)絡(luò)﹑無線通信技術(shù)；

趙建平（1964—），男，教授，主要研究方向為無線通信技術(shù)；

王 蒙（1990—），男，碩士研究生，主要研究方向為無線傳感器網(wǎng)絡(luò)﹑無線通信技術(shù)；

楊恒耀（1990—），男，碩士研究生，主要研究方向為無線傳感器網(wǎng)絡(luò)﹑無線通信技術(shù)；

張 浩（1990—），男，碩士研究生，主要研究方向為無線傳感器網(wǎng)絡(luò)﹑無線通信技術(shù)。

2016-07-13；

2016-10-12 Received date:2016-07-13;Revised date:2016-10-12

國家自然科學(xué)基金資助項目（No.11404185）；山東省高等學(xué)?？萍加媱濏椖抠Y助（No.J12LN 08）；曲阜師范大學(xué)技術(shù)開發(fā)項目（No.hxkj2015017）

Foundation Item:National Natural Science Foundation of China(No.11404185);Science and Technology Project of Higher Education of Shandong Province(No.J12LN08);Qufu Normal University Technology Development Project(No.hxkj2015017)