基于跳距修正的DV-Hop改進(jìn)定位算法研究

李琳芳,崔微微,趙欣

（河南科技學(xué)院,河南新鄉(xiāng)453003）

基于跳距修正的DV-Hop改進(jìn)定位算法研究

李琳芳,崔微微,趙欣

（河南科技學(xué)院,河南新鄉(xiāng)453003）

針對DV-Hop（Distance Vector-Hop）定位算法在估算跳距時存在較大誤差的情況,分析了跳距影響因子,提出了一種跳距修正算法.該算法通過對每跳的平均距離以及跳數(shù)進(jìn)行加權(quán)處理減少跳距誤差.仿真結(jié)果表明,在相同網(wǎng)絡(luò)環(huán)境下,改進(jìn)后的DV-Hop算法在不增加硬件開銷的基礎(chǔ)上提高了定位精度.

無線傳感器網(wǎng)絡(luò)；節(jié)點定位；定位算法；DV-Hop

無線傳感器網(wǎng)絡(luò)（WSN）是將大量傳感器節(jié)點部署在某一區(qū)域,借助傳感器節(jié)點進(jìn)行信息獲取、傳輸以監(jiān)測目標(biāo)區(qū)域[1].無線傳感器網(wǎng)絡(luò)中監(jiān)測及其他許多服務(wù)都是基于位置信息的,因此獲悉傳感器節(jié)點位置顯得尤為重要[2].傳感器節(jié)點因應(yīng)用環(huán)境的特殊性,事先將所有節(jié)點布置在感知區(qū)域不太現(xiàn)實,受成本、能耗等問題的限制,為每個傳感器節(jié)點安裝GPS定位模塊或其他外部設(shè)施也不實際[3],必須采用其他方法實現(xiàn)傳感器節(jié)點定位.

無線傳感器網(wǎng)絡(luò)節(jié)點定位技術(shù)大體分為基于測距的和無需測距的兩類.基于測距的定位技術(shù)以已知方位的信標(biāo)節(jié)點作為參考坐標(biāo)點,通過幾何測距計算節(jié)點的位置[4],目前主要包括TOA,TDOA,AOA、RSSI等算法[5].基于非測距的定位技術(shù)一般是根據(jù)網(wǎng)絡(luò)本身的聯(lián)通性、路由及拓?fù)浣Y(jié)構(gòu)等信息來估計節(jié)點位置,目前主要包括APIT算法、質(zhì)心法、DV-Hop算法等[6].

基于測距的定位算法優(yōu)勢在于定位精度高、效果好,但需對節(jié)點配置硬件裝置,定位過程中能耗較大,受環(huán)境的影響較大；基于非測距的定位算法則因低成本優(yōu)勢受人推崇,由于對硬件要求低,使得它更適合大規(guī)模網(wǎng)絡(luò),而且受環(huán)境的影響較小,雖然定位精度相對較低,但能滿足大多數(shù)的傳感器應(yīng)用要求[7]. DV-Hop是一種典型的非測距定位算法,是很多定位算法的思想依據(jù).本文在闡述DV-Hop算法原理及分析DV-Hop算法誤差基礎(chǔ)上,提出了一種改進(jìn)算法,從平均跳距與跳數(shù)兩方面做加權(quán)修正處理.

1 DV-Hop定位算法

1.1 DV-Hop定位原理

DV-Hop算法大體分以下三個步驟[8]：

（1）記錄信標(biāo)節(jié)點到未知節(jié)點的最小跳數(shù)

信標(biāo)節(jié)點通過廣播方式向鄰居節(jié)點發(fā)送包含跳數(shù)的信息元組,鄰居節(jié)點自動記錄下該信標(biāo)節(jié)點的最小跳數(shù)信息,然后把跳數(shù)加1后發(fā)送給鄰居節(jié)點,這個階段后,未知節(jié)點記錄了與每個信標(biāo)節(jié)點的最小跳數(shù).

（2）計算未知節(jié)點與信標(biāo)節(jié)點的距離

