无线传感器网络中一种改进的DV-Hop 定位算法研究*

何少尉

（浙江邮电职业技术学院，浙江 绍兴 312366）

0 引言

随着无线通信技术的快速发展，拥有感知、计算和网络通信能力的传感器以及传感器构成的无线传感器网络成为研究人员关注的焦点。传感器拥有低成本、低功耗、体积小的特点，无线传感器网络有着极为广泛的应用前景[1-2]。节点的定位算法是传感器网络的关键技术。DV-Hop 算法是一种广泛研究的免测距定位算法，具有开销小、成本低和抗噪性能强等优点。DV-Hop 算法仅需要考虑最邻近的信标节点的平均距离来计算平均每跳距离，使得算法的定位精度不高。目前，对DV-Hop 算法的改进已经进行了较多研究，如文献[3]基于进化算法提出改进的DV-Hop 定位算法，文献[4]通过设置跳数阀值来约束节点间的最小跳数，并通过加权处理平均跳距来改善DV-Hop 定位算法的精度。相关研究均能在一定程度上提高定位精度。本文针对DV-Hop 定位算法中存在的不足，提出一种利用提高全网平均每跳距离来改进DV-Hop 定位算法精度的方法，以期为无线传感器网络的定位提供新的方法。

1 DV-Hop 定位算法

DV-Hop 定位算法起源于美国路特葛斯大学。根据已知节点跳数的平均值，与已知节点的最小跳数的乘积来预测未知节点的距离，采用三边测量方法来获得节点位置信息的方法[5]。DV-Hop 算法不仅可以规避信标节点数量有限的缺点，还可以获得目标范围外的众多信标节点的大概距离。DV-Hop算法获取距离是间接的，把有方向、有大小的距离信息和网络的互通特性相结合，再转变为近似距离[6]。在定位的各个环节中，每个节点都起着至关重要的作用，缺一不可。

DV-Hop 算法的定位过程分为3 个阶段。

第一阶段：计算未知节点与每个信标节点的最小累计量化值。

未知节点根据信标节点向其传达的位置坐标和有关推算的程序，加上自身具有的关于坐标的片段或者演练的路径，获取更加精确的位置数据。

网络中的每个节点要想达到完全捕捉到全部节点的最小累计的量化值，先要准确收集全部节点的最小累计量化值。对信标节点相同的一组中累计量化值相对比较大的值，可以在容错范围内划去不计，直接将有效累计量化值加上1，随后传送给周围节点[7]。

第二阶段：计算未知节点和信标节点的实际跳段距离。

所有的节点完成第一阶段后保留了全部节点的最小累计的量化值和相关的位置数据，然后进入DV-Hop 定位算法的第二阶段，使用式（1）计算未知节点和信标节点的实际跳段距离：

式中，i、j代表信标节点，坐标分别用(xi，yi)、(xj，yj)表示；hj表示的在i与j不相等的前提下，i、j之间的量化单位总数。信标节点通过用生存期字段来代表所有量化距离的平均单位距离值，然后将其传送到系统中，而且未知节点只对首次接受的距离做保留，然后按照保留的距离总数和信标节点总数计算出每一个信标节点的单位距离，最后发给相邻的节点[8]。

第三阶段：计算未知节点坐标位置。

未知节点计算自身坐标是根据第二阶段中接收到的所有信标节点的跳段距离，一般采用三边测量法或极大似然估计法[9]。DV-Hop 定位算法举例如图1 所示。

图1 DV-Hop 定位算法举例

图1 中，第一阶段和第二阶段后，信标节点L1、L2、L3两两之间的真实距离和跳数很容易得出，所以信标节点L2计算的每跳平均距离为（50+70）/（2+5）=17.14。假设A 从L2获得平均每跳距离，则节点A 与L1、L2、L3这3 个信标节点之间的距离为3×17.14、2×17.14、3×17.14，最后A 的坐标位置就能按照三边测量法得出结果。

2 一种改进的DV-Hop 节点自定位算法

2.1 DV-Hop 节点自定位算法的不足

DV-Hop 算法的精确度仅仅限于跳数小于2 的节点间的距离，所以当DV-Hop 算法采用乘法计算未知节点和信标节点的距离时误差较大，精确度明显降低。产生误差的原因如图2 所示。

图2 未知节点与信标节点距离

