无线传感器网络质心和DV-Hop混合定位算法研究

张 悦，梁建国，张 浩，花 嵘，冯鲁彬

(山东科技大学计算机科学与工程学院，山东青岛 266590)

0 引言

物联网技术使互联网领域得到充分扩展，改变了人类社会的生活方式[1]，而在物联网中最重要的组成部分是无线传感器网络(wireless sensor networks，WSN)。节点定位技术是无线传感器网络的重要技术支撑，对无线传感器网络应用的有效性起着至关重要的作用[2]。目前无线传感器网络节点定位分为基于测距定位和无需测距定位[3]。基于测距的定位精度比较高，但是对于硬件依赖性较高，不适用于功耗和成本较低的无线传感器网络应用领域[4-5]。无需测距的定位虽定位精度比较低，但是对于节点的硬件要求不高，可以满足大多数无线传感器网络的定位需求[6]，目前此定位方法更受大家青睐。无需测距的定位算法有质心定位算法[7]、DV-Hop定位算法[8]等。质心定位算法和DV-Hop定位算法在定位过程中完全依靠网络连通度来实现节点定位，无需外界任何硬件手段[9-11]。然而，这两种算法定位精确度与锚节点的个数、节点通信半径以及节点总数等有非常大的关系。质心定位算法在锚节点分布密度较高的情况下定位性能较高，在锚节点分布密度较低的情况下，其定位效果比较差，而对于DV-Hop定位算法而言，在稀疏的锚节点个数下仍能对节点进行定位，但其定位效果却不理想[12-15]。

综上所述，本文针对质心定位算法和DV-Hop定位算法在定位性能上存在问题，从3个方面对其进行了改进。在质心定位算法和DV-Hop定位算法实现有机结合、优势互补的基础上，提出了一种质心和DV-Hop混合定位算法(mixed centroid and DV-Hop algorithm，MCDA)，以提高定位的性能。

1 技术思路

本文通过引入TTL值设定限定锚节点广播数据包的范围、提高邻居锚节点的比例以及改进质心定位算法3方面对定位性能进行改进。

1.1 引入TTL值以改进DV-Hop定位算法通信开销大的问题

DV-Hop定位算法由2次泛洪组成，第1次泛洪中节点获得锚节点的位置信息和距离锚节点的最小跳数，在第2次泛洪中将跳数信息转换为距离信息(数据包结构如图1所示)。

(a)第1次泛洪

(b)第2次泛洪图1 DV-Hop定位算法2次泛洪的数据包结构

在无线传感器网络中，未知节点和锚节点随机分布，且数量较大，因此在广播数据包和节点传递过程中，很难避免发生数据包的冲突或碰撞[16]。如若冲突发生，不仅会导致信息的缺失，从而使得节点间的最小跳数产生偏差，进而影响正常的节点定位；还会导致数据包的重传，使网络开销增大，进而拖延整个定位过程，导致网络能量消耗过多[17-18]。

因此，需要找到一种有效的方法，在一定程度上减少节点间的传播跳数，从而减小定位误差，并降低网络的整体开销，以达到节约能量的目的。

本文通过为数据包设置一个TTL生存周期域来减少通信量(改进的数据包格式如图2所示)。

(a)第1次泛洪

(b)第2次泛洪图2 改进后2次泛洪的数据包结构

基于TTL值的设定，可以控制广播包仅在TTL值规定的范围内进行数据传输，避免了泛洪数据包过程中的冲突或碰撞，降低数据传输失误的概率以及数据包重传造成的网络负担。还可以降低定位过程中基础性问题出错的概率，缓解网络高速超负荷数据包分组转发的压力，使网络的整体开销较小，能量分配更加有效。

1.2 提高邻居锚节点的比例以解决质心定位算法中锚节点少定位率低的问题

在质心定位算法中，若周围没有锚节点，未知节点将无法实现定位。本文通过提高未知节点中邻居锚节点的比例来提高节点的定位率。

