魏全瑞,劉俊,韓九強(qiáng)

(西安交通大學(xué)電子與信息工程學(xué)院,710049,西安)

改進(jìn)的無線傳感器網(wǎng)絡(luò)無偏距離估計(jì)與節(jié)點(diǎn)定位算法

魏全瑞,劉俊,韓九強(qiáng)

(西安交通大學(xué)電子與信息工程學(xué)院,710049,西安)

針對無線傳感器網(wǎng)絡(luò)中基于跳數(shù)的節(jié)點(diǎn)定位算法不能滿足無偏距離估計(jì)、節(jié)點(diǎn)定位誤差大的問題,提出了一種改進(jìn)的無偏距離估計(jì)與節(jié)點(diǎn)定位算法(UEDV-hop,Unbiased Estimation DV-hop)。該算法分析期望距離和跳數(shù)的關(guān)系,建立一種新的期望距離與跳數(shù)模型,根據(jù)節(jié)點(diǎn)通信半徑是否已知分別推導(dǎo)了兩種UEDV-hop的求解形式。仿真實(shí)驗(yàn)結(jié)果表明:所提的兩種UEDV-hop算法的估計(jì)距離在不同跳數(shù)時都近似等于該跳期望距離,算法在距離估計(jì)和節(jié)點(diǎn)定位精度上相對于DV-hop(Distance Vector-hop)算法及基于最小二乘法改進(jìn)的DV-hop算法都有較大提高,在節(jié)點(diǎn)數(shù)目等于2 500時,UEDV-hop算法的估計(jì)距離誤差比DV-hop算法降低了9.5%,定位精度提高了55%。

無線傳感器網(wǎng)絡(luò);距離估計(jì);節(jié)點(diǎn)定位

無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法是一個重要的支撐技術(shù)[1-5]。通常用戶不僅需要知道發(fā)生了什么,還需要知道事件發(fā)生的地點(diǎn)或目標(biāo)所處的位置。節(jié)點(diǎn)定位算法允許網(wǎng)絡(luò)中每個節(jié)點(diǎn)獲取自身的位置信息,位置信息可以是節(jié)點(diǎn)的絕對坐標(biāo)或相對坐標(biāo)。定位算法必須滿足低成本、高能效、高定位精度的要求,受節(jié)點(diǎn)資源限制,現(xiàn)有的無線傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)定位問題仍未得到圓滿解決?；谔鴶?shù)的距離估計(jì)算法僅需要節(jié)點(diǎn)間的跳數(shù)信息,成本低、適用范圍廣,逐漸受到廣泛關(guān)注。

現(xiàn)有基于跳數(shù)的節(jié)點(diǎn)定位算法可分為兩類[6]:啟發(fā)式算法,例如DV-hop(Distance Vector-hop)算法[7-8];數(shù)學(xué)分析類算法,例如基于期望每跳前進(jìn)距離的無需測距節(jié)點(diǎn)定位算法LAEP(A Novel Range-Free Localization Algorithm Using Expected Hop Progress)算法[9-10]。數(shù)學(xué)分析類算法通過節(jié)點(diǎn)分布模型、節(jié)點(diǎn)通信模型,推導(dǎo)出節(jié)點(diǎn)平均每跳距離,此類算法的缺點(diǎn)在于,需要知道節(jié)點(diǎn)通信半徑、具體的節(jié)點(diǎn)分布模型。在很多無線傳感器網(wǎng)絡(luò)的應(yīng)用中,節(jié)點(diǎn)隨機(jī)散播在目標(biāo)區(qū)域內(nèi),節(jié)點(diǎn)分布函數(shù)、節(jié)點(diǎn)通信半徑等信息不一定事先確切已知,無法應(yīng)用數(shù)學(xué)分析類算法。

啟發(fā)式算法根據(jù)錨節(jié)點(diǎn)的信息得到整個網(wǎng)絡(luò)的距離與跳數(shù)關(guān)系,距離估計(jì)結(jié)果更符合跳數(shù)與距離的實(shí)際情況,且算法不需要節(jié)點(diǎn)分布模型和節(jié)點(diǎn)通信模型等信息,應(yīng)用范圍更加廣泛。但是,這類算法需要錨節(jié)點(diǎn)數(shù)目多,錨節(jié)點(diǎn)運(yùn)算量大,定位精度隨著錨節(jié)點(diǎn)增加而改進(jìn),整體定位精度不高,因此出現(xiàn)了很多針對DV-hop的改進(jìn)算法。

