无线传感器网络DV-Hop定位算法

丛珊，陈桂芬

（长春理工大学 电子信息工程学院，长春 130022）

无线传感器网络是目前国际上备受关注的研究领域，微机电系统、无线通信和嵌入式技术的进步推动了无线传感器网络的发展，无线传感器具有十分广阔的应用前景［1］。无线传感器网络是由大量传感器节点以自组织和多跳的方式构成的无线网络［2］，其目的是将感知、采集和处理的数据和信息传送给监控中心或终端用户，实现“人与物”之间、“物与物”之间的通信。在军事领域，无线传感器网络在战场监视、国土安全、战场侦察、目标定位、目标跟踪等方面起到很重要的作用。近年来，已经由最初的军事应用发展到民用领域，例如环境监测、工业控制、医疗健康、智能家居、科学探索和公共安全等方面，使人们可以即时地得到有效的消息，从而提高了人民的生活质量。其中，定位技术是无线传感器网络许多应用中的基础技术。节点定位是根据少数位置已知的节点通过定位算法确定位置未知的节点信息，在无线传感器网络中建立起节点之间相互关联的定位机制［3］。目前，最有名在无线传感器网络中应用得比较广泛的是GPS（全球定位系统），虽然它能够获得很高的位置精度，但是不适合使用在大规模的传感器节点中。首先，一个GPS接收器至少需要三个卫星确定目标位置，这在很多情况下是不可能的，例如室内和地下。第二，在计算环境中，小型的传感器节点对于大型昂贵的GPS接收机是不适合的。最后，传感器节点一般会部署在环境比较恶劣，或者人类无法到达的地区，电池无法更换，GPS接收机消耗了太多了的能量，大量的用在传感器节点上能耗太大。所以，GPS不符合无线传感器网络的要求，如果传感器带有GPS，价格昂贵，会导致资源浪费。所以，利用传感器节点进行定位在很多实际应用中是很重要的，提出一种花费少，能耗低同时定位精度高的定位算法是很有实际意义的。定位技术有很多中不同的分类方法，目前，应用较多的分类方法是基于测距（range-based）与无需测距（range-free）的定位算法［4］，其中，基于测距的定位技术需要测量节点之间的距离［5］，虽然定位精度高，但是其对硬件的依赖性大，功耗大。考虑到能耗和花费的原因，人们对无需测距定位算法的关注度更高。因为无需测距定位算法主要依靠网络的连通性进行定位［6］，花费低，易实现，而且可以满足大多数应用对精度的要求。在无需测距的定位算法中，DV-Hop算法应用得比较广泛。

1 DV-Hop定位算法

美国学者Dragos Niculescu和Bsdri Nath等人基于距离矢量路由和GPS原理设计了一系列分布式定位算法，统称为APS［7］，其中包括DV-distance算法、DV-Bearing算法、DV-Radial算法、DV-Hop算法、Euclidean算法和DV-coordinate算法。在这六种算法里面，DV-Hop定位算法应用的比较广泛，其原理与距离矢量路由算法比较相似。DV-Hop算法的主要思想是用未知节点到锚节点的最小跳数乘以距离未知节点最近的锚节点的平均每跳距离，之后计算未知节点与锚节点的距离，进而计算未知节点的位置，主要分为以下三个阶段：

第一阶段：节点获得与锚节点的最小跳数［8］。锚节点以泛洪方式向网络中广播数据包，信息包括锚节点的ID、位置信息和一个初始值为0的跳数值，格式如。锚节点的信息包数据会被接收节点接收并且记录，之后把跳数加1再传递给下一个节点，在信息传递的整个过程里，节点或许会多次接收到同一个锚节点的数据包，节点对同一个锚节点数据信息的跳数信息进行比较，具有最小跳数的值的信息包被筛选并记录下来，然后丢掉具有较大跳数值的信息包。

第二阶段：计算锚节点与未知节点的距离［9］。当每个锚节点都知道与网络中除该节点之外的其余锚节点的最小跳数信息后，用式（1）计算其平均每跳距离：

式中，HopSizei表示锚节点i的平均跳距，坐标(xi,yi)，(xj,yj)分别表示锚节点i与锚节点j的坐标，hij为节点i与节点j之间的最小跳数。

