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

曹廣華 張紅杰

(東北石油大學電氣信息工程學院，黑龍江 大慶 163318)

無線傳感器網(wǎng)絡(Wireless Sensor Network，WSN)是由大量智能傳感器節(jié)點構(gòu)成的具有信息感知、信息傳送和信息處理能力的綜合型智能信息網(wǎng)絡，具有成本低、自組織和環(huán)境適應性強的特點[1,2]。節(jié)點定位是WSN的關鍵技術之一，目前使用較多的無線傳感器網(wǎng)絡定位方法有基于測距的定位算法和無需測距的定位算法。筆者將對無需測距的DV-Hop定位算法進行分析并對其加以改進。

1.1 DV-Hop算法

根據(jù)節(jié)點是否已知自身的位置，傳感器節(jié)點分為信標節(jié)點和未知節(jié)點。信標節(jié)點在網(wǎng)絡中所占的比例小，可以通過攜帶GPS定位設備等措施獲得自身的精確位置，未知節(jié)點利用信標節(jié)點的位置信息來確定自身位置。DV-Hop算法是一個典型的利用信標節(jié)點間多跳信息來確定未知節(jié)點位置的定位策略，傳統(tǒng)DV-Hop算法可以分為以下3個步驟[3,4]。

首先獲取節(jié)點與每個信標節(jié)點間的最小跳數(shù)。根據(jù)典型的距離矢量路由協(xié)議，每個信標節(jié)點向網(wǎng)絡中廣播自身的位置信息分組，網(wǎng)絡中的全部節(jié)點能夠記錄下到每個信標節(jié)點的最小跳數(shù)。

然后計算信標節(jié)點與未知節(jié)點的距離。每一個信標節(jié)點按照自身列表中記錄的其余信標節(jié)點的位置和最小跳數(shù)信息，計算平均每跳距離hopsizei，計算式為：

(1)

其中hij為信標節(jié)點i和j的最小跳數(shù)；(xi,yi)、(xj,yj)分別為信標節(jié)點i和j的坐標。

未知節(jié)點根據(jù)接收到的平均跳距和記錄到的每個信標節(jié)點的最小跳數(shù)，通過下式計算出與每個信標節(jié)點的距離：

d=hopsizei×N

(2)

其中，N為未知節(jié)點與信標節(jié)點的最小跳數(shù)。

最后利用三邊法或極大似然估計法計算未知節(jié)點的自身位置。

1.2 DV-Hop算法誤差分析

DV-Hop算法是一種非測距方法，實現(xiàn)簡單且能耗適中。在節(jié)點分布均勻的各向同性密集網(wǎng)絡中，節(jié)點的定位精度較高。但在網(wǎng)絡節(jié)點分布不均勻的網(wǎng)絡中，由于節(jié)點的隨機部署，信標節(jié)點相對未知節(jié)點的數(shù)量和位置分布不均勻，致使信標節(jié)點估計的平均每跳距離不能準確地反映全網(wǎng)的平均每跳距離，在使用式(2)時會造成較大的累積誤差，對定位精度有很大程度的影響，所以未知節(jié)點需要選擇合適的信標節(jié)點進行定位才能使定位精度更準確[5]。

2 DV-Hop改進算法

筆者針對平均每跳距離誤差大的問題，使用文獻[6]中提到的跳距誤差修正方法，使計算出的每跳距離盡可能地反映網(wǎng)絡的平均跳距。對于信標節(jié)點分布對定位精度的影響，提出一種基于擬合曲線的未知節(jié)點選擇最佳信標節(jié)點參與定位的方法。

2.1 跳距誤差修正方法

每個信標節(jié)點先根據(jù)傳統(tǒng)DV-Hop算法的第二階段計算出平均每跳距離，將平均跳距廣播至網(wǎng)絡中，廣播數(shù)據(jù)分組信息為{ID，hopsizei}，ID為信標節(jié)點序號，hopsizei為信標節(jié)點i計算的平均跳距，每個節(jié)點接收所有信標節(jié)點的平均跳距并將該跳距信息添加到自己的數(shù)據(jù)列表中，再將信息分組向鄰居節(jié)點廣播，忽略重復的ID信息分組，然后每個節(jié)點將記錄的所有平均跳距相加取平均值，得到全網(wǎng)的平均跳距aver為：

