基于优先级与时间裕度的卫星应急观测任务规划*

郭 超，熊 伟，刘呈祥

(装备学院 a.研究生管理大队；b.复杂电子系统仿真实验室，北京 101416)



基于优先级与时间裕度的卫星应急观测任务规划*

郭 超**a，熊 伟b，刘呈祥a

(装备学院 a.研究生管理大队；b.复杂电子系统仿真实验室，北京 101416)

应急观测是对地观测卫星为配合地面紧急行动而执行的任务，具有紧迫性、集中性等特点，为任务规划带来了困难。针对应急观测的特点，描述了影响任务规划的卫星资源及任务的主要属性，定义了考虑重要性与紧迫性的任务优先级，提出了一个反映任务紧迫性要求满足程度的属性——时间裕度。建立了任务规划模型，构造了一个基于优先级与任务时间裕度的规划目标，确定了一系列规划约束，并利用遗传算法对模型进行求解。通过与最大化任务重要度的常规任务规划进行对比可见，所建立的模型能够有效提高任务成功率。

对地观测卫星；应急观测；任务规划；时间裕度

1 引 言

对地观测卫星的任务规划就是在卫星数量固定、传感器能力有限，而任务之间存在冲突的情况下，确定任务的执行顺序以及其与资源、时间的对应关系，以排除不同任务之间的冲突，并最大化满足用户的需求，对于提高卫星资源的利用率、优化观测任务的执行方案具有重要的意义。现有相关研究通过对目标观测过程建立整数规划[1]、约束满足问题(Constraint Satisfied Problem，CSP)[2-4]、图论[5]模型，并利用启发式算法[6]或智能算法[7]来求解，取得了较好的效果。

完整的对地观测任务包含目标观测和数据下传两个步骤，现有的多数研究以目标观测过程的规划为主，往往假设通信资源充足，数据下传不受约束而予以忽略。仅有少数学者研究了同时考虑目标观测和数据下传的情况，典型研究如：孙凯等[8]研究了成像卫星星地联合调度问题，分别给出了成像观测和数据回传两个阶段调度的优化目标和约束条件，但其将成像观测和数据回传作为两个独立的过程，以前者的结果作为后者的输入预案，后者的结果无法对前者产生影响；Wang等[9]研究了考虑数传过程的对地观测卫星星座的规划问题，提出一种基于优先级的冲突避免启发式算法，但未考虑任务截止时间的影响。

此外，现有研究多针对常规背景下的观测任务，实际上目前对地观测卫星在抢险救灾、局部战争、突发事件处置等紧急活动中也发挥着重要作用。以上研究成果直接应用于此类应急背景下的观测任务尚显不足，因此，本文从应急观测任务规划的特点入手，在现有规划模型的基础上提出改进，建立了应急观测任务规划模型。

2 应急观测任务的特点

应急观测是卫星支持地面紧急行动时所承担的观测活动，任务时间和所针对的目标都无法事先确定，具有较强的时效性要求。现有研究中对数传过程的简化假设，对于常规情况下的观测任务是可行的，这是因为常规观测任务的执行时间是确定的，不会在一定时间内集中突然出现大量紧急观测需求，且不要求将观测结果尽快下传，卫星可长时间存储观测数据等待下传时机。应急观测不同于常规观测，主要体现在紧迫性、时间集中性和空间集中性3个特点。

(1)紧迫性

应急观测任务的紧迫性来源于两个方面：一是观测的紧迫性，指任务所指向的目标可能只在当前一段时间内可见，若无法及时获得足够目标信息，目标状态及观测条件可能发生变化，要求卫星在一定的截止时间内完成观测：二是任务总体的紧迫性，指地面行动的执行者需要尽早获得卫星的观测数据，若目标信息无法及时下传，其时效性会降低进而导致任务失败，故要保证在一定截止时间内观测数据下传完毕。

(2)时间集中性

在地面紧急行动中，各种突发情况无法预测，造成了应急观测任务需要随机到来，往往表现为在一定时间内突然集中出现。

