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

魏全瑞,劉俊,韓九強

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

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

魏全瑞,劉俊,韓九強

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

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

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

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

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

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

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

1 DV-hop算法基本原理

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

d=Hh

(1)

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

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

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

(2)

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

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

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

(3)

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

Ax=b

(4)

式中

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

xLS=(ATA)-1ATb

(5)

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

(6)

2 無偏估計UEDV-hop算法

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

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

(7)

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

α=r-0.5H

(8)

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

2.1 通信半徑已知

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

(9)

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

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

(10)

已知現有錨節點之間的真實距離和估計距離,那么估計距離的均方誤差為

(11)

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

(12)

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

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

2.2 通信半徑未知

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

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

(13)

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

(14)

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

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

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

(15)

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

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

2.3UEDV-hop算法流程圖

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

圖1 待定位節點及錨節點的UEDV-hop定位流程圖

3 仿真結果

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

3.1 距離估計

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

(16)

(17)

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

圖2 不同跳數的歸一化誤差均值

圖3 不同跳數的歸一化絕對誤差

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

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

圖4 節點數目對歸一化絕對誤差的影響

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

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

3.2 定位精度

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

(18)

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

圖6 節點數目對歸一化均方誤差的影響

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

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

4 結 論

在無線傳感器網絡中,無需測距的節點定位算法是節點定位研究中的難題之一。針對傳統基于跳數的定位算法,例如DV-hop算法不能滿足無偏的距離估計,使得定位誤差大的問題,首先提出了期望距離與跳數關系的新模型,進而利用錨節點來估計新模型的參數,提出了無偏估計DV-hop新算法,并根據節點通信半徑是否已知兩種應用情況推導了兩種UEDV-hop求解形式。最后,仿真實驗表明,所提出的兩種UEDV-hop算法近似屬于無偏的距離估計算法,且兩種UEDV-hop算法在距離估計和節點定位精度上相對于DV-hop算法及DV-hop(LS)算法都有較大提高,UEDV-hop算法在節點數目等于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] 周旭,李善倉,王新珩.大規模傳感器網絡局部半定規劃的節點定位算法 [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] 李善倉,傅鵬,張德運.無線傳感器網絡中的分布式節點定位方法 [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] 王文杰,張渭樂,殷勤業.利用離去角度的無線傳感器網絡分布式節點定位方法 [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.

[本刊相關文獻鏈接]

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

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

李彬,王文杰,殷勤業,等.一種利用天線旋轉的無線傳感器網絡定位算法.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]

王文杰,張渭樂,殷勤業.利用離去角度的無線傳感器網絡分布式節點定位方法.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