基于EDV-Hop的免测距定位算法研究

汤文亮，陈 松，周金栋，黄智水

（华东交通大学软件学院，江西南昌 330013）

基于EDV-Hop的免测距定位算法研究

汤文亮，陈 松，周金栋，黄智水

（华东交通大学软件学院，江西南昌 330013）

为了更好地提高无线传感器网络节点定位精度，降低定位成本，针对APS算法存在的不足，提出一种新的免测距定位算法EDV-Hop，通过限制跳数实现局部范围内的定位信息提取，同时调整平均每跳距离，以此提高定位精度。在网络随机部署和任意节点密度的条件下估算节点位置，并从精度和有效性两个方面进行度量。仿真结果表明，EDV-Hop算法比DV-Hop具有更好的定位性能，它能够减少节点间通信量，降低通信成本，提高定位精度。

无线传感器网络；EDV-Hop；免测距定位；定位精度；锚节点；

目前，免测距定位算法大部分是依赖于自组织定位系统（APS）的思想，并把自组织定位算法作为无线传感器网络免测距定位算法的基准［1-2］。在APS中，提出一种分布式的、逐跳的定位算法，此类算法能为无线传感器网络中所有节点提供近似位置信息，并且此类算法被视为距离矢量路由和GPS定位的扩展。尽管APS简单且实用，但是只有当网络节点密集部署、均匀分布的条件下才能得到可接受的位置估计信息。如果节点是随机部署且不均匀的分布，则基于APS算法的定位精度急剧恶化。基于APS定位算法的效率不高，主要有两种观点。第一种观点是锚节点位置信息广播和紧随的估计平均跳距信息广播分离。第二种观点是平均跳距来自无线传感器的整体信息，其中包括非定位信息的引入。如果网络不是均匀密集部署，则会产生大于所必需的误差。

针对APS算法存在的不足，本文提出基于EDV-Hop（expected distance vector-hop）的免测距定位算法，运用该算法估计节点的位置。换言之，在网络随机部署和任意节点密度的条件下，运用EDV-Hop算法分析跳进展，然后估计节点位置。基于邻居节点的有效信息，节点运用EDV-Hop定位算法可独立地确定位置信息。另外，EDV-Hop算法可同步完成广播锚节点位置信息及节点之间相应距离信息。

1 EDV-Hop网络模型

无线传感器网络的随机部署，节点分布随机、节点密度任意［3-4］。因此，我们不能假定节点在空间或者形式上分布是规则的。节点部署通常是通过低空飞机撒落或者无人地面车载工具［5-6］。

定义1 假定网络中的所有节点通信能力相同，若节点ni通信半径为r0，则其覆盖面积M(ni,r0)=πr20。显然，若节点ni的邻居节点nj，则nj的邻节点肯定包括ni。

定义2 假定E(C)为位于传输覆盖范围内的平均节点数目，并定义EC平均连通度为某节点的传输覆盖范围内的邻居节点平均数目。因此，E(C)=λπr20，EC=λπr20-1。

定义3 锚节点Ai(Xi,Yi)通过GPS或人工方式确定其坐标。

2 EDV-Hop跳进展分析

2.1 准备阶段

在节点密集部署的无线传感器网络中，任何两个节点之间存在最短的多跳路径，如图1所示。当转发下一跳时，传输数据远离源节点，其累积距离通过通信范围增加而增加。因此，假如所有节点拥有同样的传输范围，则任何两个节点之间的近似估计距离d为传输半径和它们之间相应跳计数乘积，其表达式为

式中：h为S节点和D节点之间的跳数。节点稀疏地部署，如图2所示。大多数定位算法更倾向于采用大量不精确的距离预测，这是因为节点密度稀疏部署的无线传感器网络不适合在节点之间直接构建最短多跳路径。在这种情况下，下一转发节点的路径位于传输范围边界的概率非常低。跳进展和传输半径的相应差异是可评估的。

图1 无线传感器网络密集部署Fig.1 Dense deployment of WSN

图2 无线传感器网络稀疏部署Fig.2 Sparse deployment of WSN

为了避免这个问题，本文利用期望距离矢量跳和跳计数乘积，提出估计无线传感器网络中任何S和D之间的距离，其表达式为

式中:h为S节点和D节点之间的跳计数，E(R)是邻居节点之间的期望跳进展。在随机节点密度和相同的传输半径的无线传感器网络中，为了得到期望跳进展，本文引出跳进展分析模型。

2.2 跳进展分析

