无线传感器网络APIT算法边界效应的改进

冀常鹏　丰竹松　华一阳

1(辽宁工程技术大学电子与信息工程学院　辽宁 葫芦岛 125100)

2(辽宁工程技术大学研究生院　辽宁 葫芦岛 125100)



无线传感器网络APIT算法边界效应的改进

冀常鹏1丰竹松2华一阳1

1(辽宁工程技术大学电子与信息工程学院辽宁 葫芦岛 125100)

2(辽宁工程技术大学研究生院辽宁 葫芦岛 125100)

摘要在无线传感器网络中，针对APIT算法存在边界效应导致定位精度不足的问题，提出一种基于节点信号强度和的改进定位算法SAPIT(sum of signal strength based APIT)。该算法在PIT测试前，先确定三角形内所有节点收到三个锚节点信号强度和的最小值，利用该最小值排除引起边界效应的邻居节点；然后结合PIT测试和网格扫描算法，确定待定位节点的坐标位置。仿真结果表明，SAPIT算法降低了In-To-Out Error和Out-To-In Error的发生概率，有效地提高了节点的定位精度。

关键词无线传感器网络边界效应信号强度和定位精度

IMPROVEMENT OF BOUNDARY EFFECTS OF APIT IN WSN

Ji Changpeng1Feng Zhusong2Hua Yiyang1

1(School of Electronic and Information Engineering,Liaoning Technical University,Huludao 125100,Liaoning,China)2(Institute of Graduate,Liaoning Technical University,Huludao 125100,Liaoning,China)

AbstractIn wireless sensor networks, for the problem that the boundary effects existing in APIT algorithm cause the lack of localisation precision, we proposed an improved localisation algorithm which is based on the sum of signal strength of nodes (SAPIT). The SAPIT algorithm determines the minimum sum of signal strength of three anchor nodes received by all the nodes in triangle before the PIT test. Then the algorithm uses the minimum sum to eliminate the neighbour nodes incurring the boundary effects. Finally, it combines PIT test with gird scanning algorithm to determine the coordinate positions of the unknown nodes. Simulation results showed that the SAPIT algorithm reduced the probabilities of occurrence of in-to-out error and out-to-in error, and effectively improved the precision of nodes localisation.

KeywordsWireless sensor networksBoundary effectsSum of signal strengthLocalisation precision

0引言

在无线传感器网络中存在着大量随机分布的传感器节点，每一节点都可作为一个独立的数据采集器，对检测区域进行实时监控。对节点返回的数据信息进行处理时，如果节点的位置信息不能得到确定，那么采集的数据将失去意义。因此，传感器节点的自定位问题成为无线传感器网络的重要研究内容之一。如今传感器在实际中被广泛应用，如环境检测、汽车跟踪、地理标记以及水下传感器[1]，都需要将节点位置信息作为一项重要指标。此外，节点的位置信息也被用于改进网络方案，譬如在基于路由协议的网络中，位置的确定能省去路由遍历的过程，从而节省寻找路由所用的时间和能量[2]。

目前存在的定位算法根据其是否需要测定节点间的距离分为两大类：一类是基于测距的定位算法，代表算法有RSSI、TDOA、TOA和AOA等定位算法[3]；一类是非基于测距的定位算法[4]，常用算法有质心算法、APIT算法和DV-hop算法等[5]。基于测距的定位算法比非基于测距的定位算法的定位精度高，但同时对硬件有较高要求，成本也随之增加。非基于测距的定位算法虽然定位精度稍低，但完全可以满足实际需要，且对硬件要求较低，在成本和功耗方面均具有优势。因此，非基于测距的定位算法一直是研究的热点。

APIT算法由He等人在2003年提出[6]，相比于其他非基于测距的定位算法，APIT算法由于定位精度高，通信开销小等优点而备受关注。但是APIT算法一直存在边界效应问题，即In-To-Out Error和Out-To-In Error。针对Out-To-In Error问题，周勇等人提出了三角形重心扫描算法[7]，而针对In-To-Out Error问题，韩彪[8]等人通过设置影响因子来减小误差。由于改进后误差仍然较大，王新生[9]等人在前人改进的基础上，设置计数器来减小误差，但该方法增加了能量损耗。文献[10]利用三角形面积和对有效三角形进行判断，文献[11]利用角度和对有效三角形进行判断，但两种方法计算量很大，致使定位时间加长[10,11]。文献[12-14]通过结合其他定位算法进行改进，在提高定位精度的同时加大了算法的复杂程度。Chiti和姚艳等人分别从扫描算法上对APIT算法进行改进，没从根本上解决边界效应带来的误差[15,16]。以上算法均对APIT算法进行了改进，在一定程度上减小了定位误差，但都没有同时对In-To-Out Error和Out-To-In Error进行很好地解决。本文从引起边界效应的根源入手，对APIT算法进行改进，提出一种基于节点信号强度和的定位算法—SAPIT算法。该算法较好地解决了边界效应的问题，明显提高了节点的定位精度。

