基于并行架构的敏捷卫星任务调度优化算法

张 超,李艳斌,陈金勇

(1. 中国电子科技集团公司航天信息应用技术重点实验室,石家庄 050081;2. 中国电子科技集团公司第五十四研究所,石家庄 050081)

0 引 言

在卫星遥感任务调度技术中,实际上要解决的是约束优化和多目标优化问题[1]。现有研究大多采用最优化算法、基于规则的启发式算法和智能优化算法求解。许多研究表明，最优化算法只能解决小规模的单星成像任务规划问题。基于规则的启发式算法具有简单、直观、便于实现、运算效率高等优点，但解的质量难以保证。禁忌搜索、模拟退火、粒子群算法、差分演化算法等智能优化算法在求解组合优化问题和多目标优化问题方面显示了较强的能力，近年来在成像卫星任务规划领域得到了广泛的应用。Bonissone将领域知识引入进化算法，通过显性知识和隐性知识，处理卫星成像过程中的静态和动态约束，解决了一个包含25个卫星的星座的任务规划问题[2]。韩伟设计了离散粒子群的位置变化公式利用粒子群算法求解向多对地观测卫星任务规划问题[3]。

敏捷卫星的发展使卫星对地面目标的观测时间范围更大，观测角度更加灵活多变。敏捷卫星在分散目标快速响应、地面目标三维信息获取、兼顾高分辨率成像与大范围覆盖等需求中应用广泛。敏捷卫星的任务规划调度问题国外研究主要集中在法国欧空局的Lematre 和 Panwadee、美国 NASA 喷气推进实验室(JPL)等。Lematre[4]针对法国Pleiades敏捷卫星的日常任务调度问题，比较了贪婪、动态规划、约束规划以及局部搜索等四种算法，其研究结果显示，局部搜索算法在考虑所有约束的情况下性能最好。Mancel[5]在 Lematre的基础上针对法国的 Pleiades 卫星建立了整数规划模型，并采用列生成算法进行求解。在国内，李玉庆[6]针对三轴稳定卫星点目标任务规划调度问题提出了一种基于模拟退火与遗传算法相结合的混合遗传算法。余婧采用序列二次规划方法求解敏捷卫星同轨多条带拼幅成像问题[7]。

1 敏捷卫星任务规划调度问题分析

敏捷卫星能够以俯仰、滚动以及偏航灵活的姿态机动调整能力获得更大范围、更加高效的对地观测能力，典型的工作模式有：多条带拼接模式，立体成像模式和多点目标快速成像工作模式。其中：

多条带拼接模式是指敏捷卫星将区域目标分解为多个可观测的条带，利用敏捷卫星在俯仰、侧摆的二维姿态快速机动实现推扫成像。敏捷卫星继续飞行立即进行俯仰方向的反向机动，同时通过侧摆将卫星指向平移约一个幅宽的距离，使得后一次推扫的起始条带与前一次推扫的起始条带相邻[8]。在任务调度时需要通过合理确定它们的拍摄顺序，不同的拍摄顺序对应要求卫星进行不同的姿态调整和变换过程。立体成像模式是指对同一地区实现不同角度的观测以形成立体像对，从而得出该地区的三维成像信息。此种工作模式主要是利用卫星俯仰轴的姿态机动来实现同轨2次或3次对同一地物不同角度观测。根据摄影测量原理[9]，当基高比接近1时，对于图像处理立体效果来说较好，因此可以选取在±25°时进行立体成像，以便得到较好的立体成像效果。在任务调度时需要通过合理确定卫星对目标2次或3次观测时的姿态角度，以及后续目标的冲突关系。多点目标快速成像模式是利用敏捷卫星的快速姿态指向能力，实现对分散的目标快速成像。这种成像模式主要利用卫星侧摆加俯仰的快速姿态机动能力实现同轨内距离沿轨迹方向较近的多个点目标成像。在任务调度时需要通过合理确定每个的目标成像开始时间、姿态角度实现近距离多个目标的成像冲突消解。

敏捷卫星特有的姿态灵活机动能力使得卫星对点目标可视时间窗口的变为了一个长时间窗口。点目标观测需要持续一段很短的时间，实际观测片段可以在观测可见时间窗口内自由滑动。因此在一个长时间窗口内，对点目标成像的开始时间决定了成像时采用的俯仰角度，也就决定了卫星成像质量，如图1所示。同时，敏捷卫星的任务调度过程是一个调度-选择相结合过程，如图2所示。首先需要调度卫星-目标任务匹配关系；然后备选目标任务还需要在可访问时间窗口中选择成像的时刻。

图1 敏捷卫星成像时间影响成像质量示意图

图2 选择点目标实际的成像片段示意图

