RSSI PDOA NFER
N Y N long long short strong strong weak big big small （二）定位阶段算法分析：
Trilateration[26]是通过三个已知坐标的信标节点以及这三个信标节点到未知节点的距离信息，根据二维空间距离公式建立方程组，采用线性化方法来求解出未知节点的位置信息。假设已知三个信标节点A、B、C的坐标分别为(x1,y1)、
(x2,y2)、(x3,y3)它们到未知节点D的距离分别为：d1、d2、d3，未知节点D
的坐标设为(x,y)。可以得到下列方程：
?d12?(x?x1)2?(y?y1)2??222?（2-1） d?(x?x)?(y?y)?2?22?222??d3?(x?x3)?(y?y3)?根据上式可得未知节点D的坐标方程为：
?x??2(x1?x3)?y???2(x?x)???232(y1?y3)?2(y2?y3)???1222?x12?x3?y12?y3?d3?d12??2?（2-2） 22222??x1?x3?y1?y3?d3?d1??Multilateration是已知三个以上信标节点的坐标信息以及信标节点到这个未知节点的距离信息，利用两点间的距离公式可计算出未知节点到信标节点之间的距离，最后利用最小二乘法（LS，Least Square）、极大似然估计（MLE，Maximum Likelihood Estimation）或最小均方误差（MMSE，Minimum Mean Square Error）等求出未知节点的坐标信息。
Triangulation是通过未知节点的接收器天线阵列来测量出周边信标节点所发出信号的入射角信息，利用所得到的角度信息和信标节点的坐标信息，根据Trilateration算出未知节点的坐标。
Maximum Likelihood Method[27]原理如图2-2所示。
12nD34
图2-2 最大似然估计法
Figure 2-2 Maximum Likelihood Method
在该算法中已知1，2，3，…n等n个信标节点的坐标为：(x1,y1)、(x2,y2)、
(x3,y3)，…(xn,yn)。它们到未知节点D的距离分别为：d1、d2、d3…dn，假
设未知节点D的坐标为(x,y)。那么存在如下公式：
?(x1?x)2?(y1?y)2?d1???（2-3）
?(x?x)2?(y?y)2?dnn?n从第一个方程开始分别减去最后一个方程可得：
?x12?xn2?2(x1?xn)x?y12?yn2?2(y1?yn)y?d12?dn2??（2-4）式??x2?x2?2(x?x)x?y2?y2?2(y?y)y?d2?d2nn?1nn?1nn?1nn?1n?n?1（2-4）可表示为：AX?b，其中：A、X、b如下面（2-5）到（2-7）所示：
?2(x1?xn)A??????2(xn?1?xn)2(y1?yn)????（2-5）
2(yn?1?yn)???x12?xn2?y12?yn2?dn2?d12???b????（2-6）
?x2?x2?y2?y2?d2?d2?nn?1nnn?1??n?1?x?X???（2-7）
?y?利用最大似然估计法或最小二乘法可得D的坐标为：
X?(ATA)?1ATb（2-8）
2.3.2 基于无需测距的定位算法
基于测距的定位算法虽然能够实现精确定位，但往往也对硬件要求较高，导致硬件成本增加，不利于大面积、多领域、广角度的使用。无需测距的定位算法使用起来比较简单，只需要利用未知节点到参考节点之间的估计距离值或其它位置信息，然后用三边测量法或极大似然估计法来计算出未知节点的坐标信息。无需测距定位算法由于不需要精确测量节点间的距离信息，极大地降低了对节点硬件的要求，另外它是利用节点间的距离估计值来进行计算，因此受环境的影响较小，在许多对节点定位精度要求不高的应用场合能够大量使用。现有的基于无需测距的定位算法主要有：DV-HOP算法、质心算法、Amorphous算法、APIT算法、凸规划算法和MDS-MAP算法等。下面分别介绍这几种方法：
（1） 质心定位算法（Centroid）
质量中心简称质心（Centroid），指物质系统上被认为质量集中于此的一个假想点。
在传感器网络中，质心是指多边形的几何中心[28]，多边形各个顶点坐标的几何平均值即为质心坐标。质心定位算法是University of Southern California的NirupamaBulusu等提出的，该算法适用于室外节点密度较高情况下的定位，它是基于网络的连通性（Connectedness）实现对节点的定位。其基本思想是：未知节点根据自身设定的门限值来接收周围信标节点所发出的包含节点位置和ID的信息来确定其所在的区域，根据其接收到的信标节点的ID及位置信息计算所在区域的质心，并把这个区域的质心作为自身的定位结果。该算法简单易行，对硬件要求较低，不需要额外任何硬件设备，但在定位过程中需要较多的信标节点，另外该算法在定位过程中都假设节点拥有理想的无线信号传输模型，这与实际的情况还有很大的差别，因此影响了Centroid的定位精度。
^质心定位算法的基本原理如图2-3所示。
A1A6(x,y)A2
A3A5A4图2-3质心算法示意图
Figure 2-3 Diagram of Centroid Principle
该算法中，多边形区域A1、A2、A3…A6的六个顶点坐标分别为：(x1,y1)、
(x2,y2)、(x3,y3)、(x4,y4)、(x5,y5)、(x6,y6)，则区域的质心为：
(x,y)?(x1?x2?x3?x4?x5?x6y1?y2?y3?y4?y5?y6,)（2-9）
66（2） 不定型定位算法（Amorphous）
Amorphous[29]是基于连通性的定位算法，它需要预先知道网络的连通度。算法实现过程中，首先未知节点计算与每个信标节点之间的最小跳数；然后计算未知节点到每个信标节点的跳段距离，其中假设网络中节点的通信半径相同；最后Amorphous实现起来比较简再利用Trilateration或MLE等算法来进行定位计算。
单，但定位精度不是很高，另外还有两个显著的缺点：一是需要预先知道网络的连通度；二是定位过程中需要较高的节点密度。
（3） 近似三角形内点测试法（APIT）
APIT（Approximate Point-in-Triangulation Test）算法能够以较高的定位精度APIT定位算法在实现过程中未知节点首先通过收集邻适应于复杂的地理环境。
居节点的节点标识符、位置信息、发射信号功率的大小等信息来确定该节点是否位于不同的信标节点所组成的三角形内，然后统计包含未知节点的三角形区域，并把这些三角形区域的交集构成一个多边形，这个多边形基本上确定了未知节点所在的区域并缩小了未知节点所在的范围，最后计算这个多边形区域的质心，并将质心作为未知节点的位置，这样就实现了未知节点的定位。
APIT定位算法基本原理如图2-4所示。
A3A2SA4A5
A1AnA6图2-4APIT算法示意图 Figure 2-4 Diagram of APITPrinciple
在图2-4中未知节点从它所能接收到信号的信标节点A1、A2、A3…An中随机选择三个，并测试自身是否在这三个信标节点所组成的三角形中，测试完成后再随机选取另外三个信标节点继续测试，直到测试完所有的组合为止。在图2-4中，未知节点分别选取?A1A2A3、?A2A3A4、?A3A4A5…?A1A2An并测试自身是否位于这三个信标节点所组成的三角形中，判断完成后也就确定了这些三角形的交叉区域（如图中的阴影部分）所组成的多边形，然后计算这个多边形的质心S，并把质心S的坐标作为该未知节点的坐标。APIT定位算法利用电磁波衰落模型，相对于别的定位算法有着更高的定位精度，对节点密度要求也低，在节点密度较高的情况下定位更为准确，另外APIT定位算法的通信量小且适用于电磁波不规则的模型，能够在大多数场合应用。
（4） 凸规划定位算法
凸规划定位算法(Convex Optimization)是一种集中式的定位算法，所谓的集中式的定位算法是相对于分布式定位算法而言的，集中式定位算法采用集中的思想，收集到所有的传感器节点的有效信息后统一进行定位计算，集中式定位算法的可扩展性不好，信号传输和处理比较麻烦，不能够灵活使用。凸规划定位算法的基本原理如图2-5所示：未知节点首先根据其通信半径和与之能进行通信的信标节点建立其可能存在的位置区域，当穷举完这些区域之后按照一定的标准对这些区域进行筛选和位置划分，最后确定一个矩形区域（如图中阴影区域外的矩形区域），计算出该矩形区域的质心并把它作为未知节点的坐标，以此来实现节点定位。