基于邻居节点相似度的改进DV-Hop节点定位算法

廖惜春，杨志高，任敬哲

(五邑大学信息与通信工程学院，广东江门529020)

近年来，随着射频通信技术、物联网技术、嵌入式技术的迅速发展，无线传感器网络(Wireless Sensor Network，WSN)在国防军事、交通管理、环境监测等领域得到广泛应用和深入研究。其中，在目标跟踪、环境监测等应用领域中，节点的位置信息至关重要。只有确定节点的确切位置，才能详细地表征“在什么地点发生了什么事件”。若缺少节点的位置信息，则感知到的数据可能失去应用价值。因此传感器节点在随机播撒后，通过定位技术确定节点位置是十分必要的。

定位技术是WSN的核心技术之一。WSN的定位算法，可以根据实际应用中所需定位机制的不同，分成基于测距算法(Range-based)和无需测距算法(Range-free)两大类。其中，基于测距的定位机制需要利用未知节点至信标点之间的距离或角度信息，采用三角测量法、三边测量法或最大似然估计法，计算未知节点位置。而无需测距的定位机制则不需要预先知道未知节点至信标点之间的距离和角度信息，只需要通过网络中节点间邻近关系或节点的连通性等信息实现节点定位。如质心、APIT(Approximate Point-in-triangulation Test)定位、DV-Hop(Distance Vector-Hop)定位、Amorphous和MSD-MAP。由于无线传感器网络硬件设备的限制，无需测距的定位算法得到广大学者的关注。

DV-Hop算法的“无需测距定位法”是研究人员关注较多的算法之一。学者们针对其定位精度较低的缺点，提出了许多改进方法，但尚未达到理想效果。文献［1］采用的算法，虽然具有较高的定位精度，但通信开销和计算量都较大。如果将RSSI引入DV-Hop算法，虽然可以提高定位精度，但增加了节点的硬件开销。文献［2］采用遗传算法和模拟退火算法对DV-Hop算法进行改进，虽然降低了定位误差，但是算法复杂，能源消耗多。文献［3］提出采用粒子群优化的方法，但是该改进算法需要测量信号的方向，从而需要添加相应硬件设备，增加了节点的硬件成本。文献［4］先获得网络中信标节点之间的平均跳距，再计算每个信标节点的平均跳距，进而获得这两个平均跳距之间的误差，从而修正全网的平均跳距。文献［5］针对DV-Hop定位算法在不规则网络中的定位精度进行改进，考虑了未知节点与信标节点之间的路径可能与信标节点间的路径重合这一特性，对平均跳距进行修正，在一定程度上提高了定位精度，但是由于考虑的因素较少，所以定位精度提高的不是太明显。

本文在对DV-Hop定位算法进行研究分析的基础上，通过总结大量改进算法的优缺点之后，提出了基于邻居节点相似度的DV-Hop改进算法。通过仿真分析，结果表明:算法可在无需增加节点硬件以及通信开销的基础上，提高节点的定位精度。

1 DV-Hop定位算法

1.1 DV-Hop 算法描述

DV-Hop算法的核心思想为将未知节点与信标节点之间的距离用信标节点间平均跳距和未知节点与信标节点之间的最小跳数的乘积来表示。然后通过三边测量法或者最大似然估计法求出未知节点的坐标。定位的过程主要分为以下3个阶段［6］:

1)测量未知节点与信标节点之间的最少跳数。采用经典的距离交换协议，使监测区域中所有未知节点获取与信标节点间的跳数信息。

2)计算未知节点到信标节点的估计距离。每个信标节点获得自身到其他信标节点的跳数以及其他信标节点的坐标后，计算信标节点i平均每跳的距离，称为平均跳距di，计算公式为

式中:xi，yi为信标节点i的坐标;hij为信标节点i和j之间的最少跳数。

然后，信标节点将计算获得的平均跳距di以广播的形式通知网络中的其他节点。

