基于四面体体积判断的三维APIT 定位算法

徐磊磊， 徐保国

(江南大学 轻工过程先进控制教育部重点实验室，江苏 无锡214122)

无线传感器网络(Wireless Sensor Networks，WSNs)是一种新型信息感知、收集和处理技术，其应用能否成功实施的关键是节点提供的位置信息是否准确［1-2］。目前，应用在传感器网络中的定位方法主要分为基于测距技术和非基于测距两类［3］。基于测距技术通常通过测量节点间的距离或角度关系，使用常用的定位方法(如三角测量法、三边测量法以及最大似然估计法等)估算出待定位节点的位置［4］。由于需要额外的硬件支撑且易受环境的影响，不太适用大规模传感器网络的部署。非基于测距的技术一般利用节点之间的邻近关系和连通性实现定位，无需额外的硬件，能够满足多数应用的定位要求，性价比较高。典型的算法有质心法、APIT算法［5］、凸规划算法、DV-Hop 算法［6］等。

目前，三维定位算法的研究通常在二维定位算法的基础上扩充维数形成新的三维定位算法。刘玉恒等［7］将二维的APIT 算法引入到三维空间，提出了APIT-3D 定位算法，在通信开销未显著增加的条件下获得了较好的定位精度，但此过程中容易发生边界效应，影响定位精度;相卫华等［8］提出利用三维网格定位解决重叠四面体区域的定位问题;胡伟等［9］提出了四面体质心迭代解决网格扫描算法计算复杂度问题，但在邻居节点数量较少或未知节点处于四面体边界时，会出现测试错误。

针对以上问题，文中提出一种基于四面体体积测试三维近似内点测试(VJ-APIT)的无线传感器网络定位算法，该算法利用推导出的体积公式改进内点测试方法，同时修正RSSI 测距误差。与传统的算法相比，改进后的算法减少了未知节点误判的概率，从而提高了定位精度。

1 APIT-3D 算法

APIT-3D 算法的基本原理:假设存在一个方向，待定位未知节点沿着此方向运动，同时接近或者远离四面体4 个顶点A，B，C，D，则未知节点在四面体区域外，否则，在四面体内［10］。同二维平面类似，由于实际的网络是静态网络，利用高节点密度模拟移动，通过无线信号传播特性判断未知节点接近还是远离锚节点，即通过比较邻居节点接收到的信号强度大小判定未知节点与该邻居节点跟锚节点的远近关系，从而有效模拟未知节点的移动，即APIT-3D测试。

在网络部署完成后，对监控区域进行网格划分，设网格分辨率为q，以一个锚节点为中心建立空间直角坐标系。设三维立体空间区域为正方体ψ，体积为V，对于任何一个立方体网格有φi∈ψ，则共有V/a3个网格，每个网格均为动态网格，初始化为0，可根据情况加减1。APIT-3D 测试结束后，所有包含待定位节点四面体区域的网格加1，不包含的网格减1。统计所有网格数值，找到权重最大的区域，即为需要寻找的区域。将重叠区域的质心作为待定位节点的估算位置。

2 VJ-APIT 算法原理

和二维算法类似，APIT-3D 同样存在着In-to-Out Error 和Out-to-In Error 两种误判，文中提出的改进APIT-3D 算法从避免两种误判发生的角度出发，基本思路是通过所推导的体积计算公式，利用四面体体积和判断未知节点位于四面体内部还是外部，从而改进内点测试方法。

2.1 新内点测试方法

体积判断原理如图1 所示。设锚节点A，B，C，D组成的四面体ABCD 的体积为V，未知节点M 与4 个锚节点组成4 个小四面体ABCM，ABMD，AMCD，MBCD，体积记为V1，V2，V3，V4。若V1+ V2+ V3+V4=V，则可判断未知节点在四面体内部(见图1(a));若V1+V2+V3+V4＞V，则可判断未知节点在四面体外部(见图1(b))。

图1 体积判断原理Fig.1 Volume estimation principle

该方法改进了内点测试方法，相比原来的方法更简明适用。其关键是如何计算四面体的体积，分两种情况考虑:

1)对于锚节点而言，本身位置已知，可获得其坐标，设A，B，C，D 4 个坐标分别为(x1，y1，z1)，(x2，y2，z2)，(x3，y3，z3)，(x4，y4，z4)。由数学知识可以求出四面体ABCD 的体积为VABCD，其计算公式为