現(xiàn)有的DV-hop算法及其改進(jìn)算法,采用距離為跳數(shù)和平均每跳距離乘積的模型,這種模型并不能反映每跳的期望距離和跳數(shù)的真實(shí)關(guān)系,距離估計(jì)不是無偏估計(jì),基于現(xiàn)有模型的節(jié)點(diǎn)定位算法的節(jié)點(diǎn)定位精度也會受到影響。為此,采用本文所提出的新的期望距離與跳數(shù)的關(guān)系模型[11],通過類似DV-hop算法的步驟,提出一種新的無偏的DV-hop改進(jìn)算法(Unbiased Estimation DV-hop)。最后給出了距離估計(jì)和定位精度的仿真實(shí)驗(yàn)結(jié)果,并與傳統(tǒng)DV-hop及其改進(jìn)算法進(jìn)行了比較分析。

1 DV-hop算法基本原理

本節(jié)將詳細(xì)介紹DV-hop算法的基本思路和步驟,以及基于最小二乘的DV-hop改進(jìn)算法。DV-hop算法是經(jīng)典的基于跳數(shù)的距離估計(jì)算法,通過跳數(shù)與距離的關(guān)系模型,利用錨節(jié)點(diǎn)之間的關(guān)系得到模型的參數(shù),進(jìn)而確定節(jié)點(diǎn)間距離。DV-hop算法所采用的模型為

d=Hh

(1)

式中:d為估計(jì)距離;h為節(jié)點(diǎn)間跳數(shù);H為平均每跳距離。DV-hop算法分3個步驟。

步驟1所有節(jié)點(diǎn)獲得它到所有錨節(jié)點(diǎn)的跳數(shù)。錨節(jié)點(diǎn)通過受控范圍廣播其坐標(biāo)信息,同時所有節(jié)點(diǎn)獲得它到錨節(jié)點(diǎn)的跳數(shù)信息。

步驟2每個錨節(jié)點(diǎn)利用已經(jīng)得到的其他錨節(jié)點(diǎn)的位置信息和對應(yīng)的跳數(shù)信息,計(jì)算平均每跳距離

(2)

式中:m為錨節(jié)點(diǎn)數(shù)目,hij為錨節(jié)點(diǎn)i和j之間的跳數(shù);(xi,yi)、(xj,yj)分別指錨節(jié)點(diǎn)i和j的坐標(biāo)。

進(jìn)而,所有錨節(jié)點(diǎn)廣播其平均每跳距離Hi。當(dāng)待定位節(jié)點(diǎn)u收到該錨節(jié)點(diǎn)i的平均每跳距離后,代入式(1)得到節(jié)點(diǎn)之間的估計(jì)距離。

步驟3待定位節(jié)點(diǎn)在得到錨節(jié)點(diǎn)的坐標(biāo)和到錨節(jié)點(diǎn)的距離之后,對每個錨節(jié)點(diǎn)都可得到如下方程

(3)

在收到m個錨節(jié)點(diǎn)的信息后,就得到了一個含有m個方程的非線性方程組。解此非線性方程組的方法有很多,本節(jié)采用引入新變量w=x2+y2的方法將方程組線性化求解。方程組以矩陣的形式表示

Ax=b

(4)

式中

將此方程的最小二乘解作為節(jié)點(diǎn)的估計(jì)位置,可得到如下公式

xLS=(ATA)-1ATb

(5)

現(xiàn)有眾多對DV-hop的改進(jìn)算法,大部分改進(jìn)都是針對平均每跳距離的改進(jìn),其中采用最小二乘法求解平均每跳距離的算法簡單有效,其計(jì)算錨節(jié)點(diǎn)的平均每跳距離的公式為

(6)

2 無偏估計(jì)UEDV-hop算法

