基于雙通信半徑的DV-Hop改進算法

趙建平，馬淑麗

(曲阜師范大學 物理工程學院,山東 曲阜 273165)

?

基于雙通信半徑的DV-Hop改進算法

趙建平，馬淑麗

(曲阜師范大學 物理工程學院,山東 曲阜 273165)

Foundation Item:National Natural Science Foundation of China(No.11302118); Natural Science Foundation of Shandong Province(No. ZR2014FM011);Supported by the Science and Technology Project of Higher Education of Shandong Province(No.J12LN08)

摘要：節點定位技術是無線傳感器網絡的關鍵技術之一。基于雙通信半徑的DV-Hop定位算法雖然比DV-Hop算法大大提高了定位精度，但是還可以進一步改進。在雙通信半徑定位算法基礎上，用最佳指數值概念改進錨節點計算平均每一跳距離的公式。將平均每跳距離進行加權處理，未知節點選擇校正值時，用所有錨節點與未知節點距離的遠近影響未知節點的校正值。MATALB仿真實驗證明，提出的基于雙通信半徑的最佳指數加權DV-Hop算法能提高基于雙通信半徑算法的定位精度。改進的算法不會增加節點的硬件成本。

關鍵詞：無線傳感器網絡;節點定位;雙通信半徑DV-Hop;加權DV-Hop

0引言

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

DV-Hop算法只是用節點間傳輸信息和跳數值計算坐標[5]，誤差很大。影響節點定位精度大的原因很多，如通信半徑、錨節點平均每一跳距離、未知節點校正值的選取、錨節點部署方式等。許多文獻為了提高定位精度而改進算法。本文結合其他文獻(如文獻[6])提出的基于多通信半徑的DV-Hop算法，在求錨節點平均每一跳距離、未知節點校正值的選取上進一步改進算法，并提出一種基于多通信半徑最佳指數值加權的DV-Hop算法。

1多通信半徑DV-Hop算法

2003年，美國羅格斯大學(Rutgers University)Dragos Niculescu等人提出6種分布式定位算法，DV-Hop定位算法是其中之一[7-8]。多通信半徑DV-Hop算法是DV-Hop算法的一種改進算法。2014年，文獻[6]提出基于雙通信半徑改進的DV-Hop算法。文獻[9]在此基礎上提出基于三通信半徑的改進DV-Hop算法，并實驗仿真驗證了基于雙、三通信半徑的改進算法能大大提高DV-Hop算法定位精度。后來，文獻[10]提出一種基于多通信半徑的DV-Hop算法。

所謂的多通信半徑即網絡中錨節點可以通過延時發送信息，并在每個固定的時間段使用不同的通信半徑。

一般而言，多通信半徑的DV-Hop算法的前提環境是錨節點有延時功能，可以有多種通信半徑范圍。網絡中未知節點通信范圍相同。所有節點可以接收和發送信息。

n通信半徑的DV-Hop算法定位步驟：

第一步：錨節點計時開始，向網絡以通信半徑R1廣播信息。信息內容包括錨節點編號、坐標、跳數值e1。接收節點保留信息并不轉發。

第二步：計時一段時間(錨節點傳輸信息和接收節點保留信息所需要的時間)，假設為t，錨節點計時清零，又開始計時，第二次向網絡廣播，此次廣播信息中的跳數值為e2，通信半徑使用R2。接收節點如果在第一步沒有接收信息則保留并不轉發信息。如果在第一步已經接收了某錨節點的信息則拋棄。

第n+1步：錨節點計算自己平均每一跳距離，如式(1)，并廣播。接收節點只接受最近的錨節點平均跳距，并作為校正值。

(1)

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

最后一步，未知節點根據校正值和最小跳數求到每錨節點間的距離，如式(2)。當得到超過三個以上錨節點距離時，可以用三邊測量法、極大似然估計法等計算坐標。

dlj=dHopp×hlj

(2)

dHopp為未知節點l的校正值(p即錨節點p)，hlj為未知節點l與錨節點j間的最小跳數值。

一般，多個通信半徑DV-Hop算法中錨節點最大通信半徑與未知節點的通信半徑相同，在第一步到第n步錨節點發送的跳數值和通信半徑根據下式得到。

(3)

由式(3)看出，通信半徑R越多，跳數值e劃分的越細，計算的平均每一跳距離越精確。文獻[10]指出錨節點的通信半徑個數越多定位精度越高，但是網絡節點泛洪次數越多節點能耗越大。

定位精度是評判一個定位算法的重要指標，如式(4)，值越小說明定位誤差越小，定位性能越好。

(4)

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

2改進算法

2.1改進基于多通信半徑的DV-Hop算法

本文在多通信半徑DV-Hop算法基礎上實施最佳指數值下的加權DV-Hop算法。本文改進的算法定位步驟與n通信半徑的DV-Hop算法前n步相似，在第n+1步和最后一步分別進行算法的改進。在第n+1步改進錨節點計算平均每一跳距離的公式。在最后一步，改進未知節點獲取校正值的方法。

