無線傳感網中DV-Hop定位算法的改進研究

邴曉瑛，徐保國

（1.江南大學輕工過程先進控制教育部重點實驗室，江蘇 無錫　214122；2.江南大學物聯網工程學院，江蘇 無錫　214122）

無線傳感網中DV-Hop定位算法的改進研究

邴曉瑛1，徐保國2

（1.江南大學輕工過程先進控制教育部重點實驗室，江蘇 無錫214122；2.江南大學物聯網工程學院，江蘇 無錫214122）

針對網絡拓撲結構不規則的無線傳感器網絡中經典DV-Hop定位算法計算未知節點位置存在較大誤差的問題，提出了一種基于多通信半徑修正跳數的改進算法。通過對通信半徑進行分級細化，利用多級通信半徑修正信標節點到信鄰節點的跳數信息，使未知節點的平均跳距更符合實際網絡情況。仿真結果表明，在相同的網絡拓撲結構下，改進的定位算法有效的提高了傳感器節點的定位精度。

無線傳感器網絡；DV-Hop定位；多通信半徑；定位精度

無線傳感器網絡（Wireless Sensor Network，WSN）現已廣泛應用于很多領域，而傳感器節點的位置特別重要，是WSN應用的基礎。現階段定位算法主要分為兩類，基于測距（Range-based）的定位算法和基于非測距（Range-free）[1]的定位算法。其中DV-Hop[2]算法是典型的基于非測距的定位算法，該算法硬件成本較低、能耗較小，傳輸的信號受外界影響較小，并且能滿足大部分實際應用對定位精度要求。

美國Rutgers University的Dragos Niculescu等利用GPS和距離矢量路由思想提出了DV-Hop算法[3]，定位精度較低。隨著社會的發展需要，對許多應用的定位精度要求愈來愈高。許多學者對經典的DV-Hop算法進行了深入研究并改進，文獻[4]采用雙通信半徑細化節點間的跳數信息，提高定位精度；文獻[5]利用RSSI修正節點間的跳數信息，使跳數值更精確；文獻[6]利用設定跳數閾值選擇適當的信標節點估計平均每跳距離，未知節點一句跳數對信標節點分類，并加權修正距離，提高定位精度。

文中深入地分析了傳統DV-Hop定位算法定位誤差大的原因，在不改變傳統算法框架的基礎上，利用多通信半徑來修正傳統算法第一階段得到的未知節點與信標節點間的最小跳數，使未知節點與信標節點間的距離更接近真實值。實驗結果表明，改進的算法能有效的減小定位誤差，提高定位精度。

1　問題分析

1.1DV-Hop定位算法

根據DV-Hop定位算法第一、二階段得到的未知節點D （x，y）與信標節點（x1，y1），（x2，y2），…，（xn，yn）最小跳數與平均每跳距離[7]，求得相應節點間距離為d1，d2，…dn，則

可表示為線性方程組AL+ε=b，ε為n-1維隨機誤差向量，其中L=（x，y）T，則最小二乘法求得方程的解為L=（ATA）-1ATb。

1.2誤差分析

在經典DV-Hop定位算法中，利用到未知節點最近的信標節點的估算平均跳距與最小跳數乘積等效替代其直線距離，精確度受網絡連通度影響較大。經過深入分析，最小跳數信息是造成誤差原因之一。

DV-Hop定位算法中，選擇具有最少折點的幾個跳段等效為未知節點與信標節點之間的直線段，那么該折線段中各點越接近共線，誤差越小。由于網絡中節點隨機分布，共線概率較低，誤差必然存在。未知節點與信標節點間的跳數越多，與其相關的測量dn距離誤差越大，式（3）中向量b的每個元素均包含測量距離dn，導致誤差累加。

針對上述DV-Hop定位誤差的產生的原因，本文對如何精確未知節點與信標節點間的最小跳數作出相應的改進研究。

2　多通信半徑改進跳數信息

2.1基本思想

