高分多模卫星启发式调度模型任务规划系统实现

邱虎 刘明亮 李紫未

(中国资源卫星应用中心，北京 100094)

高分多模卫星具有分辨率高，敏捷性强，可中继传输等特点，可以实现对目标的快速访问和传输，因此，在地面任务管理系统中对星地资源，结合各种约束的综合管控，实现系统收益最大化，满足更多用户的需求具有非常重要的意义。

但另一方面，高分多模卫星对地观测任务调度问题约束条件众多，问题复杂，任务调度问题的特点有以下几个方面。

1)观测开始时间的不确定性

由于高分多模卫星的较强机动性，因此其对地面观测目标的可见时间窗口相对较长，最长可以达到几分钟，目标的观测开始时间可以在此时间内任意选择，观测动作可以在卫星飞行到观测目标的上方之前、之时或者之后，而非敏捷卫星在观测地面目标时，其观测开始时间是确定的，不能够前移或者后移，否则其观测到的目标数据就不完整[1-2]。高分多模卫星通过机动性实现同一轨道的全覆盖观测多个目标，这一优点使得如何在可见时间窗口内安排观测窗口成为一个重要的问题，这将直接约束敏捷卫星强大观测能力的发挥。

2)时间窗口选择的多样性

高分多模卫星具有俯仰、偏航及滚动等3个方向的自由度，对目标的可观测机会成倍增加，对同一任务也可能有多个时间窗口。在数据回传的过程中，同一任务也必须在多个回传时间窗口内选定一个作为其回传窗口。因此，无论是观测时间窗口还是回传时间窗口，都需要在多个窗口内选定，显示出问题时间窗口选择多样性的特点。

3)数据回传活动的不确定性

高分多模卫星具有实时传输、延时回放及中继中转并回放等模式获取数据，由于高分辨率数据率高及实传弧段的不足，不同数据的获取优先级不同，也增加了数据获取模式的复杂性。同时，对于数据回传活动对后续观测活动影响很大，怎样确定回传任务及其回传时间才能更有利于后续观测活动也是高分多模卫星任务调度问题的关键之一。

4)观测次序的不确定性

对两个地理位置相近的观测目标而言，高分多模卫星对它们的观测活动次序是不定的，取决于用户偏好或者算法选择[3-4]，而非敏捷卫星对它们的观测次序是由星历的先后事先决定的。观测次序的不确定性，增强了高分多模卫星任务调度的灵活性，也增加了其求解难度。

5)用户需求的多样性

由于高分多模卫星强大的观测能力和图像特性，用户对目标的观测需求相应复杂和多样，比如多条带拼接需求、立体成像需求等，也是敏捷卫星体现其强大观测能力的关键。其中存在的多个条带如何同时安排、条带之间的机动时间如何计算、立体成像任务如何安排等问题也为任务调度的难点之一。

6)能量消耗与补充的不确定性

高分多模卫星的能量平衡是影响观测任务的重要问题。通过对不同任务能量消耗的计算，可以实现较小的代价实现更多的任务观测。因此，观测任务如何选择观测资源成为调度算法中要解决的难点之一。

启发调度算法是一种基于直观或经验构造的算法[5]，对优化问题的实例能给出可接受的计算成本(计算时间、占用资源等)内，给出一个近似最优解。本文主要研究了高分多模卫星在一定使用约束和可用资源下，建立基于用户需求满足最大化收益的函数模型，进而寻找最优解，并在系统中进行验证。

1 建模及求解

高分多模卫星任务规划问题，就是在综合考虑卫星、载荷、地面站等资源的能力和不同用户的任务需求、不同规划目标的基础上，将生成的成像任务合理分配给卫星，进行约束检查并消除任务间的冲突，确定各个元任务的具体执行次序、执行时间、执行方式，最大限度地满足用户及管理部门的需求，生成卫星对地观测和接收计划[6]。将其抽象为数学模型即为在高分多模卫星现有的约束下，实现综合收益的最大化。