首先,經(jīng)過第一步,信標(biāo)節(jié)點可獲得與其他信標(biāo)節(jié)點的距離與最小跳數(shù)信息,根據(jù)公式（1）估算每跳平均距離

式（1）中（xi,yi）,（xj,yj）分別為信標(biāo)節(jié)點i、j的坐標(biāo),hj為信標(biāo)節(jié)點i與j之間的最小跳數(shù).

然后,信標(biāo)節(jié)點以廣播方式將每跳平均距離告知網(wǎng)絡(luò)中的未知節(jié)點,未知節(jié)點以收到的第一個每跳平均距離為參考值,這樣確保未知節(jié)點從最近的信標(biāo)節(jié)點獲取每跳平均距離.

最后,根據(jù)之前記錄的跳段數(shù)信息,用每跳平均距離乘以跳數(shù),估算未知節(jié)點到每個信標(biāo)節(jié)點的距離.

（3）計算未知節(jié)點坐標(biāo)

當(dāng)未知節(jié)點估算出與多個信標(biāo)節(jié)點的距離后,利用三邊測量法或極大似然估計法計算其坐標(biāo).

1.2 DV-Hop算法誤差分析

DV-Hop算法的核心思想是用每跳平均距離乘以跳數(shù)來估計兩個節(jié)點間的距離,用估計距離代替兩個節(jié)點間實際直線距離是DV-Hop算法一個主要的誤差來源.

DV-Hop算法誤差分析示意圖如圖1所示.

圖1 DV-Hop算法誤差分析示意Fig.1 DV-Hop algorithm error analysis schematic

圖1中L1、L2、L3為已知的信標(biāo)節(jié)點,M為未知節(jié)點,傳感器節(jié)點受通信半徑的限制,不是所有節(jié)點都可以直接通信.圖1中實線代表節(jié)點間可直接通信,虛線代表節(jié)點間不能直接通信,需要借助中間節(jié)點的跳轉(zhuǎn)實現(xiàn)通信.

根據(jù)DV-Hop算法,由公式（1）可求得L1每跳平均距離

節(jié)點M與信標(biāo)節(jié)點L1跳數(shù)最小,所以M的每跳平均距離為15,M與L1之間跳數(shù)為1,估算M與L1跳距為15×1=15,在圖1中可知節(jié)點M與信標(biāo)節(jié)點L1的實際距離為30.由此可知,估算的跳距與節(jié)點間實際距離是存在誤差的,所以盡可能的使得估算的跳距與實際距離接近便可提高定位精度.

2 DV-Hop改進(jìn)算法

基于對DV-Hop算法誤差分析,節(jié)點定位誤差主要由節(jié)點間估計距離引起,而估計距離受每跳平均距離和跳數(shù)影響,下面針對這兩方面對DV-Hop算法進(jìn)行改進(jìn).

2.1 每跳平均距離修正

針對DV-Hop算法中對每跳平均距離的簡單取值進(jìn)行修正,對每跳平均距離作歸一化處理,為每跳平均距離求得一個加權(quán)系數(shù),用加權(quán)后的每跳平均距離代替原始每跳平均距離.

改進(jìn)算法的每跳平均距離計算步驟如下：

步驟1：根據(jù)公式（1）求得每個信標(biāo)節(jié)點的每跳平均距離HopSizei.

步驟2：假設(shè)網(wǎng)絡(luò)中有n個信標(biāo)節(jié)點,且未知節(jié)點能收到這n個信標(biāo)節(jié)點的信息.根據(jù)公式（2）求得網(wǎng)絡(luò)中信標(biāo)節(jié)點的每跳平均距離的平均值HopSizeAVG

步驟3：對于n個信標(biāo)節(jié)點,HopSizei與HopSizeAVG相差較小的話賦予一個較大的權(quán)值,反之則賦予一個較小的權(quán)值.根據(jù)公式（3）求得權(quán)重因子δi,根據(jù)公式（4）對δi作歸一化處理得到加權(quán)系數(shù)Ci

