基于DV－HOP 的改进算法WDV－HOP 及仿真

唐 辉，纪 萍

(河海大学文天学院 电气信息学院，安徽 马鞍山 243031)

随着具有感知、计算和通信能力的微型传感器的出现，由传感器节点组成的网络(Wireless Sensor Network，WSN)。已被列为对人类未来生活产生影响的10 大新兴技术之一［1］。由于节点的位置均是随机的，节点所采集到的数据若是无位置信息几乎是毫无应用价值的。所以，节点定位也就成为关键问题。考虑到WSN 网络特殊的要求，定位算法应简单、准确、能量有效等。DV－HOP(Distance Vector－Hop)是一种实用有效的算法，但该算法在定位精度上通过存在不足。本文首先讨论DV－HOP 算法，并提出一种改进的节点定位算法WDV－HOP，进行仿真实验，验证了定位效果。

1 DV－HOP 原理及AHS 转发机制与节点定位

基于非测距的定位算法中通常广播3 种定位消息:DV－HOP、Dv－Distance 和Euclidean。在DVHOP 算法中锚节点获取到距其周围所有锚节点的坐标信息和跳数信息后，便可计算出AHS(Average of Hop)。然后该锚节点就向其周围的普通节点广播该AHS 值。当普通节点接收到锚节点发送的AHS 值以及距离锚节点的最小跳数后，便可计算出到锚节点的距离。当一个普通节点得到距离3 个或3 个以上锚节点的距离后，就能依据三边法则计算出其自身的坐标［2］。

每一个锚节点均存储一张“锚节点表”该表记录有邻居锚节点的ID 号、坐标信息、以及其邻居锚节点的最小跳数等信息。定位开始阶段每个锚节点对外广播包含自身的ID、坐标信息、以及初始计数器值为零的消息。可称该消息为“跳数获取消息”，当其他锚节点收到该消息后便开始检查自己的锚节点表，若表中还没有该锚节ID 的记录，则在自己的锚节点表中加入一条记录，同时将消息中的计数器值加1 后向周围节点转发。若锚节点表中已存在该锚节点ID 的记录，则比较记录中的跳数值是否大于收到消息中的跳数值，若大于则更新为较小的值，同时也将消息中的计数器值加1 转发。若消息中的跳数值大于或等于锚节点表中的值，则直接丢弃该消息不再转发。

DV－HOP 位算法中一个重要的消息是锚节点发送含有AHS 值的消息。定位开始后锚节点启动定时器，当更新AHS 值定时器到达后，锚节点便开始计算AHS 值，若“锚节点表”被更新也将促发新一轮AHS值的计算。AHS 在网络中按一定的规则转发，普通节点只接受相同ID 锚节点的AHS 值，第一个AHS 值的获取采用先到先得的方式，对于随后转发的不同ID 锚节点的AHS 值则采取丢弃原则。当所有锚节点的AHS 值均被计算出后整个AHS 求解过程结束［3－5］。而当普通节点获取到AHS 值与到3 个或3 个以上锚节点的最小跳数后，可利用三边算法计算出其物理坐标。由于整个定位过程均为迭代进行，因此称该定位算法为迭代法［2］。

2 改进的算法WDV－HOP

在DV－HOP 算法中信标节点的主要任务是计算出AHS 值。AHS 值的计算公式为

其中，R 是物理坐标已知的信标节点两两之间的距离值矩阵

其中，H 是定位初始阶段获得的信标节点之间的最小跳数值矩阵

信标节点是预先布设好或地理位置是可通过类似GPS 等方法精确获取的。所以，矩阵R 是已知的。因此，矩阵AHS 值完全取决于跳数值矩阵H，同时定位误差也主要来源于H 值。若能找到更合理的H，则能计算出更加真实反应网络情况的AHS 值。从普通节点一侧分析:dij=AHSj×hij，其中dij是普通节点i 到锚节点j 的距离，hij是普通节点i 到锚节点j 的最小跳数值。dij的大小与AHSj和hij值均有关［3－4］。综上分析，可分别从信标节点和普通节点两侧着手提出改进的测距算法。

(1)在信标节点侧提出以下改进措施:每个信标节点维护一张邻居信标节点的信息表，信息表中维护着自身到各个信标节点的路径字段NBHopMsg，规定到每个邻居信标节点i 至少记录5 条路径信息，5 条路径分别记录着该信标节点到达邻居信标节点的不同路径所需的跳路径与跳数，而对于少于3 条路径的情况则需重新启用路径获取过程以保证计算的精确度。这样，信标节点j 在计算AHSj值时，对于记录中的每一个跳数值分别计算其对应的AHS 值:AHSj1=rji/hopji1，AHAj2=rji/hopji2，…，AHSj5=rji/hopji5…，最后再用信标节点间的跳数值做权值并对所得AHS 值求加权平均即

最终计算得到信标节点j 到信标节点i 的加权AHSJ值;到其他信标节点也依据同理获得其对应的AHS 值，最终将信标节点j 的所有AHS 值用信标节点间的距离做加权求得最终值，距离越远权值越大。通过上述加权方法得到改进的AHS 值能更加真实地反映该信标节点附近的网络情况，使最终的定位结果更精确

