An Improved DV-Hop Localization Algorithm Based on Threshold Mechanism and Correcting Distance for Wireless Sensor Networks*

XIANG Mantian，WANG Sheng，YANG Youhua（.SchoolofSoftware，NanchangUniversity，Nanchang33009，China；.SchoolofInformationEngineering，NanchangUniversity，Nanchang33003，China）



An Improved DV-Hop Localization Algorithm Based on Threshold Mechanism and Correcting Distance for Wireless Sensor Networks*

XIANG Mantian1*，WANG Sheng1，YANG Youhua2
（1.SchoolofSoftware，NanchangUniversity，Nanchang330029，China；2.SchoolofInformationEngineering，NanchangUniversity，Nanchang330031，China）

In the wireless sensor network DV-Hop localization algorithm，the location of unknown nodes only consid⁃ers the average hop distance from its nearest anchor node，which is used to multiply the number of hops to replace the real distance but thus，it will lead to large positioning errors.This paper proposes a high-accuracy localization al⁃gorithm TMCD-DV-Hop，which is a developed DV-Hop algorithm of relative high accuracy，based upon threshold mechanism and distance correction and the developed algorithm firstly calculates hop thresholds，and the effect of the other beacon nodes lying outside the nearest anchor node in the local range and global range is considered，thus，best corrected average hop distance has been chosen to estimate the distance，and an estimated coordinate is gained by centroid algorithm after the combinatorial optimization of anchor nodes within the single-hop communicative radi⁃us，meanwhile，another estimated coordinate is gained by weighted least-squares method.At last arithmetic mean of two estimated coordinates is considered as orientation coordinate for unknown nodes.Simulation experiment mani⁃fests that in the same network environment，developed TMCD-DV-Hop algorithm could better lower down position⁃ing errors than DV-Hop in the end the positioning accuracy is elevated.

wireless sensor network；DV-Hop algorithm；threshold mechanism；corrected average hop distance

无线传感器网络WSN（Wireless Sensor Net⁃work）是由大量的多功能，低功耗，低成本，能够感知外界特性的传感器节点组成［1］，这些节点随机部署或撒在监测区域内，它们之间通过无线通信的方式形成一个多跳自组织网络［2］。节点的定位技术是无线传感器网络应用中的关键技术之一［3］，根据在定位过程中是否需要测量节点间的距离，可将无线传感器网络定位算法分为测距（Range-based）定位算法和非测距（Range-free）定位算法［4］。在WSN中非测距定位算法备受关注，其中DV-Hop［5］定位算法因有简单、经济、高适用性和高效性等特点而得到了广泛应用，但其也有定位误差较大的不足，如在网络平均连通度为10，锚节点密度为10%时，其定位误差约为33%［6］。因此，本文将重点研究如何对DV-Hop算法进行改进，深入剖析DV-Hop算法定位过程中存在的不足，在不改变原始DV-Hop算法的基本框架和不增加额外硬件设备的前提下，提出了一种改进算法TMCD-DV-Hop，与原始的DV-Hop算法相比，TMCD-DV-Hop能有效地降低定位误差。

1　DV-Hop算法原理

DV-Hop定位算法是由Dragos Niculescu［5-6］等人根据全球定位系统GPS（Global Positioning System）定位思想和距离矢量路由机制提出的一种分布式非测距算法。DV-Hop算法受环境因素的影响小，也无需额外的测距设备，这些特点使DV-Hop算法适用于节点配置简单，成本低和规模大的无线传感器网络。DV-Hop算法所需的锚节点数量较少，采用多跳的方式进行定位，下面对DV-Hop算法进行简单描述。

1.1DV-Hop算法描述

DV-Hop定位算法主要分为以下三个阶段：

①计算跳数：锚节点通过洪泛（Flooding）方式广播自身的坐标信息，其中初始跳数为0，未知节点接收并记录到每个锚节点的最小跳数，同时忽略到同一锚节点其他跳数较大的路径，然后将跳数值加1，并转发给邻居节点。

②估算距离：设锚节点St的坐标为（xt，yt），它的邻居锚节点Sk（k=1，2，…，Nk）的坐标为（xk，yk），每个锚节点根据获得到的其它锚节点坐标和到它们的最小跳数，通过式（1）来计算锚节点平均跳距Hopsize。

其中：htk是锚节点St和Sk之间的最小跳数。

③未知节点定位：未知节点根据到3个或3个以上锚节点的距离，利用三边测量法或极大似然估计法计算自身坐标。

