基于DV-HOP的改進定位算法*

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

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

基于DV-HOP的改進定位算法*

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

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

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

無線傳感器網絡；節點定位；雙通信半徑DV-Hop；加權DV-HOP

0 引 言

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

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

1 基礎概述

1.1 DV-Hop定位算法

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

DV-Hop定位算法只是利用節點間的傳輸跳數值信息和錨節點的坐標值進行未知節點的坐標計算。假設網絡中所有節點都可以進行雙通信，且通信過程無障礙，每個節點都有自己的通信范圍即通信半徑，自帶GPS導航設備的錨節點有n個。

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

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

第二步：錨節點根據第一步得知的其他錨節點的位置信息等，計算自己的平均每一跳距離：

其中，錨節點i到其他錨節點的平均每一跳距離是dHopi，錨節點i﹑j間的最小跳數是hij。

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

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

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

其中，網絡中節點個數為N，節點通信半徑為R，節點i的真實坐標與估算坐標則分別為(x0i, y0i)﹑(xi,yi)。

1.2 DV-HOP算法存在的不足

第一，利用傳統DV-HOP算法，每個節點要接收和轉發所有錨節點的數據包結構。這些節點處于活動狀態，需要較長時間等待數據包，導致網絡中的通信開銷和能量消耗隨之增加。

第二，錨節點所占的比例不同，平均跳段距離也就不同。比例越高，平均跳段距離越精確。當比例增加到一定程度時，距離保持穩定。但是，當錨節點所占比例過高時，則將增加所需費用。

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

圖1 網絡節點分布

2 改進算法

2.1 改進錨節點每一條距離公式

文獻[11]利用最小均方差準則，錨節點平均每一跳距離滿足：

對函數f求關于dHopi的偏導并取零，得到最小均方誤差下的平均每跳距離公式：

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

文獻[4]改進式（10），提出最佳指數值概念，在最佳值下求錨節點平均每一跳距離。經過多次仿真發現，指數在取非2即取1.9～2.0間的數時，能提高定位精度，公式如下：

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

2.2 改進未知節點選擇校正值的方法

在未知節點選擇和計算校正值時，文獻[7]提出改進未知節點選擇校正值的方法。求未知節點i校正值時，首先將錨節點p通過式（10）求得的平均每一跳距離乘以一個加權系數XSip。這個系數能體現未知節點i與錨節點p間的跳數值大小：

將所有錨節點乘以加權系數的平均每一跳距離累加，并將累加值作為該未知節點的校正值JZi：

最后，將未知節點i的校正值乘以與其他錨節點間的跳數值，求得該未知節點與其他錨節點間的估算距離：

2.3 改進節點間通信半徑的方法

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

圖2 網絡分布

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

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

3 MATLAB實驗

3.1 仿真環境驗證

在邊長為100 m的正方形區域分布109個節點，其中9個錨節點。節點分布環境，如圖3所示。

圖3 仿真環境節點分布

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

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

圖4 五種算法對比

3.2 基于雙通信半徑的最佳跳數加權算法性能比較

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

圖5 求最佳跳數

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

圖6 三種算法對比

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

圖7 兩種算法對比

4 結 語

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

[1] 彭力.無線傳感器網絡技術[M].北京:冶金工業出版社,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中基于最佳指數的加權DVHop算法[J].通信技術,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] 李娟,劉禹,錢志鴻.基于雙通信半徑的傳感器網DV-Hop定位算法[J].吉林大學學報:工學版,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].通信技術,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] 馮江,朱強,吳春春.改進的DV-Hop定位算法研究[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] 黃炎炎,陳向東,倪進權等.改進的DV-Hop無線傳感器網絡定位算法[J].通信技術,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] 劉士興,黃俊杰,劉宏銀等.基于多通信半徑的加權DV-Hop定位算法[J].傳感技術學報,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] 魏全瑞,劉俊,韓九強.改進的無線傳感器網絡無偏距離估計與節點定位算法[J].西安交通大學學報,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].電子與信息學報,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—），女，碩士研究生，主要研究方向為無線傳感器網絡﹑無線通信技術；

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

王 蒙（1990—），男，碩士研究生，主要研究方向為無線傳感器網絡﹑無線通信技術；

楊恒耀（1990—），男，碩士研究生，主要研究方向為無線傳感器網絡﹑無線通信技術；

張 浩（1990—），男，碩士研究生，主要研究方向為無線傳感器網絡﹑無線通信技術。

2016-07-13；

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

國家自然科學基金資助項目（No.11404185）；山東省高等學校科技計劃項目資助（No.J12LN 08）；曲阜師范大學技術開發項目（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)