現(xiàn)有模型中距離為平均每跳距離和跳數(shù)乘積,并不能真實(shí)描述期望距離和跳數(shù)之間的關(guān)系。因此,基于現(xiàn)有模型的算法,其估計(jì)的距離并不是無偏估計(jì),節(jié)點(diǎn)定位也會產(chǎn)生較大的誤差。根據(jù)DV-hop算法及本文研究的期望距離與跳數(shù)的關(guān)系[11],提出一種近似無偏估計(jì)的DV-hop節(jié)點(diǎn)定位算法,使估計(jì)距離等于該跳的期望距離,并改善節(jié)點(diǎn)的定位精度。

為了更清楚地描述UEDV-hop算法,首先將所提出的距離與跳數(shù)的新模型表示為

(7)

模型中有平均每跳距離H、偏差α和節(jié)點(diǎn)通信半徑r3個變量,它們之間的關(guān)系為

α=r-0.5H

(8)

因此,只須求得其中兩個參數(shù),就可得到完整的距離與跳數(shù)的關(guān)系,進(jìn)而通過節(jié)點(diǎn)間跳數(shù)估計(jì)節(jié)點(diǎn)間的距離,最終確定待定位節(jié)點(diǎn)的位置。

2.1 通信半徑已知

上述距離與跳數(shù)的新模型是基于網(wǎng)絡(luò)拓?fù)涓飨蛲缘募僭O(shè)條件推導(dǎo)出來的。一般假設(shè)所有節(jié)點(diǎn)具有相同的通信半徑。如果r已知,那么可以將r和α代入式(7)得到一個僅與H相關(guān)的模型

(9)

UEDV-hop算法通過現(xiàn)有錨節(jié)點(diǎn)之間的距離和跳數(shù)關(guān)系來估計(jì)H的值,并采用最小二乘法計(jì)算平均每跳距離。與DV-hop算法不同,式(9)將1跳節(jié)點(diǎn)和h跳節(jié)點(diǎn)(h>1)的距離分開描述,因此需用跳數(shù)大于1的錨節(jié)點(diǎn)對計(jì)算平均每跳距離H。

對錨節(jié)點(diǎn)i,選取所有到其跳數(shù)大于1的錨節(jié)點(diǎn),將它們之間的距離和跳數(shù)代入式(9),可得

(10)

已知現(xiàn)有錨節(jié)點(diǎn)之間的真實(shí)距離和估計(jì)距離,那么估計(jì)距離的均方誤差為

(11)

最小化估計(jì)距離的均方誤差,即?f/?Hi=0,則錨節(jié)點(diǎn)i的平均每跳距離為

(12)

在得到了錨節(jié)點(diǎn)i的平均每跳距離Hi和節(jié)點(diǎn)通信半徑后,代入式(7)可得到待定位節(jié)點(diǎn)u到錨節(jié)點(diǎn)i的估計(jì)距離。

節(jié)點(diǎn)通信半徑已知,本算法只須計(jì)算一個變量平均每跳距離Hi,錨節(jié)點(diǎn)的計(jì)算量小。1跳節(jié)點(diǎn)的期望距離在圓盤模型和節(jié)點(diǎn)均勻分布假設(shè)下,恒等于2r/3,因此1跳節(jié)點(diǎn)的估計(jì)距離均方誤差最小。算法以估計(jì)距離的均方誤差最小為條件,因此所得到的平均每跳距離更接近于錨節(jié)點(diǎn)數(shù)目多的跳數(shù)對應(yīng)的情況。

2.2 通信半徑未知

在無線傳感器網(wǎng)絡(luò)的工程應(yīng)用中,節(jié)點(diǎn)的通信范圍可以隨著輸入能量的變化而改變,因此很多情況下節(jié)點(diǎn)的通信半徑是未知的。傳統(tǒng)的DV-hop等算法不需要節(jié)點(diǎn)的通信半徑。本節(jié)討論在通信半徑未知時UEDV-hop算法的實(shí)現(xiàn)。

將距離與跳數(shù)關(guān)系中通信半徑用其他兩個變量表示,可以得到

(13)

和上節(jié)相同,式(13)分為兩段描述距離和跳數(shù)的關(guān)系,需要用跳數(shù)大于等于2的錨節(jié)點(diǎn)對得到Hi和αi的值。對任意錨節(jié)點(diǎn)i,將它的2跳及以上鄰居錨節(jié)點(diǎn)的距離和跳數(shù)代入式(13)中相應(yīng)的式子,就得到一個關(guān)于變量Hi和αi的線性方程組