设未知节点X的坐标为（x，y），锚节点Sk（k=1，2，…，Nk）的坐标为（xk，yk），未知节点与锚节点间的距离为dk（k=1，2，…，Nk），则可得如下方程组：

把式（2）转化为线性方程组：

通过对式（3）转化，求出未知节点的坐标：

其中：

1.2DV-Hop算法误差分析

①在锚节点采用式（1）计算平均跳距时，利用的是除自身外的其他所有锚节点，这样得到的平均跳距能够反映全局范围内的节点平均密度情况，但不能反映本锚节点局部范围内的情况。因此，在密度均匀的各向同性网络中采用该方法得出的平均跳距与真实平均跳距间的误差较小，但在密度不均匀的各向异性网络中误差将较大。

②当未知节点到锚节点的跳数≥2时，误差将会累计［7］，因此导致DV-Hop算法的估算距离与真实距离间存在较大的误差，且误差的大小与跳数成正比。

③在未知节点的定位阶段，锚节点的迭代定位会使误差积累。因为下一轮可能会在前一轮定位误差的基础上引入新的误差而累计出更大误差，当网络规模较大时，累积误差将会导致极大的定位误差［8］。

1.3DV-Hop算法研究现状

针对原始的DV-Hop算法存在定位误差较大的问题，国内外许多研究学者提出了大量对DV-Hop算法的改进方法。文献［9］针对原始DV-Hop算法精度不高的问题，提出了一种ABDV-Hop（Artificial Bee Colony DV-Hop）算法，将鲁棒性强、收敛速度快且全局寻优性能优异的人工蜂群算法应用于DV-Hop算法中。文献［10］提出了一种基于簇内RSSI测距的改进DV-Hop定位算法，借助RSSI测距技术，该算法只校正一跳通信范围内的节点距离，而对于二至多跳不进行RSSI测距校正，这是由于RSSI受环境和障碍物等外界因素影响大，导致测距误差大，并且RSSI的发射和接收都会消耗较多的能量，缩短节点寿命。文献［11］提出了一种基于最小均方误差准则求平均跳距的DV-Hop改进算法，算法对不同的锚节点采用不同的跳距来计算到它们的距离，利用未知节点与锚节点的范围作为约束条件来优化求得的节点位置。文献［12］提出了一种基于跳数区域划分的DV-Hop改进算法，引入了RSSI测距技术和限跳机制，优化了参与定位锚节点组合，最后采用了多次三边测量法，用质心法确定未知节点的坐标。上述方法都能在一定的程度上减小原始DV-Hop算法的定位误差，但仍存在进一步提高定位精度的改进空间。

2　TMCD-DV-Hop算法原理

2.1TMCD-DV-Hop算法

TMCD-DV-Hop算法针对原始DV-Hop算法定位精度较低的不足做了改进，整个算法的流程如下所述：

①阈值取值设定

假设在L×L的定位区域中，未知节点Xi（i= 1，2，…，Ni），锚节点Sk（k=1，2，…，Nk）的坐标为（xk，yk），节点通信半径为R，跳数阈值V的取值与通信半径、锚节点密度密切相关，一般来说V由式（5）确定［13］。

其中：ρ是锚节点密度。为提高节点定位率和定位精度，V的取值通常要比理论值稍大一些，根据大量仿真实验结果表明，一般V的取值为2～5，即可达到理想的定位精度。

②平均跳距校正

在算法的距离估计阶段，本文提出了另一种方法。如图1所示，未知节点A不再使用最近锚节点B1的平均跳距来计算到各个锚节点的距离，而是每个锚节点的平均跳距都参与未知节点A的距离计算。当每个锚节点用式（1）算出平均跳距后，需要进一步校正。通过欧几里得公式算出所有锚节点之间的距离，用锚节点之间的距离减去估计距离得到估计距离的误差，然后除以总跳数得到单跳平均误差，其计算方法如式（6）所示。然后根据式（7）计算校正之后的平均跳距，再乘以跳数得到到各锚节点的距离。经过跳距校正之后，未知节点A的定位误差明显比原始算法的少。

则锚节点校正平均跳距为：

图1　DV-Hop算法理论模型

当节点随机分布在监测区域中，网络拓扑结构不规则，所以未知节点定位需要考虑全局与局部范围来校正平均跳距，选择出最优平均跳距以降低不同的网络密度对锚节点平均跳距的误差影响，使未知节点到锚节点的估计距离更加准确，从而提高定位精度。首先从全局范围来考虑，把所有相互通信的锚节点按跳数n（1≤n≤V）分类记录下来，计算出全局n跳的单跳平均跳距h¯n：

