一种基于APIT 的无线传感器网络混合型定位算法

何登平，范茂林

(1.重庆邮电大学 通信新技术应用研究中心，重庆400065;2.重庆信科设计有限公司，重庆400065)

0 引 言

无线传感器网络(WSNs)作为一种全新的信息获取和处理技术在目标跟踪、入侵监测及一些定位相关领域有广泛的应用前景。定位作为无线传感器网络应用的基础和关键技术之一，对传感器节点明确自身位置和了解传感器节点的位置分布状况这两个重要信息是非常必要的［1，2］。

无线传感器网络定位算法根据距离分类［3］，可以分为:1)基于距离(range-based)的定位算法，主要方法有:RSSI［4］，TOA［1，2］，TDOA［1，2］和AOA［1，2］等;2)与 距 离 无 关(range-free)的定位算法，常见的有:近似三角形内点测试(approximate point in trianlge test，APIT)算法［1，2］、DV-Hop(distance vector-hop)算法［1，2］、Amorphous 算法［1］和MAP算法［2，5］等。这些算法中，APIT 定位算法是一种适用环境广、算法复杂度低、成本低、实现相对容易的算法。为了提高APIT 算法的定位精度，文献［6］提出了利用角度求和来减小未知节点是否位于三角形内的误判;为了提高APIT 算法在信标节点稀疏的环境下的定位覆盖率，文献［7］提出了一种基于RSSI 和APIT 的混合定位算法减小定位误差和提高定位覆盖率。

本文提出一种混合型算法，它通过减小三角形内点测试(PIT)的三角形误判、选择优良的三角形，提高了信标节点密集环境下的定位精度，并且在此基础上，结合DV-Hop算法与两点定位法在稀疏环境下能计算出未知节点坐标的优点，提高了信标节点稀疏环境下的定位覆盖率。

1 APIT 算法分析

1.1 APIT 算法基本原理

APIT 算法［1，2］的基本原理是:未知节点通过信息发送，接收在它通信半径内的信标节点;然后，对接收到的信标节点通过PIT，判断未知节点是否在由任意3 个信标节点组成的三角形区域内部，当由n 个信标节点时，就进行C3n次PIT;最后，对于未知节点位于三角形内的区域覆盖成一个多边形区域，这个多边形的质心就作为是未知节点的位置。

1.2 APIT 算法存在的问题

1)在判断未知节点是否在3 个信标节点组成的三角形区域内部，容易产生两个错误，即In-To-Out 和Out-To-In。例如:图1(a)图，当节点M 从实际位置1 模拟移动到位置2 时，收到来自A，B，C 的信号强度同时变弱，节点M 同时远离了A，B，C 三个点，就会判定为M 处于三角形外，即，In-To-Out error。同理，图1(b)，当节点M 从实际位置1 模拟移动到位置2 时，根据信号强度测得节点M 就远离了A，并同时靠近了B，C 两点，就会判定为M 处于三角形内，即，out-to-in error。

图1 两种误判情况Fig 1 Two situations of misjudgement

2)在无线传感器节点密集的环境下，假设未知节点的邻居信标节点有n 个组成的集合，此时，有个三角形对未知节点进行定位，而n 取值比较大时，经三角形判断后，仍然存在一部分信号强度弱的PIT 节点对节点定位，每增加一个信号强度弱的三角形区域，就改变了多边形的质心，影响了定位精度。

3)在无线传感器节点稀疏的环境下，当侦听到信标节点数量小于3 时，未知节点无法定位;当侦听到信标节点数量不小于3 时，但如果不存在PIT 三角形使未知节点位于其内，未知节点也是无法定位的。因此，在这种信标节点稀疏的环境下APIT 算法的定位覆盖率是很低的。

2 算法的改进

针对上述问题，结合DV-Hop 算法与两点定位法对APIT 算法进行改进，提出了一种混合型算法，该算法的流程图如图2 所示。

在对信标节点进行PIT 判断未知节点是否在由任意3 个信标节点组成的三角形区域内部时，判断条件在原APIT算法条件下，增加此原则［6］:通过RSSI 方法求得信标节点A，B，C 和未知节点M 这4 个节点的两两之间的距离，再利用三角形余弦定理求角度，若∠AMC+∠AMB+∠BMC=360°，M 位于三角形内;反之，判断M 位于三角形外。

图2 混合型算法流程图Fig 2 Flow chart of mixed algorithm