敏捷卫星任务规划问题求解面临着很多的难点，复杂多样的观测任务模式、更加灵活的姿态机动能力、更长的可观测时间窗口导致了解空间增大，多个临近目标观测窗口重叠，且临近目标耦合度高，观测顺序不再固定。同时不同观测开始时间对应不同观测姿态角度，进而影响成像质量和任务间卫星姿态转换时间，这些都给敏捷卫星成像任务的调度及观测时间的确定带来了困难。

2 敏捷卫星任务规划调度模型

敏捷卫星任务规划调度建模十分复杂，文献[10-11]只考虑任务安排数量和优先级最大化作为规划目标建立约束满足模型，文献[12]将云层遮挡最小作为规划目标建立了敏捷卫星任务规划数学模型，上述文献都没有将任务安排数、任务优先级和任务质量统一考虑。在成像时卫星离地面目标越近、采用的观测角度越小则成像的地面分辨率越高。敏捷卫星对目标的成像时间决定了成像姿态角度，进而决定了成像质量，这是一种具有时间依赖性的成像质量。这与并行机加工调度问题“提早-延期”惩罚相似[13]，卫星在最佳观测角度成像获得的图像质量最高，而提早或延期成像获得的图像质量则会降低。因此，敏捷卫星任务规划调度模型中将成像质量最好转化为成像观测角度最小，并将其引入规划目标中，建立了多目标组合优化模型。本文只考虑与所研究问题直接相关的约束条件，主要包括数传固存约束、数传模式、指令模板、工作时间(分为观测、接收两个部分)、能源约束和姿态转换，对相关约束与冲突定义如表1所示。

表1 约束表

① 模型假设及约束变量定义

建立任务调度模型的假设及约束变量的定义：

1)调度开始时间为TS，调度截至时间为TE；

2)假设有n个要完成的任务，记为A={a1,a2,…,an}，每个任务的优先级为P={p1,p2,…,pn}，成像角度为IA={ia1,ia2,…,ian}；

3)定义观测元任务决策变量xj，如果元任务能够完成，则xj=1，反之，xj=0；

4)第j个观测元任务的开始时间变量记为sj，结束时间变量为ej，第j个元任务的实际开始时间为saj，实际结束时间为eaj；

7)定义一个任务数传模式变量Pj，如果任务做记录模式，则Pj=1，如果任务做实传模式，则Pj=0；

8)定义接收任务决策变量ki，如果接收元任务能够执行接收，则ki=1，反之，ki=0；

9)第i个接收任务的开始时间变量记为swi，结束时间变量为ewi；

10)单圈次最大观测时长为To，单圈次最大接收时长为Tr；

11)卫星最大固存为M，单位时间的观测数据占用固存为mj，假设在第j个记录文件放入固存之前固存占用量为Mj；

12)假设卫星电池初始电量为Eg。

② 模型表示

规划目标：

(1)

(2)

(3)

考虑约束：

Ts≤sj≤TEandTs≤ej≤TE, 1≤j≤n

(4)

对于∀j，满足saj≥sj且eaj≤ej

(5)

对于∀j，如果Pj=0，则∃i，使得

saj≥Si，1≤j≤n，1≤i≤m

(6)

对于∀j，如果Pj=0，则∃i，使得

eaj≤Ei，1≤j≤n，1≤i≤m

(7)

(8)

其中：jh、jb分别表示观测元任务序列中前后两个相邻的任务序号。

Mj+xj(ej-sj)mj≤M

(9)

(10)

(11)

模型说明：

式(1)表示完成任务的优先级之和最大；式(2)表示完成元任务数最多，即完成目标数量最多；式(3)表示完成任务的成像角度之和最小，即成像质量惩罚函数；式(4)表示所有任务的开始和结束时间必须在规定的时间段[Ts,TE]之内；式(5)表示所有的观测元任务的实际观测片段必须在观测可见时间窗口内； 式(6)表示当aj做实传模式时如果任务在时间窗口Wi内执行，那么任务的开始时间必须在相应的时间窗口的开始时间之后；式(7)表示当aj做实传模式时任务的结束时间必须在相应的时间窗口的结束时间之前。式(4)、(5)限定做实传的任务必须在对应的时间窗口之内完成；式(8)表示后一个任务的开始时刻和前一个任务的结束时刻之间的间隔时间必须不小于它们之间角度姿态调整需要的时间；式(9)表示固存占用量加上当前记录文件固存占用量必须不超过最大固存；式(10)表示单圈次中观测元任务总的时长必须不超过单圈次最大观测时长，其中s、e表示单圈次中第一个和最后一个任务的序号；式(11)表示单圈次中接收任务总的时长必须不超过单圈次最大接收时长。

3 敏捷卫星任务调度优化算法

① 敏捷卫星任务编码设计

