基于三角形外接圆覆盖的改进APIT定位算法*

2015-05-09汤文亮周琳颖

传感技术学报 2015年1期

关键词：外接圆定位精度三角形

汤文亮,周琳颖

(华东交通大学软件学院,南昌 330013)

基于三角形外接圆覆盖的改进APIT定位算法*

汤文亮*,周琳颖

(华东交通大学软件学院,南昌 330013)

在无线传感器网络(WSN)中,传感器节点定位在整个WSN体系中占有重要地位。APIT(Approximate Point-In-Triangulation Test近似三角形内点测试法)相对于其他定位算法,具有硬件要求较低,定位性能较好等优点。该算法在节点密集的网络中,可以得到比较合理的定位精度,性能也相对稳定。然而,在节点随机分布的网络中,其定位误差是不容忽视的,且定位覆盖率也相对较低。针对此问题,分析了APIT测试中的典型错误——三角形内外覆盖判断错误以及产生的原因,提出了一种基于三角形外接圆覆盖的改进APIT算法——APICT(Approximate Point-In-Circumcircle Test)算法,并将此算法与APIT算法的仿真结果进行比较,证明了此算法的定位精度具有显著优势。

无线传感器网络;定位算法;三角形外接圆覆盖;定位精度;APIT算法;三角形内外覆盖

无线传感器网络[1]WSN(Wireless Sensor Networks)是由传感器节点、感知对象和观察者3个基本要素构成。传感器节点是WSN的基本组成实体。WSN的典型工作方式[2]为:大量无线传感器网络节点布设在监测区域内或监测对象周围,节点之间通过自组织快速形成一个感知网络。

在WSN中,由于传感器节点所采集的数据或探测的事件通常都需要有相对应的地理信息作标识,所以节点具备定位能力(如借助GPS或其他定位方法)对于许多应用来说是一个非常重要的前提[3]。另外,节点的位置信息也常常被某些通信协议所利用,如利用节点间地理位置信息控制节点的发送功率以及约束波束的方向性,以降低节点通信能耗以及提高网络容量;利用节点间的相对地理位置信息进行路由决策,以降低路由控制开销,提高网络的能量有效性及可扩展性。因此,节点定位技术在WSN中才尤为重要[4]。

由于传感器网络节点能量、存储及处理能力的限制,必然要求定位算法是低复杂性的[5]。提高测距准确度是提高节点定位精度的一个有效途径,难点是测距的实现要受节点能量、硬件复杂度及体积的限制。而且在实际应用中,测距准确度是不可能无线提高的,这就需要从算法的角度来进一步提高定位精度。

定位算法分类标准各异,学术界也已经提出了很多基于WSN的节点定位算法,对算法的分类和总结也已经出现在一些文献中[6]。从算法采用的手段来看,可以分为两大类:基于测距的定位机制和非基于测距的定位机制。第1种类型的算法基于节点间距离长度或方位角度信息,通常的测距技术包括基于时间的测距技术(TOA/TDOA)和基于接收信号能量的测距技术(RSSI)等,通过以上这些不同的测距技术,获得节点间点到点的距离或角度信息,然后再使用三角测量法、三边测量法或多边测量法等计算出节点位置;第2种类型的算法则无需距离和角度信息,而仅仅需要得到待定位节点与相邻节点间的连通信息,然后实现节点定位,这类定位机制中的一些典型算法有质心定位算法、APS算法、APIT算法等。基于测距的定位技术一般定位精度较高,但是对无线传感器网络节点的硬件要求也比较高,因此在WSN的的现发展阶段性价比不高;而非基于测距的定位算法虽然在对硬件要求不高且技术上实现简单的情况下,能够满足大多数应用的定位精度,但其产生的误差也往往较大。APIT算法相对其他几种基于距离无关定位算法,在定位精度、硬件成本、节点密度、节点分布等方面性能较好。

然而,在PIT测试中,APIT由于相邻节点密度较低,在三角形内外覆盖问题上有时会做出错误的判断,最终影响定位精度。

