李东新，彭 云，常 青，李 晶，于 渊

(1.北京航空航天大学 电子信息工程学院，北京100191；2.北京航天长征飞行器研究所，北京100076；3.交通信息通信技术研究发展中心，北京100011)



基于粒子群算法的伪卫星布站优化设计

李东新1，3，彭 云2，常 青1，李 晶3，于 渊3

(1.北京航空航天大学 电子信息工程学院，北京100191；2.北京航天长征飞行器研究所，北京100076；3.交通信息通信技术研究发展中心，北京100011)

针对伪卫星布站问题，采用粒子群智能优化算法，以导航定位中精度因子作为粒子群适应度函数，采用线性递减惯性权值策略，通过适当次数的进化与迭代，最终寻找到最优化的伪卫星布站设计方案。通过对两条竖直平面内的抛物线轨迹进行仿真验证，结果表明，基于粒子群算法的伪卫星布站优化设计方案可以减小全程精度因子，提高了伪卫星独立定位系统的定位精度。

粒子群算法；线性递减惯性权值策略；伪卫星布站

0 引言

卫星导航定位的基本作用是向各类用户和运动平台实时提供准确、连续、可靠的位置、速度和时间信息。当前各种全球导航卫星系统，其系统的精度、可靠性和可用性都在一定程度上依赖于可跟踪卫星的数量以及几何分布情况。由于受到以上因素的制约，在峡谷、室内以及地下等比较苛刻的观测环境下，可视卫星的数量和几何布局就不能满足定位的需求。同时，由于用户与导航卫星之间的距离一般都比较远，信号衰减较大，导航信号到达地面时都比较弱，在复杂电磁环境下，极易受到干扰而无法使用。位于地面的伪卫星系统就能够更好解决这个问题。国内外学者在这一领域进行了深入的研究，相关的研究成果已经初步应用于露天矿边坡变形监测、坝体变形监测以及建筑物变形监测等领域，并产生了良好的效益[1-4]。

伪卫星不仅可以辅助GNSS导航定位，而且因为其自身功能和原理与导航卫星类似，且具有设置灵活机动，抗干扰性能好等优点，所以在特定环境，可以完全替代导航卫星，进行独立定位。伪卫星系统中，伪卫星的几何分布情况对用户导航定位精度具有重要影响，伪卫星布站技术是伪卫星系统设计的关键技术之一，在伪距测量误差一定的情况下，伪卫星良好的几何位置分布可以大大减小导航定位误差，提高定位精度。

粒子群优化算法(Particle Swarm Optimization，PSO)是Kennedy和Eberhart[5]于1995年提出的一种全局优化进化算法，其思想来源于对鸟群捕食行为的研究，同遗传算法和蚁群算法相比，PSO有着算法简单、容易实现，并且可调整参数少等特点，因此被广泛应用于结构设计[6]、电磁场[7]和任务调度[8]等工程优化问题中。

在本文中，我们采用粒子群优化算法对伪卫星独立定位系统中伪卫星的几何位置进行优化，并用两条竖直平面内的抛物线轨迹进行导航定位几何精度因子仿真试验，仿真结果表明，采用基于改进的粒子群布站优化算法能够大大减小导航定位精度因子，提高了定位精度。

1 伪卫星定位原理

伪卫星定位原理同卫星导航原理类似，利用到达时间测距原理来确定用户的位置。伪卫星定位原理如图1所示。

图1 伪卫星定位原理图Fig.1 Principle of pseudo-satellite positioning

接收机测量伪卫星发射信号与接收机接收到信号之间的时间差Δt，乘以光速c便可求得距离ρ(ρ=cgΔt)。由于伪卫星系统时钟和接收机时钟并不完全同步，存在时钟偏移误差，设这个误差为δtu。一般伪卫星布设在地面或对流层以内，电磁波必然要通过对流层，由于对流层引起测量误差设为T，则用户相对于伪卫星i的观测方程为

ρi=ri+c·(δtu-δti)+Ti+εi

(1)

ρi-Ti+cgδti-εi=

(2)

其中含有4个未知量，通过接收到至少4颗伪卫星信号联立求解，就可以单独实现导航定位。

2 精度因子DOP

虽然伪卫星定位原理和GNSS导航定位原理相似，但由于伪卫星布站区域仅限于对流层到地平面区域，大多数伪卫星平台都直接安装在地面，组成地基伪卫星网，伪卫星布局受限，从而造成伪卫星独立定位系统中定位精度很差，严重影响伪卫星系统的可用性和性能。