图2 中，L1代表信标节点，未知节点用A 表示，它们之间的跳数已经处于大于等于2 的情况。图2粗虚线表示的就是L1和A 节点之间的距离，等于跳数与每跳的平均距离（细虚线）的乘积，此处即是误差产生的根本原因。

2.2 DV-Hop 节点自定位算法的改进思路

DV-Hop 算法在第一个阶段时只收集到全部节点中的最小累计量化值，而改进后的算法保留自己的计算结果后发送到网络中，起到一个校对的作用。发送的数据是以分组的方式进行传播，一般格式为{di，ci}，其中ci表示信标节点i到剩下全部信标节点每跳距离的平均值。当所有节点收到数据后，会把这些分组数据保存在自己的数据表中，并且再次向相邻的节点传输，而重合的分组信息将自动被删除。重新设定的第一阶段，每个节点都能参与进来，共同计算出整个网络的每跳距离的平均值。计算原理：将ci即全部信标节点的平均值加权平均，得到整个网络的平均每跳距离为：

然后，未知节点可以得出自身到每个信标节点的大概距离为：

第三阶段未知节点如能利用最大似然估计法预估自身的大致坐标，当未知节点收到至少3 个信标节点的位置信息后，就能计算得到自己的位置信息。

根据以上分析，提出进一步的改进思路：利用全网平均每跳距离c代替最近信标节点的平均每跳距离ci；无论是未知节点间还是信标节点间得出的距离，都更能代表它们之间的实际距离，使之后的计算结果更加准确。要想提高全网平均每跳距离c，需从根源上找解决的办法。首先，要想办法减小各个信标节点之间的距离误差，尽可能接近真实的距离，这样计算出的全网平均每跳距离c才更有代表性，进而提高最终位置信息的精确度。

将信标节点i的平均每跳距离误差定义为：

其中：节点j为信标节点i数据表中的其他信标节点；hopsij代表信标节点i、j之间的跳数；ni为信标节点i数据表中其他信标节点总数；|dtrue-dset|ij表示信标节点i、j之间实际距离与计算距离之差的绝对值，其中：

因此，提出一种改进的DV-Hop 定位算法，具体描述如下。

（1）平均每跳的距离改进。在改进算法中，全网平均每跳的距离经过两个阶段就能得到，后续各个信标节点利用式（4）就能得出各自的平均每跳距离误差，然后各个坐标节点会把自身的平均每跳距离误差进行分组后发送到网络中，即改进的算法中添加的第三个数据分组广播阶段。以{idi，diseri}的数据分组方式进行，diseri代表信标节点i与剩下信标节点之间的平均每跳距离误差。各个接收到分组的数据信息后会自动添加到数据表中，并且发送给相邻的节点。对于分组信息中重合的idi号，节点会自动删除。这样的处理无论是信标节点还是未知节点，都能知道全部信标节点计算的平均每跳距离误差，最后再进行整个网络的平均每跳距离误差的计算，即把信标节点得到的所有平均每跳距离误差相加取平均，即：

其中：n为网络中的信标节点总数。通过该新增加的阶段，每个未知节点得到整个网络的平均每跳距离误差。由于已经在第二个数据分组广播阶段后得到了整个网络的平均每跳距离c，修正得到新的网络平均每跳距离为：

其中：k为变量参数，-1 ≤k≤l，k的取值随具体的网络环境而定，k值的大小影响着定位精度。这样未知节点就可以得出自身到每个信标节点的大概距离为：

第三阶段未知节点利用最大似然估计法或者三边定位法得到自己的大致坐标，所以当未知节点收到至少3 个信标节点的位置信息后，就能计算得到自己的位置信息。

（2）网络区域的上下界限判断。对网络来说，虽然网络区域的大小无法衡量，但能大致判断网络区域的上下界限：

其中xarea为网络区域在x轴上的分量，yarea为网络区域在y轴上的分量

改进之后的算法减小了整个网络中的平均定位误差，只要针对出现偏差的未知节点的位置信息进行改正，就能从根本上解决整个网络中误差问题的出现。

3 仿真实验结果与分析

如图3 所示，假设在通信半径为30 m、100 m×100 m 的范围里随意分布200 个传感器节点，其中有20 个信标节点，其中*表示信标节点，·表示未知节点。用传统的DV-Hop 定位算法得到每一个未知节点的坐标，再根据实际的位置坐标计算出未知节点的定位误差。

图3 传感器节点分布