1APIT算法分析

APIT算法的主要思想：在初始阶段，未知节点先收集邻居锚节点信息;然后通过判断确定包含未知节点的三角形，把多个三角形形成的重叠区域的质心作为未知节点的坐标。

1.1APIT算法步骤

第一步信息收集阶段。未知节点收集邻居锚节点的信息，包括信号强度、坐标等，同时邻居节点之间交换所接收到的锚节点信息。

第二步PIT测试阶段。用三角形内点测试法判断未知节点是否位于锚节点组成的三角形内，重复进行直至所有锚节点组合测试完毕。

第三步利用网格扫描算法得出三角形重叠部分，求出该重叠区域的质心位置，以此作为待定位节点的坐标[17,18]。

1.2APIT算法误差分析

在APIT算法中，判断未知节点是否位于锚节点组成的三角形内部是算法的关键步骤。该步骤以三角形内点测试法(PIT)作为理论依据，其定义如下：若点M位于三角形外部，则存在一个方向，使得点M沿此方向移动时，能够同时靠近或远离三角形的三个顶点A、B、C；否则，点M位于三角形内部。

在上述PIT测试中，节点M被假定为可移动的。但在实际传感器网络中，待定位节点大多是静止的，这使得APIT测试应运而生。其定义如下：假设节点M的所有邻居节点均不同时靠近或远离3个锚节点A、B、C，那么点M位于三角形内部；否则，点M位于三角形外部。

在APIT算法中，要想判断未知节点是否位于三角形内部，必须通过与邻居节点交换信息，这使得算法判断结果与邻居节点的分布密切相关。并且APIT只能判断有限的方向，因此，在实际测试中，常出现将内部节点判断为外部节点(In-To-Out Error)或将外部节点判断为内部节点(Out-To-In Error)的情况，统称为边界效应[19,20]。

如图1中(a)所示，节点M原本位于三角形内部，但邻居节点1从三个锚节点收到的信号强度值均小于M收到锚节点的信号强度值。根据APIT定义，判定M位于三角形外部，发生In-To-Out Error。由此可知，只有当邻居节点没有移出三角形外部时，PIT测试才能成立。

如图1中(b)所示，节点M原本位于三角形外部，与邻居节点1、2对比后，没有同时远离或者同时接近三个锚节点的邻居节点。根据APIT定义，判定M位于三角形内部，发生Out-To-In Error。这是由于邻居节点数目过少，节点密度低造成的。

图1　In-To-Out Error和Out-To-In Error

2SAPIT算法

通过对APIT算法分析可知，APIT算法产生误差的主要原因是部分邻居节点导致了边界效应。若能减少此类邻居节点，则可以提高节点定位的精确度。基于这一思想，本文提出一种基于信号强度和的改进算法。该算法在PIT测试前，先确定三角形内所有节点收到三个锚节点信号强度和的最小值，利用该最小值排除引起边界效应的邻居节点，然后结合PIT测试和网格扫描算法，确定待定位节点的坐标位置。

2.1传播模型

无线电传播模型分为规则传播模型和不规则传播模型。其中不规则传播模型更加接近于现实传播[21,22]。不规则传播模型相比规则传播模型，增加了相关参数，但对SAPIT算法理论推导没有影响，因此选择规则传播模型作为该算法推导的基础。规则传播模型公式如下：

(1)

其中，PR(d)是距离发送节点d米处收到的信号强度，Pr为发送节点的发送功率，PL(do)是参考距离为d0米的路径损耗。参照规则传播模型的经典取值，将η取为4，A=Pr-PL(do)，d0=1m，故可写成：

PR(d)=A-40logd

(2)

2.2确定最小信号强度和