3)估计未知节点位置。未知节点利用到各个信标节点之间的最少跳数和平均跳距，求自身的估计坐标。假设(x，y)是未知节点N的坐标，(xi，yi)是第i个信标节点的坐标。未知节点N与信标节点i之间的估计距离为di，并且将未知节点N和网络中所有信标节点的估计距离表达式整合成方程组，则有

将上述n个二元二次方程，转化为AX=b的形式。其中

方程AX=b用标准最小二乘法求解得位置节点坐标为

1.2 DV-Hop 算法的不足

1)DV-Hop算法中，平均跳距是通过信标节点之间的最小跳数和信标节点之间的距离获得。实际中，信标节点之间的距离为直线距离，最小跳数的每跳不一定在同一直线上，且每跳的跳距是不同的。如图1所示。DV-Hop算法将信标节点之间的距离和最小跳数之商作为平均跳距。这一平均跳距会由于网络中的节点稀疏程度和连通度的不同而出现不同程度的误差。

图1 节点多跳通信链路图

2)用信标节点间的平均跳距与未知节点和信标节点之间的最小跳数的乘积，代替未知节点与信标节点之间的实际距离。其中未知节点和信标节点之间的最小跳数的通信路径并非呈直线分布，且节点间跳距不同。所以通过此步骤获得距离也会引入误差。

2 DV-Hop改进定位算法

2.1 相关定义

1)邻居节点:在无线传感器网络中，节点都有一定的通信半径，处于此范围之内的节点称为该节点的邻居节点。

2)邻居节点相似度:无线传感器网络中的节点可以通过信息交换，获取自身的邻居节点ID号列表，并且和其他节点的邻居节点列表作比较，节点间的邻居节点列表中的节点ID号相同的数目越大，邻居节点的相似度越大，其值为式中:δ可以改变节点间邻居列表中ID号相同的节点数目对邻居节点相似度的影响;Numcom指的是节点间邻居列表中ID号相同的节点数目;Numi和Numj分别指未知节点i和j的邻居节点数目。

2.2 改进算法要点

2.2.1 单跳节点处理

无线传感器网络中可以通过单跳直接和信标节点通信的未知节点。在DV-Hop中全部采用网络中邻近信标节点的平均跳距作为距离，实际中，网络中较多的未知节点可以和信标节点直接通信，如图2所示。未知节点和信标节点的距离也不尽相同。使用平均跳距作为这些节点与信标节点的距离，从而导致信标节点的邻居节点区分度单一，而引入较大的误差。所以，本论文在此处引入修正方法。

图2 信标节点的邻居节点

本文提出邻居节点相似度的概念，通过网络信息交换获取节点的邻居节点列表后，根据式(7)可以求出节点i与节点j的邻居节点相似度εij。

对单跳节点进行修正后的距离为

2.2.2 多跳节点处理

余弦定理:已知三角形两边之长及其夹角，可以求得第三边的长度。

根据余弦定理，在节点ABC组成的三角形中，如图3所示。本文假设知道AB和BC的长度，以及∠ABC的度数θ。就可以根据余弦定理，求出AC的长度，这样就将节点A到节点C之间的折线通信路径转化为求直线AC的长，表达式为

图3 节点通信等效模型

未知节点间单跳跳距的修正方法，采用单跳节点处理方式，根据未知节点ABC的邻居节点列表和式(7)、式(8)求出节点A到节点B和节点B到节点C的距离。

节点间的距离越近则邻居节点的相似度越高，而节点距离越远，邻居节点的相似度越低。所以，本文将通过节点间邻居节点的相似度来调整夹角θ的度数。如图4所示，节点i和节点j恰好处于彼此的通信半径之外时，节点k通过多跳模式传递信息，当节点k距离节点i和节点j距离最远时，此时∠ikj的度数最小，且近似等于。

图4 节点通信夹角最小情况

如图5所示，节点i，j恰好位于各自通信半径边缘处，且节点k位于此交集处。此时，节点i，k，j组成一条直线，通信夹角最大，近似为π。节点i，j的距离最远。

图5 节点通信夹角最大情况

式中:εij通过式(7)获得;γ为邻居节点相似度所占权重值，改变其大小可以改变γ在通信夹角中的影响程度，γ值大小根据具体网络连通情况和节点的疏密程度而定。

