航天测控资源调度问题建模与求解研究综述

摘要/Abstract

摘要： 航天测控资源调度为测控方案决策和航天测控资源网络建设提供支持,具有重要的研究意义。介绍了航天测控资源调度问题的分类和解决流程。分析了该问题的建模方法及其相关的目标函数设计、约束条件分析、优先级确定等关键技术。归纳了该问题的求解算法和冲突消解方法,对主要算法分类进行了评述。总结了航天测控资源调度效果评价的主要研究内容。综合分析了航天测控资源调度问题的研究发展情况,并结合发展需求,分析了相关技术的研究方向。所做的工作对航天测控资源调度问题研究具有很好的理论参考意义。

关键词: 航天测控, 资源调度, 建模, 优化算法, 研究综述

Abstract: The research of Aerospace TT&C Scheduling (ATT&CS) is very important, because of its support for TT&C scheme decision-making and TT&C resource net constructing. The classification and resolution flow of the ATT&CS problem were introduced. Then, the modeling methods and related key techniques, such as designing of object function, analysis of constraints, and priority determining, were analyzed. The solving algorithms and conflict resolution methods were summed up, and the major categories of algorithm were evaluated. The main content of scheduling evaluation research was summarized. The possible future researches for related techniques were discussed based on the analysis of development and demand of the ATT&CS problem. The work has good theoretical guiding sense to the research of the ATT&CS Problem.

Key words: aerospace TT&C, scheduling, modeling, optimization algorithm, research overview

中图分类号:

V556

鄢青青, 沈怀荣, 邵琼玲. 航天测控资源调度问题建模与求解研究综述[J]. 系统仿真学报, 2015, 27(1): 1-12.

Yan Qingqing, Shen Huairong, Shao Qiongling. Research Overview on Modeling and Solution of Aerospace TT&C Scheduling Problem[J]. Journal of System Simulation, 2015, 27(1): 1-12.

参考文献