在DV-Hop定位算法中，兩點之間的直線距離小于通信半徑，即將其記為1跳。若網絡中節點分布如圖1所示，設通信半徑R=30 m，從圖中可以看出，信標節點O可以與節點A、B、C進行通信，那么HopOA=1，HoOB=1，HopOC=1，但是OA與OC的距離相差較大，OD間跳數記為2跳時，對計算信標節點O平均跳距影響比較大。在計算未知節點與信標節點最小距離時，這種計算節點間最小跳數的機制也會導致誤差的產生，并在定位過程中繼續累加誤差。若能將信標節點到信鄰節點間的跳數分級細化，必然能減小誤差，提高定位精度。文中提出了一種利用多通信半徑來精確信標節點與信鄰節點間的跳數，減小定位誤差。

圖1　多通信半徑跳數計算Fig.1　More communication radius calculation

2.2具體步驟

設網絡通信半徑為R，將信標節點與信鄰節點間分為m級，網絡中各信標節點與其鄰居節點的實際距離為d，跳數記為H1，i∈[1，m]且為正整數，則

根據式（4），若取R=30m，m=3，則圖1中的OA、OB、OC、 OD跳數值為信標節點與信鄰節點的跳數值不再是整數，是更加精確的小數，與距離更接近正比關系，有效的提高了數據的精確性，減小定位誤差。

具體步驟如下：

1）設定m，R值，首先取i=1；

2）若i

4）間隔時間t，令i=i+1，轉向步驟2）；

5）信標節點以通信半徑R在網絡中廣播自身信息分組，接收節點每接收到一個分組信息，判斷是否為記錄的最小跳數值。若是，保存該信標節點的最小跳數并將hop=hop+1轉發給鄰居節點；若不是，將原來已保存的最小跳數值加1轉發給鄰居節點。若該分組來自同一信標節點，則忽略。

2.3改進DV-Hop具體實現步驟

基于多通信半徑改進DV-Hop定位算法流程圖如圖2。

圖2　改進DV-Hop算法流程圖Fig.2　Improved DV-Hop algorithm flow chart

3　仿真實驗及結果分析

3.1仿真環境及參數設定

本文采用MATLAB仿真軟件實現傳感器節點定位算法。假設所有傳感器節點均勻隨機分布在100 m×100 m的正方形區域內。

為了能更直觀的評價基于多通信半徑改進DV-Hop算法的性能，將其通信半徑等級分為m=1，2，3，4，5級進行對比仿真實驗，并比較分析實驗數據。為確保結果的準確性，在每種測試條件下，算法分別進行50次隨機分布測試，取算術平均值。定位算法性能評價標準為歸一化定位誤差，其計算公式為：

其中，（xir，yir），（xie，yie）代表第 i個未知節點的實際坐標和通過定位算法得出的估計坐標，R為網絡通信半徑，N為未知節點總數。

3.2仿真結果分析

3.2.1信標節點比例對定位精度的影響

圖3表示了節點總數N=100，通信半徑R=30 m，信標節點比例在5%～35%變化時，通信半徑分級m不同時節點定位誤差圖。由圖可知，m=1，2，3，4，5時定位誤差與信標節點比例整體上成反比。在信標節點比例為5%～15%時，定位誤差受信標節點比例影響較大，當信標節點比例超過15%后，定位誤差變化均趨于穩定。由圖可知，m=1，2，3時定位誤差減小效果較明顯，m=4，5時定位誤差減小的較少，m=2較m=1 即DV-Hop定位算法定位誤差平均減小了約17%；m=3較m=2定位算法定位誤差平均減小了約12%；m=4較m=3定位算法定位誤差平均減小了約8%；m=5較m=4定位算法定位誤差平均減小了約5%。

圖3　信標節點比例不同時的定位誤差Fig.3　Localization error with different Beacon node ratio

3.2.2通信半徑對定位精度的影響

圖4表示了節點總數N=100，信標節點數為30，通信半徑在22～50 m變化時，通信半徑分級m不同時節點定位誤差圖。由圖可知，m=1，2，3，4，5時定位誤差與通信半徑變化整體上成反比。這是由于通信半徑越大，每個節點的鄰居節點越多，網絡連通度越高，節點的平均跳距和跳數信息越準確。由圖可知，m=1，2，3時定位誤差減小效果較明顯，m=4，5時定位誤差減小的較少。m=2較m=1即DV-Hop定位算法定位誤差平均減小了約15%；m=3較m=2定位算法定位誤差平均減小了約10%；m=4較m=3定位算法定位誤差平均減小了約6%；m=5較m=4定位算法定位誤差平均減小了約4%。

