DV-Hop定位算法的误差分析

朱慧勇

（西安铁路职业技术学院，陕西 西安 710026）

美国的Rutgers University（路特葛斯大学）的 Niculescu等[1]利用GPS定位和距离向量路由的原理提出了（Distance Vector-Hop，DV-Hop）定位算法。

1 DV-Hop算法的过程

DV-Hop定位算法可以分为3个过程：第一过程是无线传感器网络（Wireless Sensor Networks，WSN）中使用经典距离矢量交换协议来获得节点距锚节点的最小跳数；第二过程是每个锚节点根据与其他锚节点之间的距离和最小跳数，计算自己的平均跳距，并采用可控洪泛法向全网广播，保证未知节点仅收到一个广播值；第三过程是未知节点利用收到的广播值与至少3个的锚节点的最小跳距，来获得未知节点到锚节点距离，然后采用3边测量定位或者最小二乘法来得到自身的位置。

2 获得节点距锚节点的最小跳数

首先使用距离矢量交换协议，锚节点向它的邻居节点广播消息，消息包括锚节点的标识符、位置信息和跳数值，跳数的初始值设置为0；邻居节点接收到消息后，先将跳数值加1，然后记录下此消息，并将记录下的信息广播给它的邻居节点，重复以上步骤，直到所有节点都具有锚节点的位置信息和彼此间的最小跳数。由于采用广播的途径，一个锚节点广播的消息可能多次到达同一节点，导致信息冗余，增加了通信开销。为了消除广播消息的无限循环，只有新的锚节点消息才能被节点广播，垃圾消息将被抛弃。垃圾消息是指节点在接收信息的时候，由于路径的不同，导致节点可能收到多个相同锚节点的信息，感兴趣的是跳数值最小的那条消息，其他消息都认为是垃圾消息。

3 未知节点获得平均跳距

锚节点根据自己存储的消息，即其他锚节点的标识符、位置信息和跳数值通过式（1）运算得到这个锚节点跟其他锚节点之间的每跳的平均距离，即平均跳距：

i代表这个锚节点，j代表其他锚节点，（xi,yi）和（xj,yj）分别表示节点i和节点j的位置的坐标，hopj表示锚节点i和锚节点j的跳数值，HopSizei是锚节点i的平均跳距。

每个锚节点经过式（1）计算后，都得到了对应的平均跳距。然后，锚节点向自己的邻居节点广播包含有自己平均跳距的消息，邻居节点存储消息后也接着广播这条消息。重复广播，直到所有未知节点都收到平均跳距的消息。如果未知节点收到多个包含平均跳距的消息，那么它仅存储第一个收到的消息，抛弃后来收到的消息，这就意味着大部分未知节点收到的平均跳距是离自己最近的锚节点发出的。

3.1 未知节点计算自己的位置

这时，未知节点存储的信息有全部锚节点的标识符、位置坐标信息和最小跳数，以及平均跳距。可以用相应的最小跳数与平均跳距的乘积来作为未知节点与相应锚节点的估计距离。如果未知节点知道与3个或者3个以上的锚节点的估计距离之后，就可以采用3边定位法或者最小二乘法进行自身定位。

3.2 DV-Hop算法的性能分析

为了更直观地说明DV-Hop算法的性能，本文使用Matlab软件来做仿真实验。仿真环境设置：100 m×100 m的二维正方形区域，节点总数为100个，锚节点为20个，节点通信半径R为30 m。节点在仿真区域随机分布，没有障碍和干扰。

节点随机分布图如图1所示，图中*表示锚节点，o表示未知节点。定位误差如图2所示，中间用直线连起来的两头其中一个是估计位置，另一个是实际位置。本次仿真结果是定位误差为29.6%。

图1 节点随机分布

图2 定位误差

在相同的条件下，又运行了很多次，定位误差基本保持在30%左右。运行过程中，可以看到DV-Hop算法只需要少量的锚节点，计算和通信开销适中，节点不需要有测距的能力，是一个可扩展的定位算法。对于各向同性的密集网络，可以得到一个合理的平均跳距，使它们能够实现更好的定位精度；但对于不规则拓扑结构的网络，定位精度下降幅度较大。

4 DV-Hop定位算法误差分析

影响DV-Hop算法的定位精度主要有两方面，一方面是外部客观因素，另一方面是算法本身的主观因素。下面从这两方面分析。

4.1 客观因素

在部署无线传感器网络的时候，很多情况下，节点都是随机部署的。随机部署会造成两方面的问题：一方面会造成网络拓扑不规则；另一方面是节点分布不均匀。在分析DVHop算法性能的时候，DV-Hop算法适合于各同向性网络，而对不规则网络，定位效果比较差。节点分布不均匀主要是指锚节点和未知节点分布不均匀，比如在某片较大的区域只有一个锚节点，而在某片较小的区域有很多锚节点。节点分布不均匀会产生一些节点无法定位，这些无法定位的节点叫作不良节点。不良节点有4种情况。如图3所示：（a）中表示完全孤立的节点，无法与整个网络进行通信；（b）中显示一个锚节点，它有3个邻居未知节点，在DV-Hop算法中，是可以估计出位置的，但未知节点的位置都一样，因此也是无法定位的；（c）中两个锚节点是无法通过DV-Hop算法定位未知节点的；（d）中的情况和（b）类似。

4.2 主观因素

在DV-Hop定位算法中，有4要素：未知节点到锚节点的最小跳数；未知节点收到的平均跳距；未知节点通过最小跳数乘以平均跳距来估计距离；未知节点通过3边定位法或者最小二乘法来定位。下面按这4要素来分析误差的产生。

图3 不良节点

4.2.1 最小跳数

DV-Hop算法采用最小跳数为基础是有一定的依据的，在选取节点之间的跳数的时候，通常节点之间会有好多条路径，不同的路径，跳数可能也不同，这时候，最小跳数可以在某种程度上表示两个节点之间的联系。但是如果节点之间最小跳数所在的路径是‘U’型或者‘C’型的时候，最小跳数会失效，不能准确表示两节点之间的联系。

4.2.2 平均跳距

DV-Hop算法中，未知节点的平均跳距由离自己最近的锚节点计算出来，这种方法是借鉴单点代表局部，某种程度上来说也是可取的。而锚节点在计算平均跳距的时候，如果锚节点之间最小跳数比较大，而锚节点之间的欧式距离又是固定的，从而使平均跳距偏小，不利于定位。

4.2.3 估计距离

DV-Hop算法中，用最小跳数与平均跳距的乘积来作为估计距离。经过上面的分析，节点之间最小跳数所在的路径是‘U’型或者‘C’型的时候，或者节点的平均跳距偏小的时候，估计距离就会有很大的偏差。

4.2.4 3边定位法或者最小二乘法

采用3边定位法，会降低计算量从而减少能量消耗，但是3边定位法在距离信息比较准确的情况下，定位精度才准确。采用最小二乘法，如果估计距离本来就不准确，再进行处理，就会造成误差累积，最终导致比较大的误差。

5 结语

本文讲解了DV-Hop定位算法的过程和性能分析，深入地探讨了产生定位误差的客观原因和主观原因。在未来的工作中，针对这些客观原因与主观原因，要多多思考，如何能克服这些困难。

[参考文献]

[1]NICULESCU D，NATH B.DV based positioning in Ad Hoc networks[J].Telecommunication systems，2003（22）：267-280.