无线传感器网络近似三角形内点测试定位算法改进
作者：曹 磊， 徐 晨
发布日期：2008-07-17
摘 要： 作为重要的共性支撑技术之一，传感器网络" title="传感器网络">传感器网络" title="无线传感器网络" title="无线传感器网络">无线传感器网络">无线传感器网络的定位问题极具研究价值。分析了近似三角形内点测试算法，对该算法进行了改进。仿真分析表明：较之原算法，改进算法降低了错判发生的概率。
关键词： 无线传感器网络 定位 近似三角形内点测试算法
根据节点定位机制可将现有无线传感器网络WSN（Wireless Sensor Network）自身定位算法分为两类[1]：基于距离的(Range-based)和不基于距离的(Range-free)定位算法。Range-based 定位算法通过测量相邻节点之间的绝对距离或方位来计算未知节点的位置，现阶段常用的定位算法有：RSSI、TOA、TDOA和AOA。Range-based 定位机制使用各种算法来减小测距误差对定位的影响，包括多次测量、循环定位求精[2]。这些算法在获得相对精确定位结果的同时，对节点硬件要求高且都要产生大量计算和通信开销，因此Range-based 定位机制虽在定位精度" title="定位精度">定位精度上有可取之处，却常常不适用于低功耗、低成本的无线传感器网络应用领域。Range-free定位算法则无需节点间的距离和角度信息，仅根据网络连通性等信息实现定位，常用的定位算法有质心、DV-Hop、Amorphous和APIT等。Range-free 定位机制在成本、功耗等方面具有优势，对硬件要求也较低，因此备受关注。特别是APIT可以利用现有传感器节点" title="传感器节点">传感器节点自带的无线功率发射装置，在无需增加额外硬件的情况下实现定位。
1 APIT 定位算法[3]
1.1 算法基本思想
APIT（Approximate Point in Trangulation Test）定位算法将未知节点可能的位置区域利用其通信半径内已知位置的锚节点进行三角形划分，取各部分的公共区域作为未知节点位置的估计。如图1 所示，阴影部分区域是包含未知节点的所有三角形的重叠区域，黑点指示的质心位置作为未知节点的位置。
1.2 PIT 算法原理
APIT算法的理论基础是最佳三角形内点测试法PIT(Perfect Point-In-Triangulation Test)， PIT 测试原理如图2 所示：假如存在一个方向，沿着这个方向未知节点M 会同时远离或接近三角形的3 个顶点A、B、C，则M 位于△ABC 外；否则，M 位于△ABC内。
为了在静态网络中执行PIT 测试，如果节点M的邻节点没有同时远离或同时靠近3 个锚节点A、B、C，则就判定M在△ABC 内；否则，判定M在△ABC外。
1.3 APIT定位原理
APIT算法利用传感器网络较高的节点密度来模拟节点移动，利用无线信号的传播特性来判断是否远离或靠近锚节点。通常在给定方向上，一个节点距锚节点越远，接收信号强度越弱，通过信息交换来判断与某一锚节点的远近，以此来仿效PIT 中的节点移动。图3(a)中，待定节点M通过与邻节点1 交换信息，得知自身若运动至节点1，将远离锚节点B和C，但会接近锚节点A，邻节点2、3、4 的通信和判断过程类似，最终确定自身位于△ABC 中；在图3(b)中，通过信息交换节点M 可知：自身若移动至邻节点2将同时远离锚节点A、B、C，故判断自身在△ABC外。
在APIT算法中，一个未知节点在其通信半径内任选3 个锚节点，测试自己是否位于它们所组成的三角形中，使用不同锚节点的组合重复测试，直到穷尽所有组合或达到了所需的定位精度。
APIT具体步骤：
(1)收集信息：未知节点收集邻近锚节点的信息，如位置、标识号、接收到的信号强度等，邻居节点之间交换各自接收到的锚节点的信息；
(2)APIT测试：测试未知节点是否在不同的锚节点组合成的三角形内部；
(3)计算重叠区域：统计包含未知节点的三角形，计算所有三角形的重叠区域；
(4)计算未知节点位置：计算重叠区域的质心位置，作为未知节点的位置。
1.4 APIT重叠区域计算的实现
APIT测试结束后，APIT 用grid SCAN 算法(如图4所示)进行重叠区域的计算。在此算法中，网格阵列代表节点存在的可能性最大的区域。首先令每个网格的初值为0。如果判断出节点在三角形内，则相应三角形所在区域的每个网格的值加1；同样，如果判断出节点在三角形外，则相应三角形所在区域的每个网格的值减1。计算出所有的三角形区域的值后，找出具有最大值的重叠区域，最后计算出这个重叠区域的质心即为未知节点的位置。
1.5 in-to-out error与out-to-in error
由于APIT只能判断有限的方向(即邻节点的个数)，因此在某些情况下可能做出错误的判断。如图5(a)所示，未知节点M 靠近三角形的一条边，且邻节点4 位于三角形外部，可见节点4 较之未知节点M 同时远离3 个端点A、B、C。根据APIT 的定义，未知节点M 就做出在△ABC 外的错误判断，称作in-to-out error。当节点M 的邻节点的分布如图5(b)所示时，M 就会做出位于△ABC 内的错误判断，称作out-to-in error。
分别作出以A、B、C为圆心，AM、BM、CM为半径的圆在M点的切线。由图6可见，角1与角2之和越大，发生out－to－in error的概率越大，即待定位节点离三角形的边长越远，发生out－to－in error的可能性越小。这与三角形内越靠近三角形边界的节点越容易发生in－to－out error的情况是一致的。
试验显示[3]，在无线信号传播模式不规则和传感器节点随机部署的情况下，APIT 算法的定位精度高、性能稳定，测试错误概率相对较小(最坏情况下14%)；平均定位误差小于节点无线射程的40%。且该算法最大的优点是与其他非基于距离的算法相比算法简单，受节点密度影响较小且节点间通信量少，这就大大降低了功耗，对资源受限的传感器网络较为适用。
2 APIT 算法改进
三角形内的一点移动后是不可能离三个顶点都近的，所以如发现一点在一个方向上移动后离三个顶点都近，则这点必定在三角形外。于是，在未知节点获知所有邻节点与判定三角形顶点的远近距离后，首先判定是否有邻节点离三个顶点都近，如有就判未知节点在圆外，否则，再考虑移动后离三个顶点都远的情况。
由分析可知，相比于out－to－in error，发生in－to－out error的可能性大得多。因此本文针对后者提出了一种改进方案：即随着邻节点数目的改变，相应调整判定位于三角形外的条件，即要求待判定节点都远离三角形三个顶点的邻节点的个数要达到相应的数目，才判定未知节点位于相应三角形的外部，而不同于传统APIT只要求一个方向上都远离三角形的三个顶点即可，此处要求都远离的节点数满足大于等于n/m的要求，n为待判定节点邻节点的个数，m为权重系数，分析表明m＝4和m＝5时能达到较好的效果。
3 实验仿真
在未知节点的通信半径内随机布设n（4，5，6，7，8，9，10，15，20）个邻居节点，在权重分别为4与5时，进行100次仿真实验，求出错判的次数。
设三角形ABC三点分别为A（0，0），B(3,4),C(4,3)，三角形内一紧靠三角形AB边的待判定节点M1坐标为（1.6,2)，由此可以模拟in-to-out error错判的情况。令通信半径为2.60（此数值为M1点到点" title="点到点">点到点A、B、C的最长距离），随机布设的区域为1.6-2.60
由于新算法提高了APIT判三角形外的条件，势必会产生少量将三角形外点判为三角形内点的错判，即out-to-in error。
另设圆外一点M2(1.5,4)作为待判定节点， 由此可以模拟out-to-in error 的错判情况，令通信半径为4.272（此数值为M2点到点A、B、C的最长距离），随机布设的区域为1.6-4.272
由仿真结果可见，新算法能明显减少in-to-out error发生的概率，但也增加了少量的out-to-in error。权重系数m取4时，相比于m取5能更有效减少in-to-out error的发生，但也增加了out-to-in error。可以根据实际情况选取合适的权重系数。同时，可以看到当邻节点个数达到9个或更多时，新算法产生out-to-in error的可能性已经很小。总体而言，新算法改善了APIT的性能，有其可取性。
本文提出了一种APIT判定条件随着未知节点的邻节点数的变化而进行相应调整的新策略，仿真显示新算法在增加了些许out－to－in error的情况下，显著减少了in－to－out error的发生的概率。随着无线传感器网络应用领域的不断扩展，对传感器定位的研究也将进一步深化。由于各种应用差别很大，没有普遍适合于各种应用的定位算法，因此将针对不同的应用，通过综合考虑节点的规模、成本及系统对定位精度的要求，来设计最适合的定位算法系统。
参考文献
[1] 孙利民，李建中，陈 渝，等. 无线传感器网络[M].北京:清华大学出版社，2005.
[2] MAO G Q, FIDAN B, ANDERSON B. Wireless sensor network localization techniques[J]. Comput. Networks,2007,51(10):2529-2553.
[3] HE T, HUANG C D, BLUM B M, et al. Range-free localization schemes in large scale sensor networks. in Proc.ACM/IEEE 9th Annu. Int. Conf. Mobile Computing and Networking(MobiCom’03), 2003.
[4] 史龙,王福豹,段渭军,等.无线传感器网络Rang-Free自身定位机制与算法[J]. 计算机工程与应用,2004(23):127-132.
[5] LANGENDOEN K, REIJERS N. Distributed localization in wireless sensor net-works: a quantitative comparison[J]. Computer Networks 2003,43:499-518.