步驟4：根據(jù)公式（5）求得修正后的每跳平均距離HopSize

2.2 跳數(shù)修正

在DV-Hop算法中,用每跳平均距離與跳數(shù)乘積代替節(jié)點間的直線距離是存在誤差的,跳數(shù)越多,累積誤差也越大.針對這一問題,可以對不同范圍內(nèi)的跳數(shù)賦予不同的權(quán)重,以改善跳數(shù)過多造成的累積誤差過大的現(xiàn)象,使得跳段距離與直線盡可能的擬合.權(quán)重賦予原則是跳數(shù)越少,權(quán)重越大；跳數(shù)越多,權(quán)重越小[9].通過反復(fù)試驗構(gòu)建如公式（6）所示的模型

式（6）中w是權(quán)重,hop是跳數(shù),max不表示具體數(shù)值,代表極大值,在DV-Hop算法步驟（1）（2）中,涉及到跳數(shù)hop的,根據(jù)公式（6）進(jìn)行加權(quán)處理,用w×hop代替hop值.

3 仿真及分析

3.1 仿真環(huán)境配置

將DV-Hop算法與改進(jìn)算法在MATLAB平臺上進(jìn)行仿真分析以檢驗改進(jìn)算法的性能.

在100 m×100 m在正方形區(qū)域內(nèi),隨機(jī)分布200個節(jié)點,其中10個信標(biāo)節(jié)點,190個未知節(jié)點,節(jié)點通信半徑R=40 m.節(jié)點隨機(jī)分布圖如圖2所示,*代表未知節(jié)點,o代表信標(biāo)節(jié)點.

圖2 節(jié)點隨機(jī)分布圖Fig.2 Node random distribution

3.2 實驗及結(jié)果分析

考慮到節(jié)點定位誤差受信標(biāo)節(jié)點數(shù)量的影響,為更全面地檢驗改進(jìn)算法的性能,分別進(jìn)行了節(jié)點數(shù)量固定不變與節(jié)點數(shù)量變動兩種情況下的實驗研究.

3.2.1 信標(biāo)節(jié)點數(shù)量固定不變在信標(biāo)節(jié)點數(shù)量保持不變的情況下,節(jié)點位置誤差如圖3所示.圖a為DV-Hop算法定位未知節(jié)點的位置誤差,圖3-b為改進(jìn)算法定位未知節(jié)點的位置誤差,橫軸為未知節(jié)點,縱軸為誤差距離.

圖3 節(jié)點位置誤差Fig.3 Node position error

根據(jù)圖3-a與b仿真曲線可知,改進(jìn)算法單個未知節(jié)點定位誤差距離整體比傳統(tǒng)DV-Hop算法小.定義平均定位誤差為

式（7）中eAVG代表平均定位誤差,ej表示單個未知節(jié)點的誤差,n表示未知節(jié)點數(shù)量.根據(jù)公式（7）利用MATLAB仿真求得在上述實驗環(huán)境配置下,傳統(tǒng)DV-Hop算法的平均定位誤差為34.150 4 m,改進(jìn)算法的平均定位誤差為24.495 4 m,改進(jìn)算法平均定位誤差距離比傳統(tǒng)DV-Hop算法小.

3.2.2 信標(biāo)節(jié)點數(shù)量變動網(wǎng)絡(luò)中信標(biāo)節(jié)點比例與定位誤差關(guān)系如圖4所示.橫坐標(biāo)為信標(biāo)節(jié)點在總節(jié)點中所占比例,縱坐標(biāo)為誤差精度.實線表征的是傳統(tǒng)DV-Hop算法定位誤差與信標(biāo)節(jié)點的比例關(guān)系,虛線表征的是改進(jìn)算法定位誤差與信標(biāo)節(jié)點的比例關(guān)系.

圖4 信標(biāo)節(jié)點比例與定位誤差關(guān)系Fig.4 Relationship between the ratio of beacon nods and location error

定義誤差精度為

式（8）中eAVG為平均定位誤差,根據(jù)公式（7）可求得,R為通信半徑,仿真環(huán)境配置R=40 m.

