无线传感器网络定位技术综述

1 引 言

无线传感器网络作为一种全新的信息获取和处理技术在目标跟踪、入侵监测及一些定位相关领域有广泛的应用前景。然而， 无论是在军事侦察或地理环境监测， 还是交通路况监测或医疗卫生中对病人的跟踪等应用场合， 很多获取的监测信息需要附带相应的位置信息， 否则， 这些数据就是不确切的，甚至有时候会失去采集的意义， 因此网络中传感器节点自身位置信息的获取是大多数应用的基础。首先， 传感器节点必须明确自身位置才能详细说明“在什么位置发什么了什么事件”， 从而实现对外部目标的定位和跟踪； 其次， 了解传感器节点的位置分布状况可以对提高网络的路由效率提供帮助， 从而实现网络的负载均衡以及网络拓扑的自动配置， 改善整个网络的覆盖质量。因此， 必须采取一定的机制或算法来实现无线传感器网络中各节点的定位。

无线传感器网络定位最简单的方法是为每个节点装载全球卫星定位系统（GPS） 接收器， 用以确定节点位置。但是， 由于经济因素、节点能量制约和GPS 对于部署环境有一定要求等条件的限制， 导致方案的可行性较差。因此， 一般只有少量节点通过装载GPS 或通过预先部署在特定位置的方式获取自身坐标。另外， 无线传感器网络的节点定位涉及很多方面的内容， 包括定位精度、网络规模、锚节点密度、网络的容错性和鲁棒性以及功耗等， 如何平衡各种关系对于无线传感器网络的定位问题非常具有挑战性。可以说无线传感器网络节点自身定位问题在很大程度上决定着其应用前景。因此， 研究节点定位问题不仅必要， 而且具有很重要的现实意义。

2 WSN 定位技术基本概念

2.1 定位方法的相关术语

1） 锚节点（anchors）： 也称为信标节点、灯塔节点等， 可通过某种手段自主获取自身位置的节点；

2） 普通节点（normal nodes）： 也称为未知节点或待定位节点， 预先不知道自身位置， 需使用锚节点的位置信息并运用一定的算法得到估计位置的节点；

3） 邻居节点（neighbor nodes）： 传感器节点通信半径以内的其他节点；

4） 跳数（hop count）： 两节点间的跳段总数；

5） 跳段距离（hop diSTance）： 两节点之间的每一跳距离之和；

6） 连通度（cONnectivity）： 一个节点拥有的邻居节点的数目；

7） 基础设施（infrastructure）： 协助节点定位且已知自身位置的固定设备， 如卫星基站、GPS 等。

2.2 定位方法的性能评价标准

无线传感器网络定位性能的评价标准主要分为7 种， 下面分别进行介绍。

1） 定位精度。定位技术首要的评价指标就是定位精确度， 其又分为绝对精度和相对精度。绝对精度是测量的坐标与真实坐标的偏差， 一般用长度计量单位表示。相对误差一般用误差值与节点无线射程的比例表示， 定位误差越小定位精确度越高。

2） 规模。不同的定位系统或算法也许可以在一栋楼房、一层建筑物或仅仅是一个房间内实现定位。

另外， 给定一定数量的基础设施或一段时间， 一种技术可以定位多少目标也是一个重要的评价指标。

3） 锚节点密度。锚节点定位通常依赖人工部署或使用GPS 实现。人工部署锚节点的方式不仅受网络部署环境的限制， 还严重制约了网络和应用的可扩展性。而使用GPS 定位， 锚节点的费用会比普通节点高两个数量级， 这意味着即使仅有10%的节点是锚节点， 整个网络的价格也将增加10 倍， 另外， 定位精度随锚节点密度的增加而提高的范围有限， 当到达一定程度后不会再提高。因此， 锚节点密度也是评价定位系统和算法性能的重要指标之一。

4） 节点密度。节点密度通常以网络的平均连通度来表示， 许多定位算法的精度受节点密度的影响。

在无线传感器网络中， 节点密度增大不仅意味着网络部署费用的增加， 而且会因为节点间的通信冲突问题带来有限带宽的阻塞。

5） 容错性和自适应性。定位系统和算法都需要比较理想的无线通信环境和可靠的网络节点设备。

