無線傳感器網(wǎng)絡(luò)中DV-Hop定位算法的改進(jìn)

曾福庚

(海南熱帶海洋學(xué)院 數(shù)學(xué)系,海南 三亞,572022)

?

無線傳感器網(wǎng)絡(luò)中DV-Hop定位算法的改進(jìn)

曾福庚

(海南熱帶海洋學(xué)院 數(shù)學(xué)系,海南 三亞,572022)

針對無線傳感器網(wǎng)絡(luò)無需測距的DV-Hop定位算法中存在誤差率較大的問題,本文從兩個方面對其進(jìn)行了改進(jìn):引入平均誤差修正信標(biāo)節(jié)點間的平均每跳距離;引入權(quán)重因子計算未知節(jié)點坐標(biāo).仿真結(jié)果表明,改進(jìn)算法比傳統(tǒng)DV-Hop算法誤差率更低,能更好地應(yīng)用于實際場景.

無線傳感器網(wǎng)絡(luò); DV-Hop定位算法;平均每跳距離;權(quán)重因子

0 引言

傳感器是一種能獲取并將估計物理量轉(zhuǎn)換成信號的設(shè)備,且其輸出信號可以由觀察者或儀器讀取.傳感器在無線網(wǎng)絡(luò)中獲得輸入信息,存儲信息,轉(zhuǎn)換和傳輸數(shù)據(jù)到其他設(shè)備[1].比如,熱電偶轉(zhuǎn)換溫度的輸出電壓可以通過一個電壓表讀取.無線傳感器網(wǎng)絡(luò)(WSNS)包括數(shù)以千計的節(jié)點,其內(nèi)置傳感器可以從周圍環(huán)境收集各種信息,已被廣泛用于工業(yè)生產(chǎn)、環(huán)境監(jiān)測、軍事偵察等領(lǐng)域[2].定位技術(shù)是無線傳感器網(wǎng)絡(luò)研究的最重要的問題之一,因為在任何情形中都很需要了解節(jié)點的位置信息.諸如火山監(jiān)控、水質(zhì)監(jiān)測、精確農(nóng)業(yè)等環(huán)境監(jiān)測的應(yīng)用中,如果不知道捕獲的數(shù)據(jù)是在什么位置獲取的,那么測量數(shù)據(jù)是無意義的.此外,節(jié)點位置估計還可以在庫存管理、入侵檢測、道路交通監(jiān)控、健康監(jiān)測、偵察和監(jiān)視等方面有諸多應(yīng)用.

當(dāng)前的定位算法主要分為兩類:基于測距的定位算法(Range-based)[3]和無需測距定位算法(Range-free)[4].基于測距的定位算法通過測量節(jié)點間點對點的距離或角度等信息來實現(xiàn)定位,其定位精度高,對硬件和成本的需求也較高.無需測距定位算法利用網(wǎng)絡(luò)的連通性,通過節(jié)點間的距離來估計未知節(jié)點的位置.受到傳感器價格、體積、功耗以及可擴(kuò)展性等因素的限制,基于測距的定位算法在實際使用中有一定的局限性,而無需測距定位算法具有更高的實用性.

DV-Hop (Distance Vector Hop)算法[5-6]是當(dāng)前研究應(yīng)用中最為廣泛的一種無需測距定位算法,其通過距離矢量的路由協(xié)議獲得各信標(biāo)節(jié)點的信息,突破了未知節(jié)點須與信標(biāo)節(jié)點相鄰才能實現(xiàn)定位的限制[7].然而隨著未知節(jié)點到達(dá)信標(biāo)節(jié)點跳數(shù)的增加,測距誤差也會越來越大,因而計算未知節(jié)點和信標(biāo)節(jié)點的距離估算也比較粗糙.本文通過修正信標(biāo)節(jié)點間的平均每跳距離以及引入權(quán)重因子對DV-Hop算法進(jìn)行改進(jìn).仿真結(jié)果表明,改進(jìn)后的方案可以有效地減少誤差,更好地提高DV-Hop算法的定位精度.

1 DV-Hop算法簡介

DV-Hop[5-6]算法由Niculescu D等人提出,通過計算距離矢量和節(jié)點之間的跳數(shù)來估算未知節(jié)點到信標(biāo)節(jié)點的距離,并應(yīng)用多邊測量法或者最大似然估計計算未知節(jié)點的位置情況.DV-Hop算法主要由以下3個階段組成:

第1階段(計算最小跳數(shù)值): 信標(biāo)節(jié)點通過典型的距離矢量路由交換協(xié)議廣播自身ID和坐標(biāo)信息,使網(wǎng)絡(luò)中所有節(jié)點能計算到各信標(biāo)節(jié)點的最小跳數(shù)值h.

第2階段(計算平均每跳距離值): 信標(biāo)節(jié)點根據(jù)上一階段收到的最小跳數(shù)值和自身坐標(biāo)信息,利用式(1)計算自身的平均每跳距離值.

(1)

其中信標(biāo)節(jié)點i和信標(biāo)節(jié)點j的坐標(biāo)分別為(xi,yi),(xj,yj);hij表示信標(biāo)節(jié)點j到信標(biāo)節(jié)點i的最小跳數(shù)值;dij表示信標(biāo)節(jié)點i和信標(biāo)節(jié)點j的距離.Hopsizei表示信標(biāo)節(jié)點i的平均每跳距離.

信標(biāo)節(jié)點在計算出平均每跳距離值后,將它作為校正值在網(wǎng)絡(luò)中泛洪廣播,未知節(jié)點收到后,將校正值乘以到該信標(biāo)節(jié)點的最小跳數(shù)值作為未知節(jié)點與信標(biāo)節(jié)點的距離.

第3階段(定位估計值計算): 當(dāng)未知節(jié)點獲得到三個以上信標(biāo)節(jié)點的距離時,通過使用最大似然估計計算未知節(jié)點的坐標(biāo).

令信標(biāo)節(jié)點集合S=(xi,yi)T,其中i=1,2,…,N,N,表示信標(biāo)節(jié)點的個數(shù),未知節(jié)點坐標(biāo)X=(x,y)T到信標(biāo)節(jié)點i的最小跳數(shù)值為hi.由第2階段所知,未知節(jié)點X=(x,y)T到信標(biāo)節(jié)點i的距離值為

di=hi×Hopsizei.

(2)

未知節(jié)點X到N個信標(biāo)節(jié)點的距離表示如下:

(3)

將(3)中前N-1個方程依次減去第N個方程并整理得:

(4)

記式(4)為AX=b,其中

(5)

(6)

使用最小二乘法可以得到未知節(jié)點X的估計坐標(biāo)為:

X=(ATA)-1ATb.

(7)

2 改進(jìn)的DV-Hop定位算法

通過對DV-Hop定位算法的原理深入研究,其誤差主要是由最小跳數(shù)值計算出的平均每跳距離造成的,因此,設(shè)法提高后兩個工作步驟,即在定位過程的第2步中對校驗值進(jìn)行修正和第3步中引入權(quán)重因子計算未知節(jié)點坐標(biāo).

2.1 細(xì)化第2階段(計算校驗值)

在DV-Hop算法第2階段中,將信標(biāo)節(jié)點間的距離求和除以它們相互的跳數(shù)之和作為每跳平均距離,每個信標(biāo)節(jié)點將此估計值作為校正值在網(wǎng)絡(luò)中泛洪廣播.由于在網(wǎng)絡(luò)中節(jié)點之間的連通一般不是直線,所以計算出來的校正值要比實際值偏大.信標(biāo)節(jié)點之間實際距離和估計距離存在一定的誤差,而且一般情況下實際距離要比估計距離小.

(8)

(9)

2.2 細(xì)化第3階段(未知節(jié)點坐標(biāo)計算)

在DV-Hop算法第3階段中,對未知節(jié)點坐標(biāo)的計算引入權(quán)重因子wp,i,其中p表示未知節(jié)點,i表示信標(biāo)節(jié)點.假設(shè)某個未知節(jié)點到達(dá)信標(biāo)節(jié)點的跳數(shù)越大,它們之間的距離誤差也會越大,對應(yīng)的加權(quán)應(yīng)當(dāng)較小,故取權(quán)重因子如下:

(10)

將權(quán)重因子wp,i(i=1,2,…,N-1)寫成對角矩陣式,有

(11)

使用最小二乘法可以得到未知節(jié)點X的估計坐標(biāo)為

X=(ATWTAW)-1ATWTWb.

(12)

3 仿真分析

為了驗證改進(jìn)算法的性能,本節(jié)使用MATLAB 2014a對傳統(tǒng)DV-Hop定位算法和改進(jìn)算法在不同條件下進(jìn)行對比分析.在模擬實驗中,所有信標(biāo)節(jié)點和未知節(jié)點都是隨機(jī)部署在平面區(qū)域內(nèi),通過改變信標(biāo)節(jié)點的數(shù)量和傳感器節(jié)點的數(shù)量兩個方面來比較兩個算法的性能.在模擬中,定位平均誤差函數(shù)[8-9]如下:

(13)

其中(xe,ye)表示未知節(jié)點的估計坐標(biāo),(xt,yt)表示未知節(jié)點的實際坐標(biāo),是網(wǎng)絡(luò)中所有節(jié)點的個數(shù),R為節(jié)點通信半徑.

3.1 改變信標(biāo)節(jié)點比率

首先比較傳統(tǒng)DV-Hop定位算法和改進(jìn)算法在不同信標(biāo)節(jié)點比率下的性能.假設(shè)所有節(jié)點的數(shù)目是80,傳感器節(jié)點的通信半徑為10m. 取50次模擬結(jié)果的平均值作為誤差率,逐步增加信標(biāo)節(jié)點的比例,具體的結(jié)果如圖1所示.

圖1 不同信標(biāo)節(jié)點比率下的比較

圖2 不同信標(biāo)節(jié)點總數(shù)下的比較