在卫星导航定位系统中，有很多方法可以评定伪卫星的几何分布结构对定位精度的影响，精度因子(DilutionofPosition，DOP)由于计算较为简单并且表达直观，成为其中较为常用的一种衡量尺度。在同等用户等效距离误差的条件下，DOP值越小，往往代表星座分布结构越好，定位精度越高。通过对已知卫星几何分布下空间内各点的DOP的仿真计算，可以得到对相应分布结构的评价结果，以此作为设计、选择伪卫星组网方式好坏的判断依据。

设用户接收机的位置为(xu，yu，zu)，第i颗伪卫星的位置为(xi，yi，zi)(i=0，1，…，n，n为伪卫星数目)。由伪卫星的几何分布可以首先得到观测矩阵如下[9]

(3)

其中，(axi，ayi，azi)为从用户接收机(即需要计算DOP的位置)指向第i颗卫星的单位矢量。单位矢量的计算式如下

(4)

得到观测矩阵G后，可以由此得到权系数矩阵H如下

(5)

而相应的各种DOP值都可以根据权系数矩阵H计算得到。

常用精度因子有几何精度因子(GDOP)、位置精度因子(PDOP)、水平精度因子(HDOP)、垂直精度因子(VDOP)和时间精度因子(TDOP)。几何精度因子GDOP反应了空间位置误差和时钟误差的综合影响；空间位置精度因子PDOP反应了空间位置误差的影响；水平位置精度因子HDOP反应了水平位置误差的影响；垂直位置精度因子VDOP反应了垂直位置误差的影响；时间精度因子TDOP反应了时钟误差的影响，其表达式分别如下

(6)

由式(6)，我们有了评价精度因子的指标，可以看出精度因子只与用户位置和伪卫星位置有关，根据不同的要求，取不同的精度因子，为粒子群优化中的适应度函数，则可以找到对应的最优的伪卫星布站方案。

3 基于粒子群算法的伪卫星布站优化方法

3.1 基本粒子群优化方法

在基本的粒子群算法中，先在可行解空间中随机初始化n个粒子构成初始种群，并为每个粒子随机初始化一个速度，每个粒子都对应优化问题的一个解，并由目标函数为之确定一个适应值，而速度用来决定粒子在解空间中的运动。在算法的每次迭代中，粒子将跟踪自身从开始到当前找到的自身最优解和种群当前找到的最优解，逐代搜索，直到最后得到最优解。

(7)

其中，c1和c2称为加速度因子，通常取为2；R1与R2为均匀分布于[0，1]之间的随机数，且相互独立；a称为约束因子，通常为1；ω为惯性权值，通常取为1。

式(7)为粒子群算法基本算法，即基本粒子群算法。基本PSO算法早期收敛速度非常快，但却暴露出局部搜索能力差的缺点，这使得算法后期收敛速度缓慢且求解精度降低。

为了改进粒子群算法，使得开始迭代时尽可能在较大范围内搜索，避免陷入局部最优解，当迭代到达一定阶段后，缩小迭代范围，在较小范围内迭代求解，提高求解精度，Shi等[10]进一步提出了LDIV策略，即在迭代过程中线性地减小惯性权值，并表示为

(8)

其中，ωmax、ωmin分别表示优化过程中惯性权值的最大最小值，N表示最大迭代次数，np表示当前已迭代的次数。通过线性递减惯性权值，提高了优化算法性能，减少迭代次数，提高了精度，本文采用线性递减粒子群算法来优化伪卫星布站问题。

3.2 基于粒子群算法的布站优化设计

基于粒子群算法的优化布站设计主要分以下几步：

1)初始化。确定可布站分布范围和需要布站的伪卫星数目，取所有伪卫星三维位置坐标值的组合作为每个粒子的位置，在可布站分布范围内随机初始化粒子的位置矢量和速度矢量，伪卫星数目至少为4。并将粒子当前位置初始化为该粒子历史最优解，以所需DOP因子为适应度函数，寻找当前DOP最小的粒子位置为全局最优解。

2)逐步迭代。按照式(7)和式(8)，进行粒子位置和速度进化，在更新位置过程中，我们要不断对每个粒子的各维位置坐标进行检测，若大于所限定区域上界，则约束为上界；若小于所限定区域下界，则约束为下界，这样使得粒子不超出所限定区域。同时，对DOP因子的计算过程涉及到矩阵求逆，在求逆之前应先检测矩阵是否可逆，对于不可逆的结果定义为无效位置，不参与最优解计算与比较，继续下一次迭代。

