陳晶杰，羅 明

(西安電子科技大學，西安 710071)

?

一種無線傳感器網(wǎng)絡中DV-Hop定位的改進算法

陳晶杰，羅 明

(西安電子科技大學，西安 710071)

針對無線傳感器網(wǎng)絡中經(jīng)典定位算法DV-Hop存在定位精度低的缺陷，提出了一種改進算法。在傳統(tǒng)DV-Hop算法的基礎上，首先采用最小均方誤差準則校正信標節(jié)點的平均每跳距離，然后對各未知節(jié)點到參考信標節(jié)點的平均每跳距離進行加權處理，最后通過參數(shù)分析，對未知節(jié)點進行位置修正。仿真實驗結果表明，改進算法相比于傳統(tǒng)的DV-Hop定位算法以及已有的改進算法具有很高的定位精度，并且無需增加額外的硬件設施。因此在工程上具有很好的實用性。

無線傳感器網(wǎng)絡；節(jié)點定位；DV-Hop算法；最小均方誤差

0 引 言

無線傳感器網(wǎng)絡(WSN)由大量傳感器組成。這些微型傳感器彼此合作，對環(huán)境中觀測對象的參數(shù)進行實時的監(jiān)測、感知和采集，并且通過無線通道，以自組網(wǎng)的形式傳送到控制中心[1]。傳感器網(wǎng)絡在軍事國防、環(huán)境監(jiān)測、城市管理、防恐反恐、生物醫(yī)療等眾多應用領域內發(fā)揮著巨大的作用[2-4]。節(jié)點定位是實現(xiàn)上述應用的重要前提，沒有位置信息的傳感數(shù)據(jù)對用戶是沒有任何意義的[5]。因此，消息節(jié)點位置的獲取在傳感器網(wǎng)絡的實際應用中發(fā)揮著至關重要的作用。

無線傳感器節(jié)點定位算法大體可以分為兩大類[6-7]：基于測距的定位算法和無需測距的定位算法?；跍y距的定位算法主要是測量點到點之間的絕對距離或者方位信息，這種定位算法雖然有很高的定位精度，但是其計算量比較大，增加了節(jié)點系統(tǒng)的通信開銷，違背了無線傳感器網(wǎng)絡低功耗的原則，在現(xiàn)實中很難實現(xiàn)。無需測距的定位算法不需要直接測量節(jié)點之間的距離和方位信息，這種算法主要是利用節(jié)點之間的網(wǎng)絡連通性來確定節(jié)點的具體位置，并且無需測距的定位算法在原有的硬件設施上就能夠實現(xiàn)節(jié)點定位，不需添加額外的硬件設施，對無線傳感器的小型化、時效性具有重要意義。DV-Hop是美國路特葛斯大學的Dragos Niculescu等人利用距離矢量路由協(xié)議和GPS定位原理提出的一系列無需測距定位算法中的一種節(jié)點定位算法[8]。

通過對DV-Hop定位算法的研究，節(jié)點定位在網(wǎng)絡環(huán)境下存在著比較大的定位誤差。在對DV-Hop定位算法的改進方面，文獻[9]、[10]提出了對各信標節(jié)點的平均每跳距離相加取均值的改進算法，即算術平均處理。文獻[11]提出基于未知節(jié)點對各信標節(jié)點平均每跳距離進行加權處理的改進算法，即加權處理。本文則在重點研究分析了Dv-Hop節(jié)點定位算法對平均每跳距離以及定位方程解算過程中存在不足的基礎上，提出了一種改進方法。通過仿真驗證了該方法具有很好的定位性能。

1 DV-Hop節(jié)點定位算法

DV-Hop定位算法是一種基于距離矢量路由協(xié)議而無需進行測距的定位算法，其主要思想是將未知節(jié)點到各個信標節(jié)點之間的距離用網(wǎng)絡平均每跳距離乘以跳數(shù)來表示的，最后再使用三邊定位法或最大似然估計法來確定未知節(jié)點的的坐標信息[7]。

DV-Hop節(jié)點定位算法主要由3個階段組成：

