非测距定位技术简介

1）质心算法

我们知道，在计算几何学里多边形的几何中心称为质心，多边形顶点坐标的平均值就是质心结点的坐标，如图4－18所示。假设多边形定点位置的坐标向量表示为pi＝（xi，yi）T，则这个多边形的质心坐标为

例如，如果四边形ABCD的顶点坐标分别为（x1，y1），（x2，y2），（x3，y3），（x4，y4），则它的质心坐标计算如下：

这种方法的计算与实现都非常简单，根据网络的连通性确定出目标结点周围的信标参考结点，即可直接求解信标参考结点构成的多边形的质点。

在传感器网络的质心定位系统的实现中，锚点周期性地向邻近结点广播分组信息，该信息包含了锚点的标识符和位置。当未知结点接收到的来自不同锚点的分组信息数量超过某一阈值或在接收一定时间之后，就可以计算这些锚点所组成的多边形的质心，以此确定自身位置。由于质心算法完全基于网络连通性，无需锚点和未知结点之间的协作和交互式通信协调，因而易于实现。

图4－18　质心定位算法图示

质心定位算法虽然实现简单、通信开销小，但仅能实现粗粒度定位并且需要信标锚点具有较高的密度，各锚点部署的位置也对定位效果有影响。

2）DV－Hop算法

DV－Hop算法解决了低锚点密度引发的问题，它根据距离矢量路由协议的原理在全网范围内广播跳数和位置。每个结点设置一个至各锚点最小跳数的计数器，根据接收的消息更新计数器。锚点广播其坐标位置，当结点接收到新的广播信息时，如果跳数小于存储的数值，则更新并转播该跳数。

如图4－19所示，已知锚点L1与L2、L3之间的距离和跳数。L2计算得到校正值（即平均每跳距离）为（40＋75）／（2＋5）＝16.42 m。假设传感器网络中的待定位结点A从L2获得校正值，则它与3个锚点之间的距离分别是D1＝3×16.42，D2＝2×16.42，D3＝3×16.42，然后使用多边测量法即可确定结点A的位置。

图4－19　DV－Hop定位算法举例

3）APIT算法

近似三角形内点测试法（Approximate Point－In－triangulation Test，APIT）［1］首先确定多个包含未知结点的三角形区域，这些三角形区域的交集是一个多边形，它确定了更小的包含未知结点的区域；然后计算这个多边形区域的质心，并将质心作为未知结点的位置。

（1）APIT算法的基本思想

未知结点首先收集其邻近信标结点的信息，然后从这些信息结点组成的集合中任意选取三个信标结点。假设集合中有n个元素，那么共有种不同的选取方法，确定个不同的三角形，逐一测试未知结点是否位于每个三角形内部，直到穷尽所有种组合或达到定位所需精度。最后计算包含目标结点所有三角形的重叠区域，将重叠区域的质心作为未知结点的位置。如图4－20所示，阴影部分区域是包含未知结点的所有三角形的重叠区域，黑点指示的质心位置作为未知结点的位置。(www.xing528.com)

图4－20　APIT定位原理图示

（2）APIT算法的理论基础

APIT算法的理论基础是最佳三角形内点测试法（Perfect point－In－triangulation Test，PIT）。PIT测试原理如图4－21所示，假如存在一个方向，结点M沿着这个方向移动会同时远离或接近顶点A、B、C，那么结点M位于△ABC外；否则，结点M位于△ABC内。

图4－21　PIT原理图示

在传感器网络中，结点通常是静止的。为了在静态的环境中实现三角形内点测试，提出了近似三角形内点测试法：假如在结点M的所有邻居结点中，相对于结点M没有同时远离或靠近三个信标结点A、B、C，那么结点M在△ABC内；否则，结点M在△ABC外。

近似三角形内点测试法利用网络中相对较高的结点密度来模拟结点移动，利用无线信号的传播特性来判断是否远离或靠近信标结点，通常在给定方向上，一个结点距离另一个结点越远，接收到信号的强度越弱。邻居结点通过交换各自接收到信号的强度，判断距离某一信标结点的远近，从而模仿PIT中的结点移动。

（3）APIT测试举例

如图4－22（a）所示，结点M通过与邻居结点1交换信息可知，结点M接收到信标结点B、C的信号强度大于结点1接收到信标结点B、C的信号强度，而结点M接收到信标结点A的信号强度小于结点1接收到信标A的信号强度。那么根据两者接收信标结点的信号强度判断，如果结点M运动至结点1所在位置，将远离信标结点B和C，但会靠近信标结点A。依次对邻居结点2、3、4进行相同的判断，最终确定结点M位于△ABC中；而在图4－22（b）中可知，结点M假如运动至邻居结点2所在位置，将同时靠近信标结点A、B、C，那么判定结点M在△ABC外。

图4－22　APIT测试举例

（4）APIT定位具体步骤

①收集信息：未知结点收集邻近信标结点的信息，如位置、标识符、接收到的信号强度等，邻居结点之间交换各自接收到的信标结点的信息。

②APIT测试：测试未知结点是否在不同的信标结点组合成的三角形内部。

③计算重叠区域：统计包含未知结点的三角形，计算所有三角形的重叠区域。

④计算未知结点位置：计算重叠区域的质心位置，作为未知结点的位置。

在无线信号传播模式不规则和传感器结点随机部署的情况下，APIT算法的定位精度高，性能稳定，但APIT测试对网络的连通性提出了较高的要求。相对于计算简单的类似的质心算法，APIT算法精度高，对信标结点的分布要求低。