基于TDOA的基站布局对定位精度影响分析*

周恭谦, 杨露菁, 刘 忠, 彭业飞

(海军工程大学电子工程学院, 湖北 武汉 430033)

基于TDOA的基站布局对定位精度影响分析*

周恭谦, 杨露菁, 刘 忠, 彭业飞

(海军工程大学电子工程学院, 湖北 武汉 430033)

对基于TDOA的定位方程进行分析,通过对其进行微分运算,求解出定位误差关于基站目标方位角的非线性函数,分析函数找出了影响定位精度的具体要素。此外针对非线性函数求解困难的问题提出一种混沌双扰动粒子群算法(CDDPO)对该函数求解,当待测目标位置发生变化时该算法能够迅速找出满足定位误差最小的基站布局,总结归纳了使误差最小时的定位基站布局的特点。最后通过实例验证了结论的正确性。

基站布局;定位精度;混沌双扰动粒子群算法;时差定位;微分运算

TDOA即到达时间差,是指无线射频信号同一时刻到达两个基站的时间差。TDOA技术是一种无线定位技术,是根据无线射频信号到达两个基站之间的距离差来定位的一种技术[1]。基于TDOA的定位方法主要是通过测量经待测目标发射信号到达不同基站的到达时间差来实现的,该方法不要求待测目标和基站之间的时间同步,但是要求各个基站之间必须同步,保证同一时刻下信号源到达各个基站之间的时间差是个定值,时间差与光速的乘积就是距离差。根据求解双曲线的算法可知,为了确定待测的位置,至少需要两条相交的双曲线才可以确定,双曲线的交点处就是信号源的位置估计值。因此,要确定待测目标的位置则至少需要用三个基站[2]。相比传统的定位方法，TDOA有以下优点[3]:1)TDOA 不存在相位模糊的问题,因此测向基线可以不受限制；2)TDOA 系统复杂度低；3)TDOA 系统定位的精度较高。因此，基于TDOA的时差定位技术在目标定位方面得到了广泛的应用,本文对TDOA定位方程进行研究,分析影响定位精度的要素,并通过寻优求解找出了满足待测目标误差最小时对应的基站最优布局。

1 基站布局对定位精度影响分析

以三站为例，基于TDOA对待测目标(x,y)的定位方程为:

(1)

其中：(x1,y1)为中心基站,(x2,y2),(x3,y3)为副站的位置,R1,2,R1,3分别为中心基站和两个副站之间的距离差。

对方程(1)进行微分有:

(2)

图1 定位基站与待测目标连线角度关系示意图

(3)

上式可简化为dR=TdZ。

解上式可得dZ=T-1dR，即

(4)

(5)

求解式(5)可得

(6)

则定位误差E可表示为

(7)

又由图1可知β1=α2-α1,β2=α1-α3则(式7)可表达为

(8)

由图1可知

由式(8)可知：当测距误差一定的情况下,影响定位精度的因素是定位基站和目标所成的方位角,当出现α1=α2=α3中任意一种情况时目标的位置不可测,即定位基站的布设不应出现位置重合或接近,同时避免目标出现在任意两站的连线的延长线上。由式(8)可知：当β1=π,β2=π,β1+β2=π同时满足时误差最小,显然这是不可能的,这三者之间是一种互相影响互相约束的关系,所以待测目标与两个基站之间夹角对定位误差的影响不能单独进行研究判断。而对于式(8)的求解是个非线性最优化问题,粒子群算法被广泛应用于这方面,但该算法初期收敛很快,后期易陷入局部最优点。针对其存在的缺陷性,混沌粒子群算法被提出并广泛应用,其将粒子群算法在全局搜索上的快速性和混沌算法在一定范围内的遍历性相结合,提高了搜索的精度。下文提出一种双扰动的混沌粒子群算法,通过仿真与混沌算法对比证明了该方法能够有效地提高收敛速度,提高寻优能力,并使用该方法求解待测目标定位误差的最小值时各基站布设位置的坐标值。

