现有的快速选星算法主要集中在2个方面：①从所有可见卫星中选择最佳卫星几何分布的某些可见卫星。研究者根据最优选星方案的卫星分布特点，利用卫星高度角和方位角信息实现卫星的区域划分，并对如何分配高仰角和低仰角的选星数目展开讨论[5-6]。②GDOP的计算。GDOP通常可看作是接收机测量误差与定位误差之间的放大倍数，是用来衡量从m颗可见卫星(m>n)中选择出的n颗卫星子集是否具有较好的空间几何分布的重要指标。GDOP的计算存在矩阵相乘和求逆过程，明显增加了选星的计算量。若实现快速选星，可通过求逆引理等方法简化求解GDOP的计算公式[7]，也可以采用优化算法尽可能减少GDOP的计算次数[8-10]，二者都能在一定程度上缩减选星耗时。2010年，Mosavi和Divband[8]提出用遗传算法(GA)实现选星，通过GA的快速寻优能力减少GDOP的计算次数。然而GA选星存在易陷入局部最优的问题，研究者又对算法进行大量改进，提高了算法选星结果的准确性[9-10]。但由于GA的计算过程需要调节的参数过多，所以在保证选星准确性的条件下，GA选星速度也会随着可见卫星数目的增加而减慢。
与GA类似，粒子群优化(Particle Swarm Optimization, PSO)算法是一种随机寻优算法。目前该算法已经在目标跟踪、图像处理等诸多领域得到应用[11-12]，但在多星座选星方面少有文献提及。本文针对PSO算法在组合导航选星上的应用进行研究，建立了PSO选星算法模型；引入混沌序列改进算法，提高选星有效性；通过实际的导航数据进行仿真实验，验证所提算法的性能。
1 混沌粒子群优化模型 在多星座组合卫星导航系统中，为了降低接收机的运算量，需要从可见的所有卫星中选出空间结构较优的一组用于定位。精度因子(DOP)常用来衡量卫星空间几何分布情况，其计算公式中存在矩阵相乘和求逆，是选星中比较耗时的运算。而PSO算法能够通过有限次迭代，从全部解空间中快速搜索到符合条件的目标解。因此，运用PSO算法的快速寻优能力，从全部可见卫星组合中快速选取空间几何分布较好的卫星组合，能够减少DOP的计算次数，从而减少选星的耗时。
PSO算法是Eberhart和Kennedy通过模仿鸟类的觅食行为而产生的[13]，搜索空间的个体通过比较自身所经过的最优位置和种群中其他粒子最优位置，不断调整自身速度，使其向最优解靠拢。个体被称为“粒子”，每个粒子为d维空间的一个点，第i个粒子可以表示为xi=[xi1, xi2, …, xid]，粒子在运动过程中，会根据自身经验产生个体极值pbest=[pi1, pi2, …, pid]，同时在种群中会产生全局极值gbest，粒子通过2个“极值”不断调整自身位置，位置更新如式(1)所示，使其不断趋近全局最优值。第i个粒子的位置变化速度被表示为vi=[vi1, vi2, …, vid]。
 | (1) |
 | (2) |
式中：t为当前迭代次数；N为种群中粒子的总数；ω为惯性权重；c1和c2为加速常数，分别调节向pbest和gbest方向的运动速度；r1和r2为0~1之间均匀分布的随机数。另外，通过设置微粒的速度范围[vmin, vmax]和位置范围[xmin, xmax]，可以对粒子运动的步长进行适当的限定。
惯性权重ω对全局和局部搜索的平衡起到了重要作用，其值通常是从0.9~0.4线性递减的[14]。在迭代过程中，表达式为ω=ωmax－(ωmax－ωmin)t/tmax，ωmax和ωmin分别为最大和最小惯性权重，tmax为总的迭代次数。
PSO算法的结果容易陷入局部最优，为此引入混沌理论，提高结果的有效性。混沌搜索，即对于给定的优化函数，将变量从混沌空间映射到解空间，然后利用混沌变量进行搜索[15]，可避免搜索结果陷入“局部最优”。
Logistic映射是较为常见的混沌序列产生方法，其表达式为
 | (3) |
式中：zi∈(0, 1)。当z0?{0, 0.25, 0.5, 0.75, 1}、μ=4时，Logistic映射产生混沌序列。利用Logistic映射初始化均匀分布的初始粒子，能够增强PSO算法的稳定性[16]。
首先生成(0, 1)的随机数zi，根据式(3)更新zi，然后根据公式xi=ximin+zi(ximax－ximin)，将混沌空间映射到待优化的解空间。
2 北斗/GPS组合导航选星算法 2.1 混沌粒子群优化适应度函数 适应度函数又称为目标函数，是用来评价粒子优劣的重要衡量标准，适应度函数的选取直接影响算法结果的有效性。本文采用的适应度函数是各可见卫星组合的GDOP值，用于评价所选卫星组合的空间几何结构性能。
选星算法主要以用户与可见卫星组合的空间几何分布为衡量标准。针对用户与可见卫星组合的空间几何分布特性的表征，DOP是应用最广泛的参数，按照DOP进行选星可以保证定位精度[1]。卫星导航定位系统的DOP可用GDOP与用户等效测距误差(User Equivalent Range Error，UERE)的乘积来表示，即
 | (4) |
