基于极大团模型的多星多站测控资源调度方法研究

doi:10.16381/j.cnki.issn1003-207x.2020.0150

中国管理科学 ›› 2023, Vol. 31 ›› Issue (2): 73-83.doi: 10.16381/j.cnki.issn1003-207x.2020.0150

基于极大团模型的多星多站测控资源调度方法研究

胡雪君¹, 王建江², 孙清³, 白剑³, 韩雪³

1.湖南大学工商管理学院，湖南长沙410082； 2.国防科技大学系统工程学院，湖南长沙410073；3.西安卫星测控中心，陕西西安710043

收稿日期:2020-02-04 修回日期:2020-10-15 出版日期:2023-02-20 发布日期:2023-02-28
通讯作者: 王建江（1986-），男（汉族），新疆乌鲁木齐人，国防科技大学系统工程学院副教授，博士，研究方向：卫星资源规划调度、组合优化，Email：jianjiangwang@nudt.edu.cn. E-mail:jianjiangwang@nudt.edu.cn
基金资助:
国家自然科学基金资助项目(71801218,72071075,71701067);湖南省自然科学基金资助项目(2020JJ4672,2019JJ50039);湖南省科技创新计划资助项目(2022RC1241)

Research on TT&C Scheduling Methods of Multi-satellites and Multi-stations Based on Maximal Cliques

HU Xue-jun¹, WANG Jian-jiang², SUN Qing³, BAI Jian³, HAN Xue³

1. Business School, Hunan University, Changsha 410082, China;2. College of Systems Engineering, National University of Defense Technology, Changsha 410073, China;3. China Xi’an Satellite Control Center, Xi'an 710043, China

Received:2020-02-04 Revised:2020-10-15 Online:2023-02-20 Published:2023-02-28
Contact: 王建江 E-mail:jianjiangwang@nudt.edu.cn

摘要/Abstract

摘要： 针对实际应用中大量卫星测控需求不能得到满足这一瓶颈问题，为缓解地面站测控资源有限与不断增长的测控需求数量之间的矛盾，研究多星多站测控调度问题。考虑卫星-地面站可见测控弧段间的冲突及地面测控设备转换时间约束，同时考虑同一测控设备上可能存在多个满足需求的测控弧段，以测控需求是否分配到某一测控弧段为决策变量，建立了多星多站测控调度0-1整数规划模型。针对传统0-1整数规划模型约束众多、规模庞大、难以求解的不足，本文提出了测控弧段区间图描述，基于区间图描述构建了测控调度极大团模型，大幅减少了约束数量，有效提高问题求解效率。为了获取区间图的所有极大团，设计了一个多项式时间(O(nlogn))的极大团获取算法，并从理论上证明了算法的复杂度和最优性。此外，针对存在升降轨特定类型测控数量要求的调度问题，本文对极大团模型进行了拓展，建立了相应的线性整数规划模型。实验结果表明，对于满足实际应用需求的周计划调度问题(测控需求数量≥9000)，极大团模型能够在数分钟内得到单次测控需求调度问题最优解。对于多次测控需求调度问题，拓展的极大团模型也能高效求解，得到问题最优解或近似最优解，满足实际应用需求。相对于目前调度系统实际采用的启发式方法，本文算法能够大幅提高测控任务调度成功率。

关键词: 多星多站测控；调度方法；整数规划；极大团模型；极大团算法；最优性

Abstract: TT&C scheduling of satellites refers to the allocation of limited TT&C resources to satisfy a large number of tracking, telemetry and remote-control requests. With the development of space technology, satellites are widely used in remote sensing, navigation, communication, mapping and other fields. The TT&C demands of satellites are increasing continuously, and the scarce TT&C resources become more and more valuable. In order to alleviate the contradictions between the limited resources of ground stations and the increasing TT&C demands, the multi-satellite and multi-station scheduling problem is studied.

Key words: multi-satellite and multi-station TT&C; scheduling methods; integer programming; maximal cliques; an algorithm for maximal clique enumeration; optimization

中图分类号:

V556
TP391

胡雪君, 王建江, 孙清, 白剑, 韩雪. 基于极大团模型的多星多站测控资源调度方法研究[J]. 中国管理科学, 2023, 31(2): 73-83.

HU Xue-jun, WANG Jian-jiang, SUN Qing, BAI Jian, HAN Xue. Research on TT&C Scheduling Methods of Multi-satellites and Multi-stations Based on Maximal Cliques[J]. Chinese Journal of Management Science, 2023, 31(2): 73-83.

参考文献