而真实环境往往比较复杂， 且会出现节点失效或节点硬件受精度限制而造成距离或角度测量误差过大等问题， 此时， 物理地维护或替换节点或使用其他高精度的测量手段常常是困难或不可行的。因此， 定位系统和算法必须有很强的容错性和自适应性， 能够通过自动调整或重构纠正错误， 对无线传感器网络进行故障管理， 减小各种误差的影响。

6） 功耗。功耗是对无线传感器网络的设计和实现影响最大的因素之一。由于传感器节点的电池能量有限， 因此在保证定位精确度的前提下， 与功耗密切相关的定位所需的计算量、通信开销、存储开销、时间复杂性是一组关键性指标。

7） 代价。定位系统或算法的代价可从不同的方面来评价。时间代价包括一个系统的安装时间、配置时间、定位所需时间； 空间代价包括一个定位系统或算法所需的基础设施和网络节点的数量、硬件尺寸等； 资金代价则包括实现一种定位系统或算法的基础设施、节点设备的总费用。

上述7 个性能指标不仅是评价无线传感器网络自身定位系统和算法的标准， 也是其设计和实现的优化目标。为了实现这些目标的优化， 有大量的研究工作需要完成。同时， 这些性能指标相互关联， 必须根据应用的具体需求做出权衡以设计合适的定位技术。[page]

2) 基于信号到达角度的方法

AOA 测距技术依靠在节点上安装天线阵列来获得角度信息。由于大部分节点的天线都是全向的， 无法区分信号来自于哪个方向。因此该技术需要特殊的硬件设备如天线阵列或有向天线等来支持。

优点： 能够取得不错的精度。

缺点： 传感节点最耗能的部分就是通信模块，所以装有天线阵列的节点的耗能、尺寸以及价格都要超过普通的传感节点， 与无线传感器网络低成本和低能耗的特性相违背， 所以实用性较差。

关于AOA 定位的文献比较少，最早提出在室内采集方向信息， 并以此实现定位的方法，它的硬件部分包括微控制器、RF 接收器、5 个排成“V”型的超声波接收器， 其测量误差精度为5°。随后， 一些学者提出了在只有部分节点有定位能力的情况下确定所有节点的方向和位置信息的算法。

3) 基于接收信号强度的方法

RSSI 是在已知发射功率的前提下， 接收节点测量接收功率， 计算传播损耗， 并使用信号传播模型将损耗转化为距离。

优点： 低成本。每个无线传感节点都具有通信模块， 获取RSSI 值十分容易， 无需额外硬件。

缺点： 1) 锚节点数量需求多。由于RSSI 值在实际应用中的规律性较差， 使得利用RSSI 信息进行定位的算法在定位精度以及实用性上存在缺陷。所以为了达到较高的定位精度， 利用RSSI 信息进行定位的算法通常需要较多数量的锚节点。2) 多路径反射、非视线问题等因素都会影响距离测量的精度。

早期的RSSI 距离测量方法有Hightower 等人设计的室内定位SpotON tags 系统， 通过RSSI 方法来估计两点间的距离， 通过节点间的相互位置来进行定位， 在边长3 m 的立方体内， 其定位精度在1 m 以内。目前， 基于RSSI 值的距离测量方法可以分为2 种， 一种是需要预先测试环境信息的方法， 即在实验开始前， 对定位的区域进行大量的RSSI 值测试，将不同点得到的RSSI 值保存到数据库中， 建成场强图或拟合曲线， 在实际测试时查询和调用。另外一种是无需预先测试环境信息的方法， 直接在定位区域进行节点布置和定位， 如双曲线模型法，迭代的分布式算法， 结合露珠洪泛思想引入RSSI 机制的HCRL(hop-count-ratio based localization)算法等。

总体来说， 需要预先测试环境参数的方法在实际定位中计算量小， 这类方法只需要简单的查表或根据拟合曲线进行计算， 其缺点是实验前需要做大量的准备工作， 而且一旦环境改变则预先建立的模型将不再适用。无需预先测试环境参数的方法需要定位引擎的计算操作， 往往具有复杂的计算过程，但适应性较强。

以上几种测距方法各有利弊， 以2009 年发表的基于测距法的文献来看， 研究RSSI 方法的大约占了以上几种方法总数的52%, TOA 方法25%, TDOA 方法13%和AOA 方法10%, 其比例图如图1 所示， 从实用性的角度来看， 基于RSSI 的定位方法更简便易行， 因此， 基于RSSI 测距方法的研究占基于测距算法研究总数的一半以上。