目前,虽然有很多学者做了APIT的改进算法[7-10],但他们大多都是在节点密集程度较高的情况下,对定位精度进行了各方面提高,而本文的APIT改进算法是考虑了即使在节点密集程度不高的情况下,仍能保持较高的定位精度。

APIT算法中,待定位节点通过PIT测试得出自己可能位于3个锚节点所构成的三角形区域集合后,便直接计算包含待定位节点的所有三角形交集的质心,并将其作为自己的位置估算。然而,由于三角形内外覆盖判断错误的存在,这些三角形区域并不总是包含待定位节点。因此PIT测试得到的位置估计往往精度不高。

然而针对以上问题,本文提出了一种基于三角形外接圆覆盖的无线传感器网络定位算法APICT(Approximate Point-In-Circumcircle Test)。该算法不同于APIT中的PIT测试,不用通过相邻节点间信息交换来模拟PIT测试的节点移动,而是通过PICT测试:求出3个锚节点所构成的三角形的外接圆,并计算这个外接圆的圆心及半径,然后测量待定位节点到圆心距离,最后通过与半径的对比确定待定位节点是否在园内。接着再用重复PICT(Point-In-Circumcircle Test)测试直到穷尽所有组合或达到所需定位精度,最后计算包含待定位节点的所有圆的交集质心,最终得到的坐标平均值便是所求节点位置。

1 APIT定位算法及不足之处

1.1 APIT定位算法

一般来说,WSN中有两种节点:一种是已知自己物理位置信息的,称为锚节点,另一种不知道自己物理位置信息的,需要定位的节点,称为待定位节点或未知节点。

APIT算法的主要思想是:一个待定位节点任选3个相邻锚节点,通过PIT测试自己是否位于它们所构成的三角形中,使用不同参考节点组合重复测试直到穷尽所有组合或达到所需定位精度,最后计算包含待定位节点的所有三角形的交集质心,并以这一点作为待定位节点位置。

APIT(Approximate PIT Test)算法理论基础[11]是PIT:假如存在一个方向,沿着这个方向待定位节点M会同时远离或接近锚节点A、B、C,那么节点M位于△ABC外;否则,节点M位于△ABC内。

为了在静态网络中执行PIT测试,定义了APIT测试:假如节点M的相邻节点没有同时远离或靠近锚节点A、B、C,则节点M就在△ABC内;否则,在△ABC外。它利用WSN较高的节点密度来模拟节点移动,同时,在给定方向上,节点离锚节点越远,接收信号强度越弱的无线传播特性来判断其与锚节点的远近。通过相邻节点间信息交换来模拟PIT测试的节点移动,从而判断自身是否在△ABC内。使用不同锚节点组合重复PIT测试直至穷尽,最后计算包含待定位节点的区域的交集质心,以此作为所求位置。

1.2 APIT定位算法的不足之处及原因分析

如上所述,由于APIT测试必须通过与相邻节点间信息交换才能判断是否位于三角形内,所以,APIT测试的正确性与周围邻居节点的分布情况密切相关[12]。然而在实际测试中,算法有时仅仅分析有限的几个方向(依赖于相邻节点数量),导致PIT测试有时会做出错误的判断。

在图1中,待定位节点M本应位于△ABC外部,当节点M通过与相邻节点1交换信息,得知自己如果运动至节点1处,则将远离锚节点B和C,但会接近锚节点A,与相邻节点2,3和4通信和判断过程类似。因此,根据PIT测试理论,最终判断M位于△ABC内部,这种错误简称为ETI(External To Internal)错误。

图1 EIT错误

如图2所示,待定位节点M本应位于△ABC内部,但由于某些相邻节点在△ABC之外且离锚节点A、B和C都比较远,所以,当节点M通过与相邻节点2交换信息,得知自己如果运动至节点2处,则将同时远离锚节点A,B和C。因此,根据PIT测试理论,最终判断M位于△ABC外部,这种错误简称为ITE(Internal To External)错误。

图2 ITE错误

那么,产生这两种错误的原因究竟是什么呢?

针对ETI错误,本文认为主要原因是,相邻节点的不规则部署,造成待定位节点在进行PIT测试时有效的邻居节点数目过少,最终导致EIT错误。