由圖1觀察到,隨著信標(biāo)節(jié)點比例的增加,誤差率有減少的趨勢.改進(jìn)算法要明顯優(yōu)越優(yōu)于傳統(tǒng)DV-Hop定位算法.在不同的信標(biāo)節(jié)點比率下,改進(jìn)方案要優(yōu)于傳統(tǒng)DV-Hop算法大約20%.

3.2 改變節(jié)點總數(shù)

比較兩個算法在不同節(jié)點總數(shù)下的性能.假設(shè)信標(biāo)節(jié)點的比率為20%,傳感器節(jié)點的通信半徑為10m.取50次模擬結(jié)果的平均值作為誤差率,逐步將節(jié)點總數(shù)從30增加到100,得到的結(jié)果如圖2所示.

由圖2觀察到,隨著節(jié)點總數(shù)的增加,誤差率有減少的趨勢,并逐步趨向于平穩(wěn).因為改進(jìn)算法引入了修正校正值和權(quán)重因子,所以在相同條件下,改進(jìn)算法誤差率要明顯低于傳統(tǒng)的DV-Hop算法,總體改進(jìn)方案要優(yōu)于傳統(tǒng)DV-Hop算法大約15%.

4 結(jié)論

本文改進(jìn)算法分為兩個方面:修正每跳平均距離以及引入權(quán)重因子計算未知節(jié)點坐標(biāo).計算量方面,改進(jìn)算法要比傳統(tǒng)DV-Hop算法計算量稍大,但總體能以相對較小的計算量獲得較低的誤差率.降低誤差率是定位算法的一個關(guān)鍵目標(biāo),而仿真分析結(jié)果表明:在不同的信標(biāo)節(jié)點比率下,改進(jìn)方案要優(yōu)于傳統(tǒng)DV-Hop算法大約20%,此外在不同的節(jié)點總數(shù)下,改進(jìn)方案要優(yōu)于傳統(tǒng)DV-Hop算法大約15%,因此改進(jìn)方案在實際應(yīng)用中更具優(yōu)勢.

[1]GargM,GorshiEA,SinghEM.AReviewonLocalizationTechniquesinWSN[J].InternationalJournalofEngineeringScience, 2016, 6(5): 5804-5808.

[2]DaiH,ChenAG,GuXF,etal.Localisationalgorithmforlarge-scaleandlow-densitywirelesssensornetworks[J].Electronicsletters, 2011, 47(15): 881-883.

[3]楊鳳,史浩山,朱靈波,等.一種基于測距的無線傳感器網(wǎng)絡(luò)智能定位算法[J].傳感技術(shù)學(xué)報, 2008, 21(1): 135-140.

[4]LiM,LiuY.RenderedPath:Range-FreeLocalizationinAnisotropicSensorNetworksWithHoles[J].IEEE/ACMTransactionsonNetworking, 2010, 18(1): 320-332.

[5]NiculescuD,NathB.DVbasedpositioninginadhocnetworks[J].TelecommunicationSystems, 2003, 22(1-4): 267-280.

[6]NiculescuD,NathB.Adhocpositioningsystem(APS)usingAOA[C].INFOCOM2003.Twenty-SecondAnnualJointConferenceoftheIEEEComputerandCommunications.IEEESocieties.IEEE, 2003, 3: 1734-1743.

[7]周玲, 康志偉, 何怡剛.基于三角不等式的加權(quán)雙曲線定位DV-HOP算法[J].電子測量與儀器學(xué)報, 2013, 27(5): 389-395.

[8]馬淑麗, 趙建平.多通信半徑的無線傳感器網(wǎng)絡(luò)DV-Hop定位算法[J].傳感技術(shù)學(xué)報, 2016(4): 593-600.

[9]ZhangJ,GuoN,LiJ.AnImprovedDV-HopLocalizationAlgorithmBasedontheNodeDeploymentinWirelessSensorNetworks[J].InternationalJournalofSmartHome, 2015, 9(10): 197-204.

(編校:何軍民)

Improved DV-Hop Localization Algorithm for Wireless Sensor Networks

ZENG Fu-geng

(Department of Mathematics, Hainan Tropical Ocean University, Sanya Hainan 572022, China)

The conventional DV-Hop algorithm is a typical range-free localization algorithm. It will bring about large error, due to taking average hop distance as the expected distant. In order to reduce the error, the original algorithm was improved from two aspects. Firstly, the average hop distance of the beacon nodes was corrected by introducing the average hop distance error. Secondly, the weight factor was added so as to calculate the coordinates of the unknown nodes. The simulation results show that the improved algorithm has lower error rate than that of the conventional DV-Hop algorithm, thus it applies to the actual scene more accurately.

wireless sensor networks; DV-Hop localization algorithm; average hop distance; weight factor

2016-08-14

三亞市院地科技合作項目(2015YD14)

曾福庚(1983-), 男,漢族,江西吉安人,海南熱帶學(xué)院數(shù)學(xué)系副教授,博士,研究方向為應(yīng)用數(shù)學(xué)與密碼學(xué).

TP393

A

1008-6722(2016) 05-0068-04

10.13307/j.issn.1008-6722.2016.05.13