基于联合分步APIT定位算法的改进

汤文亮，蔡 静，周琳颖，桂玉杰

(1.华东交通大学 软件学院，南昌 330013； 2.华东交通大学 图书馆，南昌 330013)

基于联合分步APIT定位算法的改进

汤文亮1，蔡 静1，周琳颖1，桂玉杰2

(1.华东交通大学 软件学院，南昌 330013； 2.华东交通大学 图书馆，南昌 330013)

针对无线传感网络(wireless sensor network,WSNs)APIT节点定位算法在锚节点低密度环境下的节点误判和节点失效等问题给出了改进，在APICT定位算法的基础上提出了联合分步定位算法UNION-APICT(union approximate point-in-circumcircle Test)，该算法是结合连通性的测距技术，RSSI测距技术以及质心定位和APICT等技术，来联合解决对未知节点定位问题;通过仿真实验结果表明，改进后的UNION-APICT在APICT算法的基础之上平均定位误差减少了10%～25%，定位性能有了明显的提升；随着通信半径R和最大探测距离rmax的增加，定位误差也在逐渐减小，该算法较APIT和APICT定位算法在锚节点密度、节点覆盖率和定位精度上都有所提高。

无线传感器网络;APICT;UNION-APICT;锚节点密度;节点覆盖率;定位精度

0 引言

无线传感网络(wireless sensor networks，WSNs)广泛应用于医疗卫生，环境监测(如：森林突发火灾，石油管道破裂具体地点监测)，军事等领域[1]。节点定位作为一项基本技术，它是无线传感器网络中收集环境信息、目标检测和跟踪的应用的基础[2]。因此如何让无线传感网络更广泛地应用到实际领域里面去是近几年的研究热点，国内外专家学者在提高定位节点的定位精度付出了很多的努力[3]。因而，研究定位算法，提高节点定位精度，实现传感网络的普及是有着重要意义。

目前，根据定位过程中是否测量实际节点间的距离，大致可以分为测距(range-based)和非测距( range-free) 算法[4]定位算法；在众多的定位算法中[5-9]，APIT (approximate point-in-triangulation test) 定位算法具有实现起来简单，定位功耗较小、精度高且成本低的优点，它是节点定位技术研究领域中的一大热点[10]。但是APIT算法会因为未知节点临近锚节点分布不均匀或锚节点由于在一条直线上不能组成三角形等原因，其节点定位受到了影响，达不到合适定位精度[11]。文献[12]引入了移动锚节点的概念，通过使用移动锚节点让锚节点分布起来更均匀；并且将异构传感器添加进来进行节点布置，该文献中还使用了RSSI模型对改进的APIT算法进行修正，但是缺点也在这里，由于RSSI进行取值，所以RSSI的误差也就成了定位精度里的最大影响因子；文献[13]采用分步定位算法对未知节点进行测量，该算法是只需要3个参考节点进行定位，有效地避免使用三边测量法无解的情况，适应性强、实用性强，但该文仅用一种算法使在锚节点密度低的情况下无法定位。

文献[14]提出了一种基于三角形外接圆覆盖的改进APIT定位算法。该算法改进后，在节点密度一定的情况下性能优于APIT。但APICT(approximate point-in-circumcircle test) 算法在针对节点应用在复杂环境下，没有考虑怎么使用最少的锚节点达到节点覆盖率最优的状态，所以本文在研究APICT算法的基础上，发现了一种可以参考各未知节点之间的位置关系来实现定位的方法，并拟名为联合分步定位算法UNION-APICT(union approximate point-in-circumcircle test)，它将定位技术联合起来对未知节点进行分步协同定位，这样得出在锚节点低密度分布情形下的一个新的高精度定位算法。

1 UNION-APICT算法

联合分步定位算法UNION-APICT利用三边测量法或极大似然估计、基于接收信号能量(RSSI)的测距技术、基于连通性的测距技术以及质心定位等技术对待定位节点的估测位置进行多次定位，从而达到提高网络定位覆盖率和定位精度的目的。

1.1 UNION-APICT算法思想

UNION-APICT定位算法的基本思想是：

1)若待定位节点S不能与锚节点进行相互通信，则通过基于连通性的测距方法获得相邻节点间的距离，利用三边测量法或极大似然估计法对待定位节点M进行定位，得到最终位置坐标；

2)若S能与锚节点进行通信，则按照 APICT 定位算法的步骤[14]求出S的估测位置P；

3)S向以P为圆心，以r(r<=R)为半径的目标圆形区域内发射探测信号，假设ESSI和RSSI的值分别为PE和PR，当圆形区域内的节点一旦接收到来自S的探测信号，则立刻将带有S的标识ID、信号强度和位置坐标等信息向周围广播出去，S接收并记录探测信号覆盖范围内锚节点的节点信息及PE和PR，求出每个锚节点的PE和S的PR之间的差值，最后通过S位置坐标计算公式求得S的最终坐标(x,y)。