式中：σp为导航定位位置/时间解的精度；σUERE为伪距测量值的标准差；GDOP与用户到卫星的几何结构有关。从式(4)可知，当σUERE确定时，GDOP越小，定位精度越高。
GDOP可定义为协方差矩阵的迹的平方根，即
 | (5) |
式中：trace(·)表示矩阵的迹；H为观测矩阵。假设北斗/GPS组合导航接收机能接收到m颗GPS卫星、k颗北斗卫星，即可产生m+k个观测量，构成的观测矩阵为
 | (6) |
式中：(ei, ni, ui)为接收机近似位置指向第i颗卫星单位矢量的方向余弦，下标G代表GPS星座，可见星数目为1，2, …，m, 下标B代表北斗星座，可见星数目为1，2, …，k。
2.2 混沌粒子群优化选星算法设计 假设某时刻接收机接收到可见卫星总数为n颗，从中选取m颗，使其GDOP值尽可能小。在混沌粒子群优化(CPSO)算法选星中，每个粒子代表一种可见卫星组合，粒子的位置由m个元素决定，每个元素代表一颗可见卫星，CPSO选星算法具体步骤如下：
步骤1 ??可见卫星提取。根据导航电文，提取当前时刻仰角大于遮蔽角的卫星(本文中的遮蔽角取值为5°)，得到该时刻的可见卫星总数。
步骤2 ??编码。对当前时刻接收机观测到的所有可见卫星进行随机排列，然后将可见卫星从1, 2, …, n依次连续编码，编码与可见卫星一一对应。
步骤3 ??生成初始种群。将n颗可见卫星按照每m颗为一组进行组合，形成Cnm种可见卫星组合，每种组合方式被视为一个粒子。设定种群大小为M，根据式(3)，从Cnm种可见卫星组合中混沌搜索M个组合，形成初始种群G0={x0i}(i=1, 2, …, M)；种群中第i个粒子表示为x0i=[x0i, 1, x0i, 2, …, x0i, m]，x为卫星编号，m为选星颗数；初始速度v0i=[v0i, 1, v0i, 2, …, v0i, m]，v为卫星号的改变量，初始速度设置为[0, 0, …，0]。下标“0”表示粒子经过0次迭代，即为初始位置和速度。
步骤4 ??适应度的计算。本文采用的适应度函数是编码所对应的可见卫星组合的GDOP，记为粒子的目标值fti=GDOPi，下标“t”为粒子经过t次迭代。将初始种群中的粒子依次代入适应度函数中，得出各粒子的适应度值(即GDOP)。将种群中GDOP最小的粒子设置为初始种群最优位置gbest，每个粒子当前的位置gt, i为初始个体最优位置pbest。
步骤5 ??更新。对于每个粒子，根据式(1)和式(2)不断修正种群中粒子的位置xti和速度vti，分别计算新位置对应的目标值fti，并更新粒子所经过的最优位置pbest和种群最优位置gbest。直到达到最大迭代次数，终止迭代。
将CPSO算法应用到选星过程中，需要明确3个量：初始化粒子种群、选取适应度函数和速度位置的更新，其基本步骤流程如图 1所示。
 |
| 图 1 CPSO选星算法流程 Fig. 1 Flowchart of CPSO satellite selection algorithm |
| 图选项 |
在算法流程中，粒子更新时需注意2个关键点：①可见卫星编号为整数，因此更新过程中必须保证粒子位置中的每个元素都为整数，否则将找不到与编码对应的可见星；②选星颗数为m颗，如果粒子位置中的元素有相同的，选星颗数就会少于m颗。为了保证选星数目，每次更新都必须判断更新后的粒子位置中是否有相同元素。本文给出的解决办法是在粒子进入迭代循环后，首先判断每个粒子中是否存在相同的元素。如果存在相同元素，则对粒子中元素从小到大排序，找出相同元素的个数及位置，在与之重复的第k个元素值上加k，然后返回重新判断是否有重复元素，直到该粒子中无相同元素为止。
3 仿真验证与结果分析 CPSO选星是为了解决北斗/GPS组合导航下选星颗数大于5的选星问题。本文选取北斗/GPS接收机坐标为[-2 279 827.315 6，5 004 704.309 4，3 219 776.209 3]m，选星颗数为6。卫星位置由导航星历计算，卫星的截止高度角设为5°，仿真开始时间为2016-07-31 00:00:00，仿真时长为3 h，仿真步长为1 min。
本文将采用遍历法选星得到的GDOP值作为参考。假设全部可见卫星数目为n，从中选取m颗可见星，有Cnm种组合。所谓遍历法，就是逐个计算Cnm种组合的GDOP值，得出GDOP最小值。北斗/GPS可见卫星数目及其对应的GDOP最小值如图 2所示。
 |
