基于并行遗传算法的高轨卫星导航选星方法

石涛; 庄学彬; 林子健; 曾小慧

doi:10.13700/j.bh.1001-5965.2022.0118

基于并行遗传算法的高轨卫星导航选星方法

doi: 10.13700/j.bh.1001-5965.2022.0118

中山大学系统科学与工程学院，广州 510006

详细信息

通讯作者:
E-mail：zhuangxb@mail.sysu.edu.cn

中图分类号: V241.6；TN967.6
计量
- 文章访问数: 171
- HTML全文浏览量: 72
- PDF下载量: 13
- 被引次数: 0
出版历程
- 收稿日期: 2022-03-04
- 录用日期: 2022-07-02
- 网络出版日期: 2022-09-14
- 整期出版日期: 2023-12-31

Satellite selection based on parallel genetic algorithm for high orbit autonomous satellite navigation

School of Systems Science and Engineering，Sun Yat-Sen University，Guangzhou 510006，China

More Information

Corresponding author: E-mail：zhuangxb@mail.sysu.edu.cn

摘要

摘要:
高轨航天器自主导航能力在北斗三号卫星导航系统建成后得到了增强，但是也带来了部分时刻可见星数量冗余的问题。为降低运算量以保证服务的实时性，提出一种利用多种群并行遗传算法 (PGA) 进行快速选择当前最优可见星组合的方法。该方法将加权精度因子 (WDOP) 作为适应度评判标准，利用粗粒度式并行划分成的多个子种群进行搜索加速，并通过变异因子差异化设置与子种群间的信息交流来提高搜索能力。对多个典型高轨环境下7颗及以上选星任务的仿真测试表明，基于PGA的选星方法解相比遍历法所求最优解绝对误差平均值小于0.1，相对误差最大不超过1%。仿真结果表明，在典型高轨环境F₁接收机利用四系统组合导航时，所提方法可以有效地快速、准确完成指定卫星数的选星任务。
- 北斗三号卫星导航系统 /
- 高轨 /
- 选星 /
- 并行遗传算法 /
- 加权精度因子
Abstract:
After the BeiDou-3 navigation satellite system was finished, the performance of high-orbit autonomous navigation was improved, but it also occasionally resulted in the redundancy of visible satellites. In order to reduce the arithmetic operations to ensure the real-time performance, based on a multiple-population parallel genetic algorithm (PGA), a new method to quickly select the optimal combination of visible satellites was proposed. The algorithm chooses the weighted dilution of precision (WDOP) as the fitness function, uses sub-populations in coarse-grained to speed up the search, and improves the searchability through the differential setting of mutation factors and the information exchange between sub-populations. The simulation experiments result of 7 or more satellite selection tasks in several typical high orbit environments show that the average absolute error between the PGA-based selection algorithm solution and the optimal solution obtained by the ergodic method is less than 0.1, and the maximum relative error is less than 1%. The outcomes demonstrate that, when the receiver employs the four-system integrated navigation in a typical high-orbit environment, the algorithm can efficiently execute the task of choosing satellites for the specified number of satellites fast and precisely.
- BeiDou-3 navigation satellite system /
- high orbit /
- satellite selection /
- parallel genetic algorithm /
- weighted dilution of precision

HTML全文

图 1 高轨航天器接收不同高度导航卫星信号示意图

Figure 1. Schematic diagram of spacecraft in high orbit receiving navigation satellite at different altitudes

下载: 全尺寸图片幻灯片

图 2 3种并行模型

Figure 2. Three parallel models

下载: 全尺寸图片幻灯片

图 3 交叉过程

Figure 3. Crossover operator

下载: 全尺寸图片幻灯片

图 4 选星数对精度与计算量的影响

Figure 4. Impact of number of selected satellites on accuracy and calculation

下载: 全尺寸图片幻灯片

图 5 WDOP误差值

Figure 5. WDOP error

下载: 全尺寸图片幻灯片

图 6 误差与子种群数关系

Figure 6. Error in relation to sub-population number

下载: 全尺寸图片幻灯片

表 1 接收机工作轨道根数

Table 1. Elements of working orbits of receiver

轨道类型	半长轴/ km	偏心率	轨道倾角/(°)	近地点幅角/(°)	平近点角/(°)	升交点赤经/(°)
	42166.3	0	0	0	264	90
GEO	42166.3	0	0	0	324	90
	42166.3	0	0	0	24	90
	42166.3	0	60	0	0	335
