一种基于可移动锚节点的DV-HOP改进定位算法

胡 淼，陶正苏

（上海交通大学 电子信息与电气工程学院，上海 200240）

无线传感器网络是将大量传感器随机布设到某一目标区域，以无线的方式进行通信，并将采集到的数据在全网中进行传输，以实现对目标区域的监测。传感器的位置信息对监测活动至关重要，没有位置信息的的监测消息往往是没有意义的，而且无线传感器网络中的许多路由协议和运用都是在位置信息已知的前提下设计的，因此传感器的定位是传感器网路的关键技术之一。

无线传感器网络定位技术有许多种，大致可以分为基于距离定位和距离无关定位两类。基于距离的定位主要是通过测量传感器节点之间的距离或角度实现对未知节点的定位，TOA、TDOA、RSSI和AOA等是常见的基于距离的定位算法，这类定位算法对收发节点间的时间性有严格要求，对硬件条件要求较高，但定位精度相对较高；距离无关定位利用网络内部连通性来实现对未知节点定位，质心算法、DV-Hop、Amorphous和APIT等是常见的距离无关算法。其中，DV-Hop算法具有易实现，对硬件要求低等特点。但是，锚节点分布不均的情况下，DV-Hop具有较大的定位误差，针对DV-Hop的这一缺陷，提出了一种基于可移动锚节点的DV-Hop定位算法，并通过仿真实验对两种算法性能进行比较。

1 DV-Hop算法及其改进

1.1 DV-Hop算法

Niculescu等人首次在文献中提出了DV-Hop定位算法，类似传统网络中的距离向量路由机制，DV-Hop定位过程可以分为3个步骤：

第1步，计算未知节点与每锚节点的最小跳数。

锚节点向邻居节点广播自身位置信息分组，其中包括跳数字段，初始化为0。接收节点只记录到每个锚节点最小跳数，并将跳数字段加1转发给邻居节点。由此，所有节点记录下到每个锚节点的最小跳数。

第2步，计算锚节点与信标节点的实际跳段距离。

每个锚节点根据第一步中其他锚节点的位置信息和相距跳数，利用公式（1）估算平均每条距离：

其中（xi，yi），（xj，yj）是锚节点 i， j的坐标，hj是锚节点 i与 j的之间的跳数。锚节点再将计算的每跳平均距离用带有生存字段的分组广播到全网中，未知节点只记录收到的第一个每条平均距离，并转发给邻居节点。未知节点根据记录的每跳平均距离以及第一步当中的跳数计算到每个锚节点之间的跳段距离。

第3步，未知节点根据到各个锚节点的跳段距离值，利用三边测量法或极大似然估计法计算未知节点的坐标。

当所有锚节点到未知节点P的距离d已知时，可按式（2）进行计算:

可由式（2）可得线性方程组：

对式（3）使用标准的最小均方误差估计方法可以得到节点的坐标为：

1.2 基于移动锚节点DV-Hop算法

DV-Hop是一种典型的与距离无关定位算法，其误差主要产生于利用锚节点计算出来的平均每跳距离来代替全局平均每跳距离，为减小误差就要求锚节点能够尽量均匀的分布在被测区域中，使锚节点平均每跳距离更接近全局平均每跳距离。针对这一特点，文献[4]提出了一种基于可规律移动锚节点定位算法RRDV-Hop，RRDV-Hop利用一个规律移动的锚节点近似的构建出N个均匀分布于网络的锚节点，提高了定位精度。文中参考文献[4]的思路，在假设所有的锚节点都有一定移动能力的基础上，提出了基于移动锚节点DV-Hop定位算法 MAN-DV Hop（Mobile Anchor Node-DV Hop）。

MAN-DV Hop设定所有的锚节点都具有一定的移动能力，在所有节点随机部署在监测区域后，锚节点会与通信范围内的其他锚节点产生一种虚拟力（virtual force），而锚节点会根据虚拟力的大小及方向计算出自身位置的修正值，并移动到相应位置，实现锚节点的重新部署，使所有的锚节点能够均匀的分布于整个网络当中。然后MAN-DV Hop根据锚节点的新位置计算平均每跳距离，再完成未知节点的定位。

