无线传感器网络基于测距的节点定位算法综述

罗兰花　梁海英　任子亭

【摘 要】基于测距的定位方法对测量的距离信息运用几何知识求解未知节点的位置，常用在定位精度较高的领域，可在误差、能耗、受环境因素影响等方面进行优化。本文对基于测距的无线传感器网络节点定位算法进行详细地分析和比较。

【关键词】无线传感器网络；节点定位；三边测量法；最大似然估计法

【Abstract】The node localization based on distance always using geometric knowledge to solve the unknown nodes position. Its used in the field of high positioning accuracy， and it can bring optimization in error， energy consumption， and influenced by environmental factors. The paper detailed analysis and comparison of the node localization algorithm based on ranging of wireless sensor networks.

【Key words】Wireless sensor network； Node localization； Three sided measurement； Maximum likelihood estimate

0 引言

近十年来，无线传感器网络得到了前所未有的发展，在众多领域中得到了广泛的实际应用，被认为是影响人类发展的十大技术之一。尽管节点定位在定位精度、定位时间、能量开销等方面有了很大改进，但仍然是制约和影响无线传感器网络应用的关键技术之一。

1 常见定位方法分类

无线传感器网络中节点定位方法根据不同手段和角度有不同的分类方法，典型的分类有以下几种。

1.1 绝对定位和相对定位

绝对定位为网络命名空间提供一个唯一的地址，定位结果为坐标位置，如经纬度等。此类定位方法对网络变动时适应性较好；相对定位则以网络中某些节点作为参考节点，为其他节点建立坐标，相对定位不提供唯一的地址，无需信标节点，网络变动时适应性差。

1.2 粗粒度与细粒度

根据信号强度、角度或时间等信息计算未知节点的位置称为细粒度定位，如Radio Camera定位系统中的信号模式匹配技术（signal pattern matching）[1]；根据逐渐接近信标节点的信息来度量未知节点的方法称为粗粒度定位，如质心、衰减模型、凸规划、Active Badge和ParcTAB均属于粗粒度定位。

1.3 集中式定位和分布式定位

集中式定位先将所需的信息传递到中心节点然后进行计算，该方法侧重于对定位信息的集中处理，可以获得相对精确的定位，缺点[1]是中心节点能耗大，容易造成个别节点过快耗尽能量，从而影响其他节点定位。

分布式定位则依赖于节点间的信息交换和协调，获得足够信息后节点自行定位计算。分布式定位通过节点间合作减少了整体定位时间，且能耗比较均衡，但会放大和累积定位过程的误差，从而影响定位精度。

1.4 基于测距定位和无需测距定位

基于测距定位方法测量节点间的距离、角度、信号强度和传输时间等信息，然后借助三边测量、三角测量、最小二乘法或最大似然估计法计算未知节点的位置；无需测距定位方法则通过网络连通度、节点间相对距离计算未知节点位置。

基于测距定位方法能实现较精确的定位，但对节点硬件要求高、功耗大和易受环境因素的影响，常用于精度要求较高的专业领域，如国防军事、国家安全等。无需测距的定位方法具有硬件要求低、成本低、能耗小等优点，但存在误差较大、定位精度较低等问题，常用在精度要求相对较低的领域，如环境监测等。

2 节点位置计算方法及其分析

2.1 三边测量法

三边测量法利用三个已知信标节点的坐标和未知节点的距离推导出未知节点的坐标。假设已知A、B、C三个节点，坐标分别为（xa，ya），（xb，yb），（xc，yc），A、B、C到未知节点D的距离为别为d1、d2、d3，未知节点可用几何图形表示为以已知节点为圆心，节点距离为半径三个圆的交点，如下图1所示。

三边测量法的缺点是节点距离误差较大时，可能出现三个圆无法交于一点，方程无解即定位失败。

2.2 三角测量法

三角测量法根据三个信标节点与未知节点的角度和三个节点的坐标信息计算节点间的距离，然后计算出未知节点坐标。该方法也是一种基于几何运算的定位方法。

三边测量法和三角测量法属于形式化数学方法，并不能很好地直接应用在无线传感器网络中。因此，国内外研究人员对这两种方法进行了优化和适应性修改，以适用无线传感器网络。

2.3 最大似然估计法

最大似然估计（maximum likelihood estimation， MLE）是通用的数学估计方法，当测试数据量大时具有逼近特性，是三边测量法的扩展方法。

2.4 最小二乘法

最大似然估计求解时利用方程相减的方法消去二次项，这会损失已知坐标信息。如上述实数方程组（1）不存在任何一组值（x，y）使其满足方程组，那么可以通过找到一组值（x'，y'）使得方程组两边的值最接近，即求近似解。另外考虑到误差，误差的平方称为二乘方，误差最小就是最小二乘法。实际使用中常将最小二乘法常和最大似然法结合起来求解。

上述方法是节点计算的基本方法，随着研究不断深入和应用领域的不断扩展，涌现了很多改进方法，同时三维节点位和智能定位等新的定位技术的出现，使得节点计算方法得到了很大的优化。