2.2改進錨節點求平均每一跳距離公式

用式(1)求平均每一跳距離會導致誤差較大。文獻[11]根據最小均方差準則提出求錨節點和平均每一跳距離的公式如式(5)，并提出最佳指數值概念。

(5)

本文將計算平均每一跳距離公式改為式(6)，仿真出多通信半徑算法下定位精度達到最高時的指數值α，并將其作為最佳值數值代入式(6)，提出最佳指數值下的多通信半徑DV-Hop改進算法。經實驗發現，本文在n通信半徑的DV-Hop算法第n+1步采用式(6)，在最佳指數值α下計算錨節點平均每一跳距離，會降低多通信半徑DV-Hop算法誤差，提高定位精高度。

(6)

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

多通信半徑DV-Hop算法將未知節點的校正值選擇為離自己最近的錨節點的平均每一跳距離。文獻[12-13]改進DV-Hop算法時，選擇全部錨節點的平均每一跳距離，提出對參與未知節點定位的錨節點進行加權處理。

本文改進多通信半徑DV-Hop算法中校正值的選擇和計算方法：最后一步求未知節點i校正值時，首先在第n+1步將錨節點p通過式(2)求得的平均每一跳距離乘以一個加權系數XSip。這個系數能體現未知節點i與錨節點p間的跳數值大小。使與未知節點較近的錨節點系數值較大，如式(7)：

(7)

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

(8)

式(8)中錨節點平均每一跳距離dHopp采用最佳指數值下的式(6)計算，進一步減小距離估算誤差。

最后，將未知節點i的校正值乘以與其他錨節點間的跳數值，求得該未知節點與其它錨節點間的估算距離。本文算法在n通信半徑的DV-Hop算法最后一步采用式(9)計算未知節點與錨節點的估算距離，如式(9)：

dij=JZi×hij

(9)

3MATLAB實驗

考慮多通信半徑算法中通信半徑數越多節點泛洪次數越多，會影響節點能量消耗和網絡生命周期，所以本文只實驗基于雙通信半徑的改進算法。

3.1雙通信半徑算法與最佳指數加權算法

假設網絡區域為100米邊長的正方形，隨機部署100個節點，錨節點覆蓋率9%。節點分布環境如圖1所示。

圖1　節點分布

在相同錨節點覆蓋率和不同的通信半徑下，仿真對比文獻[6]提出的基于雙通信半徑的DV-Hop算法、原DV-Hop算法、最佳指數值下的加權DV-Hop算法(單通信半徑)。對比兩種改進算法能提高的定位精度。由于節點分布隨機性，程序仿真100次，如圖2所示。

圖2　三種算法對比

文獻[6]算法比原DV-Hop算法能大大提高定位精度。最佳指數下的加權DV-Hop算法提高的定位精度沒有文獻[6]算法高。通信半徑35米時，文獻[6]、最佳指數加權DV-Hop算法分別提高定位精度12.7%、1.85%。

3.2基于雙通信半徑的最佳指數加權算法

將基于雙通信半徑加權DV-Hop算法用式(6)求錨節點平均每一跳距離。取不同的α值，找出使雙通信半徑加權DV-Hop算法的定位精度最高時的α值，并將此值作為最佳值。如圖3所示，相同通信半徑下，隨著指數值增大，定位精度先提高后降低，且不同的通信半徑對應不同的最佳指數。

圖3　求最佳指數值

將最佳指數值下基于雙通信半徑的加權DV-Hop算法(即本文改進的算法)與文獻[6]算法對比，由于節點分布隨機性，程序仿真100次。如圖4所示，在不同的通信半徑下，本文算法比文獻[6]算法定位精度高約2%。

圖4兩種算法對比

對比圖2和圖4，可以看出，錨節點覆蓋率9%，不同的通信半徑下，最佳指數下的加權DV-Hop算法能比DV-Hop算法提高定位精度約1.7%左右，基于雙通信半徑的最佳指數加權算法能比基于雙通信半徑的算法提高2%左右的定位精度，所以兩種改進的DV-Hop算法的結合能提高的定位精度不是疊加的。本文改進的基于雙通信半徑的DV-Hop算法能大大提高DV-Hop算法定位精度，通信半徑35米時，提高約14.65%。

為了進一步驗證改進算法的定位性能，仿真不同錨節點覆蓋率和不同通信半徑下改進的算法，并與基于雙通信半徑的DV-Hop算法對比，如圖5所示。

圖5　兩種算法對比

在錨節點覆蓋率取10%~28%時，通信半徑取25、30、35、40、45、50米時，改進的基于雙通信半徑DV-Hop算法定位精度明顯比基于雙通信半徑DV-Hop算法高2.5%左右。

4結語

