趙建平，馬淑麗

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

?

基于雙通信半徑的DV-Hop改進(jìn)算法

趙建平，馬淑麗

(曲阜師范大學(xué) 物理工程學(xué)院,山東 曲阜 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)

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

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò);節(jié)點定位;雙通信半徑DV-Hop;加權(quán)DV-Hop

0引言

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

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

1多通信半徑DV-Hop算法

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

所謂的多通信半徑即網(wǎng)絡(luò)中錨節(jié)點可以通過延時發(fā)送信息，并在每個固定的時間段使用不同的通信半徑。

一般而言，多通信半徑的DV-Hop算法的前提環(huán)境是錨節(jié)點有延時功能，可以有多種通信半徑范圍。網(wǎng)絡(luò)中未知節(jié)點通信范圍相同。所有節(jié)點可以接收和發(fā)送信息。

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

第一步：錨節(jié)點計時開始，向網(wǎng)絡(luò)以通信半徑R1廣播信息。信息內(nèi)容包括錨節(jié)點編號、坐標(biāo)、跳數(shù)值e1。接收節(jié)點保留信息并不轉(zhuǎn)發(fā)。

第二步：計時一段時間(錨節(jié)點傳輸信息和接收節(jié)點保留信息所需要的時間)，假設(shè)為t，錨節(jié)點計時清零，又開始計時，第二次向網(wǎng)絡(luò)廣播，此次廣播信息中的跳數(shù)值為e2，通信半徑使用R2。接收節(jié)點如果在第一步?jīng)]有接收信息則保留并不轉(zhuǎn)發(fā)信息。如果在第一步已經(jīng)接收了某錨節(jié)點的信息則拋棄。

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

(1)

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

最后一步，未知節(jié)點根據(jù)校正值和最小跳數(shù)求到每錨節(jié)點間的距離，如式(2)。當(dāng)?shù)玫匠^三個以上錨節(jié)點距離時，可以用三邊測量法、極大似然估計法等計算坐標(biāo)。

dlj=dHopp×hlj

(2)

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

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

(3)

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

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

(4)

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

2改進(jìn)算法

2.1改進(jìn)基于多通信半徑的DV-Hop算法

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

2.2改進(jìn)錨節(jié)點求平均每一跳距離公式

用式(1)求平均每一跳距離會導(dǎo)致誤差較大。文獻(xiàn)[11]根據(jù)最小均方差準(zhǔn)則提出求錨節(jié)點和平均每一跳距離的公式如式(5)，并提出最佳指數(shù)值概念。

(5)

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

(6)

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

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

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

(7)

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

(8)

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

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

dij=JZi×hij

(9)

3MATLAB實驗

考慮多通信半徑算法中通信半徑數(shù)越多節(jié)點泛洪次數(shù)越多，會影響節(jié)點能量消耗和網(wǎng)絡(luò)生命周期，所以本文只實驗基于雙通信半徑的改進(jìn)算法。

3.1雙通信半徑算法與最佳指數(shù)加權(quán)算法

假設(shè)網(wǎng)絡(luò)區(qū)域為100米邊長的正方形，隨機部署100個節(jié)點，錨節(jié)點覆蓋率9%。節(jié)點分布環(huán)境如圖1所示。

圖1　節(jié)點分布

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

圖2　三種算法對比

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

3.2基于雙通信半徑的最佳指數(shù)加權(quán)算法

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

圖3　求最佳指數(shù)值

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

圖4兩種算法對比

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

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

圖5　兩種算法對比

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

4結(jié)語

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

參考文獻(xiàn)：

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

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

[2]曹文明.傳感器網(wǎng)絡(luò)覆蓋定位模糊信息處理方法[M]. 北京:電子工業(yè)出版社,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]李娟,劉禹,錢志鴻.基于雙通信半徑的傳感器網(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 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]黃炎炎,陳向東,倪進(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 Improved DV-Hop Localization Algorithm for Wireless Sensor Networks[J]. Communications Technology, 2014,47(07):765-769.

[10]劉士興,黃俊杰,劉宏銀等.基于多通信半徑的加權(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 Algorithm based on Multi Communication Radius [J].Chinese Journal of Sensors and Actuators,2015,28(06) :883-887.

[11]馬淑麗,趙建平.無線傳感器網(wǎng)絡(luò)中DV-Hop定位算法的改進(jìn)[J].通信技術(shù),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]馮江,朱強,吳春春.改進(jìn)的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的無線傳感器網(wǎng)絡(luò)定位算法研究[D].太原:太原理工大學(xué),2011.

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

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

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

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

文獻(xiàn)標(biāo)志碼：A

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

基金項目：國家自然科學(xué)基金資助項目(No.11302118)；山東省自然科學(xué)基金資助項目(No.ZR2014FM011)；山東省高等學(xué)?？萍加媱濏椖抠Y助(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