一种基于DCSP模型的遥感卫星任务调度算法仿真与分析

马红梅， 项 杰， 王 昊， 李瑞琴

(上海卫星工程研究所， 上海 200240)

0 引言

传统的卫星遥感任务功能的实现，是通过地面上注任务包，卫星根据地面安排好时序完成遥感任务。这种实现遥感任务的方法完全依赖于地面对此次遥感任务的精确分解，地面若注数不成功，将会导致遥感卫星任务的错误执行，进而会给遥感卫星的安全使用带来影响。传统的遥感任务功能的实现已不能满足遥感卫星应用方面的要求。

本文提出一种基于DCSP(Dynamic Constraint Satisfaction Problem，动态约束满足问题)模型的遥感卫星任务调度算法[1]。

1 遥感卫星任务

经过多年建设，我国已基本建成星地一体测控通信体系，但是我国的测控站尚未实现全球覆盖，无法对卫星进行24小时全球跟踪及监控。

遥感任务是指遥感卫星通过卫星资源对特定的地面目标进行探测。对于一般卫星遥感任务的实现，需要地面在测控弧段内，将提前安排好的指令上注。遥感卫星收到指令后，按照指令执行时间，依次执行指令。由于传统遥感卫星无任务调度的能力，即仅根据地面上注的遥感卫星观测目标，智能分解卫星指令的能力。随着遥感卫星任务量的增多，导致地面指令的分解工作量大幅度增大。

对于传统的遥感卫星任务，若存在遥感任务冲突，只有任务执行后将无正确数据传送到地面，才发现此次任务的失败。这样即浪费宝贵的遥感卫星资源，又增加了地面人员的工作要求。因此，遥感卫星星载软件需增加一种任务调度算法，从而有效完成各项遥感任务。

2 遥感卫星调度约束

遥感卫星任务调度问题的本质是在一定的约束条件下，按照给定的卫星有限资源条件下，将卫星资源和卫星可用时间窗口分配给不同任务，是一个包括卫星资源选择和时间窗口选择的双重选择问题，主要有以下几个要求和特点。

(1) 时间窗口

卫星调度的一个最大特点在于卫星是围绕地球按照一定的轨道运行，并不是时时可见的。因此，这事实上是增加了卫星调度过程中的约束条件。如果要卫星执行对某个目标的观测任务，那么在卫星遥感器和目标之间必须要有可见时间窗口。而这个时间窗口是由卫星轨道、遥感器、目标位置共同确定的。因此，进行调度计算时，遥感卫星成像时间必需在卫星时间窗口内。

(2) 卫星资源的可选性

传统的调度问题，资源通常都是可以完全互换的。在卫星调度问题中，具有同样功能的卫星资源是可以互换的。但是，由于受到地面设备资源的制约，同样的数据下传，需要采用不同数据下传通道。

假设有一个观测任务vi，要求观测目标，需要及时下传载荷数据。但是此时数传地面站比较忙，无法下传。而此时，卫星只能现将数据暂时存储等数传地面站有空闲时间再将数据下传到地面。或者使用中继通道，将数据先发送到中继卫星，再由中继卫星下传到地面。

(3) 任务的不可中断性

卫星的任务通常具有不可中断性，即在调度过程中，若确定了某个任务的开始时间和结束时间，则在该段时间内，不能插入其它任务。

3 调度约束算法实现

3.1 任务元组描述

遥感卫星调度问题可以用五元组来描述：

J={V,P,Q,TB,R}

(1)

式中：V为要执行的遥感任务集合(即遥感卫星观测目标集)，包括预先确定的任务和随时改变的任务，V={v1,v2,…,vi,…}，vi表示遥感卫星第vi个遥感任务；P为遥感卫星任务等级，pvi表示遥感任务vi本身的重要程度，pvi∈{1,2,3,4,5}，数值越大，等级越高；Q为遥感卫星用户优先级，qvi表示遥感任务用户需求紧迫程度，qvi∈{1,2,3,4,5}，数值越大，用户优先级越高；TB为任务时间窗口集，相对于某个指定的遥感任务，每个卫星的可用时间窗口的集合，每一个时间窗口可表示为一个闭区间(Svi,Ovi)，其中Svi表示遥感任务vi开始时刻，Ovi表示遥感任务vi结束时刻，受到遥感卫星的能源限制，每轨的工作任务数量是有限的，tmin表示两次遥感任务的最小间隔时间；R为卫星资源集，单次任务可用的资源，R={R1,R2,…,Rm,…}。