(3)空间集中性

由于作战、抢险等紧急行动一般不会覆盖广大的地理空间，而只是集中在有限的空间边界内进行，如局部战场、受灾区域等，故应急观测任务所指向目标的地面位置也具有一定的局限性，不会出现目标大范围分散的情况。

紧迫性使任务具有更为苛刻的时间约束，不仅需要在有限的可见的时间窗口和一定的截止时间内完成观测，还需要在任务要求的截止时间内将观测数据下传，以同时满足目标观测的紧迫性和任务总体紧迫性的双重要求。时间和空间上的集中性则会导致任务分布的不均匀，大大增加了不同任务间的潜在冲突，这种冲突既包括在卫星传感器资源占用上的冲突，也包括在星地数据传输资源占用上的冲突，导致任务可能因两种原因而失败：一是因等待可用观测资源而令观测不能及时完成；二是因等待可用通信资源而令观测数据不能及时下传，现有研究中对数传过程的简化假设将不再适用，故应急观测任务规划不能像常规观测任务规划一样开展。

3 应急观测任务规划建模

假设SAT={sat1,sat2,…,satm}为对地观测卫星集合，m为卫星总数量，TASK={task1,task2,…,taskn}为应急观测任务集合，n为任务总数量，T为所有任务执行的总时段。实际的对地观测任务需要考虑的因素很多，为降低建模难度，在此做如下假设：

(1)任意对地观测卫星只拥有一个有效的观测载荷，且任意时刻最多只能服务于一项应急观测任务；

(2)一旦一颗卫星开始执行某一项任务后必须待此任务执行完毕方可执行其他任务，期间不允许资源抢占；

(3)一颗卫星先后执行两个任务需要的时间间隔忽略不计。

3.1 卫星应急观测中的资源和任务

(1)资源描述

任意卫星资源sati∈SAT可以用五元组描述：

(2)任务描述

任意任务taskj∈TASK可以用七元组描述：

3.2 任务优先级与时间裕度

图1 任务执行时间

在常规观测任务规划中，重要性更大的任务应当优先执行，以获得更高的收益。而在应急观测任务规划中，还要考虑到任务越紧迫越容易失败，应该优先执行，而最大允许等待时间的长短反映了任务观测和数传的紧迫性，故定义任务taskj优先级为

其含义为在执行taskj过程中，实际用于等待可用资源的时间在最大允许等待时间中的比重，反映了任务执行方案满足特定紧迫性要求的程度。Rj越大说明taskj实际观测和数传开始时刻相对于对应截止时刻的提前程度越大，taskj能够尽早完成，腾出可用资源执行其他任务。

3.3 基于优先级与时间裕度的规划模型

定义反映任务taskj规划结果的变量xij，若任务taskj由sati执行成功，则xij=1；否则，xij=0。根据前文的描述，规划应考虑两类约束：任务假设约束和任务执行条件约束，各约束组含义如表1所示。

表1 应急观测任务规划约束

Tab.1 Constraints of emergency mission planning

类型约束组约束条件约束含义问题假设约束C1∀t∈T,∑nj=1xij≤1任意时刻每个卫星只能服务于一个任务∑mi=1xij≤1每个目标只被观测一次xij(tjse-tjsb)·xij'(t'jse-t'jsb)≤0任务之间不存在资源抢占任务执行条件约束C2C3C4∑mi=1Si≥1;∃sati∈SAT,Ci>djSAT中能够找到可用资源sati,sati满足当前星载存储空间大于taskj任务数据量[tjsb,tjse]⊂WTi,j卫星sati对taskj的目标有观测时间窗口tjse-tjsb≥ljstaskj的观测执行时间[tjsb,tjse]大于最短观测时间ljmtjse≤tjsd在观测截止时刻tjsd前完成目标观测[tjtb,tjte]⊂WGisati对地面站有数传时间窗口tjte-tjtb≥ljttaskj数传时间执行时间[tjtb,tjte]能够支持任务数据下传完毕tjte≤tjtd在数传截至时刻tjtd前完成目标数据下传