在三角形内，若某一节点收到的三个锚节点信号强度之和最小，那么三角形内任意节点信号强度和均大于该最小信号强度和。又由于信号在传播过程中逐渐减小，那么三角形外任意节点收到的信号强度和均小于该最小信号强度和。在APIT算法中，产生误差的主要原因在于邻居节点的合法性(即是否会产生边界效应)不能保证。而在SAPIT算法中应用上述理论，可对邻居节点的合法性进行判断，通过最小信号强度和能够把不合法的邻居节点排除，从而使PIT测试更加准确。下面推出此最小信号强度和的位置所在。

若某点处的节点收到三个锚节点信号强度之和最小，其中di、dj、dk为此点到三个锚节点的实际距离，那么：

Pmin=PR1(di)+PR2(dj)+PR3(dk)

=3A-40log(di×dj×dk)

(3)

图2　锚节点构成锐角三角形

令S= di×dj×dk，当P取最小值时，S取最大值。因此，要想求得Pmin，可以通过求Smax获得。

为求锚节点组成的三角形内的Smax，分别对可能形成的锐角三角形、直角三角形、钝角三角形进行分析，每类三角形各取5点作为参考。图2-图4为三类三角形示意图，表1-表3为三类三角形S值表。

表1　锐角三角形各点S值

对10个锐角三角形各取50个点计算其S值，最终确定S的最大值点位于最长边的中点处。

图3　锚节点构成直角三角形

取点位置N(最长边中点)O(直角边一点)L(直角边AC一点)E(三角形外一点)J(三角形内一点)S=di×dj×dk21693.39198.88284.64165.85

对10个直角三角形各取50个点计算其S值，最终确定S的最大值点位于最长边的中点处。

图4　锚节点构成钝角三角形

取点位置T(三角形最长边中点)K(靠近T的点)M(三角形边一点)L(三角形边一点)F(三角形外一点)S=di×dj×dk128.29137.19118.9975.20187.38

对10个钝角三角形各取50个点计算其S值，其最大值点并非位于最长边的中点处。三边S值分布大体趋势如图5所示，从图中可以看出，最大值点位于最长边的中点附近。

图5　钝角三角形三边各点的S值(AB最长)

通过对三类三角形分析可知，当锚节点构成的三角形为锐角三角形或直角三角形时，Smax点位于三角形最长边的中点处；当锚节点构成的三角形为钝角三角形时，Smax点位于最长边中点的附近，由于误差比(Smax-S中)/Smax最大约为5%，对算法判定影响很小，因此误差可忽略，仍将Smax点看作位于最长边的中点处。锚节点组成的三角形越不规则，S最大值点偏离最长边中点处的程度越大。但在传感器网络中，传播模型大致为圆形，锚节点组成三角形相对规则。综上所述，三角形最长边中点处的S值最大，同时信号强度和最小。因此取三角形最长边中点处的信号强度和为最小信号强度和。

2.3改进算法的步骤

1) 在进行PIT测试前，锚节点通过广播向其通信范围内的所有未知节点发送坐标、标识号、信号强度等信息，节点在传感器内寄存所接收到的信息。表4为节点收到的锚节点信息，其中A、B、C表示锚节点，(X,Y)为锚节点的坐标信息，SS为节点接收的锚节点信号强度值。

表4　接收的锚节点信息

2) 在锚节点广播信息后，待定位节点同其通信范围的邻居节点交换并存储节点信息。表5为交换后的信息表。

表5　信息交换后节点的信息

3) 待定位节点收到广播信息后，从接收到信号的所有锚节点中任意选取3个，计算所组成的三角形各边长以获得最长边。求其中点坐标，计算中点到三个锚节点距离，然后通过传播模型计算三角形内最小信号强度和。过程如下:anchor_i(xi，yi), anchor_j(xj，yj),anchor_k(xk，yk)分别为锚节点坐标。

(4)

比较Dij、Dik、Djk，若Dij≥Dik≥Djk，取Dij中点M的坐标为：

(5)

计算：

(6)

求得：

Pmin=PR1(Dmi)+PR2(Dmj)+PR3(Dmk)

=3A-40log(Dmi×Dmj×Dmk)

(7)

