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

邴曉瑛，徐保國(guó)

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

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

邴曉瑛1，徐保國(guó)2

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

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

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

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

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

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

1　問(wèn)題分析

1.1DV-Hop定位算法

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

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

1.2誤差分析

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

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

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

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

2.1基本思想

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

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

2.2具體步驟

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

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

具體步驟如下：

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

2）若i

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

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

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

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

圖2　改進(jìn)DV-Hop算法流程圖Fig.2　Improved DV-Hop algorithm flow chart

3　仿真實(shí)驗(yàn)及結(jié)果分析

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

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

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

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

3.2仿真結(jié)果分析

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

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

3.2.2通信半徑對(duì)定位精度的影響

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

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

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

4　結(jié)　論

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

[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é)報(bào)，2014，44（2）:502-507.

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

[6]祝宇鴻，歷彥愷，胡俊.基于跳數(shù)閾值和節(jié)點(diǎn)分類的DV-Hop算法[J].吉林大學(xué)學(xué)報(bào)：信息科學(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]賈曉強(qiáng).一種基于C/S模式的中間件SDO的P2P平臺(tái)的網(wǎng)絡(luò)拓?fù)湓O(shè)計(jì)[J].電子設(shè)計(jì)工程，2014（13）:31-33.

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

[10]陳茜.流程改進(jìn)提升檢測(cè)實(shí)驗(yàn)室管理水平[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稿件編號(hào)：201503105

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

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