成像卫星是目前世界上应用范围最广的一类卫星[1-2]．在区域作战、反恐维稳及抗洪救灾等任务较密集、时效性强的应急活动中是必不可少的[3-4]．针对应急活动如何制定高效的调度方案是非常重要的，此时有必要考虑任务的合成观测．考虑任务合成的方法不仅可减少卫星能耗，还可以增加观测任务的数量．对于卫星任务合成调度问题：文献[5]研究了单卫星单轨道问题的最优合成方法，文献[6]提出了有效的快速模拟退火算法．文献[7]采用图论中的团划分理论对成像侦察任务进行合成．文献[8]研究了基于时间窗口的相邻任务间的合成．文献[9]研究了基于固定观测角度的多任务的覆盖问题，但没考虑合成任务时间窗口约束．文献[10]建立了单星调度问题的团划分模型并给出了相关求解算法．针对多星任务合成调度问题，文献[11]将原问题分解为任务分配与任务合成的分解优化思路去求解．文献[12]基于一种改进的烟花算法解决了密集任务成像卫星调度问题，先对任务间所有可能进行合成分析，然后基于合成任务建立任务调度模型并给出了相关求解算法．上述研究都取得了不错的实验效果，但对于时效性要求较强的问题，其时间代价相对较大．所以本研究针对较大规模密集型多星任务调度问题中反馈结果迅速的需求，提出了一种基于MS(均值漂移)的成像卫星任务合成调度方法，并给出了相应的求解算法．1 问题描述与建模本研究中成像卫星合成任务规划问题可以描述为：在满足卫星资源约束和任务需求的情况下，首先对任务进行合成约束，然后基于合成任务进行调度规划，为合成任务分配观测时间和卫星资源，制定合成任务观测方案，追求最大的观测收益[4]．本研究的观测任务只包含点目标，在调度求解前须对观测任务进行任务合成分析．设S={S1,S2,⋯,SM}表示M个卫星资源，Sj表为第j个卫星资源；t={t1,t2,⋯,tn}表示n个观测任务，ti为第i个观测任务；ti的时间窗口集合表示为oi=∪j=1M∪k=1Nijoijk，Nij=|oij|为ti在卫星Sj中的时间窗口数量，oijk={(sijk,eijk),gijk}为任务ti在卫星Sj观测下的第k个时间窗口，sijk和eijk分别为时间窗口oijk的起止时间，gijk为其观测角度．对于卫星Sj，其相关变量包括：视场角Δgj，单次最长开机时间ΔAj，遥感器侧摆速率λj，单位时间内观测所需存储空间系数αj，能量系数βj．遥感器侧摆能耗系数为ρj，最大存储容量及最大存储能量分别为Mj和Pj．1.1　合成观测在任务较密集的情况下，传统观测方法往往使得许多任务之间互相排斥，导致卫星观测效率低．成像卫星有一定视场，在一次成像过程中须调整卫星成像角度来更好地同时覆盖多个任务[6]．在一次成像过程中可同时被观测的任务集合称为一个合成任务．如图1中任务tm和tn被成像卫星的同一观测条带覆盖，称为一个合成任务，记作T(m，n)．任务合成观测不仅可以通过减少传感器的打开次数节约卫星能量资源，还可以消减任务间的冲突提高观测收益．其中，任务之间相互冲突是指：由于两任务间的时间间隔太短，不足以完成卫星在两任务之间的姿态转换．10.13245/j.hust.211012.F001图1成像卫星合成观测示意图定义1 成像卫星在一次过境过程可以观测的任务称为元任务[12]．本研究中元任务为一个点目标．定义2 若观测活动同时覆盖了若干个按时序排列且满足合成约束条件的元任务ti,ti+1,⋯,tl，则称该元任务组成了一个合成任务T(i,l)．一个合成任务为一观测活动，至少包含一个元任务．合成任务中的元任务须满足合成约束条件，包括观测角度约束和时间约束．对于卫星Sj，由视场角Δgj决定其视场范围．对于时间窗口oijk下的合成任务T(i,l)，包含的元任务序列ti,ti+1,⋯,tl的观测角度gijk,g(i+1)jk,⋯,gljk须满足max(gijk,g(i+1)jk,⋯,gljk)-min(gijk,g(i+1)jk,⋯,gljk)≤Δgj.对于T(i,l)，元任务序列在oijk下须满足的时间约束为max(eijk,e(i+1)jk,⋯,eljk)-min(sijk,s(i+1)jk,⋯,sljk)≤ΔAj.特别地，当第k个合成任务Tk包含两个元任务tm与tn时，那么Tk的时间窗口与观测角分别为：{min(smjk,snjk),max(emjk,enjk)}；gjk=(gmjk+gnjk)/2.文献[13]研究了合成任务的最优观测角度算法，有如下性质．性质1 若合成任务T(i,l)成立，观测角度为gj(i,l)，则eljk-sijk≤ΔAj，|gijk-gljk|≤Δgj，且gijk,gljk∈{g¯j(i,l)-Δgj/2,g¯j(i,l)+Δgj/2}成立．性质2 若T(i,l)成立，ti,ti+1,⋯,tl的任务观测角中最大为gmax，最小为gmin，则gj(i,l)的取值区间为(gmax-Δgj/2,gmin+Δgj/2).1.2　数学模型成像卫星合成任务规划问题可以用五元组〈S，T，O，C，F〉表示，其中：T为任务集合，O为合成任务的时间窗口，C为约束条件集合，F为目标函数．以最大化观测收益为目标，考虑任务唯一性约束与调度不可中断约束，以及卫星的固存和能量约束，建立考虑任务合成的多星调度问题的数学模型．为方便描述，记合成任务的集合为T={T1,T2,⋯,TN}，Tk为第k个合成任务，N为合成任务数．Tk的时间窗简记为Ojk={(sjk,ejk),gjk}，sjk,ejk为Tk时间窗口的起止时间，gjk为其观测角度，有max∑j=1M∑i=1nxijpi；(1)s.t. ∑j=1M∑i=1nxij≤1; (2)sjk≤ejk；(3)ejk-sjk≤ΔAj；(4)ejk+t0(k,k+1)≤sj,k+1；(5)βj∑k=1N(ejk-sjk)+ρj∑k=1N-1|gj,k+1-gjk|xk≤Pj；(6)αj∑k=1N(ejk-sjk)xk≤Mj；(7)(ejk-sjk)xk=djk；(8)t0(k,  k+1)=|gj,k+1-gjk|/λj+sj, (9)式中：pi为ti的优先级；dkj为Sj观测Tk的持续观测时间；sj为Sj开机稳定时间，t0(k,k+1)为Tk与Tk+1之间的卫星转换时间．决策变量为xij=1(ti被Sj观测),0(其他); (10)xk=1(Tk被Sj观测),0(其他). (11)式(1)表示卫星的收益，即被观测的元任务收益之和．式(2)表示任务的唯一性约束，每个ti至多被观测一次．式(3)与(4)为合成任务Tk的观测时间约束，保证每个合成任务时间窗口的起始时间不能大于其终止时间，且观测时段不能超过卫星的最大开机时间．式(5)表示两个观测活动之间的卫星转换时间约束，前一观测任务的终止时间加上卫星转换时间不超过下一任务的观测开始时间．式(6)为卫星的能量约束．式(7)为固存约束．式(8)表示任务的不可间断性约束．式(9)表示卫星Sj从第k个到第k+1观测任务之间的转换时间．式(10)和(11)为决策变量．2 任务合成算法及其求解算法2.1　基于MS的卫星任务合成方法本研究对成像卫星合成任务的规划考虑了关于时间和观测角度两种维度上的任务合成．根据文献[14-16]，将每个元任务ti看成空间中的一个点，通过不断地更新漂移向量Yab，使得椭圆区域Wab能够覆盖更多的任务，即Yab=∑xi∈Wabwi{[XMS(ti),GMS(ti)]-(x*,y*)},式中：wi为权重因子，采用单位高斯核函数计算，代表了任务Ti对中心位置(x*,y*)的重要程度；XMS(ti)与GMS(ti)分别为元任务ti在当前时间窗下的观测时间与观测角度．椭圆区域内的覆盖点集合Wab为Wab=ti:(XMS(ti)-x*)2a2+(GMS(ti)-y*)2b21，式中：a为合成任务的观测时长限制参数；b为合成任务的观测角度限制参数．基于MS的卫星任务合成算法分为以下几个步骤．a. 对观测任务进行任务合成预处理，并在随机的卫星轨道上随机选取一个合成任务作为该簇的初始中心B．b. 计算椭圆区域内覆盖的点集合Wab，漂移向量Yab，新的中心点Bnew=B+Yab，并更新中心点，令Bnew→B．c. 计算||B-Bnew||≤δ0，判断当前迭代是否满足该停止准则，δ0为一很小的常量．d. 若不满足停止准则，则转步骤b，直至满足停止准则．e. 若已满足停止准则，则判断Wab中覆盖的任务是否合成成功．若合成成功，则标记Wab中覆盖的任务已访问；若任务合成失败，则Wab中覆盖的任务继续尝试在其他的轨道继续合成，如果没有后续观测机会就标记已访问．f. 依次遍历其他轨道信息，直至所有任务都被访问．2.2　成像卫星任务合成规划问题的求解方法蚁群优化算法是模拟现实世界蚂蚁觅食行为的一种仿生搜索算法[17-19]．考虑到蚁群算法的随机搜索功能、正反馈机制，以及MS的聚类机理，构造了基于MS任务合成的蚁群求解算法来解决本研究中的任务规划问题．先利用基于MS的卫星任务合成算法确定合成任务序列；然后利用改进蚁群算法对合成任务序列进行求解．首先，蚂蚁随机选取一个合成任务作为初始点，依据状态转移规则选择下一个合成任务，直至形成一条可行解．蚂蚁选择完一个节点后，执行局部信息素更新；在所有蚂蚁完成一条可行解的搜索后，执行Insert搜索，而后全局信息素更新．2.2.1　信息素矩阵根据每个合成任务的任务需求度来构造信息素矩阵．初始时刻各边上的信息素浓度为τi,j(0)=(ψi+ψj)/(2max ψ)，式中：max ψ为合成任务的最大需求度；ψi为合成任务Ti的任务需求度．又有ψi=∑ti∈Tipi|oi|，式中|oi|为ti的可见窗口数量．2.2.2　状态转移规则在蚂蚁选完初始节点后，根据下面的规则选择其下一个可观测的合成任务Tj，即j=argmaxl∈Jk(i){[τil]γ[ηil]λ}    (q≤q0);J    (qq0), (12)式中：τil为边(i,l)上的信息素浓度；ηil为启发式因子，代表蚂蚁从i转移l到的期望程度；γ为信息素在概率计算中的权重；λ为启发因子所占的权重；Jk(i)为第k只蚂蚁访问完第i个合成任务后的后续可访问集合，具体表示为P(J|i)=[τiJ]γ[ηiJ]λ/∑l∈Jk(i)([τil]γ[ηil]λ). (13)2.2.3　局部信息素和全局信息素更新在蚂蚁选择完一个可观测合成任务Tl后，执行边(i,l)上的信息素更新，即τil←(1-ρloc)τil+ρlocτ0，(14)式中：ρloc为局部信息素挥发因子；τ0为初始信息素浓度．在所有蚂蚁完成各自可行解的构建后，选择收益值最大的一个解执行全局信息素更新，规则为τu,v←(1-ρglo)τu,v+ρgloΔτu,v，(15)式中：ρglo为全局信息素挥发系数；信息素增量Δτu,v=Q/(max ψ+1-ψv)((u,v)∈Lbest),0    (其他),其中Lbest为当前最优路径，Q为全局信息素增量因子．蚁群算法虽能够快速找到较好的解，但容易陷入局部最优，使得解的精度和收敛效果不是很好，为此设计了Insert搜索算子[20-22]．Insert搜索算子是基于当前代中的精英解进行局部寻优的，具体的算法步骤如下．a. 选择当前迭代M只精英蚂蚁解，依次遍历寻优．b. 随机选择一个精英解中的第E个合成任务，并计算与第E个合成任务同轨道的后续可访问集合J(E)，若J(E)非空，则转步骤c；若J(E)空，则转步骤d．c. 若J(E)非空，则在J(E)中随机选择一个合成任务作为该解中的第E+1个位置处的合成任务，并判断原解E位置后的合成任务与新加入的合成任务与之间是否有冲突，若没有冲突，则后续任务依次顺延，得到新解；若有冲突，则删除原解中冲突的合成任务，补全解序列直至没有可插入合成任务．d. 若J(E)为空，则选择不同轨道的可行合成任务安插在E+1位置，补全解序列直至没有可以插入的合成任务．3 仿真实例仿真实验的测试算例参考文献[23]的配置生成算例，任务目标是在中国区域内随机生成．共21组算例，任务数量为100~700，增量步长为100，观测时间为5～7 s，卫星数量为3．卫星的视场角度分别为3°，5°和8°；单次开机时间分别为200，150，180 s；侧摆角范围为45°；开机稳定时间为10 s；卫星单轨的固存为100，能量为100．测试的实验环境为Windows10，2.0 GHz CPU，1 GiB内存的计算机上运行，采用Matlab R2014a实现编程．本研究主要考虑基于MS任务合成方法与未考虑任务合成条件的两种观测模式下的改进蚁群算法的性能对比．蚁群算法的实验参数设计：迭代次数为60；信息素参数为1；期望因子为2；全局信息素挥发系数为0.6；局部信息素挥发系数为0.2；当任务数量分别为100~300，400~600及700时，蚂蚁数量分别为10，15及20．为避免实验部分赘述，本研究只列出部分代表性实验结果．当任务规模为100，300，采用1颗卫星进行观测时的迭代收益变化情况分别见图2和3，具体实验结果(观测的元任务数量和观测收益)见表1，图中：V为收益；N1为迭代次数．当任务数量为100时，采用传统的观测方式收益较高．当任务数量增加时，采用基于MS任务合成方法的优势较明显；当任务规模较小时，任务分布相对稀疏，卫星资源相对充足，满足约束条件的任务基本都可以被观测到．在资源充足的条件下，对元任务的观测更加灵活；但通过任务合成后，合成任务的观测机会可能会减少，对合成任务的观测也不像元任务那样灵活．所以在资源充足条件下，通过任务合成而缩小解的搜索空间的方法是不明智的．10.13245/j.hust.211012.F002图2任务数为100的任务观测收益1—基于MS任务合成；2—任务未合成(下同)．10.13245/j.hust.211012.T001表1两种任务合成模式下的实验结果任务数量未考虑任务合成基于MS任务合成元任务数收益元任务数收益1003621432212200432734634030044282573834004830069435500513161056936004932597659700483369262610.13245/j.hust.211012.F003图3任务数为300的任务观测收益当采用3颗卫星进行观测时，实验情况与卫星数量为1时类似，当任务数量较小卫星资源相对充足时，采用传统观测方式较为灵活，观测收益较高；当任务数量较大时，采用基于MS合成策略的优势较明显．图4和5为当任务数为400，600时的迭代收益变化情况，随着问题规模变大，任务变得更为密集，问题受卫星资源约束影响较大，此时基于MS任务合成算法的观测收益明显优于未经任务合成的收益．在此种情况下，通过任务合成能有效避免任务间的冲突及节约卫星资源能耗来提高对任务的观测率．10.13245/j.hust.211012.F004图4任务数为400的任务观测收益10.13245/j.hust.211012.F005图5任务数为600的任务观测收益图6和7分别列出了当卫星数为1和3时，两种观测模式下随机10次实验的平均实验时间，图中：H为实验时间；n1为目标任务数．不难发现：当卫星数量为1时，考虑任务合成花费的时间多10 s左右；当卫星数量为3时，任务数量多于500时采用任务合成的算法时间逐渐低于未考虑任务合成的实验时间．研究表明基于MS的求解算法是可行有效的．10.13245/j.hust.211012.F006图6观测卫星数为1的实验时间1—考虑任务合成；2—未考虑任务合成(下同)．10.13245/j.hust.211012.F007图7观测卫星数为3的实验时间综上实验结果，对于较大规模任务密集的卫星任务规划问题，考虑基于MS任务合成的求解算法优于传统模式下的观测结果．