染色体结构由观测目标的编码和接收元任务的编码拼接得到，根据任务规划需求采用整数编码的方式。传统卫星一个观测目标的基因位取值只能是0到1两种，0代表对应的该点目标没有被选中，1代表该点目标会被安排进行观测成像，所有观测目标和接收元任务的数量之和即为染色体的长度。然而，敏捷卫星根据不同任务观测模式基因位取值范围不同，对于观测元任务数量不同。对于多点目标连续成像模式，每个点目标可以被观测N次；对于立体成像模式，每个目标至少被观测2次；对于宽幅目标，根据区域条带分解得到多个观测条带，即一个观测目标对应多个观测元任务，相关元任务必须一起安排；因此，敏捷卫星观测元任务对应的基因位取值范围为0到N；敏捷卫星接收元任务基因位的取值范围为0、1或2，0代表对应的接收元任务没有被选中，1代表对应的接收元任务被选中并且做回放模式，2代表对应的接收元任务被选中且做实传模式。

② 基于排序变异的差分演化算法

DE算法的核心算子是差分变异算子。一般情况下，变异算子是从当前种群中随机选择。在自然界中，优良物种总是包含好的基因信息，因此，它们有更多的机会被用来指导其他物种进化。受这种现象启发，双亲个体被选中为变异算子的概率是根据它们在当前种群中的评价值排名来决定的，评价值较高的个体将获得更大的差分变异概率，其中个体权重的设置使用二次方模型(quadratic model)。采用这种基于排序的变异方式，将种群个体进行适应度排序后，进行迭代更新，能够维持局部搜索和全局搜索的平衡。

weights[i]=pow((double)(i+0)/S_size,2.0)

(12)

③ 遗传模拟退火混合算法

本文针对模拟退火算法解的质量与求解时间长之间的矛盾，将遗传算法与模拟退火算法结合起来，提出了一种改进的遗传模拟退火算法。改进遗传模拟退火算法的基本思想是：与传统的模拟退火算法总体运行过程相类似，从一组随机产生的初始解(初始种群)开始全局最优解的搜索过程，通过选择、交叉、变异等遗传操作来产生候选解，然后对候选解采用Metropolis准则判断是否接受其作为下一代种群中的个体，执行退温操作。这个运行过程反复迭代进行，直到满足终止条件。

④ 基于相似度和聚集度的粒子群算法

根据标准PSO算法的性能分析，随着算法迭代运行，粒子变得越来越相似，算法缺少多样性，从而影响算法的全局搜索能力。改进的粒子群算法的基本思想是：根据每条染色体的基因位与最优染色体进行比较，计算出每条染色体与最优染色体的相似度，然后根据相似度计算出每一代种群的聚集度。随着迭代运行，标准PSO算法会越来越聚集在一起，因为粒子最终都向最优点粒子靠近。改进的粒子群通过相似度和聚集度，在染色体变异过程中，当种群聚集度大的时候，增加染色体的变异概率，从而使种群的多样性增加，有利于寻找到更优的结果。

图3 约束处理流程

⑤ 约束处理

敏捷卫星任务调度优化是一个带约束的优化问题，需要考虑诸多约束。算法运行过程中产生的逻辑规划对象很有可能是不合法的，必须要对这样的逻辑规划对象进行处理。算法在产生逻辑规划对象经约束处理模块，对组合元任务集进行处理，得到新的满足约束的组合元任务集。然后通过编码，生成对应的修正的逻辑规划对象，即规划结果。约束处理模块依次按照以下顺序进行约束处理：观测时间冲突约束、数传模式约束、指令模板约束、工作时间约束、文件下传约束、能源约束。

⑥ 仿真测试结果

针对差分演化算法、模拟退火算法以及粒子群算法三种算法分别提出了改进算法。为了测试改进算法的效果，选取了5批工程数据，每批数据包含300个观测元任务，分别从综合评价值(完成任务数、优先级之和、俯仰角之和)以及耗时比较改进前后的算法效果。改进后的差分演化算法是使用了rankDE策略的算法，改进后的模拟退火算法是遗传模拟退火算法，改进后的粒子群算法是通过引入相似度和聚集度的概念来增大变异概率的算法。

图4 改进前后算法的综合评价值

图5 改进前后算法的耗时

通过以上图表数据的展示，可以看出：使用rankDE策略的差分演化算法，其规划结果及耗时与改进前的算法规划结果及耗时比较接近，改进效果并不明显；遗传模拟退火算法的改进效果比较明显，改进后的规划结果明显较优，虽然耗时相对较多，但算法改进后的耗时与差分演化算法接近，属于可接受范围；引入相似度和聚集度使变异概率增大之后的粒子群算法，其规划结果比未改进的粒子群算法的规划结果较优，虽然其耗时也相应的增加了，但综合其他算法来看，其耗时仍少于差分演化算法和模拟退火算法，说明粒子群算法的改进效果较明显。

4 并行算法研究

① 并行算法模型