无线传感器网络中的任意三个通信节点ABC，如图3所示。通过式(8)获得AB和BC的长度，再通过式(10)获取AB和BC的夹角。根据余弦定理，带入式(9)，方可将实际中的折线通信距离转化为求直线距离，减少了由于折线通信带来的误差。

2.3 改进算法实现

1)计算全网节点间的最小跳数

信标节点向邻居节点以广播的形式发送一个信标，包括位置信息字段和邻居节点列表字段。其中位置信息字段包括自身坐标、ID号和跳数值，跳数值初始化为0。邻居节点列表字段包括通信半径内的所有节点的ID和邻居节点的数目，初始化为NULL。

节点收到其他节点发来的信息后，位置信息字段更新坐标和ID号，同时跳数值加1;邻居节点列表字段将接收到的位置信息中的ID号取出，存入邻居节点列表中，邻居节点数目加1，并继续向其他邻居节点广播，通过这种泛洪方式向整个网络传播数据。若节点收到来自同一个节点的多个信息，则比较其跳数值，只保留最小跳数值的信息，这样就保证了所得到的跳数值是到网络中所有节点的最短路径。

经过此阶段，网络中的所有节点都获得各个信标节点的坐标，以及邻近节点的ID号和个数。以及它到各节点的最小跳数。

2)计算未知节点和信标节点的实际跳距

每个信标节点根据第一步中获取的到其他信标节点的位置信息和跳数，利用式(1)估计平均跳距di。

信标节点的邻居节点中的未知节点根据式(7)求出未知节点和信标节点的相似度εi。并且将εi带入到式(8)中修正di为d'i。

通过多跳间接和信标节点通信未知节点，距离修正处理如下:

对于和信标节点通信的节点采用两跳通信的未知节点。首先，采用式(7)和式(8)修正未知节点i与信标节点的前驱节点j之间的单跳距离d'ij，然后结合信标节点的前驱节点j和信标节点B(即信标节点的邻居节点)之间的修正距离d'jB。再根据式(10)求出未知节点i和信标节点B通过节点j通信的夹角θiB，带入到式(9)中得到两跳通信修正距离d'iB。表达式为

对于通过三跳或三跳以上和信标节点通信的节点采用和两跳距离修正同样的方法，先求出两跳路径后，再相互结合，直到获取源节点到信标节点距离。通过此修正方法，使全网中的未知节点获得到各个信标节点的修正距离。

3)计算未知节点坐标

将2)获取的未知节点到各信标节点的修正距离，代入到式(2)中，使用最小二乘法，求得未知节点的坐标。

3 仿真结果极其分析

检测区的范围是100 m×100 m的正方形区域，随机播撒100个节点。网络中节点的通信半径为R。δ和γ根据监测区域节点分布的疏密程度和连通度分别设置为0.9和1。未知节点坐标与实际坐标之间的相对定位误差表示为

式中:erri代表每个未知节点的误差;UN代表未知节点的个数。

通过对DV-Hop、参考文献［5］算法、参考文献［7］算法、本文算法进行仿真，并对实验结果进行比较。从而证明了本文算法的有效性与可行性，图6～图9给出了网络中的节点通信半径不同时，随着网络中信标节点比例变化，三种算法的定位误差比较结果。

图6 R=30 m时定位误差随参考节点比例变化的情况

图7 R=25 m时定位误差随参考节点比例变化的情况

图8 R=20 m时定位误差随参考节点比例变化的情况

从图中可以看出在相同的通信半径下，本文改进算法和文献［5］、文献［7］的算法的定位误差距均低于DV-Hop定位算法。通信半径为30 m时，本文的改进算法比DV-Hop定位算法在相对定位误差上降低了33.34% ～35.35%。比文献［5］、文献［7］定位算法降低了10.06% ～21.41%。且各个算法的定位误差随着信标节点比例的增加，定位误差都不断减小，且趋于平稳。当网络中的信标节点数目一定时，随着节点的通信半径减小，节点的定位误差也随之减小。如当信标节点的比例为10%，节点的通信半径分别为30 m时，DV-Hop定位算法获得的未知节点的相对定位误差为92.22%［5］，文献［5］定位算法获得结果为76.26%，文献［7］定位算法获得结果为78.14%，本文改进定位算法结果为58.48%;在不同的通信半经中，信标节点比例小于10%时，改进算法较DV-Hop定位算法的定位误差降低了约32% ～35%，且与文献［5］和文献［7］的定位算法获得的定位误差降低了约18% ～20%。