| 图 2 北斗/GPS可见卫星数及对应的GDOP最小值 Fig. 2 Number of BDS/GPS visible satellite and their minimum GDOP |
| 图选项 |
由图 2中可以看出，同一时刻，接收机接收到北斗/GPS可见卫星数目约为18颗，以从18颗可见卫星中选取6颗为例，需要进行C186=18 564次GDOP值的计算，单次选星耗时约为4 s左右。
按照PSO选星步骤，设定算法参数：迭代次数MaxIt=50，种群大小M=100，惯性权重ω=0.729 8，加速常数c1=c2=1.496 2，vmax=2。选取某一时刻进行GDOP值的计算，随着迭代次数的增加GDOP值的变化如图 3所示。
 |
| 图 3 PSO选星时GDOP值随迭代次数的变化 Fig. 3 Change of GDOP with iteration numbers of PSO satellite selection |
| 图选项 |
通过遍历法得出该时刻的GDOP最小值为2.25。图 3中的结果显示，PSO算法的收敛速度很快，迭代次数在小于15次时就稳定在2.34附近，且在后续迭代过程中保持不变。很明显，PSO算法出现“早熟”现象，即陷入局部最优解。
采用CPSO算法对同一时刻进行仿真实验，结果如图 4所示。
 |
| 图 4 CPSO选星时GDOP值随迭代次数的变化 Fig. 4 Change of GDOP with iteration numbers of CPSO satellite selection |
| 图选项 |
从图 4中可以看出，CPSO算法同样在迭代次数低于15次时收敛，并有效改善了PSO选星算法易陷入局部最优的缺点。在迭代次数为50次时，耗时约为1.5 s左右，如果按需求适当减少迭代次数，选星耗时也会有所减少。
遍历法、PSO和CPSO选星算法在相同历元的选星耗时及其对应的选星结果(最后一列数字代表卫星号)如表 1所示。
表 1 三种选星算法性能对比 Table 1 Performance comparison of three satellite selection algorithms
| 选星算法 | 单次耗时/s | GDOP | 选星结果 |
| 遍历法 | 4.074 824 | 2.251 038 | 92127373839 |
| PSO | 1.665 020 | 2.347 418 | 92127373842 |
| CPSO | 1.435 994 | 2.333 044 | 92127333837 |
表选项
从表 1中数据得知，基于PSO和CPSO的选星算法在单次选星所用时间约为遍历法选星的37.5%，但选星结果仍有偏差。为了充分验证算法性能，下面将给出仿真时长为3 h的PSO和CPSO选星GDOP计算误差，其误差定义为新算法所得到的GDOP值与遍历法选星所得到GDOP值的差值，结果如图 5所示。
 |
