无线传感器网络相对定位算法综述

　　定位技术是无线传感器网络中的支撑技术，缺少位置数据的信息往往是没有意义的。随着无线传感器网络向节点数量多，铺设范围广，基础设施简单和硬件成本低的方向发展，如何在减少节点硬件组件，算法实现简单的同时获得相对准确的定位信息已成为主要研究的课题之一。现有定位算法根据定位过程中是否需要使用已知位置的信标节点，分为绝对定位算法和相对定位算法。前者一般是在待测区域事先布置一定比例的锚节点，这些节点通过GPS或是其他方法已得知自身绝对坐标，其余的未知节点通过与这些信标节点通信获得自身坐标。相对定位算法则完全不需要事先布置信标节点，通过算法制定的方案，选取一定数量的未知节点建立相对坐标，其余的节点通过节点之间的协作关系和消息传输获取自身在相对坐标系中的相对位置实现定位。相对定位算法无需信标节点和基础设施，硬件成本低，并且不会受到复杂环境对远距离信号传输的影响，适合于对节点硬件，能耗以及环境适应性有很高要求的无线传感器网络应用。

　　2. 定位算法分析

　　在无线传感器网络中，节点定位一般包括三个部分：距离测定、位置计算和定位过程。

　　(1) 距离测定：就是获得两个节点之间距离的方法，可分为基于测距和无需测距。基于测距的算法(range-based)通过节点自身携带的测距功能直接测量两个节点之间的距离。当前比较重要的测距方法主要是到达时间(TOA)、到达时间差(TDOA)和信号强度测距(RSSI)或者到达角度(AOA)。

　　TOA(Time of Arrival)：该技术通过测量信号传播时间来测量距离。使用TOA 技术最基本的定位系统是GPS，GPS 系统需要昂贵、高性能的电子设备来精确同步卫星时钟。因WSN节点硬件尺寸、价格和功耗限制，GPS 和其他TOA 技术无法广泛应用于WSN。
　　
　　TDOA(Time Difference On Arrival)：TDOA测距技术被广泛应用于WSN定位方案中。通过记录两种不同信号(常使用RF和超声波)到达时间差异，基于已知信号传播速度，直接把时间转化为距离。已有多种定位算法使用TDOA实现测距。但该技术受限于超声波传播距离有限(超声波信号通常传播距离仅为20-30英尺，因而网络需要密集部署)和NLOS(Non-Line-Of-Sight)问题对超声波信号的传播影响。虽然已有发现并减轻NLOS影响的技术，但都需要大量计算和通信开销，不适用于低功耗的WSN应用中。
   
　　RSSI(Received Signal Strength Indicator)：已知发射功率，在接收节点测量接收功率，计算传播损耗，使用理论或是经验的信号传播模型将传播损耗转化为距离，该技术主要使用RF 信号。因传感器节点具有无线通信能力，故是一种低功率、廉价的测距方式，RADAR、SpotON等许多项目中使用了该技术。他的主要误差来源是环境影响所造成的信号传播模型的建模复杂性；反射、多径传播、NLOS)、天线增益等问题都会对相同的距离产生显著不同的传播损耗。通常将其看为一种粗糙的测距技术，它可能产生50%的测距误差。
   
　　AOA(Angle of arrival)：该技术是估算邻居节点发送信号方向，可通过天线阵列或多个接收器来实现，除定位外，还能提供方向信息，如MIT 的The Cricket Compass 等项目中都使用AOA 技术。

　　无需测距的算法(range-free)不需要节点自身的测距设备，通过跳数或是其他信息估计自身到选定的信标节点的距离值，由于是估计得到的数值，相对于基于测距的算法获得的距离值误差偏大。

　　(2) 位置计算：在获取上述距离值之后，节点需要通过位置计算的方法计算得到坐标值。现有的算法一般采用三边测量法和三角测量法计算坐标。 

图1 三边测量法示意图

　　如图1 所示，在未知节点获得三个以上的信标节点距离值之后，就可以通过式(1)、式(2)和式(3)计算自身坐标。式中，(xa , ya)、(xb , yb)、(xc , yc)分别是三个信标节点的坐标，da、db、dc 是未知节点到三个信标节点的距离。

　　式(1)经过线性化，可得线性方程式(2):