1.3 锚节点间虚拟力模型

为了使锚节点更均匀的分布于整个监测区域，可假设相隔较近的锚节点间会产生一种虚拟力，使锚节点移动到合适位置，直到虚拟力弱化为0。在传感器网络中，节点见常构建的虚拟力模型主要有4种。第1种虚拟力定义：

式（4）中dij表示锚节点i和j之间的距离，rc为节点通信半径，当两个锚节点间的距离超过0.5rc时，锚节点间不在产生虚拟力。

参考电荷之间库伦力模型，可以得到第2种虚拟力定义：

式（5）中 Qi，Qj原本表示两个电荷所带的电量 i，j而在传感器网络中可用，节点的网络连通度来代替。

第3种虚拟力定义为：

式（6）中有两个距离阈值rth与Rth，dij表示两节点之间的距离，rth与Rth的变化将影响锚节点对监测区域的覆盖率。

第4种常见的虚拟力定义为：

式（7）中wA表示虚拟力的引力系数，wR表示虚拟力的斥力系数，利用wA，wR可调节锚节点重部署后的疏密度。文献[5]分析了4种模型中各个参数对网络覆盖率的影响，MAN-DV Hop可根据不同节点分布情况选定不同的虚拟力模型。

当锚节点受到通信范围内其他锚节点产生虚拟力后，由原位置（x0，y0）更新到新位置（xnew，ynew），转化模型为：

式（8）中，Maxstep是传感器节点的最大移动距离，Fxy是作用于传感器节点的虚拟力，Fx，Fy分别是虚拟力在X轴和Y轴方向上的分量，Fth是设定的虚拟力阈值，当两个锚节点间的虚拟力绝对值小于阈值时，锚节点不发生移动。

1.4 虚拟力模型的选定

文献[5]分析了4种虚拟力的参数对模型性能的影响，其中用来评定模型性能的指标包括：覆盖增加率，覆盖效率，平均移动距离。模型一结构简单，且锚节点间的虚拟力只是斥力。当节点的通信半径较小时，MAN DV-hop选取模型一作为锚节点间的作用力，改善锚节点分布过于密集时的情况。当锚节点通信半径较大时，模型一中虚拟力大小与通信半径成正比rc，锚节点间斥力过大，使计算的平均每跳距离偏离真实值。当传感器节点通信半径较大时，网络的平均每跳值Hopsize

式（9）中a，b为小于1的范围系数。由此，综合模型1、模型3、模型4MAN DV-hop构建虚拟力模型：

式（10）表明，当量锚节点间的距离时 dij∈（rth，Rth），MANDV Hop认为此时锚节点间的距离分布是合理的，此时锚节点间不产生虚拟力作用 。当锚节点间的距离dij∈（0，rth）∪（Rth，rc）时，MAN DV-Hop认为节点间的距离过短或者过长，节点间产生虚拟力作用，且dij∈（0，rth）虚拟力为斥力，dij∈（Rth，rc）时，虚拟力为引力。 式（10）中 k1表示斥力系数系数，k2表示引力系数，用来控制虚拟力作用的强弱。

1.5 边界条件

由于MAN-DV Hop设定锚节点具有一定的移动能力，并在虚拟力的作用下移动到新的位置。对于初始随机分布在监测区域边界的锚节点，经过移动后锚节点可能越过监测区域的边界或大部分通信范围不在监测区域内。式（8）中设定了锚节点的最大移动距离Maxstep，若锚节点初始位置是（xo，yo），MAN-DV Hop 需判断（xo±Maxstep，yo±Maxstep）是否处于监测区域内。MAN-DV Hop算法流程图如图1所示。

图1 MAN DV-Hop定位算法流程图Fig.1 Flow chart of MAN DV-Hop algorithm

2 仿真验证

2.1 参数设置与误差指标

为了验证MAN-DV Hop算法的性能，采用Matlab进行仿真实验。在仿真实验中，假设所有节点都随机分布在一个20 m×200 m的二维平面上，在该区域内随机放置200个节点，未知节点的通信半径为rc，锚节点携带GPS定位设备，因此锚节点的坐标位置是已知的，并且锚节点具有一定的移动能力。仿真通过计算未知节点的定位坐标与实际坐标之间的平均误差与节点通信半径的比值来评定定位精度的高低，节点平均定位误差率：

