一种无需测距的无线传感器网络定位算法研究

托乎提努尔，陈 曙

(山东大学信息科学与工程学院，济南250100)

无线传感器网络(Wireless Sensor Network，WSN)是由大量成本低廉的，具有感知能力、计算能力和无线通讯能力的传感器节点组成的智能网络。WSN节点一般被密集部署在特定的监控区域内，节点间以无线、多跳的通信方式自组织网络拓扑结构，通过协同工作完成单个节点不能完成的全局任务［1］。

节点定位是无线传感器网络非常重要的技术之一，目前已经提出了许多以获取节点准确坐标位置为目的的定位算法。按照定位所采用的距离参数获得方式，把定位算法分为基于测距算法(Range-based)和无需测距算法(Range-free)［2］。基于测距的定位算法常用的测距技术有TOA或TDOA测距、AOA测距和RSSI测距［3-5］。Range-based定位算法对网络的硬件设施提出了较高的要求，同时通常需要多次测量，这些算法在获得相对精确定位结果的时候，都要产生大量计算和通信开销。因此，Range-free定位算法受到越来越多的关注。

Range-free定位算法无需距离和角度信息，仅根据网络连通性和己知位置的锚节点信息来实现相对精确的定位功能。这种算法降低了对节点的硬件要求，使节点成本更适用于大规模传感器网络［6］，而且其定位性能受环境因素的影响较小。典型的算法包括质心、DV-Hop［7］、Amorphous、APIT 等［8-9］。在DV-Hop定位算法中，锚节点广播包含自身位置和跳数信息的分组，对于每个待定位节点，它只记录到每个锚节点的最小跳数，知道锚节点的位置和平均每跳距离，就可以利用三边测量法或极大似然估计法计算自身位置。

本文先简要介绍DV-Hop算法的基本思想，分析和研究算法原理及误差产生的主要原因，然后提出原来算法的改进方法，并给出仿真实验的结果及其分析。

1 DV-Hop定位算法

DV-Hop定位算法，是一种基于距离矢量路由的无需测距定位算法，其基本思想是将未知节点到锚节点之间的距离用网络每跳平均距离和两者之间跳数之积表示，再使用三边定位运算法获得节点位置信息。

1.1 算法的基本思想

DV-Hop算法的定位过程分为3个阶段［10-12］:

(1)计算未知节点与每个锚节点的最小跳数。锚节点向邻居节点广播自身位置信息的分组，其中包括跳数字段，初始化为0。接收节点记录到每个锚节点的最小跳数，忽略来自同一个锚节点的较大跳数的分组。然后将跳数加1，并转发给邻居节点。通过这个方法，网络中的所有节点能够记录到每个锚节点的最小跳数。

(2)计算未知节点和锚节点的每跳平均距离。

每个锚节点根据第一阶段中记录的其他锚节点的位置信息和相距跳数，利用式(1)估算平均每跳的实际距离。

其中(xi，yi)，(xj，yj)为锚节点i，j的坐标，hij是锚节点i与j之间的跳数。然后，锚节点将计算的每跳平均距离用带有生存期字段的分组广播至网络中，未知节点仅记录接收到的第一个每跳平均距离，并转发给邻居节点。这个策略确保了大多数节点从最近的锚节点接收到每跳平均距离值。未知节点接收到每跳平均距离后，根据记录的跳数，计算到每个锚节点的跳段距离。

(3)计算未知节点的位置。

当未知节点获得到附近锚节点的估计距离之后，通常采用三边测量法进行位置估计。假设某一未知节点u坐标为(x，y)测得到n个锚节点的距离，第i个锚节点的坐标为(xi，yi)，节点u到锚节点i的距离为di。根据上面的已知数据，可以得到如式(2)所示的系统方程:

由式(2)可得，

未知节点u的坐标有如式(5)可以得到，

1.2 算法存在的问题

DV-Hop算法的不足有以下几个方面:

(1)在一个锚节点覆盖范围内，不管未知节点位置在哪儿，都算1跳，即1 Hop。如图1所示，K是锚节点，A，B是未知节点，R是锚节点的通信半径，根据DV-Hop算法计算KA=1 Hop，KB=1 Hop，即KA=KB，所以产生误差。

图1 DV-Hop算法误差示意图

(2)DV-Hop算法用锚节点间的直线距离来估算锚节点间信息通路的曲线距离，在计算最小跳数时，无论相邻节点物理距离的远或近，跳数值均只固定增加1，并不能反映距离的差别，因而导致定位结果存在较大的误差。

由于DV-Hop算法存在上面所说的定位误差问题，在大规模传感器网络中积累这些误差产生很大的误差，降低定位精度，很大程度上影响准确定位。所以减少误差DV-Hop定位算法中的最关键问题。

2 改进的DV-Hop定位算法

本文提出了两种改进方案，对DV-Hop算法的第2个，第3个阶段进行修改，然后把两种方法相结合，提出了一个新的DV-Hop算法。

2.1 改进方法1

锚节点的数量很大程度上影响WSN定位算法的精度，如果网络中有较少数量的锚节点，定位误差会增加。所以尽量提高参与某一未知节点定位的锚节点数量。本方法的主要思想是:第1步，第2步和原来的DV-Hop算法一样。第3步，与锚节点直接相邻的未知节点先定位，然后使其升级到锚节点，下次参与定位未知节点，扩展锚节点数量，然后再重新回到第1步计算，直到把全部未知节点定位为止重复运行。