1.1 变量定义

高分多模卫星的任务规划问题可以抽象为使用资源(卫星资源、接收窗口资源)在约束条件下(卫星观测时间约束、卫星存储资源约束、卫星摆动约束、观测窗口时间约束)对观测目标(点目标，区域目标)的最大收益值。

为了更好引入及描述在一定约束条件下的收益目标函数以及其约束条件模型，先将场景中的使用的相关变量定义如下。

观测目标可以是多个点目标和多个区域目标集合，T={t1,t2,…,tN}，其中N为目标数量；

wi为观测目标ti的收益(优先级)，i=1,…N；

Ssce和Esce为场景的开始时间和结束时间；

oikv为卫星s对目标ti的第k个时间窗口内构造的第v个条带；

wsikv为任务条带oikv的最早观测开始时间，weikv为最迟观测开始时间，dikv为任务条带oikv的观测持续时间，rikv为观测侧摆角度；

wsrikv为任务条带oikv实际观测开始时间，werikv为实际观测结束时间；

卫星观测oikv的侧视角rikv，卫星观测oikv的俯仰角pikv；

ui∈(0,1)，ui=1代表条带oikv可以直拍直传，[dsi,dei]表示条带oikv的直传时间窗口；

sdi∈(0,1),sdi=1代表条带oikv要求立体成像；

Wsi为任务ti的观测开始时间(ti第一个条带观测开始时间)，Wei为任务ti的观测结束时间(ti最后一个条带观测结束时间)；

Dwsi为任务ti的回传开始时间(ti第一个条带回传开始时间)，Dwei为任务ti的回传结束时间(ti最后一个条带回传结束时间)；

M表示卫星的存储的最大容量；

E表示可以消耗的卫星能量阈值；

rikv表示t时刻卫星上的存储容量使用数值；

Et表示t时刻卫星上的电量数值；

tsuv,u≠v表示卫星观测条带oiku和条带oikv之间的姿态转换时间；

Tsij,i≠j表示卫星观测目标ti和目标tj之间的姿态转换时间；

fuv∈(0,1),u,v∈oik,fuv=1表示观测条带oijku和条带oijkv连续观测；

Fij∈(0,1),i,j∈T,Fij=1表示任务ti和任务tj被卫星s连续观测；

需要说明的是观测目标ti的所有条带观测收益相同；当oikv为立体成像任务条带时，pikv固定值，并且此时wsikv=weikv，即立体成像任务的观测开始时间是固定的。

1.2 模型建立

1)目标函数

(1)

式中：wi为观测目标ti的综合收益(价值综合优先级)；xik=1表示目标i在卫星s的第k个时间窗口观测 ；xikv=1表示目标i的任务条带v在卫星s的第k个时间窗口观测，0表示任务条带v没有被选择观测。

2)约束条件

(1)观测时间窗口约束，即任务及其条带的观测时间不得超出其时间窗口，即

∀v∈oi:(xikv=1)⟹(wsikv≤wsrikv≤

werikv≤weikv)

(2)

(2)任务之间的姿态机动时间约束，即两个连续观测任务中，前一个任务的观测结束时间加上机动时间不得超过后一个任务的观测开始时间，即

∀ti,tj∈T:(Fij=1)⟹Wei+Tsij≤Wej

(3)

式中：Tsij为机动时间，Wej为后一任务的观测开始时间。

(3)连续观测条带之间的姿态机动时间约束，即两个连续观测条带中，前一个条带的观测结束时间加上机动时间不得超过后一个条带的观测开始时间，即

∀u,v∈oi:(fuv=1)⟹wsriku+diku+tsuv≤wsrikv

(4)

(4)任务观测规则约束，即一个任务的所有条带在其一次观测机会中必须全部观测或者全部不观测，即

(5)

(5)任务观测唯一性约束，即在一个调度周期中，每个任务及其条带只能被观测一次，即

(6)

式中：NT为观测目标总量。