3)更新最优解。每次迭代后都要重新计算各个粒子的适应度(这里指所要求优化目标的DOP值)。对每个粒子当前适应度和该粒子历史最优适应度进行比较，若优于历史最优适应度，则更新该粒子的最优解。最后，选出粒子群的最优适应度作为全局最优解。

4)算法结束。当到达优化迭代次数或者达到求解精度后结束迭代，当前全局最优解即为最优布站方案。

算法流程如图2所示。

图2 基于粒子群算法的伪卫星布站优化设计流程图Fig.2 Flow chart of pseudo-satellite stationoptimization design based on particle swarmoptimization algorithm

4 仿真分析

根据一种最基本的伪卫星定位系统的设计，采用4～5颗伪卫星组成伪卫星网络，在本次仿真中，对坐标系的定义进行说明如下：坐标系用o0x0y0z0表示，坐标原点用o0表示，o0x0轴在坐标原点的水平面内，指向瞄准方向；o0y0轴沿过坐标原点的铅垂线，与o0x0轴垂直且指向上；o0z0轴与o0x0轴及o0y0轴形成右手直角坐标系。在以上坐标系中，伪卫星布局范围(-300，0，-300)，(-300，0，300)，(60，0，-300)，(60，0，300)(单位：km)。目标优化轨迹为从两条从原点出发在xoy平面内以抛物线方式前进一段距离。由于最远端对应精度因子最差的点，以轨迹最远端(坐标(300，10，0))为优化点，以此来实现对整条轨迹的优化。

1)4颗陆基伪卫星(Y=0)，以HDOP为粒子群适应度函数，迭代次数200次，伪卫星布站优化结果如表1所示(坐标单位为km)。

表1 4颗陆基伪卫星、HDOP为适应度函数的布站优化结果Tab.1 Optimization results of pseudo-satellite stationby 4 ground-based pseudo-satellites and HDOP as the fitness function

以表1优化结果为伪卫星位置，对远近两种轨迹的HDOP进行仿真，结果如图3所示。

由图3可以看出，优化后的伪卫星布站可以使得较近轨迹上的HDOP在1.6～2.18，较远轨迹上的HDOP在1.6～3.17，已经达到了可以与GPS导航卫星相比拟的程度，可以满足工程对水平方向定位精度要求的需求。

图3 沿着近轨迹和远轨迹HDOP仿真曲线图Fig.3 Simulation curves of HDOP along the track of near and far trajectories

2)4颗陆基伪卫星(Y=0)，以PDOP为粒子群适应度函数，迭代次数200次，伪卫星布站优化结果如表2所示(坐标单位为km)。

表2 4颗陆基伪卫星、PDOP为适应度函数的布站的优化结果Tab.2 Optimization results of pseudo-satellitestation by 4 ground-based pseudo-satellites and PDOP as the fitness function

以表2优化结果为伪卫星位置，对近轨迹和远轨迹的HDOP、VDOP、GDOP进行仿真，结果如图4所示。

由图4中6个仿真图可以看出，以定位精度因子PDOP为粒子群适应度函数情况下，在水平方向定位精度比以HDOP为适应度函数求解得水平方向精度稍差，由于伪卫星都布设在地面，垂直方向精度因子都比水平方向精度因子大很多，说明地基伪卫星不适用于高程定位。通过粒子群算法优化，可以保证在较近仿真轨迹上，垂直精度因子小于32；在较远仿真轨迹上，垂直精度因子小于55。也说明在远离伪卫星区域的地表附近，定位精度急速恶化，此时应采用其他方法弥补伪卫星高程定位的不足，以确保飞行器全程导航定位。

3)3颗陆基伪卫星(Y=0)，1颗高程20km以内空基伪卫星(0km≤Y≤20km)，以PDOP为粒子群适应度函数，迭代次数200次，伪卫星布站优化结果如表3所示(坐标单位为km)。

表3 3颗地基伪卫星和1颗空基伪卫星、PDOP为适应度函数的布站的优化结果Tab.3 Optimization results of pseudo-satellite station by 3 ground-based and 1 air-based pseudo-satellites and PDOP as the fitness function

以表3优化结果为伪卫星位置，对较近仿真轨迹和较远轨迹的HDOP、VDOP、GDOP进行仿真，结果如图5所示。