(14)

式(14)有兩個未知數(shù),因此至少需要兩個方程才能得到確切的解,也即要求每個錨節(jié)點(diǎn)至少有兩個2跳以上的相鄰錨節(jié)點(diǎn),才能確定該錨節(jié)點(diǎn)的距離與跳數(shù)的關(guān)系。

通過最小二乘法解式(14),很容易得到Hi和αi的值。每個錨節(jié)點(diǎn)廣播自身的Hi和αi的值。當(dāng)待定位節(jié)點(diǎn)u收到錨節(jié)點(diǎn)i的廣播信息后,將節(jié)點(diǎn)u和錨節(jié)點(diǎn)i之間的跳數(shù)代入式(13),可以得到待定位節(jié)點(diǎn)u和錨節(jié)點(diǎn)i的估計(jì)距離。

一般情況下,每跳前進(jìn)距離是隨著跳數(shù)的增加而增加的,并趨近于一個固定值。該固定值隨著節(jié)點(diǎn)密度增大趨近于r[11],因此根據(jù)算法所得到的估計(jì)距離誤差在2跳時最大。為改進(jìn)2跳節(jié)點(diǎn)的估計(jì)距離,假設(shè)2跳節(jié)點(diǎn)均勻分布在以源節(jié)點(diǎn)為圓心、內(nèi)半徑為r、外半徑為r+H的圓環(huán)內(nèi),那么2跳節(jié)點(diǎn)的期望距離可以表示為

(15)

以此作為2跳節(jié)點(diǎn)的估計(jì)距離。至此,通過現(xiàn)有錨節(jié)點(diǎn)之間的關(guān)系,可得到所有節(jié)點(diǎn)到錨節(jié)點(diǎn)的估計(jì)距離,且不需要通信半徑r的信息。

最后,將待定位節(jié)點(diǎn)到錨節(jié)點(diǎn)的估計(jì)距離和錨節(jié)點(diǎn)的坐標(biāo)代入式(3)。在得到3個或更多錨節(jié)點(diǎn)的信息后,將方程組線性化,通過最小二乘法計(jì)算待定位節(jié)點(diǎn)的估計(jì)位置。

2.3UEDV-hop算法流程圖

整個UEDV-hop算法的待定位節(jié)點(diǎn)及錨節(jié)點(diǎn)的定位算法流程圖如圖1所示。

圖1 待定位節(jié)點(diǎn)及錨節(jié)點(diǎn)的UEDV-hop定位流程圖

3 仿真結(jié)果

本節(jié)從距離估計(jì)精度和定位精度的仿真兩方面來考察UEDV-hop算法的性能。為了驗(yàn)證算法性能,本文利用Matlab7.9建立如下仿真環(huán)境,在1×1的正方形區(qū)域范圍內(nèi),隨機(jī)均勻分布1 500個節(jié)點(diǎn),其中錨節(jié)點(diǎn)所占比例為3%,錨節(jié)點(diǎn)均勻分布且坐標(biāo)信息精確無誤差。節(jié)點(diǎn)通信符合圓盤通信模型,且所有節(jié)點(diǎn)具有相同的通信半徑(r=0.1)。所有節(jié)點(diǎn)都可通過多跳的方式和其他任意節(jié)點(diǎn)通信,沒有孤立節(jié)點(diǎn)。為了比較節(jié)點(diǎn)數(shù)目和錨節(jié)點(diǎn)比例對距離估計(jì)絕對誤差和定位誤差的影響,在其他參數(shù)不變的情況下,通過改變節(jié)點(diǎn)數(shù)目或錨節(jié)點(diǎn)比例進(jìn)行仿真。

3.1 距離估計(jì)

3.1.1 不同跳數(shù)下算法的歸一化誤差均值及絕對誤差 為了驗(yàn)證距離估計(jì)算法的性能,采用歸一化誤差均值eM和歸一化絕對誤差eA評價算法性能,其定義為

(16)

(17)