每个锚节点的平均每跳距离被计算出来之后，锚节点把自己的平均每跳距离向整个网络传播，未知节点接收锚节点的平均每跳距离，并且保留距离它最近的锚节点的平均每跳距离，用该平均每跳距离乘以未知节点与锚节点的最小跳数，就是未知节点与锚节点间的距离，如式（2）所示：

式中，dij表示未知节点j与锚节点i的距离，HopSizei表示距离未知节点j最近的锚节点i的平均每跳距离，hij是未知节点j和锚节点i间的最小跳数。

第三阶段：计算未知节点的位置。当用上述方法计算出未知节点到三个或者三个以上锚节点的距离时，用三边定位法或者极大似然估计法计算未知节点的估计位置。

1.1 DV-Hop定位算法的缺点

（1）传统的DV-Hop定位算法是把距离未知节点最近的锚节点平均每跳距离作为未知节点的平均每跳距离。该平均每跳距离与未知节点到锚节点的最小跳数相乘可以得到两个节点之间的距离。但是在实际应用中，传感器节点是随机分布的，所以网络节点平均每跳距离与实际的距离是有偏差的。

（2）传感器节点的密度也会影响定位的精度。在传感器节点密度大的区域，节点间实际的距离较小，在节点密度小的区域，实际的距离较大，如果仍然用平均每跳距离计算节点间的距离会与实际的距离有很大的偏差。

（3）在最后的定位阶段，三边定位法虽然计算简单，但是对误差比较敏感。而极大似然估计法在一定程度上减小了误差，但是其计算起来较为复杂，得出的定位结果还是存在较大误差。

针对DV-Hop定位算法在定位过程中的缺陷，文献［10-13］对其进行改进：文献［10］针对第三步中使用多边定位法估计未知节点坐标存在较大误差，提出来多边定位法和泰勒级数展开法相结合的改进算法，首先用多边定位法初步估计节点位置，然后利用估计位置作为初始值，对坐标进行迭代运算；文献［11］对节点设定了优先级，直接由三个或者三个以上锚节点定位的节点级数最高，为一级节点，在二级节点的定位中把一级节点看成锚节点进行定位，以此类推，可逐级得到位置节点较低的节点的坐标；文献［12］首先用整个网络所有锚节点的平均每跳距离相加，除以锚节点个数得到整个网络的平均每跳距离，然后求得整个网络的平均定位误差，最后用平均定位误差修正未知节点的坐标。文献［13］针对传统定位算法中，两个节点之间距离小于网络通信半径就记为一跳，当两个节点之间距离很小时，误差比较大的情况下，提出了多通信半径的改进算法。

2 改进算法

2.1 加权DV-Hop定位算法

传统的定位算法利用距离未知节点跳数最少的锚节点的平均每跳距离作为未知节点的平均每跳距离，而加权的DV-Hop定位算法则是综合考虑所有锚节点的平均每跳距离，根据锚节点和未知节点之间的跳数作为不同平均每跳距离的权值的衡量值，权数的大小可以反映锚节点对未知节点平均每跳距离的影响，能够有效减小由于使用单个锚节点的平均每跳距离造成的估计位置误差。一个未知节点所有的权值相加等于1，假设未知节点一共接收到N个锚节点的平均每跳距离，到锚节点i的距离为Ni，那么该锚节点的权值可以用下式表示：

从上式能够看出，未知节点与锚节点间的最小跳数可以反映权值的大小，两者是反比的关系，未知节点与锚节点的最小跳数越大，那么对应的权值越小，未知节点与锚节点的最小跳数越小，那么对应的权值越大。假设锚节点i的平均每跳距离是di，其对应的权值是Wi，那么未知节点的平均每跳距离可用式（4）表示：

改进算法考虑了网络中所有锚节点的平均每跳距离，与传统的算法相比可以减小定位误差，提高定位精度。

2.2 Min-Max修正算法

用上述方法对DV-Hop算法进行改进之后，还是会存在个别节点定位不精确的问题，所以接下来需要对第三步进行改进，在未知节点用三边定位法或者极大似然估计法计算坐标后，用Min-Max修正算法对未知节点的位置进行修正，修正算法的基本原理为：取距离未知节点最近的三个锚节点，以锚节点到未知节点的距离的2倍为边长做出正方形，三个正方形会有重叠区域，如果未知节点位于重叠区域中，则不修改坐标，若未知节点不在重叠区域中，则需要修改坐标。