在选择优良的三角形，除去信号强度弱的三角形，选择原则:在信标节点密集时，设置一个门阈值P，P 为未知节点在PIT 点内的所有三角形3 个节点的信号强度和的平均值(记三角形个数为K)，不等式左边表示当前三角形3 个节点的信号强度之和，即限制条件公式为

在信标节点稀疏环境下，并且邻居信标节点不小于3时，利用DV-Hop 算法［1，2］进行定位。因为它通过距离矢量路由方法计算未知节点与信标节点的最小跳数，并计算每跳的平均距离，每跳平均距离与最小跳数的乘积就作为未知节点与信标节点之间的估算距离，当存在3 个信标节点时，使用三边测量法或最大似然估计法计算出未知节点的坐标。

只有2 个邻居信标节点的环境下，利用两点定位法［7］进行节点定位，它根据RSSI［4］分别测得未知节点与2 个信标节点的距离，再根据这2 个信标节点的坐标，求得未知节点的坐标。

3 仿真结果与分析

本实验在Matlab 仿真平台实现，实验模型的特点及其参数如下:

1)无线传感器网络覆盖范围:1 000 m×1 000 m 的二维平面。

2)本网络布放200 个传感器节点，信标节点与未知节点是比例根据实验参数而定，各个节点是随机分布的，通信半径是200 m，都具有相同的通信、感知、存储能力。

3)此环境是理想的虚拟环境，没有考虑外部环境对无线信号在传播过程没有干扰，无线信号只因距离传播才会出现能量损耗。

对APIT 算法进行改进后(即减小PIT 时的三角形误判和选择优良的三角形)，根据仿真结果，如图3 所示，信标节点比例稀疏时，改进后的APIT 算法定位精度提高较小(在3%以下);随着信标节点的增加，定位精度明显提高(提高4%～8%左右)。整体而言，改进后的APIT 算法定位精度较大提高。

图3 改进前后APIT 算法定位精度比较Fig 3 Localization precision comparison between APIT and improved APIT algorithm

根据混合型算法的仿真结果，如图4 所示，在信标节点稀疏时，随着混合型算法定位覆盖率的增大，定位精度受到一定的影响。但随着信标节点比例的增大，在信标节点密集环境下混合型算法的定位精度也将增大。如图5 所示，在信标节点比例稀释条件下，混合型算法的定位覆盖率比APIT 算法将明显增大。因此，这种混合型算法大大提高了信标节点稀疏环境下的定位覆盖率。

图4 APIT 和混合型算法定位精度比较图Fig 4 Localization precision comparison between APIT algorithm and mixed algorithm

4 结 论

图5 定位覆盖率比较图Fig 5 Localization coverage rate comparison

为了提高信标节点密集环境下的定位精度、稀疏环境下的覆盖率，本文以APIT算法为基础，提出了一种混合型定位算法。通过减小PIT 的三角形误判、选择优良的三角形，对APIT 算法进行改进，提高了信标节点密集环境下的定位精度，并在此基础上，根据DV-Hop 算法的优点和两点定位算法的特点，提高了信标节点稀疏环境下的定位覆盖率。

［1］ 孙利民，李建中，陈 渝，等.无线传感器网络［M］.北京:清华大学出版社，2006.

［2］ 郑 军，张宝贤.无线传感器网络技术［M］.北京:机械工业出版社，2012:133-147.

［3］ He T，Huang C，Blum B M，et al.Range-free localization schemes for large scale sensor networks［C］∥Proceedings of the 9th Annual International Conference on Mobile Computing and Networking，ACM，2003:81-95.

［4］ Sahu P K，Wu E H，Sahoo J.DuRT:Dual RSSI trend based localization for wireless sensor networks［J］.IEEE Sensors Journal，2013，13(8):3115-3123.

［5］ Ssu K F，Ou C H，Jiau H C.Localization with mobile anchor points in wireless sensor networks［J］.IEEE Transactions on Vehicular Technology，2005，54(3):1187-1197.

［6］ 胡中栋，贾方方.基于角度判断的无线传感器网络APIT 定位算法研究［J］.传感器与微系统，2013，32(1):73-75.

［7］ Chen B，Sun J，Xu W B，et al.A mixed localization algorithm based on RSSI and APIT with fitness analysis and optimization［C］∥2012 11th International Symposium on Distributed Computing and Applications to Business，Engineering＆Science(DCABES)，IEEE，2012:164-168.