无线传感器网络中一种改进的DV-Hop定位算法

叶小岭;王伟;张颖超;张鹏飞

【摘 要】节点定位是无线传感器网络应用的关键技术,文章分析了DV-Hop算法及提出的一些改进方法;DV-Hop算法简单把跳数作为衡量节点距离的标准,这样会由于跳数相同、实际距离远近不同而选用错误的锚节点定位引起较大误差;通过引入了RSSI测距模型,把测距技术和非测距技术相结合,校正距离锚节点远近,在一跳之内以及多跳情况下分别实现更高精度的定位从而达到在一定程度上降低定位误差的目的.

【期刊名称】《计算机测量与控制》 【年(卷),期】2010(018)002 【总页数】3页(P488-490)

【关键词】无线传感器网络;节点定位;DV-Hop算法;RSSI 【作 者】叶小岭;王伟;张颖超;张鹏飞

【作者单位】南京信息工程大学信息与控制学院,江苏南京210044;南京信息工程大学信息与控制学院,江苏南京210044;南京信息工程大学信息与控制学院,江苏南京210044;南京信息工程大学信息与控制学院,江苏南京210044 【正文语种】中 文 【中图分类】TN011 0 引言

无线传感网络 (WSN,wireless sensor networks)由于在军事、医学、环境保护等领域有着非常广阔的应用前景,受到众多国家科研机构的重视。它综合了传感器技术、嵌入式计算技术、现代网络及无线通信技术、分布式信息处理技术等,能够通过各类集成化的微型传感器协作地实时监测、感知和采集各种环境或监测对象的信息,这些信息通过无线方式被发送,并以自组多跳的网络方式传送到用户终端以供应用。节点的定位是无线传感网络关键的技术。由于传感器节点存在资源有限、随机部署、通信易受环境干扰甚至失效等特点,定位机制必须满足自组织性、健壮性、能量高效等要求。在无线传感器网络节点定位研究领域,目前,已经提出了一些适用有效的传感器网络的节点定位算法,主要有 DV-Hop算法、DV-distance算法、位置分发算法、Euclidean算法等[1]。文章在DVHop算法的基础上,加入了RSSI测距技术,作为对DV-Hop算法的一种改进方法。 1 节点定位算法分析 1.1 节点定位的基本概念

节点定位是无线传感器网络配置和运行的一个基本和关键问题。所谓节点定位是指对于一组未知位置坐标的网络节点,通过估计至邻居节点的距离或邻居数目,利用节点间交换的信息,确定每个节点位置的机制。通常配置网络时不能对所有节点实施精确控制和人工设置。 1.2 节点定位的原理

在无线传感器网络定位中,定位主要通过角度或距离测定未知节点与3个或3个以上信标节点的位置关系,来计算未知节点的坐标.例如,未知节点知道了该节点到m个信标节点的距离,就可以利用此理论确定此节点的位置.假设m个信标节点的坐标分别为(x1,y1),(x2,y2),…,(xm,ym),待确定位置节点的坐标是(xi,yi),该节点到m个参考节点的距离分别是λ1,λ2,…,λm,根据二维空间距离计算公式,可以获得一个非线性方程组,将其线性化并使用最小二乘方法来求解,可以得到待定位置节点的坐标

(xi,yi)。

1.3 节点定位算法分类

节点定位算法比较多,在特定条件下,某些算法在某些性能指标上可能优于其它算法,而在其它方面可能处于劣势。通过研究和归纳后认为,根据定位过程中是否需要测量实际节点间的距离,目前把定位算法主要分为基于距离的(rangebased)定位算法和距离无关 (range-free)定位算法。前者包括到达时间 (TOA)技术、时间差(TDOA)测距技术、到达角 (AOA)定位法以及信号强度测距 (RSSI)法,后者包括质心算法、DV-Hop算法。距离无关的定位机制受环境因素的影响小,且节点不用附加额外的测距模块,因而节点简单、费用低,适合大规模的无线传感器网络应用[2].提出DV-Hop算法综合RSSI测距模型将是定位系统中很好的方案。 2 DV-Hop定位算法原理

