无线传感器网络中APIT--VP三维定位算法*

陈月娥， 余 敏

(江西师范大学 计算机信息工程学院，江西 南昌 330022)

0 引 言

无线传感器网络(wireless sensor networks, WSNs)具有随机部署、覆盖范围广、网络自组织、鲁棒性强等优点，故其应用范围非常广泛，如环境保护、军事监控、医疗护理、智能安防等领域[1]。在依赖于位置信息的无线传感器网络应用中,只有掌握了传感器节点的具体位置信息,才能够明确感知数据的实际意义，因此，节点定位技术是众多实际应用的基础和前提，是无线传感器网络研究的重点和难点。

目前，无线传感器网络节点定位算法根据是否需要测量节点间的距离将定位算法分为基于测距(range-based)和基于非测距(range-free)两大类。基于测距的定位需要特定的硬件设置，通过不同的测距技术，如TOA,TDOA,AOA及RSSI等，测量相邻节点之间的绝对距离或方位，然后再利用三边测量法、三角测量法或极大似然估计法等计算未知节点的位置；基于非测距的定位机制则无需距离或角度信息，仅根据邻近关系和连通性实现节点的定位，典型的定位算法有质心法、凸规划法、DV-HOP、APIT算法等[2～4]。基于测距的定位算法虽然可以取得较高的定位精度，但大都需要额外的硬件支持，使其在无线传感器网络的发展阶段性价比不高；而非测距的定位算法在不需要额外添加复杂硬件设备的情况下，能够满足大多数应用的定位精度，性价比高[5]。目前众多的距离无关的三维定位算法中，最为典型并且备受关注的是刘玉恒、蒲菊华等人提出的无线传感器网络近似三角形内点测试三维(approximate point-in-tetrahedron,APIT—3D)自身定位算法[6], 而本文正是在该算法的基础上提出了改进的无线传感器网络中近似三角形内点测试垂面(APIT—VP)分割三维定位算法。

1 算法描述

1.1 基于中垂面分割的三维定位方法

刘志强等人提出基于中垂面分割的无线传感器网络三维定位方法[7],首先根据待定位节点S周围的锚节点坐标，为节点S建立一个长方体，保证S周围的所有锚节点都在这个长方体内，然后再进行空间划分，把该长方体划分成一个个边长为N的小正方体;其次利用信号强度损耗可判断S到任意2个锚节点的距离远近，由此得出S节点肯定在这2个锚节点确定的中垂面的一侧，利用该中垂面来切割空间划分后的若干小正方体可以不断缩小定位区域;最后取其质心作为定位结果。

1.2 APIT—3D算法

该算法的基本思想是:未知节点收集其所有可见信标节点的位置信息，任意选择 4 个信标节点组成一个四面体，判断自己是否在四面体内部，如果未知节点在某个四面体内部,则认为该四面体为该未知节点的一个可能位置区域(possible location area，PLA)。通过循环的选取不同的四面体进行测试直至穷尽组合，筛选出所有是PLA的四面体，然后用三维网格扫描算法获得所有是PLA的四面体的交集空域，计算该空域的三维质心，并以此质心坐标估计未知节点的位置。

APIT—3D算法的理论基础是PIT—3D测试定理。如果存在一个方向，当未知节点沿此方向运动时，会同时接近或远离四面体的4个顶点，则此未知节点在四面体外部;否则,在四面体内部。

在实际测试中，可以利用无线传感器网络节点密集分布的特点，未知节点选取所有邻居节点判断各自距离信标节点的远近，从而可以在最大程度上近似实现对所有方向进行测试。PIT—3D测试中，一般采用接收信号强度指示(received signal strength indication，RSSI)来判断远离还是接近信标节点。

APIT—3D定位算法有几个重要缺陷：

1)在PIT—3D测试中，当邻居节点数量较少或未知节点处于某些特殊位置时，会引起测试出错，出现InToOut和OutToIn错误。

2)节点分布不均匀时，在节点密度较大的区域，邻居节点与信标节点数量过多引起PIT—3D测试计算量增大；而节点密度较小时，定位精度较低，更有可能出现未知节点周围的信标节点数目小于4个时，造成无法对未知节点进行定位。

3)在计算多个四面体重叠区域的重心时，采用网格扫描算法，计算复杂度较大，效率较低。

1.3 APIT—VP算法设计

针对APIT—3D定位算法存在的几个重大缺陷，本文在算法上进行如下改进：1)为了减少InToOut和OutToIn错误，在节点上设置相应的MAXRSS和MINRSS阈值来进一步判断。2)在邻居节点和信标节点数量较多的情况下设置RSSI阈值，将设定阈值范围内的节点视为合法节点，低于设定法制的节点视为不可见节点。当信标节点少于4个时，利用加权的三维质心定位算法对未知节点进行定位。3)利用中垂面分割法代替网络扫描算法以减少计算复杂度和节点能耗。

改进后的APIT—VP定位算法工作流程如下：

1)节点部署完成后，网络初始化配置。信标节点向网络广播消息(包括信标节点的ID、位置坐标等)。

2)未知节点W(x,y,z)周期性地接收可见信标节点的位置信息并记录信标节点的RSSI值，将可见信标节点按RSSI值降序排列组成节点W的信标节点队列W-List,若信标节点数量过多,则为信标节点队列设置最大长度。

3)设未知节点W从上一步获取了N个信标节点。若1≤N≤3，则执行步骤(4)；若N<1，则执行步骤(5)；否则，执行改进的APIT—3D算法：