依据大量实验表明，当锚节点跳数n＞V，未知节点的定位从单个锚节点的局部范围来考虑，远比从全局范围来考虑时的定位误差小。把其他锚节点到未知节点按跳数n分类记录，利用式（8）计算出锚节点局部n跳的单跳平均跳距hn。

一般情况下，定位误差服从高斯分布，根据参数估计理论，作为估计子误差的代价函数，使用均方误差比使用方差或偏差更为合理［14］。即通过式（9）求得估计子误差的代价函数f1

综上所述，依据阈值V的取值，未知节点使用选择出的最佳合理平均跳距来计算到各个锚节点的距离比原始算法直接使用最近锚节点的平均跳距更为准确。计算方法如式（11）所示：

③未知节点定位

设未知节点Xi的坐标为（xui，yui），它到各个锚节点Sk（k=1，2，…，Nk）的距离为dik，其中dik是Xi利用式（11）计算得到的与锚节点Sk间的距离。

（a）用质心算法求未知节点的估计坐标

为了准确的定位出未知节点，它单跳内的锚节点比多跳引起的定位误差要小很多，当未知节点Xi单跳范围内的锚节点个数m≥3时，将这些锚节点随机组合成个三角形。每一个三角形都采用质心算法得到未知节点的一个估计坐标，然后对以这些估计坐标为顶点的多边形再用质心算法求出Xi的估计坐标Xc：

其中：（xt，yt）是第t个三角形质心的估计坐标。

（b）用加权最小二乘法求未知节点的估计坐标

为了使得定位准确，在定位阶段引入加权最小二乘法。根据到锚节点估计距离的不同，引入不同的加权系数，以提高定位精度。在实际应用中，加权系数Wk的取值与误差的协方差有关。理论证明，当加权矩阵W取测量误差方差阵的逆矩阵时可使估计误差的方差最小，但实际应用中加权矩阵W的定义有待进一步改善。通常情况下，当节点间的跳数较大时，估计距离的误差也较大，此时加权值应取小一些；当节点间的跳数较小时，估计距离的误差也较小，此时加权值应取大一些［8］。因此，为了减小定位误差，本文引入一个加权系数矩阵W：

图2　TMCD-DV-Hop算法流程图

最后未知节点Xi的定位坐标为：

TMCD-DV-Hop算法的整个流程如图2所示。

3　仿真结果及分析

为验证TMCD-DV-Hop算法的性能，在Matlab中对DV-Hop算法和TMCD-DV-Hop算法进行对比，并对实验数据进行具体分析，定位误差用节点通信半径归一化后的节点平均定位误差表示：

其中：N为未知节点的总数；（xi，yi）为未知节点的真实坐标；（x̂i，ŷi）为未知节点的估计坐标；R为节点的通信半径。

默认仿真参数为：在100 m×100 m的二维正方形平面内，随机分布150个节点，其中锚节点比例为10%，节点通信半径R=30 m。以下所有仿真实验，未特别说明时，参数默认取以上的值。为减小节点随机分布的影响，每种参数下默认将TMCDDV-Hop算法和DV-Hop算法各进行100次节点随机分布的仿真，然后再求定位误差的平均值。

3.1默认参数下的定位误差

在默认仿真参数下进行一次仿真，得到如图3的定位误差图。图中未知节点的实际位置和估计位置间用直线相连，直线的长短可以直观地表示定位误差的大小。图3（a）是DV-Hop算法的定位误差图，图3（b）是TMCD-DV-Hop算法的定位误差图。

图3　定义误差图

由图3可知，图3（b）中大部分节点的定位误差线要比图3（a）中的短，所以TMCD-DV-Hop算法中大部分节点的定位误差要比DV-Hop算法小。因为TMCD-DV-Hop算法加入了阈值机制与平均跳距校正过程，所以图3（b）中没有节点超出WSN边界。而DV-Hop算法在定位过程中，最近锚节点的平均跳距误差对定位结果影响很大，当未知节点利用离它跳数大于2的锚节点的平均跳距去估计到锚节点的距离时，带来的误差也就越大。所以图3（a）中节点定位误差很大，甚至有些节点定位越界。图3（a）中节点的平均定位误差为0.335，图3（b）中为0.243，TMCD-DVHop算法的定位误差较DV-Hop算法减小了27.5%。

3.2不同通信半径下定位结果的比较