图1 各类方法研究比例图

3.1.2 节点坐标计算方法

无线传感器节点定位过程中， 当未知节点获得与邻近参考节点之间的距离或相对角度信息后， 通常使用以下原理计算自己的位置。

1) 三边测量法是一种基于几何计算的定位方法，如图2 所示， 已知3 个节点A, B, C 的坐标以及3 点到未知节点的距离就可以估算出该未知点D 的坐标，同理也可以将这个结果推广到三维的情况。

2) 三角测量法也是一种基于几何计算的定位方法， 如图3 所示， 已知3 个节点A, B, C 的坐标和未知节点D 与已知节点A, B, C 的角度， 每次计算2 个锚节点和未知节点组成的圆的圆心位置如已知点A, C与D的圆心位置O, 由此能够确定3 个圆心的坐标和半径。最后利用三边测量法， 根据求得的圆心坐标就能求出未知节点D 的位置。

图2 三边测量法原理示意图

图3 三角测量法原理示意图

[page]

3) 极大似然估计法。如图4 所示， 已知n 个点的坐标和它们到未知节点的距离， 列出坐标与距离的n 个方程式， 从第1 个方程开始， 每个方程均减去最后一个方程， 得到n?1 个方程组成的线性方程组，最后用最小二乘估计法可以得到未知节点的坐标。

图4 极大似然估计法原理示意图

4) 极小极大定位算法， 在无线传感器网络定位中也被广泛使用。如图5 所示， 计算未知节点与锚节点的距离， 接着锚节点根据与未知节点的距离d, 以自身为中心， 画以2d 为边长的正方形， 所有锚节点做出的正方形中重叠的部分的质心就是未知节点的坐标。针对极小极大定位算法对锚节点密度依赖过高的问题， 有学者利用锚节点位置信息提出了分步求精定位算法， 该算法在只利用适量的锚节点的情况下可达到较高定位精度。

图5 极小极大定位算法原理示意图

文献[35]在12 m×19.5 m 的范围内对上述三边测量法、极大似然估计法和极小极大法方法的计算量和精度进行了测试。实验表明， 极大似然估计法的计算量最大， 锚节点小于10 个时， 极小极大法的计算量最小， 在锚节点较少情况下， 三边法和极小极大法的精确度较高， 而当锚节点超过6 个时， 极大似然估计法精确度更高。因此， 在计算坐标时要根据实际情况合理选择坐标计算方法。另外， 针对现存的定位算法都是假设信标节点不存在误差， 与真实情况不符的情况， 文献[36]提出信标优化选择定位算法(OBS)， 即通过减小定位过程中的误差传递来提高定位精度。

3.2 基于非测距的算法

基于非测距的算法与测距法的区别在于前者不直接对距离进行测量， 而是使用网络的连通度来估计节点距锚节点的距离或坐标， 由于方法的不确定性， 基于非测距的方法众多。下面按时间顺序，介绍部分典型非测距定位算法。

Bulusu 等人提出了一个单跳， 低功耗的算法，它利用锚节点的连通性来确定坐标。未知节点的坐标通过计算无线电范围内所有节点的质心获得。节点将自己定位在与它们表现相近节点的质心处， 该算法虽然简单， 但误差较大， 需要的锚节点密度较高。约90%节点的定位精度在锚节点分布间距的1/3以内。

He 等人提出了APIT 算法， 目标节点任选3 个相邻锚节点， 测试未知节点是否位于它们所组成的三角形中。使用不同锚节点组合重复测试直到穷尽所有组合或达到所需定位精度。最后计算包含目标节点的所有三角形的交集质心， 并以这一点作为目标节点位置， 该算法需要较高的锚节点密度， 其定位精度为40%。

Niculescu 等人提出了DV-Hop 定位算法， 它从网络中收集相邻节点信息， 计算不相邻节点之间最短路径。DV-Hop 算法使用已知位置节点的坐标来估测一个跳跃距离， 并使用最短路径的跳跃距离估计未知节点和锚节点的距离， 该算法仅适用于各向同性的密集网络， 当锚节点密度为10%时， 定位误差为33%。

Radhika 等人提出的Amorphous Positioning 算法，使用离线的跳跃距离估测， 同DV-Hop 算法一样， 通过一个相邻节点的信息交换来提高定位的估测值，需要预知网络连通度， 当网络连通度为15 时， 定位精度20%。

