基于LS-PSO的北斗伪距单点定位算法

席志红,常佳博

(哈尔滨工程大学 信息与通信工程学院，哈尔滨　150001)



基于LS-PSO的北斗伪距单点定位算法

席志红,常佳博

(哈尔滨工程大学 信息与通信工程学院，哈尔滨150001)

北斗伪距单点定位具有易于实现、不存在整周模糊度、速度快等特点，具有很大的研究和应用价值;传统最小二乘法由于引入了线性误差、对初始值依赖性强而导致定位精度低;为了提高北斗伪距单点定位的精度，通过分析最小二乘法和粒子群算法的优缺点，提出了一种LS-PSO组合算法;首先利用最小二乘法定位计算接收机的大约位置，作为粒子群算法解的基准值并建立解的搜索空间，然后利用粒子群算法得到全局最优值，解算出精度更高的结果;经过实验验证，LS-PSO组合算法可以稳定的解算出m级精度的定位结果，并且三维方向偏差都在大约5 m以内;最后通过与遗传算法的收敛情况和最小二乘法的定位精度进行对比，证明LS-PSO组合算法可以快速的收敛到最优解并且有效的提高了北斗伪距单点定位精度。

北斗；伪距单点定位；最小二乘-粒子群；精度

0　引言

近年来，北斗卫星导航系统的发展越来越迅速，提高北斗的定位精度一直是研究的热点。伪距单点定位不涉及到模糊度的求解，而且只要观测卫星数目足够可以快速地定位出大约的位置，在北斗完成组网后，北斗伪距观测质量优于 GPS，特别是北斗GEO 卫星伪距观测量受多路径、硬件延迟及随机噪声的影响比北斗其他卫星及GPS卫星都要小很多[1]。但是其之前受限于观测卫星较少而稍微劣势于GPS。因此如何提高北斗系统伪距单点定位精度，也是时下研究的热点方向。鉴于传统的最小二乘法虽然可以快速解算出位置，但是结果不可靠，偏差较大，而且在解算过程中进行了线性化处理，引入了线性误差。所以基于伪距观测的非线性方程，对其进行直接解算寻找最优值，也是提高伪距单点定位的方法之一。文献[2]提出了一种基于遗传算法的GPS单历元解算方法，该方法虽然有效的提高了定位精度，但是遗传算法的收敛速度太慢，很耗解算时间；文献[3]同样采用了遗传算法进行了GPS的动态单点定位，但是同样存在收敛速度慢的问题。文献[4]提出了一种快速的最小二乘算法，利用差值法和牛顿法相结合进行解算，加速了解算的速度和可靠性，但是由于其还是进行了线性化处理，所以同样不可避免地引入了线性误差。

1　北斗系统简介

北斗导航系统是中国自行研制的全球卫星导航系统。北斗导航系统目前在轨正常工作的卫星有5颗GEO卫星、5颗IGSO卫星和4颗MEO卫星。北斗导航系统在2012年已具备覆盖亚太地区的定位、导航和授时以及短报文通信服务能力。预计在2020年左右，建成覆盖全球的北斗卫星导航系统。

北斗系统的时间基准为北斗时(BDT)，起始历元为协调世界时(UTC) 2006 年 1 月 1 日00 时 00 分 00 秒，单位为国际单位制(SI)秒[5]。GPST可以在200纳秒的偏差内粗略的通过公式(1)来转换为BDT：

tBDT=tGPST-14

(1)

北斗系统采用的坐标系统为2000中国大地坐标系(CGCS2000)。

2　北斗伪距单点定位数学模型

北斗系统t时刻的码伪距观测模型[6]为：

(2)

+δion+δtrop+δtide+δrel-cδs(t)

(3)

式中,Xs(t)、Ys(t)、Zs(t)为t时刻卫星在地心坐标系下位置矢量的三分量，Xr、Yr、Zr为接收机在地心地固坐标系(ECEF)下位置矢量的3个分量。卫星的钟差参数已知，可以通过卫星广播导航电文得到。钟差参数包括toc，a0，a1和a2。toc为本时段钟差参数参考时间，单位为秒，其它3个参数为二进制补码，则t时刻的卫星钟差可由式4得到 ：

δs(t)=a0+a1(t-toc)+a2(t-toc)2+δrel

(4)

其中：δrel为相对论校正项，单位为s，其值为：

(5)

信号发射时刻的北斗时可由

t=tsv-δs(t)

(6)

得到，t为信号发射时刻的北斗时，单位为秒，tsv为信号发射时刻的卫星测距码相位时间，单位为秒，式中，t可忽略精度，用tsv替代。对于北斗系统，需要通过星上设备时延差TGD1、TGD2进行修正，对于B1I信号，通过 TGD1修正，对于B2I信号，通过TGD2修正[7]。

