基于任务压缩的成像卫星任务规划

刘彬彬，李 晖，赵 曼，董理君，吴 杰

(中国地质大学(武汉) 计算机学院，湖北 武汉430074)

基于任务压缩的成像卫星任务规划

刘彬彬，李 晖，赵 曼，董理君，吴 杰

(中国地质大学(武汉) 计算机学院，湖北 武汉430074)

传统成像卫星任务规划过程中任务在时间窗口确定后是不可变的，但受限于卫星的各类约束条件，有些任务无法执行。针对该问题，在任务可以压缩的前提下，提出了采用多种任务压缩的方法处理指令模板冲突和消解文件下传约束，提高规划结果质量。对任务压缩策略进行了实验，测试结果表明，任务压缩策略的使用能够有效优化规划结果，提高卫星观测时长和完成任务数。

任务压缩；卫星任务规划；指令模板冲突；文件下传约束

AbstractIn the process of traditional imaging satellite mission planning,task is immutable after the confirmation of time window.Owing to the limitation of various satellite constraints,some tasks cannot be completed.To solve this problem,a variety of task compression strategies were proposed to deal with instruction template conflict and to resolve file downstream constraint under the premise that the task can be compressed,in order to improve the quality of planning results.Finally,the task compression strategies are tested.The results indicate that the use of task compression strategies can effectively optimize the planning results and increase satellite observation time and tasks completed.

Keywordstasks compression;satellite mission planning;instruction template conflict;file downstream constraint

0 引言

成像卫星利用可见光、多光谱、高光谱、超光谱和合成孔经雷达 (Synthetic Aperture Radar，SAR) 等星载传感器，获取地面目标的图像信息[1]。成像卫星对地观测具有覆盖范围广、运行时间长、不受国界和空域限制、无需考虑人员安全等独特优势，可以对全球任何地区实施观测[2]。卫星任务规划是卫星系统核心模块，其性能直接影响到卫星系统的工作效益[3]。主要目标是对卫星资源进行有效的分配和调度，制定卫星的观测计划，最大限度地完成用户提交的观测任务需求。

卫星任务规划是指为处理大量的用户任务，对组网卫星制定拍摄计划[4]。需要考虑固有的卫星能力约束及任务需求约束，是一个多约束的复杂组合优化问题。现有的卫星任务规划模型可以归纳为3类：数学规划模型[5-6]、约束满足模型[7-9]和其他模型[10-12]。李军等[13]建立了针对重点保障任务和其他重要任务评价的约束满足模型。Fabrizio[14]提出了一种紧时间序列模型，包括了大量复杂技术约束，用非标准的拉格朗日启发式算法求解。李云峰[15]给出卫星数传调度模型，把约束置于每个任务中，降低了建模和求解的难度。Frank[16]采用了基于约束的间隔框架对卫星星上资源建模，提出了基于资源满足的启发式搜索算法，但忽略了任务冲突的情况。

现有研究一般是在任务不可压缩的前提下开展的。但是由于卫星技术的不断发展，卫星的数传模式逐渐呈现多样化和复杂化，规划时往往有多种数传模式可供选择。为了选择出满足约束条件的最优安排方式，实际工程中允许对任务进行压缩以提高卫星的资源利用率。

本文基于任务可以压缩的特点，提出了多种任务压缩的方法优化卫星任务规划结果。卫星任务压缩是指在原始的观测任务和接收任务不满足约束条件时不删除整个任务，通过压缩任务的持续时间来消解约束冲突。

1 任务压缩

卫星任务规划问题需要考虑诸多的约束，有些任务往往无法满足所有约束。虽然通过删去观测任务可以消解冲突，但是会导致规划结果不理想。通过压缩任务时间，可以使规划结果满足各类约束的同时最大化观测任务完成数和观测时长。本文阐述了通过任务压缩来处理指令模板冲突和消解文件下传约束。基于任务压缩的卫星任务规划程序流程如图1所示。

图1 基于任务压缩的卫星任务规划程序流程

指令模板冲突和文件下传约束的处理单元是组合元任务，一个组合元任务对应一种数传模式，至少包含一个观测任务或一个接收任务。指令模板冲突是指任务之间的间隔时间不满足最短间隔时间要求。采用任务压缩，需要满足2个必要条件：一是任务被压缩后能够满足最小观测时长约束；二是压缩后任务必须满足一种数传模式的要求。文件下传约束是指由于接收窗口时长的限制而无法接收太大的成像文件，通过压缩观测使接收窗口能够被最大化利用。