IGSO	42166.3	0	120	0	0	34
	42166.3	0	90	0	0	94
SSTO	43321.3	0.84	15	270	92	262
	40482.9	0.84	16	60	84	309
	40482.9	0.84	100	100	84	280
	40482.9	0.84	100	270	84	280

下载: 导出CSV

表 2 并行遗传选星结果对比

Table 2. Results comparison of satellite selection based on PGA

种群数	平均误差			平均方差			平均耗时/ms
种群数	M=150	M=200	M=250	M=150	M=200	M=250	M=150	M=200	M=250
1	0.1071	0.0962	670	0.0419	0.0436	879	0.0180	0.0185	1104
2	0.0748	0.0685	355	0.0435	0.0412	466	0.0246	0.0174	576
3	0.0811	0.0747	253	0.0317	0.0197	322	0.0222	0.0172	409
4	0.0890	0.0798	187	0.0410	0.0339	256	0.0162	0.0106	317
5	0.1227	0.1340	161	0.0498	0.0429	222	0.0323	0.0231	265
6	0.1467	0.1467	149	0.0787	0.0787	195	0.0385	0.0385	243

下载: 导出CSV

表 3 不同选星数下方法性能

Table 3. Performance under different number of satellites selected

选星数	平均误差	平均方差	平均耗时/ms	遍历法平均耗时/ms
7	0.025 5	0.019 8	212	12 837
8	0.026 3	0.021 9	237	34 251
9	0.016 6	0.014 6	280	79 591
10	0.016 2	0.010 6	317	162 492
11	0.010 8	0.002 9	360	293 288

下载: 导出CSV

表 4 选星方法效果对比

Table 4. Performance comparison of effects of satellite selection algorithms

轨道类型	平均定位误差/m
轨道类型	baseline	PGA	PSO
GEO 0°	8.44	7.51	7.88
GEO 125°	19.09	17.24	17.77
SSTO	26.36	21.41	22.10

下载: 导出CSV

参考文献(24)

