定位算法调研一、定位算法的研究意义对于大多数应用，不知道传感器位置而感知的数据是没有意义的。
传感器节点必须明确自身位置才能详细说明在什么位置或区域发生了特定事件,实现对外部目标的定位和追踪。
用无线传感器网络进行目标的跟踪定位，就是综合传感器自身位置信息和网络节点与目标的关系信息，确定目标所处的地理位置。
对于移动目标而言，连续不断的定位就是跟踪。
传感器自身的位置信息，是实现目标定位跟踪的基础,而网络节点与目标的关系信息，则是实现目标定位跟踪的关键。
另一方面，了解传感器节点位置信息还可以提高路由效率,可以为网络提供命名空间,向部署者报告网络的覆盖质量,实现网络的负载均衡以及网络拓扑的自配置等。
b5E2RGbCAP尽管现有的许多定位系统和算法能够较好的解决WSN自身定位问题。
但依然存在如下一些问题: (1> 未知节点必须与锚点直接相邻,从而导致锚点密度过高。
(2> 定位精度依赖于网络部署条件。
(3> 没有对距离/角度测量误差采取抑制措施,造成误差传播和误差积累,定位精度依赖于距离/角度测量的精度。
(4> 依靠循环求精过程抑制测距误差和提高定位精度，虽然循环求精过程可以明显地减小测距误差的影响,但不仅产生了大量的通信和计算开销,而且因无法预估循环的次数而增加了算法的不确定性。
(5> 算法收敛速度较慢。
因此必须采用一定的机制改进或者避免以上问题，从而实现更高精度的WSN自身定位。
p1EanqFDPw二、定位算法的研究现状从1992年AT&T Laboratories Cambridge开发出室内定位系统Active Badge至今,研究者们一直致力于这一领域的研究。
事实上,每种定位系统和算法都用来解决不同的问题或支持不同的应用,它们在用于定位的物理现象、网络组成、能量需求、基础设施和时空的复杂性等许多方面有所不同。
DXDiTa9E3d根据定位算法中对节点位置的不同计算方式，可以分为集中式定位算法以及分布式定位算法。
集中式定位算法把所需信息传送到某个中心节点,并在那里进行节点定位计算的方式。
Doherty等[1]假定网络中存在一定比例的锚点，根据凸规划(convex optimization>来估计不确定节点的位置。
MDS-MAP[2]则采用了多维定标的方法来提高定位精度。
这两种算法都是典型的集中式定位算法，其后一系列的算法对该算法进行改进以提高节点定位精度。
分布式定位算法是指依赖节点间的信息交换和协调,由节点自行进行定位计算的方式。
质心算法中[3]，每个节点通过计算它所侦听到的锚点的中心位置来确定自身位置，如果锚点布置的比较好，则定位误差能够得到很好的改善。
APIT算法[4]中的节点侦听自己附近锚点的信号，根据这些信号，APIT算法把临近这个节点的区域划分为一个个相互重叠的三角形区域。
然后采用划分网格的方法找出自己所在的区域，如果能够侦听到足够多的锚点信息，这个区域可以变得很小，从而提高算法的定位精度。
RTCrpUDGiT根据定位算法中节点获取信息的不同方式，可以分为基于测距技术的定位和无须测距技术的定位(range-based versus range-free>两大类。
Range-Based定位通过测量节点间点到点的距离或角度信息,使用三边测量(trilateration>、三角测量(triangulation>或最大似然估计(multilateration>定位法计算节点位置；Range-Free定位则无须距离和角度信息,仅根据网络连通性等信息即可实现。
5PCzVD7HxARange-Based定位常用的测距技术有RSSI,TOA,TDOA和AOA。
RSSI(received signal strength indicator>虽然符合低功率、低成本的要求,但有可能产生 50%的测距误差[5]。
TOA(time of arrival>需要节点间精确的时间同步,无法用于分布式定位；TDOA(time difference on arrival>技术受限于超声波传播距离有限(WSN所使用的超声波信号通常传播距离仅为20~30英尺,因而网络需要密集部署>和NLOS问题对超声波信号传播的影响；AOA(angle of arrival>也受外界环境影响,而且需要额外硬件,在硬件尺寸和功耗上可能无法用于传感器节点。
除上述测距技术的局限性以外,range-based定位机制使用各种算法来减小测距误差对定位的影响,包括多次测量[6],循环定位求精[7],这些都要产生大量计算和通信开销。
所以,range-based定位机制虽然在定位精度上有可取之处,但并不适用于低功耗、低成本的应用领域。
jLBHrnAILg因功耗和成本因素以及粗精度定位对大多数应用已足够(当定位误差小于传感器节点无线通信半径的40％时,定位误差对路由性能和目标追踪精确度的影响分别小于15%和7%[8]>,range-free定位方案倍受关注。
DV-Hop[9，10]、凸规划[1]和MDS-MAP[2]等就是典型的range-free定位算法,其中MDS-MAP还可以在range-based条件下实现更精确的定位。
xHAQX74J0X在国内，彭刚等[14]提出了一种低成本的实用的定位策略。
该策略只是增加了少量的信标节点，通过节点之间的跳数信息，来估算出各节点到信标节点的距离，通过三角测距的原理，确定各个节点的具体位置。
LDAYtRyKfE在众多的定位算法中，存在一些比较典型的算法，如：➢凸规划定位算法[1]加州大学伯克利分校的Doherty等人将节点间点到点的通信连接视为节点位置的几何约束,把整个网络模型化为一个凸集,从而将节点定位问题转化为凸约束优化问题,然后使用半定规划和线性规划方法得到一个全局优化的解决方案,确定节点位置。
同时也给出了一种计算未知节点有可能存在的矩形区域的方法。
如图1所示,根据未知节点与锚节点之间的通信连接和节点无线射程,计算出未知节点可能存在的区域(图中阴影部分>,并得到相应矩形区域,然后以矩形的质心作为未知节点的位置。
Zzz6ZB2LtkAnchor node Unknown node图1 凸规划算法示意图凸规划是一种集中式定位算法,在锚节点比例为10%的条件下,定位精度大约为100%。
为了高效工作,锚节点必须部署在网络边缘,否则节点的位置估算会向网络中心偏移。
dvzfvkwMI1➢N-hop multilateration primitive定位算法[11]加州大学洛杉矶分校的在AHLos算法[12]的基础上,Andreas Savvides等人提出了n-hop multilateration primitive定位算法。
它不仅给出了判定节点是否可参与collaborative multilateration的充分条件,并使用卡尔曼滤波技术循环定位求精,减小了误差积累。
该算法分为3个阶段。
rqyn14ZNXI(1> 生成协作子树:根据判定条件,在网络中生成多个由未知节点和锚节点组成的限制条件完整或超限制条件的构形,称为协作子树.每个构形包括n个未知变量(未知节点的坐标>和至少n个非线性方程式,并确保每个未知变量拥有唯一解。
未被协作子树包含的节点在整个算法的后处理阶段进行定位。
EmxvxOtOco(2> 计算节点位置的初始估算:根据锚节点位置、节点间距离和网络连通性信息对每个节点的位置进行粗略估算,结果作为第3阶段的输入。
如图2所示,图中A,B为锚节点,C,D为未知节点,测得节点间距a,b,c,可推算出节点C的x坐标取值范围为。
但该方法有一个明显的缺点就是要求锚节点必须被部署在网络边缘。
SixE2yXPq5(3> 位置求精:根据预设的定位精度,使用卡尔曼滤波技术在每个协作子树范围内(每个节点位置有唯一解>对第2阶段的结果进行循环求精,可选用分布式或集中式两种计算模式。
6ewMyirQFL 实验显示,该算法的定位精度可达3cm(节点测距误差为1cm,锚节点比例为20%>。
图2 n-hop multilateration primitive中节点位置的初始估算➢MDS-MAP定位算法[2]MDS-MAP是一种集中式定位算法,可在range-free和range-based两种情况下运行,并可根据情况实现相对定位和绝对定位。
它采用了一种源自心理测量学和精神物理学的数据分析技术——多维定标(multidimensional scaling>,该技术常用于探索性数据分析或信息可视化。
kavU42VRUsMDS-MAP算法由3个步骤组成:(1> 首先从全局角度生成网络拓扑连通图,并为图中每条边赋予距离值。
当节点具有测距能力时,该值就是测距结果。
当仅拥有连通性信息时,所有边赋值为1。
然后使用最短路径算法,如Dijkstra或Floyd算法,生成节点间距矩阵。
y6v3ALoS89(2> 对节点间距矩阵应用MDS技术,生成整个网络的2维或3维相对坐标系统。
(3> 当拥有足够的锚节点时(2维最少3个,3维最少4个>,将相对坐标系统转化为绝对坐标系统。
实验显示,当网络的节点密度减小时,定位误差增大,并且无法定位的节点数量增加；而当网络连通度达到12.2时,几乎全部节点都可实现定位；在拥有200个节点(其中4个锚节点>,平均连通度为12.1的网络中,在range-free条件下,定位误差约为30%；而在range-based条件下,定位误差为16%(测距误差为5%>。
M2ub6vSTnP ➢APIT定位算法[4]APIT算法是一种无须测距技术的定位算法。
其基本思想是利用一些束缚条件把未知节点的位置确定在一块尽量小的区域内，然后取这块区域内的一点作为节点的位置<通常是该区域的质心位置）。
0YujCfmUCwAPIT算法中节点侦听自己附近锚点的信号，根据这些信号，APIT算法把临近这个节点的区域划分为一个个相互重叠的三角形区域。
然后采用划分网格的方法找出自己所在的区域，如果能够侦听到足够多的锚点信息，这个区域可以变得很小，从而提高算法的定位精度。
结果表明，该算法比其他基于锚点的算法需要更少的计算量以及更少的通信量。
eUts8ZQVRd➢质心定位算法[13]质心算法是由南加州大学的Bulusu N等提出的一种仅基于网络连通性的室外定位算法。
该算法的核心思想是：锚点周期性的向邻居节点广播Beacon信号，信号包括节点ID及位置信息。
当未知节点收到来自不同锚点的Beacon的数量超过预定门限值或者接收一定时间后，该节点就确定自身位置为这些锚点所组成的多边形的质心。