本文涉及5种数传模式，一种数传模式对应一套指令模板，具体数传模式指令模板如表1所示。表1中，ti(i=1,2,3,4,5,6,7)为指令模板时间，表示做相应的数传模式前后需要的指令控制时间；tmin为最小成像时间；Δt1、Δt2均为固定时长；T代表成像；W代表回放；TW代表同时成像和回放。其中：Δt1>Δt2>Δtmin，t1>t2>t3>t4，t5>t6>t7。

表1 数传模式指令模板汇总

序号模板名称开始时间结束时间备注1成像延时回放TW1-t1TW1+t5成像时间tmin成像+回放时间TW12回放W1-t2W1+t7回放时间W13成像T1-t3T1+t6成像时间T14回放转成像延时回放W1-t2TW1+t5回放时间W1W1需不小于Δt2成像+回放时间TW15成像转成像延时回放T1-t4TW1+t5成像时间T1T1需不小于Δt1成像+回放时间TW1

1.1 任务压缩处理指令模板冲突

本文提出了2种压缩策略来处理指令模板冲突：基于贪婪思想保留任务价值更高的任务(简称策略1)、启发式动态调整指令模板(简称策略2)。

1.1.1 基于贪婪思想保留任务价值更高的任务

指令模板冲突压缩前(情形1)如图2所示，任务1和任务2在添加指令模板后存在冲突，首先比较它们的价值，选择价值较低的进行压缩。假设任务2价值低，压缩情况如图3所示，压缩量根据冲突量计算得到，只要保证压缩后刚好不存在模板冲突即可。

图2 指令模板冲突压缩前(情形1)

图3 指令模板冲突压缩后(情形1)

上述情况没有压缩观测，仅压缩了接收开始时间，但是这种压缩必须保证压缩后的“剩余量”满足当前任务数传模式(回放转成像延时回放)的要求，即“剩余量”不小于Δt2。

当然，仅压缩任务的接收开始时间可能无法消解冲突。图4中情形2对观测也进行了压缩，以保证数传模式不变的同时满足其约束。其中，图5中“剩余量1”必须不小于Δt2。此外，观测压缩后，“剩余量2”需满足不小于tmin的要求。

图5 指令模板冲突压缩后(情形2)

假如，通过上面的策略仍然无法消解冲突，则按照贪婪准则，直接删去任务2来进行消解冲突。

虽然示例中只介绍了数传模式为“回放转成像延时回放”时的压缩方法。但是，同样的压缩方法可以被类比应用于其他数传模式，压缩都遵循如下步骤：

① 尝试压缩接收时间消解冲突，无法消解时转向步骤②；

② 尝试同时压缩接收和观测来消解冲突，无法消解时转向步骤③；

③ 删除价值较低的任务。

1.1.2 启发式动态调整指令模板

采用策略1相同情景进行分析。当任务1和任务2之间的冲突量过大，贪婪思想消解冲突是在数传方式不变的前提下进行的。然而，策略2则根据发生冲突任务的数传方式，分析不同数传方式下指令模板的差异，通过启发式动态调整任务数传模式的方式来消解冲突。

如图6和图7所示，将任务2的数传模式从“回放转成像延时回放”调整为“成像延时回放”，从而消解冲突。这种压缩虽然没有压缩任务的观测，但是，由于数传模式发生了变动，相应的指令模板也发生改变，所以，必须重新检测是否满足指令模板冲突。

图6 指令模板冲突压缩前(情形1)

图7 指令模板冲突压缩后(情形1)

假如上述处理仍然无法消解冲突，则可以将任务2的数传模式从“回放转成像延时回放”调整为“成像转成像延时回放”。因为，查看表1可以发现“回放转成像延时回放”指令模板的前模板时间为t2，而“成像转成像延时回放”指令模板的前模板时间只需要t4，由于t4

图8 指令模板冲突压缩后(情形2)

当冲突仍然无法消解时，需要在变动数传模式的基础上，继续压缩相同量(由剩余冲突量决定)的观测和接收。当然，最极端的情况就是将任务2的数传模式从“回放转成像延时回放”调整为“成像”，即删去接收部分。然后，根据冲突量来压缩观测，如图9所示。

图9 指令模板冲突压缩后(情形3)

倘若通过以上这些方式都无法消解冲突，可以尝试对发生冲突的2个任务中的前一个任务进行压缩，压缩方法以前一个任务是“回放转成像延时回放”模式为例进行介绍。