第1階段：首先通過距離矢量路由交換協(xié)議，使網(wǎng)絡環(huán)境中的所有節(jié)點接收到其距離各個信標節(jié)點的最小跳數(shù)和位置坐標信息，然后信標節(jié)點i根據(jù)其收到的距離其他信標節(jié)點的最小跳數(shù)和坐標信息后，利用公式(1)計算自己的平均每跳距離：

(1)

式中：n為總的信標節(jié)點個數(shù)；(xi,yi)和(xj,yj)分別為信標節(jié)點i和j的坐標信息；hij為信標節(jié)點i和j之間的最小跳數(shù)。

第2階段：各個信標節(jié)點首先將自己在第一階段中計算出平均每跳距離，利用可控洪泛法廣播至網(wǎng)絡中，然后網(wǎng)絡中所有的節(jié)點只接收距離自己最近信標節(jié)點的平均每跳距離。最后網(wǎng)絡中的未知節(jié)點根據(jù)自己信息表中記錄的距離各個信標節(jié)點的跳數(shù)和平均每跳距離，利用公式(2)計算其與信標節(jié)點之間的估計值：

dik=Savi×hik

(2)

式中：dik為未知節(jié)點k和信標節(jié)點i之間的估計值；hik為未知節(jié)點k和信標節(jié)點i之間的最小跳數(shù)。

第3階段：未知節(jié)點利用極大似然估計法估算自己的位置。假設未知節(jié)點k的坐標為(x,y)，第i個信標節(jié)點的坐標為(xi,yi)，信標節(jié)點i和未知節(jié)點k之間的估算距離由第2階段求得為di，則由以下公式求得未知節(jié)點的坐標：

(3)

公式(3)中用前n-1項減去最后一項，方程可以寫成AX=B的形式，其中：

(4)

(5)

利用標準最小二乘法可得未知節(jié)點估計坐標：

X=(A′A)-1A′B

(6)

2 DV-Hop節(jié)點定位算法的改進

DV-Hop節(jié)點定位算法的改進主要由以下3個部分組成：

2.1 基于最小均方誤差準則求得平均每跳距離

本文采用最小均方誤差準則對計算出的平均每跳距離進行改進。由DV-Hop定位算法原理可以知道，信標節(jié)點在接收到其他信標節(jié)點的位置信息后，平均每跳距離Savi滿足公式(7)：

(7)

式中：dij為信標節(jié)點i和j之間的真實距離；(xi,yi)和(xj,yj)分別為信標節(jié)點i和j的坐標；hij為信標節(jié)點i和j之間的最小跳數(shù)；εij為進行估值所帶來的誤差，平均每跳距離的合理選擇應該使得εij的值最小。

(8)

(9)

2.2 對未知節(jié)點到各個信標節(jié)點的平均每跳距離進行統(tǒng)一的加權處理

通過分析，傳統(tǒng)Dv-Hop定位算法在計算節(jié)點的平均每跳距離中僅僅考慮距離自己最近的信標節(jié)點廣播的信息，即每個節(jié)點只接收距離自己最近信標節(jié)點廣播的平均每跳距離和跳數(shù)，這樣的接收機具有一定的局限性，為了統(tǒng)籌整個網(wǎng)絡對節(jié)點的影響，本文采用對未知節(jié)點到各個信標節(jié)點的距離進行統(tǒng)一加權處理的思想。即未知節(jié)點在接收到各個信標節(jié)點的信息后，利用跳數(shù)通過公式(10)計算每個信標節(jié)點的權值：

(10)

式中：λi為未知節(jié)點到第i個信標節(jié)點所對應的權值;hi為未知節(jié)點到第i個信標節(jié)點的跳數(shù)。

結合公式(9)、(10)可求得新的平均每跳距離Savk：

(11)

則未知節(jié)點k到每個信標節(jié)點的距離為：

dki=Savk×hki

(12)

式中：Savk為未知節(jié)點k所對應的平均每跳距離；hki為未知節(jié)點k到第i個信標節(jié)點的跳數(shù)；dki為未知節(jié)點k到第i個信標節(jié)點的估計距離。

