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

陳晶杰，羅 明

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

?

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

陳晶杰，羅 明

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

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

無線傳感器網絡；節點定位；DV-Hop算法；最小均方誤差

0 引 言

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

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

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

1 DV-Hop節點定位算法

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

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

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

(1)

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

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

dik=Savi×hik

(2)

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

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

(3)

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

(4)

(5)

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

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

(6)

2 DV-Hop節點定位算法的改進

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

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

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

(7)

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

(8)

(9)

2.2 對未知節點到各個信標節點的平均每跳距離進行統一的加權處理

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

(10)

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

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

(11)

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

dki=Savk×hki

(12)

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

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

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

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

(13)

在公式(13)中，用離未知節點p最近的那項信標節點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)求得的未知節點具有很好的定位精度，可以使用公式(17)中求出的s(s=x2+y2)對得到的未知節點進行更新，以提高定位精度。

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

圖1 未知節點的估算坐標

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

(18)

(19)

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

(20)

3 算法仿真

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

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

(21)

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

3.1 信標節點比率與定位誤差的關系

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

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

3.2 網絡節點總個數與定位誤差的關系

圖3 網絡節點總個數與定位誤差的關系

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

3.3 節點的通信距離與定位誤差的關系

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

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

4 結束語

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

[1] 崔莉,鞠海玲,苗勇.無線傳感器網絡研究進展[J].計算機研究與發展,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]劉鋒,張翰,楊驥.一種基于加權處理的無線傳感器網絡平均跳距離估計算法[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