(3)

其中，n為信標節(jié)點的總數(shù)。之后每個信標節(jié)點再根據(jù)下式得到自身平均跳距誤差值ei：

(4)

經(jīng)過跳距誤差修正后最終信標節(jié)點i的平均每跳距離hopi為：

hopi=aver+k×ei，-1≤k≤1

(5)

根據(jù)文獻[6]可知，變量參數(shù)k取0.7最佳。最后信標節(jié)點將新的校正值hopi廣播到網(wǎng)絡中。

2.2 最佳信標節(jié)點選擇算法

在傳統(tǒng)DV-Hop算法中，未知節(jié)點只要獲得與3個或3個以上信標節(jié)點的距離時就可進行定位計算[7]，但由于信標節(jié)點相對于未知節(jié)點的位置分布會對定位精度造成較大的影響，并不是所有信標節(jié)點都參與定位計算定位精度就越高，未知節(jié)點要有選擇地選取最佳的信標節(jié)點參與定位計算，才能使定位結(jié)果更加準確。信標節(jié)點位置分布如圖1所示，黑色圓點表示信標節(jié)點，空心圓點表示未知節(jié)點，實線表示跳段，虛線表示實際距離。未知節(jié)點A用信標節(jié)點B、C進行定位計算，當用跳距乘以跳數(shù)表示AB與AC的距離時，顯然AB的估計距離要比AC的估計距離更接近實際距離，因為未知節(jié)點A到信標節(jié)點B的跳段路徑更接近一條直線?；谝陨戏治觯P者提出一種選擇最佳信標節(jié)點的方法。

圖1 信標節(jié)點位置分布

(6)

圖2 信標節(jié)點選擇

使用多個平均跳距計算距離。在新算法中結(jié)合跳距誤差修正算法，未知節(jié)點接收所有信標節(jié)點的平均跳距，并將該信息記錄在列表中，然后未知節(jié)點使用被選擇出的信標節(jié)點各自的平均跳距乘以跳數(shù)作為未知節(jié)點與被選擇信標節(jié)點的距離。

精確計算未知節(jié)點坐標。未知節(jié)點利用所選擇出來的信標節(jié)點使用極大似然估計法再次精確計算自身坐標。由于未知節(jié)點與所選擇的信標節(jié)點的距離不會偏向于曲折的跳段過程，更接近直線，更能反映真實距離，所以再次計算出的未知節(jié)點坐標會更加準確。

3 改進算法的仿真和分析

為了驗證改進DV-Hop算法在提高節(jié)點定位精度方面的有效性和可行性，使用Matlab進行仿真實驗。仿真實驗的網(wǎng)絡區(qū)域模型參數(shù)為：在100m×100m的區(qū)域進行實驗，節(jié)點通過隨機方式布置，所有節(jié)點的通信半徑都相同，為了取得客觀準確的實驗數(shù)據(jù)，所有數(shù)據(jù)采用100次實驗的平均值[10]。對傳統(tǒng)算法、已有的基于跳距誤差修正的算法和筆者提出的改進算法的定位精度進行比較，分析改進算法的性能。

定位精度C[11]一般用定位誤差值與節(jié)點通信半徑的比值表示，即：

(7)

式中 (xest,yest)——算法計算的節(jié)點坐標；

(xture,yture)——節(jié)點實際坐標。

由式(7)可知，節(jié)點定位精度C值越小表示定位越準確。

圖3描述了在相同網(wǎng)絡環(huán)境下，所有節(jié)點的通信半徑R=20m，節(jié)點總數(shù)分別為100和200時，傳統(tǒng)DV-Hop算法、基于跳距誤差修正的算法與筆者提出的改進算法定位精度隨信標節(jié)點比例的變化情況。可以看出，與傳統(tǒng)算法和基于跳距誤差修正的算法相比，當信標節(jié)點數(shù)較少時，筆者改進算法提高定位精度幅度不大，因為未知節(jié)點可選擇的最佳信標節(jié)點數(shù)較少。但隨著信標節(jié)點比例的增大，由于筆者改進算法充分考慮了信標節(jié)點位置的分布情況并且加入了跳距誤差修正算法，使距離計算更準確，所以更有效地提高了定位精度，穩(wěn)定性也越來越強。當網(wǎng)絡規(guī)模增大時(從100節(jié)點增加到200節(jié)點)，定位精度也明顯提高，如圖3a中當信標節(jié)點比例為15%時，定位精度大約為44%；而圖3b中，信標節(jié)點比例同樣為15%時，定位精度為33%。

