卫星数传调度优化算法及可视化仿真技术研究
|
摘要
随着我国航天技术的不断发展,越来越多的军用、民用卫星发射升空,这些卫星在我国的国防事业中和国民经济发展过程中发挥极其重大的作用。为了适应卫星越来越多、测控服务地面站相对较少的情况,以及更好地实现卫星所设计的任务,必须对卫星的运行进行统筹兼顾地管理和控制。卫星数传调度的目的是在多星多地面站的情况下,综合考虑各项约束,合理地分配卫星及地面站测控资源,大幅提高地面站资源的使用效率,最大限度地满足卫星数传需求。
本文分析了卫星的工作流程,详细研究了卫星地面站数传过程及其约束条件。介绍了生产调度中调度问题的三元组表示方法及实用的优化调度算法。研究了卫星数传调度的时间索引{0、1}线性规划模型,并根据拉格朗日松弛的思想提出了拉格朗日启发式及算法。研究了卫星数传调度的单地面站模型,并提出了分支定界求解算法。研究了数传调度问题的树形问题表示方法,对于每个地面站的数传任务建立了时间分类算法及直接提取算法。研究了数传调度问题的稀疏矩阵表示方法,结合任务分类提出了一种能快速求解可行解的启发式。
本文设计并实现了一个卫星数传调度仿真系统。该系统集成了卫星仿真工具STK(Satellite Tool Kit)进行轨道预报及卫星地面站可见时间窗口的计算。设计了一个随机问题产生器用于产生随机的数传任务。为了方便调度结果的显示以及人工调整调度结果,提出问题的循环树形表示方式,在此基础上结合界面库Xtreme Toolkit Pro实现简洁的操作界面。
As the constant improving of aviation technology in our country, more and more civil and military satellites are launched into space. In order to adapt to the situation of many satellites few ground stations, and in order to accomplish the specially designed satellite tasks, we must make management and control decisions in a whole perspective of satellite system. The purpose of scheduling satellite data transmission is that under the situation of many satellites few ground stations, we can reasonably schedule ground station’s measure and control resources, largely increase the ground station’s using efficiency, fulfill as many as satellite data transmission demands.
In this paper we analyze satellite’s working procedure, and study the detail procedure of satellite and ground station’s data transmission process and its constraints condition. Introduce the triple annotation used in product scheduling and common optimal methods in constraints satisfying problem. Propose a time-indexed {0,1} linear programming model and Lagrange relaxation algorithm. Study the single station model of satellite ground station’s data transmission problem, propose a branch and bound mode and algorithm. Study the tree representation method of satellite ground station data transmission problem, for each ground station applied the time classify algorithm and direct extraction algorithm. Study the sparse matrix representation method for satellite ground station data transmission problem, combing task classifying method we proposes a heuristic method able to derive a feasible solution quickly.
In this paper, we design and implement a satellite data transmission simulation system. It integrates the STK(Satellite Tool Kit) software used to predicting satellite orbit information and calculating satellite and ground station’s visibility window. We design a random task generator. In order to beautifully display scheduling result and to provide a method to modify scheduling result, we propose a circular linked tree denotation. Base on its denotation and the third interface library Xtreme Toolkit Pro, we implement a concision operation interface.
本文分析了卫星的工作流程,详细研究了卫星地面站数传过程及其约束条件。介绍了生产调度中调度问题的三元组表示方法及实用的优化调度算法。研究了卫星数传调度的时间索引{0、1}线性规划模型,并根据拉格朗日松弛的思想提出了拉格朗日启发式及算法。研究了卫星数传调度的单地面站模型,并提出了分支定界求解算法。研究了数传调度问题的树形问题表示方法,对于每个地面站的数传任务建立了时间分类算法及直接提取算法。研究了数传调度问题的稀疏矩阵表示方法,结合任务分类提出了一种能快速求解可行解的启发式。
本文设计并实现了一个卫星数传调度仿真系统。该系统集成了卫星仿真工具STK(Satellite Tool Kit)进行轨道预报及卫星地面站可见时间窗口的计算。设计了一个随机问题产生器用于产生随机的数传任务。为了方便调度结果的显示以及人工调整调度结果,提出问题的循环树形表示方式,在此基础上结合界面库Xtreme Toolkit Pro实现简洁的操作界面。
As the constant improving of aviation technology in our country, more and more civil and military satellites are launched into space. In order to adapt to the situation of many satellites few ground stations, and in order to accomplish the specially designed satellite tasks, we must make management and control decisions in a whole perspective of satellite system. The purpose of scheduling satellite data transmission is that under the situation of many satellites few ground stations, we can reasonably schedule ground station’s measure and control resources, largely increase the ground station’s using efficiency, fulfill as many as satellite data transmission demands.
In this paper we analyze satellite’s working procedure, and study the detail procedure of satellite and ground station’s data transmission process and its constraints condition. Introduce the triple annotation used in product scheduling and common optimal methods in constraints satisfying problem. Propose a time-indexed {0,1} linear programming model and Lagrange relaxation algorithm. Study the single station model of satellite ground station’s data transmission problem, propose a branch and bound mode and algorithm. Study the tree representation method of satellite ground station data transmission problem, for each ground station applied the time classify algorithm and direct extraction algorithm. Study the sparse matrix representation method for satellite ground station data transmission problem, combing task classifying method we proposes a heuristic method able to derive a feasible solution quickly.
In this paper, we design and implement a satellite data transmission simulation system. It integrates the STK(Satellite Tool Kit) software used to predicting satellite orbit information and calculating satellite and ground station’s visibility window. We design a random task generator. In order to beautifully display scheduling result and to provide a method to modify scheduling result, we propose a circular linked tree denotation. Base on its denotation and the third interface library Xtreme Toolkit Pro, we implement a concision operation interface.
引文
[1]Gooley T D.Automating the Satellite Range Scheduling Process[D].Ohio:Air Force Institute of Technology,1993.
[2]Schalck,Automating Satellite Range Scheduling[D].Ohio:Air Force Institute of Technology,1993.
[3]Agnese J,Bataille N,Bensana E,et a1.Exact and Approximate Methods for the Daily Management of an Earth Observation Satellite[C].Proceeding of the 5th ESA Workshop on Artificial Intelligence and Knowledge Based Systems for Space,1995.
[4]Wolfe W J and Sorensen S E.Three Scheduling Algorithms Applied to the Earth Observing Systems Domain[J].Management Science,2000.46(1):148-168.
[5]Pemberton JC. and Galiber F. A Constraint-Based Approach to Satellite Scheduling[C].Proceedings of Constraint Programming and Large Scale Discrete Optimization,DIMACS Workshop,2001.
[6]王远振,赵坚,聂成.多卫星一地面站系统的Petri网模型研究[J].空军工程大学学报(自然科学版),2003,4(2):7-10.
[7]Bresina J L. Heuristic-Based Stochastic Sampling. Proceedings of the Thirteenth National Conference on Artificial Intelligence, Portland, OR, 1996:271-278.
[8]F.Wong, Supervisor of Planning, 21 SOPS, Onizuka Air Force Base, CA,Telephone interview,(June 1992).
[9]M.Roberts, L.Barbulescu, A.E.Howe, L.D.Whitley. Trading places: How to schedule more in a multi-resource oversubscribed scheduling problem. In Proceedings of the International Conference on Planning and Scheduling,2004
[10]David E.Joslin and David P.Clements.“Squeaky Wheel”Optimization.In Journal of Artificial Intelligence Research, volume 10,pages 353–373,1999.
[11]Bianchessi N, Jean-Francois Cordeau. A heuristic for the multi-satellite, multi-orbit and multi-user management of earth observation satellites[J]. European Journal of Operational Research,2005:750-762.
[12]Parish SA. A Genetic Algorithm Approach to Automating Satellite Range Scheduling [D]. Ohio: Air Force Institute of Technology, 1994.
[13]阎志伟,牛轶峰,李汉铃.基于并行禁忌遗传算法(PTGA)的预警卫星传感器调度研究[J].宇航学报, 2003, 24(6):598-603
[14]金光,武小悦,高卫斌.卫星地面站资源调度优化模型及启发式算法.系统工程与电子技术,2004,26(12):1839-1841.
[15]何川东,郭玉华,李军,靳肖闪.卫星任务规划可视化仿真系统设计与实现.计算机仿真,2007,24(06):45-48.
[16]王江云,彭晓源,王行仁.基于HLA的卫星分布式仿真系统.计算机工程与设计2004 ,25(5):700-702.
[17]曹裕华,冯书兴,张彦,刘淑丽. Web环境下的军事航天任务规划系统设计和实现.装备指挥技术学院学报,2007,18(3):47-51.
[18]陈金勇,冯阳,彭会湘.一种卫星照相规划软件的可视化设计与实现.无线电通信技术,2004,30(6):35-37.
[19]贺仁杰.成像侦察卫星调度问题研究.长沙:国防科学技术大学博士学位论文,2004.
[20]刘洋.成像侦察卫星动态重调度模型、算法及应用研究.长沙:国防科技大学博士学位论文,2005.
[21]阮启明.面向区域目标的成像侦察卫星调度问题研究.长沙:国防科技大学博士学位论文,2006.
[22]王永刚,刘玉文.军事卫星及应用概论.北京:国防工业出版社,2003.
[23]刘德刚.航空公司实时飞机和机组调配问题的研究.北京:中国科学院博士学位论文,2002.
[24]Verfaillie G.Russian Doll Search for Solving Constraint Optimization Problems. Proceedings of AAAI-96.Portland:Oregon,1996.181-187.
[25]Wolfe W.J,Sorensen S.E.Three Scheduling Algorithms Applied to the Earth Observing Systems Domain Management Science,2000,46(1):148-168.
[26]Veridian Inc.Generic Resource Event and Activity Scheduler.2003.
[27]Jeremy Frank,Ari Jonsson,Robert Morris,David Smith.Planning and Scheduling for Fleets of Earth
[28]J Pemberton.Towards scheduling over-constrained remote sensing satellites. Proceedings of the 2nd International Workshop on Planning and Scheduling for Space.San Francisco,CA,2000.
[29]Analytical Graphics Inc.Satellite Tool Kit 5.0.2003.
[30]M.G.C.Resende T.A.Feo,and S.H.Smith.A greedy randomized adaptive search procedure for maximum independent set.Operations Research,1994.
[31]Ingber L.Very Fast Simulated Re-annealing.Math Compute Modelling,1989,12:967-973.
[32]T.A.Feo M.G.C.Resende,and S.H.Smith.Fortran subroutines for approximate solution of maximum independent set problems using GRASP.ACM Trans.Math. Software,1998,25(3):341-352.
[33]陈站华.资源卫星任务安排测试方法的研究与实现.无线电工程,2005,35(3):62-64.
[34]张钧屏,方艾里,万志龙.对地观测与对空监视.北京:科学出版社,2001.
[35]曾华锋,夏洪流,周刚.现代侦察监视技术.北京:国防工业出版社,2001.
[36]李菊芳.航天侦察多星多地面站任务规划问题研究.长沙:国防科技大学博士学位论文,2005.
[37]王远振,赵坚,聂成.多星地面站系统资源配置优化研究综述.系统工程与电子技术,2004,26(4):437-439.
[38]代树武.航天器自主运行关键技术的研究北京:中国科学院空间科学与应用研究中心博士后论文,2002.
[39]王钧.成像卫星综合任务调度模型与优化方法研究.长沙:国防科技大学博士学位论文,2007.
[40]张帆.成像卫星计划编制中的约束建模及优化求解技术研究.长沙:国防科技大学博士学位论文,2005.
[41]代树武,孙辉先.卫星的智能规划与调度.控制与决策,2003,18(2):203-206.
[42]Torsten Fahle,Ulrich Junker,Stefan E Karisch,Niklas Kohi.Constraint Programming Based Column Generation for Crew Assignment.Journal of Heuristics,2002,8(1):59-81.
[43]Earth Observation Satellite Constellations.The 9th International Conference on Space Operations(SpaceOps 2006).Rome,Italy,2006.
[44]邢文训,谢金星.现代优化计算方法.清华大学出版社.2005
[45]张智海.调度:原理、算法和系统.清华大学出版社.2007
[46]谢金星,薛毅等.优化建模与LINDO/LINGO软件.清华大学出版社.2005
[47]谷宏志.基于启发式算法的卫星地面站资源调度系统设计与实现.西安电子科技大学硕士学位论文.2007
[2]Schalck,Automating Satellite Range Scheduling[D].Ohio:Air Force Institute of Technology,1993.
[3]Agnese J,Bataille N,Bensana E,et a1.Exact and Approximate Methods for the Daily Management of an Earth Observation Satellite[C].Proceeding of the 5th ESA Workshop on Artificial Intelligence and Knowledge Based Systems for Space,1995.
[4]Wolfe W J and Sorensen S E.Three Scheduling Algorithms Applied to the Earth Observing Systems Domain[J].Management Science,2000.46(1):148-168.
[5]Pemberton JC. and Galiber F. A Constraint-Based Approach to Satellite Scheduling[C].Proceedings of Constraint Programming and Large Scale Discrete Optimization,DIMACS Workshop,2001.
[6]王远振,赵坚,聂成.多卫星一地面站系统的Petri网模型研究[J].空军工程大学学报(自然科学版),2003,4(2):7-10.
[7]Bresina J L. Heuristic-Based Stochastic Sampling. Proceedings of the Thirteenth National Conference on Artificial Intelligence, Portland, OR, 1996:271-278.
[8]F.Wong, Supervisor of Planning, 21 SOPS, Onizuka Air Force Base, CA,Telephone interview,(June 1992).
[9]M.Roberts, L.Barbulescu, A.E.Howe, L.D.Whitley. Trading places: How to schedule more in a multi-resource oversubscribed scheduling problem. In Proceedings of the International Conference on Planning and Scheduling,2004
[10]David E.Joslin and David P.Clements.“Squeaky Wheel”Optimization.In Journal of Artificial Intelligence Research, volume 10,pages 353–373,1999.
[11]Bianchessi N, Jean-Francois Cordeau. A heuristic for the multi-satellite, multi-orbit and multi-user management of earth observation satellites[J]. European Journal of Operational Research,2005:750-762.
[12]Parish SA. A Genetic Algorithm Approach to Automating Satellite Range Scheduling [D]. Ohio: Air Force Institute of Technology, 1994.
[13]阎志伟,牛轶峰,李汉铃.基于并行禁忌遗传算法(PTGA)的预警卫星传感器调度研究[J].宇航学报, 2003, 24(6):598-603
[14]金光,武小悦,高卫斌.卫星地面站资源调度优化模型及启发式算法.系统工程与电子技术,2004,26(12):1839-1841.
[15]何川东,郭玉华,李军,靳肖闪.卫星任务规划可视化仿真系统设计与实现.计算机仿真,2007,24(06):45-48.
[16]王江云,彭晓源,王行仁.基于HLA的卫星分布式仿真系统.计算机工程与设计2004 ,25(5):700-702.
[17]曹裕华,冯书兴,张彦,刘淑丽. Web环境下的军事航天任务规划系统设计和实现.装备指挥技术学院学报,2007,18(3):47-51.
[18]陈金勇,冯阳,彭会湘.一种卫星照相规划软件的可视化设计与实现.无线电通信技术,2004,30(6):35-37.
[19]贺仁杰.成像侦察卫星调度问题研究.长沙:国防科学技术大学博士学位论文,2004.
[20]刘洋.成像侦察卫星动态重调度模型、算法及应用研究.长沙:国防科技大学博士学位论文,2005.
[21]阮启明.面向区域目标的成像侦察卫星调度问题研究.长沙:国防科技大学博士学位论文,2006.
[22]王永刚,刘玉文.军事卫星及应用概论.北京:国防工业出版社,2003.
[23]刘德刚.航空公司实时飞机和机组调配问题的研究.北京:中国科学院博士学位论文,2002.
[24]Verfaillie G.Russian Doll Search for Solving Constraint Optimization Problems. Proceedings of AAAI-96.Portland:Oregon,1996.181-187.
[25]Wolfe W.J,Sorensen S.E.Three Scheduling Algorithms Applied to the Earth Observing Systems Domain Management Science,2000,46(1):148-168.
[26]Veridian Inc.Generic Resource Event and Activity Scheduler.2003.
[27]Jeremy Frank,Ari Jonsson,Robert Morris,David Smith.Planning and Scheduling for Fleets of Earth
[28]J Pemberton.Towards scheduling over-constrained remote sensing satellites. Proceedings of the 2nd International Workshop on Planning and Scheduling for Space.San Francisco,CA,2000.
[29]Analytical Graphics Inc.Satellite Tool Kit 5.0.2003.
[30]M.G.C.Resende T.A.Feo,and S.H.Smith.A greedy randomized adaptive search procedure for maximum independent set.Operations Research,1994.
[31]Ingber L.Very Fast Simulated Re-annealing.Math Compute Modelling,1989,12:967-973.
[32]T.A.Feo M.G.C.Resende,and S.H.Smith.Fortran subroutines for approximate solution of maximum independent set problems using GRASP.ACM Trans.Math. Software,1998,25(3):341-352.
[33]陈站华.资源卫星任务安排测试方法的研究与实现.无线电工程,2005,35(3):62-64.
[34]张钧屏,方艾里,万志龙.对地观测与对空监视.北京:科学出版社,2001.
[35]曾华锋,夏洪流,周刚.现代侦察监视技术.北京:国防工业出版社,2001.
[36]李菊芳.航天侦察多星多地面站任务规划问题研究.长沙:国防科技大学博士学位论文,2005.
[37]王远振,赵坚,聂成.多星地面站系统资源配置优化研究综述.系统工程与电子技术,2004,26(4):437-439.
[38]代树武.航天器自主运行关键技术的研究北京:中国科学院空间科学与应用研究中心博士后论文,2002.
[39]王钧.成像卫星综合任务调度模型与优化方法研究.长沙:国防科技大学博士学位论文,2007.
[40]张帆.成像卫星计划编制中的约束建模及优化求解技术研究.长沙:国防科技大学博士学位论文,2005.
[41]代树武,孙辉先.卫星的智能规划与调度.控制与决策,2003,18(2):203-206.
[42]Torsten Fahle,Ulrich Junker,Stefan E Karisch,Niklas Kohi.Constraint Programming Based Column Generation for Crew Assignment.Journal of Heuristics,2002,8(1):59-81.
[43]Earth Observation Satellite Constellations.The 9th International Conference on Space Operations(SpaceOps 2006).Rome,Italy,2006.
[44]邢文训,谢金星.现代优化计算方法.清华大学出版社.2005
[45]张智海.调度:原理、算法和系统.清华大学出版社.2007
[46]谢金星,薛毅等.优化建模与LINDO/LINGO软件.清华大学出版社.2005
[47]谷宏志.基于启发式算法的卫星地面站资源调度系统设计与实现.西安电子科技大学硕士学位论文.2007