未知節(jié)點k從多個信標節(jié)點中通過不同的權值得到平均每跳距離，使得定位節(jié)點的平均每跳距離更加符合網(wǎng)絡的實際平均每跳距離。

2.3 對未知節(jié)點的估值進行修正，進一步提高定位精度

未知節(jié)點利用極大似然估計法估算自己的位置:

(13)

在公式(13)中，用離未知節(jié)點p最近的那項信標節(jié)點k去除其余n-1項，得到：

?i=1,2,…,n且i≠k

(14)

簡化公式(14)得到n-1項公式：

(15)

公式(15)的矩陣形式為：

GZ=D

(16)

利用標準最小二乘法對方程GZ=D進行求解得：

Z=(G′G)-1G′D

(17)

通過式(17)求得的未知節(jié)點具有很好的定位精度，可以使用公式(17)中求出的s(s=x2+y2)對得到的未知節(jié)點進行更新，以提高定位精度。

根據(jù)公式(17)未知節(jié)點可以估算出自己的坐標(xu,yu)，并且求出s的值。但是由于未知節(jié)點與各信標節(jié)點之間距離dpi計算誤差的影響，未知節(jié)點并不滿足s=x2+y2。未知節(jié)點的估算坐標如圖1所示。

圖1 未知節(jié)點的估算坐標

A為由公式(17)計算出的未知節(jié)點的坐標，B和C分別為當s>x2+y2和s

(18)

(19)

未知節(jié)點的更新通過(xu,yu)和(xs,ys)的均值來表示。因此，未知節(jié)點的更新坐標可以表示為：

(20)

3 算法仿真

為了檢測比較本文改進算法的性能，本次仿真在MATLAB平臺上對傳統(tǒng)DV-Hop定位算法，文獻[9]、[10]提出的算術平均處理算法，文獻[11]提出的加權處理算法以及本文提出的改進算法在基于節(jié)點定位誤差方面進行仿真評估。網(wǎng)絡仿真的模型參數(shù)如下假設：在100 m×100 m的區(qū)域里隨機生成傳感器節(jié)點的坐標，并且假設各傳感器節(jié)點的感知、計算以及通信能力一致。

衡量DV-Hop節(jié)點定位算法中最重要的一個性能指標就是定位精度[11]:

(21)

從公式(20)中可以看到，總的節(jié)點數(shù)(N)、信標節(jié)點數(shù)(n)、節(jié)點通信距離(R)都會對DV-Hop的定位精度產(chǎn)生影響。因此，本次仿真主要考慮以下3種情況，即信標節(jié)點比率與相對定位誤差的關系、網(wǎng)絡節(jié)點總個數(shù)與相對定位誤差的關系、節(jié)點的通信距離與相對定位誤差的關系。

3.1 信標節(jié)點比率與定位誤差的關系

仿真參數(shù)：節(jié)點數(shù)為300，通信半徑為25 m，信標節(jié)點比例為5%、10%、15%、20%、25%、30%。由圖2明顯可知，隨著信標節(jié)點比率的不斷增加，4種節(jié)點定位算法的相對定位誤差都呈遞減趨勢；并且在相同條件下，本文改進算法的平均定位精度明顯優(yōu)于傳統(tǒng)DV-Hop定位算法、算術平均定位算法以及加權處理定位算法。

圖2 信標節(jié)點比率與定位誤差的關系

3.2 網(wǎng)絡節(jié)點總個數(shù)與定位誤差的關系

圖3 網(wǎng)絡節(jié)點總個數(shù)與定位誤差的關系

仿真參數(shù)：通信半徑為25 m，信標節(jié)點數(shù)為30，總節(jié)點數(shù)依次為150、200、250、300、350、400、450。由圖3可知，在網(wǎng)絡節(jié)點總個數(shù)相同的情況下，本文改進算法的定位誤差較低；并且隨著節(jié)點總個數(shù)的增加，4種定位算法的定位誤差均有所降低。本文改進定位算法誤差比DV-Hop傳統(tǒng)定位算法平均降低了8%～10%。

3.3 節(jié)點的通信距離與定位誤差的關系