在无线传感器网络中，量化路径距离和网络参数之间的关系是非常重要的［8-9］。路径距离定义为源节点S到目的节点D之间路径长度，路径长度为所有路径当中最短的路径。源节点S转发到目的节点D跳进展的每一跳定义为R，R是随机变量。在一维情况下，节点下一跳通常是线性方向转发到目的节点最远一跳。然而在二维的情况下，下一跳也许不在目的节点D与源节点S的连线上，如图3所示。

为了便于描述和分析，本节定义如下参数：

图3 跳进展分析Fig.3 Hop progress analysis

ri为S节点到下一潜在转发节点ni的跳距，如图3中的r1和r2，其中：r1=Sn1，r2=Sn2。Ri为S节点到其下一潜在转发节点ni的跳距ri映射到S和D之间连线上，如图3中的R1和R2。θi为S节点到其下一潜在转发节点ni与SD的夹角，如图3的θ1和θ2。

图3清晰地显示了源节点S的传输范围，节点n1比节点n2紧靠S的传输范围的边界。然而，相应的映射跳距R1小于R2，例如，当r2＜r1时，R2＞R1。因此，S与D之间的通信，节点n2比节点n1优先作为下一转发节点。跳距和映射跳距之间的关系可表示为：Ri=ricosθi。

只有当邻居节点比当前其他节点更接近目的节点D时，才能作为下一转发节点。例如，节点n3位于节点S的通信范围内，但它比S更远离目的地D，因此不能作为S到D的中间转发节点。这就使得本文必须考虑确定任何从S转发到D的潜在转发区域。

2.3 确定潜在转发区域

图4 潜在转发区域确定Fig.4 Determination of potential transferring zone

3 EDV-Hop算法描述

本节利用三边测量技术和第2节期望跳进展分析结果作为免测距定位EDV-Hop算法描述的基础。在描述EDV-Hop算法之前，先介绍相关符号所表示的意义。P0表示期望跳进展；ni表示节点ni的编号；Ai表示锚节点Ai的编号；Na表示网络中锚节点的数目；Γi表示节点ni的邻居节点集合；τi表示节点ni的邻居节点数目；∑i

pc表示到锚节点Ai的当前累积跳进展；∑iHC表示到锚节点Ai的当前累积跳计数；∑i Pr表

示收到到锚节点Ai的当前累积跳进展；∑iHr表示收到到锚节点Ai的当前累积跳计数。EDV-Hop算法描

述，具体如下。

初始化阶段：节点与其相连通的邻居节点交换问候数据包。邻居节点之间数据交换仅限于单跳通信，不允许转播问候数据包。实际上，节点会保存Γi和τi的信息，该信息从来自其邻居节点的问候数据包中获取。例如，每个问候数据包包含发送节点nj的ID号，然后任何节点ni在nj的传输范围内能得到问候数据包，再后ni检查是否一个重复的数据包，如果是，则忽略该数据包，否则更新本地数据库。

待初始化阶段和处理阶段顺利完成之后，采用三边测量技术计算出节点位置。

值得一提，EDV-Hop算法不同于DV-Hop算法。DV-Hop算法在两个不同的阶段，广播锚节点位置坐标和邻居节点之间的平均跳距，采用超过必需的通信开销，增加通信时延。EDV-Hop算法广播锚节点位置坐标的同时估计节点之间的相应跳距，该算法是在一个阶段内完成。因此，EDV-Hop算法可显著地降低了网络通信和传输时延。

4 EDV-Hop算法评估

在网络设置相同的环境下，根据已定义好的度量指标，对EDV-Hop、DV-Hop算法进行比较。并且，仿真验证EDV-Hop算法采用不同锚节点部署方式对平均误差的影响。

4.1 评估度量定义

4.2 仿真实验

仿真实验中，假设200个节点按2维泊松分布部署在方形区域内，传输半径为10 m，方形区域A＝50×50 m2。本文通过改变部署节点数目，得到不同的节点密度和连通性。

在无线传感器网络中，这两种算法采用到锚节点的距离估计估计节点的位置。毫无疑问更精确的距离估计得到更好的位置估计。根据位置估计误差，图7显示位置估计精度。图5表明EDV-Hop算法在位置估计误差偏离实际位置r0范围内的节点比例超过90%。另外，超过70%的节点估计位置与实际位置的误差在r02范围内，而DV-Hop只有49%的节点能实现这样的功能。因此，EDV-Hop算法比DV-Hop算法具有更好的位置估计性能。

