航空学报 > 2010, Vol. 31 Issue (5): 1045-1053

电磁探测卫星星上自主规划模型及优化算法

陈浩, 李军, 景宁, 刘湘辉, 唐宇   

  1. 国防科学技术大学 电子科学与工程学院
  • 收稿日期:2009-04-05 修回日期:2009-06-30 出版日期:2010-05-25 发布日期:2010-05-25
  • 通讯作者: 陈浩

Scheduling Model and Algorithms for AutonomousElectromagnetic Detection Satellites

Chen Hao, Li Jun, Jing Ning, Liu Xianghui, Tang Yu   

  1. College of Electronic Science and Engineering, National University of Defense Technology
  • Received:2009-04-05 Revised:2009-06-30 Online:2010-05-25 Published:2010-05-25
  • Contact: Chen Hao

摘要: 电磁探测卫星自治(AEDS)是一类对地观测卫星,其搜集的信息对工业、科研和军事等领域有着重要的意义。针对电磁探测卫星有效载荷特点,建立了基于动态拓扑结构无环路有向图的星上自主规划数学模型,提出了基于标记更新最短路径搜索的星上自主规划精确算法,对其完备性和时间复杂度进行了分析。并对精确算法时间复杂度较高的缺点,将近似支配概念引入到模型中,提出了标记更新最短路径搜索近似算法,分析了算法的近似程度和时间复杂度。最后,根据模拟的数据进行实验及分析,表明该方法能有效解决电磁探测卫星自主任务规划问题。

关键词: 电磁探测卫星自治, 规划调度, 动态拓扑结构无环路有向图模型, 标记更新算法, 算法近似比分析

Abstract: Autonomous electromagnetic detection satellite (AEDS) is a type of earth observation satellites. The information collected by AEDS is very important in some application domain, such as industry, science and military. Considering the specific requirements and constraints of AEDS, this article established an ordered flexible topology directed acyclic graph onboard scheduling model, designed a scheduling algorithm based on graph label updating, and then analyzed the completeness and time complexity of the algorithm. Because of its high time complexity, the article introduced the concept of approximately dominant paths to our model. On this basis, we proposed an approximation algorithm which is improved from the original algorithm. Then, the time complexity and performance ratios of the approximation algorithm are analyzed. Finally, experiments are conducted to validate the proposed scheduling algorithms and demonstrate their practicability. The results show that the proposed approach can solve the AEDS onboard planning and scheduling problem effectively.

Key words: autonomous electromagnetic detection satellite, planning and scheduling, flexible topology directed acyclic graph model, label updating algorithm, performance ratio for approximation algorithm analysis

中图分类号: