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

An Improved APIT Localization Algorithm Based on Triangle-Circumcircle Cover

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

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.