（管理科学与工程专业论文）成像卫星鲁棒性调度方法及应用研究.pdf

国防科学技术大学研究生院博士学位论文 摘要 成像卫星是一类用于从太空中获取地面遥感信息的对地观测卫星，随着成像 卫星的数量和种类的逐步增多，成像任务的需求量也将快速增加，对成像任务的 时效性、准确性要求将更加严格，任务管理的复杂度也将大大增加。成像卫星调 度就是在综合考虑卫星资源能力和成像任务要求的基础上，将资源分配给相互竞 争的多个任务，并确定各任务的起止时间，以排除不同任务之间的资源使用冲突， 充分发挥卫星系统的能力，并最大化满足各类用户的需求。目前，对成像卫星调 度问题的研究还主要集中在确定性调度领域。在实际的成像卫星系统运行过程中， 存在着很多不确定性因素，如新任务的插入、已安排任务的取消、任务属性的改 变、天气的变化、卫星资源状态的变化等。论文在总结和分析国内外相关研究工 作的基础上，采用鲁棒性调度方法求解不确定条件下的成像卫星调度问题，将成 像卫星鲁棒性调度分为鲁棒性调度方案生成和鲁棒性调度方案动态调整两个阶 段。本文的主要研究工作和创新点如下： ( 1 ) 提出了成像任务收益的计算方法和基于邻域的鲁棒性指标，建立了成像 卫星鲁棒性调度模型。论文在对影响成像任务收益的主要影响因素进行分析的基 础上，拓展了任务收益的计算方法，使得成像任务的收益不仅反映了观测目标的 重要程度，而且兼顾了成像质量和当前调度周期后任务的剩余可行观测机会。借 鉴连续函数的鲁棒性优化思想，提出了基于邻域的鲁棒性指标，分析了问题的主 要约束条件，在此基础上，建立了成像卫星鲁棒性调度模型。 ( 2 ) 针对成像卫星鲁棒性调度模型，提出了基于偏好的分层多目标遗传算法 p h m o g a 。论文借鉴文化算法的双层空间概念和基于偏好的加权p a r c t o 方法，设 计了一种基于偏好的分层多目标遗传算法p h m o g a 。针对成像卫星鲁棒性调度的 特点，采用合适的编码方式对问题的解进行描述，给出了构造初始种群的贪婪随 机插入算法，提出了基于知识进化层的知识进化策略，设计了与编码方式相对应 的任务序列交叉算子和多态变异算子，并对算法的收敛性进行了分析。 ( 3 ) 提出了任务最早开始执行时间和最晚开始执行时间的计算方法，给出了 遗传操作的可行性分析和参数更新方法。在成像卫星调度问题中，时间约束和能 量约束是两类主要的约束条件，只有满足约束条件的遗传操作才是可行的。论文 针对时间约束和能量约束，提出了关键任务序列和后向能量负荷等概念，给出了 任务最早开始执行时间和最晚开始执行时间的计算方法。针对转移任务操作和交 换任务操作，给出了具体的可行性分析方法和参数更新方法。 ( 4 ) 针对成像卫星鲁棒性调度方案动态调整问题，建立了成像卫星动态调度 模型，提出了动态插入任务启发式算法d i t h a 。论文针对各种不确定因素造成的 第i 页 国防科学技术大学研究生院博士学位论文 扰动，把成像卫星鲁棒性调度方案动态调整问题统一描述为一类插入任务的动态 调度问题。针对成像卫星动态调度问题的特点，建立了成像卫星动态调度模型， 提出了动态插入任务启发式算法d i t h a 。计算实例和测试实验结果表明，在对调 度方案进行动态调整时，调整的结果一方面与动态调整的方法有关，另一方面也 与调度方案的鲁棒性有关。调度方案的鲁棒性越强，动态调整的效果越好。 ( 5 ) 将上述研究成果应用于成像卫星规划调度系统，介绍了该系统的设计和 实现，并利用该系统对一个具体的应用实例进行了求解和分析，求解结果验证了 本文提出的成像卫星鲁棒性调度方法的有效性。 主题词：成像卫星；鲁棒性调度；动态调度；偏好；多目标遗传算法；启发 式算法 第i i 页 国防科学技术大学研究生院博士学位论文 a b s t r a c t i m a g i n gs a t e l l i t ei sak i n do fe a r t ho b s e r v a t i o ns a t e l l i t e ( e o s ) a c q u i r i n gr e m o t e s e n s i n gi n f o r m a t i o nf r o mo u t e rs p a c e t h ei m a g i n gr e q u i r m e n t sw i l la u g m e n tr a p i d l y 谢也t h ei n c r e a s e m e n to ft h ei m a g i n gs a t e l l i t e s ，t h et i m ee f f i c i e n c ya n d a c c u r a c yo f t h e i m a g i n gt a s k sw i l lb em o r ea n dm o r er i g o r o u sa n dt h ec o m p l e x i t yo ft a s km a n a g e m e n t w i l lb ee n h a n c e dl a r g e l y s c h e d u l i n go fi m a g i n gs a t e l l i t e sm e a n st oa l l o c a t em u l t i p l e s a t e l l i t er e s o u r c e st om u l t ic o m p e t i t i v et a s k sw i t h o u tc o n f l i c ta n da s c e r t a i nt h e e x e c u t i o nt i m e so ft h o s et a s k sa c c o r d i n gt ot h eu s e r sr e q u i r e m e n t sa n ds a t e l l i t e c a p a b i l i t i e s ，a n dm a k e st h e m o s tu s eo ft h el i m i t e dr e s o u r c e si no r d e rt os a t i s f y m u l t i f a r i o u so b s e r v i n gr e q u i r e m e n t si nf u t u r e s of a r ，r e s e a r c h e sh a v eb e e np r i m a r i l y f o c u s e do ni m a g i n gs a t e l l i t e ss c h e d u l i n gp r o b l e mw i t h o u tu n c e r t a i n t y i np r a c t i c e ，t h e s a t e l l i t e sa r ew o r k i n gi nac o m p l e xe n v i r o n m e n t ，f a c e d 谢也d i f f e r e n tu n c e r t a i n t i e ss u c h a si n s e r t i o no fn e wt a s k s ，c a n c e l l a t i o no fa r r a n g e dt a s k s ，c h a n g eo ft a s kp r o p e r t i e s ， c h a n g eo fw e a t h e rc o n d i t i o n ，u n a n t i c i p a t e dc h a n g e si ns a t e l l i t er e s o u r c e sa n de r e 。b a s e d o nt h es u m m a r i z i n ga n da n a l y z i n go fr e s e a r c hw o r k si n s i d ea n do u t s i d e ，t h i st h e s i s d e v i d e st h ew h o l ep r o b l e mi n t ot w op h a s e si n c l u d i n gt h ec r e a t i o no fr o b u s ts o l u t i o n p h a s ea u dt h ed y n a m i ca d j u s t m e n to fr o b u s ts o l u t i o np h a s e t h em a i nr e s e a r c hc o n t e n t s a n da c h i e v e m e n t so ft h i st h e s i sa r ea sf o l l o w s ： ( 1 ) p u t t i n g f o r w a r dt h e i m a g i n g t a s k g a i nc o m p u t a t i o nm e t h o d a n dt h e n e i g h b o r h o o d - b a s e dr o b u s t n e s sm e a s u r e ，a n dp r e s e n t i n gt h ei m a g i n gs a t e l l i t e sr o b u s t s c h e d u l i n gm o d e l o nt h eb a s i so fa n a l y s i so nt h em a i nc o n t r i b u t i n gf a c t o r s ，w ee x t e n d t h et a s kg a i nc o m p u t a t i o nm e t h o dt ot a k ei n t oa c c o u n tt h ei m p o r t a n c eo fo b s e r v i n g t a r g e t ，i m a g eq u a l i t ya n dr e m a i n i n gf e a s i b i l i t yo p p o r t u n i t i e sa tt h es a l n et i m e w et h e n p r o p o s ean e i g h b o r h o o d b a s e dr o b u s t n e s sm e a s u r ef o rs c h e d u l i n gw h i c hi si n s p i r e db y a d v a n c e si nr o b u s to p t i m i z a t i o no fc o n t i n u o u sf u n c t i o n s ，a n a l y s et h em a i nc o n s t r a i n t s a n dp r e s e n tt h ei m a g i n gs a t e l l i t e sr o b u s ts c h e d u l i n gm o d e l ( 2 ) p r o p o s i n gap r e f e r e n c e - b a s e dh i e r a c h i c a lm u l t i o b j e c t i v eg e n e t i ca l g o r i t h m 0 ) h m o g a ) t os o l v et h ei m a g i n gs a t e l l i t e sr o b u s ts c h e d u l i n gm o d e l m st h e s i sd e s i g n s p h m o g aw h i c hi s i n s p i r e db yh i e m c h i c a lp l a c e so ft h ec u l t u r ea l g o r i t h ma n d p r e f e r e n c e - b a s e dw e i g h t e dp a r e t o a c c o r d i n gt ot h ec h a r a c t e ro fi m a g i n gs a t e l l i t e s r o b u s ts c h e d u l i n g ，w eu s et h ea p p r o p r i a t ee n c o d i n gm e t h o dt od e p i c tt h e s o l u t i o n , g i v ea g r e e d yr a n d o m i z e di n s e r ta l g o r i t h mt oc o n s t r u c ti n i t i a lf e a s i b l ep o p u l a t i o nf o re v o l u t i o n , p r o p o s eak n o w l e d g ee v o l u t i o ns t r a t e g yb a s e do nt h ek n o w l e d g ee v o l u t i o ns p a c e ，d e s i g n t h et a s ks e q u e n c e b a s e dc r o s s o v e ro p e r a t o ra n dm u l t i m o d em u t a t i o no p e r a t o r ，a n d a n a l y z et h ec o n v e r g e n c ef o rp h m o g a ( 3 ) p r e s e n t i n gt h ec o m p u t a t i o nm e t h o d so fe a r l i s ts t a r te x e c u t i o nt i m ea n dl a t e s t s t a r te x e c u t i o nt i m e ，a n dp r o v i d i n gt h e f e a s i b i l i t ya n a l y s i sa n dp a r a m e t e r su p d a t e 第i i i 页 国防科学技术大学研究生院博士学位论文 m e t h o d so fg e n e t i co p e r a t o r s t i m ec o n s t r a i n ta n de n e r g yc o n s t r a i n ta r ep r i m a r y c o n s t r a i n t si ni m a g i n gs a t e l l i t e ss c h e d u l i n gp r o b l e m t h i st h e s i sp r o v i d e st h en o t i o n so f c r i t i c a lt a s ks e q u e n c ea n db a c k w a r de n e r g yl o a da n dp r e s e n t st h ec o m p u t a t i o nm e t h o d s o fe a r l i s ts t a r te x e c u t i o nt i m ea n dl a t e s ts t a r te x e c u t i o nt i m e t h ef e a s i b i l i t ya n a l y s i sa n d p a r a m e t e r su p d a t em e t h o d sa l et h e np r o v i d e df o rt a s kt r a n s f e r r i n go p e r a t i o na n dt a s k e x c h a n g i n go p e r a t i o n ( 4 ) p r e s e n t i n gt h ei m a g i n gs a t e l l i t e sd y n a m i cs c h e d u l i n gm o d e la n di t sd y n a m i c i n s e r tt a s k sh e u r i s t i ca l g o r i t h m ( d i t h a ) w i t hr e g a r dt ot h ed y n a m i c a d j u s t m e n t p r o b l e mo fi m a g i n gs a t e l l i t e sr o b u s ts o l u t i o n t 1 1 i st h e s i sd e s c r i b e st h ep r o b l e mw i t ha u n i f i e df o r mo fd y n a m i cp r o b l e mw i t ht a s k si n s e r t i o n c o n s i d e r i n gt h e d i f f e r e n t p e r t u r b a t i o n s ，a n dp r e s e n t st h ei m a g i n gs a t e l l i t e sd y n a m i cs c h e d u l i n gm o d e la n di t s d y n a m i c i n s e r tt a s k sh e u r i s t i c a l g o r i t h m 硼1 e d e m o n s t r a t i o nc a l c u l a t i o na n d e x p e r i m e n t so nt e s ti n s t a n c e ss h o wt h a tr e s u l to ft h ea d j u s t m e n td e p e n d sb o t ho n a d j u s t i n ga p p r o a c ha n dr o b u s t n e s so ft h es o l u t i o n ( 5 ) i n t r o d u c i n gt h ed e s i g na n dr e a l i z a t i o no ft h ei m a g i n gs a t e l l i t e sp l a n n i n ga n d s c h e d u l i n gs y s t e mw i mt h ea p p l i c a t i o no ft h ea f o r e m e n t i o n e da c h i e v e m e n t s a l s oa n e x a m p l ea p p l i c a t i o ni sg i v e na n ds o l v e db yt h es y s t e m ，t h er e s u l tc o n f n m st h ev a l i d i t y o fi m a g i n gs a t e l l i t e sr o b u s ts c h e d u l i n ga p p r o a c hp r o v i d e di nt h i sp a p e r k e y w o r d s ：i m a g i n gs a t e l l i t e s ；r o b u s ts c h e d u l i n g ；d y n a m i cs c h e d u l i n g ； p r e f e r e n c e ；m u l t i 一0 b je c t i v eg e n e t i ca l g o r i t h m ；h e u r i s t i ca l g o r i t h m 第i v 页 国防科学技术大学研究生院博士学位论文 表 目录 表3 1 成像任务的可行时间窗口3 3 表3 2 非鲁棒性调度方案s 。：3 3 表3 3 鲁棒性调度方案占，3 3 表4 1 偏好关系及其含义4 7 表4 2 成像任务的可行时间窗口。8 0 表4 3 鲁棒性调度方案s ，8 2 表4 4p h m o g a 算法和r v n t s 算法的比较8 4 表4 5 成像卫星调度问题测试实例构造因素水平表8 6 表4 6 均匀设计表以( 6 6 ) 8 7 表4 7 ( 6 6 ) 的使用表8 7 表4 8 混合均匀设计表以( 3 2 2 1 ) 8 7 表4 9 测试实例t p i t p 6 8 8 表5 1 新任务的可行时间窗口1 0 9 表5 2 调整后的新调度方案j ，1 1 0 表5 3 非鲁棒性调度方案s 一1 11 表5 4 调整后的新调度方案s 。1 1 3 表5 5 成像卫星动态调度问题测试实例ll5 表5 6 不同算法求解的实验结果1 1 6 表5 7d i t h a 算法在不同迭代搜索深度下的平均参数值1 1 9 表6 1 卫星轨道数据1 2 7 表6 2 卫星星载遥感器性能参数1 2 7 表6 3 观测目标的经纬度参数1 2 8 表6 4 成像任务的主要参数1 2 9 表6 5 成像任务的可行时间窗口1 3 1 表6 6 鲁棒性调度方案s r 1 3 2 表6 7 非鲁棒性调度方案s 1 3 3 表6 8 新任务属性1 3 5 表6 9 调整后的新调度方案s j 1 3 6 第页 国防科学技术大学研究生院博士学位论文 表6 1 0 调整后的新调度方案7 1 3 8 表6 1l 三种动态调整方法的比较1 4 0 第v 页 国防科学技术大学研究生院博士学位论文 图目录 图1 1 论文的组织结构图1 4 图2 1 星载遥感器观测范围与实际观测场景的关系示意图1 7 图2 2 成像任务的组织实施过程。1 8 图2 3 成像卫星鲁棒性调度策略2 5 图3 1 连续函数的鲁棒性优化思想3 0 图3 2 调度方案的鲁棒性示例3 1 图3 3 重新分配任务示意图3 2 图4 1m o e a 的三种适应值计算方法4 3 图4 2 常用的密度评估方法4 4 图4 3 两种实现精英策略的方法4 5 图4 4 剪枝操作可能引起的外部种群退化4 6 图4 5p 玎o g a 算法结构5 l 图4 6 成像卫星调度问题染色体编码结构5 4 图4 7g r i a 算法流程。5 6 图4 8 基于一加权支配的存档方法。6 l 图4 9 任务序列交叉算子6 2 图4 1 0 多态变异操作的流程图6 4 图4 11 初始种群分布。8 l 图4 1 2 初始种群个体染色体编码结构示意图8 2 图4 1 3 近似加权p a r e t o 最优层8 2 图4 1 4 不同偏好下的近似加权p a r e t o 层8 9 图4 1 5p h m o g a 算法求解的两个目标函数的收敛曲线8 9 图4 1 6 一般m o g a 算法求解的两个目标函数的收敛曲线9 0 图4 1 7t p i t p 6 测试问题实例的近似加权p a r e t o 层。9 1 图5 1 动态调度问题的任务划分9 4 图5 2 插入任务的动态调度9 6 图5 3 基于拥挤度规则的任务直接插入过程1 0 0 图5 4 插入任务f 1 0 1 图5 5 基于自由度规则的任务迭代插入过程1 0 2 图5 6 任务替代插入过程1 0 5 图5 7 按最早开始执行时间规则插入。1 0 6 第v i 页 国防科学技术大学研究生院博士学位论文 图5 8 按合理方式插入1 0 6 图5 9 任务在资源上的重叠度1 0 7 图5 1 0 成像卫星动态调度流程1 0 8 图5 1 1 不同算法求解的调度方案平均收益变化比较1 1 7 图5 1 2 不同算法求解的调度方案平均任务变化率比较1 1 7 图5 1 3 不同算法求解的平均计算时间比较1 1 8 图5 1 4 不同迭代搜索深度下的调度方案平均收益变化比较1 1 9 图5 1 5 不同迭代搜索深度下的平均计算时间比较1 1 9 图5 1 6 鲁棒性调度方案和非鲁棒性调度方案动态调整的平均收益变化比较1 2 0 图5 1 7 鲁棒性调度方案和非鲁棒性调度方案动态调整的平均任务变化率比较1 2 0 图5 1 8 鲁棒性调度方案和非鲁棒性调度方案动态调整的平均计算时间比较1 2 1 图6 1 成像卫星规划调度系统组成1 2 4 图6 2 成像卫星规划调度系统运行框架1 2 6 图6 3 观测目标分布图1 2 8 图6 4 新观测目标分布图1 3 5 第v i i 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文题目：盛倦里星垒挂! 陛通廑左洼区应届丛壅 学位论文作者签名：垒歪&日期：歹掰年垆月，日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目： 盛倦里星鱼挂! 睦调廑友洼丞廑周盈究 学位论文作者签名：垄! 至陵 作者指导教师签名： 日期：妒础年铲月，乒日 日期：力裾年垆月，矿日 国防科学技术大学研究生院博士学位论文 第一章绪论 1 1 研究背景 成像卫星是一类用于从太空中获取地面遥感信息的对地观测卫星，具有覆盖 区域广、持续时间长、不受空域国界限制、无需考虑人员安全问题等独特的优势。 成像卫星的星载遥感器可以细分为多种类型，如可见光相机、红外相机、多谱段 相机、合成孔径雷达( s a r ) 等，它们各自具有不同的特点和优点【l j 。成像卫星在 轨道上运行，可以根据用户的需求对不同的地面目标实施成像，以获取各种有价 值的信息。目前，成像卫星已逐渐成为各领域获取地面信息的重要手段【l j l 2 j 【3 j 【4 】。 一般情况下，成像卫星按照预定的成像计划来实施成像。成像卫星调度是卫 星成像任务计划编制的核心内容，它本质上是一个优化决策过程，对于更好地利 用成像卫星遥感器资源，优化卫星系统整体性能，发挥它们的最大综合效益具有 至关重要的作用。现代经济与社会的发展越来越依赖于空间信息的支持，用户对 成像卫星的需求也日益增多，这就要求对卫星资源进行合理分配，以能在有限的 时间内最大限度地满足不同用户、不同收益的图像需求。通过成像卫星调度，在 综合考虑卫星资源能力和成像任务要求的基础上，将资源分配给相互竞争的多个 任务，并确定各任务的起止时间，以排除不同任务之间的资源使用冲突，充分发 挥成像卫星系统的能力，并最大化满足用户的需求。 目前，我国在卫星应用方面采用的主要是单星任务管理模式，即每颗卫星及 其应用系统自成体系，由各自专门的机构负责管理，相互之间缺乏协调和配合。 随着卫星技术和信息技术的发展，成像卫星的数量和种类将逐步增多，成像任务 的需求量也将快速增加，成像任务类型更加复杂多样，对成像任务的时效性、准 确性要求将更加严格，任务管理的复杂度也将大大增加，现有的各卫星独立运行 管理的工作模式显然已无法满足未来的需要。此外，成像卫星对地面目标( 包括 陆地和海洋) 实施观测活动，具有观测范围大、时效性好、不受国界和地理条件 限制、运行时间长等特点。但是，成像卫星有其特殊的运动规律，无法长时间在 目标上空盘旋飞行，只能周期性的对目标实施观测，同时成像卫星有效载荷在使 用方法和容量上也有很多限制。因此，为了充分发挥成像卫星资源的效益，满足 信息化条件下的快速信息获取需求，迫切需要把多颗成像卫星资源作为相互协作 配合的整体进行一体化考虑，对成像卫星调度问题进行研究。 虽然目前已经有一些有关成像卫星任务调度的相关理论研究和软件系统，但 其研究重点主要局限在确定性调度领域，很少考虑在实际的卫星应用过程存在的 不确定性因素，因此不能很好地满足我们的实际需要。在实际的成像卫星规划调 第l 页 国防科学技术大学研究生院博士学位论文 度系统中，存在着很多不确定性因素，如新任务的插入、已安排任务的取消、任 务属性的改变、天气的变化、卫星资源状态的变化等。由于不确定性因素的存在， 调度方案在执行过程中常常会由于各种扰动而无法顺利执行下去，需要对调度方 案及时地进行调整。例如，由于卫星资源自身原因( 如遥感器失效、卫星失控等) 或者环境原因( 加被敌方干扰等) ，卫星资源的状态将发生变化，原先在调度方 案中已安排的部分任务无法顺利执行，需要对调度方案及时地进行调整，给这些 受影响的任务重新分配资源，以更好地满足用户需求。因此，有必要研究不确定 条件下的成像卫星调度问题。 目前，对不确定条件下的成像卫星调度问题的研究还比较少，主要集中在动 态调度领域。动态调度采用反应式调度策略，首先生成一个初始最优的调度方案， 在调度方案执行的过程中，当扰动发生时对调度方案进行动态调整。在进行调度 方案的动态调整时，不仅希望保持调度方案的收益尽可能好，而且希望新老调度 方案的差异尽可能小【5 1 1 6 1 。上述要求一方面与动态调整的方法有关，另一方面也与 调度方案的鲁棒性有很大关系。当扰动发生时，鲁棒性强的调度方案能够在调整 幅度不大、计算时间较短的情况下获得新的收益较好的调度方案。相反，鲁棒性 差的调度方案，即使其收益较好，在面临扰动时也往往难以通过小的调整获得新 的收益较好的调度方案，无法满足实际应用的要求。因此，在制定调度方案时， 需要综合考虑调度方案的收益和鲁棒性。尽管动态调度方法可以应对不同的扰动， 但由于不利用有关扰动的任何知识和信息，生成的调度方案鲁棒性不强，调度方 案往往不易调整。因此，有必要采用鲁棒性调度方法求解不确定条件下的成像卫 星调度问题。 本文采用鲁棒性调度方法，将成像卫星鲁棒性调度分为鲁棒性调度方案生成 和鲁棒性调度方案动态调整两个阶段。在鲁棒性调度方案生成阶段，以调度方案 收益指标和鲁棒性指标为优化目标，获得一个综合考虑收益和鲁棒性的调度方案。 在鲁棒性调度方案动态调整阶段，当面临扰动时，既要保证调整后的新调度方案 收益尽可能好，又要保证与原调度方案的差异尽可能小。采用鲁棒性调度方法求 解不确定条件下的成像卫星调度问题，可以保证调度方案在面临各种扰动时仍然 能够获得较好的收益，满足用户和决策者的需求。本文针对不确定条件下的成像 卫星调度问题的特点，对成像卫星鲁棒性调度方法进行了研究，提出了成像任务 收益的计算方法和基于邻域的鲁棒性指标，建立了成像卫星鲁棒性调度模型；设 计了基于偏好的分层多目标遗传算法，提出了时间约束和能量约束的相关概念， 给出了遗传操作的可行性分析和参数更新方法；分析了成像卫星鲁棒性调度方案 动态调整问题，在对动态调度问题进行任务划分的基础上，把成像卫星鲁棒性调 度方案动态调整问题统一用插入任务的成像卫星动态调度问题进行描述；建立了 第2 页 国防科学技术大学研究生院博士学位论文 成像卫星动态调度模型，提出了求解该模型的动态插入任务启发式求解算法。在 对成像卫星鲁棒性调度方法进行研究的基础上，设计实现了成像卫星规划调度系 统，并针对一个应用实例研究了具体的求解过程。对成像卫星鲁棒性调度方法及 应用的研究有助于将成像卫星调度理论研究和实践应用相结合，具有重要的理论 意义和实际应用价值，已经逐渐引起人们的关注和研究兴趣。基于本文的研究成 果已经在成像卫星任务规划和调度的相关项目中得到部分应用，对充分发挥成像 卫星系统资源能力和辅助决策者进行科学合理的调度决策起到了重要作用。 1 2 国内外研究现状 1 2 1 成像卫星调度问题研究现状 对成像卫星调度问题的研究主要集中在模型和算法两个方面。为便于阐述， 本文分别对成像卫星调度问题的模型和算法研究进行回顾和总结。 ( 1 ) 模型研究 法国欧空局的b e n s a n a r 7 】等人研究了s p o t 5 卫星的日常调度问题，分析了2 0 个具有代表性的问题，分别建立了整数规划模型和基于加权约束满足问题( v a l u e d c o n s t r a i n ts a t i s f a c t i o np r o b l e m ) 的调度模型。法国的v a s q u e z 8 等人也研究了s p o t 5 卫星的日常调度问题，将问题映射为背包问题，建立了背包问题的约束满足问题 模型。法国的g a b r e l 9 噜人基于图论和数学规划方法讨论了类似s p o t 5 的单颗卫 星日常调度问题，建立了整数规划数学模型。美国加州大学的s o n g 1 0 等人研究了 单颗对地观测卫星在一个地区内有多个相互冲突的任务需求时如何选择一个合适 的场景，使每个可见时间窗的收益最大，为此他建立了非线性规划模型。美国的 p e n l b e 哟n 【1 1 】【1 2 】等人建立了约束满足问题模型，使用i l o gs o l v e r s c h e d u l e r 执行基 于约束传播的求解机制，并以此开发出商业化卫星调度系统g r e a s 。美国的 w o l f e 1 3 1 等人研究了每个任务只有一个可行时间窗口情况下的卫星调度问题，将卫 星调度问题映射为带时间窗约束的背包问题，并建立了相应的整数规划模型。 h 秭s o n 【1 4 】考虑了卫星侧视等约束条件，建立了整数规划模型。加拿大的n i c h o l a s l l 5 1 等人将单星调度问题看作是单机调度问题，建立了相应的整数规划模型。 以上理论研究主要针对单星调度问题，大都基于一些简化模型，不考虑某些 实际的约束条件。其中b e n s a n a 7 】和v a s q u e z 8 】等人考虑了存储容量的限制，但是没 有考虑数据传输任务，g a b r e l 9 1 、p e m b e r t o n 【1 1 】【1 2 1 、w o l f e 1 3 1 和n i c h o l a s 1 5 】等人都没 有考虑存储容量的限制以及数据传输任务。 随着成像卫星的数量和种类的逐步增多，成像任务的需求量也将快速增加， 任务类型更加复杂多样。为了充分发挥成像卫星资源的效益，需要把多颗成像卫 第3 页 国防科学技术大学研究生院博士学位论文 星资源作为相互协作配合的整体进行一体化考虑，对成像卫星调度问题进行研究。 美国弗吉尼亚大学的b u r r o w b r i d g e 1 6 】、美国国家航空航天管理局( n a s a ) 的 g l o b u s 1 7 1 、f r a n k 1 8 】和m o r r i s 1 9 】【2 0 】等人从理论上探讨了多颗卫星联合调度问题。 b u r r o w b r i d g e 1 6 】在其硕士论文中讨论了如何对地面测控资源进行优化分配，使其满 足多颗成像卫星的测控需求，在他的调度模型中没有考虑成像需求、图像获取和 下传等因素。g l o b u s 1 1 刀等在文献中讨论了一般的成像卫星调度问题，在他的研究 中考虑了任务需求的优先级、以及每颗成像卫星具有多个遥感设备资源的约束条 件，但没有考虑卫星的存储容量限制，下传数据等因素，在文中也没有给出具体 的模型表示以及算法实现的细节。不同于前面两位学者，f r a n k 1 8 】等人的研究考虑 了成像卫星调度问题中的大多数约束条件，如任务需求的优先级、卫星存储容量 限制、数据下传的速率限制等约束，并给出了一种基于约束的模型表示和描述方 法。然而在f r a n k 的模型中，所有的任务需求在调度之前必须声明其需求的资源。 从文献介绍来看，f r a n k 的模型求解算法研究工作还没有完全完成，文中给出的算 法还只能对一些小规模的调度问题进行处理。美国的一份2 0 0 3 年度的a d 报告f 2 l 】 在关于情报侦察任务规划问题的研究中，不仅试图考虑多种多颗成像卫星，还试 图同时考虑对来自陆、海、空等更多种成像手段的联合任务规划。该报告初步设 计了一个能够描述使用多种侦察手段进行联合侦察的数学模型，并给出了三个优 化目标，即最小化未完成的侦察任务数，最小化侦察设备的空闲时间，以及最小 化未达到任务要求的最小分辨率的差值。但该文献在给出了一个相当复杂的数学 模型之后，并没有给出相应的有效求解算法。 国内方面，中国电子科技集团公司第五十四研究所 2 2 1 1 2 3 】针对单颗卫星的日常 调度设计开发了卫星照相规划管理软件，综合用户需求、轨道特性、有效载荷特 性、信息传输机制等条件，利用可视化的分析决策设计思路实行对卫星照相安排 的规划控制。该照相规划管理软件依靠规则进行决策分析和照相规划，软件中时 间精确到秒量级。该软件为卫星调度人员提供了一个有决策分析功能的作业界面， 能够根据调度人员安排照相任务或撤销照相安排的动作计算出相关的目标、跟踪 接收时段并相应地修改显示状态。然而该软件同具体卫星相关，卫星只执行星下 点照相，不考虑遥感器姿态调整，也不考虑区域目标的侦察需求，而且卫星成像 计划的编制工作主要是依靠调度人员手工进行。中国科学院空间科学与应用研究 中心的代树武等人【2 4 1 1 2 5 】【2 6 1 对卫星运行中的自主控制技术及对地观测卫星的智能规 划和调度技术进行了初步研究，提出了卫星模型、推理机支持下的智能规划与调 度技术结构和采用分层a g e m 控制的自主控制系统，主要用于将卫星成像计划分 解成比较详细的控制指令序列，没有考虑卫星成像计划的编制过程。 贺仁杰博士【2 7 】在其博士学位论文中对面向点目标的成像侦察卫星调度问题进 第4 页 国防科学技术大学研究生院博士学位论文 行了初步的研究和探讨，他把成像侦察卫星调度问题看作是一个有时间窗口约束 的多机调度问题，给出了问题的混合整数规划和约束满足问题两种模型以及相应 的不同求解算法。李菊芳博士【2 8 】进一步考虑了数据存储和下传的情况，采用约束 规划混合建模思想，建立了面向点目标的成像侦察卫星调度问题混合约束规划模 型。张帆博士 2 9 】在其博士学位论文中对面向点目标的单星调度问题进行了分析， 采用图论思想建立了卫星成像多目标最短路径问题模型。阮启明博士p u j 研究了面 向区域目标的观测活动构造方法，提出了网格空间的概念与构造方法，并在此基