由于智能优化算法的内在并行性，其并行处理方式是很自然的解决途径。本文中，卫星任务规划算法在并行模式上采用全局型和独立型。为了应用并行计算，必须把算法分解成相互独立的若干问题[14]。

全局型—主从式模型(mast-slave model)首先统一三种智能优化算法的编码格式，然后在主线程中进行搜索，然后将算法的每一次迭代中得到的解分配到对应的处理器独立进行的编码解析、约束检查、评价和计算解的适应值等操作，然后将其返回给调用线程。主从式模型示意图如图6。

图6 主从式模型的并行演化计算架构图

独立型—孤岛模型(island model)进行并行处理，多个解用“种群”表示，将“种群”分为若干个“子种群”分配给对应的处理器，每个处理器不仅独立计算适应度，而且独立进行选择、重组交叉和变异操作。每次迭代完成以后，选择“种群”中所有解的评价值中最高的解作为当前最优解。判断这个解是否满足终止条件的要求，满足则退出，不满足则继续迭代，如图7所示。

图7 孤岛模型的并行演化计算架构图

② 并行算法测试

并行测试结果很大程度取决于并行环境，三种运行模式硬件采用四核Core(TM) i3-4150 3.5 Ghz、内存4 G。针对同一批测试数据，对主从式并行和孤岛式并行进行测试，分别采用三种算法运行10次求平均值，利用平均耗时与未加速的算法耗时进行对比，具体的算法耗时见表3，成像任务规划性能加速比如图8。

在没有并行运算的情况下，三种算法运行耗时均较多；在采用并行框架后，三种算法运行时间均有明显下降；在主从式并行模型下，加速比分别为模拟退火算法1.614、差分演化算法1.911、粒子群算法1.990；在孤岛式并行模型下加速比分别为差分演化算法1.960、模拟退火算法2.254、粒子群算法2.478。综合比较两种模型，加速效果都很明显，但就两种模型来看，孤岛式并行模型加速效果更明显，三种算法的加速效果都高于主从式并行模型的加速比。

表2 三种算法并行模型运行时间表

图8 智能优化算法并行加速比图

5 结 语

本文针对敏捷卫星任务规划调度问题的特点，构建了基于成像质量惩罚系数的敏捷卫星任务规划组合优化模型；并对常见智能优化算法(差分演化、粒子群和模拟退火三种算法)进行改进实现和测试评价；在此基础上采用全局-主从式模型和独立-孤岛模型分别实现了三种算法单机多核并行计算技术。实验结果验证了提出的算法是可行的和有效的。

[1] 徐雪仁, 宫鹏, 黄学智,等. 资源卫星(可见光)遥感数据获取任务调度优化算法研究[J]. 遥感学报, 2007, 11(1):109-114.

[2] Bonissone P P, Subbu R, Eklund N, et al. Evolutionary algorithms+domain knowledge=real-world evolutionary computation[J]. IEEE Transactions on Evolutionary Computation, 2006, 10(3):256-280.

[3] 韩 伟,张学庆. 一种基于离散粒子群的多星任务规划算法[J].无线电工程,2015,45(1):1-4.

[5] Mancel C, Lopez P. Complex optimization problems in space systems[C].13Th International Conference on Automated Planning & Scheduling (ICAPS’03). 2003.

[6] 李玉庆, 徐敏强, 王日新. 三轴稳定卫星点目标观测任务优化调度技术[J].吉林大学学报:工学版, 2008, 38(6):1447-1451.

[7] 余婧, 喜进军, 于龙江,等. 敏捷卫星同轨多条带拼幅成像模式研究[J]. 航天器工程, 2015, 24(2):27-34.

[8] 张新伟, 戴君, 刘付强. 敏捷遥感卫星工作模式研究[J]. 航天器工程, 2011, 20(4):32-38.

[9] 王任享．三线阵CCD影像卫星摄影测量原理[M].北京：测绘出版社，2006:1-23.

[10] 孙凯，邢立宁，陈英武等.基于分解优化策略的多敏捷卫星联合对地观测调度[J].计算机集成制造系统, 2013, 19(1):127-136.

[11] 郝会成，姜维，李一军.基于混合遗传算法的敏捷卫星任务规划求解 [J].科学技术与工程. 2013, 13(17):4972-4978.

[12] 何磊, 刘晓路, 陈英武, 邢立宁. 面向敏捷卫星任务规划的云层建模及处理方法[J]. 系统工程与电子技术, 2016, 38(4): 852-858.

[13] 陈成. 时间依赖调度方法及在敏捷卫星任务规划中的应用研究[D]. 国防科学技术大学. 2014.

[14] 付鑫, 张峰, 冯占林,等. 基于并行计算的混沌遗传算法对反导预警雷达部署优化研究[J]. 中国电子科学研究院学报, 2016(3):276-282.