无线传感器网络DV-Hop定位改进算法*

卫开夏,田金鹏,王克谦

1.徐州师范大学计算机学院,江苏徐州 221116;2.上海大学 通信与信息工程学院,上海 200072;3.信阳供电公司,河南 信阳 464000

无线传感器网络 (Wireless Sensor Networks)是当前在国际上备受关注的、涉及多学科高度交叉、知识高度集成的前沿热点研究领域[1]。对于传感器网络来说,传感器节点的位置信息至关重要,事件发生的位置或获取信息的节点位置是传感器节点监测消息中所包含的重要信息,没有位置信息的监测数据往往毫无意义。因受成本、功耗、扩展性等问题的限制,为每个传感器安装 GPS模块等这些传统定位手段并不实际,甚至在某些场合可能根本无法实现,而且 GPS定位在定位精度、实时性方面有时并不能满足特定的需求,因此针对具体的定位需求,必须采用一定的算法机制来实现传感器节点的定位。

无线传感器网络节点按定位过程中是否需要测距信息,可分为无需测距的定位方法和基于测距技术的定位方法。近年来,关于传感器网络节点定位技术研究成为无线传感网络技术的一重要研究热点并取得大量的研究成果。其中,具有代表性算法研究成果有：凸规划算法[2]及其改进算法[3],APS算法[4-7]、Cooperative Ranging[8]、AHLos[9]算 法、n-Hop Multilateration Primitive[10]算法 、MDS-MAP[11]算法等。

无需测距的定位方法被认为是一类具有好的成本效益的解决方案。在无需测距定位方法中,DVHop(Distance Vector-Hop)节点定位方法由于对信标节点比例要求较少,定位精度较高,目前已成为一种经典的无需测距定位方法[12]。

DV-Hop定位方法的主要思想是引入最短路径算法到信标节点的选择过程中,从而在未知节点的位置估计过程中可以有效利用多跳信标节点的位置信息,这种方法可以大大减少实现网络定位所需信标节点的比例(密度),从而大大降低网络的布置成本。

本文就 DV-Hop算法的误差成因进行了分析,在 DV-Hop定位算法优点的基础上,针对该算法只适用于各向同性网络的不足,对 DV-Hop算法进行局部优化,使得改进后的 DV-Hop算法减少了数据包发送量,提高了定位精度,并且对于不规则形状的节点分布具有较强的适应性。

1 DV-Hop定位算法

DV-Hop定位算法是 APS算法系列中使用最为广泛的定位方法,其定位过程不依赖于测距方法,利用多跳信标节点信息来参与节点定位,定位覆盖率较大。DV-Hop算法非常类似于传统网络中的距离向量路由机制,在该定位机制中,未知节点首先计算与信标节点的最小跳数,然后估算平均每跳距离,利用最小跳数乘以平均每跳距离,估算得到未知节点与信标节点之间的距离,再利用三边测量法或极大似然估计法计算未知节点的坐标。

DV-Hop定位算法可以分为以下 3个阶段：

(1)计算未知节点与每个信标节点的最小跳数

信标节点向邻居节点广播自身位置信息的分组,其中包括跳数字段,初始化为 0。接收节点记录具有到每个信标节点的最小跳数,忽略来自同一个信标节点的较大跳数的分组。然后将跳数值加 1,并转发给邻居节点。通过这个方法网络中的所有节点能够记录下到每个信标节点的最小跳数。

(2)计算未知节点与信标节点的实际跳段距离

每个信标节点根据第 1阶段中记录的其他信标节点的位置信息和相距跳数,利用式(1)估算平均每跳的实际距离,

其中,(xi,yi)、(xj,yj)是信标节点 i、j的坐标 ,hj是信标节点 i与 j(i≠j)之间的跳段数。

然后,信标节点将计算的每跳平均距离用带有生存期的字段的分组广播到网络中,未知节点仅记录接收到的第 1个每跳平均距离,并转发给邻居节点。这个策略可以确保绝大多数未知节点从最近的信标节点接收每跳平均距离。未知节点接收到平均每跳距离后,根据记录的跳数,计算到每个信标节点之间的距离。

(3)未知节点计算自身位置

未知节点利用第 2阶段中记录的到各个信标节点的跳段距离,利用三边测量法或极大似然估计法计算出自身坐标。

如图 1所示,经过第 1和第 2阶段,能够计算出信标节点 L1与 L2、L3之间的距离和跳数。信标节点 L2计算得到校正值(即每跳平均距离)为(40+75)/(2+5)=16.42。假设未知节点 A从 L2获得校正值,则它与 3个信标节点之间的距离分别为L1：3×16.42,L2：2×16.42,L3：3×16.42,最后可利用三边测量法确定节点 A的位置。

图1 DV-Hop算法示意图