2)对于待定位节点和锚节点构成的四面体而言，由于待定位节点的坐标未知，所以不能用式(1)直接计算。体积计算的推导如图2 所示。

图2 体积计算的推导Fig.2 Derivation of the volume calculation

由图2 可知，利用RSSI 测距技术可以测出未知节点和任意3 个锚节点组成的四面体(不妨以四面体ABCM 为例)的六条棱长分别为l，m，n，p，q，r。为推导方便，以M 为坐标原点建立空间直角坐标系，由式可知:

将式(2)两边同时平方得

由矢量数量积的坐标表达式及数量积的定义得

根据余弦定理

x1x2+ y1y2+ z1z2= MA·MB =

将式(4)和式(5)代入式(3)，求出四面体的体积

同理，可以求出其他3 个四面体的体积，从而判断出待定位未知节点是否在四面体内。该方法改进了内点测试方法。

2.2 修正RSSI 测距误差

在VJ-APIT 算法中，要利用RSSI 测距技术计算未知节点到锚节点之间距离。RSSI 测距技术是利用接收信号强度对比发射信号强度算出信号在传播过程中的损耗值，根据理论或经验的传播模型将传播损耗转化为距离值。实际应用中，由于受到反射、天线增益、非视距、多径传播等各种环境因素的影响，测距误差较大。针对上述问题，文中提出了一种修正RSSI 测距误差的方法以提高测距精度。

无线传感器网络中，由于锚节点的位置已知，可由节点的坐标计算出任意两个锚节点的距离。这个距离是真实的距离，称为实际距离，记为d1。也可由RSSI 测距方法获得距离，这个距离称为测量距离，记为d2。比较测量距离和实际距离，将两者相减可得到RSSI 测距的误差值Δd，即Δd = d2－ d1，网络中所有锚节点平均测距误差如下:

其中，Δd 为平均RSSI 测距误差值;n 为锚节点总数;m 为锚节点通信半径内的锚节点数;dij为锚节点i 到锚节点j 的实际距离;d'ij为锚节点i 到锚节点j 的测量距离。

将平均RSSI 测距误差值修正到节点到其他节点的测量距离，具体表示为

其中，d'u为修正后的测量距离;du为修正前的测量距离。

修正方法降低了网络中任意两点的距离测量误差，提高了测量精度，可使节点的定位精度获得提高。

3 VJ-APIT 定位算法步骤

VJ-APIT 算法主要从改进内点测试方法和RSSI测距误差两个方面提高节点的定位精度，具体步骤如下:

1)网络部署完成后，锚节点广播自身信息，包括标识号ID、位置、信号强度等。锚节点和待定位节点均接收其通信范围内的邻居锚节点信息。若未知节点收到锚节点的个数n ≥4，则继续执行下一步，否则节点M 定位结束。

3)用三维网格扫描算法计算出四面体的重叠区域，即所有包含未知节点的四面体的交集，将权值最大的部分作为优选区域。

4)将重叠区域的质心位置坐标作为未知节点M 的估算位置，完成节点M 的定位。

4 仿真实验分析

为有效评估VJ-APIT 算法的性能，通过与原APIT-3D 算法对比分析，采用Matlab7.1 进行一系列模拟仿真。为了减少随机分布和降低实验的偶然性，最终仿真数据取20 次相同参数环境结果的平均值。

仿真实验采用随机部署模型，将所有的节点(锚节点和待定位节点)随机部署在1 000 m ×1 000 m ×1 000 m 的标准立方形监控区域内。节点总数为300，未知节点通信半径为200 m，锚节点与未知节点通信半径比为1.2，传输模型采用规则模型。

图3 为在其他条件不变的情况下改变锚节点比例的实验结果。

图3 锚节点比例对定位误差的影响Fig.3 Effect of the anchor node proportion on the positioning error

由图3 可以看出，两种定位算法定位误差都随着锚节点比例的增大而下降，并逐渐趋于平稳。锚节点比例较低时，两种算法定位误差均较大。当锚节点比例逐渐增大，相比于APIT-3D 定位算法，改进的VJ-APIT 算法定位精度提高很多。这是由于VJ-APIT 算法改进了内点测试方法，减少了两种误判发生的概率，从而提高了定位精度。从曲线的趋势来看，改进算法更适合大规模、连通度高的网络。