(δs(t))B1I=δs(t)-TGD1

(7)

(δs(t))B2I=δs(t)-TGD2

(8)

则钟差之差：

(9)

式中卫星钟差δs(t)已知，接收机钟差δr(t)未知。将式(9)代入式(2)中并整理得：

(10)

L=F(X)+V,P

(11)

其中:L为观测向量；X为未知数向量，F(X)是X对应的非线性函数，V为残差向量，P为观测向量的权矩阵。因此根据公式(11)可以对未知数向量X进行最小二乘估计。

则解观测方程由最小二乘准则可的目标函数为：

H(x)=minVTPV

(12)

观测方程解算未知数的有解的充分非必要条件是，观测值的格式大于或者等于未知数的个数。观测值的个数可以表示为ns·nt，其中ns为卫星的个数，nt为观测的历元数。方程的未知量为观测站的三维坐标和每个历元的钟差，因此，观测方程有解的基本条件[8]可以表示为：

ns·nt≥3+nt

(13)

由式(13)可知方程有解需要的最少观测卫星数为2时，最少观测历元数为3；当观测的卫星数为时，可以得到最少观测历元数为1。所以可知，只要有4颗以上的观测卫星，就可以求出任意历元的4个未知量。

3　基于LS-PSO的北斗伪距单点定位的求解与实现

3.1LS算法定位解算

最小二乘算法(LS)作为卫星导航常用的定位算法，已经广泛的用于伪距单点定位的基本运算当中，根据式(11)，将非线性函数F(X)在待求点(X0,Y0,Z0)展开为泰勒级数[9]，并且忽略二阶及以上高阶项，得：

(14)

即：

(15)

将式(16)代入式(10)，可得：

(16)

其中：vs为卫星s的残差向量。

令

则公式(16)可以表示为：

(17)

将所有卫星的系数放在一起构成系数矩阵A，则可以得到北斗伪距单点定位的线性系统方程：

L=A·dX+V,P

(18)

其中:L为观测向量，dX为未知数向量，V为残差向量，P为观测向量的权矩阵。因此根据公式(19)可以对未知数向量dX进行最小二乘估计。

根据加权最小二乘法的原理，式(19)的最小二乘解为：

dX=(ATPA)-1ATPL

(19)

求出dX然后更新(X0,Y0,Z0)，使：

(X0,Y0,Z0)=(X0+dXr,Y0+dYr,Z0+dZr)

(20)

利用牛顿迭代法，不断迭代更新(X0,Y0,Z0)的值，直到达到预设精度阈值，即可得到接收机的位置。

3.2PSO算法的基本原理

粒子群算法(particle swarm optimization，PSO算法)是一种基于群智能的优化算法，是对鸟儿觅食的社会行为的模拟。它从一组随机解出发，通过迭代寻找最优解。由于原始PSO算法有容易陷入局部最优解，收敛精度差等缺点，因此研究者们对PSO算法进行了多种改进措施，Shi等人提出了惯性权重线性下降PSO算法(LDW-PSO)，该算法可以提高算法的收敛性能，平衡收敛的全局性和收敛速度，在多峰函数中效果明显；Clerk提出了带收缩因子的PSO算法(CFM)，该算法在保证收敛性的同时使速度的限制放松，毕晓君教授在《信息智能处理技术》一书中，提出了基于种群分类与动态学习因子的粒子群改进算法，改算法采用动态调整学习因子的方法平衡进化不同阶段粒子的全局和局部搜索能力，提高了算法的性能[10]。

基于北斗伪距定位的数学模型是单峰多维的函数，本文采用引入收缩因子的PSO算法(CFM-PSO)进行北斗伪距单点定位，设置收缩因子k：

(21)

假设代优化问题的解释N维的，由M个粒子组成一个群体，任何一个可能的解(一个粒子)都可以看成是一个N维向量Xi={xi1,xi2,···,xiN},i=1,2,3,···,M。同时粒子i还具有一个与Xi(t)同维数的，随着迭代次数t增加而不断变化的速度向量Vi(t)。将Xi带入目标函数就可以求出第i个粒子的适应值，根据适应值的大小衡量值的优劣。

PSO算法的基本流程为[11]：

1)初始化种群规模M，设定初始值Xi(0)，初始速度Vi(0)(i=1,2,3,···,M)，初始第i个粒子的最好位置Pi(0)和整个群体记忆的最好位置Gi(0)；

2)设迭代次数为t，令t=1开始迭代；