在理论基础下，可得出无线信号传播模型中信号的强度和距离两者之间的关系如式(1)所示:

(1)

PR(d)表示在参距离等于d时，在接收点处得到的RSSI值；PR(d0)则表示在参考距离等于d0时的RSSI值；n表示路径消耗指数，由公式(1)式可以得到PE与PR之间的差值：

(2)

UNION-APICT算法涉及RSSI的相关应用，无线信号在传播过程中通过RSSI得到的PE和PR能算出传播过程中的功率消耗，最后可以通过无线信号转播模型将功率损耗即可推得两者间的距离。

1.2 UNION-APICT算法流程

1.2.1 算法流程图

UNION-APICT算法流程如图1所示。

图1 UNION-APICT定位算法流程图

2 仿真结果及分析

仿真实验使用Matlab7.0实现。

2.1 仿真实验相关参数设置

本实验中为凸显复杂环境下出现的低密度节点分布情况，将实验参数初步设定如下：通信区域为300 m×300 m，锚节点的R与待定位节点的R的比例系数为1，即两者的R相同。

2.2 仿真实验与结果分析

本节将对联合APICT定位算法以及三边测量法或极大似然估计、RSSI测距技术、基于连通性的测距技术等进行分步的UNION-APICT算法进行仿真实验，并分别从不同的节点总数N、锚节点比例H、最大探测距离r和通信半径R等方面和APICT 定位算法在定位精度上进行对比分析。

2.2.1 节点总数和锚节点比例不同

当锚节点数量N=100和200，且锚节点比例H分别为0.05、0.1、0.15、0.2、0.25、0.3时，UNION-APICT定位算法与APICT定位算法的定位误差对比如图2和图3所示。

图2 N=100定位误差对比图

图3 N=200定位误差对比图

根据上图数据我们可以推出UNION-APICT的定位误差总是比APICT低，且在N不同时，随着H的增大，UNION-APICT的定位误差逐渐降低，APICT的定位误差基本维持在0.42左右。经计算可知：当锚节点数量N=100和N=200时，UNION-APICT算法比APICT算法的平均定位误差分别减少12.5%和21%。

对比分析上述两图数据可知：不论当N相同时，H不同，或者当H相同，N不同时，UNION-APICT定位算法的定位误差都相对APICT定位算法趋于平稳，也就是说即使在低密度节点总数覆盖下或低密度锚节点比率覆盖情况下，UNION-APICT相对APICT定位算法算法定位误差仍旧相差无几。由此可得出结论：在复杂WSN中(尤其低密度WSN情况下)，UNION-APICT定位算法相对APIT定位算法更适用，且精度更高。

2.2.2 节点通信半径R不同

当锚节点数量N=200，锚节点比例H=0.2，节点通信半径R分别为 20 m、60 m、100 m、140 m、180 m，待定位节点的探测距离r的范围为(0.1R，0.5R)时，UNION-APICT定位算法与APICT 定位算法的定位误差对比如图4所示。

图4 不同R的定位误差对比图

由图4可知，UNION-APICT算法的定位误差明显比APICT 的定位误差小，在随着测距半径R的增大，UNION-APICT定位算法误差呈现下降的趋势，而APICT的误差基本上是保持不变的。原因是随着R的逐渐增大，待定位节点发射探测信号的r也跟着增大，与此同时探测目标区域内锚节点密度也随之增大，这样就使得最终的节点定位误差有所降低，但是APICT的定位误差虽然从R开始增大的时候就开始慢慢减小，但是当R增大到250 m后，基本维持在0.42不变，这就说明了UNION-APICT定位算法的良好可扩展性。

通过上述分析可得出结论：在R逐渐增大时，UNION-APICT定位算法的平均定位误差比APICT定位算法减小18%，且随着R的增大，UNION-APICT的定位误差也在逐渐降低。

2.2.2 最大探测距离rmax不同

图5是当N=100，H=0.2，R=60 m，待定位节点最大探测距离rmax分别为 0.5 R，0.6 R，0.7 R，0.8 R，0.9 R时，UNION-APICT定位算法的定位误差图。如图可知，随着rmax增大，UNION-APICT算法的定位误差不断减小，但是减小幅度不大，当rmax=0.7R时，UNION-APICT算法的定位误差趋于稳定了，这是因为当rmax逐渐增大时，待定位节点的探测圆形咪表区域内锚节点的密度也随之增大，这样使得待定位节点和锚节点之间的二次通信后的所得到的定位精度有所提高，而当目标区域内的锚节点数量达到一定值时，UNION-APICT定位算法的误差也随之趋于稳定。

图5 不同rmax的定位误差图

因此，经过以上实验及分析可知：在一定范围内，UNION-APICT算法会随着rmax的增大，节点定位精度会跟着也会有所提高。

