李琳芳,崔微微,趙欣

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

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

李琳芳,崔微微,趙欣

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

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

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

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

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

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

1 DV-Hop定位算法

1.1 DV-Hop定位原理

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

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

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

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

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

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

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

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

（3）計(jì)算未知節(jié)點(diǎn)坐標(biāo)

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

1.2 DV-Hop算法誤差分析

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

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

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

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

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

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

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

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

2.1 每跳平均距離修正

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

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

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

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

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

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

2.2 跳數(shù)修正

在DV-Hop算法中,用每跳平均距離與跳數(shù)乘積代替節(jié)點(diǎn)間的直線距離是存在誤差的,跳數(shù)越多,累積誤差也越大.針對(duì)這一問(wèn)題,可以對(duì)不同范圍內(nèi)的跳數(shù)賦予不同的權(quán)重,以改善跳數(shù)過(guò)多造成的累積誤差過(guò)大的現(xiàn)象,使得跳段距離與直線盡可能的擬合.權(quán)重賦予原則是跳數(shù)越少,權(quán)重越大；跳數(shù)越多,權(quán)重越小[9].通過(guò)反復(fù)試驗(yàn)構(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平臺(tái)上進(jìn)行仿真分析以檢驗(yàn)改進(jìn)算法的性能.

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

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

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

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

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

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

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

式（7）中eAVG代表平均定位誤差,ej表示單個(gè)未知節(jié)點(diǎn)的誤差,n表示未知節(jié)點(diǎn)數(shù)量.根據(jù)公式（7）利用MATLAB仿真求得在上述實(shí)驗(yàn)環(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é)點(diǎn)數(shù)量變動(dòng)網(wǎng)絡(luò)中信標(biāo)節(jié)點(diǎn)比例與定位誤差關(guān)系如圖4所示.橫坐標(biāo)為信標(biāo)節(jié)點(diǎn)在總節(jié)點(diǎn)中所占比例,縱坐標(biāo)為誤差精度.實(shí)線表征的是傳統(tǒng)DV-Hop算法定位誤差與信標(biāo)節(jié)點(diǎn)的比例關(guān)系,虛線表征的是改進(jìn)算法定位誤差與信標(biāo)節(jié)點(diǎn)的比例關(guān)系.

圖4 信標(biāo)節(jié)點(diǎn)比例與定位誤差關(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é)點(diǎn)比例的增加都在減小,定位精度都有所提高,而改進(jìn)算法的定位精度要始終優(yōu)于DV-Hop算法.

4 小結(jié)

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

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

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

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

[4]曾星,宋萍.一種基于航跡推算與接收信號(hào)強(qiáng)度指示相結(jié)合的移動(dòng)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位方法[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特點(diǎn)對(duì)DV-HOP算法改進(jìn)的研究[J].西安郵電學(xué)院學(xué)報(bào),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é)報(bào),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ù)研究重點(diǎn)項(xiàng)目(14B120009)

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