改进的无线传感器网络无偏距离估计与节点定位算法

魏全瑞,刘俊,韩九强

(西安交通大学电子与信息工程学院,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]。通常用户不仅需要知道发生了什么,还需要知道事件发生的地点或目标所处的位置。节点定位算法允许网络中每个节点获取自身的位置信息,位置信息可以是节点的绝对坐标或相对坐标。定位算法必须满足低成本、高能效、高定位精度的要求,受节点资源限制,现有的无线传感器网络中的节点定位问题仍未得到圆满解决。基于跳数的距离估计算法仅需要节点间的跳数信息,成本低、适用范围广,逐渐受到广泛关注。

现有基于跳数的节点定位算法可分为两类[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