首先,考察不同算法的歸一化誤差均值eM隨跳數(shù)變化的情況,仿真結(jié)果如圖2所示。DV-hop算法和DV-hop(LS)算法的歸一化誤差均值在不同跳數(shù)下均不等于0,這說明估計(jì)距離和該跳期望距離存在較大偏差。歸一化誤差均值在1跳時小于0,說明1跳的期望距離大于平均每跳距離H,UEDV-hop算法在不同跳數(shù)情況下歸一化誤差均值近似等于0,這表明UEDV-hop算法的估計(jì)距離是近似無偏的。

圖2 不同跳數(shù)的歸一化誤差均值

圖3 不同跳數(shù)的歸一化絕對誤差

圖3比較了4種算法的歸一化絕對誤差隨跳數(shù)的變化,可以看到DV-hop和DV-hop(LS)算法的歸一化絕對誤差均大于UEDV-hop算法,6跳的歸一化絕對誤差近似等于UEDV-hop算法。這表明歸一化絕對誤差受到估計(jì)距離和期望距離偏差的影響,偏差越大歸一化絕對誤差就越大。由圖2可見,兩種UEDV-hop的歸一化絕對誤差隨著跳數(shù)增加而增加,且增加的幅度隨著跳數(shù)增加而減小,這說明隨著跳數(shù)的增加,相同跳數(shù)節(jié)點(diǎn)距離的分布更分散。

3.1.2 不同節(jié)點(diǎn)數(shù)目的歸一化絕對誤差 下面考察整體估計(jì)距離的絕對誤差,對所有待定位節(jié)點(diǎn)到錨節(jié)點(diǎn)之間的距離,求其估計(jì)距離歸一化絕對誤差的平均值。圖4比較了在不同節(jié)點(diǎn)數(shù)目下4種算法的歸一化絕對誤差eA,其中錨節(jié)點(diǎn)比例設(shè)置為3%。UEDV-hop1和UEDV-hop2的歸一化絕對誤差最小,這表明所提算法的定位精度優(yōu)于傳統(tǒng)DV-hop算法及其改進(jìn)算法。隨著節(jié)點(diǎn)數(shù)目的增加,4種算法的歸一化絕對誤差都隨之減小,并趨于一個固定值,這說明基于跳數(shù)的距離估計(jì)精度有極限值。

圖4 節(jié)點(diǎn)數(shù)目對歸一化絕對誤差的影響

3.1.3 不同錨節(jié)點(diǎn)比例的歸一化絕對誤差 圖5對比了4種算法在不同錨節(jié)點(diǎn)比例下絕對誤差eA的變化,節(jié)點(diǎn)數(shù)目固定為1 500。由圖可見,隨著錨節(jié)點(diǎn)比例增加,4種算法的估計(jì)距離絕對誤差都隨之減小,并趨近于一個固定值。這是因?yàn)榛谔鴶?shù)的距離估計(jì)算法估計(jì)距離精度只與通信半徑和網(wǎng)絡(luò)連通度相關(guān),錨節(jié)點(diǎn)比例的增加只使得估計(jì)距離接近期望距離,從而減小了估計(jì)距離誤差。

圖5 錨節(jié)點(diǎn)比例對歸一化絕對誤差的影響

3.2 定位精度

距離估計(jì)的最終目的是用于節(jié)點(diǎn)的定位,本節(jié)考察所提出的距離估計(jì)算法的節(jié)點(diǎn)定位精度。用歸一化均方誤差eR考察節(jié)點(diǎn)定位精度,其定義為

(18)

首先考察4種算法在不同節(jié)點(diǎn)數(shù)目下的定位精度,錨節(jié)點(diǎn)數(shù)目固定為3%,仿真結(jié)果如圖6所示。由圖可見,4種算法定位結(jié)果的歸一化均方誤差都隨著節(jié)點(diǎn)數(shù)目增加而減小。兩種UEDV-hop算法的節(jié)點(diǎn)定位誤差幾乎相等,且小于DV-hop算法和DV-hop(LS)算法的定位結(jié)果。在節(jié)點(diǎn)數(shù)目為2 500時,雖然UEDV-hop算法的歸一化絕對誤差和DV-hop算法相差0.02r左右,但UEDV-hop算法的歸一化均方誤差約為DV-hop算法的一半,這說明無偏的距離估計(jì)對定位結(jié)果的影響大。

