陳晶杰，羅 明

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

?

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

陳晶杰，羅 明

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

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

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

0 引 言

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

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

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

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

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

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

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

(1)

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

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

dik=Savi×hik

(2)

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

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

(3)

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

(4)

(5)

利用標(biāo)準(zhǔn)最小二乘法可得未知節(jié)點估計坐標(biāo)：

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

(6)

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

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

2.1 基于最小均方誤差準(zhǔn)則求得平均每跳距離

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

(7)

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

(8)

(9)

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

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

(10)

式中：λi為未知節(jié)點到第i個信標(biāo)節(jié)點所對應(yīng)的權(quán)值;hi為未知節(jié)點到第i個信標(biāo)節(jié)點的跳數(shù)。

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

(11)

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

dki=Savk×hki

(12)

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

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

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

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

(13)

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

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

(14)

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

(15)

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

GZ=D

(16)

利用標(biāo)準(zhǔn)最小二乘法對方程GZ=D進(jìn)行求解得：

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

(17)

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

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

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

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

(18)

(19)

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

(20)

3 算法仿真

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

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

(21)

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

3.1 信標(biāo)節(jié)點比率與定位誤差的關(guān)系

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

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

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

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

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

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

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

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

4 結(jié)束語

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

[1] 崔莉,鞠海玲,苗勇.無線傳感器網(wǎng)絡(luò)研究進(jìn)展[J].計算機(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]劉鋒,張翰,楊驥.一種基于加權(quán)處理的無線傳感器網(wǎng)絡(luò)平均跳距離估計算法[J].電子與信息學(xué)報,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