研究锚节点采用三角或方形部署对EDV-Hop算法的性能影响。在网络参数相同的条件下，采用不同的锚节点部署方式，分别研究其对平均误差的影响。改变节点在感兴趣区域内的数目，数目变化区间为100～400。在三角和方形部署的策略下，图6显示了平均误差范围。显然，当节点连通性增加，这两种部署方案的平均定位误差都减少了。这实际上是因为节点连通性越高，节点更能直接或者最短跳距到达锚节点，精确位置估计的节点就更多。另外，仿真结果表明，在同样的网络设置以及更少的锚节点条件下，三角锚节点部署的平均误差范围小于方形锚节点部署。因此，在无线传感器网络中本文推断锚节点的部署对定位系统来说同样是至关重要的，仿真结果表明：锚节点三角部署的网络比方形部署的网络定位性能更优。

图5 位置误差分布Fig.5 Distribution of position errors

5 结束语

图6 锚节点不同部署的平均误差Fig.6 Average error of anchor nodes in different deployment

无线传感器网络感知感兴趣的数据具有重要的意义，节点物理位置估计是极其重要的。本文提出基于免测距的EDV-Hop算法估算节点位置。根据精度和有效性的度量，EDV-Hop算法比DV-Hop具有更好的定位性能。并且，在锚节点稀少的条件下，EDV-Hop算法验证了锚节点三角部署的网络比方形部署的网络节点平均定位误差减少了10%左右。

［1］WONG S Y，LIM J G，RAO S，et al.Density-aware Hop-count localization in wireless sensor networks with variable density［C］//Proc.IEEE Wireless Comm.and Networking Conf.（WCNC 05），2005：1848-1853.

［2］XIAO Q J，XIAO B，CAO J N，et al.Multihop range-free localization in anisotropic wireless sensor networks：a pattern-driven scheme［J］.IEEE Transactions on mobile computing，2010，9（11）：1592-1607.

［3］ WANG C，LIU K，XIAO N.A range free localization algorithm based on restricted-area for wireless sensor networks［C］//ICCGI'08，2008：97-101.

［4］SUN YU R，MEI S L.APower-aware and range-free localization algorithm for sensor networks［C］//APCC'06，2006：1-5.

［5］ WANG X.Qos issues and qos constrained design of wireless sensor network［D］.Ph.D dissertation，Univ.of Cincinnati，2006：111.

［6］ WANG L，XIAO Y.A survey of energy-efficient scheduling mechanisms in sensor network［J］.Mobile Network Applications，2006，11（5）：723-740.

［7］WANG Y，WANG X，XIE B，et al.Intrusion detection in homogenous and heterogeneous wireless sensor networks［J］.IEEE Transactions on Mobile Computing，2008，7（6）：698-711.

［8］ NASIPURI A，LI K.A directionality based location discovery scheme for wireless sensor networks［C］//Proc.First ACM Int’l Workshop Wireless Sensor Networks andApplications，2002：105-111.

［9］ CAI SHAOBIN，LI XI，GAO ZHENGUO，et al.Modified improved alternating combination trilateration algorithm with a variable［C］//International Multisymposiums on Computer and Computational Sciences，2008：98-101.

［10］徐小卜，王勇，陶晓玲.基于支持向量机分类的WSN节点定位算法［J］.计算机工程，2010，36（24）：90-91.

［11］汤文亮，黄智水.无约束插值的Monte Carlo无线传感器网络节点定位方法［J］.传感器与微系统，2010，29（5）：54-55.

［12］谢昕，张恒，于忠平，等；基于能量与功率控制的TopDisc拓扑算法研究［J］.华东交通大学学报，2010，27（3）：58-61+87.

AResearch on Range-free LocalizationAlgorithm Based on EDV-Hop

Tang Wenliang，Chen Song，Zhou Jindong，Huang Zhishui
（School of Software，East China Jiaotong University，Nanchang 330013，China）

In order to improve node location accuracy in wireless sensor networks and reduce the cost，the paper puts forward a new Range-free Localization algorithm，EDV-Hop，to overcome the shortcomings of the APS.Local localization information extraction is realized by limiting the hopping number；the location accuracy is improved by adjusting the average distance per hop.In the condition that the nodes in the network are deployed randomly and the density of the nodes is arbitrary，the paper estimates the location of nodes，and measures it from both accuracy and effectiveness.The simulation results show that EDV-Hop algorithm has better positioning performance than DV-Hop，and that it can reduce the traffic among the nodes，reduce the communication cost and improve the location accuracy.

wireless sensor network；EDV-Hop；range-free localization algorithm；location accuracy；anchor node

TP393.3

A

1005-0523（2012）03-0040-06

2012-03-15

国家自然科学基金项目（61162001；31101081）；江西省科技工业支撑计划项目（2010BGA02200）

汤文亮（1969－），男，副教授，研究方向为WSN、信息安全。