3 结论

本文在APICT定位算法的基础提出了联合分步定位算法UNION-APICT，通过实验及分析可知UNION-APICT算法是一种适应在低密度的环境下也能保证较高定位精度和较高定位覆盖的定位算法，此算法在APICT算法的基础之上平均定位误差减少了10%～25%，定位性能有了明显的提升；另外，当通信半径R和最大探测距离上面rmax，随着R和rmax的增加时，定位误差也在逐渐减小，相比APIT算法可扩展性有所提升。

[1] Ahmadalipour A, Sadeghzadeh J, Vafaei A A, et al. Effects of environmental enrichment on behavioral deficits and alterations in hippocampal BDNF induced by prenatal exposure to morphine in juvenile rats[J]. Neuroscience, 2015, 305(10): 37-43.

[2] Zhu C, Zheng C, Shu L, et al. A survey on coverage and connectivity issues in wireless sensor networks[J]. Journal of Network & Computer Applications, 2012, 35(2):619-632.

[3] Han G J, Chao J, Zhang C Y. The impacts of mobility models on DV-hop based localization in Mobile Wireless Sensor Networks[J]. Science(S1084-8045), Journal of Network & Computer Applications, 2014, 42(4): 70-79.

[4] 彭 宇，王 丹.无线传感器网络的定位技术综述[J].电子测量与仪器学报, 2011, 13(6) :25-29.

[5] 毛利洋，林秀晶，邵开来，等.基于RSSI的无线传感网络协同定位算法及其应用[J].机电工程，2012(1):116-119.

[6] 陈凤娟. 无线传感器网络中的节点定位算法[J]. 信息安全与技术, 2013, 4(10): 60-61.

[7] 陈 伟. 基于压缩感知的无线传感网络定位研究[D]. 南京：南京邮电大学，2014.

[8] 石 欣，印爱民，陈 曦.基于RSSI的多维标度室内定位算法[J].仪器仪表学报，2014(35):261-268.

[9] 夏心江, 胡 钢, 王烨华. 基于锚球交域重心的WSN三维定位算法研究[J]. 计算机工程与应用, 2013(10): 76-79.

[10] 陈 涛. 无线传感器网络改进APIT定位算法[D]. 广州：暨南大学, 2012.

[11] 吴 栋，纪志成，张 彪. 基于无线传感器网络的改进APIT定位算法[J]. 系统仿真学报，2015(27): 2965-2972.

[12] 马正华, 章 明, 李 敏, 等. 分步定位法在ZigBee定位系统中的应用[J]. 测控技术, 2012, 31(4): 111-113.

[13] 冯秀芳, 崔秀锋, 祈会波. 无线传感器网络中基于移动锚节点的APIT的改进定位算法[J]. 传感技术学报, 2011, 24(2): 269-274.

[14] 汤文亮, 周琳颖. 基于三角形外接圆覆盖的改进APIT定位算法[J]. 传感技术学报, 2015(1): 121-125.

[15] 杨成成. 基于ZigBee的CNG加气站可燃气体泄漏检测与定位系统研究[D]. 北京：中国石油大学, 2011.

Improved APIT Localization Algorithm Based on Joint Step

Tang Wenliang1，Cai Jing1，Zhou Linying1, Gui Yujie2

(1.School of Software, East China Jiaotong University, Nanchang 330013, China; 2.Library, East China Jiaotong University, Nanchang 330013, China)

The classic APIT(approximate Point-in-Triangulation test) algorithm has been utilized in node localization in wireless sensor networks for major applications, however, it is easily fall into nodes misjudgments and node failure as its accuracy can not be guaranteed in low node density scenarios. To solve this problem, this paper proposes an improved node localization algorithm UNION-APICT(union approximate Point-in-Circumcircle test) which focuses on improving the localization accuracy by combining the connected ranging method, the RSSI ranging technology, the centroid localization and APICT together, which can solve the unknown node localization problem effectively. The simulation experiment results demonstrate that the UNION-APICT can achieve the lower average location error as much as 10% to 25% than APICT scheme. And when the communication radius R and the maximum detection range Rmax increasing, the node localization error decreasing accordingly. Compared with the APIT and APICT localization algorithms, the new UNION-APICT can get performance improvement significantly both in anchor nodes density, the coverage, and localization accuracy.

wireless sensor networks; APIT; UNION-APICT; anchor node density; node coverage; positioning accuracy

2016-07-17；

2016-08-04。

2014年省科技计划项目(2014X0012);2016年省科技计划项目(20161BBE50092);2014年省教育规划课题(14YD002)。

汤文亮(1969-)，男，教授，硕士生导师，主要从事无线传感器网络和信息安全方向的研究。

1671-4598(2016)12-0213-03

10.16526/j.cnki.11-4762/tp.2016.12.061

TP393.3

A