如果三个锚节点的坐标分别(x1,y1)、(x2,y2)、(x3,y3)，到锚节点的距离分别为d1、d2、d3，那么重叠部分可以表示为：

如果未知节点的估计坐标在重叠区域内，那么就认为定位不存在误差，不需要对位置进行修正，如果未知节点的估计坐标不在重叠区域内，那么需要对位置进行修正，假设未知节点原来计坐标为(x,y)，修正后的坐标为(X,Y)，用如下公式进行修正：

当x＜max(xi-di)时，X=max(xi-di)；

当x＞max(xi-di)时，X=max(xi+di)；

当y＜max(yi-di)时，Y=max(yi+di)；

当y＞min(yi-di)时，Y=min(yi+di)。

从上述算法改进原理可以看出，在Min-Max修正算法中，几乎都是一些加减算法，存在较少的乘法，总体来说没有复杂的运算。在实际的应用中，定位的延迟时间与能量的消耗都不高，非常适合用于成本不高、能量有限和对实时性要求较高的无线传感器网络中，所以Min-Max修正算法是非常具有实际运用价值的。

改进后算法步骤如下：

（1）锚节点以泛洪方式向网络中广播信息包，节点获得与锚节点的最小跳数。

（2）计算整个网络中所有锚节点的平均每跳距离，用加权改进算法计算每个未知节点新的平均每跳距离。未知节点新的平均每跳距离乘以未知节点与锚节点之间的最小跳数，求得未知节点到锚节点的距离。

（3）当未知节点获得到三个或者三个以上锚节点距离时，用三边测量法或者极大似然估计法计算未知节点坐标［14］。

（4）用Min-Max修正算法修正未知节点坐标，若节点估计坐标在正方形相互重叠区域内，则不需要对节点坐标进行修改，若节点的估计坐标不在正方形的相互重叠区域内，则需要对未知节点坐标进行修正。

3 算法仿真

为了更加充分了解改进算法的定位精度，用Matlab 2016a对算法进行仿真。在100m×100m的感知区域内，随机的分布着传感器节点，通信半径为20米，其中有未知节点，有一部分是携带GPS的位置已知的锚节点，下面分别讨论锚节点比例、总节点数对传统定位算法与改进算法的定位精确度的影响，每种仿真都进行100次，然后取这100次结果的算术平均值作为最后的结果，其中节点定位误差可用式（6）表示，E为节点定位误差，(x,y)是节点的实际坐标，(X,Y)是节点的估计坐标，R是节点的通信半径。已被定位的未知节点的定位误差相加总和除以其个数等于节点的平均定位误差。

图1表示传感器节点的分布图，在100m×100m的正方形区域内随机生成100个传感器节点，其中锚节点的个数是8个，未知节点的个数是92个。

图1 节点分布示意图

图2为锚节点的比例分别为5%、10%、15%、20%、25%、30%时，对传统算法与加权DV-Hop定位算法定位精度进行比较。从图中能够看出，锚节点比例为5%时，加权定位算法与传统定位算法的误差几乎一样，随着锚节点比例增加，误差逐渐拉开，锚节点比例为20%时，加权算法对比传统算法的精度提高的最多，达到3.5%，之后，加权定位算法精度提高的比例有所减少。总体来说，改进的加权定位算法提高了定位精度，减小了定位误差。

图3为锚节点的比例分别为5%、10%、15%、20%、25%、30%时，传统算法与Min-Max修正算法的定位误差比较。从图中可以看出用Min-Max修正算法对节点位置进行修正后定位误差明显比传统定位算法小，在锚节点比例为20%时，高了5.3%，虽然在锚节点比例大于25%时，定位误差降低的比例有所减少，但是定位精度仍然比传统定位精度高。

图2 锚节点比例与定位误差的关系

图3 锚节点比例与定位误差的关系

图4为锚节点个数一定，总节点数分别为100，120，140，160，180，200，220时，Min-Max修正算法与传统算法的误差比较。从图中可以看出当节点总数较少时，Min-Max修正算法的定位效果明显比传统的定位算法要好，随着节点总数的增加，当节点总数大于130时Min-Max修正算法与传统算法定位误差越来相近，所以Min-Max修正算法不适用于节点总数较大的情况，但是在实际应用中增加总节点数势必会增加花费，所以Min-Max修正算法还是有一定的实用性的。

