本发明涉及卫星技术领域，特别是涉及通信约束下面向复合任务的异构多星在线协同方法。
背景技术：
分布式对地观测卫星系统呈现异构化趋势，观测任务请求的复合性逐渐增强，同时复合任务中各子任务之间会存在渐次可调度特性，使得多星在线协同任务调度机制与算法面临新的挑战，因此需要针对通信约束下面向复合任务的异构多星在线协同任务调度问题进行研究。
技术实现要素：
优选地，将复合任务分为前摄复合任务和渐次复合任务，对于前摄复合任务，每当该复合任务发布时，采用一次性调度；对于渐次复合任务，后一子任务在前一子任务完成之后生成并发布，采用渐次性调度。
优选地，若应用场景中只存在前摄复合应急任务，则在第o″批应急任务发布后，将在线协同调度问题构建为如下混合整数线性规划(milp)模型：
若应用场景中包括渐次复合紧急任务，则在第o″批中渐次应急任务j″的第p″个子任务生成并发布时，将在线协同调度问题构建为如下混合整数线性规划(milp)模型：
其中，
coiojp+(siojpk+prik)yiojpk+olfiojp(yiojpk-1)≤coik(2)
coik+(sikojp+projp)yikojp+olfik(yikojp-1)≤coiojp(3)
coio′j′p′+(sio′j′p′ojp+priojp)yio′j′p′ojp+olfio′j′p′(yio′j′p′ojp-1)≤coiojp(4)
(triop+projp)xiojp+sikojpyikojp+sio′j′p′ojpyio′j′p′ojp≤coiojp(5)
prikzik+siojpkyiojpk≤coik(6)
(oesiojp+projp)xiojp≤coiojp(7)
(oesik+prik)zik≤coik(8)
coiojp≤olfiojpxiojp(9)
coik≤olfikzik(10)
beiojp+projp＝coiojp(11)
beik+prik＝coik(12)
coi0＝0,coi(vi+1)＝tl(13)
zi0＝1,zi(vi+1)＝1(14)
xiojp＝{0,1},yiojpk＝{0,1},yikojp＝{0,1},yio′j′p′ojp＝{0,1},zik＝{0,1},wiojp＝{0,1},caiojp＝{0,1}(15)。
优选地，采用有向无环图(树状图)对复合任务进行表示，其中根节点是复合任务，除根节点之下的节点表示分解后的子任务，所述子任务与子任务完成需执行的方法相对应，连接边代表着任务之间的关联关系，对地观测卫星接收到复合任务后，根据局部知识，对其进行分解，得到局部任务结构视图；当接收到其他对地观测卫星通信传递来的信息时，对局部任务结构视图进行更新和维护。
优选地，渐次复合任务对应的全局任务视图是渐次动态变化的，每个子任务对应于不同的能力需求，而不同的能力分布于不同的对地观测卫星上。
优选地，所述对地观测卫星leo通过geo作为中继节点进行通讯。
附图说明
图1是的示意图。
图1是基于gpgp的多星在线协同机制框架。
图2是全局任务视图示意图。
图3a和图3b局部任务视图示意图。
图4是前摄复合任务的全局任务视图。
图5是渐次复合任务的全局任务视图。
图6a、图6b和图6c示出各算法在任务空间分布u(-45,45)和不同滚动调度周期下的结果，其中，图6a表示总收益；图6b表示总通信次数；图6c表示不同完成程度的应急任务百分占比。
图7a、图7b和图7c示出各算法在任务空间分布u(-45,45)和不同滚动调度周期下的结果，其中，图7a表示总收益；图7b表示总通信次数；图7c表示不同完成程度的应急任务百分占比。
图8a、图8b和图8c示出各算法在任务空间分布u(-45,45)和不同滚动调度周期下的结果，其中，图8a表示总收益；图8b表示总通信次数；图8c表示不同完成程度的应急任务百分占比。
图9a、图9b和图9c示出各算法在任务空间分布u(-45,45)和不同滚动调度周期下的结果，其中，图9a表示总收益；图9b表示总通信次数；图9c表示不同完成程度的应急任务百分占比。
图10a、图10b和图10c示出各算法在任务空间分布u(-45,45)和不同滚动调度周期下的结果，其中，图10a表示总收益；图10b表示总通信次数；图10c表示不同完成程度的应急任务百分占比。
具体实施方式
异构分布式对地观测卫星系统是位于不同轨道上的卫星集合，并且各对地观测卫星配备有多种不同类型的成像载荷(可见光、红外、高光谱和多光谱等等)，同时各个卫星的载荷类型也不相同。从而，系统内各星之间可以协同完成一复合任务。
表1各常用对地观测载荷类型及其成像特点与实际应用
为了表述的统一简便，对本章后续中所用到的字符进行统一定义：
下标
i,i′:对地观测卫星编号，i＝1,2,...,n1
g:通信中继节点编号，g＝1,2,...,n2
j,j′:应急观测任务编号，j＝1,2,...,u
j0:前摄复合任务编号，j0＝1,2,...,u
j1:渐次复合任务编号，j1＝1,2,...,u
k:常规任务编号，k＝1,2,...,vi
p,p′:子任务编号，p＝1,2,...,bj
o,o′,o″:应急任务批次编号，o＝1,2,...,l
参数量
h:整个调度区间
tl:整个调度区间h的时长
n1:系统中对地观测卫星的数量
n2:可用通信中继节点的数量
θ:可用简单任务的总数量
u:一批应急任务中的任务数量
l:整个调度区间h内的应急任务总批次
vi:对地观测卫星i上已上传的常规任务数量
ci:对地观测卫星i的能力集合
bj:应急任务j中的子任务数量
sproll:对地观测卫星的侧摆角速度
maxθ:对地观测卫星的最大侧摆角
cojp:应急子任务ojp所需的卫星能力
projp:应急子任务ojp的成像时长
eojp:应急子任务ojp的收益，由管理者或星上决策给出
ecojp:完成应急子任务ojp时的收益系数，由管理者或星上决策给出
θiojp:对地观测卫星i上应急子任务ojp的观测角度
cik:对地观测卫星i上常规任务k所需的卫星能力
prik:对地观测卫星i上常规任务k的成像时长
eik:对地观测卫星i上常规任务k的收益，由管理者或星上决策给出
wiojp:当应急子任务ojp可在对地观测卫星i上调度执行时，等于1，否则，等于0。
本发明中所研究的问题特性如下：
4.在线调度：星上计算能力弱，近实时性要求高，即要求算法简便快捷实用；
5.复合应急任务分解的动态性：面向火山爆发、森林火灾等星上即时发现的任务，针对同一目标，其后续任务的星上生成具有高度动态性；
6.卫星自身的能力约束：每个卫星上面搭载有限的成像载荷，且一次只能有一种成像载荷工作。
本发明中，子任务是指简单任务，简单任务被定义为不能进一步简化的任务。通常，它对应于只需要单颗卫星就能完成的单个任务。
对于第o批中的简单应急任务j，其初始型描述形式是一个多元组ptoj＝<idoj，longitudeoj，latitudeoj，coj，proj，eoj＞，ptoj＝ptoj1，bj＝1
—idoj是一标识符；
—longitudeoj是地面应急观测目标的经度坐标值；
—latitudeoj是地面应急观测目标的经度坐标值；
—coj是所需的卫星能力；
—proj是成像时长；
—eoj是任务完成后所得的收益。
相对应的特定型描述形式是一多元组＜idoj,lsati,oesioj,olfioj,coj,proj,eoj,θioj＞。
复合任务是指可以分解成一系列简单子任务的任务，而所有这些子任务都面向同一观测目标(点目标或区域)，可见一个复合任务对应于地面上的一个目标。对于第o批中的复合应急任务j，其初始型描述形式为：
其中，ptojp＝＜idojp,cojp,projp,eojp＞。
针对特定的对地观测卫星i，应急子任务ptojp将其形式转换为特定形式<idojp，lsati，oesiojp，olfiojp，cojp，projp，eojp，θiojp>。
复合任务分为前摄复合任务和渐次复合任务。在到达系统之前，前摄复合任务具有完整的描述形式，其子任务齐备。相比之下，渐次复合任务中，后一个子任务会在前一个子任务执行完成后生成。对于同一观测目标，通过对有关目标及其周围环境的观测，收集到新的目标信息，从而在星上可能生成新的后续子任务，则只有在前序的子任务完成之后，新生成的子任务才变得可用。
也就是说，前摄复合任务是指针对观测目标的已知信息较多时，该复合任务及其分解后的一系列子任务是一次性给定的，比如水灾监测、地震灾后观测评估等等应用领域。
相对应的调度方式是一次性调度，即对复杂任务中的全部子任务进行一次性分解和一次性协同分配调度。
针对前摄复合任务的在线协同调度，存在以下特点：
1.只需一次协同调度；
2.对目标信息的先验知识要求高；
3.随着复合任务中各子任务的依次执行，根据所获取的实时目标信息，可能会需要对后续子任务进行动态调整(如改变任务属性，取消已安排的后续子任务等等)，从而重调度成本大。
渐次复合任务是指针对观测目标的已知信息较少或完全未知时，该复合任务所包含的子任务是渐次生成的，即只有当前一子任务执行完成之后，并进行星上图像数据处理，以判别是否发布下一子任务，比如火山爆发、森林火灾等应用领域。
相对应的调度方式是实时渐进式调度，即当前一子任务完成后，才对后续子任务进行决策和分配调度。
其主要特点是采用渐进式调度，后续子任务的调度可充分利用前续子任务执行过程中获取的观测目标信息。
从多对地观测卫星系统协同角度，本发明的问题中存在调度计划之间的交叉依赖关系(xd)，即复合任务中一系列子任务存在时序先后约束，则需要将该复合任务分配给一卫星子集。
问题求解是对工作模式进行分配并对任务操作进行调度。在本发明中，各子任务的完成需要具有特定载荷能力的卫星，则需要决定执行任务的卫星子集并对任务进行调度。
复合任务中的子任务约束
coioj(p-1)＜bei′ojp，i′≠i，p＝2,...,bj。
在对地观测卫星i上调度安排第o批中应急任务j的第p个子任务，需满足：
(beiojp＞oesiojp)∩(coiojp＜olfiojp)＝1，otwiojp＝[oesiojp,olfiojp]。
3.子任务渐次生成约束
对于渐次复合任务子任务是动态生成的，并且后续子任务只有在前续子任务完成之后才变得可用。
4.所需的卫星能力约束
5.相互关联的子任务收益
异构分布式对地观测卫星系统
前摄复合应急任务的时效性
定义针对该子任务的时效性指标为：
其中
渐次复合应急任务的时效性
若应用场景中只存在前摄复合应急任务，则在第o″批应急任务发布后，将在线协同调度问题构建为混合整数线性规划(milp)模型，如下：
若应用场景中包括渐次复合紧急任务，则在第o″批中渐次应急任务j″的第p″个子任务生成并发布时，将在线协同调度问题构建为混合整数线性规划(milp)模型，如下：
决策变量
xiojp＝{0,1},yiojpk＝{0,1},yikojp＝{0,1},yio′j′p′ojp＝{0,1},zik＝{0,1},wiojp＝{0,1},caiojp＝{0,1}(15)
针对集中-分布式架构的合同网协议协同机制存在以下局限性：一是合同网协议中的通信是采用广播通信方式，所需的通信次数多，相应的通信代价高；二是复合任务的任务约束关系只能通过拍卖商这一中心节点进行协同控制，交互次数多，不适用于协同调度耦合度高的复合任务；三是对中心节点的能力要求高，因为拍卖商作为中心节点，需要具备复合任务的分解能力和协同能力。
本发明基于上述局限，针对分散式架构，基于通用部分全局规划，将已提出的在线协同算法与复合任务之间的约束相结合，形成异构多星在线协同机制。
首先，每颗对地观测卫星上执行单星在线调度算法，调度该对地观测卫星的常规任务和上述协同分配算法分配给该对地观测卫星的应急观测任务，所述单星在线调度算法包括：
除上述两种调度时刻点之外，不在任何其他时刻点进行调度。
更具体地，在所述单星在线调度算法中，在t-驱动的调度时刻点的具体调度算法如下：
输入：
–已到达且在t-驱动调度时刻点之前未被调度的应急观测任务集合；
–已接收且在t-驱动调度时刻点之前未被调度的常规观测任务集合；
输出:
具体步骤如下：
步骤12将和整合为一个观测任务集合；
步骤13按照设定的启发式规则，对整合后的观测任务集合中的任务进行排序；
步骤14按照排序，对所述整合后的观测任务集合中的任务一一进行调度，以确定是否将之加入到中，直至所述整合后的观测任务集合中再无任务可加入中，
在c*-驱动的重调度时刻点的调度算法如下：
—在调度时刻点t之前已到达且未调度的应急观测任务集合；
步骤22根据设定的启发式规则，对中的应急观测任务进行排序；
步骤23按照新的任务次序，一一选取中的应急观测任务并对进行修订，直至中再无应急观测任务可加入中，
步骤24输出已修订的调度计划
gpgp是一递增且渐进的协同机制，并对最优对地观测卫星协同策略进行近似，因为gpgp中一次性的协同决策并不能完全反映在已调度活动的执行过程中发生的动态变化或者新任务的到达。而活动执行会出现应急突发情况，新任务会到达对地观测卫星，或者对地观测卫星所接收到来自其他对地观测卫星的新消息或更改过的消息时，对地观测卫星会对当前的调度方案进行重新评估，修订自身的协同策略，进而让其他对地观测卫星修订自身的调度方案和协同策略。
可见，gpgp将该问题分解为一系列的异步且渐进的本地优化问题，每个对地观测卫星有相应的本地优化问题，其中协同部分是由gpgp解决，而调度部分是由本地调度器解决；来对全局优化问题(对各对地观测卫星进行任务选取并排序，生成具有最高组合收益的方案)进行近似求解。每个本地优化问题都包括对本地对地观测卫星任务的选择并排序；而这些本地优化问题也会进行修订，通过其他对地观测卫星对本地对地观测卫星任务的承诺以及来自其他对地观测卫星的调度结果来实现，以反映其他对地观测卫星的任务与本地任务之间的动态渐进式互动。
相对于面向对地观测卫星分析的协同机制，gpgp是面向任务分析的协同机制。面向对地观测卫星分析的协同机制是通过分析对地观测卫星的内部结构和推理过程，进而设计协同策略，而面向任务分析的协同机制则是在确定任务结构，理清任务之间关联关系的基础上，对协同策略进行设计。面向任务分析的协同机制认为协同是管理任务之间关联关系的过程，则对任务之间的关联关系进行分类和定义，并根据关联关系的不同，设计不同的协同策略。此类协同策略注重定量计算任务之间的关联关系，更新全局任务视图和各对地观测卫星的局部任务视图，而对对地观测卫星的认知模型不作特别要求。
为形式化描述gpgp及其相应的协同问题，采用taems(taskanalysis，environmentmodeling，andsimulation)框架对复合任务进行形式化描述。taems框架有两点特征：一是对子任务之间关联关系的明确和定量表示，即用函数的形式描述活动选择与时序对性能的影响；二是从多个抽象层次对任务结构进行表示。
分散式架构下，各对地观测卫星的本地调度、执行、通信和信息采集等模块共同组成协同模块的平台基础，而协同模块可为本地调度器提供信息，包括对局部任务视图的修订以及对任务视图中子任务的本地和非本地承诺，从而使本地调度器生成更好的调度计划。
基于gpgp的异构多星在线协同机制主要由四个部分组成：
1.局部任务视图交互；
针对当前复合任务，每个对地观测卫星仅具有主观的任务视图。该部分是指各对地观测卫星对自身的局部任务结构视图，同其他对地观测卫星进行交互。在此交互过程中，会发现自身任务结构与共享任务结构之间存在的协同关联关系。
2.调度结果通信传递；
3.方法冗余冲突消解；
该部分对应于m-cbba算法或m-acbba算法中一致性构建阶段的冲突消解规则。当生成承诺时，对地观测卫星会等待其他非本地承诺的到达，选取其中一个最佳对地观测卫星进行方法执行，同时其余对地观测卫星撤销相应的承诺。
4.使能协同关系处理；
在gpgp协同机制中，任务视图是各对地观测卫星用于交互各自对复合任务认知的主要信息表现形式。各对地观测卫星在交互过程中，更新和维护任务视图，并将视图中的约束关系应用于束构建和一致性构建中，从而实现协同。
在taems中，每个复合任务都由一系列子任务组成，并且子任务之间存在关联关系，则采用有向无环图(树状图)对复合任务进行表示，其中根节点是复合任务，除根节点之下的节点表示分解后的子任务，方形节点表示任务完成需执行的方法(对应于特定的对地观测卫星)，连接边代表着任务之间以及任务与方法之间存在的关联关系。可见一任务视图代表了一个复合任务的分解过程，因此对地观测卫星接收到复合任务后，根据局部知识，对其进行分解，得到局部任务视图；当接收到其他对地观测卫星通信传递来的信息时，对局部任务视图进行更新和维护。方形节点不是必须的，例如可以直接与各leo相对应。
图2是一全局任务视图。复合任务t通过任务分解，可以将其分解为t1、t2和t3三个子任务(parent-childrelation)，这里t的收益被定义成t1、t2和t3三者中的最大收益。子任务t1的完成是需要由对地观测卫星a的方法(或者功能、能力)a1和对地观测卫星b的方法b1共同完成。子任务t5与子任务t4构成使能关系(enablerelation)，因此系统必须先完成子任务t5，才能去完成子任务t4。局部任务视图的描述与之类似，只是视图中只有自已一个对地观测卫星，如图3所示。
对于前摄复合任务，在其发布时，所有一系列子任务均给定，且相互之间存在使能关系；每个子任务对应于不同的能力需求，而不同的能力分布于不同的对地观测卫星上。因此，在其全局任务视图中，叶节点表示具体对地观测卫星上的能力，如图4所示。
对于渐次复合任务，在其发布时，子任务未完全给出，而是后一子任务是在前一子任务执行完成后才生成的，相互之间存在使能关系，因此渐次复合任务对应的全局任务视图是渐次动态变化的。每个子任务对应于不同的能力需求，而不同的能力分布于不同的对地观测卫星上，如图5所示。
表2三颗对地观测卫星和三颗geo卫星的轨道参数设置
我们对比了面向分布式卫星系统的四种在线协同调度算法，包括单项任务下的合同网协议算法si-cnp，批次任务下的合同网协议算法ba-cnp，改进的一致性束算法m-cbba和改进的异步一致性束算法m-acbba。
我们采用三项性能指标，分别是总收益，通信总次数和在已调度成功的应急任务中任务完成度分布。这三项指标的具体描述如下：
(1)系统总收益，指分布式卫星系统在整个调度区间内的所有已调度成功的任务收益之和。
(2)通信总次数。通信总次数是是三种单向通信情况的通信次数之和，分别是leo向geo发起通信，geo向leo发起通信以及geo之间单向通信。
(3)已调度成功的应急任务中任务完成度分布。对于复合任务的调度安排，存在不同的任务完成度。若一复合任务包括两个子任务，且仅有第一个子任务调度成功，则任务完成度为50％，同样，若一复合任务包括三个子任务，且前两个子任务调度成功，则任务完成度为67％。
面向前摄复合任务的实例结果分析
(1)场景1：每颗对地观测卫星搭载三种不同的成像载荷；收益系数为1.5；整个调度区间内的应急任务均为前摄复合任务，包括可分解为两个子任务和可分解为三个子任务的前摄复合任务，各占总数量的50％。
表4各算法在不同参数条件下所取得的总收益
表5当t为6min时，与si-cnp相比，各算法的收益增长(％)
表6当t为12min时，与si-cnp相比，各算法的收益增长(％)
表7在不同参数条件下各算法所需要的通信次数
图6表明随着应急任务到达速率增加，系统的总收益和总通信次数增加。m-acbba算法所取得的总收益最高，同时m-cbba算法所需的通信次数最少。在滚动调度周期t为12min时，si-cnp和m-acbba算法对应100％完成的复杂应急任务比例大于滚动调度周期t为6min时的比例。
综上所述，当系统中的通信成本代价高时，m-cbba算法可在系统总收益和通信次数之间取得平衡，而当系统的通信成本低时，m-acbba算法是获得高系统总收益和高应急任务调度成功比例的最佳选择。
(2)场景2：每颗对地观测卫星搭载两种不同的成像载荷；收益系数为1.5；整个调度区间内的应急任务均为前摄复合任务，包括可分解为两个子任务和可分解为三个子任务的前摄复合任务，各占总数量的50％
与场景1中的表4相比，本场景表9中各算法所取得的收益值有所下降；与场景1中的表7相比，本场景中表10各算法所对应的通信量基本一致；与与场景1中图6(c)相比，本场景图7(c)显示完成度为100％的应急任务比例明显降低，同时仅完成第一个应急子任务的比例上升，对应于完成度为33％和50％的比例之和，说明任务协同调度完成的效果明显降低。
综上所述，每颗对地观测卫星上搭载的成像载荷数量减少，会导致系统总收益值下降，任务完成度降低，而通信次数并未降低。则对于通信成本高的情况，尽可能多搭载成像载荷更有利。
表9各算法在不同参数条件下所取得的总收益
表10在不同参数条件下各算法所需要的通信次数
(3)场景3：每颗对地观测卫星搭载三种不同的成像载荷；收益系数为1.2；整个调度区间内的应急任务均为前摄复合任务，包括可分解为两个子任务和可分解为三个子任务的前摄复合任务，各占总数量的50％
与场景1中的表4相比，本场景表11中各算法所取得的收益值有所下降；与场景1中的表7相比，本场景中表12各算法所对应的通信量基本一致；与与场景1中图6(c)相比，本场景图8(c)显示完成度为100％的应急任务比例明显降低，同时仅完成第一个应急子任务的比例上升，对应于完成度为33％和50％的比例之和，说明任务协同调度完成的效果明显降低。
综上所述，收益系数减小，会导致系统总收益值下降，任务完成度降低，而通信次数并未降低。则要提高前摄复合任务的任务完成度，需保证足够高的收益系数。
表11各算法在不同参数条件下所取得的总收益
表12在不同参数条件下各算法所需要的通信次数
面向渐次复合任务的实例结果分析
(4)场景4：每颗对地观测卫星搭载三种不同的成像载荷；收益系数为1.5；整个调度区间内的应急任务均为渐次复合任务，包括可分解为两个子任务和可分解为三个子任务的渐次复合任务，各占总数量的50％
与场景1中的表4相比，本场景表13中各算法所取得的收益值有所下降；与场景1中的表7相比，本场景中表16各算法所对应的通信量基本一致；与场景1中图6(c)相比，本场景图9(c)显示完成度为100％的应急任务比例降低，同时仅完成第一个应急子任务的比例上升，对应于完成度为33％和50％的比例之和，说明任务协同调度完成的效果明显降低。
综上所述，由于存在通信约束，则对于渐次复合任务的星上协同调度效果弱于前摄复合任务。
表13各算法在不同参数条件下所取得的总收益
表14当t为6min时，与si-cnp相比，各算法的收益增长(％)
表15当t为12min时，与si-cnp相比，各算法的收益增长(％)
表16各算法在不同参数条件下所需的通信次数
(5)场景5：每颗对地观测卫星搭载两种不同的成像载荷；收益系数为1.5；整个调度区间内的应急任务均为渐次复合任务，包括可分解为两个子任务和可分解为三个子任务的渐次复合任务，各占总数量的50％
与场景4中的表13相比，本场景表18中各算法所取得的收益值有所下降；与场景4中的表16相比，本场景中表19各算法所对应的通信量基本一致；与与场景4中图9(c)相比，本场景图10(c)显示完成度为100％的应急任务比例明显降低，同时仅完成第一个应急子任务的比例上升，对应于完成度为33％和50％的比例之和，说明任务协同调度完成的效果明显降低。
表18各算法在不同参数条件下所取得的总收益
表19各算法在不同参数条件下所对应的通信次数
最后需要指出的是：以上实施例仅用以说明本发明的技术方案，而非对其限制。本领域的普通技术人员应当理解：可以对前述各实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换；这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的精神和范围。