图9 R=15 m时定位误差随参考节点比例变化的情况

算法复杂度分析:文献［1］将RSSI引入DV-Hop算法，在复杂度上增加了节点关于RSSI强度值计算的相关部分，并且算法需要额外的硬件成本。而文献［2］和文献［3］虽然采用了经典的遗传算法、模拟退火算法和粒子群优化的方法对DV-Hop算法进行改进，这样极大地增加了算法的复杂度，同时能源消耗多。同时文献［3］还需要添加硬件设备，增加了硬件成本。文献［5］主要针对未知节点与信标节点之间的路径可能与信标节点间的路径重合这一点进行修正，一定程度上提高定位精度，算法复杂度较低，但是由于考虑的因素较少，所以定位精度提高的不是太明显。本文算法通过邻居节点列表的比较，获取邻居节点相似度，并在此基础上对节点的跳距进行修正，在此处略加大算法复杂度。但是节点定位精度却得到较大的提高。

综上所述，本文的改进定位算法，无论是相当于传统的DV-Hop定位算法还是文献［5］的定位算法，均在节点的相对定位误差上都有了较大幅度的降低。

4 结论

本文针对DV-Hop定位算法在单跳通信中，处理信标节点的邻居节点距离没有区分度，统一采用平均跳数与单跳之积的形式表示，以及多跳通信中该算法没有考虑折线通信，依然采用同样的方式处理，从而导致该算法的定位精度较低的情况。同时，这一点也是文献［5］没有考虑到的。本文提出了邻居节点相似度的概念，并应用此概念分别对单跳节点(邻居节点)的距离进行修正，克服了DV-Hop定位算法在处理单跳节点时，采用同样的距离表示距离信标节点的距离;在多跳通信中，结合余弦定理将DV-Hop和文献［5］中的折线距离代替实际中的直线距离，转化为求直线距离的运算，同时修正了多跳通信中每一跳的距离。使得本算法在定位过程中增加了节点跳距区分度，克服了DV-Hop定位算法和文献［5］定位算法较单一的计算。由于本算法中的邻居节点相似度综合考虑了网络的连通度和节点的疏密程度等因素，且可根据实际情况作出相应的调整。所以本算法的实际应用价值较高且具有较好的鲁棒性。

但是，改进后的算法在提高定位精度的同时增加了算法复杂度，并且网络中节点的邻居节点列表的存取上需要占用节点额外的内存空间。这些不完善之处还需要后续进一步改进和深入研究。

［1］刘艳文，王福豹，段渭军，等.基于DV-Hop定位算法和RSSI测距技术的定位系统［J］.计算机应用，2007，27(3):516-527.

［2］赵仕俊，孙美玲，唐懿芳.基于遗传模拟退火算法的无线传感器网络定位算法［J］.计算机应用与软件，2009，26(10):189-192.

［3］王驭凤，王岩.基于矢量和粒子群优化的传感器网络节点定位［J］.计算机应用，2009，29(1):309-311.

［4］林金朝，刘海波，李国军，等.无线传感器网络中DV-Hop节点定位改进算法研究［J］.计算机应用研究，2009，26(4):1272-1275.

［5］沈明玉，张寅.基于改进的平均跳距和估计距离的DV-Hop定位算法［J］.计算机应用研究，2011，28(2):648-650.

［6］章浩，李萍萍，张西良.无线传感器网络节点定位机制研究［J］.电视技术，2006，30(2):70-72.

［7］林金朝，刘海波，李国军，等.无线传感器网络中DV-Hop节点定位改进算法研究［J］.计算机应用研究，2009，26(4):1272-1275.