DV-Hop定位算法非常类似于传统网络中的距离向量路由机制,其算法的定位过程可以分为以下三个阶段。

第一阶段:使用典型的距离矢量交换协议,使网络中所有节点获得距锚节点的跳数。为了获得节点间的跳数,锚节点向所有邻居节点广播一个包含其位置信息和跳数(初始值为0)的数据包。接收到该数据包的节点将跳数加1,继续向它的邻居节点转发(除了来源方向),这个过程一直持续下去,直到网络中每个节点都获得每个锚节点的位置信息和相应的跳数值。如果某个节点接收到来自相同锚节点的多个数据包,这表明它到该锚节点有多条路径,此时,节点将保留含有最小跳数值的数据包,而忽略其它数据包,这样就可保证每一个节点得到和锚节点的最小跳数[3]。如图1所示,锚节点A广播的数据包以近似于同心圆的方式在网络中逐次传播,图中的数字代表距离锚节点A的跳数。

图1 锚节点A广播数据包的示意图

第二阶段:在获得其他锚节点位置和相隔跳距之后,锚节点i根据下式计算它和周围

节点的网络平均每跳距离,hdi=(Xj,Yj)是锚节点i、j的坐标,h(i,j)是锚节点i与锚节点j之间的跳数。hdi用来计算锚节点i和周围待定位节点的距离。锚节点进行第二次广播,锚节点向所有邻居节点广播一个包含hd的数据包,同样,当一个节点接收到了第一个hd后,便丢弃所有后来者,这样确保所有节点可从最近的锚节点接收到hd。未知节点接收到hd后,便用hd与它接收到的最小跳数hops的乘积来近似代替它到锚节点i的距离,di=hops×hdi。

第三阶段:当未知节点获得3个或更多锚节点的距离后,利用三边测量法或极大似然估计法计算自己的位置。 3 DV-hop算法的改进方法

由于DV-hop算法采用跳段距离之和代替实际距离,随着跳段数的增加而误差增大,因此为了提高定位精度降低网络的通信量,方法一设置一个门限跳数M,限制接收大于门限跳数M的数据包,当未知节点与锚节点之间最小跳数 N≤M时节点将跳数值自动加1并转发给其他的邻居节点,否则丢弃该分组,即LDV-hop算法。由于设定了门限跳数M,减少了数据通信量,降低了节点能耗,定位精度高,但是通信量也会随着网络连接度的增加而增加。

由于采用三边定位理论,所以网络中可能存在某些不良边界节点无法实现自身定位,例如以下三种情况:(1)节点只与一个可以确定位置的节点直接连接;(2)节点的一跳邻居内只有两个节点可以定位;(3)节点是一个节点群,而该群内没有锚节点且只与一个可以定位的节点与网络连接。为了剔除不良节点,方法二在算法设计中引入两个约束条件:首先,节点接收信息是最新的;其次,接收信息中的跳数小于转发节点曾经发出信息的跳数。满足这两个条件的信息才能够被节点转发,否则被自己邻居节点丢弃。这样,不良节点就不能够获得足够多的参考节点信息,无法进行定位估算,在一定程度上减小了定位的平均误差。

把不良节点直接丢弃或者删除掉,可以减小定位误差,减少通信计算和能量损耗,但是

造成网络中可用节点的数量减少,降低了网络的覆盖率。方法三,信标节点的定位误差对未知节点的计算误差影响不太大。因此可以将已经定位的节点升级为信标节点,进而用来定位其它未知节点,减少网络中不良节点的数量,通过多次加权求平均的方法降低累积误差。

如果三个锚节点共线或者接近共线时,特别是在网络分布不均匀或者是节点稀疏环境下,将导致较大的位置估计误差。另外,DV-Hop算法中未知节点与锚节点的距离1跳之内的平均距离估计误差为通信距离的0.2倍左右,而5跳距离的距离估计误差平均值约为通信距离的0.6倍,可见,未知节点与由锚节点构成的三角形之间的相对距离会影响未知节点的位置估算精度。方法四,引入了一个共线度的概念提出了一种基于网络局部拓扑的自适应共线度阈值确定方法来约束锚节点之间以及未知节点和锚节点的拓扑关系,仿真结果表明尤其在锚节点比例比较低、网络拓扑不规则及网络拓扑锚节点稀疏的情况下表现出了良好的可靠性和鲁棒性[4]。