［1］ 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.
［2］ Barbulescu L, Howe A E, Whitley L D, et al. Understanding algorithm performance on an oversubscribed scheduling application［J］. Journal of Artificial Intelligence Research, 2006, 27(1): 577-615.
［3］ Li Yuqing, Wang Rixin, Liu Yu, et al. Satellite range scheduling with the priority constraint: an improved genetic algorithm using a station ID encoding method［J］. Chinese Journal of Aeronautics, 2015, 28(3): 789-803.
［4］李玉庆, 王日新, 徐敏强, 等. 基于改进遗传算法的一类多资源测控调度问题研究［J］. 宇航学报, 2012, 33(1): 85-90.Li Yuqing, Wang Rixin, Xu Minqiang, et al. An improved genetic algorithm for a class of multi-resource range scheduling problem［J］. Journal of Astronautics, 2012, 33(1): 85-90.
［5］陈峰.一种基于分散搜索的多星测控调度遗传算法［J］. 计算技术与自动化, 2015, 34(1): 67-72.Chen Feng. A genetic algorithm based on scatter search to multi-satellite TT&C scheduling［J］. Computing Technology and Automation, 2015, 34(1): 67-72.
［6］白剑, 高惠荔, 谷小松, 等. 航天测控资源统一分配的多维遗传算法［J］. 飞行器测控学报, 2017, 36(1): 25-30.Bai Jian, Gao Huili, Gu Xiaosong, et al. A multi-dimensional genetic algorithm for unified scheduling of spacecraft TT&C resources［J］. Journal of Spacecraft TT&C Technology, 2017, 36(1): 25-30.
［7］凌晓冬. 多星测控调度问题建模及算法研究［D］. 长沙：国防科学技术大学, 2009.Ling Xiaodong. Research on multi-satellite TT&C scheduling models and algorithms［D］. Changsha: National University of Defense Technology, 2009.
［8］凌晓冬, 武小悦, 刘琦. 多星测控调度问题的禁忌遗传算法研究［J］. 宇航学报, 2009, 30(5): 2133-2139.Ling Xiaodong, Wu Xiaoyue, Liu Qi. Study of gats algorithm for multi-satellite TT&C scheduling problem［J］. Journal of Astronautics, 2009, 30(5): 2133-2139.
［9］ Zufferey N, Amstutz P, Giaccari P. Graph colouring approaches for a satellite range scheduling problem［J］. Journal of Scheduling, 2008, 11(4): 263-277.
［10］ Zhang Zhaojun, Hu Funian, Zhang Na. Ant colony algorithm for satellite control resource scheduling problem［J］. Applied Intelligence, 2018, 48(10): 3295-3305.
［11］ Zhang Zhaojun, Zhang Na, Feng Zuren. Multi-satellite control resource scheduling based on ant colony optimization［J］. Expert Systems with Applications, 2014, 41(6): 2816-2823.
［12］王海波, 王日新, 徐敏强. 基于蚁群优化-模拟退火的天地测控资源联合调度［J］. 宇航学报, 2012, 33(11): 1636-1645.Wang Haibo, Wang Rixin, Xu Minqiang. Solving space and ground TT&C resources integrated scheduling problem with ant colony optimization-simulated annealing algorithm［J］. Journal of Astronautics, 2012, 33(11): 1636-1645.
［13］刘艳秋, 徐世达, 张颖,等. 考虑路径可行性与仓储集货模式下的回收车辆路径问题研究［J］. 中国管理科学, 2016, 24(12): 98-107.Liu Yanqiu, Xu Shida, Zhang Ying, et al. Research on recycling path optimization problem with feasibility of path and concentrated treatment mode［J］. Chinese Journal of Management Science, 2016, 24(12): 98-107.
［14］康宁, 武小悦. 航天测控调度模型及其上界求解算法［J］. 系统工程理论与实践, 2010, 30(9): 1695-1700.Kang Ning, Wu Xiaoyue. TT&C scheduling model and upper bound solution algorithm［J］. Systems Engineering-Theory & Practice, 2010, 30(9): 1695-1700.
［15］康宁. 航天测控优化调度模型及其拉格朗日松弛求解算法［D］. 长沙：国防科学技术大学, 2011.Kang Ning. TT&C scheduling upper bound solution algorithm based on Lagrangian relaxation［D］. Changsha: National University of Defense Technology, 2011.
［16］ 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.
［17］康宁, 武小悦. 航天测控调度分枝定界算法［J］. 计算机工程与应用, 2011, 47(31): 17-19.Kang Ning, Wu Xiaoyue. Branch and bound algorithm for TT&C scheduling［J］. Computer Engineering and Applications, 2011, 47(31): 17-19.
［18］彭春, 李金林, 王珊珊,等. 多类应急资源配置的鲁棒选址-路径优化［J］. 中国管理科学, 2017, 25(6): 143-150.Peng Chun, Li Jinlin, Wang Shanshan, et al. Multiple relief resources robust location-routing optimization［J］. Chinese Journal of Management Science, 2017, 25(6): 143-150.
［19］苏志雄, 魏汉英, 涂远芬. 资源受限下平行工序顺序对优化的0-1规划模型［J］. 中国管理科学, 2019, 27(8): 208-216.Su Zhixiong, Wei Hanying, Tu Yuanfen. 0-1 formulation model for optimization of pairing parallel activities under resource constrained［J］. Chinese Journal of Management Science, 2019, 27(8): 208-216.
［20］陈峰. 多星测控调度问题的遗传算法研究［D］. 长沙：国防科学技术大学, 2010.Chen Feng. Research on genetic algorithm for multi-satellite TT&C scheduling problem［D］. Changsha: National University of Defense Technology, 2010.
［21］ Ma Shaohan, Wallis W D. Maximal-clique partitions of interval graphs［J］. Journal of the Australian Mathematical Society, 1988, 45(2): 227-232.
［22］ Habib M, Mcconnell R, Paul C, et al. Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing［J］. Theoretical Computer Science, 2000, 234(1-2): 59-84.

基于极大团模型的多星多站测控资源调度方法研究

Research on TT&C Scheduling Methods of Multi-satellites and Multi-stations Based on Maximal Cliques

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 0

Metrics

本文评价

推荐阅读 10