在默认仿真参数下，其他参数不变，节点的通信半径从20 m到40 m，TMCD-DV-Hop算法和DVHop算法的定位误差如图4所示。从图中可以看到，随着通信半径的不断增大，TMCD-DV-Hop算法和DV-Hop算法的定位误差都在趋于减小，且TMCD-DV-Hop算法的定位误差始终比DV-Hop算法小。当通信半径R为20 m时，TMCD-DV-Hop算法的定位误差较DV-Hop算法减小了17.5%；R为30 m时，减小了15.2%；R为40 m时，减小了11.5%；定位精度的提高始终明显。主要原因是由于通信半径的增大，节点定位覆盖率增大，定位误差就会减小，不过由图可知，当通信半径继续增大时，定位精度的提高幅度有所减小，主要是通信半径的增大影响了跳数的计数，比如节点间单跳内最远通信范围与最近通信范围的估计距离值都一样，必然就会导致计算估计距离的误差增大，因此说明TMCD-DV-Hop算法更适合在通信半径适中的情况下进行定位。

图4　不同通信半径下的定位误差

3.3不同锚节点密度下定位结果的比较

在默认仿真参数下，其他参数不变，锚节点比例从8%增大到20%，TMCD-DV-Hop算法和DVHop算法的定位误差如图5所示。由图得知，随着锚节点比例的增大，TMCD-DV-Hop算法和DV-Hop算法的定位误差都在趋于减小，且TMCD-DV-Hop算法的定位误差始终比DV-Hop算法小。锚节点比例为8%时，TMCD-DV-Hop算法的定位误差较DVHop算法减小了11.4%；为14%时，减小了21.9%；为20%时，减小了23.8%，定位精度的提高始终明显。锚节点比例增大，单个锚节点对定位的影响就小，计算平均跳距带来的误差也就减小，同时单跳内锚节点也较多，定位也就更准确，但随着锚节点比例增大，定位成本也增大，当达到相同的定位精度时，TMCD-DV-Hop算法明显较DV-Hop算法所需锚节点比例少、成本低。

图5　不同锚节点密度下的定位误差

3.4不同节点个数下定位结果的比较

在默认仿真参数下，其他参数不变，总节点数从100增大到200，TMCD-DV-Hop算法和DV-Hop算法的定位误差如图6所示。由图得知，随着总节点数的增大，TMCD-DV-Hop算法和DV-Hop算法的定位误差都在减小，且TMCD-DV-Hop算法的定位误差始终比DV-Hop算法小。总节点数为100时，TMCD-DV-Hop算法的定位误差较DV-Hop算法减小了15.6%；为150时，减小了20.2%；为200时，减小了24.1%，定位精度的提高始终明显。随着节点个数的增加，节点通信半径内邻居节点数将增多，跳数计算将更准确，而且网络覆盖率也会增大，那么在计算距离时误差也将减小。在图6中，总节点数越多，定位精度提高的幅度越大，TMCD-DV-Hop算法越优于DV-Hop算法。

图6　不同总节点数下的定位误差

3.5归一化平均定位覆盖率结果的比较

为比较算法的性能，在仿真默认参数下，锚节点比例从8%增加到20%，TMCD-DV-Hop算法和DV-Hop算法的归一化平均定位覆盖率如图7所示。从图7可以看出，TMCD-DV-Hop算法和DVHop算法的定位覆盖率都会随着锚节点比例的增加而有所提高。TMCD-DV-Hop算法的覆盖效果优于DV-Hop算法，因为未知节点在进行定位之前，TMCD-DV-Hop算法根据阈值选择最优校正平均跳距来计算距离，降低了未知节点与锚节点之间估计距离的误差，因而可以避免节点间距离误差过大导致的节点无法定位情况的产生，同时还对参与定位的单跳通信半径内的锚节点进行组合优化后，采用质心算法得到一个估计坐标作为参考，因此大多数情况下，未知节点能够很好的定位，提高了算法的定位覆盖率。

图7　归一化平均定位覆盖率曲线图

4　总结

DV-Hop算法采用离未知节点最近锚节点的平均跳距乘以最小跳数估算距离，由于节点的通信路径大都是曲线，而真实距离是直线，因此用曲线估计距离代替直线真实距离会导致定位误差。同时DV-Hop算法计算距离不考虑局部与全局的适用性、不同区域节点密度的随机性和不均匀性，从而导致较大定位误差。TMCD-DV-Hop改进算法的优点在于：在不改变DV-Hop算法的总体框架下，在距离估计阶段和未知节点定位阶段进行改进：距离估计阶段，考虑最近锚节点之外的其他锚节点在局部范围和全局范围的影响，依据阈值选择最优的校正平均跳距来估计距离；未知节点定位阶段，对参与定位的单跳通信半径内锚节点组合进行优化，以质心法以及加权最小二乘法的两个估计坐标算术平均值作为未知节点的定位坐标。

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