在质心定位算法中，未知节点只把节点通信范围内的锚节点作为邻居节点，通过邻居锚节点所围成多边形的质心定位为自己的坐标。但在实验过程中发现，有些节点虽然不在未知节点的通信范围之内，但它还是可以作为邻居锚节点(如图3所示)，锚节点B在节点通信半径r内被视作邻居锚节点，但锚节点C不在通信范围内，故不能视作邻居锚节点，实际上锚节点C与锚节点B间的距离相差很小，在一定程度上可以升级为未知节点C的邻居锚节点。

改进具体实现为：在原来的质心定位算法中只用1跳范围内的锚节点进行定位，现将节点通信范围扩大到2跳范围，使用2跳范围内的锚节点定位。

(a)邻居锚节点

(b)锚节点

1.3 减小定位误差

扩大通信范围在很大程度上可以提高邻居锚节点的比例，但其定位误差也会随之增大，因此，需要改进质心定位算法以减小定位误差，具体改进步骤如下。

步骤1：在用上述方法找到未知节点邻居锚节点的基础上，对邻居锚节点进一步选择，判断1跳范围内是否存在锚节点，若存在则选择1跳范围内的邻居锚节点进行定位，否则选择大于1跳小于2跳范围内的邻居锚节点。选定后，对其范围内的锚节点进一步取舍，首先用DV-Hop定位算法计算得出锚节点每跳的平均距离，锚节点每跳的平均距离再乘以未知节点到锚节点的跳数作为未知节点到锚节点的距离，判断该距离是否在1.5倍通信范围内，如果在其范围内，则升级为锚节点，否则抛弃。

(1)

式中：n是锚节点的总数；(xi,yi)、(xj,yj)分别为锚节点i和j的坐标；hij是锚节点i和j之间的跳数。

如图3所示，未知节点A的邻居锚节点有B、C、D、E，由于1跳范围内有锚节点B、C、D，则选择它们进行定位，锚节点E将被抛弃，若A在1跳范围内无锚节点，则判断锚节点E是否在1.5倍通信范围内，若在其范围内则选择，否则抛弃。

步骤2：用传统质心定位算法对未知节点定位。

步骤3：在以上2步的基础上，进行节点的定位计算，在图4中，U、U′分别为未知节点和传统质心定位算法估算出的U的位置，A、B、C、D、E、F为未知节点U的邻居锚节点。首先分别计算每个邻居锚节点到U′的距离；其次根据计算的距离为每个邻居锚节点赋予不同的权重，使距离U′远的邻居锚节点获得较小的权重，较近的邻居锚节点获得较大的权重；最后重新计算未知节点U的坐标，经过多次迭代，使未知节点U的坐标更加准确。

图4 改进质心定位算法示意图

计算锚节点与其他锚节点的距离的公式为

(2)

式中：dk为锚节点与其他锚节点的距离；(xi,yi)、(xk,yk)为锚节点的坐标。

计算权重系数的公式为

(3)

式中：ρk为权重系数；d0为一个很小可以忽略不计的值。

计算未知节点U坐标(x,y)的公式：

(4)

式中：(x,y)为重新计算未知节点U的坐标；ρk为权重系数。

2 质心和DV-Hop混合定位算法的提出

综合上述内容，本文提出了一种质心和DV-Hop混合定位算法，即MCDA定位算法。

MCDA定位算法分为4个阶段：

(1)未知节点计算与每个锚节点的最小跳数与DV-Hop定位算法类似，不同的是在锚节点的广播数据包中包含了TTL值来限定广播包传输的跳数；

(2)计算每个锚节点每跳的平均距离，公式如下

(5)

式中：ci为计算所得每个锚节点每跳的平均距离；Dij为锚节点i和j之间的距离；hij为锚节点i和j之间的跳数。

(3)选择2跳范围内的锚节点作为未知节点的邻居锚节点；

(4)利用改进质心定位算法计算未知节点位置。

3 仿真实验及分析

为了能够更客观、准确地模拟出MCDA定位算法的真实性能，在MATLAB平台实验仿真时，所有节点包括锚节点和未知节点均在网络区域中随机生成。仿真参数的设置如表1所示。

