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

曹廣華 張紅杰

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

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

1.1 DV-Hop算法

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

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

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

(1)

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

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

d=hopsizei×N

(2)

其中，N為未知節點與信標節點的最小跳數。

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

1.2 DV-Hop算法誤差分析

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

2 DV-Hop改進算法

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

2.1 跳距誤差修正方法

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

(3)

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

(4)

經過跳距誤差修正后最終信標節點i的平均每跳距離hopi為：

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

(5)

根據文獻[6]可知，變量參數k取0.7最佳。最后信標節點將新的校正值hopi廣播到網絡中。

2.2 最佳信標節點選擇算法

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

圖1 信標節點位置分布

(6)

圖2 信標節點選擇

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

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

3 改進算法的仿真和分析

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

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

(7)

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

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

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

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

a. 節點總數為100

b. 節點總數為200

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

a. 節點總數為100

b. 節點總數為200

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

4 結束語

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

[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] 任豐原,黃海寧,林闖.無線傳感器網絡[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] 王福豹,史龍,任豐原.無線傳感器網絡中的自身定位系統和算法[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] 李輝,熊盛武,劉毅,等.無線傳感器網絡DV-Hop定位算法的改進[J].傳感技術學報,2011,24(12):1782～1786.

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

[8] 劉少強,龐新苗,樊曉平,等.一種有效提高節點定位精度的改進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.