Savvides 等人介绍了一种N-Hop multilateration算法， 使用卡尔曼滤波技术循环求精， 该算法避免了传感器网络中多跳传输引起的误差积累并提高了精度， 节点通信距离为15 m, 当锚节点密度为20%,测距误差为1 cm 时， 定位误差为3 cm。

Capkun 等人提出了self-positioning algorithm(SPA)， 该算法首先根据通信范围在各个节点建立局部坐标系， 通过节点间的信息交换与协调， 建立全局坐标系统， 网络中的节点可以在与它相隔N 跳的节点建立的坐标系中计算自己的位置。

综上可知， 非测距算法多为理论研究， 其定位精度普遍较低并且与网络的连通度及节点的密集程度密切相关， 因此， 其适用范围有一定的局限性， 在进行无线传感器网络定位技术研究过程中应更多地考虑基于测距的定位算法。

[page]

4 新型WSN 定位研究分析

除了传统的定位方法， 新型的无线传感器网络定位算法也逐渐出现， 如利用移动锚节点来定位未知节点、在三维空间内定位未知节点、以及采用智能定位算法来提高定位精度等， 下面分别介绍。

4.1 基于移动锚节点的定位算法

利用移动锚节点定位可以避免网络中多跳和远距离传输产生的定位误差累计， 并且可以减少锚节点的数量， 进而降低网络的成本。如MBAL(mobilebeacon assisted localization scheme)定位方法， 锚节点在移动过程中随时更新自身的坐标， 并广播位置信息。未知节点测量与移动节点处于不同位置时的距离， 当得到3 个或3 个以上的位置信息时， 就可以利用三边测量法确定自己的位置， 进而升级为锚节点。此外， 移动锚节点用于定位所有未知节点所移动的路径越长则功耗越大， 因此对移动锚节点的活动路径进行合理规划可以减小功耗。

文献[48]提出了一种基于加权最小二乘法的移动锚节点定位距离估计算法， 作者首先建立一个移动模型， 锚节点沿着线性轨迹移动， 使用加权最小二乘法来减小距离估计误差， 并在Cramér-Raobound(CRB) 的基础上分析了距离估计的最小误差边界， 该算法在距离估计和位置估计方面都有较好的性能。

利用移动锚节点自身的可定位性和可移动性可定位网络局部相关节点， 但移动锚节点的路径规划算法和采取的定位机制需要深入考虑。2009 年发表的关于WSN 定位的文章中， 约25%是关于移动节点定位的。

4.2 三维定位方法

随着传感器网络的空间定位需求不断提升， 三维空间场景下的定位也成为了一个新的研究方向。

目前的三维定位算法包括基于划分空间为球壳并取球壳交集定位的思想， 提出的对传感器节点进行三维定位的非距离定位算法APIS(approximatepoint in sphere) 。在此基础上针对目前三维定位算法的不足， 提出的基于球面坐标的动态定位机制， 该机制将定位问题抽象为多元线性方程组求解问题，最终利用克莱姆法则解决多解、无解问题。建立了WSN 空间定位模型并结合无线信道对数距离路径衰减模型， 为解决不适定型问题提出了Tikhonov 正则化方法， 并结合偏差远离方便的得到了较优的正则化参数， 在3.5 m×6 m×3 m 的区域内定位精度可控制在2 m。

三维定位方法可扩展WSN 的应用场合， 目前三维定位在许多方面还有待完善， 如获取更准确的锚节点需要寻求更精确的广播周期和消息生存周期， 缩减定位时间需要改进锚节点的选择和过滤机制等。

4.3 智能定位算法

随着电子技术的发展和芯片计算能力的提高，传感器网络节点本身的性能也有提升， 复杂算法也可以在网络中实现。因此， 智能定位算法也纷纷被提出。

对于无线传感器网络的户外三维定位， 将锚节点固定在直升机上通过GPS 实时感知自身位置， 采用基于RSSI 的测距方法， 利用粒子滤波定位技术实现定位， 该方法不需要任何关于未知节点的先验知识， 非常适合应用于户外定位。

神经网络对于解决无线传感器网络的定位问题是一个切实可行的办法， 将3 种神经网络： 多层感知神经网络， 径向基函数神经网络和递归神经网络与卡尔曼滤波的2 个变形进行比较， 可以根据不同情况下的定位需求灵活选择定位方法。使用神经网络和网格传感器训练的灵活的模型， 可以提高定位精度， 且不需要额外的硬件支持。网络训练每隔一段时间进行一次更新来最小化误差， 并且通过增加网格节点密度来提高定位精度。

