陳晶杰，羅 明

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

?

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

陳晶杰，羅 明

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

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

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

0 引 言

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

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

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

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

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

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

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

(1)

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

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

dik=Savi×hik

(2)

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

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

(3)

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

(4)

(5)

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

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

(6)

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

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

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

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

(7)

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

(8)

(9)

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

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

(10)

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

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

(11)

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

dki=Savk×hki

(12)

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

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

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

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

(13)

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

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

(14)

簡(jiǎn)化公式(14)得到n-1項(xiàng)公式：

(15)

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

GZ=D

(16)

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

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

(17)

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

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

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

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

(18)

(19)

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

(20)

3 算法仿真

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

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

(21)

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

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

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

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

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

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

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

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

仿真參數(shù)：在原有網(wǎng)絡(luò)仿真環(huán)境區(qū)域內(nèi)隨機(jī)產(chǎn)生200個(gè)傳感器節(jié)點(diǎn)，并且使得信標(biāo)節(jié)點(diǎn)的個(gè)數(shù)為40。為了研究節(jié)點(diǎn)通信半徑與定位誤差的關(guān)系，使節(jié)點(diǎn)的通信距離依次為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é)點(diǎn)通信距離與定位誤差的關(guān)系

4 結(jié)束語

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

[1] 崔莉,鞠海玲,苗勇.無線傳感器網(wǎng)絡(luò)研究進(jìn)展[J].計(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ì)算法[J].電子與信息學(xué)報(bào),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