由于无线传感器网络通常被应用到比较复杂的野外环境中,地形并不是理想的平面,在定位计算的过程中因地形的影响引入的误差较大。方法五,在DV-Hop算法的第二个步骤中对地形做以下修正来提高定位精度:首先计算出整个网络的平均每跳距离和每个节点到信标节点的距离;由于每个锚节点都有精确的物理坐标,这样每对信标节点i,j间的真实距离与估算出来的距离就有个差值Δd,引入增长比uki=Δ d/d,最后给出未知节点k到信标节点i的距离增加比uki计算式为和uih分别为信标节点i到信标节点j与k的距离增加比;mkij和mkih分别为节点k到连线ij和ih的偏离系数);节点k到信标节点i估算距离可以修正为:d′ki=dij/1+μki。该修正操作会引起算法计算复杂度的增加和高能量损耗,但是定位精度较高,可以在网络节点能量较为充足的情况下采用[5]。

4 DV-Hop算法和RSSI相结合的改进定位方法

DV-Hop算法简单把跳数作为衡量节点距离的标准,这样会由于跳数相同、实际距

离远近不同而选用错误的锚节点定位引起较大误差。为了更好地解决这个问题,本文引入了 RSSI测距模型,把测距技术和非测距技术相结合,主要通过校正距离锚节点远近,在一跳之内以及多跳情况下分别实现更高精度的定位从而达到在一定程度上降低定位误差的目的[6]。

为了根据RSSI值估算节点到邻接点的距离,结合无线电传输路径损耗模型 (采用大尺度衰减模型),其数学描述如下:信道的衰落模型是:其中d为距信源的距离,km;P loss(d)为经距离d后的路径损耗,dB;xσ为平均值为0的高斯分布随机变数,其标准差范围为4～10,Pt为发射功率,可由功率的传输路径损耗计算距离d(发射信号功率不能够设置的过大,要确保多跳定位也能够实现而不是单纯依靠某种定位机制来定位。据衰落模型进行的数据统计,一般在d≤4m的范围内采用RSSI定位精度较高)。 改进方法的定位思想如下: 图2 流程图

(1)布署无线传感器网络节点并对节点初始化;

(2)计算RSSI模型值,广播节点信息 (位置以及RSSI模型测距值);

(3)未知节点收集到锚节点足够多的跳数信息之后,计算每跳得平均距离,对于跳数大于1的,不使用该方法。当跳数为1时,提取从锚节点获取的值,当RSSI模型值在平均每跳距离值的范围内时,说明未知节点获取的锚节点距离较近则不修改跳数值采用DV-Hop算法定位;否则,利用RSSI算法对节点实施定位,从而在一定程度上降低节点的定位误差。改进的流程图如图2所示。 5 结论

本文在传统的DV-Hop算法的基础上,加入了RSSI测距技术,提出一种新的DV-Hop算法的改进方法。把测距技术和非测距技术相结合,达到在一定程度上降低定位误差和提高定位精确的目的。 参考文献:

【相关文献】

[1]张晓龙,解慧英,赵小建.无线传感器网络中一种改进的DV-Hop定位算法 [J].计算机应用,2007,27(11):2672-2674.

[2]马祖长,孙怡宁.无线传感器网络的定位算法 [J].计算机工程,2004,30(7):13-14. [3]于 宁,万江文,等.无线传感器网络定位算法研究 [J].传感技术学报,2007,1:187 -192.

[4]张文祥,马银花,郭继坤.无线传感器网络路由算法的研究 [J].计算机测量与控制,2009,17(3):617-619.

[5]Poggi C,Mazzini G.Collinearity for sensor network localization[A].Proceeding s of 2003 IEEE 58th Vehicular Technology Conference[C].Piscataway,NJ,USA:IEEE,2004.3040 -3044. [6]Shang Y,Rumi W,Zhang Y,et al.Localization from connectivity in sensor networks[J].IEEE Transactions on Parallel and Distributed Systems,2004,15(11):961 -974.