改進的無線傳感器網絡無偏距離估計與節(jié)點定位算法

魏全瑞,劉俊,韓九強

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

改進的無線傳感器網絡無偏距離估計與節(jié)點定位算法

魏全瑞,劉俊,韓九強

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

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

無線傳感器網絡;距離估計;節(jié)點定位

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

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

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

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

1 DV-hop算法基本原理

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

d=Hh

(1)

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

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

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

(2)

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

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

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

(3)

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

Ax=b

(4)

式中

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

xLS=(ATA)-1ATb

(5)

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

(6)

2 無偏估計UEDV-hop算法

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

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

(7)

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

α=r-0.5H

(8)

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

2.1 通信半徑已知

上述距離與跳數(shù)的新模型是基于網絡拓撲各向同性的假設條件推導出來的。一般假設所有節(jié)點具有相同的通信半徑。如果r已知,那么可以將r和α代入式(7)得到一個僅與H相關的模型

(9)

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

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

(10)

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

(11)

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

(12)

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

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

2.2 通信半徑未知

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

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

(13)

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

(14)

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

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

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

(15)

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

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

2.3UEDV-hop算法流程圖

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

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

3 仿真結果

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

3.1 距離估計

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

(16)

(17)

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

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

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

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

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

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

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

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

3.2 定位精度

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

(18)

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

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

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

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

4 結 論

在無線傳感器網絡中,無需測距的節(jié)點定位算法是節(jié)點定位研究中的難題之一。針對傳統(tǒng)基于跳數(shù)的定位算法,例如DV-hop算法不能滿足無偏的距離估計,使得定位誤差大的問題,首先提出了期望距離與跳數(shù)關系的新模型,進而利用錨節(jié)點來估計新模型的參數(shù),提出了無偏估計DV-hop新算法,并根據(jù)節(jié)點通信半徑是否已知兩種應用情況推導了兩種UEDV-hop求解形式。最后,仿真實驗表明,所提出的兩種UEDV-hop算法近似屬于無偏的距離估計算法,且兩種UEDV-hop算法在距離估計和節(jié)點定位精度上相對于DV-hop算法及DV-hop(LS)算法都有較大提高,UEDV-hop算法在節(jié)點數(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ī)模傳感器網絡局部半定規(guī)劃的節(jié)點定位算法 [J].西安交通大學學報,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] 李善倉,傅鵬,張德運.無線傳感器網絡中的分布式節(jié)點定位方法 [J].西安交通大學學報,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è).利用離去角度的無線傳感器網絡分布式節(jié)點定位方法 [J].西安交通大學學報,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] 孔慶茹,楊新宇,閆超,等.一種基于接收信號強度指示的改進型定位算法 [J].西安交通大學學報,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.

[本刊相關文獻鏈接]

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

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

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

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

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

王文杰,張渭樂,殷勤業(yè).利用離去角度的無線傳感器網絡分布式節(jié)點定位方法.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—),男,博士生;劉俊(通信作者),男,講師。

國家自然科學基金資助項目(61105021,61071217);教育部高等學校博士學科點專項科研基金資助項目(20110201110010)。

時間:2014-04-16

10.7652/xjtuxb201406001

TP393

:A

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

網絡出版地址:http:∥www.cnki.net/kcms/detail/61.1069.T.20140416.1746.010.html