图4 为不同通信半径比对定位误差的影响。

由图4 可以看出，在通信半径d 在1 ～1.75 时，由于处于锚节点稀少地区的未知待定位节点容易出现两类误判，因此定位误差较高，改进算法相比原算法大幅提高了定位精度。随着通信半径比的增大，网络连通度增大，两者定位误差均呈下降趋势。从图4 中可以看出，改进算法定位精度相对于原算法定位性能更好。

锚节点比例对定位耗时的影响如图5 所示。

图4 不同通信半径比对定位误差的影响Fig.4 Effect of the communication radius ratio on the positioning error

图5 锚节点比例对定位耗时的影响Fig.5 Effect of the anchor node proportion on the locating time-consuming

由图5 可以看出，随着锚节点比例的增大，定位耗时也相应增加。这是由于锚节点数目增大能够构成的四面体数目增多，定位计算消耗的时间也随之变大，VJ-APIT 定位算法相比原算法增加少量通信耗时，但提高了显著定位精度，这是合理的代价。

5 结 语

文中从改进内点测试方法和RSSI 测距误差两个方面，提出了一种改进的APIT-3D 算法，即VJ-APIT 算法。该算法提出的修正RSSI 测距误差方法提高了测量精度，有效降低了节点间的测距误差，提高了节点定位精度，改进内点测试方法，减少了In-to-Out Error 和Out-to-In Error 两种误判的概率。算法虽增加了少量通信耗时，但实现了更准确的定位。改进算法更适合大规模、连通度高的网络。

［1］Akyildiz I F，Weilian S，Sankarasubramaniam Y，et al.A survey on sensor networks［J］.Communications Magazine，IEEE，2002，40(8):102-114.

［2］XU E Y，DING Z，Dasgupta S.Sourcelocalization in wireless sensor networks from signal time-of-arrival measurements［J］.IEEE Transations on Signal Processing，2011，59(6):2887-2897.

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

ZHOU Yong，XIA Shixiong，Ding Shifei，et al.An improved APIT node self-localization algorithm in WSN based on triangle-center scan［J］.Journal of Computer Research and Development，2009，46(4):566-574.(in Chinese)

［4］LI S，DING X，YANG T. Analysis of five typical localization algorithms for wireless sensor networks［J］. Wireless Sensor Network，2015，7(4):27-29.

［5］HE T，Huang C D，Blun B M，et al.Range-free localization schemes in large scale sensor networks［C］//Proc of the 9th Annual Int’l Conf on Mobile Computing and Networking.New York:ACM，2003:81-95.

［6］LIN Z G，LI L，ZHANG H Q，et al.An APIT algorithm based on DV-HOP multi-hop［J］.Advanced Materials Research，2013，787(2):1038-1043.

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

LIU Yuheng，PU Juhua，HE Yang，et al. Three-dimensional self-localization scheme for wireless sensor networks［J］. Journal of Beijing University of Aeronautics and Astronautics，2008，34(6):647-651.(in Chinese)

［8］相卫华，贾超，王华奎，等.无线传感器网络三维APIT 网格化算法［J］.传感技术学报，2012，25(5):639-643.

XIANG Weihua，JIA Chao，WANG Huakui，et al. Three-dimensional grid of APIT algorithm in wireless sensor network［J］.Chinese Journal of Sensors and Actuators，2012，25(5):639-643.(in Chinese)

［9］胡伟，朱西平，文红，等.基于四面体质心迭代的三维APIT 定位算法研究［J］.传感技术学报，2013，26(10):1432-1436.

HU Wei，ZHU Xiping，WEN Hong，et al. Three-dimensional APIT localization algorithm based on tetrahedron centroid iteration［J］.Chinese Journal of Sensors and Actuators，2013，26(10):1432-1436.(in Chinese)

［10］陈月娥，余敏.无线传感器网络中APIT-VP 三维定位算法［J］.传感器与微系统，2014，33(5):148-153.

CHEN Yuee，YU Min. APIT-VP 3D localization algorithm for WSNs［J］. Transducer and Microsystem Technologies，2014，33(5):148-153.(in Chinese)