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

趙建平，馬淑麗

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

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

0引言

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

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

1多通信半徑DV-Hop算法

2003年，美國(guó)羅格斯大學(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算法，并實(shí)驗(yàn)仿真驗(yàn)證了基于雙、三通信半徑的改進(jìn)算法能大大提高DV-Hop算法定位精度。后來(lái)，文獻(xiàn)[10]提出一種基于多通信半徑的DV-Hop算法。

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

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

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

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

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

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

(1)

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

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

dlj=dHopp×hlj

(2)

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

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

(3)

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

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

(4)

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

2改進(jìn)算法

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

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

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

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

(5)

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

(6)

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

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

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

(7)

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

(8)

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

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

dij=JZi×hij

(9)

3MATLAB實(shí)驗(yàn)

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

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

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

圖1　節(jié)點(diǎn)分布

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

圖2　三種算法對(duì)比

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

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

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

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

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

圖4兩種算法對(duì)比

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

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

圖5　兩種算法對(duì)比

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

4結(jié)語(yǔ)

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

參考文獻(xiàn)：

[1]彭力.無(wú)線(xiàn)傳感器網(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]李娟,劉禹,錢(qián)志鴻.基于雙通信半徑的傳感器網(wǎng)DV-Hop定位算法[J].吉林大學(xué)學(xué)報(bào)：工學(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ú)線(xiàn)傳感器網(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é)報(bào),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ú)線(xiàn)傳感器網(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]馮江,朱強(qiáng),吳春春.改進(jìn)的DV-Hop定位算法研究[J].計(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.

[13]蔣馥珍.基DV-HOP的無(wú)線(xiàn)傳感器網(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—)，男，教授，主要研究方向?yàn)闊o(wú)線(xiàn)通信技術(shù)；

馬淑麗(1989—)，女，碩士研究生，主要研究方向?yàn)闊o(wú)線(xiàn)傳感器網(wǎng)絡(luò)、無(wú)線(xiàn)通信技術(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

作者簡(jiǎn)介：

中圖分類(lèi)號(hào)：TP393

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

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

基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(No.11302118)；山東省自然科學(xué)基金資助項(xiàng)目(No.ZR2014FM011)；山東省高等學(xué)?？萍加?jì)劃項(xiàng)目資助(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