图4 总节点个数与定位误差的关系

图5为先使用加权DV-Hop算法后再进行位置修正（加权-MinDV-Hop）与传统算法的在锚节点比例分别为5%、10%、15%、20%、25%、30%时定位误差比较。可以看出改进定位算法的定位精度比传统的定位精度高，在锚节点比例为15%和25%时最为明显。通过比较图2、图3可知：对平均每跳距离进行加权计算后再对未知节点的位置坐标进行修正，比单用加权算法和Min-Max修正算法的定位精度更高。

图5 锚节点比例与定位误差的关系

4 结语

介绍了一种无需测距定位算法，DV-Hop定位算法。并分析了该算法在定位过程中的缺点。针对传统的DV-Hop定位算法在第二步和第三步存在的不足之处，提出了改进算法。每个未知节点的平均每跳距离不再仅仅由距离它最近的锚节点的平均每跳距离决定，而是把网络中所有锚节点的平均每跳距离都考虑进来。根据锚节点与未知节点的距离，计算出锚节点平均跳距对应的权值，进而计算出所有未知节点加权后的平均每跳距离，最后对未知节点坐标用Min-Max算法修正。仿真结果表明，对传统的定位方法仅用加权改进算法或者Min-Max改进算法，在一定的程度上提高了定位精度，但是先用加权算法对平均每跳距离进行改进再用Min-Max算法修正未知节点坐标，定位精度会更高，由于改进方法计算起来方便，不需要增加额外的硬件，所以具有很强的应用性。

参考文献

［1］ 姚先连，胡贞，吕晓玲.无线传感器网络中卡尔曼滤波在移动目标跟踪中的研究［J］.长春理工大学学报：自然科学版，2011，34（3）：88-92.

［2］ 李雪梅.基于DV-HOP算法的无线传感器网络节点定位技术研究［D］.太原：太原理工大学，2012.

［3］ 梁红燕.无线传感器网络DV-HOP节点定位算法的研究［D］.沈阳：东北大学，2013.

［4］ 尚小航.基于DV-HOP的无线传感器网络定位算法研究［D］.长春：吉林大学，2012.

［5］ 李成岳.基于DV-Hop的无线传感器网络节点定位算法研究［D］.吉林大学，2011.

［6］ Abdelali Hadir，Khalid Zine-Dine，Mohamed Bakhouya，et al.An optimized DV-Hop location algorithm usingaveragehopweightedmeaninWSNs［C］.2014 5th Workshop on Codes，Cryptography and Communication Systems（WCCCS）.2014.

［7］ 许毅，陈立家，甘浪雄，等.无线传感器网络技术原理及应用［M］.北京：清华大学出版社，2015.

［8］ Qihong Tao，Linghua Zhang.Enhancement of DV-Hop by weighted hop distance［C］.2016 IEEE AdvancedInformationManagement，Communicates，Electronic and Automation Control Conference（IMCEC）.2016.

［9］ Songlin Liu，Chungang Liu，Wenbin Zhang，et al.Hybrid localization algorithm based on APIT and DV-HOP in WirelessSensor Networks［C］.2015 IEEE/CIC International Conference on Communications in China-Workshops（CIC/ICCC），2015.

［10］ 林金朝，李小玲，刘海波.无线传感器网络DV-Hop算法改进与性能［J］.重庆大学学报，2010，33（2）：127-132.

［11］ 姜晓荣.无线传感器网络DV-Hop定位算法［D］.太原：太原理工大学，2010.

［12］ Mohaddeseh Peyvandi，Ali A.Pouyan.An improved DV-Hop localization algorithm in wireless sensor networks［C］.2015SignalProcessing andIntelligent Systems Conference（SPIS），2015.

［13］ 邴晓瑛.无线传感器中DV-Hop定位算法的改进研究［D］.江南大学，2016.

［14］ Wei Gao，Yue Sun，Wenjun Li，et al.An improved DV-Hop algorithm based on hop distance and estimated coordinates［C］.2017 29thChinese Control And Decision Conference（CCDC）.2017.