图4 沿着近轨迹和远轨迹HDOP、VDOP和PDOP仿真曲线图Fig.4 Sinulation curves of HDOP，VDOP and PDOP along the track of the near and far trajectories

图5 沿着近轨迹和远轨迹HDOP、VDOP和PDOP仿真曲线图Fig.5 Simulation curves of HDOP，VDOP and PDOP along the track of the near and far trajectories

由图5中6个仿真曲线图可以看出，增加1颗空基伪卫星后，除去轨迹起始点和终止点处，全程VDOP和PDOP有一定改进，HDOP有一定的恶化。增加空基伪卫星后，提高了高程定位精度，从而用户三维定位精度都有所提高，但是空基伪卫星需要将伪卫星放置于20km高空，会有飞行器移动的动态造成用户测距困难，可能引入较大误差。

从以上仿真结果可以看出，基于粒子群算法的伪卫星布站优化方案，可以根据不同指标要求和不同布站环境下寻找出较优化的伪卫星布站方案，从而证实了本文所提出方案的可行性。

5 结论

通过本文所述线性递减权值粒子群优化算法，对伪卫星布站进行优化设计，针对不同适应度函数，优化得出满足不同要求的伪卫星布站方案，大大提高了伪卫星独立导航定位系统的定位精度，提高了伪卫星系统的性能，本文方案对伪卫星布站设计具有重要的工程应用价值。

[1] Choudhury M，Rizos C.Slow structural deformation monitoring using Locata-A trial at Tumut Pond Dam[J].Journal of Applied Geodesy，2010，4(4)：177-187.

[2] Bonenberg L K，Hancock C，Roberts G W.Locata performance in a long term monitoring[J].Journal of Applied Geodesy，2013，7(4)：271-280.

[3] Jianpeng W，Jingxiang GAO，Chao LIU，et al.High precision slope deformation monitoring model based on the GPS/Pseudolites technology in open-pit mine[J].Mining Science and Technology，2010，20(1)：126-132.

[4] Montillet J P，Meng X，Taha A，et al.Achieving centimeter-level positioning accuracy in urban canyons with locata technology[J].Positioning，2007，1(12).

[5] Kennedy J.Particle swarm optimization[M].Encyclopedia of Machine Learning.Springer US，2010：760-766.

[6] Elegbede C.Structural reliability assessment based on particles swarm optimization[J].Structural Safety，2005，27(2)：171-186.

[7] Robinson J，Rahmat-Samii Y.Particle swarm optimization in electromagnetics[J].Antennas and Propagation，IEEE Transactions on，2004，52(2)：397-407.

[8] Salman A，Ahmad I，Al-Madani S.Particle swarm optimization for task assignment problem[J].Microprocessors and Microsystems，2002，26(8)：363-371.

[9] GPS原理与接收机设计[M].电子工业出版社，2009.

[10] Shi Y，Eberhart R C.Empirical study of particle swarm optimization[C].Evolutionary Computation，1999.CEC 99. Proceedings of the 1999 Congress on.IEEE，1999，3.

Optimal Design of Pseudo-satellite Station Based on Particle Swarm Optimization Algorithm

LI Dong-xin1，3，PENG Yun2，CHANG Qing1，LI Jing3，YU Yuan3

(1.Electronic and Informational Engineering Institute，Beihang University，Beijing 100191，China；2.Beijing Institute of Space Long March Vehicle，Beijing 100076，China；3.R&D Center of Traffic Information and Communication Technology，Beijing 100011，China)

For pseudo-satellite station problem，we adopt the particle swarm algorithm which has the function of intelligent optimization.We use the accuracy factor of navigation and positioning as the fitness function of the particle swarm，with a linear decreasing inertia weight strategy and the appropriate number of evolution and iterative，eventually to find optimal design of pseudolite station.We use two parabolic trajectories in the vertical planes for simulation，the results show that，the station design scheme for pseudo-satellite based on particle swarm optimization algorithm can reduce the whole precision factor，and improve the positioning accuracy of independent pseudo-satellite positioning system.

Particle swarm algorithm；Linear decreasing inertia weight strategy；Pseudo-satellite station

2015 - 07 - 15；

2015 - 08 - 13。

国家863项目基金(2013AA122403)

李东新(1989 - )，男，硕士，主要从事扩频通信，卫星导航，信息处理方面的研究。

E-mail：lidx2013@buaa.edu.cn

TN967.1

A

2095-8110(2015)05-0044-08