[1] Miller James G.A New Sensor Allocation Algorithm for the Space Surveillance Network[J]. Military Operations Research (S1082-5983), 2007, 12(1): 57-70.
[2] 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 (S1099-1425), 2004, 7(1): 7-34.
[3] Marco S, Miro R, Klaus S.A Scheduling System for Small Ground Station Networks[C]// SpaceOps 2008 Conference. Rosten, VA, USA: American Institute of Aeronautics and Astronautics (AIAA), 2008: 1-7.
[4] Barbulescu L, Howe A E, Watson J P, et al. Satellite Range Scheduling: A Comparison of Genetic, Heuristic and Local Search[M]// Parallel Problem Solving from Nature—PPSN VII. Germany: Springer Berlin Heidelberg, 2002: 611-620.
[5] Parish D A.A Genetic Algorithm Approach to Automating Satellite Range Scheduling [D]. USA: Air Force Institute of Technology, 1994.
[6] Barbulescu L, Howe A, Whitley D.AFSCN Scheduling: How the Problem and Solution Have Evolved[J]. Mathematical and Computer Modelling (S0895-7177), 2006, 43(9): 1023-1037.
[7] Chien S, Lam R, Quoc V.Resource Scheduling for a Network of Communications Antennas[C]// 1997 IEEE Aerospace Conference, Co, USA, Feb 1-8, 1997. USA: IEEE, 1997.
[8] Chien S, Govindjee A, Estlin T.Automated Generation of Tracking Plans for a Network of Communications Antennas[C]// 1997 IEEE Aerospace Conference, Co, USA, Feb 1-8, 1997. USA: IEEE, 1997.
[9] 杜红梅, 刘明盛. 基于多智能体协作技术的卫星测控资源动态调度问题解算[J]. 装备指挥技术学院学报, 2010, 21(3): 76-80.
[10] 刘聪锋. 测控资源调度管理系统的构造与实现[J]. 航空计算技术, 2005, 35(3): 68-71.
[11] 闫华, 武小悦. 卫星数传应急任务调度模型[J]. 计算机工程, 2012, 37(10): 31-33, 37.
[12] 刘聪锋, 杨洁. 陆基测控资源分配决策支持系统研究[J]. 航空计算技术, 2003, 33(4): 80-83.
[13] 李力昊, 石纯一. 卫星测控站多任务决策支持系统设计[C]// 2006年航天测控技术研讨会. 北京: 中国宇航学会飞行器测控专业委员会, 2006: 61-67.
[14] Arbabi M, Pfeifer M.Range and Mission Scheduling Automation Using Combined AI and Operations Research Techniques[C]// First Annual Workshop on Space Operations Automation and Robotics, Lyndon B, Johnson Space Center, Houston, Texas, USA: NASA, 1987: 315-320.
[15] Gooley T D.Automating the Satellite Range Scheduling Process [D]. USA: Air Force Institute of Technology, 1993.
[16] Marinelli F, Nocella S, Rossi F.A Lagrangian Heuristic for Satellite Range Scheduling with Resource Constraints[J]. Computers & Operations Research (S0305-0548), 2011, 38(11): 1572-1583.
[17] Spangelo S, Cutler J.Optimization of Single-Satellite Operational Schedules Towards Enhanced Communication Capacity[C]// AIAA Guidance, Navigation, and Control Conference, 2012. USA: AIAA, 2012.
[18] Charles H L, Cheung Kar-Ming.Mixed Integer Programming & Heuristic Scheduling for Space Communication Networks[C]// 2012 IEEE Aerospace Conference, Big Sky, MT, USA, Mar 3-10, 2012. USA: IEEE, 2012.
[19] 金光, 武小悦, 高卫斌. 卫星地面站资源调度优化模型及启发式算法[J]. 系统工程与电子技术, 2004, 26(12): 1839-1841, 1875.
[20] 郑晋军, 张乃通, 张丽艳. 合理利用测控资源的动态调度模型[J]. 高技术通信, 2002, 12(7): 22-27.
[21] 张娜, 柯良军, 冯祖仁. 一种新的卫星测控资源调度模型及其求解算法[J]. 宇航学报, 2009, 30(5): 2140-2145.
[22] 陈祥国, 武小悦. 卫星数传资源负荷均衡调度模型及蚁群优化算法[J]. 系统工程, 2008, 26(12): 91-97.
[23] 王海波, 徐敏强, 王日新, 等. 基于蚁群优化-模拟退火的天地测控资源联合调度[J]. 宇航学报, 2012, 33(11): 1636-1645.
[24] 张雁, 党群, 黄永宣. 带预估选择的Memetic算法求解多星测控资源调度问题[J]. 西安交通大学学报, 2009, 43(10): 37-41.
[25] 王远振, 赵坚, 聂成. 多卫星-地面站系统的Petri网模型研究[J]. 空军工程大学学报, 2003, 4(2): 7-11.
[26] 王远振, 赵坚, 聂成. 多星地面站设备优化调度方法研究[J]. 计算机仿真, 2003, 20(7): 7-19, 54.
[27] 金光, 武小悦, 高卫斌. 卫星地面站资源配置仿真研究[J]. 系统仿真学报, 2004, 16(11): 2401-2403.
(JIN Guang, WU Xiao-yue, GAO Wei-Bin.Simulation-based Study on Resource Deployment of Satellite Ground Station[J]. Journal of System Simulation, 2004, 16(11): 2401-2403.)
[28] 王远振, 高卫斌, 聂成. 多星地面站系统资源配置优化研究综述[J]. 系统工程与电子技术, 2004, 26(4): 437-439, 453.
[29] 贺仁杰, 谭跃进. 基于约束满足的卫星地面站资源优化分配问题研究[J]. 计算机工程与应用, 2004, 18(6): 229-232.
[30] Damiani S, Dreihahn H, Noll J, et al. Automated Allocation of Esa Ground Station Network Services[C]// The 5th International Workshop on Planning and Scheduling for Space. Carol, Hamilton, USA: American Association for Artificial Intelligence (AAAI), 2006: 1-10.
[31] 朱臻, 高永明. 地面测控任务规划调度的时间窗口约束研究[J]. 软件, 2012, 33(6): 32-34.
[32] 金光. 卫星地面站测控资源调度CSP模型[J]. 系统工程与电子技术, 2007, 29(7): 1117-1120.
[33] 凌晓冬, 武小悦, 刘琦. 基于Agent的航天测控资源调度问题建模分析[J]. 系统工程与电子技术, 2008, 30(11): 2220-2223.
[34] 杜世勇, 胡进, 贾丽娟, 等. 基于多活性代理的多星测控调度方法[J]. 飞行器测控学报, 2012, 31(5): 11-14.
[35] Jian BAI, Zu-ren FENG, Jing LI, et al. A MAS Model for Spacecraft TT&C Resources Scheduling[C]// 2010 International Conference on Artificial Intelligence and Computational Intelligence. Piscataway, New Jersey, USA: Institute of Electrical and Electronics Engineers (IEEE), 2010: 167-171.
[36] 凌晓冬, 刘冰, 武小悦, 等. 基于本体的多星测控调度问题模型研究[J]. 计算机与数字工程, 2010, 38(8): 62-66.
[37] 冯宏胜, 陈杨, 武小悦. 卫星地面站资源配置的SVM回归模型[J]. 飞行器测控学报, 2011, 30(2): 15-19.
[38] 唐国金, 罗亚中, 张进. 空间交会对接任务规划 [M].北京: 科学出版社, 2008: 101-102.
[39] Johnston M D.Deep Space Network Scheduling Using Multi-Objective Optimization with Uncertainty[C]// Space OPS 2008 Conference. Rosten, VA, USA: American Institute of Aeronautics and Astronautics (AIAA), 2008: 1-8.
[40] 卜慧蛟. 多星地面站测控调度多目标优化研究 [D]. 长沙: 国防科学技术大学, 2011.
[41] 辛维政, 董光亮, 李济生, 等. 多星测控调度问题的建模与仿真[C]// 2008系统仿真技术及其应用学术会议. 北京: 中国系统仿真学会仿真技术应用专业委员会, 2008: 468-471.
[42] 白剑, 蒋卫军, 李晶. 地基测控网资源分配算法的设计与实现[J]. 宇航动力学学报, 2011, 1(1): 98-102, 122.
[43] 康宁, 武小悦. 基于任务开始时刻的天地基测控资源调度模型[J]. 装备指挥技术学院学报, 2011, 22(6): 97-101.
[44] 吴云鹤. 测控弧段优先级的确定及量化[J]. 飞行器测控学报, 2001, 20(4): 16-22.
[45] 李云峰, 武小悦. 基于综合优先度的卫星数传调度算法[J]. 系统工程学报, 2007, 22(6): 645-648.
[46] 凌晓冬, 武小悦, 刘琦. 多星测控调度问题任务优先级研究[J]. 数学的实践与认识, 2008, 38(23): 114-120.
[47] 冉承新, 王慧林, 熊纲要. 航天测控资源优先级设计分析[J]. 中国空间科学技术, 2009 (3): 78-83.
[48] 廖琼. 卫星数传调度优化算法及可视化仿真技术研究[D]. 合肥: 中国科学技术大学, 2010.
[49] 王沛. 基于分支定价的多星多站集成调度方法研究 [D]. 长沙: 国防科学技术大学, 2011.
[50] 康宁. 航天测控优化调度模型及其拉格朗日松弛求解算法 [D]. 长沙: 国防科学技术大学, 2011.
[51] 陈世福, 陈兆乾, 等. 人工智能与知识工程 [M]. 南京: 南京大学出版社, 1997, 12: 165-167.
[52] Schalck S.M. Automating Satellite Range Scheduling [D]. USA: Air Force Institute of Technology, 1993.
[53] Jang K.The Capacity of The Air Force Satellite Control Network [D]. USA: Air Force Institute of Technology, 1996.
[54] Clement B J, Johnston M D.The Deep Space Network Scheduling Problem[C]// 20^th National Conference on Artificial Intelligence. Carol, Hamilton, USA: Association for the Advancement of Artificial Intelligence (AAAI), 2005, 20(3): 1514-1520.
[55] 唐枚, 李济生. 近地航天器测控设备分配策略[J]. 宇航计测技术, 2001, 21(2): 51-54.
[56] 李云峰, 武小悦. 基于多星联合侦察的卫星数传调度问题模型[J]. 北京航空航天大学学报, 2004, 34(8): 948-951, 960.
[57] 陈理江, 武小悦, 李云峰. 基于时间灵活度的中继卫星调度算法[J]. 航空计算技术, 2006, 36(4): 48-51.
[58] 谷宏志. 基于启发式算法的卫星地面资源调度系统设计与实现 [D]. 西安: 西安电子科技大学, 2007.
[59] 刘洋, 陈英武, 谭跃. 基于贪婪算法的卫星地面站任务规划方法[J]. 系统工程与电子技术, 2003, 25(10): 1239-1241.
[60] Zufferey N, Amstutz P, Giaccari P.Graph Colouring Approaches for a Satellite Range Scheduling Problem[J]. Journal of Scheduling (S1099-1425), 2008, 11(4): 263-277.
[61] Soma P, Venkateswarlu S, Santhalakshmi S, et al. Multi-satellite Scheduling Using Genetic Algorithms[C]// Space OPS 2004 Conference. Rosten, VA, USA: American Institute of Aeronautics and Astronautics (AIAA), 2004: 1-10.
[62] Bagchi T P.Near Optimal Ground Support in Multi- Spacecraft Missions: a GA Model and Its Results[J]. IEEE Transactions on Aerospace and Electronic Systems (S0018-9251), 2009, 45(3): 950-964.
[63] Corrao G, Falone R, Gambi E, et al. Ground Station Activity Planning Through a Multi-Algorithm Optimisation Approach[C]// 2012 IEEE First AESS European Conference on Satellite Telecommunications (ESTEL). USA: IEEE, 2012: 1-6.
[64] 李元新, 吴斌. 基于遗传算法的测站资源优化分配方法研究[J].飞行器测控学报, 2005, 24(4): 1-5.
[65] Zheng Wei, Meng Xin, He Huan.Genetic Algorithm for TDRS Communication Scheduling with Resource Constraints[C]// Computer Science and Software Engineering, 2008 International Conference on. IEEE. Piscataway, NEW JERSEY, USA: Institute of Electrical and Electronics Engineers (IEEE), 2008, 3: 893-897.
[66] 李云峰, 武小悦. 遗传算法在卫星数传调度问题中的应用[J]. 系统工程理论与实践, 2008, 28(1): 124-131.
[67] 凌晓冬. 多星测控调度问题建模及算法研究 [D]. 长沙: 国防科学技术大学, 2009.
[68] 张冰. 航天测控网资源分配策略研究 [D]. 沈阳: 沈阳航空工业学院, 2010.
[69] 李玉庆, 王日新, 徐敏强, 等. 基于改进遗传算法的一类多资源测控调度问题研究[J]. 宇航学报, 2012, 33(1): 85-90.
[70] 陈峰, 武小悦. 基于协同进化的航天测控资源优化调度[J]. 系统工程与电子技术, 2009, 31(11): 2672-2676.
[71] 侯翠琴, 焦李成. 基于面向任务模型的陆基卫星测控资源克隆选择优化调度[J]. 计算机学报, 2009, 32(8): 1525-1535.
[72] 常飞, 武小悦. 基于改进粒子群算法的卫星数传任务调度[J]. 系统工程与电子技术, 2009, 31(10): 2404-2408.
[73] Zhang Na, Feng Zu-Ren, Feng Yuan-jing.An Optimization Model for Multisatellite Resources Scheduling[C]// Intelligent Control and Automation, 2006. WCICA 2006. The Sixth World Congress on. IEEE. Piscataway, NEW JERSEY, USA: Institute of Electrical and Electronics Engineers (IEEE), 2006, 2: 7400-7404.
[74] 邢立宁, 陈英武. 基于混合蚁群优化的卫星地面站系统任务调度方法[J]. 自动化学报, 2008, 34(4): 414-418.
[75] Preindl B, Seidl M, Mehnen L, ,et al. A Performance Comparison of Different Satellite Range Scheduling Algorithms for Global Ground Station Networks[C] //International Astronautical Congress. A Performance Comparison of Different Satellite Range Scheduling Algorithms for Global Ground Station Networks[C] //International Astronautical Congress, 61ST2010. Paris, France: International Astronautical Federation (IAF), 2010: B4.7.1.1-11.
[76] Wolpert D H, Macready W G.No Free Lunch Theorems for Optimization[J]. IEEE Transactions on Evolutionary Computation (S1063-6560), 1997, 1(1): 67-82.
[77] 金光, 武小悦, 高卫斌. 基于冲突的卫星地面站系统资源调度与能力分析[J]. 小型微型计算机系统, 2007, 28(2): 310-312.
[78] 杨萍, 杨锋, 吴斌, 等. 用启发式算法和基于冲突的回跳算法求解卫星测控资源调度问题[J]. 宇航学报, 2007, 28(6): 1609-1613.
[79] 翟政安, 唐朝京. 航天测控网资源均衡分配的调度方法[J]. 中国空间科学技术, 2006, 26(4): 55-60.
[80] 李云峰, 凌晓冬, 武小悦. 调度问题中的冲突研究[J]. 网络与信息技术, 2007, 26(6): 41-43.
[81] 王远振, 赵坚, 聂成. 卫星地面站设备配置效能评价指标体系研究[J]. 军事运筹与系统工程, 2003 (1): 59-64.
[82] 李云峰, 武小悦. 地面站系统服务能力评估指标及其计算方法[J]. 系统工程理论与实践, 2008, 28(2): 158-164, 175.
[83] 孟慧馨, 王晋东, 武小悦. 基于RBFNN的卫星地面站系统建模方法[J]. 计算机仿真, 2009, 26(3): 73-76, 94.
[84] 凌晓冬, 刘冰, 李宇波, 等. 多星测控调度效能评价指标体系研究[J]. 数学的实践与认识, 2012, 42(3): 52-60.