通过查看表1，发现“回放转成像延时回放”模式的后模板时间为t5s，而“成像”模式的后模板时间为t6s(t6

图10 前一个任务变换数传模式

图10中任务的结束时间没有变，由于调整数传模式后，后模板时间减小了，当冲突量较小时可以消解冲突。当然，也可以调整数传模式的同时对观测和接收进行压缩。

对于其他数传模式，可以由此类推，压缩遵循如下步骤：

① 尝试变动数传模式(其指令模板的后模板时间较当前的更短)来消解冲突；如果无法消解转向步骤②；

② 同时压缩观测与接收的结束时间、调整任务数传模式来消解冲突。如果无法消解转向步骤③；

③ 删除2个冲突任务中优先级较低的任务。

策略2总体处理步骤如下：

① 对每个任务添加指令模板时间，作为任务的指令起止时刻；

② 将任务两两进行比较，前一个任务的指令结束时刻大于后一个任务的指令开始时刻，则存在冲突，计算二者差值，记为冲突量；

③ 检查后一个任务的数传模式，通过变动数传模式及向后压缩任务时间消解冲突。冲突无法消解则继续执行步骤④；

④ 检查前一个任务的数传模式，通过变动数传模式及向前压缩任务时间消解冲突。如果冲突仍未消解则继续执行步骤⑤；

⑤ 删去其中一个价值较低的任务。

1.2 任务压缩消解文件下传约束

文件下传约束存在2种情况：① 受限于卫星固存大小，按照原始任务观测时长产生的文件使固存超出，传统的处理方式就是删除任务，任务压缩的方法则通过压缩观测使文件能够放入固存；② 在给接收窗口安排回放文件时，当固存中每个文件所需接收时长均大于接收窗口时长时，压缩观测使文件能够放入接收窗口回放。固存超出时压缩观测的情况较为简单，本文主要介绍压缩观测来为接收窗口安排回放文件的处理方法。

1.2.1 不调整数传模式

一般观测和接收按照固定的比例匹配，假设1 min的成像需要1 min的接收窗口来回放。任务压缩方式可以将任务的观测开始时间向后压缩，也可以将任务的观测结束时间向前压缩，压缩的前提是保证满足数传模式不变。

如图11和图12所示，任务1的成像文件被安排在任务2的接收窗口回放，任务2同时产生时长220 s的成像文件。但是，后面在给任务3安排回放文件时，发现无法下传任务2的文件，必须对任务2的观测进行压缩。示例中任务2的数传模式为“成像转成像延时回放”，要求观测早于接收至少Δt1(Δt1<100 s)。通过将任务2的观测开始时间向后压缩20 s从而使任务3可以接收。并且，压缩后任务2的观测早于回放100 s，满足数传模式要求。

图11 消解文件下传约束压缩前

图12 消解文件下传约束压缩后

1.2.2 调整数传模式

如图13和图14所示，任务2产生时长220 s的成像文件。但是，后面的接收窗口都无法下传该文件，必须对任务2的观测进行压缩。示例中任务2的数传模式为“成像转成像延时回放”，要求观测早于接收至少Δt1(Δt1>80 s)，任务3的接收窗口只能接收140 s的成像文件。理论上只要压缩任务2观测80 s就可以了，但是压缩后不满足“成像转成像延时回放”Δt1的约束。所以调整数传模式，将其调整为“成像延时回放”模式(要求成像早于回放tmin)压缩了90 s的观测，剩下130 s的观测。任务3的接收窗口也对应压缩10 s。

图13 消解文件下传约束压缩前

图14 消解文件下传约束压缩后

2 任务压缩实验与分析

任务压缩实验是为了对比采用任务压缩和不采用任务压缩的效果。其中，任务压缩在处理指令模板冲突时又有2种策略：基于贪婪思想保留任务价值更高的任务(策略1)和启发式动态调整指令模板(策略2)。

采用任务压缩的优化效果取决于元任务集时间窗口的分布情况。本文针对观测元任务为10、100和200的量级，分别测试不采用任务压缩、采用任务压缩策略1和采用任务压缩策略2，记录卫星完成任务数和完成观测时长。

在完成任务数方面，规划结果如图15所示。

图15 完成任务数对比

在完成观测时长方面，规划结果如图16所示。

图16 完成观测时长对比

从上述实验结果可以看出，任务压缩策略的使用能有效提高卫星完成任务数和完成观测时长。当元任务数量增多时，优化效果更加明显。并且，采用任务压缩策略二比任务压缩策略一效果更优。在实际工程中，需要最大化利用卫星观测能力，想要在完成任务数和观测时长上进行少许提升都十分不易，实验表明任务压缩的使用能够进一步提升观测效益。

3 结束语

本文提出了基于任务压缩的卫星任务规划，针对指令模版冲突和文件下传约束分别给出了任务压缩策略。在处理指令模版冲突时，设计了2种任务压缩策略进行优化。在处理文件下传时，分别给出了不调整数传模式和调整数传模式的处理方法。实验结果表明，任务压缩机制的引入有效地提高了卫星完成任务数和完成观测时长,并且在任务量大且冲突任务多时任务压缩的效果更加明显。

[1] LIN W C，LIAO D Y，LIU C Y．Daily Imaging Scheduling of an Earth Observation Satellite[J].IEEE Transactions on Systems,Man and Cybernetics,Part A:Systems and Humans,2005,35(2):213-223.

[2] 贺仁杰,高鹏,白保存.成像卫星任务规划模型、算法及其应用[J].系统工程理论与实践,2011,31(3):411-422．

[3] 姜维,郝会成,李一军.对地观测卫星任务规划问题研究述评[J].系统工程与电子技术,2013,35(9):1878-1885．

[4] 姜维,庞秀丽.提高卫星服务寿命的任务规划方法研究[J].自动化学报,2014,40(5):909-920.

[5] 李菊芳,谭跃进.卫星观测联合调度问题的VRP与JSP模型[J].系统工程,2006,24(6):111-115．

[6] 王沛,谭跃进.多星联合对地观测调度问题的列生成算法[J].系统工程理论与实践,2011,31(10):1932-1939.

[7] 刘洋,陈英武,谭跃进.一种有新任务到达的多卫星动态调度模型与方法[J].系统工程理论与实践,2005 (4):35-41.

[8] 马冬青,王蔚.基于改进遗传算法的星地任务优化调度研究[J].计算机工程与应用,2014,50(6):246-249.

[9] 庞秀丽,于渤,姜维.成像卫星任务周规划模型与算法[J].国防科技大学学报,2013,35(5):44-51.

[10] 龙运军,陈宇宁,陈英武,等.基于Petri网和混合蚁群算法的多星成像调度[J].计算机工程,2013,39(1):35-40.

[11] 唐忠兴,韩潮.基于有向无圈图的敏捷卫星姿态机动策略[J].北京航空航天大学学报,2014,40(5):69-75.

[12] 郝会成,姜维,李一军,等.基于Multi-Agent敏捷卫星动态任务规划问题[J].国防科技大学学报,2013,35(1):53-59.

[13] 李军,郭玉华,王钧,等.基于分层控制免疫遗传算法的多卫星联合任务规划方法[J].航空学报,2010,31(8):1636-1645.

[14] MARINELLI F,NOCELLA S,ROSSI F,et al.A Lagrangian Heuristic for Satellite Range Scheduling with Resource Constraints[J].Computers & Operations Research,2011,11(38):1572-1583.

[15] 李云峰,陈祥国,武小悦.卫星数传调度模型研究[J].国防科技大学学报,2007,6(29):121-125.

[16] FRANK J,JONSON A,MORRIS R.Planning and Scheduling for Fleets of Earth Observing Satellites[C]∥Proceedings of the 6th International Symposium on Artificial Intelligence,Robotics,Automation and Space,Montredal,2002:342-347.

ImagingSatelliteMissionPlanningBasedonTaskCompression

LIU Bin-bin，LI Hui，ZHAO Man，DONG Li-jun，WU Jie

(SchoolofComputerScience,ChinaUniversityofGeosciences,WuhanHubei430074,China)

TP302.1

A

1003-3106(2017)11-0073-06

刘彬彬男，(1991—)，硕士研究生。主要研究方向：智能计算与智能信息处理。

10.3969/j.issn.1003-3106.2017.11.16

刘彬彬,李晖,赵曼,等.基于任务压缩的成像卫星任务规划[J].无线电工程,2017,47(11):73-78.[LIU Binbin,LI Hui,ZHAO Man,et al.Imaging Satellite Mission Planning Based on Task Compression[J].Radio Engineering,2017,47(11):73-78.]

2017-01-18

湖北省自然科学基金资助项目(2016CFB278)。

李晖女，(1967—)，教授，硕士生导师。主要研究方向：智能计算与智能信息处理。