無線傳感器網絡中DV-Hop定位算法的改進

曾福庚

(海南熱帶海洋學院 數學系,海南 三亞,572022)

?

無線傳感器網絡中DV-Hop定位算法的改進

曾福庚

(海南熱帶海洋學院 數學系,海南 三亞,572022)

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

無線傳感器網絡; DV-Hop定位算法;平均每跳距離;權重因子

0 引言

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

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

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

1 DV-Hop算法簡介

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

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

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

(1)

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

信標節點在計算出平均每跳距離值后,將它作為校正值在網絡中泛洪廣播,未知節點收到后,將校正值乘以到該信標節點的最小跳數值作為未知節點與信標節點的距離.

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

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

di=hi×Hopsizei.

(2)

未知節點X到N個信標節點的距離表示如下:

(3)

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

(4)

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

(5)

(6)

使用最小二乘法可以得到未知節點X的估計坐標為:

X=(ATA)-1ATb.

(7)

2 改進的DV-Hop定位算法

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

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

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

(8)

(9)

2.2 細化第3階段(未知節點坐標計算)

在DV-Hop算法第3階段中,對未知節點坐標的計算引入權重因子wp,i,其中p表示未知節點,i表示信標節點.假設某個未知節點到達信標節點的跳數越大,它們之間的距離誤差也會越大,對應的加權應當較小,故取權重因子如下:

(10)

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

(11)

使用最小二乘法可以得到未知節點X的估計坐標為

X=(ATWTAW)-1ATWTWb.

(12)

3 仿真分析

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

(13)

其中(xe,ye)表示未知節點的估計坐標,(xt,yt)表示未知節點的實際坐標,是網絡中所有節點的個數,R為節點通信半徑.

3.1 改變信標節點比率

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

圖1 不同信標節點比率下的比較

圖2 不同信標節點總數下的比較

由圖1觀察到,隨著信標節點比例的增加,誤差率有減少的趨勢.改進算法要明顯優越優于傳統DV-Hop定位算法.在不同的信標節點比率下,改進方案要優于傳統DV-Hop算法大約20%.

3.2 改變節點總數

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

由圖2觀察到,隨著節點總數的增加,誤差率有減少的趨勢,并逐步趨向于平穩.因為改進算法引入了修正校正值和權重因子,所以在相同條件下,改進算法誤差率要明顯低于傳統的DV-Hop算法,總體改進方案要優于傳統DV-Hop算法大約15%.

4 結論

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

[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]楊鳳,史浩山,朱靈波,等.一種基于測距的無線傳感器網絡智能定位算法[J].傳感技術學報, 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]周玲, 康志偉, 何怡剛.基于三角不等式的加權雙曲線定位DV-HOP算法[J].電子測量與儀器學報, 2013, 27(5): 389-395.

[8]馬淑麗, 趙建平.多通信半徑的無線傳感器網絡DV-Hop定位算法[J].傳感技術學報, 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-), 男,漢族,江西吉安人,海南熱帶學院數學系副教授,博士,研究方向為應用數學與密碼學.

TP393

A

1008-6722(2016) 05-0068-04

10.13307/j.issn.1008-6722.2016.05.13