2 基于混沌双扰动粒子群算法的优化基站布局

2.1 基于Logistic映射的混沌粒子群算法

利用混沌的遍历性和随机性[4]在智能算法进行优化搜索已发展成为一种高效的全局优化技术,促使了混沌广泛应用于各个学科领域。

混沌引入到粒子群算法的方法有多种,文献[5-6]利用混沌改善速度更新式子,这些方法基本上是利用了混沌技术的遍历性,使速度更新时具有遍历性效果。这种算法是为了提高算法的搜索能力。主要有以下两种速度更新公式:

Vid(k+1)=wVid(k)+c1χ(Pid(k)-Xid(k))+

c2(1-χ)(Pgd(k)-Xid(k))

(9)

Vid(k+1)=wVid(k)+c1χ1(Pid(k)-Xid(k))+

c2χ2(Pgd(k)-Xid(k))

(10)

其中，参数ω表示惯性权重因子,c1和c2为加速常数,也称为学习因子(通常取c1=c2=2),r1和r2为两个介于(0,1)范围内变化的相互独立的随机函数。为避免粒子盲目搜索,一般将其速度和位置限制在一定空间[Vmin,Vmax]、[Xmin,Xmax]内。式(9)、(10)中的χ序列由式(11)产生,即利用Logistic方程产生的混沌序列代替随机数rand。

χk+1=μχk(1-χk)

(11)

目前,大多数学者采用基于Logistic映射。文献[7]提出了基于Logistic映射的混沌粒子群算法:第一阶段称为粗搜索阶段,先采用基于Logistic迭代映射遍历整个解集空间,当达到所求问题的相应条件(迭代次数限制)时, 即把当前解默认为接近问题的最优解;第二阶段称为细搜索阶段,以第一阶段的结果为中心附加混沌扰动,进行精确细致搜索,直至满足算法终止准则。

2.2 基于Tent映射的混沌双扰动粒子群算法(CDDTPSO)

虽然本文提出的基于Logistic映射的混沌粒子群算法改进能在一定程度上提高算法的搜索精度,但是由于Logistic映射混沌的序列主要集中分布在两端,中间区域所获分配不多,如果最优解落在中间部分,则算法便会偏离最优解的范围以致无法得到全局最优解。相对Logistic映射而言,Tent映射序列分布具有全局遍历性,且较为均匀,对初值不敏感等优点。

基于Logistic映射存在的上述缺点,本文在基于Tent映射[7]基础上加入双扰动的思想,提出混沌双扰动粒子群算法(chaotic double disturbance Particle Swarm Optimization,CDDPSO)。Tent映射也称帐篷映射,其表达式为

(12)

基于混沌双扰动的粒子群算法主要步骤为:

步骤1 混沌初始化。设定变量的取值范围[xmin,j,xmax,j],群体规模m,变量维度D。利用Tent映射(μ=0.5)生成i个混沌序列zij(i=1,2,…m,j=1,2,…D),将混沌序列zij通过式(4)线性映射到优化变量:

xij=xmin,j+(xmax,j-xmin,j)·zij

(13)

xij即为m个初始粒子种群。

步骤2 计算种群适应度。将粒子的目前位置记为Pbest,群体中适应度最优的粒子位置记为Gbest。

步骤3 利用粒子群速度公式更新粒子速度和位置,重新计算新粒子的适应度,并判断是否更新粒子的个体极值以及群体的全局极值。

步骤4 公告板记录。记录每次迭代产生的群体极值,称为公告板。并设定一个阈值T,如果公告板连续T次迭代没有更新,则转步骤5;否则转步骤6。

步骤5 混沌一次扰动。当前群体极值的混沌扰动公式为[8]:

(14)

(15)

步骤6 判断是否满足迭代结束条件(达到最大迭代次数),若满足,输出结果,终止算法;否则,转步骤7。

步骤7 早熟收敛判决。判决公式为:

(16)