DV-Hop算法采用平均每跳距离来估算实际距离,对节点的硬件要求低,实现简单。其缺点是利用跳段距离代替直线距离,存在一定的误差。

2 DV-Hop算法误差分析

在 DV-Hop定位算法中,算法的第 1阶段,由于传感器节点随机分布和广播分组过程中可能存在冲突等因素,节点得到的到信标节点的最小跳数存在有一定偏差,且跳数越多,偏差越大。

在信标节点采用式(1)估算平均每跳距离时,所利用的是除本节点外所有其他信标节点,所以得到的是全网络范围内的平均每跳距离,不能反映本信标节点局部范围内的网络密度分布情况。因此,采用该方法得出的平均每跳距离在密度均匀的各向同性网络中影响不大,但在密度不均匀的各向异性网络中,就会造成较大的误差。

在 DV-Hop算法的第 3阶段,未知节点利用了到所有信标节点的距离信息,而据前面的分析,未知节点到信标节点的最小跳数可能有偏差,跳数越多,偏差越大,且第 2阶段得出的平均每跳距离也只是对实际距离的一种估算,不可避免会存在着误差,这样信标节点距未知节点跳数越多,二者之间的跳段距离估算误差就越大,利用较远信标节点的距离信息参与位置计算,反而可能降低了定位结果的精确度。

3 DV-Hop算法改进

根据上面的分析,本文对 DV-Hop算法加以改进,改进后的方法计算过程仍与原 DV-Hop算法大致相同,下面仅对改进之处加以说明。

在 DV-Hop算法的第 1阶段,信标节点向邻居节点广播自身位置信息的分组时,该分组加上生存期字段 n,其它节点在转发该广播包时,首先检测生存期字段,如果 n大于 1,则 n=n-1,转发广播包;如果 n不大于 1,则不再转发该广播包,以保证该分组仅在 n跳范围内广播。这样每个节点仅收到 n跳范围内信标节点信息,降低了原 DV-Hop算法全网洪泛造成的高通信开销、高分组冲突概率。

在 DV-Hop算法的第 2阶段,利用式(1)估算平均每跳实际距离时,信标节点 j取自该节点 n跳范围内跳数最少的 m个信标节点。这样处理保证估算的平均每跳实际距离更符合该节点附近的节点分布,提高了距离估计精确度,并使该方法适用于各向异性网络。

最后,在未知节点利用极大似然估计法计算自身坐标时,由于信标距离该未知节点跳段越近,二者之间的距离估计越精确(概率意义上),所以这里只取跳段距离最近的 l个节点进行极大似然估计法运算。这样,既提高了定位精确度,又降低了节点的计算开销。

参数 n、m、l的取值要综合考虑信标节点比例、网络的连通度、传感器节点分布等因素。一般情况下,n要保证绝大部分未知一个节点能收到 3个以上的信标节点分组,而 m、l取 4～6即可取得相对高的精确度。

4 仿真分析

为了评估所提出的改进算法的可用性和有效性,作者利用 Matlab7.0对 DV-Hop算法及本文提出的改进算法(Improved DV-Hop,IDV-Hop)进行了实验仿真,并对相关实验结果进行分析。

仿真分析的网络模型的标准参数如下：设定节点射频通信距离是 10个长度单位,网络规模为 400个节点,均匀随机分布在边长为 100个长度单位的正方形中(这时的平均连通度为 11左右),其中信标节点比例为 5%。在相同的网络场景下,通过改变总节点数来改变网络的连通度,从而实现相同网络场景下不同网络连通度的仿真实验条件。为消除随机性产生的误差,所得仿真结果均为同样参数下仿真 100次所得结果的平均值。

(1)可定位节点比例

可定位节点比例(也称算法覆盖率)是指通过定位算法成功实现位置估计的未知节点数量占网络中所有未知节点数量的百分比。通过仿真结果(图2,IDV-Hop算法中 n取值为 3)

图2 可定位节点比例

可以看出,两种算法的可定位节点比例均和网络的平均连通度、信标节点比例、算法中分组广播的生存期字段的取值都有关系;在同样的参数条件下,IDV-Hop算法的可定位节点比例和 DV-Hop算法相比要低若干个百分点,这是因为在算法第 1阶段,可控洪泛使得部分未知节点收到的信标节点小于 3而不能实施第 3阶段的定位运算。

(2)数据包发送量

图3 数据包发送量

图3为网络连通度为 9和 12时时,DV-Hop算法与 IDV-Hop算法在数据包发送量上的比较,其中横坐标表示信标节点所占的比例,分组广播的生存期字段均取 3,IDV-Hop算法中的 n取值为 3。从图中可以看出,网络的数据通信量随信标节点比例和网络连通度的增加而增加。而在同样的网络参数下,IDV-Hop算法的数据通信量远小于 DV-Hop算法(不到原通信量的 20%),这主要是由于在算法的第 1阶段,IDV-Hop采用的部分洪泛代替了 DV-Hop算法全网范围洪泛的缘故。