3 基于测距的节点定位算法分析及比较

3.1 RSSI定位算法

RSSI定位算法基本思想通过接收到的射频信号（Radio Frequency，RF）强弱，根据传播衰减模型计算已知节点到未知节点的距离。RSSI算法优点是实现简单、硬件要求低和能耗低；缺点是易受实际环境的影响，导致平均定位误差较大。目前很多研究人员对该算法进行了改进并获得了较好的仿真和实际使用效果。

丁恩杰等[3]提出的基于RSSI和加权质心结合定位算法，该算法先通过RSSI测距得到4个信标节点到未知节点的距离，再任选其中3个距离为半径，以信标节点为圆心画圆得到3个圆的交叠区域，构成一个三角形，求出这个三角形的质心。按照该方法求出4个质心坐标，利用加权质心定位算法求出未知节点的坐标。仿真结果表明定位精度有很大的提高。

秦念庆[4]针对传统的基于RSSI定位算法存在不适定问题，提出基于Tikhonov正则化方法的多边定位算法，通过分析和大量实验最终确定最优信道衰减指数n为4，最优参考点数为5，通过实验发现基于Tikhonov正则化方法比最大似然估计法减少了定位误差，部分实验结果如表1所示。

该算法未增加硬件开销，但降低了距离误差和定位误差，算法性能优于传统的基于RSSI的最大似然估计法节点定位。

3.2 Hop-terrain迭代算法

Hop-terrain迭代算法是基于测距和无需测距相结合的定位方法。该算法分两步进行，第一步先用距离无关定位方法估算各节点的初始位置，然后用基于测距的定位方法对节点位置迭代计算以减小定位误差。实验表明，Hop-terrain算法能较好地改善稀疏信标节点问题和测量误差对节点定位的影响[5]，当网络连通度较低时，收敛性变差。

张松涛[5]提出的一个改进的基于距离约束迭代定位算法DCR（Distance Control Refinement），主要针对Hop-terrain算法在网络连通度比较低时，迭代过程收敛性下降，成功定位节点比例很低等问题。DCR算法定位过程中刷选上次迭代结果作为最新迭代结果。该算法也分为两步，第一步是节点坐标估算；第二步刷选节点位置进行迭代更新。仿真结果表明在连通度低的网络中，DCR算法节点定位成功率比Hop-terrain算法提高了20-30%，精度较高节点比例比Hop-terrain算法平均提高了6.5%[5]。

3.3 基于信号传输距离（TOA）定位算法

TOA（Time of Arrival）定位算法根据信号传播时间和速率计算信标节点到未知节点的距离。该算法分为三步。第一步测距。测量未知节点到信标节点的距离或方位，至少包含三个以上信标节点的距离信息；第二步定位。通过极大似然估计等方法计算；第三步修正。进一步矫正节点坐标，以保证精度。TOA算法测量精度较高，但要求节点之间严格的时间同步，因此对硬件需求高，成本和能耗高，应用在对精度要求高的专业领域。

刘鹏[6]提出的改进的TOA定位算法，信标节点同时发送两种不同速率的无线信号，未知节点根据接收的信号时间差计算出节点间的距离。该方法解决了时间严格同步和硬件延迟问题，仿真实验表明改进的TOA算法能获得更好的定位精度。

综合上述几类算法，从算法实现的难易程度、硬件需求、能耗、误差和需已知节点比例等方面进行比较，结果如表2所示。

除了上述基于距离的节点定位算法外，还有基于信号传输时间差（TDOA）的基本定位方法及其改进算法、基于信号到达角度（AOA）的基本定位方法及其改进算法等。总的来说，基于RSSI的定位算法具有实现简单、低成本等特点，众多研究人员对算法进行改进使其误差不断降低而更受欢迎。

4 总结

基于测距的定位方法是目前无线传感器网络使用最广泛的定位技术，它能获得较高定位精度而备受关注。本文首先对定位方法分类进行了综述，然后分析了经典的节点位置计算方法的特点，最后对无线传感器网络中几种具有代表性的基于测距的节点定位算法进行了详细分析和比较。

【参考文献】

[1]汪炀.无线传感器网络定位技术研究[D].中国科学技术大学，2007.4：19-21.

[2]于宁.无线传感器网络定位优化方法[D].北京邮电大学，2008.4：15.

[3]丁恩杰，乔欣，常飞，乔莉.基于RSSI的WSNs加权质心定位算法的改进[J].传感器与微系统，2013.7：53-56.

[4]秦念庆.基于RSSI的无线传感器网络多边定位算法研究[D].山东大学论文，2009.4：35-36.

[5]张松涛.无线传感器网络定位问题研究[D].华中科技大学，2010.5.

[6]刘鹏，宋迪，牛斗.WSN中一种改进的丁OA空间定位算法研究[J].微计算机信息，2009（25）：283-284.

[责任编辑：王楠]