为了为用户提供有用的检测服务，无线传感器网络的许多应用要求节点了解自己的位置信息。在许多情况下，没有节点位置信息的监控数据毫无意义。例如，对于森林火灾检测、天然气管道监测等应用，当事件发生时，人们关心的第一个问题是事件发生在哪里，如果只知道火灾但不知道火灾的具体位置，监测没有实质性意义，所以节点位置信息对许多场合至关重要。
在许多情况下，传感器节点随机部署在某个区域，节点无法提前知道自己的位置，因此需要通过定位技术获取自己的位置信息。目前最常见的定位技术是GPS（Global Positioning System）了，它能够通过卫星对节点进行定位，并且能够达到比较高的精度。因此，定位传感器节点最容易想到的方法是为每个节点配备一个GPS但这种方法不适用于传感器网络，主要原因如下：
1）GPS接收器通常能耗高，但对于无线传感器网络中的节点，一般能耗有限，每个节点都有一个GPS接收器将大大缩短网络寿命；
2）GPS接收器成本相对较高，无线传感器网络中的每个节点都配备了一个GPS接收器成本高，尤其是大型无线传感器网络；
因此，有必要研究适合无线传感器网络的定位技术。以下分为两部分：1）节点定位的基本概念；2）节点定位的基本思路；3）常用算法。
一.节点定位的基本概念
无线传感器网络中的节点定位是指通过一定的定位技术，根据网络中少数已知节点的位置信息确定网络中其他节点的位置信息的过程。
在无线传感器网络中，节点通常可以分为信标节点（beacon node or anchor node）和未知节点（unknown node），信标节点又称锚节点或参考点，未知节点又称普通节点。信标节点是位置信息已知的节点，未知节点是未知信息未知的节点。信标节点一般所占比例很小，通常通过手工配置或者配备GPS接收器获取自己的位置信息。
此外，还有一个节点叫邻居节点（neighbor node），邻居节点是指传感器节点通信半径内的其他节点。
以下是几个常用术语：
到达时间（Time of Arrvial，TOA），从一个节点到另一个节点所需的时间 到达时间差（Time Diffrential of Arrival，TDOA），从一个节点到另一个基点所需的时间差异 到达角度（Angle of Arrival，AOA），与自己轴的角度相比，节点接收到的信号 接收信号强度（Received Sinnal Strength，RSS），节点接收到无限信号强度的大小，也有称Received Sinnal Strength Indicator（RRSI），两个意思基本相同 视距关系（Light of Sight，LOS），两个节点之间没有障碍物，可以直接通信 非视距关系（Non Light of Sight，NLOS），两个节点之间有障碍物，不能直接通信 跳数（Hop Count），两个节点之间的跳段之和 二.节点定位技术的基本思路
节点定位有两个基本思路：
1.基于测距（Range-based）：假设传感器网络中某些节点的位置信息已知，其他节点的位置信息通过某些手段进行估计。通常有两个步骤：
测距 位置估算 为了通过信标节点获取未知节点的位置信息，在获得未知节点的位置信息之前，必须确定信标节点与未知节点的距离。
假如信标节点A的位置已知（x1，y1)节点M位置未知，最简单的想法是要求M位置:假设B位置为（x，y），A到B的距离是d1，则有
d12=（x-x1）2 （y-y1）2
显然，只有一个方程是不可能的y如果有两个信标节点呢？
这样，还有另一个方程：d22=（x-x2）2 （y-y2)2，此时可以解决方程组x和y，但是此时x和y有两个组解，x和不能唯一确定y因此，需要考虑另一个信标节点：
这样，唯一可以确定x和y这是最基本的定位思想。这里举的例子是距离和角度。
一般情况下，至少需要知道未知节点与信标节点之间的三组距离或角度值，然后通过位置估计确定位置。
通常有四种测距方法：
1)基于到达时间（TOA）的测距
该方法根据已知信号的传输速度和发送节点与接收节点之间信号的传输时间来估计距离。该方法需要非常准确地获得发送节点和接收节点之间的传输延迟，这更困难，非常困难，不适合无线传感器网络。
2)基于到达时差（TDOA）的测距
在这种方法中，节点发送两个不同传输速度的信号，接收节点根据两个信号到达的时差和传输速度计算距离。如果两个信号的传输速度是v1和v2.到达时间分别为t1和t2.从发送节点到接收节点的距离是d，则有：
t1-t2=d/v1-d/v2
可得d=（t1-t2）v1v2/（v2-v1）
3)基于到达角度（AOA）的测距
该方法根据接收信号到达时与自己轴的角度计算。该方法对硬件成本要求高，需要天线阵列，不适合无线传感器网络
4)基于接收信号的强度（RSS）的测距
信号在传输过程中会衰减，无线信号的发射功率与接收功率有一定的映射关系，因此可以利用这种关系来估计距离，
获得距离后，可以来估算位置。常用的位置估算方法有以下两种:
1)三边测量法
上述例子中的位置估算方法是三边测量法，这里就不赘述了。
至于某些文献上提到的三角测量法个人觉得跟三边测量法是一回事，就不再介绍了。
3)最大看似估计法
已知n个节点的坐标是（x1，y1），（x2，y2）…（xn，yn），它们与未知节点M的距离分别为d1，d2…dn，则有：
（x-x1）2 （y-y1）2=d12
（x-x2）2 （y-y2）2=d22
…
（x-xn）2 （y-yn）2=dn2
用第一个方程依次减去最后一个方程：
x12-xn2 y12-yn2 dn2-d12=2x(x1-xn) 2y(y1-yn)
…
xn-12-xn2 yn-12 dn2-dn-12=2x(xn-1-xn) 2y(yn-1-yn)
可以表示成 AX = B
其中A = B=X =（x,y)T
2.无需测距（range-free）
一般来说，无需测距的方法是利用网络连通性或拓扑结构来估计距离，然后利用三边测量法或大似然估计来估计位置。
三.常见算法
1.基于测距（range-based）
1）AHLos 算法
该算法是基于到达时间差的测距。信标节点首先用两个射频信号向邻居节点广播信息，然后根据到达时间差估算邻居节点的距离。收到三个信标节点的消息后，根据三边测量法估算位置。邻居节点确定位置后，将其转换为信标节点，并将上述过程重复到邻近节点的广播信息，直到所有节点定位完成。
2）RADAR算法
该算法是基于的RSS基于测距RSS有两种模型：经验模型和信号传输模型
先说经验模型:
在经验模型中，节点分散在一定区域，所有未知节点都可以直接与信标节点通信，如图所示。然后事先在该区域内采集一些位置进行RSS并以强度测试（x，y，RSS）将形式记录在数据库中。定位时，将未知节点与数据库中的数据进行比较，选择三个或三个以上或三个以上点作为估计位置，然后使用三边测量法或以下纹理法来估计位置。
信号传播模型：
信号传输模型主要有两种模型：自由空间模型和shadowing模型
假设信号发射功率与信号接收功率之间存在一定的映射关系：
其中PR是接收处的功率，PS是发射处的功率，d是发射点与接收点的距离，α根据环境，是传播因素。
shadowing模型：
其中P（d）是未知节点的信号强度或信号发射功率，P（d0)是信标节点或基站d0信号发射功率(包括d0是参考距离，一般取1m），n是衰减因衰减因素。由于实际环境中的噪声，引入了吗？例如，如果在室内传播，会有墙壁或门等障碍物，需要计算？
2.无需测距（range-free）
无需测距的定位算法不需要直接测量节点之间的距离或角度，而是根据网络的连接来估计位置。典型的无测距算法主要包括以下几种：
1）质心算法
基于两个假设条件的纹理算法：射频信号的传输遵循理想的球模型；节点的通信半径相同，不会改变。
算法运用了计算几何中心的思想，设n边形的顶点坐标分别为（x1，y1）…（xn，yn），设其质心坐标为（x，y），则有
x=（x1+x2…+xn）/ n
y=（y1+y2+…+yn）/ n
算法核心思想为：信标节点周期性地广播包含自身位置信息的消息，在时间t内未知节点收到来自信标节点i的消息数目为Nr（i，t），而时间t内信标节点i发出的消息数目为Ns（i，t），那么未知节点和信标节点的连通指标为：
C=Nr（i，t）/ Ns（i，t）
如果C大于设定的阈值，则认为未知节点处于信标节点i的覆盖区域内，即与信标节点i连通。这样对于每个未知节点都可以选出与其连通的所有信标节点，然后把这些信标节点的质心作为该未知节点的坐标。
质心算法是一种完全基于网络连通性的定位算法，其计算和实施难度都比较小，但是算法精度不高，并且通常要求信标节点具有较高的密度。
2）DV-HOP（Distance Vector-Hop）算法
DV-HOP算法是为了避免对节点距离直接测量而提出的一种基于矢量路由的非测距定位算法。该算法的核心思想是通过距离矢量路由方法获取未知节点与信标节点之间的最小跳数，并计算每跳的平均距离，然后以每跳的平均距离与最小跳数的乘积作为未知节点与信标节点的估算距离，再使用三边测量法估算未知节点的坐标位置。举个例子：
A、B、C为信标节点，M为未知节点，A到B和C的距离分别为40m和100m，而A到B和C的最小跳数分别为2和5，则A的平均跳距为：
（40+100）/ （2+5）=20m，同理可以得到B和C的平均跳数为24m和22.5m，则可以计算M距离三个信标节点的距离分别为：
320m，224m，3*22.5m，然后就可以利用三边测量法估算出M的坐标。这种方法实现比较简单，但是精度较差，不适合稀疏的以及拓扑不规则的网络。
3）APIT算法
APIT算法的基本思想同质心算法的思想类似，它利用由信标节点组成的三角形覆盖重叠区域来确定未知节点的位置。在APIT算法中，未知节点首先在其邻居节点中收集信标节点的信息。然后任意选取3个信标节点，判断自己是否在这3个信标节点组成的三角形区域内，然后不断这样循环选取3个信标节点进行判断，这样，未知节点可以确定多个包含自己的三角形区域，这些三角形区域的重叠部分是一个多边形，它确定了更小的包含未知节点的区域，然后以这个多边形区域的质心作为未知节点的坐标。
4）MAP算法
MAP（Mobile Anchor Point）是一种基于移动信标节点的非测距定位算法，也有称为MAN（Mobile Anchor Node）。其基本思想是利用可移动的信标节点在监测区域中移动并周期性的广播其当前的位置信息，然后可以确定两条以未知节点为圆心的弦，这两条弦的垂直平分线的交点就是圆心。
如图所示，S为未知节点，M为移动的信标节点，在T1时刻M移动到S的通信范围之内，然后在T5时刻移出S的通信范围，这样就可以确定了两条弦 T1T5，在T12时刻M又重新移动到S的通信范围之内，然后又在T15时刻移出S的通信范围，这样又可以确定一条弦T12T15，这两条弦的垂直平分线的交点即为圆心S的坐标，然后以圆心坐标作为未知节点S的位置。
该算法有与其他非测距定位算法相比有较高的精确度，但是缺点是移动节点是必须要有足够能量支持其在监测区域内移动，并且当未知节点的位置发生变化时，该算法有比较大的误差。
5）Amorphous算法
Amorphous算法与DV-HOP算法类似，其分为三个阶段：
第一阶段：计算未知节点与每个信标节点之间的最小跳数
第二阶段：假设网络中的节点通信半径相同，并且每跳的平均距离等于节点的通信半径，计算未知节点到每个信标节点的距离
第三阶段：采用三边测量法或者最大似然估计法估算未知节点的位置
6）凸规划定位算法
凸规划定位算法的核心思想是：如果两个节点能够直接进行通信，则它们之间的距离必定小于节点的通信半径。
如图所示，黑色实心点为信标节点，白色空心点为未知节点，假若未知节点能与信标节点通信，则其必在以信标节点为圆心、通信半径为半径的圆内，这样的话，多个这样的圆的相交区域必然包含了未知节点，然后以相交区域构成的矩形的质心作为未知节点的坐标。
7）Ring-Overlapping算法
该算法利用交叠环的思想进行定位，比如S为未知节点，A、B、C为信标节点，若A发出射频信号，而S处的信号强度RSS小于B处的信号强度而大于C处的信号强度，则S必在以A-B为内半径、A-C为外半径的环形区域内，类似地分别可以得到以B、C为中心的环形区域，而S必在这些环形区域的交叠区域内，然后以交叠区域的质心作为S的坐标。
以上算法都是有信标节点的定位算法，曾有人提出了一些没有信标节点的定位算法如SPA（Self-positioning Algorithm）算法，这种算法主要是建立全局坐标系来估算未知节点的位置，但是这种算法复杂度非常高，不适合用于大规模网络，也有人提出针对SPA算法的改进算法，如SDGPSN（Scalable and Distributed GPS free Positioning for Sensor Networks）算法。
还有一部分人提出了一些其他的算法，比如AFL（Anchor-Free Distributed Localization in Sensor Networks）算法，其利用的是局部估算方法。还有人提出了基于分簇的定位算法（Using Clustering Information for Sensor Network Localization）。
定位算法暂时就介绍这么多了，相关深入内容将在后面继续讲解。
作者：Matrix海子 出处：http://www.cnblogs.com/dolphin0520/ 本博客中未标明转载的文章归作者Matrix海子和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。