另外,IDV-Hop算法的数据通信量与还与 n的选择有关,当n较小时,该算法限制洪泛跳数范围内小,所需的数据通信量就小,但 n值也不是越小越好,如前面分析,较小的 n值会降低算法的可定位节点比例。

(3)定位精度

定位误差(Localization Error,LE)指的是通过定位算法得到的未知节点的估算位置与实际位置的偏差,这种偏差可以用两者之间的欧氏距离除以节点的通信半径来衡量,如式(2)所示。显然,定位误差的大小能最直接说明算法的有效性。

其中(xea,yea)为未知节点的估算位置,(xa,ya)为未知节点的实际位置,R为节点的通信半径。

图4给出了传感器节点均匀分布时,DV-Hop算法和 IDV-Hop算法定位精度比较结果。可以看出,在各向同性网络中,在相同的网络连通度和信标节点比例下,改进后的算法比原算法定位精度均有所提高,特别是在大于 6%时,IDV-Hop算法的定位精度随着信标节点比例升高而迅速提高,而原 DVHop算法提高并不明显,这是由于信标节点比例越高,IDV-Hop算法越有机会采用距离估计精确度较高的邻近信标节点进行定位运算,从而提高了定位精度,验证前面对 DV-Hop算法的分析。

图4 节点均匀分布时的定位精度

图5为传感器节点非均匀分布时(节点分布从左到右逐渐由疏变密),DV-Hop算法和 IDV-Hop算法定位精度结果。与图 4相比,DV-Hop算法定位精度大幅下降,而 IDV-Hop算法仅稍有下降。在同样的网络参数下,IDV-Hop算法的定位精度比 DV-Hop算法提高了大约 20%,可见,改进后的算法更适用于各向异性网络。

图5 节点不均匀分布时的定位精度

5 结语

本文分析了 DV-Hop算法只适用于各向同性网络的原因,对 DV-Hop算法进行局部性优化,给出了无线传感器网络无需测距 DV-Hop定位的改进算法。仿真结果表明,改进后的算法可定位节点比例略有下降,但提高了定位精度,特别是节点非均匀分布时的定位精度,减少了数据包发送量,因此更适用于在实际项目中应用。

[1]Akyildiz I,Su W,Sankarasubramaniam Y,et al.A Survey on Sensor Networks[J].IEEE Communications Magazine,2002,40(8)：102-114.

[2]Doherty L,Pister K SJ,Ghaoui L E.Convex Position Estimation in Wireless Sensor Networks[C]//IEEE INFOCOM2001 Anchorage Alaska,2001：1655-1663.

[3]陈迅,唐红雨,涂时亮.无线传感器网络主动分布节点定位算法[J].计算机工程与设计,2008,29(7)：1664-1667.

[4]Niculescu D,Nath B.Ad Hoc Positioning System(APS)[C]//Proc.of the IEEE INFOCOM 2003.IEEE Computer and Communications Societies,2003：1734-1743.

[5]Niculescu D,Nath B.Localized Positioning in Ad Hoc Networks[C]//1stIEEE Int'l Workshop on Sensor Network Protocols and Applications.Anchorage,A laska,2003：42-50.

[6]Niculescu D,Nath B.DV Based Position in Ad Hoc Networks[J].Journal of Telecommunication System,2005,22(4)：267-280.

[7]姚忠孝,俞立,董齐芬.基于移动信标的 DV-hop无线传感网络定位算法[J].传感技术学报,2009,22(10)：1504-1507.

[8]Savarese C,Rabaey JM,Beutel J.Locationing in Distributed Ad-Hoc Wireless Sensor Network[C]//Proc.of the 2001 IEEE Int'l Conf.on Acoustics,Speech,and Signal.IEEE Signal Processing Society,2001：2037-2040.

[9]Savvides A,Han C-C,Srivastava MB.Dynamic Fine-Grained Localization in Ad-Hoc Networks of Sensors[C]//Proc.of the 7th Annual Int'l Conf.on Mobile Computing and Networking.ACM Press,2001：166-179.

[10]Avvides A,Park H,Srivastava MB.The Bitsand Flops of the NHop Multilateration Primitive for Node Localization Problems[C]//Proc.of the 1st ACM Int'l Workshop on Wireless Sensor Networksand Applications.ACM Press,2002：112-121.

[11]Shang Y,Rum lW,Zhang Y,etal.Localization From Mere Connectivity[C]//Proc.of the 4th ACM Int'l Symp.on Mobile Ad Hoc Networking＆ Computing.Annapolis.ACM Press,2003：201-212.

[12]王福豹,史龙,任丰原.无线传感网络中的自身定位系统和算法[J].软件学报,2005,16(5)：858-868.