WSN定位算法APIT的改进型设计*

(四川信息职业技术学院，广元 628040)

引　言

当前，通信系统位置信息的获取主要采用主动式和被动式两种方式，被动式因设备简单、定位精度高而广泛被使用，但又因安全性差，并且需要通过自身的GPS与卫星通信来获取定位信息，尤其是在矿井等复杂环境下很容易受到外界电磁环境的干扰，为此有必要设计一种可靠性和安全性都较高的定位系统。APIT定位算法是一种不需要测距的定位算法，具有容易实现、成本低、功耗小和定位精度高等特点，但APIT算法在节点分布密度较高和较低两种情况下，定位误差较大，为此有必要对APIT算法进行改进，使其能准确获取其位置信息。

1　APIT定位算法原理

(1)

当搜索完所有优选三角形后，通过网格扫描算法就可以得到所有优选三角形区域无限重叠的位置，该位置即为未知节点M的位置坐标，如图1所示。

图1　网格扫描算法图

很显然APIT算法是依靠方向矢量来进行未知节点的定位的，这种定位方法要求有较高的网络连通度，而较高的网络连通度需要有一个完备的矢量集合，该矢量集合需要同时具备以下两个条件：

① 未知节点与所有邻居节点的方向矢量在整个圆周上，如图2(a)所示。

② 方向矢量是通过判定在三角形内外来实现的，如图2(b)所示。

图2　完备矢量构建图

要想使APIT算法进行，必须满足以上两个条件。然而当节点分布较少或分布不均匀时，就会出现错判情况，直接导致节点无法定位。

当满足条件①但不满足条件②时，如图3(a)所示，在三个信标节点构成的三角形中，取节点1与未知节点构建方向矢量，则出现同时远离三个信标节点的情况，由APIT算法可知，出现了未知节点位于三角形外的错误结果。而当所有的方向矢量没有同时出现远离或接近三个信标节点，即不满足条件①时，如图3(b)所示，由APIT算法可知，也会出现错误的判断结果，这种结果主要出现在节点分布密度较低的情况，如图4(a)所示。而当节点分布密集时，如图4(b)所示，定位节点同时远离或接近信标节点的方向矢量容易获得，也出现了错判的结果。

图3　不满足构建完备矢量示图

图4　不同节点分布下误判发生情况

除了错判外，当信标节点不能将普通节点全部覆盖到时，就会造成无法定位的结果，可见如果APIT算法覆盖率不高，也会使传统的APIT算法无法实现定位。

2　改进的APIT定位算法

由传统APIT定位算法可知，在节点稀疏时，方向矢量较少，很难找到同时接近或远离由信标节点构成的三角形的邻居节点，导致外判内的错误，即Out-To-In Error；同时处在边缘环境中待定位节点很难构成相当数量的信标三角形或根本无法组建三角形，以上两种情况导致传统APIT算法判定失效。为此设计以下改进算法克服判定失效。

(1)稀疏环境下的改进方法

图5　稀疏环境下最短路径

为了提高稀疏环境下定位的准确度，通过信标节点间的两两通信，来获得到达对方的最短路径，该距离值记为ξ。未知节点通过跳段式的传播方式与信标节点通信，需要的最少跳数记为λ。如图5所示。

图5中，信标节点的坐标为A(x1,y1),B(x2,y2),C(x3,y3),则三边距离总和记为L，平均最短路径记为l：

(3)

未知节点到信标节点的距离为:

(5)

化简得：

(6)

令:

(7)

(2)节点密度大环境下的改进算法

(8)

若τ>0，则未知节点在三角形内；若τ<0，则未知节点在三角形外。

以上两种改进算法是针对节点分布不均匀采取的改进算法，为了降低算法复杂度，使其算法有自适应能力，引入节点密度σ作为判定标准，为节点密度设定门限值α和β，当节点密度在α和β之间时,视为均匀分布，该改进算法被屏蔽。

3　仿真分析

为了验证APIT改进算法的性能，在1000×1000二维平面区域内部署40个信标节点和80个未知节点，信标节点通信距离设为250，未知节点的通信距离设为80。不同密度下节点定位误差仿真图如图6所示。

图6　不同密度下节点定位误差

由图6可知，当节点密度小于13%或者大于25%时，在改进的APIT算法中门限α取13%，门限β取25%，我们按最低判决。在后面的仿真实验中，均按照此阈值进行对比分析。

3.1　不同通信半径θ值下定位误差比较

信标节点距离记为Rb，Ru是未知节点通信距离，定义Rb/Ru为通信半径比，记为θ，图7、图8和图9分别为θ=1、θ=2和θ=3的通信情况，θ越大，网络覆盖面积也越大。

图7　θ=1节点通信情况

图8　θ=2节点通信情况

图9　θ=3节点通信情况

仿真不同通信半径比θ定位误差如图10所示，改进的APIT算法定位误差相比于原算法都有明显的降低。

图10　不同θ值下定位误差比较

3.2　不同网络连通度下定位误差比较

连通度是影响APIT算法精度的主要因素，设未知定位节点的通信范围为Ru，图11、图12和图13是在信标节点通信距离一定，不同Ru情况下节点的通信情况。

图11　Ru=100节点通信情况

可见Ru越大，侦听到的信标节点就越多，网络的连通度也就越好。

不同网络连通度下两种定位算法仿真图如图14所示，很明显，改进算法定位误差较原算法有明显降低。

3.3　网络覆盖率比较

信标节点越少，传统APIT算法定位越困难，而改进APIT算法即使在信标节点极少的情况下仍可定位，图15是两种算法网络覆盖率的对比图，由图可见，改进后的APIT算法相比于原算法在不同的信标节点密度下，网络覆盖率有明显的提高。

图12　Ru=200节点通信情况

图13　Ru=300节点通信情况

图14　不同网络连通度下改进算法与原算法的误差比较

图15　两种算法网络覆盖率的对比

结　语

[1] 卢玉杰.基于调频广播的无源定位系统接收机设计[J].无线互联科技,2016(9).

[2] 方锋,郭徽东.基于到达时间和方位角的固定单站无源定位仿真分析[J].舰船电子对抗,2016(2).

[3] 高宪军,李洪斌,司博文.单站无源定位的一种改进的粒子滤波算法[J].电子设计工程,2016(5).

[4] 郭徽东.基线固定条件下无源定位配置仿真分析[J].雷达与对抗,2015(4).

[5] 张志远.基于北斗卫星导航系统的无源定位方法研究[J].山西科技,2015(5).

[6] 沈金良.机场场面无源多点定位系统研究[J].舰船电子对抗, 2015(1).

[7] 王正生,仇雅芳,王琳,等.卡尔曼滤波算法在单站无源定位中的应用[J].舰船电子对抗,2014(5).

[8] 莫成坤,陈树新,吴昊,等.基于角度信息的递推最小二乘无源定位算法[J].计算机测量与控制,2014(9).

殷万君(讲师)，主要研究方向为智能信号处理。