圖6 節(jié)點(diǎn)數(shù)目對歸一化均方誤差的影響

圖7考察4種算法在不同錨節(jié)點(diǎn)比例下的定位精度,節(jié)點(diǎn)數(shù)目固定為1 500。由圖可見,隨著錨節(jié)點(diǎn)比例增加,4種算法的歸一化均方誤差隨之減小,并趨近于一個固定值。這是由于錨節(jié)點(diǎn)的增加,有助于估計(jì)距離更接近期望距離,使定位誤差最終趨近于無偏估計(jì)時的定位誤差。其中,兩種UEDV-hop算法的歸一化均方誤差最小。

圖7 錨節(jié)點(diǎn)比例對歸一化均方誤差的影響

4 結(jié) 論

在無線傳感器網(wǎng)絡(luò)中,無需測距的節(jié)點(diǎn)定位算法是節(jié)點(diǎn)定位研究中的難題之一。針對傳統(tǒng)基于跳數(shù)的定位算法,例如DV-hop算法不能滿足無偏的距離估計(jì),使得定位誤差大的問題,首先提出了期望距離與跳數(shù)關(guān)系的新模型,進(jìn)而利用錨節(jié)點(diǎn)來估計(jì)新模型的參數(shù),提出了無偏估計(jì)DV-hop新算法,并根據(jù)節(jié)點(diǎn)通信半徑是否已知兩種應(yīng)用情況推導(dǎo)了兩種UEDV-hop求解形式。最后,仿真實(shí)驗(yàn)表明,所提出的兩種UEDV-hop算法近似屬于無偏的距離估計(jì)算法,且兩種UEDV-hop算法在距離估計(jì)和節(jié)點(diǎn)定位精度上相對于DV-hop算法及DV-hop(LS)算法都有較大提高,UEDV-hop算法在節(jié)點(diǎn)數(shù)目等于2 500時,定位精度比DV-hop算法提高了55%。

[1] MAO Guoqiang,FIDAN B,ANDERSON B.Wireless sensor network localization techniques [J].Computer Networks,2007,51(10): 2529-2553.

[2] 周旭,李善倉,王新珩.大規(guī)模傳感器網(wǎng)絡(luò)局部半定規(guī)劃的節(jié)點(diǎn)定位算法 [J].西安交通大學(xué)學(xué)報(bào),2009,43(8): 38-42.

ZHOU Xu,LI Shancang,WANG Xinheng.Nodes locating algorithm based on local semi-definite programming for large scale wireless sensor networks [J].Journal of Xi’an Jiaotong University,2009,43(8): 38-42.

[3] 李善倉,傅鵬,張德運(yùn).無線傳感器網(wǎng)絡(luò)中的分布式節(jié)點(diǎn)定位方法 [J].西安交通大學(xué)學(xué)報(bào),2007,41(12): 1418-1422.

LI Shancang,FU Peng,ZHANG Deyun.Distributed nodes localization method in wireless sensor networks [J].Journal of Xi’an Jiaotong University,2007,41(12): 1418-1422.

[4] 王文杰,張渭樂,殷勤業(yè).利用離去角度的無線傳感器網(wǎng)絡(luò)分布式節(jié)點(diǎn)定位方法 [J].西安交通大學(xué)學(xué)報(bào),2010,44(2): 61-66.

WANG Wenjie,ZHANG Weile,YIN Qinye.A distributive localization method for wireless sensor networks using angle of departure [J].Journal of Xi’an Jiaotong University,2010,44(2): 61-66.

[5] 孔慶茹,楊新宇,閆超,等.一種基于接收信號強(qiáng)度指示的改進(jìn)型定位算法 [J].西安交通大學(xué)學(xué)報(bào),2008,42(2): 147-151.

KONG Qingru,YANG Xinyu,YAN Chao,et al.Improved localization algorithm based on received signal strength indicator [J].Journal of Xi’an Jiaotong University,2008,42(2): 147-151.

[6] NATH S,EKAMBARAM V N,KUMAR A,et al.Theory and algorithms for hop-count-based localization with random geometric graph models of dense sensor networks [J].ACM Transactions on Sensor Networks,2012,8(4): 111-152.