a. 節(jié)點總數(shù)為100

b. 節(jié)點總數(shù)為200

圖4描述了在相同網(wǎng)絡環(huán)境下，信標節(jié)點比例為15%、節(jié)點總數(shù)分別為100和200時，傳統(tǒng)DV-Hop算法、基于跳距誤差修正的算法與筆者提出的改進算法定位精度隨節(jié)點通信半徑變化的情況。

a. 節(jié)點總數(shù)為100

b. 節(jié)點總數(shù)為200

可以看出，隨著節(jié)點總數(shù)的增加，3種算法的定位誤差都有所減小，在節(jié)點通信半徑從10變化到40的過程中，筆者提出的改進算法的定位精度均比傳統(tǒng)算法和跳距修正的算法的定位精度高，這是由于改進算法在基于跳距誤差修正的基礎上又充分考慮了信標節(jié)點分布對定位精度的影響，選擇合適的信標節(jié)點參與定位計算，并且使用每個被選擇信標節(jié)點的每跳跳距進行距離計算，使未知節(jié)點與信標節(jié)點的估算距離更好地反映網(wǎng)絡實際節(jié)點間距，定位才更準確。

4 結(jié)束語

筆者在分析現(xiàn)有DV-Hop算法原理和產(chǎn)生誤差原因的基礎上，提出了改進算法，改進的算法考慮了信標節(jié)點位置的分布情況，取最接近直線分布的信標節(jié)點作為計算用的參考節(jié)點，從本質(zhì)上更接近使用跳距定位算法的定位原理，可以提高定位精度。當網(wǎng)絡規(guī)模擴大、信標節(jié)點數(shù)增多時，筆者提出的改進算法的定位精度比傳統(tǒng)算法都有明顯的提高；當信標節(jié)點數(shù)比例不變，網(wǎng)絡規(guī)模擴大時，隨著節(jié)點通信距離的提高，筆者提出的改進算法對定位精度也有較顯著的改善效果。

[1] Akyildiz I F,Su W L,Sankarasubramaniam Y,et al.A Survey on Sensor Networks[J].IEEE Communications Magazine，2002,40(8)：102～114.

[2] 任豐原,黃海寧,林闖.無線傳感器網(wǎng)絡[J].軟件學報,2003,14(7):1282～1291.

[3] Xiao J,Chen H, Zhang S.Research of Range-Based Syner-getic Localization Algorithm in Wireless Sensor Networks[C].2008 Control and Decision Conference.Shandong:IEEE,2008:2040～2044.

[4] 王福豹,史龍,任豐原.無線傳感器網(wǎng)絡中的自身定位系統(tǒng)和算法[J].軟件學報,2005,16(5):857～868.

[5] Mao G Q,Fidan B，Anderson B D O.Wireless Sensor Network Localization Techniques[J].Computer Networks,2007,51(10):2529～2553.

[6] 李輝,熊盛武,劉毅,等.無線傳感器網(wǎng)絡DV-Hop定位算法的改進[J].傳感技術學報,2011,24(12):1782～1786.

[7] 張佳,吳延海,石峰,等.基于DV-Hop的無線傳感器網(wǎng)絡定位算法[J].計算機應用,2010,30(2):323～326.

[8] 劉少強,龐新苗,樊曉平,等.一種有效提高節(jié)點定位精度的改進DV-Hop算法[J].傳感技術學報,2010,23(8):1179～1183.

[9] Niculescu D,Nath B.DV Based Positioning in Ad Hoc Networks[J].Journal of Telecommunication Systems,2003,22(1-4):267～280.

[10] Basagni S,Carosi A,Melachrinoudis E,et al.Protocols and Model for Sink Mobility in Wireless Sensor Networks[J].ACM SIGMO-BILE Mobile Computing and Communications Review,2006,10(4):28～30.

[11] Poggi C,Mazzini G.Collinearity for Sensor Network Localization[C].Proceedings of 2003 IEEE 58th Vehicular Technology Conference.Piscataway,NJ,USA:IEEE,2004:3040～3044.