基于OMNeT++平台的DV-Hop 定位算法改进

刘 排，武 一，南京娅，刘建民

(1.河北工业大学 信息工程学院，天津300401;2.天津现代职业技术学院 机电工程学院，天津300350)

0 引 言

无线传感器网络(WSNs)中，位置信息对无线传感网络的监控活动至关重要，事件发生的位置是无线传感器节点监控消息中所包含的重要信息，没有位置信息的监控消息往往毫无意义。因此，确定事件发生的位置对无线传感网络应用的有效性起着关键作用［1］。

根据定位机制可将现有无线传感器网络自身定位算法分为基于测距的和无需测距的定位算法两类。无需测距的算法不需要节点自身的测距设备，通过跳数或是其他信息估计自身到选定的信标节点的距离值。由于是估计得到的数值，相对于基于测距的算法获得的距离值误差偏大。常用的定位算法有质心法、凸规划、DV-Hop 算法、Amorphous算法、MDS-MAP 和APIT 算法等，DV-Hop 算法因凭借其定位过程实现简单，对节点硬件要求不高，在各向同性的网络中性能良好等优势，成为了目前应用最广泛的算法之一。

但是DV-Hop 算法的未知节点依靠测量与邻近信标节点之间的距离来推算自身位置产生的误差较大，为此，本文提出了通过定位出离信标节点距离较近的未知节点升级为信标节点的方法来减小定位中的误差，并且采用自由搜索算法取代误差较大的三边测量法来计算未知节点坐标，并在仿真平台OMNET++上验证。

1 DV-Hop 算法过程

传统的DV-Hop 算法的实现过程大致分为三步骤:

1)网络中的各个节点采用典型的距离矢量交换协议，信标节点发起第一次泛洪广播，广播的信息包括自己的ID，坐标信息和初始跳数。直到网络中的所有节点都获得信标节点的广播信息。

2)当信标节点获得其他信标的位置和相隔跳数后，信标节点利用下面公式来计算平均毎跳距离

式中 (xiyi)为信标节点的坐标，hi为信标节点i 与j(j≠i)之间的跳段数。信标节点发起第二次泛洪广播，将计算出的平均跳距广播到网络中，未知节点利用接收到的平均跳数值和第一阶段中得到的距各个锚节点跳数来近似计算到各个参考节点之间的距离［2］。

3)当未知节点获得距离锚节点的估算距离后，利用三边测量法或极大似然法来估计节点的二维坐标值，实现节点的定位［3］。

2 DV-Hop 算法的改进

DV-Hop 算法在计算未知节点与信标节点的距离时，使用折线距离代替直线距离，这样就会导致在拓扑结构不均匀的传感网络中定位误差很大［4］。在对未知节点的坐标进行估算时，通常用的三边测量法和极大似然法也存在极大误差。针对DV-Hop 算法的以上不足，本文提出了以下的改进方法。

2.1 基于RSSI 测距增加信标节点的改进方法

大量实验表明:定位误差较大的未知节点通常是那些远离信标节点的节点，增加信标节点的数目是最直接而有效的方法，但信标节点价格昂贵，能耗大，这种方法并不可取。因此，本文提出了基于RSSI 测距增加信标节点的改进方法。首先让所有信标节点利用可控范洪进行广播，信标节点发出的消息后只经过一跳，就将消息删掉不再转发，利用RSSI 测距的方法，计算出信标节点与未知节点的距离，如果有未接节点接知到三个及以上信标节点发来的消息，便可用三边测量法确定出此未知节点的位置［5］，确定出位置的未知节点便可升级为信标节点。

如图1 中，其中，●代表信标节点模块，○代表未知节点模块，A，B，C，D，E 节点都接收到了三个临近信标节点的消息，利用RSSI 测距的方法分别计算出与信标节点的距离，考虑到增加信标节点在进行泛洪广播的能耗会增加，所以，当增加信标节点时要进行选择，图中A，B 节点都接收到了信标节点2 发来的消息，所以，A，B 只将其中一个升级为信标节点即可，再利用三边测量法，计算出未知节点的坐标，这些计算出坐标的节点便可升级为信标节点。这样可在不增加额外硬件的基础上，便可增加定位的精度。

2.2 基于加权的自由搜索

图1 传感器网络节点分布图Fig 1 Distribution of WSNs node

自由搜索(free search，FS)算法是一种吸收了GA，ACO算法，PSO 算法等算法的优势的新型智能优化算法，FS 算法具有较快的全局收敛性和较强的自适应性能力，在解决DV-Hop 算法定位的优化问题显示出了优势。在FS 算法模型中，一个种群包含有m 个个体，m 个个体在半径为R 的搜索空间内移动，每个个体的移动包括全局内的搜索和局部范围内的搜索［6］，一次迭代个体移动一个搜索步，每个搜索步包含T 小步，个体对搜索步内找到的较优解进行记录，称为标记信息素，其大小与目标函数的适应度呈正比，每完成一次迭代，信息素将会被完全更新。个体的搜索本质上是一种标记信息素的过程，这些信息素将做为所有个体在下一次搜索开始时，选择起始点的依据之一，另一个依据则是个体的灵敏度［7］。当个体的灵敏度小于信息素时，个体受其影响改变搜索起点，选择搜索步T 中的最佳位置做为下一次搜索的起点;否则，个体不改变搜索起点，仍使用上一次迭代的搜索起点。

1)初始化

