（管理科学与工程专业论文）多星多载荷联合调度问题研究.pdf

， 乩： ： 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意。 学位论文题目：垒星垒戴煎珐佥调廑间题盟究 学位论文作者签名：4 三￥灶 日期： 哆年 ，2 ，月f 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文作者签名：z 塾里! 兰 作者指导教师签名： 日期： 吵年，二月f 日 日期： 7 年，二月日 ， 国防科学技术人学研究生院硕十学伉论文 目录 摘要i a b s t r a c t i i 第一章绪论1 1 1 论文背景与研究意义1 1 2 国内外研究现状及发展趋势2 1 2 1 成像卫星的发展现状2 1 2 2 单星调度问题研究现状3 1 2 3 多星调度问题研究现状5 1 2 4 软件系统8 1 2 5 研究现状评述9 1 3 论文的主要研究工作和创新点9 1 3 1 论文主要研究内容9 1 3 2 论文主要工作与创新1 0 1 4 论文组织结构1 1 第二章多星多载荷联合调度问题1 2 2 1 成像卫星的工作原理1 2 2 1 1 成像卫星遥感器1 2 2 1 2 成像过程分析1 4 2 1 3 成像卫星的数据传输1 5 2 2 多星多载荷联合调度问题分析1 7 2 2 1 多星多载荷联合调度问题约束分析1 7 2 2 2 多星多载荷联合调度问题基本输入输出分析2 1 2 2 3 问题基本假设及求解过程2 4 2 2 4 多星多载荷联合调度问题特点2 8 2 3 基于阶段优化的多星多载荷联合调度问题模型3 0 2 3 1 模型的符号定义及变量定义3 0 2 3 2 观测调度阶段的目标函数及约束条件3 3 2 3 3 数传调度阶段的目标函数及约束条件3 5 2 3 4 约束满足模型的特点3 7 2 4 本章小结3 8 第1 页 国防科学技术人学研究生院硕十学位论文 第三章多星多载荷联合调度问题求解的启发式算法3 9 3 1 启发式算法概述4 l 3 1 1 启发式算法的定义4 l 3 1 2 启发式算法的分类4 l 3 2 基于规则的启发式构造算法4 2 3 2 1 观测任务分配调度基本规则4 3 3 2 2 多任务冲突消解规则4 4 3 2 3 观测资源冲突消解4 4 3 2 4 观测调度阶段的算法4 6 3 2 5 数传任务冲突消解5 l 3 2 6 数传调度阶段的算法5 2 3 3 算法性能测试与结果分析5 3 3 3 1 测试算例的生成5 3 3 3 2 试验参数设置5 4 3 3 3 试验结果与分析5 6 3 4 本章小结5 9 第四章多星多载荷任务调度系统的设计与实现6 0 4 1 多星多载荷任务调度系统的总体框架6 0 4 1 1 系统设计原则6 0 4 1 2 系统总体框架6 1 4 2 多星多载荷任务调度系统实现6 3 4 2 1 采集任务单接收与处理子系统6 3 4 2 2 卫星及地面站资源管理子系统6 4 4 2 3 多星任务调度子系统6 5 4 2 4 单星计划编排子系统6 6 4 2 5 任务调度效能评估子系统6 8 4 2 6 计划仿真推演子系统6 9 4 3 本章小结7 0 第五章结论与展望7 1 5 1 本文总结7 l 5 1 1 多星多载荷联合调度问题建模研究7 l 5 1 2 基于规则的启发式构造算法研究7 l 5 1 3 多星多载荷任务调度系统的设计与实现7 2 5 2 进一步的研究与展望7 2 第1 i 页 围防科学技术人学研究牛院硕十学位论文 至殳访j 7 4 参考文献7 5 附录a 攻读硕士学位期间发表和录用的论文8 0 附录b 攻读硕士学位期间参加科研情况8 1 第1 i i 页 国防科学技术人学研究生院硕十学何论文 表目录 表2 1 模型中符号定义3 l 表3 1 观测任务情况表5 5 表3 2 观测资源表5 6 表3 3 观测任务的调度结果5 7 第1 v 页 国防科学技术入学研究生院硕十学位论文 图目录 图2 1 缝隙式和全景式相机的成像原理示意图1 3 图2 2 光机扫描仪和推扫式扫描仪的成像原理示意图1 4 图2 3 卫星成像示意图15 图2 4 卫星直拍直传示意图16 图2 5 卫星存储转发示意图1 6 图2 6 成像侧视角与最大侧视角度2 2 图2 7 多星多载荷联合调度问题的基本求解过程2 6 图2 8 多星多载荷联合调度预处理过程2 7 图3 1 多星多载荷联合调度问题求解框架4 0 图3 2 观测任务调度整体流程图4 6 图3 3 观测任务星i 日j 分配的流程图4 8 图3 4 观测任务遥感器间分配的流程图5 0 图3 6 观测任务分布示意图5 6 图4 1 多星多载荷任务调度系统结构图6 1 图4 2 卫星任务调度系统整体流程图6 2 图4 3 采集任务单接收与处理子系统组成图一6 3 图4 4 卫星及地面站资源管理子系统组成图：一6 4 图4 5 多星任务调度子系统流程6 5 图4 6 多星任务调度子系统主界面6 6 图4 7 单星计划编排处理流程图6 7 图4 8 任务调度效能评估子系统组成图6 8 图4 9 计划仿真推演示意图6 9 第v 页 围防科学技术大学研究生院硕十学仲论文 摘要 成像卫星是一类重要的从太空获取地面信息的对地观测卫星，在环境监测、 自然灾害预防等领域发挥了重要作用。近年来，随着成像卫星数量的增多、性能 的提高，多星联合以及单星搭载多个载荷( 可见光、红外、s a r 等) 已经成为成 像卫星发展应用的新趋势，各个载荷在物理上相对独立，在实际应用中又相互协 调，使得成像卫星具有多种观测模式。在每一种观测模式下，卫星的具体约束各 不相同，这使得成像卫星的调度问题变得更加复杂。多星多载荷联合调度问题就 是在满足各个卫星的成像约束条件下，综合各个遥感器的观测能力，最终制定相 应的观测、数传方案，以达到最大化满足用户观测需求的目的。 本文以应用需求为指导，在对多星多载荷联合调度过程及约束条件分析的基 础上，从约束建模及启发式调度规则设计的角度对多星多载荷联合调度方案生成 中的关键问题进行了深入研究，本文的主要工作和创新如下： ( 1 ) 建立了基于阶段优化的多星多载荷联合调度模型 本文分析了成像卫星的工作原理，卫星成像的约束条件以及多星多载荷联合 调度问题的基本输入输出，分析了问题的基本调度流程，指出了多星多载荷联合 调度问题的特点和难点。在综合考虑多星、多载荷、多地面站调度的观测、存储 和数传等环节的基础上，把问题分为观测调度阶段和数传调度阶段，分别给出了 优化目标和约束条件，建立了基于阶段优化的多星多载荷联合调度模型。 ( 2 ) 提出了基于规则的启发式构造算法 针对实际应用需求中多星多载荷联合调度方案生成的时效性要求以及问题最 优解迭代搜索算法的巨大时间耗费，在观测调度阶段，设计了多星之间的任务调 度分配规则和多遥感器之间的任务调度分配规则，进行了多任务冲突消解、多星 观测冲突消解、单星重访冲突消解和单星多载荷冲突消解；在数传调度阶段，设 计了数传任务冲突消除规则。在此基础上，采用了基于规则的启发式构造算法对 问题进行求解。并通过随机测试算例，验证了模型和算法的正确性和有效性。 ( 3 ) 建立了多星多载荷任务调度系统 在调度模型、基于规则的启发式算法的研究基础上及工程应用的需求，设计 实现了多星多载荷任务调度系统。 主题词：多星，多载荷，地面站，调度，启发式 第i 页 国防科学技术人学研究生院硕十学位论文 a b s t r a c t i m a g i n gs a t e l l i t ew h i c ha c q u i r e sr e m o t es 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 ei sa n i m p o r t a n tk 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 i tp l a y e di m p o r t a n tr o l e si ne n v i r o n m e n t m o n i t o r i n ga n dn a t u r a ld i s a s t e rp r e v e n t i o n r e c e n t l y ，w i t hi n c r e a s i n gs a t e l l i t en u m b e r a n di m p r o v e ds a t e l l i t ep e r f o r m a n c e ，j o i n t s c h e d u l i n go fm u l t is a t e l l i t e sa n dm u l t i s e n s o r sa l l o c a t e di no n es a t e l l i t eb e c o m ean e ws a t e l l i t ed e v e l o p m e n ta n da p p l i c a t i o n t r e n d t h es e n s o r sm i g h tb eo fd i f f e r e n tk i n d s ，s u c ha sv i s i b l el i g h t ，i n f r a r e da n ds a r t h e s es e n s o r sa r ep h y s i c a l l yi n d e p e n d e n tw h i l eo p e r a t i o n a l l yc o o p e r a t e d a sar e s u l t ， e a c hs a t e l l i t eo w ns e v e r a lo b s e r v i n gm o d e sa n di ne a c hm o d et h ed e t a i l e do p e r a t i o n c o n s t r a i n t sd i f f e ral o t a c c o r d i n g l y ，i 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 mb e c o m e s m o r ec o m p l e x m u l t is a t e l l i t e ss c h e d u l i n gp r o b l e mi sb a s e do ni n t e g r a t e dc o n s i d e r a t i o n o fc a p a b i l i t i e so fs a t e l l i t e s ，r e m o t es e n s o r s ，a n do b s e r v a t i o nr e q u e s t sf r o mv a r i o u su s e r s t h ep r o b l e mi sa i m e dt oa l l o c a t er e s o u r c e st om u l t i p l ec o m p e t i t i v eo b s e r v i n gt a s k s w i t h o u tc o n f l i c t s ，s e td o w ns a t e l l i t e s o b s e r v a t i o np l a na n dd a t at r a n s m i s s i o np l a n i t s f i n a lg o a li st om a k ef u l lu s eo ft h er e s o u r c e sa n dm a x i m a l l ys a t i s f yu s e r s r e q u e s t s g u i d e db yt h ea p p l i c a t i o nr e q u i r e m e n t so fi m a g i n gs a t e l l i t e ，t h i st h e s i sf o c u s e so n t h em o d e lc o n s t r u c t i o na n dh e u r i s t i cr u l e d e s i g no fm u l t ii m a g i n gs a t e l l i t e s j oi n t s c h e d u l i n gp r o b l e m a l lt h er e s e a r c hi sb a s e do nt h ea n a l y s i so ft h ep r o c e s so fj o i n t s c h e d u l i n ga n di m a g i n gc o n s t r a i n t s t h em a i nw o r ka n dc o n t r i b u t i o n sa r ea sf o l l o w s ： ：，f i r s t l y ，t h i st h e s i sa n a l y s e ss a t e l l i t ei m a g i n gp r o c e d u r e ，i m a g i n gc o n s t r a i n t s ，i n p u t a n do u t p u to ft h ep r o b l e m , a s c e r t a i n st h eb a s i cs c h e d u l i n gf l o wa n dc h a r a c t e r i s t i c so f t h em u l t ii m a g i n gs a t e l l i t e sj o i n ts c h e d u l i n gp r o b l e m b a s e do ni n t e g r a t e dc o n s i d e r a t i o n o fs a t e l l i t e so b s e r v a t i o n , m e m o r ya n dd a t at r a n s m i s s i o n ，t h i st h e s i sd i v i d e st h ep r o b l e m i n t oo b s e r v a t i o ns c h e d u l i n ga n dd a t at r a n s m i s s i o ns c h e d u l i n g f o re a c hs u b - p r o b l e m ， t h e i ro b j e c t i v ef u n c t i o na n dc o n s t r a i n t sa r ed e f i n e dr e s p e c t i v e l y a l s oam a t h e m a t i c m o d e lo f m u l t ii m a g i n gs a t e l l i t e sj o i n ts c h e d u l i n gp r o b l e mi sp r e s e n t e d s e c o n d l y ，i no r d e rt os o l v et h ep r o b l e mt h i st h e s i sf o c u s e so nt h ec o n s t r u c t i o no f h e u r i s t i ca l g o r i t h m s c o n s i d e r i n gt i m er e q u i r e m e n ta n dc o m p u t a t i o nc o m p l e x i t yo ft h e p r o b l e m , t a s ka s s i g n m e n tr u l e sa m o n gm u l t is a t e l l i t e sa n dm u l t is e n s o r sa r ed e v e l o p e d t oc l e a ru pc o n f l i c t s t h e s ec o n f l i c t sc o n t a i nt a s kc o n t r a v e n t i o l l s a t e l l i t eo b s e r v a t i o n c o n f l i c t s ，s i n g l es a t e l l i t er e v i s i ta n t i n o m ya n de x c l u s i v e n e s sa m o n gm u l t is e n s o r s i nt h e p h a s eo fd a t at r a n s m i s s i o ns c h e d u l i n g ，r u l e sa r ep r o p o s e dt oc l e a ru pd a t at r a n s m i s s i o n c o n f l i c t s t h e na na l g o r i t h mb a s e do nh e u r i s t i cr u l e si sp r o p o s e dt os o l v em u l t ii m a g i n g s a t e l l i t e sj o i n ts c h e d u l i n gp r o b l e m a n das e r i e so ft e s te x a m p l e sa r ec o n s t r u c t e dt o p r o v e t h ec o r r e c t n e s sa n dv a l i d i t yo ft h ea l g o r i t h m f i n a l l y , am u l t ii m a g i n gs a t e l l i t e ss c h e d u l i n gs y s t e mi sd e v e l o p e d ，w h i c h i n c o r p o r a t e ds a t e l l i t es c h e d u l i n gm o d e l ，h e u r i s t i ca l g o r i t h ma n dd e t a i l e da p p l i c a t i o n 第i i 页 同防科学技术人学研究生院硕十学位论文 r e q u t r e m e n t k e yw o r d s ：m u l t is a t e l l i t e s ，m u l t is e n s o r s ，g r o u n ds t a t i o n ，s c h e d u l i n g ， h e u r i s t i c 第i i i 页 国防科学技术人学研究生院硕十学仲论文 第一章绪论 1 1 论文背景与研究意义 成像卫星是利用星载遥感器从太空中获取地面图像信息的对地观测卫星【，具 有覆盖范围广、运行时间长、不受国界和空域限制、无需考虑人员安全等独特优 势。成像卫星主要分为光学成像卫星和雷达成像( 微波) 卫星两大类，光学成像 卫星采用可见光、红外、多光谱相机成像，而雷达成像卫星采用s a r 遥感器进行 成像。它们各自具有不同的特点，光学成像卫星的优点是空间分辨率高，但不能 进行全天候、全天时工作。雷达成像卫星不受白天、黑夜及云雾的影响，而且具 有一定的穿透能力。目前，成像卫星在军事侦察、灾害防治、环境保护、城市规 划以及农业、气象等许多领域都发挥了重要作用，同时也得到了世界各国的高度 重视【1 5 j 。 成像卫星运行于近地轨道，可以根据用户的需求对地面目标进行观测成像。 由于成像卫星的能力有限，而用户提交的任务需求很多。因此，在成像卫星的r 常管理中，地面指挥控制系统必须根据任务请求和卫星的能力进行优化调度，制 定卫星的成像计划，并生成载荷控制指令，经地面测控设备将指令注入卫星，使 得卫星按照指令执行各种动作，并完成用户所提交的各项观测任务。 我国是世界上自然灾害最多、损失最严重的国家之一。目前，资源卫星已经 应用到了灾害防治工作中，但是由于我国现有的卫星资源数量和技术有限，资源 卫星在灾害防治工作的作用尚未得到充分体现。随着卫星数量的增加和技术的改 进，如何统筹安排卫星的使用，以最大限度发挥其作用，将是一个紧迫的问题。 目前，国内外已经对卫星任务规划问题进行了较深入的研究，形成一系列的任务 规划理论和方法。但是，目前的研究主要集中在单星、多星单载荷方面，在多星 多载荷任务规划方面的研究还比较少。由于资源卫星具有可见光、红外和s a r 等 多种不同类型观测载荷，而观测载荷的相对独立性和相互协调性，使得对于不同 的观测任务，可以采用不同的相机组合( 即采用不同的工作模式) 。这样，不仅 仅使得能够满足任务对于成像载荷的要求，还能够最大化的完成用户所提交的任 务。而解决这些问题，是一个比较复杂的过程，需要把多颗成像卫星和星上搭载 的多个遥感器统一起来，综合考虑卫星和遥感器的各种运行约束条件，合理分配 卫星和遥感器资源，安排观测任务，确定任务中各活动的起止时间，最终制定相 应的观测方案，以达到最大化满足用户观测需求的目的。 多星多载荷联合调度是卫星、星载遥感器及地面站资源分配、卫星观测调度 方案和数据回传方案编制的核心内容，它本质上是一个优化决策过程，对于更好 第1 页 国防科学技术人学研究生院硕十学何论文 地利川成像卫星、星绒遥感器及地曲站资源，优化卫星系统整体性能，发挥它们 的最大综合效益具有至关重要的作用。通过多星多载荷联合调度得到的卫星任务 执行方案将能够反映卫星及地面站资源争用、任务取舍等卫星系统的实际应用特 点。对卫星任务执行方案进行仿真并就任务完成率和资源占用率等指标进行统计， 将能够合理评估卫星系统的任务执行能力和资源负荷水平。通过变换卫星系统的 配置参数并反复进行规划调度和仿真，就可以得到对不同的卫星系统配置方案满 足具体任务的能力评估结果，从而寻求最满意的卫星系统配置方案。本文研究多 星多载荷联合调度的模型及解决问题的方法，为提高卫星系统的综合效益提供理 论支持和技术保障。 1 2 国内外研究现状及发展趋势 1 2 1 成像卫星的发展现状 由于成像卫星调度是伴随着成像卫星的发展而产生的，因此，首先简要介绍 成像卫星的发展现状【6 引。 1 9 6 0 年8 月，美国成功发射世界第一颗用于军事侦察的成像卫星，使得战争 中的侦察手段发生了质的变化，世界强国不甘落后，纷纷投入巨资，大力发展成 像卫星。美国的成像卫星技术处于世界领先地位，自1 9 6 2 年发展k h 一1 系列光学 成像卫星计划，迄今已经经历了六代，共发射了2 4 0 多颗卫星，分辨率也由原来 的3 5 米发展到现在的o 1 米。同时，也在发展雷达成像卫星，“长曲棍球”雷 达成像侦察卫星可以全天候、全天时进行观测，图像分辨率达到0 3 1 米。 前苏联俄罗斯的成像侦察卫星至今已经发展到了第七代，成像分辨率可达0 2 米。法国自1 9 8 6 年至2 0 0 2 年发射了5 颗s p o t 系列的卫星，并与欧盟其他国家 共同发展下一代高分辨率光学成像卫星，即p l e i a d e s 卫星计划。 印度于1 9 9 7 年成功发射了i r s 1 d 成像卫星，分辨率达到了5 8 米。于2 0 0 1 年发射了首颗用于军事侦察的卫星“实验评估卫星”，地面分辨率达到l 米，可 覆盖全球6 0 的区域。目前在轨有4 颗卫星，并计划发射分辨率达到0 5 米的侦察 卫星。以色列于1 9 9 5 年发射“地平线3 成像卫星以来，也发射了数颗成像卫星， 其发射的e r o s b 卫星的地面分辨率达到0 7 米。德国国防部也决定研制5 颗 s a r - l u p e 小型雷达卫星，其分辨率估计能达到0 5 米，日本、韩国等国家也在大 力发展军事及民用的成像卫星。我国已经发射了多颗成像卫星，如与巴西合作的 c b i 冱s 系列卫星，最高分辨率能够达到4 米，另外，还有用于环境监测的h j 系 列卫星等。 根据美国摄影测量与遥感协会( t h ea m e r i c a ns o c i e t yf o rp h o t o g r a m m e t r ya n d 第2 页 同防科学技术人学研究生院硕十学位论文 r e m o t es e n s i n g ，a s p r s ) 公御的数掘一j ，仪在民用成像卫星方面，已有1 3 个国家 的4 1 颗中高分辨率的卫星在轨运行，至2 0 11 年，估计会达到2 1 个国家的6 9 颗 卫星。这些成像卫星在军事、民用方面发挥了重要作用，其观测能力越来越强， 地面分辨率越来越高。 伴随着成像卫星的发展，成像卫星调度也逐渐引起重视。目前，国内外已经 开展了很多成像卫星调度的研究。按照任务类型分类，可以分为面向点目标的成 像卫星调度与面向区域目标的成像卫星调度；按照卫星数量分类，可以分为单星 调度和多星调度；按照星上搭载的载荷数量分类，可以分为单载荷调度和多载荷 调度。由于单星调度和多星调度存在较大的差别，因此，下面按照卫星数量对成 像卫星调度进行回顾与总结。 1 2 2 单星调度问题研究现状 在模型研究方面，法国欧空局的b e n s a n a l l 0 1 等人研究了s p o t 5 卫星的同常调 度问题，分析了2 0 个具有代表性的问题，建立了整数规划模型。法国的v a s q u e z t 1 等人也研究了s p o t 5 卫星的日常调度问题，将问题映射为背包问题，建立了背包 问题的约束满足问题模型。法国的g a b r e l t l 2 1 等人基于图论和数学规划方法讨论了 类似s p o t 5 的单颗卫星同常调度问题，建立了整数规划数学模型。美国加州大学 的s o n g j l 3 】等人研究了单颗对地观测卫星在一个地区内有多个相互冲突的任务需求 时如何选择一个合适的场景，使每个可见时间窗口的收益最大，为此他建立了非 线性规划模型。1 美国的p e m b e r r t o n 【1 4 1 5 1 等人建立了约束满足问题模型，使用i l o g s o l v e r s c h e d u l e r 执行基于约束传播的求解机制，并以此开发出商业化卫星调度系 统g r e a s 。美国的w o l f e t l 6 1 等人研究了每个观测活动只有一个可见时间窗口情况 下的卫星调度问题，将卫星调度问题映射为带时间窗约束的背包问题，并建立了 相应的整数规划模型。加拿大的n i c h o l a s t l 7 】等人将单星调度问题看作是单机调度问 题，建立了相应的整数规划模型。 国防科技大学的张帆博士【1 8 1 在其博士学位论文中对面向点目标的单星调度问 题进行了分析，采用图论思想建立了卫星成像多目标最短路径问题模型。 国防科技大学的伍崇友硕士【l9 j 在其硕士学位论文中对面向区域目标普查的单 星调度问题进行了分析，建立了面向全球多个区域普查之卫星日常调度问题的混 合整数规划模型。 以上理论研究大都是基于一些简化模型，不考虑某些实际的约束条件。其中 b e n s a n a l l 0 】和v a s q u e z i 1 等人考虑了存储容量的限制，但是没有考虑数据传输任务， g a b r e l t 挖1 、p e m b e r t o n t l 4 , 1 5 1 、w o l f e t l 6 1 和n i c h o l a s t l 7 i 等人都没有考虑存储容量的限制 以及数据传输任务。 第3 页 国防科学技术人学研究生院硕十学1 1 i 7 ：论文 在渊度算法方曲，求解埘地观测卫星润度问题的一般力法是采用贪婪规则选 取优先级最大的观测需求进行安排，如果该观测需求不能被安排，则选取下一个 观测需求。a s t e r 调度系统f 2 0 1 正是采用了这一求解算法。 p e m b e r t o n 提出了一种对大规模问题迭代求解的方法【1 5 1 。他的基本思想是首先 按照某种规则对所有的观测需求进行排序，然后将所有的观测需求分组，再按分 组顺序对每组中的观测需求都采用完全算法求得最优解。在调度过程中，前面分 组的调度结果将作为后面分组调度的约束条件。 w o l f e 和s o r e n s e n 在文献中比较了三种不同算法【1 6 1 ：贪婪算法、具有前看功能 的贪婪算法以及遗传算法。在贪婪算法中，所有的观测需求按照优先级进行排序， 然后按照优先级顺序依次选择观测需求，将该观测需求安排到满足其约束的最好 时间点。具有前看功能的贪婪算法是在选择下一个观测需求时考虑其对其他观测 需求的影响。在遗传算法中定义了一些交叉、变异算子，允许撤销已经安排的观 测需求，从而得到一个较好的调度方案。在文中实验证明，采用遗传算法可以较 大幅度的改进贪婪算法的调度结果。 在l a n d s a t7 调度系统【2 1 1 中首先按照最早结束时间贪婪安排所有的观测需求， 然后基于优先级替换己安排的观测需求和未安排的观测需求。 s h e r w o o d l 2 2 】等人采用了a s p e n 系统对e o 1 卫星的日常活动进行调度和安排。 a s p e n 是n a s a 用于航天器任务规划的软件系统。在a s p e n 中采用了一种基于 局部邻域搜索( l o c a ls e a r c h ) 的算法，该算法的基本思想是首先生成一个初始调 度方案，然后通过调整变量取值不断消解冲突。 在s p o t 5 调度问题中，b e n s a n a 等人 1 0 , 2 3 , 2 4 】分别比较了完全搜索算法( 深度优 先搜索、动态规划、r u s s i a nd o l ls e a r c h ) 和非完全搜索算法( 贪婪搜索、禁忌搜 索) 在不同规模问题实例下的计算性能。实验证明，当问题不大时，采用完全搜 索算法可以较短的时间内得到一个最优解，但当问题规模较大时，采用完全搜索 算法就不能在合理的时间内得到问题的解，而禁忌搜索可以在合理的时i b j 内得到 问题的一个满意解。v e r f a i l l i e t 2 5 加1 和v a s q u e s t l l l 等在研究中也得到了类似的结论。 l e m a i t r e 2 6 1 等人在对一个敏捷卫星( a g i l es a t e l l i t e ) 调度问题研究中还比较了 约束规划方法和局部邻域搜索算法。他们发现，采用约束规划方法具有更强的灵 活性和适应性，而局部邻域搜索算法的求解效率和求解效果更好。 张帆博士【1 8 1 基于遗传算法针对单星单轨道圈次的任务规划问题提出了多目标 最短路径优化算法，其基本思想是同时求解多条优化成像路径，然后通过预定义 的策略筛选出最终调度方案。 伍崇友1 1 9 】根据问题的特点，在介绍启发式局部搜索的相关概念的基础上，给 出了求解混合整数规划模型的基于任务分组的贪婪式搜索算法。 第4 页 国防科学技术人学研究生院硕十学位论文 1 2 3 多星调度问题研究现状 多星调度研究比较丰富，为了便于阐述，本文分别从模型及算法两个方面进 行总结。 1 2 3 1 模型研究 国外的有美国弗吉尼亚大学的b u r r o w b r i d g e l 2 7 1 和美国国家航空航天管理局 ( n a t i o n a la e r o n a u t i c sa n ds p a c ea d m i n i s t r a t i o n ，简称n a s a ) 的g l o b u s f 2 8 l 和f r a n k l 2 9 1 等人从理论上探讨了多颗对地观测卫星调度问题。b u r r o w b r i d g e t 2 7 】在其硕士论文中 讨论了如何对地面测控资源进行优化分配，使其满足多颗对地观测卫星的测控需 求，在他的调度模型中没有考虑观测需求、图像获取和下传任务等因素。g l o b u s l 2 8 l 等在文献中讨论了一般的多颗对地观测卫星调度问题，在他的研究中考虑了任务 需求的优先级、以及每颗观测卫星具有多个遥感设备资源的约束条件，而没有考 虑卫星的存储容量限制，下传数据等因素，在文中也没有给出具体的模型表示以 及算法实现的细节。不同于前面两位学者，f r a n k t 2 9 】等人的研究考虑了对地观测卫 星调度问题中的大多数约束条件，如观测需求的优先级、卫星存储容量限制、数 据下传的速率限制等约束，并给出了一种基于约束的模型表示和描述方法。但是 在f r a n k 的模型中，所有的观测需求在调度之前必须声明其需求的资源。从文献介 绍来看，f r a n k 的模型求解算法研究工作还没有完全完成，文中给出的算法还只能 对一些小规模的调度问题进行处理。 国内在多星联合调度领域展开研究的主要有中国科学院空间科学与应用研究 中一心1 3 0 , 3 1 , 3 羽、国防科技大学1 3 3 - 4 3 1 等单位。 中国科学院空间科学与应用研究中心的代树武等人【3 0 3 2 1 对卫星运行中的自主 控制技术及对地观测卫星的智能规划和调度技术进行了初步研究，提出了卫星模 型、推理机支持下的智能规划与调度技术结构和采用分层a g e n t 控制的自主控制 系统，主要用于将卫星成像计划分解成比较详细的控制指令序列，没有考虑卫星 成像计划的编制过程。 国防科技大学的贺仁杰博士【3 3 】在其博士学位论文中对面向点目标的成像侦察 卫星调度问题进行了初步的研究和探讨，他把多星联合调度问题看作是一个有时 间窗口约束的多机调度问题，给出了问题的混合整数规划和约束满足问题两种模 型以及相应的不同求解算法。他假设卫星的存储容量足够大或中继卫星实时可用， 并因此忽略了与数据存储和数据下传相关的约束。 国防科技大学的李菊芳博士【3 4 1 进一步考虑了数据存储和下传的情况，采用约 束规划混合建模思想，建立了面向点目标的成像侦察卫星调度问题混合约束规划 模型。 第5 页 国防科学技术大学研究生院硕十学何论文 国防科技大学的刘洋博士【3 5j 基f 动态约束满足问题理论和方法，讨论了对卫 星侦察任务进行重调度的问题，给出了基于动态约束满足的多星联合调度问题的 概念模型，在卫星的存储容量足够大或中继卫星实时可用的假设前提下，结合卫 星资源故障和新任务添加的两类实际问题，建立了调度模型。 国防科技大学的李曦硕士【3 6 1 针对区域目标建立了时i 、日j 覆盖率优先与空间覆盖 率优先的两类模型。 国防科技大学的王沛硕士【3 7 】探索了面向点目标的观测活动构造方法，提出了 侦察任务需求度和时i 日j 窗口争用度的概念，并在此基础上，明确了需要考虑的约 束条件，建立了面向点目标的多星联合侦察调度问题的约束优化模型。 国防科技大学的阮启明博士【3 8 l 探索了面向区域目标的观测活动构造方法，提 出了网格空间的概念与构造方法，并在此基础上，明确了需要考虑的约束条件， 建立了面向区域目标的成像侦察卫星调度问题模型。 国防科技大学的王均博士【3 9 】在研究中针对星地调度问题给出了基于全局优化 的数学规划模型和基于阶段优化的有向图模型。他在考虑地面站调度的时候假设 多星对地面站的访问没有冲突，把卫星对地面站的访问看成是一种特殊的观测任 务，与其余的观测目标统一调度。 国防科技大学的王军民博士【加l 在对影响成像任务收益的主要影响因素进行 分析的基础上，提出了成像任务收益的计算方法和基于邻域的鲁棒性指标，分析 了问题的主要约束条件，建立了成像卫星鲁棒性调度模型。 国防科技大学的白保存博士在深入分析卫星对点、区域目标的调度特点以 及任务合成特性的基础上，提出了区域目标动态分解方法。将点目标与区域目标 统一为元任务，采用合成任务描述任务合成观测活动，并分析了合成任务与元任 务的关系，在问题约束的基础上，建立了考虑任务合成的成像卫星调度模型。 国防科技大学的慈元卓博士1 4 2 l 针对离线任务规划模式，提出了移动目标分布 离线更新和转移的方法，对未来时刻目标的分布进行估计，获得目标分布的先验 概率。在目标分布先验概率的基础上，采用不确定序贯决策求解框架部分可 观马尔可夫决策过程( p o m d p ) 建立了多星离线任务规划模型。针对在线任务规划 模式，采用了预测模型控制理论和方法，提出了多星在线任务规划的闭环控制策 略，并建立了基于预测模型控制( m p c ) 的面向移动目标搜索的多星在线滚动任务规 划模型。 国防科技大学的孙凯硕士【4 3 】分析了成像卫星的工作原理，卫星成像的约束条 件以及成像卫星星地联合调度问题的基本输入输出，分析了问题的基本调度流程， 在综合考虑多星多地面站调度的观测、存储和回传等环节的基础上，把问题分为 观测调度阶段和回传调度阶段，分别给出了优化目标和约束条件，建立了基于阶 第6 页 围防科学技术人学研究乍院硕十学位论文 段优化的成像卫星星地联合凋度模型。 1 2 3 2 调度算法 f r a n k f 2 9 1 等人在模型求解中则基于e u r o p a 系统实现了