算法的具体流程如图2所示。

图2 改进方法一的计算流程

2.2 改进方法2

为了提高定位精度，需要减少未知节点实际位置和估算位置的误差。与未知节点距离最近的锚节点，对这个未知节点平均每跳距离的影响最大。首先求每跳距离平均值，然后计算改进的每跳平均距离，具体如下:

其中，de是锚节点对未知节点作用离散之后的每跳距离，hui是锚节点之间的跳数n是锚节点个数，unknown是未知节点个数。在改进的方法中提出了一种新的误差修正值Ce计算锚节点之间的每跳平均距离误差修正值如下:

计算节点i，j之间的距离如下:

其中，hhop(i，j)是节点i和j之间的跳数。

用这种方法计算未知节点位置，和原来的DVHop算法相比更接近实际位置，我们能够有效地减少平均每跳距离误差对节点定位的影响，显著提高定位精度。

3 算法仿真与分析

为了验证改进算法的性能，本文对传统DVHop定位算法和改进算法在MATLAB平台上进行了仿真对比分析。假设仿真节点都随机分布了一个二维平面上，在一个100 m×100 m的区域内，随机布散200个节点，如图3、图4所示，其中锚节点的坐标信息是已知的，而未知节点需要通过计算得到。在仿真中对每种算法都随机运行100次，然后取其整体定位误差的平均值。

图3 节点随机分布图

图4 节点邻居关系图

在图5中，通信半径R=30 m，分别选取了4、6、8、10、12、15、18 这7 种初始锚节点数量进行观测和结果对比。从图3中可以看出，随着锚节点数量的增加，两种算法的定位误差都在降低。当锚节点数量为4～10时，两种算法的定位误差下降趋势都很明显，然后定位误差下降趋势减缓。在锚节点数量为4时，改进算法比原算法平均误差降低了约19%。仿真结果表明，改进的定位算法有效地减少未知节点的定位误差。

图5 锚节点数量和定位误差

在图6中，在实验区域内保持锚节点数量为6，通信半径从15 m变化到40 m，比较传统DV-Hop算法和改进DV-Hop算法。从图中可以看出，随着节点通信半径的增大，两种算法的节点平均定位误差都呈现递减趋势，当节点通信半径较大时，这种下降趋势明显。在相同条件下，改进算法的平均定位误差明显小于传统DV-Hop算法。当通信半径为15时，两种算法的平均误差差距最小，但源算法的定位误差仍高于改进算法。

图6 节点通信半径和定位误差

4 结论

本文针对传统DV-Hop算法在节点随机分布的网络拓扑环境下存在较大误差的问题，提出了一种改进DV-Hop定位算法。通过扩展锚节点数量和修正每跳平均距离，使得到的结果更加接近实际每跳距离。

理论分析和算法仿真显示，与传统算法相比，在定位节点无须额外增加传感器节点硬件开销的条件下，可明显提高节点定位的精度，同时具有良好的扩展性。因此，对于精度要求不高，硬件环境不足的定位应用，它是一种实用，有效的选择。对精度要求更高的环境中，需要我们将来进一步研究出应用范围更广的新的定位算法。

［1］杨石磊，樊晓平，刘少强，等.一种改进的无线传感器网络DVHop定位算法［J］.计算机测量与控制，2008，16(9):1356-1358.

［2］石为人，贾传江，梁焕焕.一种改进的无线传感器网络DV-Hop定位算法［J］.传感技术学报，2011，24(1):83-87.

［3］Niculescu D，Nath B.Ad Hoc Positioning System(APS)Using AOA［C］//IEEE Infocom，2003:1124-1136.

［4］李晓维，徐勇军，任丰原.无线传感器网络技术［M］.北京:北京理工大学出版社，2007:191-221.

［5］Wang Fubao，Shi Long，Ren Fengyuan.Positioning Systems and Algorithms for Wireless Sensor Network［J］.Journal of Software，2004，16(5):45-49.

［6］张品，孙岩.一种新的无线传感器网络DV-Hop算法［J］.电子器件，2010，33(1):117-120.

［7］Niculescu D，Nath B.DV Based Positioning in Ad Hoc Networks［J］.Telecommunication Systems，2003，22:267-280.

［8］孙晶晶.无线传感器网络定位算法的研究［D］.西安电子科技大学，8-29.

［9］Wu Yanhai，Zhang Jia，Wu Nan.Improved Localization Algorithm in Wireless Sensor Networks［C］//2011 Fourth International Conference on Intelligent Computation Technology and Automation，2011，576-579.

［10］Li Yuanyuan.Improved DV-HOP Location Algorithm Based on Local Estimating and Dynamic Correction in Location for Wireless Sensor Networks［J］.International Journal of Digital Content Technology and Its Applications，2011，5(8):196-202.

［11］Lu Qingling，Bai Mengliang，Zhang Wei.A Kind of Improved DVHop Algorithm［C］//The 2nd International Conference on Intelligent Control and Information Processing，2011，867-869.

［12］Fang Wangsheng，Yang Guangyu.Improvement Based on DV-Hop Localization Algorithm of Wireless Sensor Network［C］//2011 International Conference on Mechatronic Science，Electric Engineering and Computer，2011，2421-2424.