［2］Jonathan B，Christopher T.Handbook of Sensor Networks［C］//Sto⁃jm Enovic II，ed.Proceedings of Localization in Sensor Networks. 2005：1-18.

［3］赵灵锴，洪志全.基于无线传感器网络的DV-Hop定位算法的改进［J］.计算机应用，2011，31（5）：1189-1192.

［4］He T，Huang C D，Blum B M，et al.Range-Free Localization Schemes in Large Scale Sensor Networks［C］//Proceedings of The 9th Annual International Conference on Mobile Computing and Networking.San Diego：ACM Press，2003：81-95.

［5］Niculescu D，Nath B.Dv Based Positioning in Ad Hoc Networks［J］.Telecommunication Systems，2003，22（1/2/3/4）：267-280.

［6］Niculescu D，Nath B.Ad Hoc Positioning System（APS）Using AOA［C］//Infocom 2003.22nd Annual Joint Conference of the IEEE Computer and Communications.San Francisco，USA，IEEE Societies，2003（3）：1734-1743.

［7］毛科技，赵小敏，何文秀，等.WSN中基于区域划分的半自动DV-Hop定位算法［J］.计算机科学，2012，39（3）：39-42.

［8］胡华鹏，胡方明，周惇，等.DV-Hop无线网络定位算法研究［J］.电子科技，2013，26（11）：7-9.

［9］李牧东，熊伟，梁青.基于人工蜂群改进算法的无线传感器网络定位算法［J］.传感技术学报，2013，26（2）：241-245.

［10］黄晨钟，许力，叶阿勇，等.基于簇内RSSI测距改进的DV-Hop算法［J］.福建师范大学学报（自然科学版），2010，26（6）：29-34.

［11］嵇玮玮，刘中.DV-Hop定位算法在随机传感器网络中的应用研究［J］.电子与信息学报，2008，30（4）：970-974.

［12］夏少波，邹建梅，朱晓丽，等.基于跳数区域划分的DV-Hop改进算法［J］.传感技术学报，2014，27（7）：964-969.

［13］于宁，万江文，吴银锋.无线传感器网络定位算法研究［J］.传感技术学报，2007，20（1）：187-192.

［14］张贤达.现代信号处理［M］.北京：清华大学出版社，2002：40-42.

向满天（1977-），男，湖北恩施人，博士。南昌大学副教授、硕士生导师、江西省条代码标准化技术委员会委员、南昌市标准化专家。先后主持多项重大课题，拥有授权发明专利3项，发表核心、SCI/EI论文30余篇。主要研究领域为无线传感器网络、物联网、短距离无线通信、嵌入式网络，sosmt@163.com；

王胜（1990-），男，江西吉安人，硕士研究生，主要研究领域为无线传感器网络、无线通信等，wspw8023@sina.com；

杨友华（1990-），男，江西抚州人，硕士研究生，主要研究领域为无线传感器网络、无线通信等，yyouhua627@163.com。

EEACC：723010.3969/j.issn.1004-1699.2016.06.022

基于阈值机制与距离校正的WSN改进DV-Hop定位算法*

向满天1*，王胜1，杨友华2
（1.南昌大学软件学院，南昌330029；2.南昌大学信息工程学院，南昌330031）

在无线传感器网络的DV-Hop定位算法中，未知节点定位只考虑离它最近的锚节点的平均跳距，用它乘以跳数代替真实距离去进行定位，会导致较大的定位误差。针对DV-Hop算法以上的不足，本文提出了一种精度较高的基于阈值机制与距离校正的DV-Hop改进算法TMCD-DV-Hop。改进算法首先计算跳数阈值，考虑最近锚节点之外的其他锚节点在局部范围和全局范围的影响，依据阈值选择最优的校正平均跳距来估计距离，并对参与定位的单跳通信半径内的锚节点进行组合优化后，采用质心算法得到一个估计坐标，同时利用加权最小二乘法得到另一个估计坐标，最后以两个估计坐标的算术平均值作为未知节点的定位坐标。仿真实验表明，在同等网络环境中，改进后的TMCD-DV-Hop算法较DV-Hop算法更能有效地降低定位误差，提高定位精度。

无线传感器网络；DV-Hop算法；阈值机制；校正平均跳距

TP393

A

1004-1699（2016）06-0920-07

2015-12-14修改日期：2016-02-02

项目来源：国家自然科学基金项目（61362022，61362008）；江西省科技计划项目（20142BBE50019）