需要初始化的变量有:种群包含的个体m，空间维数d，搜索步中的搜索小步数T，搜索半径R，搜索空间的范围［Vmin，Vmax］，最大迭代次数Gmax。m 个个体被随机分散到搜索空间内

式中 rand(0～1) 为0～1 之间的随机实数。

2)搜索过程

所有个体在一个搜索步内行走T 小步，搜索到T 个新的位置。搜索过程中，目标函数的适应度记作

式中 fk为个体k 搜索到的T 个新位置中，对应的目标函数最佳值。信息素的定义如下

式中 min(fk)为所有个体中找到的最佳适应值。灵敏度的定义如下

式中 Smax为Smin灵敏度的最大和最小值，Pmax和Pmin为信息素的最大和最小值，并规定Smax=Pmax，Smin=Pmin;一个搜索步完成后，确定下一个搜索步，即下一次迭代的起始点

式中 Xhk为个体k 在搜索步T 内搜索到的最佳位置。

3)终止判断

FS 算法的判断标准有三种:

a.达到全局最优解:fmin＜fopt

b.当前迭代数g 大于最大迭代次数Gmax:g ＞Gmax

c.上述条件满足其中之一即可。

目标函数的获得:

由未知节点到信标节点的距离可得

其中xi，yi分别信标节点i 的x，y 坐标，di为未知节点到信标节点i 的距离。由上式可得

目标函数为

其中，wi为权值，n 为信标节点的个数。

3 仿真结果与分析

为了验证改进算法的有效性，采用OMNeT++进行仿真，仿真结果导入到Matlab 中进行提取和分析。仿真面积是400m×400 m 的正方形区域，节点间的通信半径为100 m，未知节点和信标节点在仿真区域内随机分布，平均误差作为评定定位精度的标准，其公式如下

自由搜索算法的参数设定:种群包含的个体数量m=60，最大迭代次数Gmax=600，搜索小步总数T=60，搜索半径R=0.1 m，x，y 坐标的搜索范围均为0～400 m。

3.1 算法稳定性能仿真结果

为了得到更加合理、接近于实际的仿真数据，对100 个传感器节点其中信标节点比例为5%的定位进行仿真22 次。

从图2 可得出，传统的DV-Hop 算法在仿真次数小于10 次时，误差的波动较大，在仿真次数大于10 次后，虽相对稳定但也有小幅度的波动。而改进的DV-Hop 算法则一直处在比较稳定的状态。经仿真数据计算可得，传统的DV-Hop 算法的均方差为4.36，改进后的均方差为1.35。改进后的节点的定位在稳定性能上要优于原始的DV-Hop算法。

图2 仿真次数对定位精度的影响Fig 2 Effect of simulation numbers on positioning precision

3.2 算法在精度上的仿真结果

为了验证改进后算法在精度上的提高，对100 个传感器节点进行仿真，传统的DV-Hop 算法与改进后的DV-Hop算法误差对比图如图3 所示。

图3 不同信标比例下的定位误差Fig 3 Localization error of different beacon ratio

从上图得出，无论上传统的DV-Hop 算法还是改进的DV-Hop 算法在整体上都是随着信标比例的增大，误差会越来越小。传统DV-Hop 算法在信标比例大于15%后，误差减小的幅度越来越小。改进后的DV-Hop 算法在误差会随着信标比例的增多而平稳下降，且在信标比例较小时，改进的DV-Hop 算法的优势表现的更加明显。

图4 节点个数对定位精度的影响Fig 4 Effect of node numbers on localization precision

由图4 可得，相较于传统的DV-Hop 算法，改进的算法在不同节点数目下的平均误差都普遍减小。其中在节点个数为240 时，改进后的DV-Hop 算法在精度上提高了15.3%，说明了改进后的DV-Hop 算法在提高算法精度上有了很大提高。

4 结 论

针对传统的DV-Hop 算法定位精度较低、算法稳定不高的缺点，本文提出了用RSSI 测距增加信标的改进方法，在不增加节点能耗的基础上，提高了算法的精度，并且用自由搜索算法取代了原来误差较大的三边测量法，自由搜索算法具有较快的全局收敛性和较强的自适应性能力，恰好符合了DV-Hop 算法的定位要求，仿真结果表明:改进后的定位算法在定位稳定性上有了明显的提高，相较于传统的DV-Hop 算法，改进的DV-Hop 算法性能稳定，其定位误差率减小了13.5%左右。

［1］ 方光伟.基于OMNeT+ +平台Gossiping 协议的仿真实现［J］.科技信息，2010(22):208－209.

［2］ 王福豹，史 龙，任丰原.无线传感器网络中的自身定位系统和算法［J］.软件学报，2005，16(5):857－868.

［3］ 杨石磊，樊晓平，刘少强，等.一种改进的无线传感器网络DV-Hop 定位算法［J］.计算机测量与控制，2008，16(9):1356－1358.

［4］ 刘 杰，董淑福，温 东，等.基于移动信标的改进DV-Hop算法［J］.传感器与微系统，2013，32(5):142－145.

［5］ Penev K，Littlefair G.Free search—A comparative analysis［J］.Information Sciences，2005，172(1/2):173－193.

［6］ 周 晖.自由搜索算法及其在传感器网络中的应用［D］.上海:东华大学，2010.

［7］ Pottie G J，Kaiser W J.Wireless integrated sensor networks［J］.Communications of the ACM，2000，43(5):51－58.