式（11）中，erri表示节点i的定位误差，un表示未知节点数量，rc表示节点的通信半径，Error值越大，表示定位误差越大，Error值越小，表示定位的精度越高。

2.2 算法仿真与分析

设定节点通信半径rc=30 m，Maxstep=10 m，锚节点数量为30，此时MAN-DV Hop选定虚拟力模型一 ，仿真实验中网络节点初始分布图如图2所示。

图2 节点分布图Fig.2 Node distribution chart

锚节点重部署后的分布图如图3所示。

图3 锚节点重构分布图Fig.3 Anchor node re-distribution chart

图中o表示未知节点，*表示锚节点。比较图2，图3可得锚节分布变化情况。通过计算，初始分布时的网络平均联通度为12.29，网络的邻居锚节点平均数目为1.775。当锚节重部署后，网络的平均连通度为12.5，网络的邻居锚节点平均数目为1.92。当锚节点通信半径rc=50 m时，虚拟力模型设定为二，k1-k2=10，Rth=0.8rc，rth=0.2rc初始分布时的网络平均联通度为29.93，网络的邻居锚节点平均数目为4.2。当锚节重部署后，网络的平均连通度为30.53，网络的邻居锚节点平均数目为4.585。结果表明传感器节点在经过网络初始随机部署后，锚节点发生移动重部署后，锚节点的分布情况趋于均匀。

设定节点通信半径rc由30 m变化到60 m，步长为5 m。Rth=0.8rc，rth=5 m，Maxstep=10 m，k1-k2=5 节点平均定位误差变化情况：

图4 平均定位误差对比图Fig.4 Average location error chart

设定通信半径rc=30 m，锚节点比例由10%变化到60%，步长为5%时，平均定位误差的变化情况：

图5 平均定位误差对比图Fig.5 Average location error chart

由图4，图5可知，在相同的网络条件下，MAN-DV Hop具有更高的定位精度。

3 结 论

文章在DV-Hop定位算法的基础上，设定锚节点具有一定的移动能力，通过构建锚节点间的虚拟力来使其移动，使锚节点更均匀的分布于整个网络，从而提高了DV-hop定位算法 的定位精度。仿真结果表明，相同条件下，随机分布的网络中，与DV-hop算法相比，MAN DV-hop算法降低了平均定位误差，并且定位精度更稳定。

[1]孙利民，李建中，陈渝，等.无线传感器网络[M].北京：清华大学出版社，2005.

[2]Niculescu D，Nath B.DV based positioning in Ad hoc networks[J].Telecommunication Systems，2003（22）：267-280.

[3]Bulusu N，Heidemann J，Estrin D.GPS-less low cost outdoor location for very small devices[J]. IEEE Personal Communications，2000，7（5）：28-34.

[4]李瑞雪，房至一，仪婷婷.基于可规律性移动锚节点和接收信号强度指示器的改进DV-Hop定位算法及其性能分析[J].吉林大学学报，2011，41（2）：435-441.LI Rui-xue，FANG Zhi-yi，YI Ting-ting.Improved DV-Hop localization algorithm based on regularly moving anchor（RMAN）and received signal strength indicator （RSSI）and its performance analysis[J].Journal of Jilin University，2011，41（2）：435-441.

[5]任孝平，蔡自兴，任清雄.四种虚拟力模型在传感器网络覆盖中的性能分析[J].信息与控制，2010，39（4）：441-445.REN Xiao-ping，CAI Zi-xing，REN Qing-xiong.Performance analysis four virtual force models used for coverage algorithm of wireless sensor networks[J].Information and Control，2010，39（4）：411-445.

[6]王雪，王晟，马俊杰.无线传感网络的虚拟力导向微粒群优化策略[J].电子学报，2007，35（11）：2038-2044.WANG Xue，WANG Sheng，MA Jun-jie.Dynamic sensor deployment strategy based on virtual forcev directed particle swarm optimization in wireless sensor networks[J].Acta Electronica Sinica，2007，35（11）：2038-2044.