约束组C1～C4限定了任务执行成功的条件，不满足约束的执行方案将被过滤。在此基础上，可以建立规划目标：

maxf=(f1)λ1(f2)λ2,

(1)

(2)

(3)

式(1)为规划目标，含义为令函数f的取值最大，包含子目标f1、f2。其中f1的含义为令可执行任务具有更高的优先级，使重要、更紧迫的任务优先执行；f2的含义为令可执行任务的时间裕度最大，使任务在特定的紧迫性要求下，等待可用资源的时间最短，执行更为及时，从整体上提高任务执行成功率。此外，式(1)中λ1、λ2(满足λ1+λ2=1)分别为f1、f2在最终规划目标中的作用权值，取值应根据实际应用中对两个子目标的偏好，通过专家打分的方式决定。

4 模型求解

应急观测任务规划的目的是确定任务的执行顺序，并为每个任务分配卫星资源和执行时间。针对前文建立的模型，采用遗传算法求解任务规划问题。本文以任务分配序列作为染色体，编码方式见文献[3]，以任务规划目标函数的倒数作为适应度计算函数，即ffitness=f-1。

本文染色体的适应度的计算方法为：遍历种群中的每个染色体，由每个染色体确定一个任务分配序列，按照该任务执行序列依次判断每一个任务是否能够执行成功，并确定相应的卫星资源和执行时间，而后按照式(1)计算每个染色体的适应度。对于序列中的任一任务taskj，执行结果的判断过程如图2所示。

图2 任务taskj执行结果判断

5 计算实例

5.1 算例参数设置

为检验任务规划模型和求解算法的有效性，构造一个应急观测任务规划问题计算实例，其参数设置如下：

(1)全局参数设置

所有的应急观测任务执行时段为

2015/11/01 04:00:00.00～2015/11/01 14:00:00.00，下行链路传输速率假设为0.5 GB/s。

(2)资源参数设置

算例最多设置6颗对地观测卫星Sat-1～Sat-6，轨道参数如表2所示。所有卫星的初始状态都为空闲，初始星载存储都为150 GB；设置用于接收观测数据的地面站20个，位置数据从STK数据库导入。

表2 卫星参数设置

Tab.2 Configuration of parameters of satellites

序号a/mei/(°)Ω/(°)ω/(°)M/(°)Sat-169931830.00067697.763243.448258.859185.695Sat-270221810.00082297.9020.096175.699323.968Sat-370105060.00081797.727241.623101.85389.460Sat-470267030.00138997.861332.333134.543235.987Sat-568516470.00157097.366348.493193.878233.067Sat-668636780.00096997.69748.440107.11173.223

(3)任务参数设置

选定目标区域范围：110°E～120°E，20°N～30°N，随机产生应急观测任务集合，各任务重要度：0～1，到达时刻为2015/11/01 04:00:00.00～2015/11/01 14:00:00.00间的随机时间点，最短观测时间10～1 000 s，数据量1～10 GB，观测截止时刻为任务到达时刻至全部任务执行完毕时刻间的随机时间点，数传截止时刻为观测截止时刻至全部任务执行完毕时刻间的随机时间点。

(4)求解算法设置

遗传算法种群数量为50，交叉概率0.6，变异概率0.05，目标函数中权值参数取λ1=0.6，λ2=0.4。

5.2 算例结果及分析

将使用本文规划模型的算例组记为F，为了验证规划模型的有效性，将常规观测中常见的、只考虑最大化任务重要度(或收益)的规划模型[3]作为计算对照组，记为F′。

