基于改进APIT算法的无线传感器网络节点定位戴天虹;李昊【摘要】定位技术是无线传感器网络中一个比较重要的技术.近似三角形内点测试(APIT)算法是一种比较常用的算法,为了提高无线传感器网络(WSNs)定位精度,在APIT算法的基础上进行改进,将三角形进行中垂线分割成4个或者6个小区间,通过对各个节点接收到目标节点信号强度进行比较,判断目标节点位于哪一个小区域内.通过仿真可以得到,改进的APIT算法精度上有了很大的提高.【期刊名称】《传感器与微系统》【年(卷),期】2016(035)001【总页数】4页(P135-138)【关键词】无线传感器网络;近似三角形内点测试算法;节点定位;中垂线分割【作者】戴天虹;李昊【作者单位】东北林业大学机电工程学院,黑龙江哈尔滨150040;东北林业大学机电工程学院,黑龙江哈尔滨150040【正文语种】中文【中图分类】TN926无线传感器网络(WSNs)具有着低成本、低损耗的特点，能够在恶劣的环境下进行数据的采集和收发,目前正在快速发展[1]。
传感器的定位问题是无线传感器网络中的一项非常重要的技术，多种无线传感器网络节点定位算法已经提出。
通过对节点位置估测机制的不同可分为两类：基于距离的定位算法和距离无关的定位算法[2]。
前者需要知道两个相邻节点之间的绝对距离和方位，根据节点之间的实际距离来确定未知节点的坐标；后者需要知道未知节点和锚节点之间的连通能力来估算出和锚节点之间的距离[3]。
前者的精确度比较高，后者只能估算出节点的大致位置。
其中，与距离无关的定位算法由于能够减少节点的能量消耗，并且延长整个网路的生命周期而得到了广泛的研究和应用。
典型的算法有：DV-Hop、质心定位、近似三角形内点(approximate point-in-triangulation,APIT)测试定位等。
本文定位采用APIT定位算法，并针对该算法定位中的不足提出改进的APIT定位算法，提高定位的精度，对改进的定位算法进行仿真，并对仿真结果进行了分析[4]。
1.1 APIT算法的基本原理APIT算法的定位过程如下：目标节点通过与周围的锚节点进行信息传递，可以得到能够与其进行通信的锚节点的集合。
假设该集合中共有n个元素，从中选择任意3个节点组成一个三角形，则一共能组成个三角形。
判断该未知节点的位置是在三角形内部或者在三角形外部，然后选择另外3个节点来确定未知节点的位置，直到穷尽所有的三角形。
计算所有三角形的重叠区域，逐渐缩小未知节点所在的区域，最后将重叠区域的质心作为未知节点的估计坐标。
如图1所示，所有可用三角形的重叠部分是未知节点所在的大致位置，点M表示的重叠部分的质心即为未知节点所在的位置。
APIT算法的最重要的部分是确定未知节点位于三角形的内部还是外部。
对此，可以采用最佳三角形内点[5](perfect point-in-triang-ulation，PIT) 测试算法来判断该未知节点是否位于三角形的内部。
图2表示的是具体的PIT算法原理。
A,B,C为三角形的三个顶点，M为需要确认的未知节点。
让M点向任意的方向发生移动，若M点在运动过程中，存在一个点，在向该点移动时，M点离A,B,C的距离是同时增大或者减小的，那么,点M位于三角形的外部;反之，M位于三角形的内部，这就是PIT原理[6]。
1.2 改进的APIT算法在整个无线传感器网络的边缘地区，传感器的数量相对来说比较少，锚节点较少，这样组成的三角形的数量也会降低。
在进行PIT算法进行定位时，会出现由于重叠区域过大造成实际位置与定位位置偏差过大的现象。
图3所示的是运用APIT定位误差较大的一种情况。
为了提高无线传感器网络的定位精度，提出一种改进的APIT算法[7]。
改进的APIT算法是根据锚节点接收到未知节点的信号强度的变化来作为依据所实现的。
如图2左图所示，目标节点在向1方向移动的过程中，可用三角形3个锚节点接收到的信号强度会发生变化，A锚节点接收到的信号强度会越来越大，B,C目标节点接收到的信号强度会越来越小。
改进的APIT算法是缩小未知节点M在三角形内的区域范围，提高节点的定位精度。
具体实现是将三角形进行分割。
对三角形进行中垂线分割，那么,三角形将会被进一步分割成几个小区间。
由三角形中垂线分割可知，锐角三角形会被分割成6个小区域，直角三角形和钝角三角形会被分割成4个小区域[8]。
图4(a),(b),(c)分别为锐角三角形、直角三角形和钝角三角形中垂线分割图。
由图4可知，经分割后，三角形被分割成三角形、四边形、五边形三种小区间。
通过对三角形3个锚节点A,B,C接收到未知节点的信号强度的比较可以判断出未知节点位于分割后的哪个小区间内[9]。
以图4(a)锐角三角形中垂线分割为例,通过对A,B,C三点接收到位置节点M发出的信号强度进行比较，若A点接收到的信号强度大于B点和C点接收到的信号强度，并且B点接收到的信号强度大于C点接收到的信号强度，那么,未知节点位于分割小区域1,2,3,4,5,6中的小区域6内，6即为可用小区域。
若A点接收到信号强度大于B,C两点接收到的信号强度，B点接收到的信号强度等于C点接收到的信号强度，那么,未知节点位于BC的中垂线上，在这种情况下，可以选择1,6这2个小区组成的共同区域作为可用小区域[10]。
对所有的可用三角形进行分割，则有多少个可用三角形就有多少个可用小区域。
找出所有可用小区域的重叠部分，求出重叠区域的质心位置，将质心位置作为未知节点的估计位置[11]。
1)改进的APIT算法与APIT算法相似，首先需要知道目标节点周围所有锚节点的信息，包括锚节点的位置和锚节点接收到目标节点的信号强度大小。
2)所有能够和目标节点进行信息通信的锚节点组成锚节点集。
任意选取3个锚节点组成三角形，判断目标节点位于三角形的内部还是外部。
已知三个锚节点接收到目标的信号强度大小，若存在一个点，该点接收到的三角形3个锚节点的信号强度比目标节点接收到的信号强度均大于或者小于，那么，该目标节点位于三角形的外部；否则，目标节点位于三角形的内部。
3)选出所有包含目标节点的三角形，将三角形进行中垂线分割，则将三角形分成四部分或者六部分。
若三角形为锐角三角形，则被分割成6个小区间，若三角形为直角三角形或者钝角三角形，则被分割成4个小区间。
通过对 3个锚节点接收到的目标节点发出的信号的强度大小进行比较，确定目标节点位于哪一个小区间内。
4)找出所有小区间的重叠区域，并且求出重叠区域的质心位置，将该质心位置作为目标节点的位置。
改进APIT算法的流程图如图5所示。
2.1 仿真环境与参数设置本文用VC来进行仿真验证，并采用无线传感器网络定位技术仿真，主要方法是将100，200，300个点随机分布在一个100 m×100 m的区域内，在仿真中分别加入APIT和改进的APIT算法，通过对平均误差的比较，验证改进算法的可行性。
在仿真过程中，节点是随机分布在该区域内的。
锚节点的密度从1 %开始慢慢增大，得出不同的锚节点密度下的平均误差。
平均误差是由定位误差和通信半径之比得到[12]。
定位误差即为定位的位置和节点真实的位置差。
通常，锚节点的数量越少，定位的难度就会越大，定位的精度就会越小，平均误差就会越大。
在实验过程中，目标节点周围锚节点的数量不同，会出现以下四种情况:1)目标节点不能接收到任何锚节点发出的信号时，将该区域的中心位置作为定位点[13]。
2)目标节点只能接收到1个锚节点发出的信号时，将该锚节点作为定位点。
3)目标节点只能接收到2个锚节点发出的信号时，将两点的中间位置作为定位点。
4)目标节点能够接收到3个及其以上锚节点发出的信号时，若目标节点位于组成的三角形外部，则取该三角形的质心作为定位点。
若位于三角形的内部，则采用APIT算法和改进的APIT算法分别进行定位得出定位点。
2.2 仿真结果图6为总节点数分别为100，200，300时的定位误差。
由图6可知，APIT算法和改进的APIT算法都随着锚节点密度的增加定位的精度也不断提高。
在整个过程中，出现以下三种情况:1)在锚节点密度比较低时，由于许多目标节点不能够接收到锚节点发出的信息，定位的精度比较低。
APIT算法和改进的APIT算法都有着较高的定位误差，曲线几乎是重合的。
2)随着锚节点密度的逐渐增大，目标节点接收到的锚节点的信息强度和数量都在不断增大，此时，APIT算法开始发挥作用，锚节点组成的可用三角形的数量也在不断地增多，平均误差不断减小。
未知节点的定位精度也在不断提高。
但改进的APIT算法的平均误差要小于APIT算法，改进APIT算法的定位精度要高于APIT算法[14]。
3)当锚节点的密度达到一定程度之后，改进的APIT算法和APIT算法定位精度逐渐趋向稳定，但改进的APIT算法仍然优于APIT算法。
图7表示的改进的APIT算法相对于APIT算法定位精度提高百分比。
从图中可以看出，改进的APIT算法比APIT算法的定位精度是先增加后减小的。
出现这种情况的原因是因为整个区域中的锚节点数量较少时，两种算法都不能够起到作用，精确度都比较低。
随着锚节点的数量不断增多，两种算法都开始发挥作用，但改进的APIT算法精确度要远远高于APIT算法导致曲线开始上升。
最后，由于锚节点慢慢趋于饱和，可用三角形的数量也在不断增加，两种算法的精确度都比较高，导致定位精度提高百分比开始下降。
从图中还可以看出，在100 m×100 m的区域中，当区域中节点的数目为40个时，改进的算法提高精度的幅度最大。
整体来说，改进的APIT算法有着比APIT算法较高的精度，定位的更加精确。
改进的APIT算法适用于设施比较简单的情况。
其主要思想就是在APIT算法的基础上，将三角形进行中垂线分割，分割成四部分或者六部分，通过对锚节点接收到的目标节点的信号强度大小的比较，确定目标节点位于三角形的哪一个小区域，求出所有可用小区域重叠部分的质心位置，将该点作为目标节点的定位位置。
仿真发现：改进的APIT算法比APIT算法在锚节点数量不算太多的情况下定位精度有所提高，随着锚节点数量的增加，定位精度提高的更快。
【相关文献】[1] 彭勇.无线传感器网络中能量高效的目标跟踪协议研究[D].长沙:中南大学,2009.[2] 周祖德，王晟.一种适用于复杂环境的无线传感定位算法[J].武汉理工大学学报,2006,15(11):121-124.[3] 薛霞，孙勇.监测煤矿的一种无线传感器网络节点定位算法[J].传感器与微系统,2010,29(9):119-121.[4] 卢迪，刘世琦.无线传感网络改进APIT定位算法[J].哈尔滨理工大学学报,2014,16(4):95-99.[5] Liu Yu,Yi Xiao,He You.A novel centroid localization for wireless sensornetworks[C]∥International Conf on Distributed Sensor Networks,ACM,2012:689-694.[6] 何登平,范茂林.一种基于APIT的无线传感器网络混合型定位算法[J].传感器与微系统,2015,34(2):133-135.[7] 王亚子，杨建辉.改进粒子群算法的无线传感器网络节点定位[J].计算机工程与应用,2014(18):99-102.[8] 杨骥，刘锋.无线传感器网络基于中垂线分割的APIT的改进定位算法[J].传感技术学报,2008,23(8):1453-1457.[9] Sheng Xiaohong,Yu Henhu.Sequential acoustic energy based source localization using particle filter in a distributed sensor network[C]∥IEEE International Conference on Acoustics,Speech,and Signal Processing，Piscataway,USA:IEEE,2004:961-972.[10] 谢国新，李新.短波干扰有效压制距离的计算方法[J].航天电子对抗,2005,2(1):53-55.[11] 曹磊,徐晨.无线传感器网络近似三角形内点测试定位算法改进[J].电子技术应用,2007(11):80-82.[12] 李琳.基于WSNs的非测距定位算法研究[D].天津:天津工业大学,2014.[13] 祁会波.无线传感器网络中基于移动锚节点的定位算法研究[D].太原:太原理工大学,2006.[14] 张骁航.基于跳距误差修正和粒子群优化的无线传感器网络定位算法研究[D].重庆: 重庆邮电大学,2012.戴天虹(1963-)，男，黑龙江哈尔滨人，博士，教授，主要从事林业工程自动化等方面的教学与科研工作。