随着计算机网络技术、通信技术、嵌入式技术和传感器技术的飞速发展和日益成熟，具有感知能力、计算能力和通信能力的微型传感器及其构成的无线传感器网络WSN(Wireless Sensor Network)引起了人们的极大关注。这种传感器网络具有低功耗、低成本、自组织的能力，能够自动进行配置和适应环境的变化，具有动态可重构性等特点，能够通过协作实时监测、感知和采集网络，分布区域内的各种环境或监测对象的信息并传送到控制中心，因而被广泛应用于国防军事、国家安全、精细农业、环境监测、智能家居、城市交通以及预防与减灾、人员营救、目标跟踪等方面，适用于在人们无法接近的极端恶劣或特殊环境下监测事件发生的地点[1]。
传感器节点通过飞行器撒播、人工埋置和火箭弹射等方式任意撒落在被监测区域内。节点的位置信息都是随机的，节点所采集到的数据，若没有位置信息几乎没有应用价值[1]。所以在无线传感器网络应用中，节点的定位一直是关键问题，同时也是人们研究的热点。由于传感器节点采用电池供电，节点数量巨大，成本太高，能量有限。因而利用GPS或其他方式先对网络中的少量节点(锚节点)进行定位，其他大部分节点以锚节点位置为参考，应用各种定位算法实现自身定位。
根据目前出现的定位算法对节点位置估测机制的不同可以分为两大类：基于距离相关的定位算法(Range-Bad Localization Schemes)和基于距离无关的定位算法(Range-Free Localization Schemes)。前者需要测量相邻节点间的绝对距离或方位，并利用节点间的实际距离来计算未知节点的位置；后者不需要自己与锚节点之间的距离或角度信息，而是根据网络连通性等信息估算出自己与锚节点
间的距离。基于距离相关的定位算法使得传感器节点造价增高，消耗了有限的电池资源，而且在测量距离和角度的准确性方面需要大量的研究。基于距离无关的定位算法则不需要知道未知节点到锚节点的距离或者不需要直接测量此距离，在成本和功耗方面比基于测距的方法具有优势[1]。如质心算法、DV-Hop、Amorphous和近似三角形内点测试法APIT等。其中，APIT定位算法的基本思想简单，实现容易。而且由于其定位功耗小、成本低、节点定位精度高等特点得到广泛应用和研究，其中有不少改进算法的效果更优。本文将
无线传感器网络APIT定位算法
唐明虎，张长宏，昝风彪
(青海民族大学计算机学院，青海西宁810007)
摘要：无线传感器网络节点定位机制的研究中，基于距离无关的定位技术得到快速发展，其中基于重叠区域的APIT定位算法在实际环境下定位精度高，被广泛研究和应用。对APIT定位算法及其改进措施进行了总结，并给出性能比较结果。
关键词：无线传感器网络；APIT；定位算法
中图分类号：TP393文献标识码：A文章编号：1674-7720(2010)21-0001-04
APIT localization algorithm in wireless nsor networks
TANG Ming Hu，ZHANG Chang Hong，ZAN Feng Biao
(College of Computer Science，Qinghai University for Nationalities，Xining810007，China)
Abstract：Localization algorithm bad on range-free has developed rapidly in wireless nsor network node localization mechanism.Especially bad on overlapping the region APIT localization algorithm in real environment，high positioning accuracy can be widely ud by rearch.This positioning technology of the APIT algorithm and its improved algorithm are reviewed，and its performance analysis and comparison of simulation.
Key words：wireless nsor networks；APIT；localization algorithm
基于距离无关的定位算法APIT 的相关改进算法进行综述，以便使APIT 算法的研究和应用得到进一步推广。
1基于区域的APIT 算法
无线传感器网络定位机制中，APIT 算法属于距离无关、区域相关的定位策略。其实现简单、定位成本
低、传感器节点功耗小、定位精度高，因而得到广泛应用。它的基本算法是从待定位节点周围的锚节点中任意选取三个，组合成一个三角形，判断该点是否位于该三角形内。如果在三角形内，则将其标记，依次对待定位节点周围的锚节点进行各种不同组合并检测，最终找出所有满足要求的三角形重叠区域，求其质心位置以替代待定位节点在网络中的具体位置坐标。算法原理见图1。该算法的基本理论依据是最佳三角形内点测试法(PIT )[2]。
1.1PIT 原理介绍
APIT 算法在进行定位之前，首先要明确未知节点M
是否处于已知的三个锚节点所连成的三角形内。因此，对于随机分布在某区域内的无线传感器网络，在需要确定位置信息的未知节点M 的无线射程范围内随机选取三个已知位置信息的锚节点：A (x a ，y a )，B (x b ，y b )，C (x c ，y c )，确定M 节点是否在锚节点构成的△ABC 内。
命题1：将节点M 向任意一个方向移动，如果节点M 至少与锚节点A 、B 、C 当中的任何一个之间远离或接近，则表明节点M 处于该△ABC 内，见图2(a )。
图书发行命题2：存在一个方向，使得节点M 沿该方向移动时，将同时远离或接近三个锚节点A 、B 、C ，则表明节点
M 处于该△ABC 外，见图2（b)。
按上述命题判断节点M 是否处于三个锚节点包围的三角形之内，条件足够，但由于实际无线传感器网络中撒布的节点规模庞大，而且大部分实际网络中，节点处于静止或移动非常缓慢的状况，因此上述判断方法不能用于待定位节点的测试。在实际网络操作中采用近似
PIT 原理测试。
近似PIT 原理(APIT 原理)：如果在待定位节点M 的
邻居节点中，没有同时远离或接近三个锚节点A 、B 、C 的点，则表明节点M 位于该△ABC 内，否则节点M 位于
△ABC 外(见图3)。对于具有N 个锚节点的规模网络，用
锚节点间的通信能够连成C 3N 个三角形。
1.2APIT 算法实现步骤
在实际无线传感器网络中实现APIT 算法可简要分为四个步骤：
(1)各节点获取在其无线射程之内所有锚节点的信帝王相
息，包括位置坐标、信号强度等信息。
(2)根据PIT 原理进行测试。
(3)聚集所有满足条件的三角形，找出其交集。(4)计算交集的重心，以其估计待定节点位置。
根据实现APIT 算法的四个步骤，可以写出其伪代码：
送母亲什么花
Receive location beacons (Xi ，Yi)from N anchors ；
//取得N 个锚节点的位置坐标
InsideSet =Ф；
/
/对设定用来存放包含待定节点区域的变量InsideSet 初始化for(each triangle Ti ∈triangles){
//穷尽锚节点组成的所有三角形
if (Point-In-Triangle-Test (Ti)==TRUE)
//判断如果待定位节点位于该三角形内
InsideSet =InsideSet ∪{Ti}；
//则将其区域标记，并调用网络扫描算法
if (accuracy(InsideSet)>enough)break ；
文学名言//如果定位精度已达要求可提前结束循环
}
Estimated Position=Center Of Gravity(∩Ti ∈InsideSet)；//计算包含待定位节点的公共区域的重心，以其代替待定
//位节点的位置
1.3APIT 算法性能分析
通过与常见几种基于距离无关定位算法之间的
比
图1
APIT 算法原理
A
M
牛鞭的功效B
C
M
A
B
C
(a)三角形内
(b)三角形外
图2
PIT 原理说明
A
B
C
(a)三角形内
M A
B
C
(b)三角形外
2
2
3
3
4
4
1
1
M 图3
近似PIT 原理测试
较，发现APIT算法在定位精度、硬件成本、节点分布和锚节点密度等方面性能比较优越。性能比较见表1[2]。在锚节点密度增大或邻居节点数目增多情况下，其定位误差呈下降趋势，而且相对其他几种算法，效果比较明显。另外，随着锚节点无线辐射范围增大，定位误差上升趋势略低于其他算法。试验显示[2]，在无线信号传播模式不规则和传感器节点随机部署的情况下，APIT算法的定位精度高、性能稳定，测试错误概率相对较小(最坏情况下14%)。平均定位误差小于节点无线射程的40%。该算法最大的优点是与其他非基于距离的算法相比，算法简单，受节点密度影响较小且节点间通信量少，这就大大降低了功耗，对资源受限的传感器网络较为适用。
1.4APIT存在的问题
对APIT算法详细分析发现其存在一定的问题，主要有以下几点：
(1)在PIT测试中，如果待定位节点靠近或完全在三角形一条边上时，将出现OutToIn或InToOut的判断错误问题。
(2)在PIT测试中，一般采用信号强度来判断远离或靠近锚节点，这在实际环境中，既增加了传感器节
点的能耗，同时也增大了判断误差。
(3)对重叠区域重心的计算中，采用的网格扫描算法效率低，计算精度不高。
(4)如果锚节点或待定位节点周围邻居节点密度过小，往往对定位精度和定位覆盖率造成很大影响，甚至造成一定比率的节点位置不能被定位[3]和定位覆盖率不高。因此要达到高的性能，就要求锚节点密度和通信范围增大。
(5)算法在执行中不仅需要定位节点间与锚节点的信息交互，也需要与邻居节点间进行信息协调处理，造成网络节点通信开销和计算量上升，使得算法的应用受到限制。
2改进的APIT算法
针对APIT定位算法存在的问题，人们提出了许多改进措施。这对APIT算法的推进与实际应用起到了积极的作用。
参考文献[4]~[7]对问题(1)、(3)进行改进，其中参考文献[4]提出基于三角形重心扫描的改进算法，在分析APIT中InToOut和OutToIn产生的原因后提出合法三角形区域、非法三角形区域和扫描算法的支持数据集等概念，通过增加对邻居节点合法性检查，减少了InToOut错误发生次数，降低了边界效应对APIT测试的影响；通过扩大邻居节点定义范围，增加了待定位节点的邻居节点数目，从而有效减少了
OutToIn错误的发生次数。参考文献[5]提出随着邻居节点数目的改变，要求待判定节点都远离三角形三个顶点的邻居节点的个数要满足≥n/m 的要求(n为待定位节点的邻居节点个数，m为权重系数)，才能判定待定位节点位于相应三角形的外部。
参考文献[8]针对问题(2)、(4)提出：在原有APIT算法的基础上引入信标节点对待定位节点M坐标估计值影响系数。避免了当待定位节点M比较靠近△ABC的一条边，或者M周围的信标节点分布不均匀时，APIT的判断出现错误。即使APIT算法发生误判，也可以通过计算信标节点对M坐标估计值影响因子系数来提高定位精度，同时也解决了anchors节点稀疏，APIT算法失效的问题。
参考文献[9]进一步考虑到网络中节点通信的安全性而提出改进的SAPIT算法。该算法利用节点通信加密、锚点身份验证、APIT测试结果安全汇总等方法，实现了APIT算法中的安全定位思想，为今后进一步研究APIT提出了新的思路。
参考文献[10]针对问题(4)、(5)，提出环形区域叠加定位算法ROCRSSI(Ring overlapping bad on Comparison of Received Signal)，算法所需网络通信量较低。其优点体现在：(1)不需要未知节点参与发送控制信号，仅需锚节点发送相应的定位控制信息，从而使得其通信代价相对较低；(2)未知节点只是收集相关的锚节点信息，与网络的连通度和邻居节点密度无关；(3)采用的圆环叠加方式比三角形叠加范围更小，提高了定位精度；(4)在不规则的无线通信模式下工作比较正常。
在对于定位精度方面，参考文献[11]利用APIT算法中三条边的中垂线将APIT算法中的三角形分割为4个或6个可用小区域，并以检测信号的强弱进一步来判定未知节点的位置，从而缩小APIT算法的定位区域，提高定位精度，提出基于中垂线分割的PB-APIT。参考文献[12]引入网格的思想，将整个监测区域划分为若干部分，在每个网格范围内采用随机的方式放置节点，从而接近节点的均匀分布，因而提出基于网格分布的定位算法。
在定位覆盖率不足的问题上，参考文献[13]~[15]分别进行了改进。参考文献[13]的改进算法增大了anchor 节点的覆盖度，降低了InToOut与OutToIn发生的概率。参考文献[14]将测距用的接收信号强度指示器RSSI与APIT相结合，引入限定距离的概念，提出改进算法RAPIT(RSSI and APIT)，将引起误差的节点的位置限定在以锚节点为圆心、以限定距离为半径的圆的重叠区域内，从而达到减少误差、提高定位覆盖度的目的。参考文献[15]从不同的锚节点比例、节点通信半径以及同一锚
表1常见算法在不同参数要求下的性能比较
Accuracy NodeDensity AnchorHeard ANR
DOI GPSError Overhead
DVHop
Good
>8
>8
>0
Good
Good
Largest
Centroid
Fair
>0
>10
>0
Good
Good
Smallest
Amorp.
Good
>8
>8
>0
Fair
Fair
Large
APIT
婴儿口腔清洁
Good
>6
>10
>3
Good
Good
Small
节点比例等方面提出改进的IAPIT算法，提高了定位覆盖率。
目前，在无线传感器网络定位技术中，将多种定位方法混合在一起的作法已经成为一种新的研究方式。
参考文献[16]将APIT和基于信号到达时间差(TDOA)的泰勒级数展开算法(TSE)混合应用，仿真发现其定位精度要高于两个算法单一定位的情况。
此外，在三维空间定位方法的研究中，参考文献[17]提出三维空间内传感器节点自身定位方法APIT-3D (Approximate-Point-In-Tetrahedron)。通过判断传感器节点是否位于由锚节点组成的四面体的内部，筛选出可能的位置区域，并最终计算这些区域交集部分的重心，作为待定位节点的位置。仿真实验表明，作为一种不基于测量设备的定位方法，APIT-3D可以达到节点通信半径的40%以下的较高精度的三维定位，而且通信开销相比于二维定位方法增幅不明显。APIT-3D定位方法无需复杂的测距设备和昂贵的外部设施，且通信协议相对简单，因此是一种低成本、低功耗的无线传感器网络三维自身定位方法。
总之，自APIT算法问世以来，人们对其进行了广泛研究，从二维平面到三维空间，从解决算法存在的问题到改进算法，以及提出定位精度、效能更高的新算法。目前，利用APIT和其他定位算法混合定位的技术更进一步得到人们的青睐。
3改进算法性能分析总结
通过以上各种算法的改进措施分析，对原APIT算法存在的有关问题得到不同程度的改进，其性能有一定的提高，部分文献提出的改进措施经过MatLab仿真，其性能的确优于APIT算法。参考文献[4]、[8]
在网络规模不大，锚节点分布比较规则且均匀情况下，效果比较明显，但在节点分布不规则环境下，其算法有待提高。
硬笔书法纸模板分析以上各种改进算法，不难发现各自对APIT中存在的某个或某几个问题给予了一定的解决，但其中仍然有一些问题，如传感器规模特大、节点分布随机而杂乱情况下，传感器网络边缘节点定位情况仍未得到更多关注。另外，在实际环境中，随机分布的节点受到风力等气候影响，以及对随机分布呈三维立体形式的整个网络节点定位等方面还有待进一步研究，以提高算法执行效率和节点定位精度。
本文回顾了APIT定位算法的基本原理，分析APIT 存在的问题并综述后期关键文献对不同问题分析和解决的方法，同时对改进算法中存在的问题进行分析并提出一些个人看法，希望在今后的工作中能够进一步探讨这些问题，使APIT算法真正在实际中得以广泛应用。
参考文献
[1]孙利民.无线传感器网络[M].北京：清华大学出版社，2008.
[2]He Tian，Huang Chengdu，Blum B M，et al.Range-free
localization schemes in large scale nsor networks[C]//
Proceedings of the9th Annual International Conference on Mobile Computing and Net-working，MOBICOM’2003，San Diego(CA，USA)，2003.New York(NY，USA)：ACM Press，2003：81-95.
[3]NAGPAL R，SHROBE H.BACHRACH J.Organizing a
global coordinate system from local information on an ad hoc nsor network.In Information Processing in Sensor Networks：Second International Workshop，IPSN2003(Palo Alto，April2003)，no.2634in Lecture Notes in Computer Science，Springer-Verlag.
[4]周勇，夏士雄.基于三角形重心扫描的改进APIT无线传
感器网络自定位算法[J].计算机研究与发展，2009，46
(4)：566-574.
[5]曹磊，徐晨.无线传感器网络近似三角形内点测试定位
算法改进[J].电子技术应用，2007，33(11).
[6]Ji Zeng，Wang Hong，Xu Jin.Improvement on APIT localization
algorithms for wireless nsor networks[J].Proceedings of the 2009International Conference on Networks Security，Wireless Communications and Trusted Computing，2009(1)：719-723.
[7]张宁，王越，王东.无线传感器网络中APIT定位算法的
改进[J].工业控制计算机，2009，22(3)：42-43.
[8]韩彪，徐昌彪，袁海，等.无线传感器网络中一种改进
的APIT定位算法[J].计算机工程与应用，2008，44(4)：122-124.
[9]孙庭波，屈玉贵，赵保华.一种无线传感器网络安全
定位的新方法[J].小型微型计算机系统，2009，130(9)：1738-1741.
[10]蒋小兰，邓平.基于区域重叠的WSN节点自定位新算
法[C].信息、电子与控制技术学术会议，2006.
[11]杨骥，刘锋.无线传感器网络基于中垂线分割的APIT
的改进定位算法[J].传感技术学报，2008，21(8)：1453-1457.
[12]裴庆祺，赵军.基于网格分布的三角形内点测试定位算
法[J].计算机工程与设计，2008，29(18)：4657-4661. [13]赵军，裴庆祺，徐展琦.无线传感器网络近似三角形内
点测试定位算法[J].计算机工程，2007，33(5)：109-111. [14]冯秀芳，曹美丽，孙超.无线传感器网络基于APIT的混
合定位算法[J].微电子学与计算机，2009，29(6)：58-61. [15]周四清，陈锐标.无线传感器网络APIT定位算法及其流淌的歌谣
改进[J].计算机工程，2009，35(7)：87-89.
[16]谢亚琴，张业荣.基于APIT和TSE算法的混合定位方法
[J].南京邮电大学学报(自然科学版)，2007，27(6)：68-71.
[17]刘玉恒，蒲菊华，赫阳，等.无线传感器网络三维自身定位
方法[J].北京航空航天大学学报，2008，34(6)：647-651.
(收稿日期：2010-06-02)
作者简介：
唐明虎，男，1974年生，硕士研究生，讲师，主要研究方向：计算机网络应用、非线性科学。