(1)全部卫星可用，观测任务集规模分别为20、50、80、110,计算结果如表3和图3所示。可见在资源一定的情况下，相比单纯考虑提高任务收益的最大化重要度(或收益)的规划模型，本文提出的应急观测任务规划模型兼顾任务重要性、紧迫性，同时考虑时间裕度的影响，能够提高整体任务执行成功率。这是因为应急观测能否执行成功很大程度上取决于其能否在截止时间内完成，将时间裕度加入规划目标可以有效地缩短任务执行中的各段空闲等待时间，提高资源利用率，从而使更多的任务及时执行。

表3 资源固定时不同规模任务集规划结果

Tab.3 Planning results under the condition of certain resources and various task numbers

任务集规模F规划成功率/%F'规划成功率/%效果提升/%2080.075.05.05076.070.06.08080.075.05.011081.876.45.4

图3 资源固定时不同规模任务集规划结果对照

Fig.3 Comparison of planning results under the condition of certain resources and various task numbers

(2)任务集规模取定为80，可用卫星分别为2颗、4颗、6颗,规划结果如表4和图4所示。可用卫星数较少时(2颗)相比可用卫星数较多时(6颗)，F较F′在任务成功率上的增幅更大，可见任务数量一定时，本文建立的应急观测任务规划模型在可用资源短缺时具有更好的效果。这是因为在资源紧缺时，任务之间的冲突严重，将有更多的任务需要等待可用资源，通过提高任务时间裕度，可以使有条件的任务尽早执行，为其他任务腾出资源，从而使更多的任务执行成功。

表4 不同资源数目时固定规模任务集规划结果

Tab.4 Planning results under the condition of a certain task number and various resources

可用卫星数F规划成功率/%F'规划成功率/%效果提升/%233.7526.257.50451.2545.006.25680.0075.005.00

图4 不同资源数目时固定规模任务集规划结果对照

Fig.4 Comparison of planning results under the condition of a certain task number and various resources

6 结束语

本文根据卫星应急观测的特点，建立了考虑目标观测和数据下传的应急观测任务规划模型，定义了兼顾重要性与紧迫性的任务优先级和时间裕度。通过计算实例可见，本文所提出的模型是合理有效的。相比典型研究[8-9]，本文建立的对地观测规划模型更具针对性：对目标观测与数据下传两个过程进行一体化规划计算，并考虑了双重截止时间约束，模型中的优先级反映了紧迫性特征对观测任务执行顺序的要求，而时间裕度反映了对任务紧迫性要求的满足程度，两者结合能够更全面地刻画应急观测任务规划目标。

相比常规观测，应急观测的需求更为多样化、条件更为苛刻，其规划问题具有较大难度。为降低困难性，本文将对地观测卫星限定在较为简单的工作模式，并对对地观测任务做了一定的简化假设，下一步将在此基础上，分析复杂的应急观测任务，并对其规划问题进行更为深入和全面的探讨。

[1] WANG P,TAN Y J.Column generation for the earth observation satellites scheduling problem[J].System Engineering Theory & Practice,2011,31(10):1932-1939.

[2] 高黎,李志猛.对地观测DSS任务分配问题的CSP模型与算法[J].空间科学学报,2012,32(2):251-256. GAO Li,LI Zhimeng.CSP model and algorithm on task allocation for earth observation DSS[J].Chinese Journal of Space Science,2012,32(2):251-256.(in Chinese)

[3] 贺川,朱晓敏,邱涤珊.面向应急成像观测任务的多星协同调度方法[J].系统工程与电子技术,2012,34(4):726-731. HE Chuan,ZHU Xiaomin,QIU Dishan.Cooperative scheduling method of multi-satellites for imaging reconnaissance in emergency condition[J].Systems Engineering and Electronics,2012,34(4):726-731.(in Chinese)

[4] 王万玉,张志强.多站多星任务调度模型及求解[J].电讯技术,2011,51(4):1-6. WANG Wanyu,ZHANG Zhiqiang.Multi-station multi-satellite task scheduling model and solution[J].Telecommunication Engineering,2011,51(4):1-6.(in Chinese)