圖4　通信半徑不同時的定位誤差Fig.4　Localization error with different communication radius

根據圖3、圖4，通信半徑分為級時節點定位誤差較經典DV-Hop減小的較明顯，由于信標節點每廣播一次自身信息分組，都要有一定的能量消耗，綜合考慮，選擇通信半徑分為3級，細化精確節點間的跳數信息較合理。

4　結　論

文中提出了一種基于多通信半徑分級細化節點間跳數的改進DV-Hop定位算法。通過多通信半徑精確節點間跳數信息，使求得的未知節點坐標更接近實際坐標，提高定位精度。仿真實驗結果表明，文中改進[9-10]算法在相同的網絡拓撲[8]結構下，有效的提高了傳感器節點的定位精度。如何更有效的節約網絡能量開銷，也是未來的一個研究方向。

[1]Maung，N.A.M.，Kawai，M.Experimental Evaluations of RSS threshold-based optimized DV-Hop localization for wireless ad-hoc networks[J].2014，50（17）:1246-1248.

[2]Gayan，S.，Dias，D.Improved DV-Hop algorithm through anchor poition re-estimation[C].Wireless and Mobile，2014 IEEE Asia Pacific Conference on.2014:126-131.

[3]NICULESCU D，NATH B.DV Based Positioning in Ad Hoc Networks[C].Telecommunication Systems，2003:22（1/2/3/ 4）:267-280.

[4]李娟，劉禹，錢志鴻.基于雙通信半徑的傳感器網絡DVHop定位算法[J].吉林大學學報，2014，44（2）:502-507.

[5]溫江濤，范學敏，吳希軍.基于RSSI跳數修正的DV-Hop改進算法[J].傳感技術學報.2014，27（1）:113-117.

[6]祝宇鴻，歷彥愷，胡俊.基于跳數閾值和節點分類的DV-Hop算法[J].吉林大學學報：信息科學版，2014，32（4）:407-412.

[7]Munsuck Jang，Inseong Song.A study on Localization Algorithm using Hop Count and RSSI[J].International Journal of Control and Automation，2013，6（3）:267-280.

[8]賈曉強.一種基于C/S模式的中間件SDO的P2P平臺的網絡拓撲設計[J].電子設計工程，2014（13）:31-33.

[9]張仁燁，白恩健.降低MIMO-OFDM系統峰均比的改進PTS算法[J].電子科技，2014（12）:1-4.

[10]陳茜.流程改進提升檢測實驗室管理水平[J].質量與標準化，2013（4）:37-40.

Localization method based on modified particle swarm optimization for wireless sensor networks

BING Xiao-ying1，XU Bao-guo2
（1.Key Laboratory of Industrial Advanced Process Control for Light Industry，Ministry of Education，Jiangnan University，Wuxi 214122，China；2.School of Internet of Things Engineering，Jiangnan University，Wuxi 214122，China）

An improved algorithm based on more communication radius and weighting corrected the unknown nodes'hop-size in order to solve the problem that when using the traditional DV-Hop algorithm localization error is too large in irregular topology network.The communication radius is graded，and hops between beacon nodes and neighbor nodes are corrected by more level communication radius，in order to make the hop size of unknown nodes more conform to the actual network.The simulation experimental results showed that，the proposed algorithm possesses of higher location precision in the same network topology，broaden the application scope of localization algorithm.

WSN；DV-Hop localization；more communication radius；location precision

TN92

A

1674－6236（2016）01-0086-03

2015-03-08稿件編號：201503105

國家自然科學基金面上項目（21276111）；國家自然科學基金青年基金（21206053）；浙江省自然科學基金重大專項（2011C12033）

邴曉瑛（1989—），女，山東青島人，碩士。研究方向：無線傳感器定位算法。