步骤8 混沌二次扰动。利用式(17)和式(18)对早熟的粒子进行混沌扰动,

(17)

X*=ψ*(xmax,j-xmin,j)+xmin,j

(18)

2.3 算法测试

由图2和图3可以看出,相对于现有的混沌粒子群算法,本文采用的CDDPSO算法在经过若干代运算之后仍保持较高的活性,可以从局部最优中跳离出来,保持较快的收敛速度,极大地提高了对最优值的全局搜索能力。

图2 Griewank函数寻优曲线

2.4 基于改进的混沌粒子群算法优化的基站定位布局

图3 Rastrigrin函数寻优曲线

以中心基站为坐标原点,两个副站在以中心基站为圆心,半径为10km的圆上,测距误差定义为7m,将坐标系中随机生成坐标点作为待测目标的位置节点,使用改进的混沌粒子群算法对式(7)进行求解,并寻找达到最小误差时各基站的坐标,改进混沌粒子群算法具体参数参考上文2.3节设置。随机生成的点及此时最优定位基站布局如图4-图13所示,具体实验数据参考表1,其中(X1,Y1)表示中心基站坐标,本文使其固定在原点,(X2,Y2)(X3,Y3)分别两副站坐标,(XX,YY)表示待测目标坐标,夹角表示两副站和中心基站所围成的角度,δ2表示定位误差的平方值,斜率积代表中心基站和待测目标连线的斜率和两副站两线斜率的乘积。从表1可以看出，随着待测目标的位置不同基站的最优布局是不同的,随着距离的增加最优布局的基站夹角逐渐增大,且定位误差也逐渐增大。但可以看出，最优布局的基站拓扑结构始终保持着中心基站和待测目标的连线和两副站连线是垂直的。由此可知,在固定的区域内,对待测目标定位精度最高的定位基站布局要满足是等腰三角形结构且待测目标和中心基站的连线和两副站连线垂直。

表1 最小误差时基站最优布局结构数据表

图4 随机点的最优基站布局示意图

图5 随机点的最优基站布局示意图

图6 随机点的最优基站布局示意图

图7 随机点的最优基站布局示意图

图8 随机点的最优基站布局示意图

图9 随机点的最优基站布局示意图

图10 随机点的最优基站布局示意图

图11 随机点的最优基站布局示意图

图12 随机点的最优基站布局示意图

图13 随机点的最优基站布局示意图

3 实例验证

上节提出的当待测目标位置确定时,定位基站保持等腰三角形且中心基站和待测目标连线和两副站之间连线垂直是使误差达到最小的条件。本节基于实例对结论进行验证,对比在等腰三角形(中心基站待测目标连线和两副站连线垂直)和偏三角形(中心基站待测目标连线和两副站连线不垂直)情况下定位误差,验证上文提出结论的正确性。在某实际实验环境中按照一定的拓扑结构布设三个定位基站,本实验以观测区圆心为原点,定位基站分别按照(-50m,0)、(50m,0)、(0,-50m)等腰三角结构和(-50m,0)、(50m,0)、(-29.678m,-40.121m)偏三角结构进行布设,并在距离观测区圆心不同距离(0～1000m范围内)位置设置多个测试点(如图14“☆”所示),本实验中取距观测区0m、50m、100m、200m、400m的测试点进行静态试验测量出测试点的真实局部坐标。

1)定位基站成等腰三角结构布设

图14 定位基站成等腰三角布设拓扑态势图

去掉由于定位基站信号通信问题造成测得偏差较大的野值,此时试验测得的不同距离情况下坐标散布图如图15-18所示。

图15 等腰三角布设距离为0m时坐标散布图

图16 等腰三角布设距离为100m时坐标散布图

图17 等腰三角布设距离为200m时坐标散布图

图18 等腰三角布设距离为400m时坐标散布图

试验结果如表2所示。

表2 等腰三角结构布设时不同距离下定位结果分析

2)定位基站成偏三角结构布设如图19所示。