仿真參數(shù)：在原有網(wǎng)絡仿真環(huán)境區(qū)域內隨機產(chǎn)生200個傳感器節(jié)點，并且使得信標節(jié)點的個數(shù)為40。為了研究節(jié)點通信半徑與定位誤差的關系，使節(jié)點的通信距離依次為20 m、25 m、30 m、35 m、40 m、45 m。從圖4的仿真結果可以看出，本文提出改進算法的定位精度比傳統(tǒng)的DV-Hop算法、算術平均改進算法以及加權改進算法都要高，相比傳統(tǒng)DV-Hop定位誤差降低了約7%。

圖4 節(jié)點通信距離與定位誤差的關系

4 結束語

本文在分析傳統(tǒng)DV-Hop定位算法的基礎上，結合已有改進算法提出了一種基于最小均方誤差準則，采用對平均每跳距離進行加權處理的算法，并且對未知節(jié)點的估值位置重新進行修正。因而，本改進算法的位置估計偏差較傳統(tǒng)的DV-Hop算法、算術平均算法以及加權處理算法都要小。仿真實驗表明，本文改進算法相比傳統(tǒng)的DV-Hop定位算法以及已有的改進算法具有很高的定位精度，并且無需增加額外的硬件設施，因此在工程上具有較強的實用性。

[1] 崔莉,鞠海玲,苗勇.無線傳感器網(wǎng)絡研究進展[J].計算機研究與發(fā)展,2005,42(1):163-174.

[2] Corken P,Wark T,Jurdak R.Environmental Wireless Sensor Networks[J].IEEE,2010,98(11):1903- 1917.

[3] Sun G,Xu G Q B.Corrosion monitoring sensor networks with energy harvesting[J].Sensors Journal,IEEE,2011,11(6):1476-1477.

[4] Raty T D.Survey on contemporary remote surveillance systems for public safety[J].IEEE,2010,40(5):493- 515.

[5] Cenedese G，Bertinato Ortolan M.Low-density wireless sensor networks for localization and tracking in critical environments[J].IEEE Transactions on Vehicular Technology,2010,59(6):2951-2962.

[6] NIculescu D,Nath B.Ad-hoc positioning system[A].Global Telecommunications Conference(GlobeCom),IEEE[C],2001:2926-2931.

[7] Hui Qu,Wicker Stephen B.Co-designed anchor-free localization and location-based routing algorithm for rapidly-deployed wireless sensor networks[J].Information Fusion,2007(9):425-439.

[8] Zhang S G,Cao J N,Chen L J,et al.Accurate and energy efficient range-free localization for mobile sensor networks[J].IEEE Transactions on Mobile Computing,2010,9(6):897-910.

[9] Hongyang C,SeZaki K.An improved DV-Hop localization algorithm for wireless sensor networks[A].IEEE International Conference on Industrial Electronics and Application[C],2008:1557-1561.

[10]劉鋒,張翰,楊驥.一種基于加權處理的無線傳感器網(wǎng)絡平均跳距離估計算法[J].電子與信息學報,2008,30(5):1221-1224.

[11]Ahn H,Hong J.DV-Hop localization algorithm with multipower beacons under noisy environment[J].IEEE,2011(3):7-12.

An Improved Algorithm Based on DV-Hop Localization in Wireless Sensor Networks

CHEN Jing-jie,LUO Ming

(Xidian University,Xi'an 710071,China)

Aiming at the defect of low localization accuracy in classical localization algorithm DV-Hop in wireless sensor networks,an improved algorithm is proposed in this paper.Based on the traditional DV-Hop algorithm,this paper first adopts the minimum mean square error calibration to revise average per jump distance of beacon nodes,then performs weight to the average per jump distance from each unknown node to the reference beacon node;finally modifies the positions of unknown nodes through parameter analysis.The simulation experiment results show that the improved algorithm has high location accuracy and needs no added hardware facility compared with the traditional DV-Hop localization algorithm and previous improved algorithms,so the algorithm has good practicability in the engineering.

wireless sensor network;node localization;DV-Hop algorithm;minimum mean square error

2014-08-02

TN914

A

CN32-1413(2015)01-0070-05

10.16426/j.cnki.jcdzdk.2015.01.017