面向预警场景的大规模星座协同调度标准建模与求解方法
收稿日期: 2024-01-18
修回日期: 2024-02-29
录用日期: 2024-04-10
网络出版日期: 2024-04-19
基金资助
国家自然科学基金航天领域企业创新发展联合重点基金(U23B2025)
Standard modeling and solving methods for large-scale constellation collaborative scheduling for early warning scenarios
Received date: 2024-01-18
Revised date: 2024-02-29
Accepted date: 2024-04-10
Online published: 2024-04-19
Supported by
Joint Key Fund for Innovation and Development of Aerospace Enterprises in the National Natural Science Foundation of China(U23B2025)
针对大规模星座任务协同调度具有卫星节点数量多、任务需求规模大、资源使用约束条件复杂，对多节点间协同调度的建模和求解要求较高等特点，设计了一种“任务预处理—统一化建模—规范优化求解—在轨指令生成”的阶段式统一化建模与求解顶层框架，在此顶层框架之下提出了一种基于改进合同网的多节点即时协同调度算法（CSA-ICNP），利用模糊寻优结合局部搜索策略提高算法的整体寻优能力。通过开展大量仿真实验，与随机搜索算法、贪婪搜索算法、基于冲突度的任务分配算法、最小负载最先分配算法和基于改进合同网协议的分布式卫星资源调度算法进行结果对比和性能分析，每个实验用例都获得了最佳目标函数值，平均提升了42.13%、41.51%、37.93%、37.53%和18.57%。
李宗凌 , 龙腾 , 赵保军 , 王天宇 , 伍国华 . 面向预警场景的大规模星座协同调度标准建模与求解方法[J]. 航空学报, 2024 , 45(22) : 330181 -330181 . DOI: 10.7527/S1000-6893.2024.30181
Large-scale constellation coordination scheduling is characterized by a large number of remote satellite nodes， large task demands， complex resource utilization constraints， and high requirements for modeling and solving collaborative scheduling between multiple nodes. This paper proposes a top-level framework for phased unified modeling and solving， which includes “task pre-processing， unified modeling， optimization solving， on-orbit instruction generation”. Under the top-level framework， a multi node real-time Collaborative Scheduling Algorithm based on the Improved Contract Network （CSA-ICNP） is proposed for space-based early warning application scenarios， which utilizes fuzzy optimization combined with the local search strategy to improve the overall optimization ability of the algorithm. The correctness and effectiveness of the proposed algorithm are verified by conducting a large number of simulation experiments. Comparison of the method proposed with Random Search algorithm（RS），Greedy Search algorithm（GS），Task Allocation Algorithm based on Conflict Degree （TAACD），Minimum Load First Allocation algorithm （MLFA） and Distributed Satellite Resource Scheduling based on Improved Contract Network Protocol （DSRS-ICNP） shows that each experimental case achieves the optimal objective function value， with an average improvement of 42.13%， 41.51%， 37.93%， 37.53% and 18.57%， respectively.
| 1 | 李宗凌， 宋桂萍， 汪路元， 等. 巨型星座高效管理与智能应用关键技术研究［J］. 航天器工程， 2023， 32（1）： 1-7. |
| LI Z L， SONG G P， WANG L Y， et al. Research on Key Technologies of High efficiency management and intelligent application for mega-constellation［J］. Spacecraft Engineering， 2023， 32（1）： 1-7 （in Chinese）. | |
| 2 | 王朝辉， 徐瑞， 李朝玉， 等. 加权负载均衡合同网大规模星座任务分配方法［J］. 航天控制， 2023， 41（4）： 59-66. |
| WANG Z H， XU R， LI C Y， et al. Large-scale constellation task allocation method through weighted load balancing contract network［J］. Aerospace Control， 2023， 41（4）： 59-66 （in Chinese）. | |
| 3 | 张逢贵， 李舒薇， 杨学海， 等. 星地系统中的站网资源优化调度综述与展望［J］. 系统仿真技术， 2023， 19（3）： 283-292. |
| ZHANG F G， LI S W， YANG X H， et al. Optimal scheduling of ground station network resources in satellite-ground systems： Overview and prospects［J］. System Simulation Technology， 2023， 19（3）： 283-292 （in Chinese）. | |
| 4 | TARTAKOVSKY A G， BROWN J. Adaptive spatial-temporal filtering methods for clutter removal and target tracking［J］. IEEE Transactions on Aerospace and Electronic Systems， 2008， 44（4）： 1522-1537. |
| 5 | HERNANDEZ M L， FARINA A， RISTIC B. PCRLB for tracking in cluttered environments： Measurement sequence conditioning approach［J］. IEEE Transactions on Aerospace and Electronic Systems， 2006， 42（2）： 680-704. |
| 6 | WU G H， LUO Q Z， DU X， et al. Ensemble of metaheuristic and exact algorithm based on the divide-and-conquer framework for multisatellite observation scheduling［J］. IEEE Transactions on Aerospace and Electronic Systems， 2022， 58（5）： 4396-4408. |
| 7 | GOOLEY T D. Automating the satellite range scheduling process［D］. Ohio： Air Force Institute of Technology， 1993：10-17. |
| 8 | GOOLEY T D， BORSI J J， MOORE J T. Automating air force satellite control network （AFSCN） scheduling［J］. Mathematical and Computer Modelling， 1996， 24（2）： 91-101. |
| 9 | HU X X， ZHU W M， AN B， et al. A branch and price algorithm for EOS constellation imaging and downloading integrated scheduling problem［J］. Computers & Operations Research， 2019， 104： 74-89. |
| 10 | 康宁， 武小悦. 基于拉格朗日松弛的航天测控调度上界求解算法［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）. | |
| 11 | 刘建平， 李晶， 张天骄. 航天测控网调度的混合构造启发式算法［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）. | |
| 12 | WU J， YAO F， SONG Y J， et al. Frequent pattern-based parallel search approach for time-dependent agile earth observation satellite scheduling［J］. Information Sciences， 2023， 636： 118924. |
| 13 | VAZQUEZ R， PEREA F， GALáN V J. Resolution of an Antenna-Satellite assignment problem by means of Integer Linear Programming［J］. Aerospace Science and Technology， 2014， 39： 567-574. |
| 14 | 邱涤珊， 张利宁， 祝江汉， 等. 多星任务规划中的FFFS-DTMB与ADTPC-DTMB算法［J］. 航空学报， 2009， 30（11）： 2178-2184. |
| QIU D S， ZHANG L N， ZHU J H， et al. FFFS-DTMB and ADTPC-DTMB algorithmin multi-satellites mission planning［J］. Acta Aeronautica et Astronautica Sinica， 2009， 30（11）： 2178-2184 （in Chinese）. | |
| 15 | 辛立强， 张超， 赵灵芝， 等. 面向复杂关联测控需求的冲突规避调度算法［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）. | |
| 16 | MANSOUR M A A， DESSOUKY M M. A genetic algorithm approach for solving the daily photograph selection problem of the SPOT5 satellite［J］. Computers & Industrial Engineering， 2010， 58（3）： 509-520. |
| 17 | WU G H， LIU J， MA M H， et al. A two-phase scheduling method with the consideration of task clustering for earth observing satellites［J］. Computers & Operations Research， 2013， 40（7）： 1884-1894. |
| 18 | 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. |
| 19 | 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. |
| 20 | 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. |
| 21 | 宋彦杰， 王沛， 张忠山， 等. 面向多星任务规划问题的改进遗传算法［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）. | |
| 22 | 薛乃阳， 丁丹， 王红敏， 等. 基于改进遗传算法的多类测控资源调度方法［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）. | |
| 23 | 伍国华， 王天宇. 基于自适应模拟退火的大规模星座测控资源调度算法［J］. 航空学报， 2023， 44（12）： 327759. |
| WU G H， WANG T Y. Large-scale constellation TT & C resource scheduling algorithm based on adaptive simulated annealing［J］. Acta Aeronautica et Astronautica Sinica， 2023， 44（12）： 327759 （in Chinese）. | |
| 24 | 谢平， 杜永浩， 姚锋， 等. 敏捷成像卫星自主调度技术综述［J］. 宇航学报， 2019， 40（2）： 127-138. |
| XIE P， DU Y H， YAO F， et al. Literature review for autonomous scheduling technology of agile earth observation satellites［J］. Journal of Astronautics， 2019， 40（2）： 127-138 （in Chinese）. | |
| 25 | 杜永浩， 邢立宁， 姚锋， 等.航天器任务调度模型、算法与通用求解技术综述［J］. 自动化学报， 2021， 47（12）： 2715-2741. |
| DU Y H， XING L N， YAO F. Survey on models， algorithms and general techniques for spacecraft mission scheduling［J］. Acta Automatica Sinica， 2021， 47（12）： 2715-2741. （in Chinese）. | |
| 26 | 刘阳， 周笛， 盛敏， 等. 面向巨型星座系统的多地面站协同测控技术［J］. 天地一体化信息网络， 2023， 4（01）： 2-11. |
| LIU Y， ZHOU D， SHEN M， et al. Multi-ground station collaborative measurement and control technology for giant constellation system［J］. Space-Integrated-Ground Information Networks， 2023， 4（01）： 2-11 （in Chinese）. | |
| 27 | LEMA??TRE M， VERFAILLIE G， JOUHAUD F， et al. Selecting and scheduling observations of agile satellites［J］. Aerospace Science and Technology， 2002， 6（5）： 367-381. |
| 28 | KODHELI O， LAGUNAS E， MATURO N， et al. Satellite communications in the new space era： A survey and future challenges［J］. IEEE Communications Surveys & Tutorials， 2021， 23（1）： 70-109. |
| 29 | DEL PORTILLO I， CAMERON B G， CRAWLEY E F. A technical comparison of three low earth orbit satellite constellation systems to provide global broadband［J］. Acta Astronautica， 2019， 159： 123-135. |
| 30 | WANG L， JIANG C X， KUANG L L， et al. Mission scheduling in space network with antenna dynamic setup times［J］. IEEE Transactions on Aerospace and Electronic Systems， 2019， 55（1）： 31-45. |
| 31 | 贺仁杰， 高鹏， 白保存， 等. 成像卫星任务规划模型、算法及其应用［J］. 系统工程理论与实践， 2011， 31（3）： 411-422. |
| HE R J， GAO P， BAI B C， et al. Models， algorithm and applications to the mission planning system of imaging satellites［J］. Systems Engineering Theory and Practice， 2011， 31（3）： 411-422 （in Chinese）. | |
| 32 | 丁冬， 何兵， 余炜， 等. 美国天基导弹预警系统发展及效能仿真研究［J］. 中国电子科学研究院学报， 2022， 17（11）： 1102-1106. |
| DING D， HE B， YU W， et al. Development and effectiveness simulation of American space-based missile early warning system［J］. Journal of China Academy of Electronics and Information Technology， 2022， 17（11）： 1102-1106 （in Chinese）. | |
| 33 | LIU B J， DENG M， WU G H， et al. Bottom-up mechanism and improved contract net protocol for dynamic task planning of heterogeneous earth observation resources［J］. IEEE Transactions on Systems， Man， and Cybernetics： Systems， 2022， 52（10）： 6183-6196. |
| 34 | WOSNIACK M E， RAPOSO E P， VISWANATHAN G M， et al. A parallel algorithm for random searches［J］. Computer Physics Communications， 2015， 196： 390-397. |
| 35 | HIEN V Q， DAO T C， BINH H T T. A greedy search based evolutionary algorithm for electric vehicle routing problem［J］. Applied Intelligence， 2023， 53（3）： 2908-2922. |
| 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 | 李夏苗， 廖文昆， 伍国华， 等. 基于两阶段迭代优化的空天观测资源协同任务规划方法［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）. | |
| 38 | 靳鹏， 李康. 基于改进合同网协议的分布式卫星资源调度［J］. 系统工程与电子技术， 2022， 44（10）： 3164-3173. |
| JIN P， LI K. Distributed satellite resource scheduling based on improved contract network protocol［J］. Systems Engineering and Electronics， 2022， 44（10）： 3164-3173 （in Chinese）. |
/
| 〈 |
|
〉 |
CJA