(6)实传任务约束，即实传任务的观测时间与回传时间必须在同一时间段，即

∀ti∈T,∀i∈Oi:(ui=1)⟹(dsi≤wrsi

(7)

式中：wrsi为实传任务的观测时间，di为回放持续时间。

(7)立体成像约束，即立体成像任务条带的最早可见时间与最晚可见时间固定不变，即

∀ti∈T:(sdi=1)⟹(wsikv=weikv)

(8)

式中：sdi=1代表条带立体成像。

(8)任务回传约束，即对于存储回放任务，每个任务的回传时间必须在其观测时间之后，即

∀ti∈T,∀i∈Oi:(ui=0)⟹(wrsi<

wrsi+di≤dsi)

(9)

式中：Oi为目标分解的元任务集合。

(9)卫星存储约束，即任意时刻卫星上观测任务所占用的存储容量不能超出其存储器的容量，即

∀t∈[Ssce,Esce]:Mt≤M

(10)

式中：Mt为任意t时刻卫星固态存储的存储容量。

(10)卫星能量约束，即任意时刻卫星上能量存量不能低于卫星可消耗的能量阈值，即

∀t∈[Ssce,Esce]:Et≥E

(11)

1.3 模型求解

高分多模卫星调度模型的求解是一类复杂的组合优化问题，可分为精确算法和近似算法。由于在实际应用中需要在一定的计算条件下，快速的求解出较优解。以启发式算法为代表的近似算法能够在短时间内获得问题的相对满意解[7]。同时综合考虑高分多模卫星生成方案的时效性，以及卫星动作的连续性，避免在方案中插入任务产生复杂的约束传播过程，设计了基于时序的动态前瞻启发式算法；按照场景的开始时间到结束时间的顺序推演来安排任务，算法中采用基于专家知识的启发式规则来决定当前任务的选择及卫星动作序列的安排。算法步骤及算法流程如图1描述如下。

图1 算法流程图Fig.1 Algorithm flow chart

(1)获取预处理之后的任务队列及时间窗口信息；

(2)按照开始时间早的顺序排列任务，形成任务列表，判断任务是否是直拍直传任务或回传任务，如果是则进入(3)，不是则(4)；

(3)判断任务是否违反姿态机动及回传约束，如果是则返回(1)，否则加入(7)的回传窗口队列；

(4)按顺序选取当前任务Ti，检查任务是否安排观测；

(5)按照规则决定当前任务Ti是否安排观测，如果安排转(6)，否则转(1)；

(6)选择当前任务方案安排卫星开机方案，转(7)；

(7)把Ti放入回传窗口队列，等待下一个回传窗口按照一定规则回传该任务；

(8)检查Ti与之前任务之间能否安排对日定向或者对地定向活动，满足要求则安排本任务，否则转(1)；

(9)输出最终任务调度结果及卫星动作序列。

1.4 算法规则

对于高分多模卫星而言，由于其具有三向的机动能力，观测目标具有一个大的时间窗口，其观测开始时间可以在这个大的时间窗口内任意选择，这样就导致任务可以在时间窗口之内滑动，那么任务冲突检测就相对复杂。

在高分多模卫星工程实现中，为保障综合效益最大化策略，其目标是在成像质量与任务数量之间寻找一个平衡点[8]，即争取完成更多的任务同时成像质量也有所提高。在前瞻任务组中，如果当前任务的观测开始时间安排在最佳成像时间点，且完成时间与后续任务的最佳成像时间点不冲突，则当前任务观测安排在最佳成像时间点；如果当前任务的完成时间与后续任务的最佳成像时间点存在交错，则当前任务安排在其最早成像时间点，保证后续任务安排在其最佳成像时间点。在工程实现中，前瞻任务与当前任务存在冲突时选择任务的规则：成像质量>优先级>剩余观测机会>窗口的长短>侧摆角的大小>俯仰角的大小。下面对各个规则进行简要描述。

(1)成像质量优先策略，指任务观测安排在成像最佳观测时间点，以期望完成任务的平均成像质量最高。但是如果任务较为密集，这样选择会对后续任务时间影响较大，导致有些任务由于时间窗口被占用太多而无法观测。

(2)高优先级，指由仿真管控给出的任务重要程度的度量，数值在1-10之间，值越大重要程度越高，需要优先完成。

(3)剩余观测机会，指在当前时间窗口之后任务还有存在的可观测时间窗口数量称为该任务的剩余观测机会。如果两个任务在执行时间上严格冲突，一般而言，有剩余观测机会的任务可以考虑延后安排观测。

(4)观测时间窗口的长短，指在优先级相同的情况下，观测时间短的任务优先安排，这是因为时间窗口越短可能引起冲突的概率就越小，能够安排更多任务。

(5)侧摆角的大小，侧摆角越大则拍摄图像的质量越差，因此当任务冲突时，尽量选择侧摆角较小的任务安排观测。

(6)俯仰角的大小，俯仰角越大则拍摄图像的质量越差，因此当任务冲突时，尽量选择俯仰角较小的任务安排观测。

另外，当冲突任务的观测时间窗口的长短、侧摆角的大小、俯仰角的大小等3种情况下差别在10%以内时，认为其差别在可以接受的范围内，然后进行下一个判断标准的比较。当2个任务5个判断标准都通过时，则安排观测时间点靠前的任务，舍弃另一个任务。

2 试验结果及分析

高分多模卫星规划系统采用浏览器和服务器(B/S)架构模式，后端部署于资源中心高性能计算服务器上，满足复杂的规划算法计算要求。操作人员通过浏览器界面操作软件，并可以设置各种可配置资源及规则项。

为测试系统目标访问特性，在需求界面中录入多个点目标散列分布于高分多模卫星单轨可视范围内(见图2)。

图2 测试点目标分布图Fig.2 Spatial distribution of the testing target points

(1)点1，2，3位于星下点两侧，用于测试访问特性；并将点2和点3优先级设置为8(较高)。

(2)点7位于星下线较远位置，滚动角超过40°，用于测试规划的约束满足情况。

(3)点4，5，6位于星下线轨迹同一侧，并且具有相同经度和相同的观测优先级，用于测试目标的访问顺序。

将图2中7个目标作为一组输入到系统中进行任务规划方案计算，经过数秒时间的计算后输出的方案如图3所示。

图3 测试目标规划方案Fig.3 Planning results based on testing targets

从规划结果可以分析得出：

(1)7个点目标参与规划，高分多模卫星通过三轴机动，实现了星下线附近6个目标的单次过境全覆盖。第7个目标点处在卫星可视范围内，但是超出设置的40°滚动角范围，没有对其进行观测，符合设计预期。

(2)点2和点3设置了较高的观测优先级，而且位于星下线较近的位置，可以通过较小的滚动角和俯仰角完成覆盖。从输出的收益值可以看出，这两点达到最高的收益值，符合设计预期。

(3)点4，5，6位于同一个经度上，观测顺序为自东向西依次观测，结合卫星飞行和地球自转特性，满足卫星总体姿态变化量小，能源消耗低的要求，符合设计预期。

(4)该规划方案经过动态启发算法计算，综合收益值为239 322,是规划算法的相对最优解，满足最大化的用户收益。

3 结束语

本文依据高分多模卫星成像特点，考虑到敏捷卫星任务规划的多样化用户需求和使用约束，根据卫星规划的难点，抽象出了问题模型，并采用了基于可配置规则的启发式算法，从规划结果可以看出，对于多目标任务的场景，任务规划系统可以快速有效的生成规划方案，在符合约束的条件下，实现对目标的最大化覆盖。通过在轨测试的检验，也达到了较好的效果。

随着卫星使用年限的增长，卫星的使用约束将会出现变化，未来还需要对模型进行针对性优化以满足新情况的使用，实现对高分多模卫星动态的效率最大化管理。