(2)标准DV－HOP 算法中，普通节点只接收从最近的信标节点发送的AHS 值，一旦某个普通节点获取到AHS 值后则会拒绝接受其他信标节点的发送数据。但事实情况是由于各种原因通常无法保证普通节点所接收的AHS 值是最近信标节点发送的，这样势必会给后面的定位造成误差。另一方面通过实际观察发现当存在较多信标节点时，AHS 消息值会存在严重浪费，所以可考虑充分利用这些AHS 值。实际中考虑到越靠近普通节点的锚节点AHS 值有着越发重要的作用，因此可给每个接收到的AHS 值做加权，权就取为普通节点到信标节点跳数的倒数。但为防止采用过多AHS 的值会产生负面影响，本改进算采用仿真经验值，将普通节点用于计算AHS 值的信标节点的个数定为≤3［5］。

(3)由于算法中是将节点间最短路径作为节点间距离的估计，因此节点的定位结果必然存在误差。本改进算法是基于分簇算法的，即簇内大于最大定位半径R 的非邻居节点的距离是通过WDV－HOP 测距法来计算，这些节点的定位精度将直接影响整个簇内节点的定位精度。因此，要提高整个节点的定位精度就需要对上述改进节点的定位结果做进一步修正。由于事先已知信标节点的物理坐标，因此可考虑充分利用信标节点的这些已知属性来提高定位精度［6－7］。下面给出一种利用信标节点信息进行修正因子的方法。设信标节点i 的邻居信标节点信息表中的记录NBi(IDk，hopn)的路径集合为

信标节点间的实际距离为Dij=(di1，…，dik，…)，，将SPi和Dij中的记录值做线形回归运算，该运算要求满足以下条件

式中，Pij为信标节点路径的条数。设普通节点l 距离信标节点u 拥有最短路径，则该节点在做距离计算时对距离值做出修正

其他节点用类似l 节点的方法做出修正。

3 仿真实验

仿真实验的节点分布如图1 所示，矩形区域内随机分布200 个节点，其中信标节点数为6 个(图中圆圈)，平局网络连通度为12，节点无线测距误差为10%，节点最大通信半径r 为15 m。

图1 矩形区域节点分布图

图2 连通度为12 的矩形区域

图3 显示的是WDV－HOP 算法应用于多维定标技术的定位结果，圆圈为信标节点。星形代表未知节点的实际位置，圆点则代表算法定位出的节点位置，二者之间的黑色连线长度代表定位误差的大小。图4 显示的是应用了WDV－HOP 算法和未使用WDV－HOP定位算法的定位结果误差对比。连线代表标准算法的定位误差大小和改进后算法的定位误差大小。从图4误差线段长度可看出，改进后算法普遍误差线段较短，即应用了WDV－HOP 算法的多维定标技术较之标准算法在定位精度方面有所提高。

图3 矩形区域改进算法定位结果图

图4 矩形区域改进算法和标准算法定位结果比较

下面通过整理部分实验数据，定量分析改进后算法在定位精度上获得的提高。表1 列出了矩形区域中不同外设条件下得到的部分定位误差数据。表1 分为两部分，第一部分显示的数据是网络连通度为12 的情况下，两种算法的节点定位误差随节点测距误差的关系数据。第二部分则列出了定位误差为0.1 的情况下，两种算法的节点定位误差随连通度变化的关系数据。

表1 矩形区域定位误差关系抽样表

从表1 第一部分可发现在节点测距误差＜0.1 的情况下，改进算法的精度略高于标准算法，而当测距误差＞0.1 时，改进算法的定位误差明显小于标准算法。从表格第二部分可看出在固定了测距误差的情况下，改变网络平均连通度值，改进算法的定位误差也小于标准算法。

4 结束语

本文描述了DV－HOP 算法的工作原理，然后借鉴DV－HOP 算法思想提出非邻居节点的测距算法WDV－HOP。改进的算法应用于多维定标技术中簇内非邻居节点间的距离计算。仿真结果表明，在相同的实验条件下改进的定位算法定位精度明显优于未改进的定位算法。同时在本次仿真实验中，节点定位精度约有3%的提升。

［1］ 周耀伟，邱卫东，温蜜.一种带认证的LU 密钥预分配方案［J］.计算机应用，2009，29(1):161－164.

［2］ CHONGG C Y，KUMAR S P.Sensor networks.evolution，opportunities，and challenges［J］.Distributcd Wireless Sensor Networks，2003，91(16):124－125.

［3］ 唐辉，张英杰，阮承治.基于DV－HOP 的改进算法及仿真［J］.电子科技，2010，23(7):69－71，76.

［4］ SAVARESE C，RABAEY J，LANGENDOEN K.Robust positioning algorithms for distributed ad－hoc wireless sensor networks［C］.Monterey:Proceeding of USENIX Technical Annual Conference，2002.

［5］ HUANG Qiqian，SELVAKENNEDYR S.A range－free localization algorithm for wirelesssensor networks［J］.Computer Aided Designed，2008，13(5):349－352.

［6］ 刘毓，马晓辉，曹津铭.基于WSN 特点对DV－HOP 算法改进的研究［J］.西安邮电学院学报，2012(6):24－26，55.

［7］ 何艳丽.无线传感器网络质心定位算法研究［J］.计算机仿真，2011，28(5):163－166，219.