4) 确定Pmin后，将邻居节点收到的三个锚节点信号强度相加，同最小信号强度和Pmin作比较。若邻居节点的信号强度和满足同时大于或同时小于该最小信号强度和，则进行PIT测试。若不满足，则对不满足的邻居节点进行下一组锚节点测试准备。重复步骤3)、步骤4)，直到所有锚节点组合测试完毕。

5) 利用网格扫描算法找出三角形重叠部分，对重叠区域求其质心作为待定位节点的坐标。

3算法仿真

本文采用MATLAB软件对SAPIT算法和APIT算法进行仿真，算法流程如图6所示。

图6　算法流程图

1) 传感器节点部署区域为1000 m×1000 m的正方形区域。

2) 300个节点随机分布在网络区域，普通节点的通信半径为200 m，锚节点的通信半径为普通节点的2倍，即400 m。

网络连通度：网络连通度表示在未知节点通信范围内的邻居节点的个数。

图7是锚节点个数为90，节点总数为300的随机分布图；图8和图9分别是用APIT算法和SAPIT算法得到的定位误差图。

将图8和图9进行对比可以发现，相比于APIT算法，SAPIT算法的定位误差更小。在APIT算法中，由于存在较严重的边界效应，导致PIT测试不准确，有效三角形判断错误，从而产生多个重叠区域。这使得APIT算法的定位误差不仅表现为数值较大，而且具有多个方向值。SAPIT算法通过判断邻居节点的合法性，在很大程度上抑制了边界效应的发生，使PIT测试更加准确，重叠区域较好地反映了节点的实际位置，使定位更加精准。

图10为APIT算法和SAPIT算法在不同网络连通度下归一化的平均误差(定位误差和通信半径之比)的比较。

图7　节点分布图　　　　　　图8　APIT定位误差图

图9　SAPIT定位误差图　　　图10　不同连通度下的误差

从图10可以看出，在连通度较低的情况下，SAPIT算法比APIT算法定位精度要高，此时影响定位精度的因素绝大部分是 Out-To-In Error，这说明SAPIT算法在一定情况下有效地抑制了Out-To-In Error，具体情况如图11所示。

随着网络连通度的增加，Out-To-In Error对精度的影响程度减小，In-To-Out Error对精度影响程度加大。从图10可以看出，随着连通度增加，APIT算法的定位误差出现反弹现象，这是由于随着邻居节点的增加，致使APIT算法发生In-To-Out Error概率增大，从而导致短时间内误差增大。而SAPIT算法的定位误差没有出现反弹现象，这是由于在PIT测试前，通过把邻居节点的合法性进行判定，把不符合要求的邻居节点排除，再进行PIT测试，避免了大部分In-To-Out Error，较好地控制了反弹现象。从图10中还可以看出，在网络连通度达到10以后，SAPIT算法定位精度明显高于APIT算法定位精度，说明对In-To-Out Error很好地解决，大大提高了定位精度。

图12是节点总数为300个，不同锚节点个数的情况下两种算法归一化的平均误差(定位误差和通信半径之比)的比较。

图11　特殊的Out-To-In Error　图12　不同锚节点数目下的误差

图12表明，当锚节点个数占总体比为10%左右时，APIT算法和SAPIT算法定位误差都较大。这是由于锚节点比例较小，很多未知节点不能收到锚节点信息所导致的。当锚节点数目逐渐增多，可以看到SAPIT算法定位精度有显著提升。其原因是SAPIT算法有效地解决了In-To-Out Error，并在一定程度上减少了Out-To-In Error，使有效三角形的数量增多，错误三角形的数量减少，三角形重叠部分质心很好地反映了未知节点的具体位置。在仿真实验中，随着锚节点数目的增加，定位时间加长，故选取最大锚节点个数占总体比例的50%，相较于APIT算法，SAPIT算法将定位精度提高了14%左右。

4结语

本文针对APIT算法中存在In-To-Out Error和Out-To-In Error，提出了一种基于节点信号强度和的SAPIT算法。仿真结果表明，SAPIT算法较于APIT算法，有效地提高了定位精度。相较于其他的APIT改进算法，SAPIT算法不需要结合其他定位算法，也不需要进行大量的计算和三角形分割，有效地节省了传感器的能量，在实际应用中具有广阔前景。但SAPIT算法仍有不足，改进算法只对一定情况下的Out-To-In Error进行了修正。下一步的工作将集中针对Out-To-In Error做出更精确的修正，提高算法的定位精度。

参考文献

