无线传感器网络的DV—Hop定位算法改进

董静薇　杨光　刘洋　张天琦

摘要：针对传统DVHop算法存在定位精准度低这一缺陷，分析了影响传统DVHop算法定位精度的三点主要因素：锚节点分布密度、平均跳距误差、极大似然法扩大误差。从算法的平均跳距计算和节点坐标计算两个阶段入手，引入RSSI（Receive Signal Strength Indicator）技术对平均跳距计算过程进行优化处理，同时对未知节点坐标计算过程采用最小二乘法进行修正。仿真结果表明：改进后的算法在测距精度上比原始算法提高了约30%；在相对定位精度上提高了约35%。

关键词：DVHop；RSSI；最小二乘法

DOI：10.15938/j.jhust.2018.01.024

中图分类号： TP399

文献标志码： A

文章编号： 1007-2683（2018）01-0132-05

Abstract：As the problems of lower localization accuracy appeared in the traditional DVHop algorithm， the author analyzed three main factors that influence the localization accuracy of original DVHop algorithm which started from the calculation of the average jump distance in algorithm and the calculation of node coordinates. The author then proposed the calculation method of average jump distance based on the weighted correction of the RSSI（Receive Signal Strength Indicator） and the calculation method of unknown node coordinates based on the correction of the total least squares （TLS）. The simulation result shows that compared to the traditional DVHop algorithm， the accuracy of the improved algorithm increased by about 30% in distance measurement as well as rose approximately by 35% in relative localization precision.

Keywords：DVHop； RSSI； total least squares （TLS）

0引言

无线传感网络（Wireless Sensor Network）属于一种经传感器节点利用多跳模式自组建的网络，经过多年发展，不再局限在军事领域，还在环境、医疗等领域广泛应用[1]。无线传感网络中最关键技术就是节点的准确定位，没有精确的定位信息，无线传感器节点在监测到的相关环境的数据信息就没有意义[2]。现有的WSN定位技术根据是否测距可分为基于测距和无需测距技术[3]。需要测距的定位技术一般利用超声波等探测手段测量节点信息，定位准确度较高，同时对基础硬件标准苛刻，所以部署网络投入成本很高；无需测距的定位技术根据未知节点和锚节点的估算距离来计算位置，对传感器节点的硬件要求相对较低。考虑到网络部署的成本，算法功耗等因素，无需测距的定位算法更具有实际使用价值。

DVHop定位方法在WSN的节点定位中使用广泛，它是一种不用测距的定位方法，对硬件的要求低，环境影响小。在实际应用场景中，此运算方法的优势包括：耗能少、运算量低、环保、对硬件无严格要求等。但是DVHop算法因为本身的计算特点存在一些先天缺陷，而最主要缺陷是定位精度较低。例如当网络中的节点分布不均衡时，由于节点间距都使用同一平均跳距计算，此时的节点的平均距离与实际距离有很大的偏差，因此该算法的定位误差比较大。

Dragos Niculescu等学者归纳提出DVHop計算方法之后，后续国内外学者对这一方法定位准确率较低的问题做出了优化与改进。例如文[4]总结出一种新的加权算法，算法融合了环境因素的同时使用了许多锚节点的平均跳距。这一方法最大的问题是：对硬件要求苛刻、运算工作量过大。文[5]提出了通过人工方式部署网络的方法，使网络中的锚节点分布均衡来减小平均跳距误差。这种方法对人力的成本太高且适用场景窄。可以看出，许多的学者耗费了大量精力去分析、探究DVHop算法，同时总结出不少改进方法，但是想要达到理想的定位水平还有不小的差距，需不断的进行完善，进一步改进。

本文针对DVHop算法定位精度低这一缺陷，提出了对平均跳距引入RSSI加权优化和对未知节点坐标进行最小二乘法修正，改进原始DVHop算法中的两个定位过程。

1DVHop算法定位流程

DVHop定位步骤一般分三步：

1）获取锚节点与未知节点间的最小跳数。

首先锚节点通过洪泛的模式，向全网络中传递自己的信息，数据包含跳数J、坐标P。然后未知节点利用距离向量交换协议（distance vector routing），获取锚节点到自己的跳数信息。如果到锚节点有多个跳数时，未知节点只计算整个过程中最小的跳数h。未知节点获取最小跳数的过程如图1所示。

2.1定位误差分析

DVHop在定位的过程中，最为核心的问题是定位精度不够。研究DVHop定位流程之后，总结了导致定位精度存在偏差的主要几个来源：

1）算法的定位精度与锚节点的分布情况和分布密度密切相关：锚节点在监测区域部署越均衡，部署量愈多，其定位地准确度愈大。锚节点的部署情况对定位的影响情况如图3所示。在实际的网络环境中，节点的布置是飞机散播等方式随机分布，节点分布不会呈现规律性的等间距分布。另一方面，锚节点的相对硬件成本较高，在网络中的存在比例小。这种情况下，网络容易出现定位盲点区域，影响算法的定位精度。

2）在定位过程中，网络使用平均跳距估计值与最小跳数相乘来计算节点间的实际距离。由于网络节点的随机部署性，节点之间的实际跳距往往差距很大，如果获得的平均跳距Hopsize不理想，必然会导致计算的估计跳距与实际跳距误差增大。当节点在网络中进行多跳，又会因为平均跳距存在的误差导致计算出的定位距离与实际距离之间误差累积增大，从而影响后续的定位过程，定位存在较大的误差。

