ACTA AERONAUTICAET ASTRONAUTICA SINICA >
Large-scale constellation TT&C resource scheduling algorithm based on adaptive simulated annealing
Received date: 2022-07-04
Revised date: 2022-07-20
Accepted date: 2022-08-04
Online published: 2022-08-08
Supported by
National Natural Science Foundation of China(62073341)
With the rapid growth of the number of satellites in orbit， the already relatively scarce Tracking Telemetry and Command （TT&C） resources are becoming even more scarce. The TT&C resource scheduling problem for large-scale constellation is restricted by multiple constraints， and is a complex combinatorial optimization problem with strong conflicts. An improved adaptive simulated annealing algorithm is proposed to solve the TT&C resource scheduling problem for large-scale constellation in order to improve the capability of TT&C systems and the revenue from completing TT&C tasks. Firstly， the satellite TT&C process is analyzed. According to satellite TT&C task requirements and resource usage constraints， a constraint satisfaction model is established aiming to maximize the total profits from task completion. A method for evaluating the conflict degree of available TT&C opportunities is proposed， and a fitness based task allocation algorithm is designed to generate a high-quality initial solution. Then， an adaptive simulated annealing algorithm combining perturbation strategy and tabu mechanism is designed， which adaptively controls the update of temperature and neighborhood structure selection probability during the optimization process of the algorithm. The short-term memory mechanism of the tabu table is used to avoid repeated searches. The perturbation strategy is combined to diverse the solution to a certain extent， thereby jumping out of the local optima and enhancing the optimization performance of the algorithm. Finally， in order to verify the effectiveness of the proposed method， a large number of simulation experiments were conducted to compare the algorithm with simulated annealing algorithm， genetic algorithm， fitness based task allocation algorithm， and maximum weight first allocation algorithm. Experimental results show that compared with traditional algorithms， the proposed algorithm improves the solution by 10.34%， 23.59%， 23.20%， and 46.51%， respectively.
Guohua WU , Tianyu WANG . Large-scale constellation TT&C resource scheduling algorithm based on adaptive simulated annealing[J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2023 , 44(12) : 327759 -327759 . DOI: 10.7527/S1000-6893.2022.27759
| 1 | 李峰， 禹航， 丁睿， 等. 我国空间互联网星座系统发展战略研究［J］. 中国工程科学， 2021， 23（4）： 137-144. |
| LI F， YU H， DING R， et al. Development strategy of space Internet constellation system in China［J］. Strategic Study of CAE， 2021， 23（4）： 137-144 （in Chinese）. | |
| 2 | 赵键， 杨芳. 中国高分辨率敏捷小卫星的技术创新及应用实践［J］. 航天器工程， 2021， 30（6）： 23-30. |
| ZHAO J， YANG F. Technical innovation and application of Chinese agile small satellites［J］. Spacecraft Engineering， 2021， 30（6）： 23-30 （in Chinese）. | |
| 3 | 杨元喜， 任夏， 王建荣. 集成型与智能型测绘卫星工程发展及其关键技术［J］. 测绘学报， 2022， 51（6）： 854-861. |
| YANG Y X， REN X， WANG J R. Development of integrated and intelligent surveying and mapping satellite project with corresponding key technology［J］. Acta Geodaetica et Cartographica Sinica， 2022， 51（6）： 854-861. | |
| 4 | 方芳， 吴明阁. “星链”低轨星座的主要发展动向及分析［J］. 中国电子科学研究院学报， 2021， 16（9）： 933-936. |
| FANG F， WU M G. Development trend and analysis of “Starlink” LEO Satellites Constellation［J］. Journal of China Academy of Electronics and Information Technology， 2021， 16（9）： 933-936 （in Chinese）. | |
| 5 | 康国栋， 张楠， 王崇， 等. 面向大规模星座的多波束测控天线及应用［J］. 空间电子技术， 2021， 18（2）： 72-78. |
| KANG G D， ZHANG N， WANG C， et al. Multiple-beam TT & C antenna and its application for large scale satellite constellation［J］. Space Electronic Technology， 2021， 18（2）： 72-78 （in Chinese）. | |
| 6 | 安元元， 李伟超， 王伟， 等. 一种低轨卫星星座测控地面站调度策略研究［J］. 时间频率学报， 2021， 44（2）： 120-131. |
| AN Y Y， LI W C， WANG W， et al. Research on schedule strategy of ground stations for LEO satellites［J］. Journal of Time and Frequency， 2021， 44（2）： 120-131 （in Chinese）. | |
| 7 | 王伟， 王钦钊， 刘钢锋， 等. 地面无人系统反制研究及关键技术分析与综述［J］. 航空学报， 2022， 43（7）： 025489. |
| WANG W， WANG Q Z， LIU G F， et al. Research on countering unmanned ground system and analysis and review of key technology［J］. Acta Aeronautica et Astronautica Sinica， 2022， 43（7）： 025489 （in Chinese）. | |
| 8 | MARINELLI F， NOCELLA S， ROSSI F， et al. A Lagrangian heuristic for satellite range scheduling with resource constraints［J］. Computers & Operations Research， 2011， 38（11）： 1572-1583. |
| 9 | 康宁， 武小悦. 基于拉格朗日松弛的航天测控调度上界求解算法［J］. 国防科技大学学报， 2011， 33（3）： 38-43. |
| KANG N， WU X Y. TT & C scheduling upper bound solution algorithm based on Lagrangian relaxation［J］. Journal of National University of Defense Technology， 2011， 33（3）： 38-43 （in Chinese）. | |
| 10 | 刘建平， 李晶， 张天骄. 航天测控网调度的混合构造启发式算法［J］. 系统工程与电子技术， 2015， 37（7）： 1569-1574. |
| LIU J P， LI J， ZHANG T J. Hybrid constructive heuristics of space measurement and control network scheduling problem［J］. Systems Engineering and Electronics， 2015， 37（7）： 1569-1574 （in Chinese）. | |
| 11 | 辛立强， 张超， 赵灵芝， 等. 面向复杂关联测控需求的冲突规避调度算法［J］. 系统工程与电子技术， 2022， 44（5）： 1581-1588. |
| XIN L Q， ZHANG C， ZHAO L Z， et al. Conflict avoidance scheduling algorithm for complex associated TT & C requirements［J］. Systems Engineering and Electronics， 2022， 44（5）： 1581-1588 （in Chinese）. | |
| 12 | ZHANG Z J， ZHANG N， FENG Z R. Multi-satellite control resource scheduling based on ant colony optimization［J］. Expert Systems With Applications， 2014， 41（6）： 2816-2823. |
| 13 | CHEN M， WEN J， SONG Y J， et al. A population perturbation and elimination strategy based genetic algorithm for multi-satellite TT&C scheduling problem［J］. Swarm and Evolutionary Computation， 2021， 65： 100912. |
| 14 | 李玉庆， 王日新， 徐敏强， 等. 基于改进遗传算法的一类多资源测控调度问题研究［J］. 宇航学报， 2012， 33（1）： 85-90. |
| LI Y Q， WANG R X， XU M Q， et al. An improved genetic algorithm for a class of multi-resource range scheduling problem［J］. Journal of Astronautics， 2012， 33（1）： 85-90 （in Chinese）. | |
| 15 | 薛乃阳， 丁丹， 王红敏， 等. 基于改进遗传算法的多类测控资源调度方法［J］. 系统工程与电子技术， 2021， 43（9）： 2535-2543. |
| XUE N Y， DING D， WANG H M， et al. Multi-type TT & C resource scheduling method based on improved genetic algorithm［J］. Systems Engineering and Electronics， 2021， 43（9）： 2535-2543 （in Chinese）. | |
| 16 | STOTTLER R， RICHARDS R. Managed intelligent deconfliction and scheduling for satellite communication［C］∥2018 IEEE Aerospace Conference. Piscataway： IEEE Press， 2018： 1-7. |
| 17 | BARBULESCU L， WATSON J P， WHITLEY L D， et al. Scheduling space–ground communications for the air force satellite control network［J］. Journal of Scheduling， 2004， 7（1）： 7-34. |
| 18 | XHAFA F， HERRERO X， BAROLLI A， et al. Evaluation of struggle strategy in Genetic Algorithms for ground stations scheduling problem［J］. Journal of Computer and System Sciences， 2013， 79（7）： 1086-1100. |
| 19 | VAZQUEZ R， PEREA F， GALáN VIOQUE J. Resolution of an antenna-satellite assignment problem by means of iteger linear programming［J］. Aerospace Science and Technology， 2014， 39： 567-574. |
| 20 | SARKHEYLI A， BAGHERI A， GHORBANI-VAGHEI B， et al. Using an effective tabu search in interactive resources scheduling problem for LEO satellites missions［J］. Aerospace Science and Technology， 2013， 29（1）： 287-295. |
| 21 | SONG Y J， ZHANG Z S， SONG B Y， et al. Improved genetic algorithm with local search for satellite range scheduling system and its application in environmental monitoring［J］. Sustainable Computing： Informatics and Systems， 2019， 21： 19-27. |
| 22 | 凌晓冬， 武小悦， 刘冰， 等. 卫星测控资源调度CSP模型研究［J］. 系统工程与电子技术， 2012， 34（11）： 2275-2279. |
| LING X D， WU X Y， LIU B， et al. Study on the CSP model of satellite TT & C resource scheduling［J］. Systems Engineering and Electronics， 2012， 34（11）： 2275-2279 （in Chinese）. | |
| 23 | 陈峰， 武小悦. 天地测控资源调度的两阶段递进遗传算法［J］. 国防科技大学学报， 2010， 32（2）： 17-22. |
| CHEN F， WU X Y. Two-stage successive genetic algorithm for space and ground TT & C scheduling［J］. Journal of National University of Defense Technology， 2010， 32（2）： 17-22 （in Chinese）. | |
| 24 | 陈峰， 武小悦. 多星测控调度的遗传算法分析［J］. 北京航空航天大学学报， 2010， 36（5）： 534-539. |
| CHEN F， WU X Y. Genetic algorithm analysis for multi-satellite TT & C scheduling［J］. Journal of Beijing University of Aeronautics and Astronautics， 2010， 36（5）： 534-539 （in Chinese）. | |
| 25 | 宋彦杰， 王沛， 张忠山， 等. 面向多星任务规划问题的改进遗传算法［J］. 控制理论与应用， 2019， 36（9）： 1391-1397. |
| SONG Y J， WANG P， ZHANG Z S， et al. An improved genetic algorithm for multi-satellite mission planning problem［J］. Control Theory & Applications， 2019， 36（9）： 1391-1397 （in Chinese）. | |
| 26 | 赵啸宇. 多星测控资源调度模型和算法研究［D］. 长沙： 国防科技大学， 2019. |
| ZHAO X Y. Research on multi-satellite TT&C resource scheduling models and algorithms［D］. Changsha： National University of Defense Technology， 2019 （in Chinese）. | |
| 27 | 鄢青青， 沈怀荣， 邵琼玲. 航天测控资源调度问题建模与求解研究综述［J］. 系统仿真学报， 2015， 27（1）： 1-12， 36. |
| YAN Q Q， SHEN H R， SHAO Q L. Research overview on modeling and solution of aerospace TT & C scheduling problem［J］. Journal of System Simulation， 2015， 27（1）： 1-12， 36 （in Chinese）. | |
| 28 | VAZQUEZ A J， ERWIN R S. On the tractability of satellite range scheduling［J］.Optimization Letters， 2015， 9（2）： 311-327. |
| 29 | 孙刚， 彭双， 陈浩， 等. 面向测控数传资源一体化场景的卫星地面站资源多目标优化方法［J］. 航空学报， 2022： 43（9）： 326114. |
| SUN G， PENG S， CHEN H， et al. Multi-objective optimization method oriented to integrated scenario of TT&C resources and data transmission resources［J］. Acta Aeronautica et Astronautica Sinica， 2022： 43（9）： 326114 （in Chinese）. | |
| 30 | SMITH D E. Choosing objectives in over-subscription planning［C］∥International conference of automated planning and scheduling， 2004： 393. |
| 31 | 孙刚， 陈浩， 彭双， 等. 一种基于偏好MOEA的卫星地面站资源多目标优化算法［J］. 航空学报， 2021， 42（4）： 524475. |
| SUN G， CHEN H， PENG S， et al. Multi-objective optimization algorithm for satellite range scheduling based on preference MOEA［J］. Acta Aeronautica et Astronautica Sinica， 2021， 42（4）： 524475 （in Chinese）. | |
| 32 | 白保存， 贺仁杰， 李菊芳， 等. 考虑任务合成的成像卫星调度问题［J］. 航空学报， 2009， 30（11）： 2165-2171. |
| BAI B C， HE R J， LI J F， et al. Imaging satellite observation scheduling with task merging［J］. Acta Aeronautica et Astronautica Sinica， 2009， 30（11）： 2165-2171 （in Chinese）. | |
| 33 | XHAFA F， HERRERO X， BAROLLI A， et al. A simulated annealing algorithm for ground station scheduling problem［C］∥2013 16th International Conference on Network-Based Information Systems. Piscataway： IEEE Press， 2013： 24-30. |
| 34 | 王慧林， 伍国华， 马满好. 多类异构对地观测平台协同任务规划方法［J］. 航空学报， 2016， 37（3）： 997-1014. |
| WANG H L， WU G H， MA M H. Coordinated task planning method of multiple heterogeneous Earth-observation platforms［J］. Acta Aeronautica et Astronautica Sinica， 2016， 37（3）： 997-1014 （in Chinese）. | |
| 35 | 李夏苗， 廖文昆， 伍国华， 等. 基于两阶段迭代优化的空天观测资源协同任务规划方法［J］. 控制与决策， 2021， 36（5）： 1147-1156. |
| LI X M， LIAO W K， WU G H， et al. A two-stage iterative optimazation method for the coordinated task planning of space and air observation resources［J］. Control and Decision， 2021， 36（5）： 1147-1156 （in Chinese）. | |
| 36 | 李夏苗， 陈新江， 伍国华， 等. 考虑断点续传的中继卫星调度模型及启发式算法［J］. 航空学报， 2019， 40（11）： 323233. |
| LI X M， CHEN X J， WU G H， et al. Scheduling model and heuristic algorithm for tracking and data relay satellite considering breakpoint transmission［J］. Acta Aeronautica et Astronautica Sinica， 2019， 40（11）： 323233 （in Chinese）. | |
| 37 | CHEN X J， LI X M， WANG X W， et al. Task scheduling method for data relay satellite network considering breakpoint transmission［J］. IEEE Transactions on Vehicular Technology， 2021， 70（1）： 844-857. |
| 38 | WU G H， WANG H L， PEDRYCZ W， et al. Satellite observation scheduling with a novel adaptive simulated annealing algorithm and a dynamic task clustering strategy［J］. Computers & Industrial Engineering， 2017， 113： 576-588. |
/
| 〈 |
|
〉 |
CJA