[1] Guo Y,Liu Y.Localization for anchor-free underwater sensor networks[J].Computers & Electrical Engineering,2013,39(6):1812-1821.

[2] Zhang G,Ding Y,Xu J,et al.Tracking Algorithm of WSN Based on Improved Particle Filter[C]//2012 11thInternational Symposium on Distributed Computing and Applications to Business,Engineering & Science (DCABES).Guilin China:IEEE,2012:149-152.

[3] Zheng J,Wu C,Chu H,et al.An Improved RSSI Measurement In Wireless Sensor Networks[J].Procedia Engineering,2011(15):876-880.

[4] Luo X,Liu Y,Long C,et al.Range-free localization algorithms in wireless sensor networks[C]//Fifth International Conference on Machine Vision (ICMV 12).Wuhan China:SPIE,2013:87842A-8.

[5] Xiangqun L,Heng G,Linlin L.An improved APIT algorithm based on direction searching[C]//2009 5thInternational Conference on Wireless Communications,Net-working and Mobile Computing (WiCOM).Beijing China:IEEE,2009:1-4.

[6] He T,Huang C,Blum B M,et al.Range-free localization schemes for large scale sensor networks[C]//Proceedings of the 9thannual international conference on Mobile computing and networking.San Diego CAUSA:ACM,2003:81-95.

[7] 周勇,夏士雄,丁世飞,等.基于三角形重心扫描的改进APIT无线传感器网络自定位算法[J].计算机研究与发展,2009,46(4):566-574.

[8] 韩彪,徐昌彪,袁海,等.无线传感器网络中一种改进的APIT定位算法[J].计算机工程与应用,2008,44(4):122-124.

[9] 王新生,廖世奇.基于区域分割的无线传感器网络定位算法[J].计算机应用与软件,2013,30(4):231-234.

[10] Wang J,Jin H.Improvement on APIT localization algorithms for wireless sensor networks[C]//International Conference on Networks Security,Wireless Communications and Trusted Computing (NSWCTC 2009).Wuhan.NY:IEEE,2009,1:719-723.

[11] Zeng F,Yu M,Zou C,et al.An Improved Point-in-Triangulation Localization Algorithm Based on Cosine Theorem[C]//Wireless Communications,Networking and Mobile Computing (WiCOM),2012 8th International Conference on.Shanghai China:IEEE,2012:1-4.

[12] Xiufang F,Huibo Q.Improvement and Simulation for a Localization Based on APIT[C]//2009 International Conference on Computer Technology and Development (ICCTD 2009).Kota Kinabalu Malaysia:IEEE,2009,2:68-72.

[13] 冀常鹏,陈美玲.无线传感网络APIT定位算法的改进[J].仪表技术与传感器,2012,8(8):84-86.

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

[15] Chiti F,Pierucci L.API 2 T:a bit of improvement for applications in critical scenarios[C]//Proceedings of the 6th International Wireless Communications and Mobile Computing Conference.Chengdu China:ACM,2010:794-798.

[16] 姚艳,禹继国,郭强.基于网格扫描的无线传感器网络定位算法[J].计算机工程,2012,38(9):86-89,96.

[17] Tan H,Liu F.Research and implementation of APIT positioning algorithm in WSN[C]//2012 9thInternational Conference on Fuzzy Systems and Knowledge Discovery (FSKD).Chongqing:IEEE,2012:2212-2215.

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

[19] Zhang S,Cao J,Zeng Y,et al.On accuracy of region based localization algorithms for wireless sensor networks[J].Computer Communications,2010,33(12):1391-1403.

[20] 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).Guilin China:IEEE,2012:164-168.

[21] Chengxu F,Zhong L.A New Node Self-Localization Algorithm Based RSSI for Wireless Sensor Networks[C]//2013 Fifth International Conference on Computational and Information Sciences (ICCIS).Shiyan China:IEEE,2013:1616-1619.

[22] Wang S S,Shih K P,Chang C Y.Distributed direction-based localization in wireless sensor networks[J].Computer Communications,2007,30(6):1424-1439.

中图分类号TP393

文献标识码A

DOI:10.3969/j.issn.1000-386x.2016.02.025

收稿日期：2014-08-11。国家自然科学基金项目(61172144)。冀常鹏，教授，主研领域：计算机通信，无线网络。丰竹松，硕士生。华一阳，硕士生。