[5] GABREL V,VANDERPOOTEN D.Enumeration and interactive selection of efficient paths in a multiple criteria graph for scheduling an earth observing satellite[J].European Journal of Operational Research,2002,139(3):533-542.

[6] 张利宁,黄小军,邱涤珊,等.对地观测卫星任务规划的启发式动态调整算法[J].计算机工程与应用,2011,47(30):241-245. ZHANG Lining,HUANG Xiaojun,QIU Dishan,et al.Heuristic dynamic adjust of task scheduling for earth observing satellite[J].Computer Engineering and Applications,2011,47(30):241-245.(in Chinese)

[7] 陈宇.基于免疫粒子群算法的多星观测调度研究[J].计算机仿真,2012,29(12):103-106. CHEN Yu.Research on multi-satellite observation scheduling based on immune particle swarm algorithm[J].Computer Simulation,2012,29(12):103-106.(in Chinese)

[8] 孙凯,陈成,陈英武,等.成像卫星星地联合成像调度[J].控制工程,2012,19(4):695-698. SUN Kai,CHEN Cheng,CHEN Yingwu,et al.Modeling and simulation on imaging satellites and ground stations joint scheduling problem[J].Control Engineering of China,2012,19(4):695-698.(in Chinese)

[9] WANG P,REINELT G.A heuristic for an earth observing satellite constellation scheduling problem with download considerations[J].Electronic Notes in Discrete Mathematics,2010(36):711-718.

郭 超(1987—)，男，山东济南人，博士研究生，主要研究方向为天基信息系统任务规划与资源调度;

GUO Chao was born in Jinan,Shandong Province,in 1987.He is currently working toward the Ph.D. degree.His research concerns mission planning and resource scheduling of space-based information system.

Email：gch_87_10_26@126.com

熊 伟(1971—)，男，山东临邑人，研究员、博士生导师，主要研究方向为天基信息系统综合集成;

XIONG Wei was born in Linyi,Shandong Province,in 1971.He is now a senior engineer of professor and also the Ph.D. supervisor.His research concerns comprehensive integration of space-based information system.

刘呈祥(1990—)，男，黑龙江佳木斯人，博士研究生，主要研究方向为信息系统效能评估。

LIU Chengxiang was born in Jiamusi,Heilongjiang Province,in 1990.He is currently working toward the Ph.D. degree.His research concerns information system effectiveness evaluation.

Mission Planning of Satellite Emergency Observations Based on Priority and Time Margin Degree

GUO Chaoa,XIONG Weib,LIU Chengxianga

(a. Department of Graduate Management；b. Science and Technology on Complex Electronic System Simulation Laboratory,The Academy of Equipment,Beijing 101416,China)

Emergency observations are tasks executed by earth observation satellites to support some urgent ground operations.They are usually pressing and concentrative so as to increase the difficulty of mission planning.According to the characteristics of emergency observations,main attributes of satellites and tasks influencing mission planning are described.In consideration of both importance and emergency,task priority is defined,and time margin degree,an attribute about the extent of task emergency demand satisfaction,is put forward.A planning model is constructed,including an objective based on task priority and time margin degree,and constraints to satisfy.Then genetic algorithm is used to solve the model.Comparison with conventional mission planning with the objective to maximize task importance shows the proposed model is effective on promoting success rates of tasks.

earth observation satellites;emergency observation;mission planning;time margin degree

10.3969/j.issn.1001-893x.2016.07.005

郭超，熊伟，刘呈祥.基于优先级与时间裕度的卫星应急观测任务规划[J].电讯技术，2016,56(7):744-749.[GUO Chao,XIONG Wei,LIU Chengxiang.Mission planning of satellite emergency observations based on priority and time margin degree[J].Telecommunication Engineering,2016,56(7):744-749.]

2015-12-22；

2016-04-05 Received date:2015-12-22；Revised date：2016-04-05

TN927

A

1001-893X(2016)07-0744-06

**通信作者：gch_87_10_26@126.com Corresponding author：gch_87_10_26@126.com