针对ITE错误,本文认为究其原因主要是,节点密度过低,所以选择了在△ABC之外且离锚节点A、B和C都较远的相邻节点,最终导致ITE错误。

2 基于三角形外接圆覆盖的改进APIT定位算法

根据以上分析可知,待定位节点的相邻节点的密度的高低是影响定位结果精确度的最大因素。故本文提出的APIC算法在相邻节点密度较低的情况下仍能保持较高精确度。

2.1 三角形外接圆覆盖的APICT算法

APICT算法具体实现步骤:

①假定节点M(x,y)是待定位节点,任取3个锚节点A(xA,yA)、B(xB,yB)和C(xC,yC),以A、B和C所构成的△ABC,画△ABC的外接圆C1,如图3所示。

图3 APICT算法图解

②求出圆C1的圆心O(xO,yO)的坐标,以及O点到A、B和C任意一点的距离,即圆的半径r。

③使用某种技术[13]实现M点到圆心O的测距,假设为l,通过对比,如果l<=r,则说明待定位节点M在圆C1内,否则在圆C1外。

④使用不同锚节点组合重复上述测试,直到穷尽所有组合或达到所需的定位精度。

⑤找出待定位节点所在的所有圆形区域的交集,最后估算这个区域的质心,并以质心作为未知节点的估计位置。

2.2 算法性能和效率分析

若不存在ETI和ITE错误,则文献[14-15]中的APIT算法和本文中的APICT算法最终获得的估计坐标值相差不大。然而在实际测试中,这两种错误都是很难避免的。试验显示[15]:APIT测试错误概率最坏情况下接近14%。

在算法执行效率上,APIT算法由于要和邻居节点多次交换信息,故需要多次和三角形3个顶点距离进行比对;而APICT算法仅需要计算三角形外接圆圆心O和半径r,而O和r只需通过三角形的3个顶点即可推算。所以,相比较而言,APICT算法具有更高的执行效率。

3 仿真结果及分析

3.1 APICT算法性能仿真分析

为了检验APICT定位算法的性能,本文使用MATLAB 7.0仿真工具对该算法进行了仿真实验。为方便体现锚节点数量及节点的分布情况对APICT算法定位精度的影响程度,本文将对APICT算法中单个节点的定位误差率做分析。

如下图4所示描述了锚节点数量在3～15时,节点定位误差率。

图4 APICT算法仿真(1)

由上图分析得出:随着锚节点数量的增加,APICT算法定位误差率逐渐减小,并且在锚节点数量达到某个值时,趋于稳定。

如下图5所示描述了在节点数目100的情况下,节点定位误差率与节点分布情况的关系。

图5 APICT算法仿真(2)

由上图分析得出:在节点数目固定的情况下,随着锚节点比率的增加,APICT算法平均定位误差率逐渐减小。由此说明:节点分布情况对定位误差率有着很大的影响。

3.2 APICT和APIT算法性能分析比较

为方便理解,本文假设每单位面积内布设1个节点的密度为1。如图6描述了在100 m×100 m的通信区域内,节点密度从0.05到0.6时,APIT算法和APICT算法节点平均定位误差率的比较。

图6 APICT与APIT算法仿真比较

由图可知,在节点密度改变的条件下,两种算法的性能也各不相同。根据本文以上分析可知,APICT算法中节点定位仅与锚节点相关,而不需要其邻居节点参与定位,所以该算法在节点密度改变的情况下其定位误差影响较低,可以说几乎无变化,而对于APIT算法,其定位精度则与网络节点密集程度有着很大的影响,定位误差率随着节点密度的增大而减小,所以可得出此结论:在节点密度一定的情况下,APICT算法的性能优于APIT。

4 结束语

本文通过分析当前较常用的一种基于区域重叠定位算法APIT,通常产生的ETI和ITE错误及其产生的原因,从而影响节点定位精度及执行效率的缺点,提出一种基于三角形外接圆覆盖的APICT算法,有效改进了算法的定位精度和执行效率。仿真实验表明,基于三角形外接圆覆盖的改进的APIT算法,在随机分布的网络中,不但可以有效地降低ETI和ITE两类错误发生的概率,改善算法的性能,而且能提高平均定位精度。影响APIT定位算法的最终定位精度的因素有很多,除了本文中讨论的锚节点密度、相邻节点部署外,定位精度还与通信半径,无效节点等其他因素有关,这些将是下一步研究的内容。