表1 仿真参数设置

由表1可知，所有数据的产生都是对网络运行仿真100次求得结果的平均值。MCDA定位算法中生存周期TTL值为15，即限制锚节点数据包仅传播15跳，定位性能仿真过程中，使用平均定位误差和定位率作为定位算法定位性能的衡量指标。

图5为WSN网络的拓扑结构图，网络区域范围是100 m×100 m，网络中所有节点随机分布，圆圈表示未知节点，星型表示锚节点。

图5 WSN网络的拓扑结构图

3.1 锚节点个数对定位性能的影响

图6为锚节点数量从3变化到30时，质心定位算法、DV-Hop定位算法以及本文提出的MCDA定位算法定位性能的变化图，选择锚节点总个数为100个，节点通信半径为25 m。当节点总数与节点通信半径不变时，3种定位算法平均定位误差都随着锚节点数量的增加而减小，当锚节点的数量增加到15以上时，3种定位算法的平均定位误差变化较小。在锚节点数量从3变化到10时，MCDA定位算法平均定位误差比DV-Hop定位算法平均定位误差低，同时比质心定位算法平均定位误差高，但是当锚节点数量从10逐渐开始增加后，MCDA定位算法的定位误差变得最低，而且它的定位率比质心定位算法高，但比DV-Hop定位算法的定位率低。

图6 不同锚节点数下的平均定位误差对比

图7为锚节点数量为从3变化到30，节点通信半径分别为20，25，30时，本文提出的MCDA定位算法定位性能的变化图。可以看出，随着锚节点的增加，MCDA定位算法定位误差不断减小，定位率不断增加；但随着节点通信半径的增加，其定位误差不断增加，其定位率也在变大，这一特性与质心定位算法相似。

3.2 节点通信半径对定位性能的影响

图8(a)、图8(b)和图8(c)给出了节点通信半径从20变化到40，锚节点数分别为5、10和20时，3种算法定位性能的比较。

图7 不同锚节点下MCDA算法的定位性能比较

(a)锚节点数为5

(b)锚节点数为10

(c)锚节点数为20图8 不同节点通信半径下定位性能比较

由图8可知，当DV-Hop定位算法在锚节点数量为5，定位误差非常大，MCDA定位算法定位误差较小，MCDA的平均定位误差与DV-Hop相比降低了53.7%，质心定位算法误差最小，但MCDA的定位率也比质心定位算法要高；当锚节点数量变为10和20，DV-Hop定位算法的定位误差迅速减小，质心定位算法和MCDA定位算法有所下降，下降幅度不大；随节点通信半径的增加，DV-Hop定位算法的定位误差先减小后增加，质心定位算法和MCDA定位算法的定位误差均持续递增；当节点数变为10和20时，MCDA的平均定位率比质心定位算法提高了28.5%和14.2%。MCDA定位率趋近于1的速度比质心定位算法快，当两者定位率都达到1时，前者定位误差要比后者小，说明改进的质心定位算法获得了一定效果。

综上所述，MCDA定位算法在锚节点数量较低时，其定位误差比质心定位算法高，比DV-Hop定位算法的定位误差低，但其定位率要高于质心定位算法，且低于DV-Hop定位算法的定位率。

4 结论

本文在分析质心定位算法和DV-Hop定位算法的基础上，从3个方面进行改进：首先通过引入TTL值设定限定锚节点广播数据包的范围以减小DV-Hop定位算法通信开销的问题；其次提高邻居锚节点的比例改进了质心定位算法锚节点低时定位率低的问题；最后改进质心定位算法减小了定位误差，进而提出了MCDA定位算法。仿真结果表明，MCDA定位算法在无需额外增加硬件设施开销的条件下，较好地解决了在锚节点较低的情况下质心定位算法定位误差小但定位率低以及DV-Hop定位算法定位率高但定位误差大的问题。尽管MCDA定位算法与其他两种算法相比在减少定位误差和提高定位率方面取得了一定的效果，但随着锚节点数量的增加，仍需研究如何提高定位率的同时并减少定位误差。