a.从信标节点队列W-list中任意选取4个信标节点，使用PIT—3D测试方法进行测试，此时在节点上设置相应的MAXRSS和MINRSS阈值来进一步判断。对于初步判定为在四面体外部的节点，如果未知节点RSSI值大于设置的阈值，则认为发生IntoOut错误；同样，对于判定为在四面体内部的节点，如果RSSI小于设定的阈值，则认为发生OutToIn错误。将符合条件的四面体加入四面体集合；

c.若得到四面体集合为Φ，则转到步骤(4);否则设集合中有K个四面体，这K个四面体中有M个信标节点，基于这M个信标节点，使用基于中垂面分割的定位算法得到未知节点的估计位置。

4)若未知节点W的可见信标节点1≤N≤3，或者步骤(3)中得到的四面体集合为Φ，用下面的RSSI加权质心算法公式估算其坐标

5)N<1情况下，既未知节点周围没有可见的信标节点，此时等待t时间，然后未知节点向其邻居节点发出位置请求，此时未知节点监听到已知节点的个数为m,并设n=n+m，然后转入步骤(2)开始顺序往下执行。

6)循环执行步骤(1)～(5),以获得所有未知节点的坐标估计值。

整个算法的流程图如图1所示。

图1 算法流程图

2 仿真实验与结果分析

为了检验定位算法的有效性，使用Matlab 7.1 对算法进行了一系列仿真实验,主要通过定位覆盖率和定位误差来比较算法的性能。仿真实验构造边长为100 m的正方体三维空间实验区域，该空间区域内随机投放了300个节点，其中信标节点控制在5 %～30 %以内，所有节点的通信半径均相同。为了减少随机分布和偶然因素带来的影响，仿真的结果是在相同的参数下仿真50次的平均值。通过比较APIT—VP和APIT—3D算法在不同的信标节点比例的情况下的定位误差和定位覆盖率，最后来分析新算法的优劣。

2.1 定位覆盖率

定位覆盖率随信标节点比例变化关系如图2所示。由图2可以看出：当信标节点比例为5 %时，APIT—3D定位覆盖率约为10 %,而APIT—VP定位覆盖率约为30 %，这说明新算法由于考虑到信标节点数量较少时的特殊情况，此时定位覆盖率高于APIT—3D算法。随着信标节点比例的增加，2种算法的定位覆盖率都明显提高，当信标节点比例约为20 %时，APIT—VP算法定位覆盖率已达85 %左右，随后信标节点比例的增加对覆盖率的影响大大降低。这是因为APIT—VP算法中，将已知节点当做信标节点辅助定位，当信标节点达到一定数量即可实现绝大部分节点的定位。而APIT—3D算法的覆盖率随信标节点比例的增加一直处于稳定的上升趋势，说明APIT—3D算法对信标节点比例的依赖程度较高。

图2 定位覆盖率与信标节点比例变化图

2.2 定位误差

定位误差随信标节点比例变化关系如图3所示。由图3可以看出：当2种算法的定位误差达到35 %左右时，定位精度很难再得到改善。在信标节点比例为5%左右时，APIT—VP算法的定位误差明显大于APIT—3D算法，因为在信标节点数量较少时，APIT—VP定位过程中利用已知节点辅助定位，已知节点本身就有误差，使得定位误差得到了累加，故定位误差较大。当信标节点比例在20%左右时，2种算法的定位误差变化不明显，此时增加信标节点比例时，APIT—VP算法略优于APIT—3D算法，因为APIT—VP算法在一定程度上避免了OutToIn和InToOut这2种错误，并且中垂面分割法在减少计算复杂度的同时，提高定位精度。

图3 定位误差与信标节点比例变化图

3 结 论

本文基于无线传感网络中经典的APIT—3D算法，提出了改进的APIT—VP三维定位算法。在分析APIT—3D算法误差来源的基础上，对其进行了相应的改进,改进后的APIT—VP算法能够精确有效地实现三维空间中节点的定位。仿真实验表明：APIT—VP算法能达到理想的定位覆盖率和定位精度，定位覆盖率可达90 %，定位误差控制在25 %左右，是一种低功耗的三维定位算法。

参考文献:

[1] Zhang Ke,Zou Chengwu,Zhang Jianping,et al. RBDV—HOP:A novel improved DV—Hop licalization algorithm for wireless sensor networks based on RSSI[C]∥The 3rd International Conference on Information Science and Engineering, Yangzhou,China:IEEE,2011:5438-5441.

[2] Zhang Jianping,Yu Min,Zhang Ke,et al.An improved weighted triangle centroid localization algorithm of APIT for wireless sensor networks[C]∥2012 International Conference on Computer and Information Science, Safety Engineering, Wuhan,China:IEEE,2012:18-21.

[3] Zeng Fanzhen,Yu Min,Zou Chengwu,et al.An improved point-in-triangulation localization algorithm based on cosine theore-m[C]∥2012 8th International Conference on Wireless Communications,Networking and Mobile Computing, Shanghai,China:IEEE,2012:1652-1655.

[4] Rong P,Sichitiu M. Angle of arrival localization for wireless sensor networks[C]∥Proc of SECON′06, Reston, USA:IEEE,2006:374-382.

[5] Zhou Yong, Xia Shixiong, Ding Shifei.An improved APIT node self-localization algorithm in WSNs based on triangle-center scan[J].Journal of Computer Research and Development,2009,16(4):566-574.

[6] 刘玉恒,蒲菊华,赫 阳,等.无线传感网络三维自身定位方法[J].北京航空航天大学学报,2008,34(6):647-651.

[7] 刘志强,王行甫.基于中垂面分割的WSNs三维定位方法[J].计算机工程,2010,36(14):90-92.