根據(jù)圖4仿真曲線可知,DV-Hop算法與改進(jìn)算法的定位誤差隨網(wǎng)絡(luò)中信標(biāo)節(jié)點比例的增加都在減小,定位精度都有所提高,而改進(jìn)算法的定位精度要始終優(yōu)于DV-Hop算法.

4 小結(jié)

針對DV-Hop算法中跳段距離代替節(jié)點間實際直線距離誤差過大問題,提出了一種改進(jìn)算法,從平均每跳距離和跳數(shù)兩方面進(jìn)行加權(quán)修正.通過配置仿真環(huán)境,以MATLAB為平臺,對DV-Hop算法和改進(jìn)算法進(jìn)行實驗分析.實驗結(jié)果表明,與傳統(tǒng)DV-Hop算法相比,在不需要增加額外硬件設(shè)施的情況下,改進(jìn)算法極大地減少了定位誤差,改善了定位效果,是一種可行算法.當(dāng)然在網(wǎng)絡(luò)節(jié)點數(shù)量多的時候,改進(jìn)算法計算量較大,仿真時間較長,在這點上,改進(jìn)算法還有改進(jìn)的空間.

[1]胡淼,陶正蘇.一種基于可移動錨節(jié)點的DV-HOP改進(jìn)定位算法[J].電子設(shè)計工程,2011,19（24）：98-100.

[2]張宏君,毛永毅.改進(jìn)的無線傳感器網(wǎng)絡(luò)節(jié)點定位算法[J].計算機(jī)應(yīng)用,2012,32（8）：2103-2105.

[3]李成岳.基于DV-Hop的無線傳感器網(wǎng)絡(luò)節(jié)點定位算法研究[D].吉林：吉林大學(xué),2011.

[4]曾星,宋萍.一種基于航跡推算與接收信號強(qiáng)度指示相結(jié)合的移動傳感器網(wǎng)絡(luò)節(jié)點定位方法[J].科學(xué)技術(shù)與工程, 2014,14（4）：245-249.

[5]Niculescu D,Nath B.Ad hoc positioning system（APS）using AOA[J].INFOCOM,Twenty-second Annual Joint Conference of the IEEE Computer and Communications,San Francisco,CA,2003：1734-1743.

[6]劉毓,馬曉輝,曹津銘.基于WSN特點對DV-HOP算法改進(jìn)的研究[J].西安郵電學(xué)院學(xué)報,2012,17（6）：24-26,55.

[7]柳小康.DV-Hop定位算法的定位精度優(yōu)化算法[D].大連：大連理工大學(xué),2013.

[8]蔣馥珍,王峰,王康,等.基于加權(quán)的DV-Hop在WSN中的應(yīng)用于研究[J].電視技術(shù),2013,37（19）：181-183.

[9]肖麗萍,劉曉紅.一種基于跳數(shù)修正的DV-Hop定位算法[J].傳感技術(shù)學(xué)報,2012,23（12）：1726-1728.

（責(zé)任編輯：盧奇）

Research on DV-Hop improved algorithm based on hop-distance correction

LI Linfang,CUI Weiwei,ZHAO Xin
（Henan Institute of Science and Technology,Xinxiang 453003,China）

Because of a big error in estimating hop-distance for DV-Hop localization algorithm,a new algorithm was proposed after analyzing the influence factors of hop-distance.In the new algorithm,the average distance of each hop and hop count were weighted to reduce the hop-distance error.The simulation results showed that under the same network environment,the improved algorithm could improve the positioning accuracy without increasing the hardware cost.

wireless sensor network;node localization;localization algorithm;DV-Hop

TN929.5；TP212.9

A

1008-7516（2016）01-0051-06

10.3969/j.issn.1008-7516.2016.01.012

2016-01-12

河南省教育廳科學(xué)技術(shù)研究重點項目(14B120009)

李琳芳(1988―),女,河南新鄉(xiāng)人,碩士,助教.主要從事信號與信息處理研究.