对于节点定位中的非视距问题， 常规的办法是采用机器学习中的支持向量回归(support vector regression,SVR) 方法进行定位以降低误差， 但其定位精度仍然受到一定的非视距误差影响， 为了降低这种影响， 研究人员提出了基于直推式回归的定位算法。利用锚节点的坐标和TOA 信息并借用核函数直接推导出未知节点的位置， 进一步提高定位 精度。

虽然智能定位算法已经成为一个新的研究方向，但由于WSN 网络本身属于低能耗的网络， 单个节点的计算能力还比较低， 目前智能定位算法不普遍适用于实际的WSN 定位系统， 但随着低功耗技术、微处理器技术、FPGA 技术的发展， 智能定位算法将在未来的定位系统中得到广泛的应用。

5 研究前景与应用分析

截至目前， 无线传感器网络定位研究已广泛开展并取得了许多研究成果， 但仍存在着一些没有被解决或被发现的问题， 目前最为关键的问题仍然是WSN 节点的能耗问题， 一切的定位算法应该在精度和能量消耗上选取一个较为折衷的效果。下面将对目前存在的问题及相应可能的解决方案进行介绍。

1) 实用性差。大部分基于非测距的定位算法只是停留在理论研究阶段， 且大都是在仿真环境下进行的， 需要假设很多不确定因素， 而这些因素在实际应用中往往不能满足， 则这些算法就失去了实际的意义。因此定位算法的设计应该更多的从实际应用上考虑， 结合实际应用情况设计实用的定位算法。

2) 应用环境单一。多数的算法都是针对特定的应用场景进行设计的， 也就是说， 每个算法都只能解决特殊的问题或应用于特定的场景， 一旦环境发生变动， 算法或系统的测量误差将增大甚至不再适用。因此， 探索更具通用性的定位算法或定位系统， 将其应用于更为复杂多变的环境中是一项新的挑战。

3) 受硬件限制。在实际定位中， 一些算法由于受到传感器节点硬件成本和性能的限制， 如某些算法需要在定位节点上增加GPS, 超声波收发器， 有向天线阵列等设备， 增加了节点硬件成本， 阻碍了其在实际定位系统中的应用。因此， 算法设计应多考虑WSN 节点的实际情况， 如只在部分节点上增加额外硬件， 或根据实际节点资源受限情况采用其他定位算法等。

4) 能量受限。测量精度、容错性和能量消耗等问题也是目前无线传感器网络研究的热点， 更是定位技术研究的热点。通常情况下， 高测量精度和低能量消耗不可兼得， 往往需要在测量精度和能量消耗上进行有效的折衷。因此， 可以在提高储能设备的容量， 或利用可能的外界环境资源为节点提供能量方向进行研究， 另外， 提出高效、节能、符合实际情况的无线传感器网络定位算法将具有现实的意义。

5) 安全和隐私问题。在大范围部署的无线传感器网络中， 安全和隐私的问题也是一个主要的研究方向。一方面， 一些应用需要节点位置信息， 另一方面， 向一些不需要知道位置的节点透露位置信息则会使网络面临安全问题。此外， 鉴于无线传感器网络的性质， 集中式算法在后台处理定位程序也使得节点的位置信息通过层层传递被过多的节点所知晓，因此分布式算法相对于集中式算法可以减少信息传递次数， 增强网络安全性， 另外， 在网络通信中使用信息加密也可以提高网络安全性。就2009 年发表的定位相关文章来说， 每4 篇发表的文章中就有1 篇提出的是分布式算法。

未来的无线传感器网络定位在解决上述问题之后将广泛应用于各类领域， 包括安全定位、变化的环境、三维空间等。

6 结 论

结合近年来无线传感器网络定位技术的发展状况， 对无线传感器网络定位的基本概念、评价标准以及国内外研究现状进行了概述， 重点对基于测距和基于非测距的无线传感器网络定位算法进行了分析， 并列举了一些新型WSN 定位的算法， 总结了目前无线传感器网络定位领域研究存在的问题和一些可以研究的内容和方向。希望本文能够为无线传感器网络定位相关领域的研究者提供一些参考和借鉴。