图19 定位基站成偏三角布设拓扑态势图

试验测得不同距离情况下坐标散布图如图20-22所示。

图20 偏三角布设距离为100m时坐标散布图

图21 偏三角布设距离为200m时坐标散布图

图22 偏三角布设距离为400m时坐标散布图

试验结果如表2所示。

表3 偏三角形结构布设时不同距离下定位结果分析

将定位基站按等腰三角形拓扑结构布设的定位结果与偏三角形拓扑结构作对比,如表4所示。

表4 不同拓扑结构布设时定位误差对比

通过上述实验可知,在待测目标位置一定的情况下中心基站和待测目标连线与两副站连线的等腰三角形定位误差比中心基站和待测目标连线与两副站连线不垂直的偏三角形定位误差小,且随着待测目标和定位基站距离增加定位误差增大,证明了上文结论的正确性。

4 结束语

本文对基于TDOA的基站最优布局进行分析,对TDOA方程进行微分运算,得出了关于定位误差与基站和待测目标连线水平角的非线性函数,并采用一种改进的混沌粒子群算法对该函数寻优,找出了满足最小定位误差时最优基站布局中各基站的坐标,总结归纳了最优布局时定位基站拓扑结构的特点,最后通过实例仿真验证了结论的正确性。

[1] 孙胜,李辉.基于TDOA定位技术的仿真研究[J].无线通信技术, 2002,11(4)：40-43.

[2] 马灵芝.基于TDOA无线传感定位算法的研究及应用[D].济南：山东大学,2012.

[3] 俞一鸣,姚远.程学虎.TDOA 定位技术和实际应用简介[J].中国无线电，2013(11):57-58

[4] Zhang L,Zhang F,Wu Q,et al.Simulatable certificate-less two-party authenticated key agreement protocol[J].Information Sciences,2010,180(2):1020-1030.

[5] MacQueen J. B. Some Methods for classification and Analysis of Multivariate Observations[C]. Proceedings of 5-th Berkeley Symposium on Mathematical Statistics and Probability, Berkeley, University of California Press, 1967:281-297.

[6] Blake-Wilson S,Johnson D,Menezes A. Key agreement protocols and their security analysis[C]∥Darnell M.LNCS 1355:Proc of the 6th IMA International Conference on Cryptography and Coding.Berlin/Heidelberg:Springer-Verlag,1997:30-45.

[7] Hong li Xu,Xu Qian, liang Zhang. Study of ACO Algorithm Optimization Algorithm Based on Improved Tent Chaotic Mapping Journal of Information &Computational Science.2012(6):1653-1660.

Analysis of the Influence of Base Station Layout on Location Accuracy Based on TDOA

ZHOU Gong-qian, YANG Lu-jing, LIU Zhong, PENG Ye-fei

(School of Electronic Engineering, Naval University of Engineering, Wuhan 430000,China)

Positioning equation based on TDOA is analyzed, the nonlinear function of position error on target azimuth of station is solved by the differential operation of the equation, the specific factor which affects the positioning accuracy is found out by analysis of function. In addition, an chaotic double disturbance particle swarm optimization algorithm is put forward to solve the function for the problem that nonlinear function is difficult to solve, the algorithm can quickly find the base station layout which satisfies the minimum position error when the target position is changed, and the features are summarized which meet the minimum positioning error of the base station layout. Finally the conclusion is verified by an example.

base station layout; positioning accuracy; chaotic double disturbance particle swarm optimization algorithm (CDDPSO); TDOA; differential operation

1673-3819(2017)06-0119-08

TN966；E917

A

10.3969/j.issn.1673-3819.2017.06.025

2017-03-20

2017-04-07

国家863计划项目(2013AA7014061)；总装预研基金(9140A01060113JB11001)

周恭谦(1988-),男,博士研究生,研究方向为模式识别、智能系统。杨露菁(1966-),女,博士生导师。刘 忠(1963-),男,博士生导师。