单次遥感任务可用的资源包括：

a) 目标区域R1——可以是点目标(一个很小的矩形区域，矩形中心点代表需要观测目标的经纬度)，或者区域目标(由一个经纬度定义的多边形区域)；

b) 图像类型R2——可以是光学图像、雷达图像等；

c) 成像时间R3——定义该图像需求的时间范围，如果超过该时间，该需求或者不安排或者降低优先级；

d) 下传途径R4——根据地面站的情况，确定图像是否需要下传或者先行保存，数传下传通道选择数传地面站通道，还是选择中继卫星通道下传；

e) 观测窗口R5——任务目标，不在遥感卫星的观测区间内，则需要对该任务进行降级。

3.2 任务调度算法描述

一般来说，由于单颗卫星资源的短缺，用户需求不能全部被满足。因此，单颗遥感卫星调度的目标就是在有限的卫星资源的条件下，最大化的完成遥感任务。单次遥感任务，需在单颗卫星资源的能力范围之内。

遥感卫星任务调度，需综合考虑遥感卫星任务等级[2]、遥感卫星用户优先级、资源满足等因素[3]，采用加权合法来设计遥感任务的目标。因此定义每次遥感任务vi综合评估值为

(2)

由此定义遥感卫星遥感任务的规划模型为

(3)

式中：a、b分别为pvi、qvi的加权系数；cm为Rm的系数，当cm=1时，资源Rm满足任务要求，当cm=0时，资源Rm不满足任务要求。

按照每次遥感任务vi综合评估值排序形成的新的评估任务队列为

(4)

遥感卫星在执行任务的时候，任务数量是一个动态变化的过程，任务执行顺序会根据任务的优先级进行动态调整的。如图1所示，如果遥感任务v2的开始时间，遥感任务v1还没有正确执行结束，两次遥感任务v1和v2的执行间隔时间不满足遥感卫星能源所能保证的最小保护时间tmin，新的遥感任务v2将会被丢弃。

(5)

4 算法设计及分析

针对遥感卫星的任务动态调度，本文设计了一种基于DCSP模型的遥感卫星任务调度算法。

基于DCSP任务调度算法，步骤如下：

a)计算任务集V中每次任务的综合评估值Kvi；

b)将任务集V中的综合评估值Kvi降序排序，形成新的评估任务队列V′；

基于DCSP任务调度算法，是按照遥感卫星任务的综合评估值进行调度计算的。假如第i个任务要进入任务队列，则算法复杂度可表示为

E=0+1/2(0+1)+1/3(0+1+2)+…+

1/n(0+1+2+…+n-1)=n(n-1)/4

(6)

因此，基于DCSP任务调度算法的算法复杂度为O(n2)。为验证此算法的有效性，根据遥感卫星实际的工作场景，进行算法测试。

测试环境：2.93 GHz CPU，2G内存，Microsoft Visual C++ 6.0开发环境。

测试数据：采用了5组不同规划场景，每个规划场景中包括普通的任务目标和重点目标和特殊目标。其中，重点目标占总任务目标比例为20%。特殊目标占总任务目标比例为5%。每个场景中目标信息如表1所示。

表1 规划场景

算法测试过程中，分别设置a、b加权系数为0.4和0.8,即卫星用户的优先等级是首选。仿真测试数据如表2所示。

由表2可知，规划时间越长，任务规划时间越长，目标覆盖率越高。特别是针对优选目标能够达到100%的覆盖率。

综上所述，一种基于DCSP模型的遥感卫星任务调度算法，能够实时解决遥感任务中资源约束等限制，能够满足遥感卫星任务调度功能。

表 2 测试数据

5 结论

本文描述了遥感卫星任务调度流程，深入分析了遥感任务时间窗口及卫星资源，有针对性地提出了一种基于DCSP模型的遥感卫星任务调度算法。该算法首先按照遥感任务综合评估值形成新的评估任务队列，然后根据是否满足最小保护时间，从而确定出遥感任务是否插入遥感卫星执行队列。仿真结果表明，该算法可以对遥感任务进行高级调度规划，满足遥感卫星任务需求，对未来遥感卫星任务调度的设计有一定的参考价值。该算法已在遥感卫星中得到广泛的应用，不仅减少遥感卫星对卫星测控弧段的依赖性，也能减少地面指令的分解工作量。