（管理科学与工程专业论文）基于启发式算法的成像卫星星地联合调度问题研究.pdf

国防科学技术大学研究生院硕士学位论文 摘要 成像卫星是一类重要的从太空获取地面信息的对地观测卫星，已经在军事经 济等领域发挥了重要作用。成像卫星星地联合调度，就是在综合考虑卫星、遥感 器以及地面站等资源的能力和不同用户的任务需求的基础上，将资源无冲突的分 配给相互竞争的多个任务，最终制定相应的观测调度方案和回传调度方案，以达 到提高资源使用效率和最大限度满足用户观测需求的目的。 本文紧密结合成像卫星在现代社会的应用需求，研究成像卫星星地联合调度 的原理与方法，着重对问题的模型和优化求解算法进行研究。本文的主要工作和 创新如下： 首先，本文分析了成像卫星的工作原理，卫星成像的约束条件以及成像卫星 星地联合调度问题的基本输入输出，分析了问题的基本调度流程，指出了问题的 主要特点和难点。在综合考虑多星多地面站调度的观测、存储和回传等环节的基 础上，把问题分为观测调度阶段和回传调度阶段，分别给出了优化目标和约束条 件，建立了基于阶段优化的成像卫星星地联合调度模型。 其次，本文重点研究了启发式算法在成像卫星星地联合调度问题中的应用， 分析了成像卫星星地联合调度问题求解的启发式规则，采用贪婪随机自适应搜索 算法( g r a s p ) 求解模型的观测调度阶段，设计了两种基于不同贪婪规则的启发 式构造算法来求解模型的回传调度阶段。本文对g r a s p 算法做出了一定的改进， 在其初始解的构造阶段设计了定长受限候选列表和变长受限候选列表两种策略， 在邻域搜索阶段结合模拟退火算法来搜索更好的解。 最后，分析了成像卫星任务调度系统在实际中的应用需求，指出了成像卫星 任务调度系统的应用分为对卫星日常工作计划的安排和对卫星系统顶层设计的支 持两个层次。在调度模型和算法研究的基础上，设计实现了成像卫星任务调度系 统。 主题词：成像卫星，地面站，调度，启发式 第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 l l 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 nm i l i t a r y r e c o n n a i s s a n c ea n de c o n o m y m u l t ii m a g i n gs a t e l l i t e sa n dg r o u n ds t a t i o n sj o i n t s c h e d u l i n gp r o b l e mi sd e f i n e da s ：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 no ft h ec a p a b i l i t i e s o fs a t e l l i t e s ，r e m o t es e n s o r s ，g r o u n ds t a t i o n s ，a n dt h eo 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 s u s e r s ，a l l o c a t et h 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 sw i t h o u tc o n f l i c t s ， s e td o w nt h es 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 ni no r d e rt om a k ef u l l u 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 yt h er e q u e s t so ft h eu s e r 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 et h e o r i e sa n dm e t h o d so fm u l t ii m a g i n gs a t e l l i t e sa n dg r o u n ds t a t i o n sj o i n t s c h e d u l i n g ，e m p h a s i z e so nt h em a t h e m a t i cm o d e la n da l g o r i t h m t h em a i nw o r ka n d c 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 ，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 sa n dg r o u n ds t a t i o n 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 n i n t e g r a t e dc o n s i d e r a t i o no 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 s t h e s i sd i v i d e st h ep r o b l e mi 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 ， d e f i n e so b je c t i v ea n dc o n s t r a i n t so f e a c hp a r t ，p r e s e n t sam a t h e m a t i cm o d e lo ft h em u l t i i m a g i n gs a t e l l i t e sa n dg r o u n d s t a t i o n sj o i n ts c h e d u l i n gp r o b l e m ：s e c o n d ，t h i st h e s i sf o c u s e so nh e u r i s t i ca l g o r i t h m si no r d e rt os o l v et h ep r o b l e m a n dp r o v i d e ss o m eh e u r i s t i cr u l e s g r e e d yr a n d o ma d a p t i v es e a r c hp r o c e d u r e ( g r a s p ) i su s e dt os o l v et h eo b s e r v a t i o ns c h e d u l i n gp a r t t w oh e u r i s t i cc o n s t r u c t i n ga l g o r i t h m s b a s e do nr e s p e c t i v eg r e e d yr u l e sa r ed e s i g n e dt os o l v et h ed a t at r a n s m i s s i o ns c h e d u l i n g p a r t s o m ei m p r o v e m e n t so fg r a s pa r em a d et oo b t a i nb e t t e rs o l u t i o n s ，i ni t s c o n s t r u c t i o np h a s e ，t w os t r a t e g i e so ff i x e dr e s t r i c t e dc a n d i d a t el i s ta n dn o n f i x e d r e s t r i c t e dc a n d i d a t el i s ta r ed e s i g n e d ，a n ds i m u l a t e da n n e a l i n ga l g o r i t h mi su s e di ni t s l o c a ls e a r c hp h a s e f i n a l l y ，i ta n a l y z e st h ea c t u a lr e q u i r e m e n t so ft h ea p p l i c a t i o nf o rt h e s a t e l l i t e m i s s i o np l a n n i n gs y s t e m t h e ni tp o i n t so u tt h et w ol e v e l so ft h ea p p l i c a t i o no ft h e s y s t e m ：t os u p p o r tt h ed a i l yw o r kp l a na n dt h et o pl e v e ld e s i g no ft h es a t e l l i t es y s t e m o nt h eb a s i so ft h er e s e a r c ho nt h em o d e la n da l g o r i t h m ，t h i st h e s i sd e s i g n sa n dr e a l i z e s am i s s i o np l a n n i n gs y s t e mo fi m a g i n gs a t e l l i t e s k e yw o r d s i m a g i n gs a t e l l i t e ，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 页 国防科学技术大学研究生院硕士学位论文 表目录 表4 1 测试算例参数表5 4 表4 2 观测调度阶段求解结果表5 4 表4 3 回传调度阶段求解表5 5 一 第1 v 页 国防科学技术大学研究生院硕士学位论文 图目录 图2 1 光机扫描仪和推帚式扫描仪的成像原理示意图1 1 图2 2 卫星成像示意图1 2 图2 3 卫星直拍直传示意图1 3 图2 4 卫星存储转发示意图1 3 图2 5 成像卫星星地联合调度流程。2 2 图2 6 回传活动次数对数据采集活动的影响2 4 图3 1g r a s p 算法基本过程的伪代码3 5 图3 2g r a s p 初始解构造的伪代码：3 6 图3 3 领域搜索的基本过程3 6 图4 1 成像卫星星地联合调度问题求解框架4 1 图4 2 模拟退火算法流程图4 4 图4 3 插入任务邻域4 5 图4 4 交换任务邻域4 5 图4 5 任务在同一卫星资源上再分配4 6 图4 6 任务在不同卫星资源上再分配4 6 图4 7 删除任务邻域4 6 图4 8 测试算例示意图5 2 图5 1 任务调度与顶层设计关系图5 7 图5 2 任务调度系统结构图5 8 图5 3 成像卫星任务调度系统主界面5 8 图5 4 成像卫星任务调度系统整体流程图5 9 图5 5 采集任务单接收与处理子系统组成图6 0 图5 6 采集任务单接收与处理子系统主界面6 1 图5 7 卫星及地面站资源管理子系统组成图6 1 图5 8 卫星及地面站资源管理子系统主界面图6 2 图5 9 任务调度子系统流程6 3 图5 1 0 效能评估子系统主界面图6 4 图5 11 计划仿真推演示意图6 4 图5 1 2 单星计划编排子系统主界面图6 5 图5 1 3 单星计划编排子系统流程6 6 第v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意 学位论文题目：基士启发盎簋法鳗盛倦里星星地噬佥调廑间题珏窒 学位论文作者签名： 孑乏b 参己1日期：加铲年2 月了日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目： 基王启发塞篡洼的盛倦里星星地鲢企迥鏖闺题盟盔 学位论文作者签名：到二纽 作者指导教师签名： 日期：舅年2 月弓日 日期钐缛：墉多 国防科学技术大学研究生院硕士学位论文 第一章绪论 1 1 论文背景与研究意义 成像卫星通过星载遥感器从太空获取地面图像信息，已经成为勘测和研究地 球资源的重要手段。成像卫星对地观测具有覆盖地域广、持续时间长、不受空域 和国界限制、不涉及使用人员的生命安全等独特优势，已经成为经济、军事、气 象、灾害防治、环境保护等各个领域获取信息的重要手段，在现代社会中扮演着 越来越重要的角色，也得到了世界各国的高度重视【l 圳。 成像卫星利用星载可见光相机、红外相机、多光谱相机或合成孔径成像雷达 ( s y n t h e t i ca p e r t u r er a d a r ，简称s a r ) ，获取地面目标的高分辨率图像信息，并 将这些图像信息通过胶卷返回舱定期地回收或通过无线电数传系统实时传回地 面，供分析判读使用。可见光相机的成像分辨率较高，美国和俄罗斯的新型可见 光卫星，可以获取地面分辨率为o 1 0 3 m 的图像，但是受天气状况的影响较大， 有云雾及夜间都不宜工作；红外相机可以夜间工作，有一定的抗伪装的能力，但 图像分辨率不及可见光卫星；多光谱相机可以获得更多的地表信息，分辨率也不 及可见光卫星；合成孔径雷达相机的空间分辨率理论上不受摄影高度影响，微波 波谱不受白天、黑夜及云雾的影响，具有全天候、全天时观测能力，而且可以观 测地下或水下一定深度的目标。s a r 的波段范围覆盖p 波段到x 波段( 甚至更高) ， 空间分辨率也较高，具有很高的应用价值。携带不同类型成像遥感设备的多颗卫 星配合工作，能够相互取长补短，提高情报信息的准确性。 成像卫星是目前世界上研制时间最早、发射数量最多、所起作用最大、最具 代表性的一类卫星，也是我国当前有能力自行开发应用的最主要的一类卫星。随 着卫星应用的发展，现代社会对卫星观测提出了更高的需求，要求观测的目标数 量和次数不断增加，对获取图像的分辨率要求、时效性要求也在不断提高。但是 成像卫星资源及其配套应用系统的能力是有限的，当需要卫星完成的观测任务数 量繁多的时候，如何分配这些资源，确定卫星观测调度方案和数据回传方案，尽 可能地满足所有用户的需要并优化资源的使用，就成为成像卫星星地联合调度需 要解决的问题。 成像卫星星地联合调度是卫星及地面站资源分配、卫星观测调度方案和数据 回传方案编制的核心内容，它本质上是一个优化决策过程，对于更好地利用成像 卫星及地面站资源，优化卫星系统整体性能，发挥它们的最大综合效益具有至关 重要的作用。成像卫星星地联合调度不但对于底层的卫星方案编制具有实际意义， 它还可以对卫星系统的顶层设计提供决策支持。通过星地联合调度得到的卫星任 - 一一一_ 第1 页 国防科学技术大学研究生院硕士学位论文 务执行方案将能够反映卫星及地面站资源争用、任务取舍等卫星系统的实际应用 特点。对卫星任务执行方案进行仿真并就任务完成率和资源占用率等指标进行统 计，将能够合理评估卫星系统的任务执行能力和资源负荷水平。通过变换卫星系 统的配置参数并反复进行规划调度和仿真，就可以得到对不同的卫星系统配置方 案满足具体任务的能力评估结果，从而寻求最满意的卫星系统配置方案，为卫星 系统的顶层设计和方案论证提供决策支持。本文研究成像卫星星地联合调度的模 型及解决问题的方法，为最大化卫星系统的综合效益提供理论和技术支持。 1 2 国内外研究现状及发展趋势 由于各国的卫星各有特点，不尽相同，成像卫星及其调度的资料作为关键技 术，都对其他国家保密，因此国外有关成像卫星的资料很难获取。我国有关成像 卫星调度问题的研究也处于起步状态。以下主要从模型、算法以及软件系统三方 面对国内外有关成像卫星调度问题研究进行回顾和总结。 1 2 1 问题模型 成像卫星调度模型目前主要有数学规划模型、约束满足模型、序列决策模型、 图模型、状态活动模型、p e t r i 网模型等。h a r r i s o n 【5 】根据雷达成像卫星的成像约束 条件建立了整数规划模型，考虑了卫星侧视等影响因素。p e m b e r t o n 6 1 、w o l f e 7 1 在研究中没有考虑星上存储设备和数据传输，且假定任务间不存在任何的时间和 逻辑关系的条件下，建立了数学规划模型。g a b r e 【8 9 】，b e n s a n a 1 0 】针对s p o t 等 成像卫星建立了整数线性规划模型。a b r a m s o n 1 1 】针对多颗d r a p e r 小卫星建立了 整数线性规划模型。l e m a i t r e 1 2 】针对灵巧卫星的任务调度，建立了约束满足问题 模型，但没有考虑星上存储设备对任务调度问题的影响。b e n s a n a 1 0 】，v e r f a i l l i e 【”】 在s p o t 任务调度研究中提出一种值约束满足问题( v a l u e dc o n s t r a i n ts a t i s f a c t i o n p r o b l e m ，v c s p ) 模型，考虑成像卫星存储容量，侧视条件约束等多种约束条件的 限制，但是没有考虑成像卫星与地面站之间的数据传输。v e r f a i l l i e 【1 4 】，d a m i a n i 1 5 1 针对成像任务的动态变化建立了成像卫星自主任务调度的序列决策模型。 国防科技大学的贺仁杰博士【l o j 在其博士学位论文中对面向点目标的成像卫星 调度问题进行了初步的研究和探讨，他把多星联合调度问题看作是一个有时间窗 口约束的多机调度问题，给出了问题的混合整数规划和约束满足问题两种模型以 及相应的不同求解算法。他假设卫星的存储容量足够大或中继卫星实时可用，并 因此忽略了与数据存储和数据回传相关的约束。 国防科技大学的李菊芳博士【1 7 】在研究中针对航天侦察星一地任务规划问题具 有的车辆路线问题( v r p ) 和加工调度问题( j s p ) 两种特殊问题模型的混合特征， 第2 页 国防科学技术大学研究生院硕士学位论文 进一步考虑了数据存储和回传的情况，采用约束规划混合建模思想建立了问题的 混合约束规划模型。 国防科技大学的王钧博士【1 8 】在研究中针对成像卫星调度问题给出了基于全局 优化的数学规划模型和基于阶段优化的有向图模型。他在考虑地面站调度的时候 假设多星对地面站的访问没有冲突，把卫星对地面站的访问看成是一种特殊的观 测任务，与其余的观测目标统一调度。 国防科技大学的刘洋博士【1 9 】基于动态约束满足问题理论和方法，讨论了对卫 星观测任务进行重调度的问题，给出了基于动态约束满足的多星联合调度问题的 概念模型，在卫星的存储容量足够大或中继卫星实时可用的假设前提下，结合卫 星资源故障和新任务添加的两类实际问题，建立了调度模型。 国防科技大学的阮启明博士【2 0 】探索了面向区域目标的观测活动构造方法，提 出了网格空间的概念与构造方法，并在此基础上，明确了需要考虑的约束条件， 建立了面向区域目标的成像卫星调度问题模型。 国防科技大学的张帆博士【2 l 】就单星调度进行了研究，以卫星的一个圈次为一 个规划周期( t r a c ks e l e c t i o na n ds c h e d u l i n g 问题) ，考虑了卫星的侧摆，将单星 成像规划调度问题转化成一个有向无环图，其中节点代表待观测的地面目标，有 向边代表从始点到终点有一个符合最小转换时间约束的任务转换，模型没有考虑 数据存储和回传，模型的求解运用了运筹学图论中的思想。 中国科学院空间科学与应用研究中心的代树武【2 2 ，2 3 】等人对卫星运行中的自 主控制技术及对地观测卫星的智能规划和调度技术进行了初步研究，提出了卫星 模型、推理机支持下的智能规划与调度技术结构和采用分层a g e n t 控制的自主控 制系统，主要用于将卫星成像计划分解成比较详细的控制指令序列，没有考虑卫 星成像计划的编制过程。 王远振等 2 4 - 2 8 研究了多卫星地面站系统中的地面站资源优化配置问题及p e t r i 网模型在此类问题中的应用，建立了时间约束着色p e t r i 网模型。在该模型中，建 立了统一的地面站设备库所和等候卫星服务的库所，对地面站设备按类型着色， 对卫星按服务要求着色，并增加了时间约束。金光等【2 9 训】在研究地面站资源优化 配置问题时，详细考虑了地面站设备的“故障修复 、卫星的“进站出站 以及 地面站设备对卫星服务等动态过程，并据此建立了p e t r i 网模型。 还有一些研究基于一些简化模型，不考虑某些实际的约束条件。如m l e m a i t r e 1 2 , 3 2 1 、j p e m b e r t o n 【6 ，3 3 】以及w j w o l f e 【7 1 和s e s o r e n s e n 【7 】等在研究中都没有考虑 星上数据的存储和回传；e b e n s a n a 【l o 1 4 1 等在研究中虽然考虑了存储容量的限制， 但是也没有考虑数据回传活动。在具体的建模方法上，l e m a i t r e 、p e m b e r t o n 都把 问题看作是一般意义上的调度问题并采用了约束规划建模方法；w o l f e 和s o r e n s e n 一一 i 第3 页 国防科学技术大学研究生院硕士学位论文 则把单星任务规划问题看作是一个有时问窗口的背包问题，并采用了传统运筹学 中的建模方法；b e n s a n a 则是用部分约束满足问题模型来描述问题的，并相应采用 了约束规划建模方法。 1 2 2 优化算法 成像卫星调度问题是一个十分复杂的问题，即使当卫星和任务数目较少，要 想求得问题的最优解也是十分困难的，因此目前主要的研究工作集中在近似算法 上。 p e m b e r t o n 【6 j 提出了一种对大规模问题迭代求解的方法。他的基本思想是首先 按照某种规则对所有的观测需求进行排序，然后将所有的观测需求分组，再按分 组顺序对每组中的观测需求都采用完全算法求得最优解。在调度过程中，前面分 组的调度结果将作为后面分组调度的约束条件。 s h e r w o o d 3 4 j 等人采用了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 ) 的算法，该算法的基本思想是首先生成一个初 始调度方案，然后通过调整变量取值不断消解冲突。 f r a n k 3 5 】等人在模型求解中则基于e u r o p a 系统实现了一个基于随机搜索的启 发式算法，该算法目前还只能对较小规模的调度问题求解。 在l a n d s a t7 调度系统【3 6 】中首先按照最早结束时间贪婪安排所有的观测需求， 然后基于优先级替换已安排的观测需求和未安排的观测需求。 在s p o t 一5 调度问题中，b e n s a n a 【1 0 1 4 】等人分别比较了完全搜索算法( 深度优 先搜索、动态规划、r u s s i a nd o l ls e a r c h ) 和非完全搜索算法( 贪婪搜索、禁忌搜 索) 在不同规模问题实例下的计算性能。实验证明，当问题不大时，采用完全搜 索算法可以较短的时间内得到一个最优解，但当问题规模较大时，采用完全搜索 算法就不能在合理的时间内得到问题的解，而禁忌搜索可以在合理的时间内得到 问题的一个满意解。v e r f a i l l i e 3 7 , 3 8 】和v a s q u e z 3 9 】等在研究中也得到了类似的结论。 l e m a i t r e 1 2 】等人在对一个敏捷卫星( a g i l es a t e l l i t e ) 调度问题研究中比较了约 束规划方法和局部邻域搜索算法。他们发现，采用约束规划方法具有更强的灵活 性和适应性，而局部邻域搜索算法的求解效率和求解效果更好。 w o l f e 和s o r e n s e n 7 1 在文献中比较了三种不同算法：贪婪算法、具有前看功能 的贪婪算法以及遗传算法。在贪婪算法中，所有的观测需求按照优先级进行排序， 然后按照优先级顺序依次选择观测需求，将该观测需求安排到满足其约束的最好 时间点。具有前看功能的贪婪算法是在选择下一个观测需求时考虑其对其他观测 需求的影响。在遗传算法中定义了一些交叉、变异算子，允许撤销已经安排的观 第4 页 国防科学技术大学研究生院硕士学位论文 测需求，从而得到一个较好的调度方案。在文中实验证明，采用遗传算法可以较 大幅度的改进贪婪算法的调度结果。 n i c h o l a s 4 0 1 等人分别从时间片价格和机会成本等角度，设计并比较了8 种启发 式算法，这些启发式算法得到了接近于上界的解。g l o b u s1 4 l 】等人比较了爬山法、 模拟退火和遗传算法等求解方法在点目标的成像卫星调度问题种的表现，发现模 拟退火算法求解质量最好。 贺仁杰博士【1 6 】比较了禁忌搜索算法和列生成法在面向点目标的多星联合调度 问题中的表现。其研究结果表明，采用混合整数规划模型描述调度问题并采用列 生成法进行求解能够获得小规模问题的最优解，当问题规模变大时，列生成法的 计算时间将急剧增加，求解效率远远低于采用禁忌搜索算法求解约束满足问题模 型。 李菊芳博士【1 7 1 l v , 较了贪婪随机插入算法、变邻域禁忌搜索算法和导引式禁忌 搜索算法等三种改进的启发式局部搜索算法。其研究结果表明，这些算法各有所 长，贪婪随机插入算法的计算速度最快，变邻域禁忌搜索算法求解质量最稳定， 导引式禁忌搜索的综合性能较好。 刘洋博士【1 9 】针对卫星资源故障问题提出了反应式调度算法，采用迭代加深策 略，结合启发式规则，进行方案最小调整，并针对新任务添加问题提出了单调算 法。 张帆博士【2 l 】基于遗传算法针对单星单轨道圈次的任务规划问题提出了多目标 最短路径优化算法，其基本思想是同时求解多条优化成像路径，然后通过预定义 的策略筛选出最终调度方案。 阮启明博士【2 0 】根据问题模型中采用了分级的两层优化目标特点，采取最大化 整体收益优先于最小化观测成本的分级优化策略，设计了贪婪随机变邻域搜索、 禁忌搜索和模拟退火等求解算法，并对这些算法的性能进行了比较和分析，得出 以贪婪随机变邻域搜索算法得到的解作为初始解的禁忌搜索过程综合表现最好的 结论。 王钧博士【l8 】在全局模式下，提出了一种基于s p e a 2 算法框架的多目标成像卫 星综合任务调度算法，试验验证了算法的有效性。在局部优化的模式下，设计了 基于拍摄概率的成像任务预分配算法，将成像卫星综合任务调度转化成单星任务 调度问题，并提出了一种基于n s g a 2 算法框架下的多目标任务调度算法。 李云峰博士在研究卫星数传调度时，提出了两阶段调度的问题求解思路，给 出了两种调度算法：一种是基于综合优先度的卫星数传两阶段调度算法；另一种 是基于免疫遗传算法的卫星数传两阶段调度算法。 第5 页 国防科学技术大学研究生院硕+ 学位论文 1 2 3 软件系统 国外目前一些用于卫星调度的通用软件系统，除了前面介绍的a s p e n 系统外， 还有美国v e r i d i a n 公司开发的通用资源、事件、活动任务规划系统( g e n e r i cr e s o u r c e e v e n ta n da c t i v i t ys c h e d u l e r ，简称g r e a s ) 4 2 】，美国分析图像公司( a n a l y t i c a l g r a p h i c si n c 简称a g i ) 在2 0 0 3 年5 月推出的卫星工具包( s a t e l l i t et o o lk i t ，简称 s t k ) 软件的任务规划模块s t k s c h e d u l e r 4 引，美国o r b i tl o g i c 公司开发的o r b v i e w t a s k i n gs y s t e m ( o t s ) 】，欧空局( e u r o p e a ns p a c ea g e n c y ) 开发的m a t ( m u l t i m i s s i o na n a l y s i sa n dp l a n n i n gt 0 0 1 ) 【4 5 】等。 中国电子科技集团公司第五十四研究所 4 6 ，4 7 】针对单颗卫星的日常调度设计开 发了卫星照相规划管理软件，综合用户需求、轨道特性、有效载荷特性、信息传 输机制等条件，利用可视化的分析决策设计思路实行对卫星照相安排的规划控制。 该照相规划管理软件依靠规则进行决策分析和照相规划，软件中时间精确到秒量 级。该软件为卫星调度人员提供了一个有决策分析功能的作业界面，能够根据调 度人员安排照相任务或撤销照相安排的动作计算出相关的目标、跟踪接收时段并 相应地修改显示状态。然而该软件同具体卫星相关，卫星只执行星下点照相，不 考虑遥感器姿态调整，也不考虑区域目标的观测需求，而且卫星成像计划的编制 对于调度人员的手工操作仍有较强的依赖。 这些通用的软件系统其内部详细的建模和求解方法难以获取，不过从它们提 供的功能和使用说明来看，g r e a s 的建模框架是一个用于构造复杂的规划任务规 划问题的组件库，规划任务规划问题通过创建代表活动、资源、事件以及约束的 对象来进行建模。其具体的建模和求解过程则通过调用i l o g 公司基于约束规划的 商用优化软件i l o gs o l v e r 4 8 】和i l o gs c h e d u l e r 4 9 】来完成。而s t k s c h e d u l e r 是a g i 公司从轨道逻辑公司( o r b i tl o g i ci n c ) 购买的一个卫星任务规划软件产品，其建 模工作主要在s t k 仿真工具包中完成，具体求解过程则主要采用了神经网络和启 发式算法。 通过测试使用可以发现，这些软件产品都存在一定的缺点，不能很好地满足 实际应用的需求。单从模型和算法的角度来看，它们首先对可选资源或者说一个 任务可以由多个可选卫星完成的情况处理功能较弱，特别是g r e a s ，不具备这种 功能。另一方面更主要的，它们对数据记录和回传活动的处理能力差，特别是 s t k s c h e d u l e r ，不能定义与数据回传相关的活动和约束。 1 2 4 研究现状总结 从上述相关工作的介绍可以看出，目前成像卫星调度问题已经得到了世界各 第6 页 国防科学技术大学研究生院硕士学位论文 国研究人员的广泛关注，并取得了许多有价值的研究成果，有些成果还在实际应 用中取得了很好的效果。总的来说，现有研究具有以下特点： 1 普遍的问题解决思路是首先结合成像卫星有效载荷特点抽象出成像约束条 件，然后建立适当的任务调度模型，以此为基础，采用相应的优化搜索算法进行 求解； 2 由于各国卫星系统性能指标及其工作模式各不相同，所以卫星成像约束条 件区别较大，产生了多种不同类型的任务调度模型，在此基础上的算法也各不相 同；虽然已有少数公司或研究机构开发了通用或专用的卫星任务调度软件系统， 但是都不能完全满足具体实际中的成像卫星调度对性能和效率等技术指标的要 求； 3 由于成像卫星调度问题的复杂度较高，一些启发式近似算法逐渐成为任务 调度问题求解的主要方法，如贪婪算法、遗传算法、禁忌搜索算法等；而精确的 方法在成像任务较多时效率相对较低，一般只适于小规模问题或经过分解的子问 题。 同时，成像卫星调度技术也面临着以下问题： 1 单颗成像卫星的任务调度往往只针对某个卫星系统，其问题模型建立在对具 体某种有效载荷的成像约束条件的基础上，当任务调度考虑多颗卫星综合任务调 度时，针对单颗卫星的模型往往不能很好的描述问题，因此建立合理的问题模型 是解决成像卫星调度问题的必要条件： 2 多颗成像卫星的调度相对于单颗卫星调度，问题规模成倍增长，复杂度急 剧增加，因而，研究有效的优化求解算法是解决成像卫星调度的关键问题； 3 卫星数据传输负责将影像数据发送给地面接收设备，是完成成像任务的重 要步骤，直接影响到任务调度结果对成像约束条件的满足情况，现有的大多数研 究都只针对成像任务，没有考虑成像卫星与地面站数据传输，而要得到相对优化 的任务调度结果必须考虑数据传输的影响。 1 3 论文的主要研究工作和创新点 1 3 1 论文主要研究内容 本文紧密结合成像卫星的应用需求，借鉴国内外关于卫星调度的研究，研究 成像卫星星地联合调度的原理与方法，着重对成像卫星星地联合调度问题的模型 和模型求解算法进行研究。 本课题的主要研究内容有： ( 1 ) 成像卫星星地联合调度问题建模研究 一一_第7 页 国防科学技术大学研究生院硕士学位论文 数学模型是求解成像卫星星地联合调度问题的基础，成像卫星星地联合调度 问题是一个非常复杂的问题，涉及众多的对象和约束条件，导致对问题的建模非 常困难。对问题的建模必须首先分析多星协同观测特点，综合考虑观测任务的获 取、存储及回传，并在合理假设的基础上对任务、卫星以及地面站资源进行统一 建模。虽然现阶段国外对于成像卫星调度问题已经有了一些方法、模型和应用软 件，但是考虑到我国卫星的实际情况，并不能直接应用。因此从我国实际的卫星 系统的应用能力出发，建立成像卫星星地联合调度模型是本文首要的研究内容。 ( 2 ) 模型求解的启发式算法研究 模型求解算法是本文研究的另一重点。本文借鉴了前人的研究成果，采用启 发式的近似算法来解决成像卫星星地联合调度问题。启发式算法处理许多实际问 题时通常可以在合理时间内得到不错的解决方案，因此现实世界中经常使用启发 式算法来解决问题。启发式算法的有效性取决与其对问题的适应性、避免陷入局 部最优的策略以及对问题基本结构的了解程度。为了能够获得较高的求解效率和 较好的求解结果，本文在深入分析问题特征的基础上，重点研究了基于规则的启 发式构造算法和贪婪随机自适应搜索算法( g r a s p ) 。 ( 3 ) 软件系统的设计与实现 本文研究的模型和算法的最终目的是将其应用到工程实践中去，设计实现卫 星任务调度软件系统。在软件系统设计和实现时，要考虑到系统的功能性要求、 可靠性要求、效率要求、易用性和易维护性要求等。对软件系统的每个子系统工 作流程和实现细节都需要仔细考虑，在分析设计的基础上最终实现整个软件系统。 1 3 2 论文主要工作与创新 ( 1 ) 论文详细分析了成像卫星星地联合调度问题，在综合考虑了问题的观测、 存储和回传等环节的基础上，确定了模型的各种参数及变量，给出了优化目标和 约束条件，建立了基于阶段优化的成像卫星星地联合调度问题模型。 ( 2 ) 针对模型的不同阶段给出了不同的求解算法。观测调度阶段采用g r a s p 进行求解，并对基本的g r a s p 算法做出了改进，在初始解的构造阶段采用定长的 受限候选列表和变长受限候选列表的两种策略来构造问题的初始解，在邻域搜索 阶段采用模拟退火算法以求得较优的解。在分析了成像卫星星地联合调度问题的 多种基本的启发式规则的基础上，设计了综合效益优先和直拍直传任务优先的两 种启发式构造算法对模型的回传调度阶段进行了求解。 ( 3 ) 将本文对模型和算法的研究应用于工程实践，设计并实现了成像卫星任务 调度系统。 第8 页 国防科学技术大学研究生院硕士学位论文 1 4 论文组织结构 本文分六个部分对上述研究内容进行研究： 第一章，绪论。介绍成像卫星星地联合调度的作用及其在实际中的应用需求， 总结了国内外对于成像卫星调度问题的研究现状及发展趋势，给出了本文的主要 研究内容和主要工作。 第二章，成像卫星星地联合调度问题。本章分析了成像卫星的工作原理，明 确了其成像过程和数据回传过程，分析了成像卫星星地联合调度问题的任务约束、 卫星资源约束和地面站资源约束，给出了问题的基本输入输出并对调度流程进行 了分析。在此基础上，对成像卫星星地联合调度问题做出了基本假设和简化，指 出了问题的特点和难点。 第三章，成像卫星星地联合调度问题建模与求解方法分析。本章在上文分析 的基础上，把问题分为观测调度阶段和回传调度阶段，分别给出了两个阶段的优 化目标及约束条件，建立了基于阶段优化的成像卫星星地联合调度问题模型。这 种分阶段的方法降低了问题的相对复杂性，提高了工程应用中的可靠性和稳定性。 本章分析了启发式算法对问题求解的适用性，介绍了基本的g r a s p 算法及其改进 策略，分析了基于规则的启发式构造算法以及在成像卫星星地联合调度问题中的 基本的启发式规则。 第四章，成像卫星星地联合调度模型求解算法。本章研究了成像卫星星地联 合调度模型的求解算法。针对观测调度阶段问题的特点，在g r a s p 算法的初始解 构造阶段通过改变算法的参数，采用完全贪婪和贪婪随机两种思想构造问题的初 始解，在邻域搜索阶段采用模拟退火进行搜索以获得更高质量的解。在回传调度 阶段，设计了综合效益优先和直拍直传任务优先两种启发式构造算法，分别对问 题进行了求解，算法结束时得到较优的观测调度方案和回传调度方案。测试算例 表明，在观测调度阶段，完全贪婪的算法在求解速度上具有优势，但是改进的 g r a s p 算法能够在可接受的时间内得到更高质量的解：在回传调度阶段，综合效 益优先算法比直拍直传任务优先算法能够回传更多的任务，收益也更高。 第五章，成像卫星任务调度系统的应用分析与设计实现。本章首先分析了卫 星任务调度的应用需求，指出了卫星任务调度的两个应用的层次，即面向卫星系 统的日常工作安排和面向卫星系统的顶层设计。其次设计实现了成像卫星任务调 度系统，成像卫星任务调度系统由采集任务单接收与处理、卫星及地面站资源管 理、任务调度、单星计划编排、计划仿真推演和任务调度效能评估六个子系统组 成。本章分析了各子系统的结构和主要功能