中继卫星任务调度方法研究
|
摘要
跟踪与数据中继卫星系统(TDRSS)是为中、低轨道的航天器与航天器之间、航天器与地面站之间提供数据中继、连续跟踪与轨道测控服务的系统,简称中继卫星系统。中继卫星任务调度是指中继卫星任务计划管理中心根据用户提交的中继资源请求,确定中继卫星的有效载荷,科学合理地分配中继卫星系统资源,以满足跟踪、测控与数据中继需要。中继卫星任务调度目的在于为中继卫星系统的任务计划编制提供科学合理的决策手段与依据。中继卫星任务调度模型的建立与算法求解是中继卫星调度需要解决的关键问题,这也是本文研究的主要内容。
本文的主要研究成果如下:
1、建立了中继卫星日常任务调度模型,并对中继卫星日常任务调度运用遗传算法进行了求解。中继卫星日常任务调度问题的重要特点在于:中继卫星与用户航天器之间并非时时可见,因此跟踪与数据通信任务存在可见时间窗口约束,且时间窗口的数量往往具有多个。只有在可见时间窗口内,跟踪与数据通信任务才可能执行。本文在分析任务时间窗口约束条件的基础上,建立了中继卫星日常任务调度的数学模型,该模型考虑的调度任务具有多个时间窗口,优化目标是满足中继请求的各个任务的收益之和的最大值。在此模型的基础上,本文采用遗传算法对中继卫星日常任务调度模型进行求解。
2、建立了中继卫星应急任务调度模型,并对中继卫星应急任务调度运用基于贪婪策略的算法进行了求解。中继卫星应急任务调度是根据计划管理中心的调整需求,对中继卫星日常任务方案进行快速调整,其目的是在最小化调整已有日常任务方案的基础上,最大化满足应急任务的规划要求。本文将中继卫星应急任务调度归纳为在中继卫星日常任务调度基础上因新应急任务插入而导致卫星资源状态改变的调度问题,并根据规则采用基于贪婪策略的优化算法来求解中继卫星应急任务调度问题。
3、根据中继卫星系统的实际情况,进行中继卫星动态调度的应用实例分析,综合验证本文提出的调度模型与算法的有效性。
通过本文的研究工作,初步完成了中继卫星任务调度问题由理论走向应用的相关探索。
TDRSS(Tracking and Data Relay Satellite System) can provide the data relaying,continuous tracking and TT&C for communications between spacecrafts of LEO(the low earth orbit)and MEO(middle earth orbit),The relay satellite scheduling is that the task plan management center of the relay satellite,according to application demands and tasks that the relay satellite should complete,selects the relay satellite and its payloads,user spacecrafts that need sending communicating data,and assigns the relay satellite system resources scientifically,The relay satellite scheduling is a main content of space resource management,which is to support task plan making of the relay satellite system.How to build and solve the scheduling models of the relay satellite is the key to the relay satellite scheduling problem and it is also the primary study of the paper.
The main contents and fruits of this paper are outlined as follows:
1、The paper builds and solves scheduling model of the relay satellite daily task. One of the most important characteristics of the relay satellite daily task scheduling problem lies in that there is time windows constraint between the relay satellite and user spacecraft.And there are many time windows between the relay satellite and user spacecraft.Tracking and Data Tasks can only be complied within the given time windows.The paper builds the single access link scheduling model based on constraints analysis.In the model,the number of time windows of task is above two.The income of object function is measured with the total income of all tasks.And based on it,the optimization framework of gene algorithm has been built and solved the relay satellite daily task scheduling model with optimization policy of gene algorithm.
2、The paper builds and solves the relay satellite emergency model,because the relay satellite emergency task scheduling and the relay satellite daily task scheduling are in the same time.So the relay satellite emergency task scheduling is a scheduling problem of new task for the changing of satellite recourse condition.According to the regulation,the paper solves the relay satellite daily task scheduling model with optimization policy of greedy algorithm.
3、This paper makes analysis of the application example of the relay satellite dynamic scheduling and It indicates that the provided scheduling models are reasonable and effective.
The search work of the paper has elementarily explored how to combine the scheduling theory with the relay satellite application field.
本文的主要研究成果如下:
1、建立了中继卫星日常任务调度模型,并对中继卫星日常任务调度运用遗传算法进行了求解。中继卫星日常任务调度问题的重要特点在于:中继卫星与用户航天器之间并非时时可见,因此跟踪与数据通信任务存在可见时间窗口约束,且时间窗口的数量往往具有多个。只有在可见时间窗口内,跟踪与数据通信任务才可能执行。本文在分析任务时间窗口约束条件的基础上,建立了中继卫星日常任务调度的数学模型,该模型考虑的调度任务具有多个时间窗口,优化目标是满足中继请求的各个任务的收益之和的最大值。在此模型的基础上,本文采用遗传算法对中继卫星日常任务调度模型进行求解。
2、建立了中继卫星应急任务调度模型,并对中继卫星应急任务调度运用基于贪婪策略的算法进行了求解。中继卫星应急任务调度是根据计划管理中心的调整需求,对中继卫星日常任务方案进行快速调整,其目的是在最小化调整已有日常任务方案的基础上,最大化满足应急任务的规划要求。本文将中继卫星应急任务调度归纳为在中继卫星日常任务调度基础上因新应急任务插入而导致卫星资源状态改变的调度问题,并根据规则采用基于贪婪策略的优化算法来求解中继卫星应急任务调度问题。
3、根据中继卫星系统的实际情况,进行中继卫星动态调度的应用实例分析,综合验证本文提出的调度模型与算法的有效性。
通过本文的研究工作,初步完成了中继卫星任务调度问题由理论走向应用的相关探索。
TDRSS(Tracking and Data Relay Satellite System) can provide the data relaying,continuous tracking and TT&C for communications between spacecrafts of LEO(the low earth orbit)and MEO(middle earth orbit),The relay satellite scheduling is that the task plan management center of the relay satellite,according to application demands and tasks that the relay satellite should complete,selects the relay satellite and its payloads,user spacecrafts that need sending communicating data,and assigns the relay satellite system resources scientifically,The relay satellite scheduling is a main content of space resource management,which is to support task plan making of the relay satellite system.How to build and solve the scheduling models of the relay satellite is the key to the relay satellite scheduling problem and it is also the primary study of the paper.
The main contents and fruits of this paper are outlined as follows:
1、The paper builds and solves scheduling model of the relay satellite daily task. One of the most important characteristics of the relay satellite daily task scheduling problem lies in that there is time windows constraint between the relay satellite and user spacecraft.And there are many time windows between the relay satellite and user spacecraft.Tracking and Data Tasks can only be complied within the given time windows.The paper builds the single access link scheduling model based on constraints analysis.In the model,the number of time windows of task is above two.The income of object function is measured with the total income of all tasks.And based on it,the optimization framework of gene algorithm has been built and solved the relay satellite daily task scheduling model with optimization policy of gene algorithm.
2、The paper builds and solves the relay satellite emergency model,because the relay satellite emergency task scheduling and the relay satellite daily task scheduling are in the same time.So the relay satellite emergency task scheduling is a scheduling problem of new task for the changing of satellite recourse condition.According to the regulation,the paper solves the relay satellite daily task scheduling model with optimization policy of greedy algorithm.
3、This paper makes analysis of the application example of the relay satellite dynamic scheduling and It indicates that the provided scheduling models are reasonable and effective.
The search work of the paper has elementarily explored how to combine the scheduling theory with the relay satellite application field.
引文
[1]常显奇,李云芝,罗小明等著.军事航天学(第2版)[M].国防工业出版社,2005.
[2]方炎申.中继卫星系统的现状与发展[J].尖端科技,2005.
[3]姜昌,范晓玲著.航天通信跟踪技术导论[M].北京工业大学出版社,2003.
[4]总装备部卫星有效载荷及应用技术专业组应用技术分组.卫星应用现状与发展[M].中国科学技术出版社,2001.
[5]夏南银.航天测控系统[M].国防工业出版社,2002.
[6]Bensana E.,Verfaillie G.,Agnese J.C.,etal..Planning and Scheduling for Fleets of Earth Observing Satellites[J].Symposium on Space Mission Operations and Ground Data Systems,Munich,1996.
[7]Gabrel C.MP for Earth observation satellite mission planning[J].Operations Research in Space and Air,2003.
[8]贺仁杰.成像侦察卫星调度问题研究[D].国防科技大学博士学位论文,2004.
[9]张帆.成像卫星计划编制中的约束建模及优化求解技术研究[D].国防科技大学博士学位论文,2005.
[10]李于衡,易克初,田红心.跟踪与数据中继卫星(TDRS)跟踪用户星的条件分析[J].空间科学学报,2006.
[11]Marco Adinolfi,Amedeo Cestal.Heuristic scheduling of the DRS communication system[J].Engineering Applications of Artificial Intelligence,1995.
[12]S.Rojanasoonthon,J.F.Bard,S.D.Reddy.Algorithms for parallel machine scheduling:a case study of the Tracking and Data Relay Satellite System[J].Journal of the Operational Research Society,2003.
[13]S.Rojanasoonthon.Parallel machine scheduling with time windows [D].Graduate School of the University of Texas at Austin,2004.
[14]方炎申.中继卫星调度模型研究[D]。国防科技大学博士学位论文,2007.
[15]顾中舜.中继卫星动态调度问题建模及优化技术研究[D].国防科技大学博士学位论文,2007。
[16]Vasquez M,Hao J K.A "logic-constrained" knapsack formulation and a tabu algorithm for the daily photograph scheduling of an earth observation satellite[J].Computational Optimization and Applications,2001.
[17]Lemaitre M,et al.Selecting and scheduling observations of agile satellites[J]. Aerospace Sciences and Technology,2002.
[18]Lin W.C.,Liao D.Y.,Liu C.Y.and Lee Y.Y.,Daily Imaging Scheduling of An Earth Observation Satellite in Proceedings of IEEE International Conf.on Systems,Man,and Cybernetics 2003[J],USA:Washington,2003.
[19]Wolfe W.J.,Sorensen S.E.,Three Scheduling Algorithms Applied to the Earth Observing Systems Domain[J],Management Science,2000.
[20]王钧.成像卫星综合任务调度模型与优化方法研究[D].国防科学技术大学博士学位论文,2007.
[21]方炎申,顾中舜,陈英武。中继卫星与用户航天器之间星路研究[J].计算机工程与设计,2005.
[22]马雨出.中继卫星系统星间链路建立中若干问题的研究[J].哈尔滨工业大学博士学位论文,2001。
[23]代树武,孙辉先.卫星的智能规划与调度[J].控制与决策,2003.
[24]张正强.基于MAS的分布式成像卫星系统任务规划与控制问题研究[D].国防科技大学博士学位论文,2006.
[25]陈慧中,王钧,李军.卫星成像规划调度系统中的可视化决策支持研究与实现[J].计算机工程与科学,2007.
[26]王凌.车间调度及其遗传算法[M].清华大学出版社,2003.
[27]方炎申,陈英武,顾中舜.中继卫星调度的CSP模型[J].国防科技大学学报,2004.
[28]陈英武,方炎申,顾中舜.中继卫星单址链路调度模型与算法研究[J].中国空间科学技术,2007.
[29]陈英武,方炎申,李菊芳.卫星任务调度问题的约束规划模型[J].国防科技大学学报,2006.
[30]李敏强,寇纪松,林丹.遗传算法的基本理论与应用[M].科技出版社,2002.
[31]Sylvain Damiani,G＇erard Verfaillie,Marie-Claire Charmeau.An Anytime Planning Approach for the Management of an Earth Watching Satellite[J].Chiba Keizai University:Ashikaga Institute of Technology,1999.
[32]Jeremy Frank Ari J＇onsson,Robert Morris,David E.Smith.Planning and Scheduling for Fleets of Earth Observing Satellites[J].Management Science,1989.
[33]Wei-Cheng Lin,Da-Yin Liao.Daily Imaging Scheduling of an Earth Observation Satellite[J].IEEE Trans on Neural Networks,1995.
[34]玄光男,程润伟.遗传算法与工程设计[M].清华大学出版社,2004.
[35]胡毓达.多目标规划有效性理论[M],上海科学技术出版社,1994.
[36]王小平,曹立明.遗传算法理论、应用与软件实现[M].西安交通大学出版社, 2002.
[37]刘洋,陈英武,谭跃进。卫星地面站系统任务调度的动态规划方法[J].中国空间科学技术,2005.
[38](美)Thomash H.Cormen Charles Ronald L.Rivest Clifford.算法导论[M].机械工业出版社,2008.
[39]林鑫.基于0-1背包问题的讨论[J].微机发展,2005.
[40]陈理江,武小悦,李云峰.基于时间灵活度中继卫星调度算法[J].航空计算技术,2007.
[41]王凌等.智能优化算法及其应用[M].清华大学出版社,2005.
[42]阮启明,廖良才,谭跃进.分布式实时专家系统平台IRS3的设计与实现[J].微型电脑应用,2005.
[43]阮启明,谭跃进,陈亦红等.流通型外贸企业的ERP系统设计与开发[J].计算机应用研究,2004增刊.
[2]方炎申.中继卫星系统的现状与发展[J].尖端科技,2005.
[3]姜昌,范晓玲著.航天通信跟踪技术导论[M].北京工业大学出版社,2003.
[4]总装备部卫星有效载荷及应用技术专业组应用技术分组.卫星应用现状与发展[M].中国科学技术出版社,2001.
[5]夏南银.航天测控系统[M].国防工业出版社,2002.
[6]Bensana E.,Verfaillie G.,Agnese J.C.,etal..Planning and Scheduling for Fleets of Earth Observing Satellites[J].Symposium on Space Mission Operations and Ground Data Systems,Munich,1996.
[7]Gabrel C.MP for Earth observation satellite mission planning[J].Operations Research in Space and Air,2003.
[8]贺仁杰.成像侦察卫星调度问题研究[D].国防科技大学博士学位论文,2004.
[9]张帆.成像卫星计划编制中的约束建模及优化求解技术研究[D].国防科技大学博士学位论文,2005.
[10]李于衡,易克初,田红心.跟踪与数据中继卫星(TDRS)跟踪用户星的条件分析[J].空间科学学报,2006.
[11]Marco Adinolfi,Amedeo Cestal.Heuristic scheduling of the DRS communication system[J].Engineering Applications of Artificial Intelligence,1995.
[12]S.Rojanasoonthon,J.F.Bard,S.D.Reddy.Algorithms for parallel machine scheduling:a case study of the Tracking and Data Relay Satellite System[J].Journal of the Operational Research Society,2003.
[13]S.Rojanasoonthon.Parallel machine scheduling with time windows [D].Graduate School of the University of Texas at Austin,2004.
[14]方炎申.中继卫星调度模型研究[D]。国防科技大学博士学位论文,2007.
[15]顾中舜.中继卫星动态调度问题建模及优化技术研究[D].国防科技大学博士学位论文,2007。
[16]Vasquez M,Hao J K.A "logic-constrained" knapsack formulation and a tabu algorithm for the daily photograph scheduling of an earth observation satellite[J].Computational Optimization and Applications,2001.
[17]Lemaitre M,et al.Selecting and scheduling observations of agile satellites[J]. Aerospace Sciences and Technology,2002.
[18]Lin W.C.,Liao D.Y.,Liu C.Y.and Lee Y.Y.,Daily Imaging Scheduling of An Earth Observation Satellite in Proceedings of IEEE International Conf.on Systems,Man,and Cybernetics 2003[J],USA:Washington,2003.
[19]Wolfe W.J.,Sorensen S.E.,Three Scheduling Algorithms Applied to the Earth Observing Systems Domain[J],Management Science,2000.
[20]王钧.成像卫星综合任务调度模型与优化方法研究[D].国防科学技术大学博士学位论文,2007.
[21]方炎申,顾中舜,陈英武。中继卫星与用户航天器之间星路研究[J].计算机工程与设计,2005.
[22]马雨出.中继卫星系统星间链路建立中若干问题的研究[J].哈尔滨工业大学博士学位论文,2001。
[23]代树武,孙辉先.卫星的智能规划与调度[J].控制与决策,2003.
[24]张正强.基于MAS的分布式成像卫星系统任务规划与控制问题研究[D].国防科技大学博士学位论文,2006.
[25]陈慧中,王钧,李军.卫星成像规划调度系统中的可视化决策支持研究与实现[J].计算机工程与科学,2007.
[26]王凌.车间调度及其遗传算法[M].清华大学出版社,2003.
[27]方炎申,陈英武,顾中舜.中继卫星调度的CSP模型[J].国防科技大学学报,2004.
[28]陈英武,方炎申,顾中舜.中继卫星单址链路调度模型与算法研究[J].中国空间科学技术,2007.
[29]陈英武,方炎申,李菊芳.卫星任务调度问题的约束规划模型[J].国防科技大学学报,2006.
[30]李敏强,寇纪松,林丹.遗传算法的基本理论与应用[M].科技出版社,2002.
[31]Sylvain Damiani,G＇erard Verfaillie,Marie-Claire Charmeau.An Anytime Planning Approach for the Management of an Earth Watching Satellite[J].Chiba Keizai University:Ashikaga Institute of Technology,1999.
[32]Jeremy Frank Ari J＇onsson,Robert Morris,David E.Smith.Planning and Scheduling for Fleets of Earth Observing Satellites[J].Management Science,1989.
[33]Wei-Cheng Lin,Da-Yin Liao.Daily Imaging Scheduling of an Earth Observation Satellite[J].IEEE Trans on Neural Networks,1995.
[34]玄光男,程润伟.遗传算法与工程设计[M].清华大学出版社,2004.
[35]胡毓达.多目标规划有效性理论[M],上海科学技术出版社,1994.
[36]王小平,曹立明.遗传算法理论、应用与软件实现[M].西安交通大学出版社, 2002.
[37]刘洋,陈英武,谭跃进。卫星地面站系统任务调度的动态规划方法[J].中国空间科学技术,2005.
[38](美)Thomash H.Cormen Charles Ronald L.Rivest Clifford.算法导论[M].机械工业出版社,2008.
[39]林鑫.基于0-1背包问题的讨论[J].微机发展,2005.
[40]陈理江,武小悦,李云峰.基于时间灵活度中继卫星调度算法[J].航空计算技术,2007.
[41]王凌等.智能优化算法及其应用[M].清华大学出版社,2005.
[42]阮启明,廖良才,谭跃进.分布式实时专家系统平台IRS3的设计与实现[J].微型电脑应用,2005.
[43]阮启明,谭跃进,陈亦红等.流通型外贸企业的ERP系统设计与开发[J].计算机应用研究,2004增刊.