3)利用式(22)和式(23)，计算每个粒子的Xi(t)，Vi(t)。

(22)

Xi(t)=Xi(t-1)+Vi(t)

(23)

其中:rand()是[0,1]之间的随机数，C1和C2是学习因子。

4)计算每个粒子的适应值，将每个粒子的适应值和其经历过的最好位置Pi(t-1)作比较，若较好，则作为当前的最优值。

Pi(t)=argmin{f(Pi(t)),f(Xi(t))}

(24)

5)将每个粒子经历的最好位置Pi(t)的适应值进行比较，得到全局最优值G(t)。

G(t)=argmin{f(P1(t)),···,f(Pi(t)),···,f(PM(t))}

(25)

6)判断是否满足终止条件(一般为迭代的最大次数)，若满足，则G(t)为最优解。

3.3基于LS-PSO组合算法的解算算法描述

LS算法的特点和不足是：

1)进行定位解算虽然速度很快，但是精度上往往很低；

2)受初始值影响较大，而且在观测值质量不是很好或者卫星数不是很多的情况下，精度更会大大地降低；

3)线性化的过程存有线性误差，影响定位精度。

PSO算法的特点和不足是：

1)不受初值的影响，收敛快，稳定高，收敛精度高的特点；

2)容易陷入局部最优，但是采用CFM以后可以有效改善；

3)在定位的开始，无法确定接收机的大体位置，所以要搜索的解空间是巨大的。

因此为了提高北斗伪距单点定位的精度，并且减小PSO的搜索范围，本文将两者结合，首先用LS算法定位得到接收机的大约位置作为PSO算法解的基准值，建立解的搜索空间，再利用PSO算法得到全局最优值，解算出精度更高的结果。

由式(3)和式(12)可以得：

(26)

H(x)作为PSO算法的适应度函数，向量X=(Xr,Yr,Zr，δr(t))组成该方程的解空间。初始化种群M，学习因子C1、C2，最大迭代次数tmax，最大速度Vmax。采用LS算法得到的定位结果Xtemp=(Xt,Yt,Zt.δt(t))作为的基准值，随机产生Xi(0)、Vi(0)，初始化Pi(0)，G(0)。对每次迭代，每个粒子，根据4.1所述流程计算，最终输出全局最优值G(t)。算法流程如图1所示。

4　实验结果及分析

实验程序是基于开源代码RTKLIB函数库进行开发，开发环境为C#，数据取哈工程某实验楼观测点2015年1月6日的30个连续历元的观测数据进行单历元解算。为了验证算法的可靠性，以下数据均在观测卫星数稳定为4的情况下进行定位。

4.1PSO算法收敛性能分析

为了验证PSO算法的收敛性能，取

M=50,φ=4,C1=C2=2.05,tmax=100

Xmax=Xtemp+30,Vmax=1.5*Xmax

其中：Xmax为解空间范围最大值，则由式(14)可求得k=0.729，选取其中一个历元进行定位解算，观察适应度函数值的收敛情况，如图2所示。

图1　LS-PSO算法流程图

图2　适应度函数收敛性能图

由图2可见，迭代次数在10左右时，适应度函数值开始大范围收敛，到28次左右时，小幅度逼近最优值，参考文献[3]中应用遗传算法解算GPS单历元单点定位时，要在进化代数大于70左右才能小幅度逼近最优值，由于GPS和北斗在单历元伪距单点定位解算时的适应度函数是相同的，因此可以看出在收敛速度上，LS-PSO算法是远远快于遗传算法的。

4.2定位精度分析

PSO算法进行定位解算是对非线性方程组的求解，因此不能用LS算法的精度标准来规划衡量LS-PSO算法的定位精度。LS算法得到的定位解释唯一解，而LS-PSO算法得到的是全局最优解，为了对比LS算法和LS-PSO算法的精度，本文采用与三维坐标与真值的差值和三维坐标与真值的几何距离来对比两种算法的精度，采用单历元重复多次定位的方法来验证算法的稳定度。

任取一个历元重复定位100次，取

M=50,φ=4,C1=C2=2.05,tmax=100

Xmax=Xtemp+30,Vmax=1.5*Xmax

其中：Xmax为解空间范围最大值。随机记录其中10次定位结果的三维坐标与真值的差值dx、dy、dz和三维坐标与真值的几何距离dr，并且记录同一历元最小二乘法相应数据作为对比。记录数据如表1所示，图2显示了100次定位的dx、dy、dz、dr的分布情况。

表1　LS-PSO算法和LS算法定位对比

图3　100次定位的dx、dy、dz、dr分布情况

