無線傳感網(wǎng)中DV-Hop定位算法的改進研究

邴曉瑛，徐保國

（1.江南大學(xué)輕工過程先進控制教育部重點實驗室，江蘇 無錫　214122；2.江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院，江蘇 無錫　214122）

無線傳感網(wǎng)中DV-Hop定位算法的改進研究

邴曉瑛1，徐保國2

（1.江南大學(xué)輕工過程先進控制教育部重點實驗室，江蘇 無錫214122；2.江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院，江蘇 無錫214122）

針對網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)不規(guī)則的無線傳感器網(wǎng)絡(luò)中經(jīng)典DV-Hop定位算法計算未知節(jié)點位置存在較大誤差的問題，提出了一種基于多通信半徑修正跳數(shù)的改進算法。通過對通信半徑進行分級細(xì)化，利用多級通信半徑修正信標(biāo)節(jié)點到信鄰節(jié)點的跳數(shù)信息，使未知節(jié)點的平均跳距更符合實際網(wǎng)絡(luò)情況。仿真結(jié)果表明，在相同的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)下，改進的定位算法有效的提高了傳感器節(jié)點的定位精度。

無線傳感器網(wǎng)絡(luò)；DV-Hop定位；多通信半徑；定位精度

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN）現(xiàn)已廣泛應(yīng)用于很多領(lǐng)域，而傳感器節(jié)點的位置特別重要，是WSN應(yīng)用的基礎(chǔ)?，F(xiàn)階段定位算法主要分為兩類，基于測距（Range-based）的定位算法和基于非測距（Range-free）[1]的定位算法。其中DV-Hop[2]算法是典型的基于非測距的定位算法，該算法硬件成本較低、能耗較小，傳輸?shù)男盘柺芡饨缬绊戄^小，并且能滿足大部分實際應(yīng)用對定位精度要求。

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

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

1　問題分析

1.1DV-Hop定位算法

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

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

1.2誤差分析

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

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

針對上述DV-Hop定位誤差的產(chǎn)生的原因，本文對如何精確未知節(jié)點與信標(biāo)節(jié)點間的最小跳數(shù)作出相應(yīng)的改進研究。

2　多通信半徑改進跳數(shù)信息

2.1基本思想

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

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

2.2具體步驟

設(shè)網(wǎng)絡(luò)通信半徑為R，將信標(biāo)節(jié)點與信鄰節(jié)點間分為m級，網(wǎng)絡(luò)中各信標(biāo)節(jié)點與其鄰居節(jié)點的實際距離為d，跳數(shù)記為H1，i∈[1，m]且為正整數(shù)，則

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

具體步驟如下：

1）設(shè)定m，R值，首先取i=1；

2）若i

4）間隔時間t，令i=i+1，轉(zhuǎn)向步驟2）；

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

2.3改進DV-Hop具體實現(xiàn)步驟

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

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

3　仿真實驗及結(jié)果分析

3.1仿真環(huán)境及參數(shù)設(shè)定

本文采用MATLAB仿真軟件實現(xiàn)傳感器節(jié)點定位算法。假設(shè)所有傳感器節(jié)點均勻隨機分布在100 m×100 m的正方形區(qū)域內(nèi)。

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

其中，（xir，yir），（xie，yie）代表第 i個未知節(jié)點的實際坐標(biāo)和通過定位算法得出的估計坐標(biāo)，R為網(wǎng)絡(luò)通信半徑，N為未知節(jié)點總數(shù)。

3.2仿真結(jié)果分析

3.2.1信標(biāo)節(jié)點比例對定位精度的影響

圖3表示了節(jié)點總數(shù)N=100，通信半徑R=30 m，信標(biāo)節(jié)點比例在5%～35%變化時，通信半徑分級m不同時節(jié)點定位誤差圖。由圖可知，m=1，2，3，4，5時定位誤差與信標(biāo)節(jié)點比例整體上成反比。在信標(biāo)節(jié)點比例為5%～15%時，定位誤差受信標(biāo)節(jié)點比例影響較大，當(dāng)信標(biāo)節(jié)點比例超過15%后，定位誤差變化均趨于穩(wěn)定。由圖可知，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　信標(biāo)節(jié)點比例不同時的定位誤差Fig.3　Localization error with different Beacon node ratio

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

圖4表示了節(jié)點總數(shù)N=100，信標(biāo)節(jié)點數(shù)為30，通信半徑在22～50 m變化時，通信半徑分級m不同時節(jié)點定位誤差圖。由圖可知，m=1，2，3，4，5時定位誤差與通信半徑變化整體上成反比。這是由于通信半徑越大，每個節(jié)點的鄰居節(jié)點越多，網(wǎng)絡(luò)連通度越高，節(jié)點的平均跳距和跳數(shù)信息越準(zhǔn)確。由圖可知，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

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

4　結(jié)　論

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

[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]李娟，劉禹，錢志鴻.基于雙通信半徑的傳感器網(wǎng)絡(luò)DVHop定位算法[J].吉林大學(xué)學(xué)報，2014，44（2）:502-507.

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

[6]祝宇鴻，歷彥愷，胡俊.基于跳數(shù)閾值和節(jié)點分類的DV-Hop算法[J].吉林大學(xué)學(xué)報：信息科學(xué)版，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平臺的網(wǎng)絡(luò)拓?fù)湓O(shè)計[J].電子設(shè)計工程，2014（13）:31-33.

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

[10]陳茜.流程改進提升檢測實驗室管理水平[J].質(zhì)量與標(biāo)準(zhǔn)化，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

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

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