| 图 5 PSO和CPSO选星的结果误差 Fig. 5 Result error of satellite selection by PSO and CPSO |
| 图选项 |
从图 5中可知，PSO和CPSO选星算法的GDOP计算误差均小于等于0.6。对所得数据进行统计，CPSO选星的GDOP计算误差平均值为0.260 9，方差为0.042 4；PSO选星的GDOP计算误差平均值为0.263 2，方差为0.043 0。
4 结论 本文提出了一种基于CPSO的北斗/GPS组合导航选星算法，利用CPSO算法的快速寻优能力，减少GDOP的计算次数，从而实现了北斗/GPS组合导航快速选星，通过对算法进行仿真验证，得到以下结果：
1) 在北斗/GPS组合导航下，选星颗数为6时，算法能够实现快速选星。该算法的单次选星时间约为1.5 s，约为遍历法选星的37.5%。
2) 利用混沌方程初始化种群粒子能够提高选星结果的准确性。
3) PSO和CPSO选星算法的GDOP计算误差均小于等于0.6，二者的平均计算误差约为0.26。
本文将CPSO算法应用于组合卫星导航选星过程中，为多星座组合导航快速选星问题提供了新的解决方法。
参考文献
| [1] | 张军. 空地协同的空域监视新技术[M]. 北京: 航空工业出版社, 2011: 36-38. ZHANG J. Air-ground collaborative airspace surveillance[M]. Beijing: Aviation Industry Press, 2011: 36-38. (in Chinese) |
| [2] | 王尔申, 杨福霞, 庞涛, 等. BDS/GPS组合导航接收机自主完好性监测算法[J]. 北京航空航天大学学报, 2018, 44(4): 684-690. WANG E S, YANG F X, PANG T, et al. BDS/GPS combined navigation receiver autonomous integrity monitoring algorithm[J]. Journal of Beijing University of Aeronautics and Astronautics, 2018, 44(4): 684-690. (in Chinese) |
| [3] | ZHANG M, ZHANG J. A fast satellite selection algorithm:Beyond four satellites[J]. IEEE Journal of Selected Topics in Signal Processing, 2009, 3(5): 740-747. DOI:10.1109/JSTSP.2009.2028381 |
| [4] | SWASZEK P F, HARTNETT R J, SEALS K C, et al.Multi-constellation GNSS: New bounds on DOP and a related satellite selection process[C]//Proceedings of the 29th International Technical Meeting of the Satellite Division of the Institute of Navigation (ION GNSS+2016).Washington, D.C.: INST Navigation, 2016: 228-235. |
| [5] | 丛丽, AHMED I A, 谈展中. 卫星导航几何因子的分析和仿真[J]. 电子学报, 2006, 34(12): 2204-2208. CONG L, AHMED I A, TAN Z Z. Analysis and simulation of the GDOP of satellite navigation[J]. Acta Electronica Sinica, 2006, 34(12): 2204-2208. DOI:10.3321/j.issn:0372-2112.2006.12.017 (in Chinese) |
| [6] | 陈灿辉, 张晓林. 一种新的卫星导航系统快速选星方法[J]. 电子学报, 2010, 38(12): 2887-2891. CHEN C H, ZHANG X L. A fast satellite selection approach for satellite navigation system[J]. Acta Electronica Sinica, 2010, 38(12): 2887-2891. (in Chinese) |
| [7] | PHATAK M S. Recursive method for optimum GPS satellite selection[J]. IEEE Transactions on Aerospace & Electronic Systems, 2001, 37(2): 751-754. |
| [8] | MOSAVI M R, DIVBAND M.Calculation of geometric dilution of precision using adaptive filtering technique based on evolutionary algorithms[C]//International Conference on Electrical and Control Engineering.Piscataway, NJ: IEEE Press, 2010: 4842-4845. |
| [9] | 宋丹, 许承东, 胡春生, 等. 基于遗传算法的多星座选星方法[J]. 宇航学报, 2015, 36(3): 300-308. SONG D, XU C D, HU C S, et al. Satellite selection with genetic algorithm under multi-constellation[J]. Journal of Astronautics, 2015, 36(3): 300-308. DOI:10.3873/j.issn.1000-1328.2015.03.008 (in Chinese) |
| [10] | 霍航宇, 张晓林. 组合卫星导航系统的快速选星方法[J]. 北京航空航天大学学报, 2015, 41(2): 273-282. HUO H Y, ZHANG X L. Fast satellite selection method for integrated navigation systems[J]. Journal of Beijing University of Aeronautics and Astronautics, 2015, 41(2): 273-282. (in Chinese) |
| [11] | 徐小钧, 马利华, 艾国祥. 基于多目标遗传算法的多星座选星方法[J]. 上海交通大学学报, 2017, 51(12): 1520-1528. XU X J, MA L H, AI G X. Satellite selection with multi-objective genetic algorithm for multi-GNSS constellations[J]. Journal of Shanghai Jiao Tong University, 2017, 51(12): 1520-1528. (in Chinese) |
| [12] | EBERHART R C, SHI Y H.Particle swarm optimization: Developments, applications and resources[C]//Proceedings of the 2001 Congress on Evolutionary Computation.Piscataway, NJ: IEEE Press, 2002: 81-86. |
| [13] | EBERHART R C, KENNEDY J.A new optimizer using Particle swarm theory[C]//Proceeding of the 6th International Symposium on Micro Machine and Human Science.Piscataway, NJ: IEEE Press, 1995: 39-43. |
| [14] | SHI Y H, EBERHAR R.A modified particle swarm optimizer[C]//IEEE International Conference on Evolutionary Computation.Piscataway, NJ: IEEE Press, 1998: 69-73. |
| [15] | 胥小波, 郑康锋, 李丹, 等. 新的混沌粒子群优化算法[J]. 通信学报, 2012, 33(1): 24-30. XU X B, ZHENG K F, LI D, et al. New chaos-particle swarm optimization algorithm[J]. Journal on Communications, 2012, 33(1): 24-30. DOI:10.3969/j.issn.1000-436X.2012.01.004 (in Chinese) |
| [16] | TIAN D P, SHI Z Z. MPSO:Modified particle swarm optimization and its applications[J]. Swarm & Evolutionary Computation, 2018, 41: 49-68. |