基于多通信半徑的DV-Hop算法能大大提高節點定位精度。本文結合文獻[6]提出的基于雙通信半徑的DV-Hop算法進一步改進算法，提出基于雙通信半徑的最佳指數加權DV-Hop算法。首先，改進錨節點平均每一跳距離公式，求出最佳指數值。然后，將最佳指數之下的錨節點平均每一跳距離乘以加權系數。改進未知節點估算與錨節點間距離的公式，從而減小估算誤差。實驗結果證明改進的算法能進一步提高定位精度，錨節點覆蓋率9%，通信半徑35米時，分別比DV-Hop算法、雙通信半徑的DV-Hop算法提高定位精度14.7%、2%。下一步將研究未知節點獲取校正值的方法，進一步提升定位精度。

參考文獻：

[1]彭力.無線傳感器網絡技術[M].北京:冶金工業出版社,2011:2.

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

[2]曹文明.傳感器網絡覆蓋定位模糊信息處理方法[M]. 北京:電子工業出版社,2010:11.

CAO Wen-ming. Fuzzy Information Processing Method for Sensor Network Coverage[M].Beijing: Electronic Industry Press,2010:11.

[3]HU Juan, JIANG Min-lan. An Improved Node Localization Algorithm in Wireless Sensor Network[C].Advanced Research and Technology in Industry Applications (WARTIA), 2014 IEEE Workshop on,Sept2014,398-401.

[4]WANG W, CHEN. An Improved DV-Distance Localization Algorithm for Wireless Sensor Networks[C]. Advanced Computer Control (ICACC), 2010 2nd International Conference on .IEEE, March 2010 , Volume 5 ,472-476.

[5]WANG Bang, WU Guang, WANG Shu, YANG L T. Localization based on Adaptive Regulated Neighborhood Distance for Wireless Sensor Networks with a General Radio Propagation Model[J].IEEE.Sensors Journal,2014, 14(11):3754-3762.

[6]李娟,劉禹,錢志鴻.基于雙通信半徑的傳感器網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 Wireless Sensor Network[J]. Journal of Jilin University (Engineering and Technology Edition), 2014,44(02):502-507.

[7]Njculescu D, Nath B. DV based Positioning in Ad Hoc Networks[J]. Journal of Telecommunication System, 2003,22(1/4):267-280.

[8]Njculescu D, Nath B. Ad Hoc Positioning System(APS) Using AoA[C].IEEE INFOCOM 2003,San Franciso, 2003,3:1734-1743.

[9]黃炎炎,陳向東,倪進權等.改進的DV-Hop無線傳感器網絡定位算法[J].通信技術,2014, 47(07):765- 769.

HUANG Yan-yan, CHEN Xiang-dong, NI Jin-quan, et al. An Improved DV-Hop Localization Algorithm for Wireless Sensor Networks[J]. Communications Technology, 2014,47(07):765-769.

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

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

[11]馬淑麗,趙建平.無線傳感器網絡中DV-Hop定位算法的改進[J].通信技術,2015,48(07):840-844.

MA Shu-li,ZHAO Jian-ping. The Improvement of DV-Hop Algorithm in Wirless Sensor Networks[J]. Communications Technology, 2015, 48(07):840-844.

[12]馮江,朱強,吳春春.改進的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.

[13]蔣馥珍.基DV-HOP的無線傳感器網絡定位算法研究[D].太原:太原理工大學,2011.

JIANG Fu-zhen. Research on Location Algorithm based on DV-Hop in WSN[D].Taiyuan:Taiyuan University of Technology,2011.

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

馬淑麗(1989—)，女，碩士研究生，主要研究方向為無線傳感器網絡、無線通信技術。

DV-Hop Modified Algorithm based on Double Communication Radius

ZHAO Jian-ping， MA Shu-li

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

Abstract：Node localization technology is one of the key technologies in wireless sensor networks. DV-Hop localization algorithm based on double communication radius, although has considerable improvement on the positioning accuracy considerably as compared with DV-Hop algorithm, also could be further modified. Based on dual communication radius location algorithm, the formula for calculating the average jump distance of the anchor nodes is improved with the optimal index value concept. When the average hop distance is weighted by the unknown node selection correction, the corrected value of the unknown node could be affected by the distance of between the anchor node and the unknown node. MATALB simulation experiments show that the proposed optimal index weighted DV-Hop algorithm based on double communication radius could improve the positioning precision without any increase in hardware cost of the node.

Key words：wireless sensor network; node localization; double communication radius DV-Hop; weighted DV-Hop

作者簡介：

中圖分類號：TP393

文獻標志碼：A

文章編號：1002-0802(2015)12-1406-05

基金項目：國家自然科學基金資助項目(No.11302118)；山東省自然科學基金資助項目(No.ZR2014FM011)；山東省高等學校科技計劃項目資助(No.J12LN08)

收稿日期：2015-07-16；修回日期：2015-10-25Received date:2015-07-16；Revised date：2015-10-25

doi:10.3969/j.issn.1002-0802.2015.12.017