[1]王汝传,孙力娟.无线传感器网络技术导论[M].出版地:清华大学出版社,2012.

[2]王小强,欧阳骏,黄宁淋.ZigBee无线传感器网络设计与实现[M].出版地:化学工业出版社,2012.

[3]崔立,鞠海玲,苗永,等.无线传感器网络研究进展[J].计算机研究与发展,2005,42(1):163-174.

[4]韩光洁.智能空间中传感器网络节点精确定位与路径规划[M].北京:科学出版社,2012.

[5]熊小华,何通能,徐中胜,等.无线传感器网络节点定位算法的研究综述[J].机电工程,2009,26(2):13-17.

[6]王福豹,史龙,任丰原.无线传感器网络中的自身定位系统和算法[J].软件学报,2005,16(5):857-868.

[7]冯秀芳,曹美丽,孙超.无线传感器网络基于APIT的混合定位算法[J].微电子学与计算机,2009,29(6):58-61.

[8]周四清,陈锐标.无线传感器网络APIT定位算法及其改进[J].计算机工程,2009,35(7):87-89.

[9]相卫华,贾超,王华奎,等.无线传感器网络三维APIT网格化算法[J].传感技术学报,2012,25(5):639-643.

[10]胡伟,朱西平,文红,等.基于四面体质心迭代的三维APIT定位算法研究[J].传感技术学报,2013,26(10):1432-1436.

[11]Nirupama Bulusu,Deborah Estrin,John Herdemann.Tradeoffs in Location Support System:The Case for Quality-Exprossive Location Models for Applications[C]//Proceedings of the Ubicomp 2001 Workshop on Location Modeling Atlanatn.Gerogia,USA:2001:7-12.

[12]Harter A,Hopper A,Steggles P,et al.The anatomy of a Context-Aware Application[C]//Proceedings of the 5th Annual ACM/IEEE International Conference on Moblie Computing and Networking.Seattle:ACM Press,1999:59-68.

[13]Andreas Savvides,Chih Chieh Han,Mani B Srivastava.Dynamic Fine-Grained Location in Ad-Hoc Networks of Sensors[C]//Proceedings of Moblie Computing and Networking(MobiCom’01),Rome,Italy:ACM Press,2001:166-179.

[14]He T,Huang C D,Blum B M,et al.Range Free Localization Schemes in Large Scale Sensor Networks[C]//Proc of the 9th Annual Int Conf on Moblie Computing and Networking.New York:ACM,2003:81-95.

[15]Tian He,Chengdu Huang,Brian M Blum et al.Range-Free Localization Schemes in Large Scale Sensor Networks[C]//Proceeding of the 9th Annual International Conference on Mobile Computing and Networking(MobiCom),San Diego,California,USA:ACM Press,2003:81-95.

An Improved APIT Localization Algorithm Based on Triangle-Circumcircle Cover*

TANGWenliang*,ZHOULinying

(School of Software,East China Jiaotong University,Nanchang 330013,China)

The sensor node localization plays an important role in wireless sensor network.Comparing with other localization algorithm,APIT(Approximate Point-In-triangulation Test)has the advantages of lower hardware requirement and better positioning performance and so on.In the network which nodes distribute densely,APIT algorithm can help get a more reasonable positioning accuracy,and its performance is relatively stable.However,in the network which nodes distribute randomly,the positioning error is not allow to ignore,and positioning coverage rate is relative lower.To solve this problem,this article analyzed a typical mistake in the APIT test and its causes,which is called the inside and outside triangle cover judgment errors,and its put forward an improved APIT algorithm,which is named APICT(Approximate Point-In-circumcircle Test)algorithm,that based on triangle circumcircle cover algorithm.Comparing with APIT algorithm,the simulation result of this algorithm proved that the positioning accuracy has improved significantly.

wireless sensor network;localization algorithm;triangle circumcircle cover;positioning accuracy;APIT algorithm;inside and outside triangle cover