　　式(2)中的N 是由于存在测距误差加入的参数，它是根据测距误差的分布形式存在的一个随机误差向量。如果未知节点测得的到信标节点的距离值大于三个，则可以加入(1)式中，进行更精确的计算。三角测量法与三边测量法类似，通过获取相对三个信标节点的角度值，计算得到图1中三个圆的半径，再经过三边测量法计算得到坐标。三边测量法和三角测量法由于涉及大量的矩阵运算和最小二乘的运算，计算量较大，针对这种情况，加州大学洛杉矶分校的Andreas Savvides等人提出的n-hop multilaterationprimitive定位算法中提出的最大最小值法通过简单的折线运算估计未知节点的位置，如图2所示。

图2 最大最小值法示意图

　　图中A点和B点为信标节点，C点为未知节点。在获得C点到A点和B点的折线距离a、b、c之后，在三角形ACK中，利用斜边AC的长度a代替直角边AK的长度，从而K点移动到K/点，B点类似，从而有：

　　最大最小值法估计得到的坐标值由于是取矩形区域的质心代替实际位置，若测得的距离值本身就存在较大的误差，那么得出的结果没有三边定位精确，在一些要求精度不是很严格的情况或者是结果经过求精之后，可以满足需要。

　　(3) 定位过程：不同算法根据上面两步获得的有限的距离值和部分节点的坐标，计算其余未知节点的机制。由于各种算法采取的策略不同，各种性能参数的区别主要由这一步决定。在分析定位算法的时候，一般要针对具体情况综合考虑上述三个方面来考察算法性能。

　　3. 典型的相对定位算法

　　3.1 SPA 算法

　　瑞士洛桑联邦工业大学的Srdjan Capkun 等人最早针对没有基础设施的移动无线自组网，提出SPA(self–positioning algorithm)算法[23]。它以网络中节点密度最大的地方选取一个参考点作为全局相对坐标系的原点，其余每个节点分别通过测距功能测得邻居节点之间的距离值，如图3所示，实线表示二者距离可测得，虚线表示二者不是邻居节点。每个节点在邻居节点中选取两个点A、B，选取原则是这两个点本身也是邻居节点，并且三个点不在同一直线上。以直线OA作为x 轴，以B点在OA上的投影BxB为y 轴正方向建立局部相对坐标系。所有的局部坐标系建立完成后，相邻的坐标系通过坐标变换实现坐标统一，最终所有节点都变换形成以选取的参考点为原点的坐标系实现定位。由于每个节点都要参与多次的坐标变换，计算量和通信开销都非常大。此算法开始是针对无线自组网提出的，不太考虑功耗问题，但是用到无线传感器网络当中，这种通信开销和节点数量呈指数比上升的算法需要根据实际情况进行改进。

图3 SPA算法示意图

　　3.2 聚类 SPA 算法

　　美国仁斯利尔理工学院Rajagopal Iyengar 等人提出的聚类SPA(clustering-basedself–positioning algorithm)算法[24]是针对上述SPA算法通信量过大而提出的改进算法。首先通过运行随机的定时器选取网络中的主节点，主节点一跳范围内的其他节点成为它的从节点。每个主节点使用SPA算法中相似的方法建立局部相对坐标系，并计算得到其余从节点的局部坐标。完成第一步之后，相邻的局部坐标系依据ID号由大到小的原则进行坐标变换，最终以ID号最小的主节点为原点建立相对坐标系，从而实现定位。由于算法以节点簇为单位进行坐标变换，计算量和通信量相对SPA算法来说都得到大幅度减少，基本与节点个数呈线性比。该算法由于簇之间变换要求拓扑结构比较规则，通信无障碍，所以在地形复杂，节点之间通信容易产生冲突的环境下，定位效果不是很好，节点覆盖率比较低。

… …

　　5. 结论

　　相对定位算法由于无需事先布置锚节点，很大程度上节约了硬件成本，受外界信号干扰的影响较小，适合用于对节点硬件成本，算法计算能耗以及节点分布有严格限制的无线传感器网络。本文从通信量、覆盖率和定位精度三个主要的性能指标对现有的几种典型定位算法进行了综合分析，通过图表的形式比较节点密度和节点分布两个方面对算法的影响，阐述了各算法在不同的节点布置环境下性能对比，说明了算法具体的适用范围，并提出了适当的改进方案。目前存在的算法大都需要在节点密度较高的环境下能获得比较理想的定位效果，如何通过节点之间的消息传输和节点协作使得算法在某些节点密度较低的环境中也能实现定位精度和节点覆盖率二者很好结合的问题，将是相对定位算法需要主要关注的方面。 


完整文章请点击：无线传感器网络相对定位算法综述