3）一般情况下，获取多个未知节点到锚节点的估测距离值之后，利用极大似然估计法等手段计算分析其他未知的節点坐标。但由于三边测量法对初始值相对敏感，测距误差对其影响很大。在极大似然估计法中，带有误差的坐标代入矩阵后，误差矩阵会严重影响所求矩阵也就是坐标定位的精确度。

2.2DVHop算法的改进方法

原始算法的定位过程受地形等外界环境因素的影响较小，但在某些具体的应用场景中，当节点分布不均衡时，实际跳距与平均跳距之间存在的误差很大。所以，为了增加DVHop计算方法的定位准确率，本文就DVHop计算方法存在的问题在两个方面展开了针对性的优化。

2.2.1RSSI平均跳距优化

本文根据信号接收强度RSSI测距原理[6]，在计算平均跳距时加入RSSI技术进行测距优化。当原算法中用RSSI测得的跳距转换为一个修正系数来修正计算出的每跳跳距。修正系数是RSSI测距长度与RSSI平均测距长度做比值计算得来的。优化后的跳距可以减小因网络中节点分布不均衡所带来的每跳的跳距误差。加入RSSI优化后的平均跳距计算方法如下：

1）改进算法在锚节点广播含有自身信息的数据包时向包中添加一个RSSI方法测得估计距离数据RSSI（n）。节点在接收到数据包后，将自身的RSSI数据与包中的RSSI（n）相加，同时将跳数Hops+1，然后重新修正数据包中的相关字段。当数据包进行了n跳到达一个节点后进行判断，如果当前跳数小于最小跳数字段时，将其刷新，反之丢弃。

2）当数据包进行了n跳到达一个锚节点时，先通过数据包中的相关字段计算出节点间的RSSI每跳跳距，然后使用式（5）计算RSSI平均估测距离。

RSSIavg=RSSI（1）+RSSI（2）+…+RSSI（n）n（5）

3）最后对平均跳距Hopsize进行优化，优化系数δi是以节点间每跳的RSSI估测距离与平均估测距离RSSIavg做比值，当数据包里的跳数是n的情况下，利用公式（6）计算出未知节点与锚节点的距离d。

2.2.2最小二乘法修正的坐标计算

在计算平均跳距过程中，尽管RSSI进行了优化，得到的平均跳距更精确，计算出的节点间距离值d更接近实际物理距离。但是计算出估测距离d与实际距离存在一定误差，由于极大似然估计法等计算方法对初始值敏感，如果直接使用估计距离对未知节点坐标进行求解，存在误差的初始值代入方程后会使定位误差进一步扩大，致使上一步的RSSI平均跳距优化工作失去意义。本文针对极大似然估计法存在的问题使用最小二乘法进行修正。

根据图6中的数据可以分析出3种算法的相对定位误差区别较大，改进后的算法在相对定位精度上优于原算法约35%，优于HDDVHop算法约23%，并且定位误差抖动小，算法的稳定性更好。

4结论

本文研究了传统的DVHop计算方法的定位步骤，对引起定位偏差的根源进行了分析和归纳，在计算平均跳距的步骤中引入RSSI技术对实际跳距进行修正；在计算未知节点坐标的步骤中针对极大似然估计法存在的误差累积使用最小二乘法进行修正。

并对比分析了原算法、HDDVHop算法与改进算法。通过仿真实验结果可以发现，根据本文对算法的两个步骤进行改进，改进后的DVHop算法在相对定位精度上优于原算法约35%，优于文献中的HDDVHop算法约23%。使算法更具有推广和使用价值。本文也存在一些不足：只考虑固定锚节点模型，没有引入移动节点定位的可能；定位算法只是在二维空间计算坐标节点。扩展到三维空间定位是DVHop定位算法未来的发展方向。

参 考 文 献：

[1]彭宇，王丹. 无线传感器网络定位技术综述[J]. 电子测量与仪器学报，2011，25（5）：389-390.

[2]李文辰，张雷. 无线传感器网络加权质心定位算法研究[J]. 计算机仿真，2013（2）：191-193.

[3]朱若茜，张礼勇. 无线传感器网络监测环境中的煤矿安全度评价[J]. 哈尔滨理工大学学报，2013（3）：32-35.

[4]Yu Hu，Xuemei Li. An Improvement of DVHop Localization Algorithm for Wireless Sensor Networks[J]. Telecommunication Systems，2013，53（1）：13-18.

[5]Shrawan Kumar，D. K. Lobiyal. An Advanced DVHop Localization Algorithm for Wireless Sensor Networks[J]. Wireless Personal Communications，2013，71（2）：1365-1385.

[6]GOLDONI E，SAVIOLI A，RISI M. Lobiyal，et al. Experimental Analysis of RSSIbased Indoor Localization with IEEE 802.15.4[C]// 2010 European Wireless Conference，2010：71-77.

[7]石欣，印爱民. 基于RSSI的多维标度室内定位算法[J]. 仪器仪表学报，2014（2）：262-265.

[8]狄振强，马淑丽. DVHop算法中未知节点获取校正值的改进方法[J]. 通信技术，2016（3）：329-332.

（编辑：关毅）