由表1可知，LS-PSO算法的三维向量偏差和与真值的几何距离差均优于LS算法；由图2可知，LS-PSO算法所得到的解算结果稳定，并且X方向与真实值偏差在5 m以内，大多数优于4 m，Y方向偏差在4 m以内，多数优于3 m，Z方向偏差在6 m以内多数优于5 m。与真值的空间几何距离偏差在6 m以内达到m级定位精度。并且数据波动很小，表示定位结果很稳定。在多数情况下，X方向和Y方向的偏差甚至可以达到厘米级。因此采用LS-PSO组合的算法可以良好的提高北斗伪距单点定位的精度，并且算法是稳定可靠地。

5　结论

本文通过对比LS算法和PSO算法的优缺点，综合两者各自的优势，提出LS-PSO组合的算法，通过LS算法确定解空间范围，PSO算法搜索得到全局最优解。通过100历元的单历元独立重复试验，证明该算法的稳定性，且精确度相对于传统LS算法有所提高。本文算法易于实现，不足是迭代计算耗费了大量的时间，因此是在牺牲了部分解算速度情况下提高了定位的精度。在连续历元解算的过程中，可以利用前一历元得到的定位结果作为本历元的初值，减小搜索范围，不但降低了搜索的复杂度，而且可以设定精度阈值，提前终止迭代，加快连续单历元解算的速度，这是下一步的研究工作，对于简单快速提高北斗伪距单点定位精度的有很大的意义。

[1] 严丽，黄丁发，冯威，等.COMPASS与GPS伪距单点定位性能比较研究[A].第三届中国卫星导航学术年会电子文集——S06北斗/GNSS测试评估技术[C].2012.

[2] 刘智敏,刘经南,刘晖. 基于遗传算法的GPS单历元单点定位方法研究[J]. 武汉大学学报· 信息科学版,2007,32(1).

[3] 徐爱功,徐涛,张明月,等. GPS 动态单点定位的遗传算法探究[J]. 测绘科学,2009(S2)：18-20.

[4] 李春华,蔡成林,邓克群,等. 一种北斗伪距单点定位的加权最小二乘 (WLS) 快速算法[J]. 重庆邮电大学学报 (自然科学版),2014,4: 008.

[5] 丰勇. COMPASS 系统的伪距单点定位算法研究[J]. 测绘与空间地理信息,2015 (7).

[6] Xu G C. GPS 理论,算法与应用[M]. 北京：清华大学出版社,2011.

[7] 北斗卫星导航系统空间信号接口控制文件公开服务信号(2.0版)[Z].中国卫星导航系统管理办公室,2013.

[8] Wellenhof H B,Lichtenegger H,Wasle E. 全球卫星导航系统 GPS,GLONASS,Galileo 及其他系统[J]. 导航定位学极，2010(2):83.

[9] 许承东. GNSS数学仿真原理及系统实现[M]. 北京：中国宇航出版社，2014.

[10] 毕晓君.信息智能处理技术[M]. 北京：电子工业出版社,2010.

[11]张建科,王晓智,刘三阳,等. 求解非线性方程及方程组的粒子群算法[J]. 计算机工程与应用,2006,42(7): 56-58.

Compass Pseudorange Single-point Positioning Algorithm Based on LS-PSO

Xi Zhihong，Chang Jiabo

(College of Information and Communication Engineering,Harbin Engineering University,Harbin150001,China)

Compass pseudorange single-point has characteristics of easy to implement,without ambiguity problem,postioning fast . It has great value for research and application. Traditional least squares algorithm has linear error and strong dependence on initial values so that its accuracy of positioning is very low. In order to improve the accuracy of Compass pseudorange single-point positioning,proposed a combination algorithm of LS-PSO by analyzing the advantages and disadvantages of least squares algorithm(LS) and particle swarm optimization(PSO).Firstly it obtains the approximate location of receiver for the base value of PSO by LS and establishes the search space of the solution. Then it calculates the global optimum by PSO so that the result has higher accuracy. Through the verification of experiments,LS-PSO can calculate m-level precision positioning results stably and the three-dimensional errors are all within 5 meters. Finally by compared with the positioning accuracy of LS and the convergence of genetic algorithm,it proves that LS-PSO can converge to the optimal solution quickly and improve the accuracy of Compass pseudorange single-point positioning effectively.

compass; pseudorange single-point positioning; LS-PSO; accuracy

1671-4598(2016)04-0167-04DOI：10.16526/j.cnki.11-4762/tp.2016.04.049

P228.4

A

2015-10-12；

2015-11-06。

席志红(1965-)，女，陕西省西安人，教授，硕士研究生导师，主要从事北斗定位算法和图像处理方向的研究。