[1]	SHI T, ZHUANG X, XIE L. Performance evaluation of multi-GNSSs navigation in super synchronous transfer orbit and geostationary earth orbit[J]. Satellite Navigation, 2021, 2(1): 1-13. doi: 10.1186/s43020-020-00033-9
[2]	ACHARYA R. Understanding satellite navigation[M]. New York: Academic Press, 2015.
[3]	YARLAGADDA R, ALI I, AL-DHAHIR N, et al. GPS GDOP metric[J]. IEE Proceedings-Radar, Sonar and Navigation, 2000, 147(5): 259-264. doi: 10.1049/ip-rsn:20000554
[4]	丛丽, ABIDAT A I , 谈展中. 卫星导航几何因子的分析和仿真[J]. 电子学报, 2006, 34(12): 2204-2208. doi: 10.3321/j.issn:0372-2112.2006.12.017 CONG L, ABIDAT A I, TAN Z Z. Analysis and simulation of the GDOP of satellite navigation[J]. Acta Electronica Sinica, 2006, 34(12): 2204-2208(in Chinese). doi: 10.3321/j.issn:0372-2112.2006.12.017
[5]	KIHARA M, OKADA T. A satellite selection method and accuracy for the global positioning system[J]. Navigation, 1984, 31(1): 8-20. doi: 10.1002/j.2161-4296.1984.tb00856.x
[6]	金玲, 黄智刚, 李锐, 等. 多卫导组合系统的快速选星算法研究[J]. 电子学报, 2009, 37(9): 1931-1936. JIN L, HUANG Z G, LI R, et al. Study on fast satellite selection algorithm for integrated navigation[J]. Acta Electronica Sinica, 2009, 37(9): 1931-1936(in Chinese).
[7]	MOSAVI M R, DIVBAND M. Calculation of geometric dilution of precision using adaptive filtering technique based on evolutionary algorithms[C]//Proceedings of the International Conference on Electrical and Control Engineering. Piscataway: IEEE Press, 2010: 4842-4845.
[8]	PHATAK M S. Recursive method for optimum GPS satellite selection[J]. IEEE Transactions on Aerospace and Electronic Systems, 2001, 37(2): 751-754. doi: 10.1109/7.937488
[9]	王尔申, 贾超颖, 曲萍萍, 等. 基于混沌粒子群优化的北斗/GPS 组合导航选星算法[J]. 北京航空航天大学学报, 2019, 45(2): 259-265. WANG E S, JIA C Y, QU P P, et al. BDS/GPS integrated navigation satellite selection algorithm based on chaos particle swarm optimization[J]. Journal of Beijing University of Aeronautics and Astronautics, 2019, 45(2): 259-265(in Chinese).
[10]	宋丹, 许承东, 胡春生, 等. 基于遗传算法的多星座选星方法[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(in Chinese).
[11]	WANG M, SHAN T, LI M, et al. GNSS-based orbit determination method and flight performance for geostationary satellites[J]. Journal of Geodesy, 2021, 95(8): 89. doi: 10.1007/s00190-021-01545-1
[12]	葛继科, 邱玉辉, 吴春明, 等. 遗传算法研究综述[J]. 计算机应用研究, 2008, 25(10): 2911-2916. doi: 10.3969/j.issn.1001-3695.2008.10.008 GE J K, QIU Y H, WU C M, et al. Summary of genetic algorithms research[J]. Application Research of Computers, 2008, 25(10): 2911-2916(in Chinese). doi: 10.3969/j.issn.1001-3695.2008.10.008
[13]	岳嵚, 冯珊. 粗粒度并行遗传算法的计算性能分析[J]. 武汉理工大学学报, 2008, 30(7): 107-110. YUE Q, FENG S. Performance analysis of thr coarse-grained parallel[J]. Journal of Wuhan University of Technology, 2008, 30(7): 107-110(in Chinese).
[14]	郭彤城, 慕春棣. 并行遗传算法的新进展[J]. 系统工程理论与实践, 2002, 22(2): 15-23. doi: 10.3321/j.issn:1000-6788.2002.02.003 GUO T C, MU C D. The parallel drifts of genetic algorithms[J]. Systems Engineering-Theory & Practice, 2002, 22(2): 15-23(in Chinese). doi: 10.3321/j.issn:1000-6788.2002.02.003
[15]	丁孟为. 遗传算法在多核系统上的性能分析和优化[D]. 上海: 上海交通大学, 2012. DING M W. Performance analysis and optimization of genetic algorithms on multi-core systems[D]. Shanghai: Shanghai Jiao Tong University, 2012 (in Chinese).
[16]	SIVANANDAM S N, DEEPA S N. Introduction to genetic algorithms[M]. Berlin: Springer, 2008.
[17]	程博文, 刘伟伟, 何熊文, 等. 猎户座飞船电子系统设计特点分析与启示[J]. 航天器工程, 2016, 25(4): 102-107. CHENG B W, LIU W W, HE X W, et al. Research on Orion electronic system[J]. Spacecraft Engineering, 2016, 25(4): 102-107(in Chinese).
[18]	王梦丽, 孙广富, 王飞雪, 等. 混合星座导航系统的加权几何精度因子分析[J]. 中国空间科学技术, 2007, 27(5): 50-56. WANG M L, SUN G F, WANG F X, et al. Weighted geometric dilution of precisio’s analysis for mixed constellation navigation sytem[J]. Chinese Space Science and Technology, 2007, 27(5): 50-56(in Chinese).
[19]	WON D H, AHN J, LEE S W, et al. Weighted DOP with consideration on elevation-dependent range errors of GNSS satellites[J]. IEEE Transactions on Instrumentation and Measurement, 2012, 61(12): 3241-3250. doi: 10.1109/TIM.2012.2205512
[20]	ZHENG L, LU Y, GUO M, et al. Architecture-based design and optimization of genetic algorithms on multi- and many-core systems[J]. Future Generation Computer Systems, 2014, 38: 75-91. doi: 10.1016/j.future.2013.09.029
[21]	LIENIG J. A parallel genetic algorithm for performance-driven VLSI routing[J]. IEEE Transactions on Evolutionary Computation, 1997, 1(1): 29-39. doi: 10.1109/4235.585890
[22]	LIU H, CAO J, CHENG X, et al. The data processing and analysis for the CE-5T1 GNSS experiment[J]. Advances in Space Research, 2017, 59(3): 895-906. doi: 10.1016/j.asr.2016.06.035
[23]	THOELERT S, ANTREICH F, ENNEKING C, et al. BeiDou 3 signal quality analysis and its impact on users[J]. Navigation: Journal of the Institute of Navigation, 2019, 66(4): 695-704. doi: 10.1002/navi.331
[24]	LIU H, CHENG X, TANG G, et al. GNSS performance research for MEO, GEO, and HEO[C]//Proceedings of the China Satellite Navigation Conference. Berlin: Springer, 2017: 37-45.