[7] NICULESCU D,NATH B.DV based positioning in Ad Hoc networks [J].Telecommunication Systems,2003,22(1): 267-280.

[8] KUMAR S,LOBIYAL D.An advanced DV-hop localization algorithm for wireless sensor networks [J].Wireless Personal Communications,2012,71(2): 1365-1385.

[9] WANG Yun,WANG Xiaodong,WANG Demin,et al.Range-free localization using expected hop progress in wireless sensor networks [J].IEEE Transactions on Parallel and Distributed System,2009,20(10): 1540-1552.

[10]VURAL S,EKICI E.On multihop distances in wireless sensor networks with random node locations [J].IEEE Transactions on Mobile Computing,2010,9(4): 540-552.

[11]WEI Quanrui,HAN Jiuqiang,ZHONG Dexing,et al.An improved multihop distance estimation for DV-Hop localization algorithm in wireless sensor networks [C]∥Proceedings of the IEEE 76th Vehicular Technology Conference.Piscataway,NJ,USA: IEEE,2012: 1-5.

[本刊相關(guān)文獻(xiàn)鏈接]

汪志偉,曹建福,鄭輯光.一種面向分簇?zé)o線傳感器網(wǎng)絡(luò)的多信道跨層協(xié)議.2013,47(6):61-67.[doi:10.7652/xjtuxb 201306011]

李彬,王文杰,殷勤業(yè),等.無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)協(xié)作的節(jié)能路由傳輸.2012,46(6):1-6.[doi:10.7652/xjtuxb201206001]

李彬,王文杰,殷勤業(yè),等.一種利用天線旋轉(zhuǎn)的無線傳感器網(wǎng)絡(luò)定位算法.2011,45(4):60-66.[doi:10.7652/xjtuxb 201104011]

楊新宇,孔慶茹,戴湘軍.一種改進(jìn)的加權(quán)質(zhì)心定位算法.2010,44(8):1-4.[doi:10.7652/xjtuxb201008001]

何欣,桂小林,安健.面向目標(biāo)覆蓋的無線傳感器網(wǎng)絡(luò)確定性部署方法.2010,44(6):6-9.[doi:10.7652/xjtuxb201006002]

王文杰,張渭樂,殷勤業(yè).利用離去角度的無線傳感器網(wǎng)絡(luò)分布式節(jié)點(diǎn)定位方法.2010,44(2):61-66.[doi:10.7652/xjtuxb201002013]

(編輯 武紅江)

AnImprovedDV-hopNodeLocalizationAlgorithmBasedonUnbiasedEstimationforWirelessSensorNetworks

WEI Quanrui,LIU Jun,HAN Jiuqiang

(School of Electronics and Information Engineering,Xi’an Jiaotong University,Xi’an 710049,China)

An improved DV-hop localization algorithm based on unbiased estimation is proposed to obtain the unbiased estimation of distance and to reduce the localization error of existing node localization methods based on hop-count for wireless sensor networks.A modified model of the relationship between expected distance and hop count is established through analyzing the hop progress information for different hop counts; Two approaches for the solution of UEDV-hop method are derived,according to whether node communication radiuses are known.Simulation results and comparisons with the DV-hop and the DV-hop (LS) algorithms show that the distance estimated by the UEDV-hop is approximately equal to the expectation distance,and that the estimation error and the localization accuracy of the UEDV-hop are improved significantly.A comparison to the DV-hop with 2 500nodes shows that the distance estimation error of the UEDV-hop is reduced by 9.5%,and the localization accuracy is improved by 55%.

wireless sensor network; distance estimation; node localization

2013-12-09。

魏全瑞(1984—),男,博士生;劉俊(通信作者),男,講師。

國家自然科學(xué)基金資助項(xiàng)目(61105021,61071217);教育部高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金資助項(xiàng)目(20110201110010)。

時間:2014-04-16

10.7652/xjtuxb201406001

TP393

:A

:0253-987X(2014)06-0001-06

網(wǎng)絡(luò)出版地址:http:∥www.cnki.net/kcms/detail/61.1069.T.20140416.1746.010.html