如图4 所示，将所有的定位误差相加求和，再除以未知节点总数得到平均定位误差为10.072 9，平均定位误差除以通信半径30 m 得到定位精确度为33.58%。从定位误差和定位精度看出，用传统的DV-Hop 算法计算得到的定位误差和定位精确度都不是很好，因此这种算法只能应用在对精度要求不高的地区。

图4 各个未知节点的定位误差

3.1 DV-Hop 定位算法的影响因素

传统的DV-Hop 算法得到的定位误差和定位精度都很高，下面进行原因探究。

首先探究定位误差和定位精度是不是受到通信半径的影响。同样模拟在100 m×100 m 的范围里杂乱分布200 个传感器节点，当中信标节点的个数还是20 个时，现在只改变节点的通信半径，分别取值为25 m、30 m、35 m、40 m、45 m、50 m、55 m、60 m 和65 m，通过仿真计算得出结果如图5 和图6所示。

图5 节点通信半径与定位误差的关系

图6 节点通信半径与定位精确度的关系

从图5 能够得到，随着通信半径的增大，定位误差随之增大。从图6 能够知道，通信半径减小，定位精确度也在减小。可见，通信半径对这两者的影响是相反的。有时候对一个通信半径虽然定位误差较小，但是定位精确度却很大；有时候定位精确度较小，但是定位误差很大。因此，一味提高或者减小通信半径是不可行的，需找到一个效益最好的平衡点。

3.2 改进的DV-Hop 定位算法仿真结果与分析

改进的DV-Hop 定位算法，模拟在相同条件下观察参数k值对定位精确度的影响。对100 m×100 m、无规律分布200 个传感器节点，20 个信标节点个数，35 m 的通信半径，增加参数k（取值为-1 到1，间隔为0.1），通过仿真观察k值对定位精确度的影响，结果如图7 所示。

图7 参数k 对定位精确度的影响

从图7 能够得到，除了k值变化、其他条件都不变情况下，定位精确度在-1～0.6 范围内随着k值的增加不断下降；在0.6～1 范围内，定位精确度随着k值的增加而增加。因此，当k值为0.6 时，定位精确度最低，也就是最精确的时候。

随后模拟在不同条件下观察参数k的值对定位精确度的影响。保持基本仿真环境不变，只改变节点总数和信标节点的个数。第1 种：在节点总数为100，信标节点数为10；第2 种：节点总数为200，信标节点数为50；第3 种：节点总数为300，信标节点数为80。参数k从-1 到1，间隔为0.1，仿真结果如图8 所示。

图8 在不同的网络环境下参数k 对定位精确度的影响

从图8 可以得到：当k从0.1～0.7 时，3 种状况下的定位精度都在0.3 以下都有最佳值。第1 种情况下，当k值为0.4 时，定位精确度最低；第2种情况下，当k值为0.6 时，定位精确度最低；第3 种情况下，当k值为0.7 时，定位精确度最低。

3.3 DV-Hop 定位算法与改进算法的对比分析

分别对传统算法和改进算法进行仿真和分析，在100 m×100 m 的范围里无规律放置200 个传感器，20 个节点是信标节点，通信半径是20 m。同时，将信标节点个数除以节点总数减去信标节点个数的差值作为k的值。用传统DV-Hop 定位算法和改进的DV-Hop 定位算法对未知节点进行定位，然后比较两者定位误差和定位精确度，仿真结果如图9、图10 所示。

图9 平均定位误差对比

图10 平均定位误差的对比

从图9 可知，传统DV-Hop 算法的定位误差比改进算法大很多，因此就定位误差来说，改进算法占很大优势。

从图10 可知，传统DV-Hop 算法的定位精确度比改进算法高出很多，即改进算法定位比较精确。因此，就定位精确度来说，改进算法占很大优势。

综上所述，改进的DV-Hop 算法大大减小了定位误差，提高了定位精度，改善了传统DV-Hop 算法的不足。

4 结语

节点定位算法是无线传感器网络中研究的一个热点。在介绍DV-Hop 算法的基础上，分析该算法存在的不足提出改进的对策，通过减小全网平均每跳距离与真实的平均每跳距离间的差距，对不在网络区域的未知节点的坐标进行重新修订。实验分析表明，改进算法的精确度明显高于DV-Hop 算法，且减小了定位误差，具有很高的可用性，为无线传感器网络的定位提供了可行的方法。