近年来，遥感卫星在轨数量不断增多、星座规模不断扩大，卫星姿态敏捷机动能力不断提高，这些都对系统应用效能的保障与提升带来了挑战。在单星层面，敏捷卫星具备三轴联合的姿态调整能力，并可以与成像过程相结合形成多点、拼幅、立体、主动推扫等成像模式，能有效提高卫星的工作效率；从系统的角度，军、民、商界均在部署数颗甚至数十颗遥感卫星组成的卫星星座，以期采用多星协同的方式完成诸如目标搜索、识别、跟踪等复杂任务。在这一背景下，如何更好地进行多星的任务分配、单星的任务规划、星间的任务协同，是充分发挥系统能力、获取更高收益所必须解决的关键问题^[1]。

由于任务数量多、可选模式丰富、时效性要求高，面向多星的任务分配需要依靠良好的机器算法予以实现；同时也可以发挥系统运行的自主能力、降低人力负担。目前国内外针对分布式星群的任务分配问题，主要采用集中式和分布式2种基本模式。在研究和实际应用中多采用集中式任务分配方法，法国的Lemaitre等^[2-3]针对敏捷卫星任务规划问题，提出了约束规划模型。

Potter等^[4]对启发式算法在任务分配中的应用很好地解决了不同任务需求对分配方式的要求。这种集中式任务规划的方法灵活性较低，且难以适应卫星在轨的实时状态变化。因此，分布式卫星的任务分配问题对规划算法提出了新的要求，即更高的灵活性、更低的计算消耗以及更快的星上响应速度。这使得分布式任务规划方法在解决这类星上任务规划问题中更具优势。

国外的分布式任务规划系统相对成熟，其中NASA的Richards等，针对分布式卫星星座的在轨自主运行问题，研发了星上自主规划系统(distributed spacecraft coordination planning and scheduling，D-SpaCPlanS)，该系统采用灵活的层次化组织结构，能够很好地适应资源或任务的变化^[4]。国内很多学者也对分布式任务规划方法进行了研究。王冲等^[5]提出基于“分治-合作”策略的多卫星中心协同规划方法，在分析各卫星中心遥感资源能力和中心之间关系的基础上建立了多卫星中心协同规划问题模型，并提出了多中心合作协同进化规划算法，将集中式优化问题转化为分布式优化问题，使得多颗卫星之间能够独立地进行决策。向仍湘^[6]研究了敏捷卫星任务调度问题，并且针对不同的任务规模，设计了不同的求解算法。陈恺建^[7]立了基于多智能体系统(multi-agent system，MAS)的遥感卫星分布式框架模型，并参考合同网协议，设计对地观测任务的投标模式，以此来实现遥感卫星的任务分配。

综合来看，传统的集中式任务分配方法对于任务规模和需求都不变的静态情况效果较好。而对于实际的系统而言，新任务的不断加入是一种常态，这就需要一种适用于动态情况下任务分配的规划方法。分布式算法能够比较好地解决这一问题，在时间维度内实现多星的协同、交互，以在系统层面更好地利用资源。本文采用基于合同网络算法的分布式任务分配方法，将遥感卫星星座/星群中的每个成员看成合同网中的一个独立的个体，既可以进行任务拍卖，也可以进行任务投标。深入结合敏捷卫星特点，以完成任务需求的总收益最高为目标，综合采用买卖、交换和置换3种合同类型，研究提出了一种适用于动态情况的分布式任务协同分配方法。

1 分布式任务模型构建 1.1 问题描述

多星多任务分配和协同应用如图 1所示，由于分布式卫星规模庞大、种类繁多，因此面向这类分布式卫星的多星多任务规划属于NP难问题。多星多任务分配即通过构建分布式卫星模型(用于描述卫星在轨运行状态及执行任务的相关约束条件)，构建任务模型(用于描述任务的相关需求)，设计算法和策略，建立卫星空间和任务空间两者之间的映射关系，最终使得分布式卫星的系统任务规划问题得到解决得一个过程。

设有N_S个卫星，以A={S₁, S₂, …, S_NS}表示，任何一个卫星可以用四元组描述：S_m={I_m, W_{m, n}, R_m, E_m}，其中：I_m代表卫星的标识；W_{m, n}代表卫星S_m与任务M_n的可见时间窗口集合。W_{m, n}={W_{m, n}¹, …, W_{m, n}^p, …, W_{m, n}^q}，其中W_{m, n}^p代表S_m与M_n的第p个可见时间窗口，q表示可见窗数量。每个时间窗口可以由五元组描述：W_{m, n}^p={S_m, M_n, T_s, T_e, G_{m, n}}，其中，T_s代表时间窗口开始的时间，T_e代表时间窗口结束时间，G_{m, n}代表卫星S_m执行M_n需的卫星姿态角。R_m表示卫星当前可用的存储容量上限(根据任务分配过程实时更新)。E_m表示卫星当前可用的电量上限(根据任务分配过程进行实时更新)。

N_M个任务，以任务集合B={M₁, M₂, …, M_NM}表示，每个任务由五元组M_n={I_n, L_n, T_LSⁿ, T_Dⁿ, V_n}表示，其中：I_n为任务的唯一识别编号；L_n表示M_n的位置信息，可以表示为L_n=l₁ⁿ, l₂ⁿ, l₃ⁿ，其中，l₁、l₂、l₃分别为M_n的经度、纬度和高度；T_LSⁿ表示用户给定的任务的最晚开始时间；T_Dⁿ表示任务所需的持续执行时间；V_n表示任务M_n的给定优先级，优先级越高，完成任务得到的收益越高。

用F_m={M_m¹, M_m², …, M_m^f_m}表示成功分配给卫星S_m的任务集合，其中f_m表示成功分配给卫星S_m的任务数量。任务分配结果需要保证每一个任务只有一颗执行卫星，即对于∀i, j∈{1, 2, …, N_S}，若i≠j，则必须满足S_i∩S_j=Ø。同时还要满足一颗卫星在同一时间下，只执行一个任务。最后以卫星完成任务后的整体收益最大化来进行分配任务^[8]。

为便于规划，通常卫星对任务的开始执行之间取可见窗的最左侧。但当同一卫星同时对2个任务可见，且可见窗有重叠部分时，则不能直接取左侧可见窗左侧为任务的开始执行时间。图 2给出了当可见窗发生冲突时的解决方案，这种情况下，在可见窗满足要求的情况下，考虑任务间的转换时间，将下一任务顺序后移即可。

1.2 任务收益计算

由于任务的优先级不同，收益的大小也不同，传统的收益函数只考虑收益总和，即：

$ P = \sum\limits_{i = 1}^{{N_S}} {\sum\limits_{j = 1}^{{N_M}} {{V_j}} } \cdot \rho _i^j $

(1)

式中：P为总收益值，V_j表示任务M_j的收益；ρ_i^j表示任务M_j分配给卫星S_i的情况，若任务M_j成功分配给卫星S_i，则ρ_i^j值为1，否则ρ_i^j值为0。

但在实际情况中，在较快的时间内开始任务也应该被考虑到收益中，即任务执行的越早、产生的应用价值越高。本文建立收益惩罚函数，并给出每个任务的期望开始时间e和任务的最晚开始时间T_LS^j，对开始时间较晚的标书予以收益惩罚：

$ f(M_i^j) = \left\{ {\begin{array}{*{20}{l}} {1,\;\:t_i^j \le e}\\ {\frac{{t_i^j - T_{LS}^j}}{{e - T_{LS}^j}},\;\:e < t_i^j < T_{LS}^j} \end{array}} \right. $

(2)

式中：f(M_i^j)为收益惩罚系数；t_i^j为任务开始执行时间。图 3给出了惩罚函数值随任务开始执行时间变化的示意图，从图中可以看出，当任务的实际开始执行时间晚于期望的开始时间时，其收益惩罚函数值越小。

应用收益惩罚函数后的任务收益函数为：

$ P = \sum\limits_{i = 1}^{{N_S}} {\sum\limits_{j = 1}^{{N_M}} {{V_j}} } \cdot \rho _i^j \cdot f(M_i^j) $

(3)

2 基于合同网的分布式任务规划与调度

传统的集中式任务分配对于静态任务集合，也就是任务规模和范围都不变的情况下，效果较好。而真实的卫星星座/星群任务调度过程中，经常会有新任务的加入。这就需要一种新型的任务规划模式，既能对静态任务集合进行分配，也能在任务集合动态变化情况下进行分配。因此本文引进合同网的方法，将其应用到分布式任务分配中，综合采用买卖合同、交换合同、置换合同这3种合同处理方式，来建立任务优化分配算法^[9-10]。

2.1 合同网算法模型

合同网算法以分布式方式处理多星任务协商、认领、分配和规划等操作。合同网协商所需数据由星间链路实现，合同网协议按照招标、投标、评标、交换、买卖和置换等方式，基于星间链路迭代完成。合同网算法的任务分配模型如图 4所示。

本文设计了遥感卫星的合同网收益模型、多星合同网算法模型及仿真验证。基于合同网的星群任务规划招投标系统的工作流程为：

1) 地面或主星收集用户的任务需求，形成招标书，并发放给作为投标方的卫星；

2) 用户作为投标方比对自身资源和任务信息，在满足基本要求的前提下填写标书；

3) 地面或主星作为招标方，收集所有标书后，对其进行评估，择选最优方案完成招标过程。

2.2 任务优化分配算法

1) 基于买卖合同的任务分配。

买卖合同可以描述为四元组{S_i, S_j, M_i^j, U_{i, j}^sale}，其中M_i^j是卫星S_i迁移给卫星S_j的任务，U_{i, j}^sale是任务M_i^j迁移后整体系统效能的变化。

设卫星S_i将其任务集F_i中的任务M_i^k向市场公布，标底为该任务售出后对自己效能的影响：

$ U_i^ - (M_i^k) = {U_i}({S_i}\backslash \{ M_i^k\} ) - {U_i}({S_i}) $

(4)

式中：U_i^-(M_i^k)表示卫星S_i售出任务M_i^k后效能的变化，U_i(S_i\{M_i^k})表示卫星S_i售出任务M_i^k后的效能，U_i(S_i)表示卫星S_i原本的效能。

针对任务M_i^k，卫星S_j买入该任务后效能的变化通过计算：

$ U_j^ + (M_i^k) = {U_j}({S_j} \cup \{ M_i^k\} ) - {U_j}({S_j}) $

(5)

式中:U_j⁺(M_i^k)表示卫星S_j买入任务M_i^k后效能的变化。

S_j参加竞标时对任务的最高出价为U_j⁺(M_i^k)，如果U_j⁺(M_i^k)>U_i^-(M_i^k)，S_j向S_i发送买卖合同竞标。S_i收到S_j的竞标信息后，若通过竞标，系统的整体效能变化可以表示为：

$ U_{i,j}^{{\rm{sale}}}(M_i^k) = U_j^ + (M_i^k) + U_i^ - (M_i^k) $

(6)

如果U_{i, j}^sale (M_i^k)>δ ^sale，其中δ ^sale>0为预先设置的阈值，并且在所有投标中，该方案对系统整体效能的改善效果最明显，则卫星S_i将通过卫星sat_j对任务M_i^k的竞标。

2) 基于交换合同的任务分配。

交换合同可以用{S_i, S_j, M_{i, j}, M_{i, j}, U_{i, j}^swap}描述，其中M_{i, j}是卫星S_i迁移给卫星S_j的任务，M_{i, j}是S_j迁移给卫星S_i的任务，U_{i, j}^swap是任务发生交换后整体系统效能的变化。

收到卫星S_i宣布的任务M_i^k后，受限于自身资源的约束无法满足买卖合同竞标的要求，则考虑进行填报交换合同，用其原有的任务M_j^l与卫星S_i的任务M_i^k进行交换。交换后系统的整体效能的变化量可以表示为：

$ \begin{array}{*{20}{c}} {U_j^{{\rm{ swap }}}(M_j^l,M_i^k) = {U_j}(({F_j} \cup \{ M_i^k\} \backslash }\\ {\{ M_j^l\} )) - {U_j}({F_j})} \end{array} $

(7)

卫星接受到标书后，首先计算该交换实现后自己的效能变化：

$ \begin{array}{*{20}{c}} {U_i^{{\rm{swap}}}(M_i^k,M_j^l) = {U_i}(({F_i} \cup \{ M_j^l\} \backslash }\\ {\{ M_i^k\} )) - {U_i}({F_i})} \end{array} $

(8)

接下来判断交换实现后系统整体效能的变化：

$ U_{i,j}^{{\rm{swap}}}(M_i^k,M_j^l) = U_i^{{\rm{swap}}}(M_i^k,M_j^l) + U_j^{{\rm{swap}}}(M_j^l,M_i^k) $

(9)

如果U_{i, j}^swap(M_i^k, M_j^l)>δ^swap，其中δ^swap>0为可预先设置的阈值，并且在所有投标中，该方案对系统整体效能的改善效果最明显，则卫星S_i将通过卫星S_j的交换竞标。

3) 基于置换合同的任务分配

置换合同可以描述为五元组{S_i, S_j, M_{i, j}, M_{j, null}, U_{i, j}^replace}，其中M_{i, j}是S_i迁移给S_j的任务，M_{j, null}是S_j舍弃的任务，U_{i, j}^replace是以上任务迁移和舍弃后系统效能变化。

收到S_i宣布的任务M_i^k后，S_j进行交换合同竞标，S_j放弃当前任务集中的任务M_{j, null}，同时接受来自S_i的任务S_{i, j}。经过这一系列的操作，系统的整体效能改变量可以表示为：

$ \begin{array}{*{20}{l}} {U_j^{{\rm{ replace }}}(M_i^k,M_j^l) = {U_j}(({F_j} \cup \{ M_i^k\} \backslash }\\ {{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \{ M_j^l\} ) - {U_j}({F_j})} \end{array} $

(10)

置换过程发生后系统整体效能的变化：

$ U_{i,j}^{{\rm{replace}}}(M_i^k,M_j^l) = U_i^ - (M_i^k) + U_j^{{\rm{replace}}}(M_i^k,M_j^l) $

(11)

如果U_{i, j}^replace(M_i^k, M_j^l)>δ^replace，其中δ^replace>0为预先设置的阈值，并且在所有投标中，该方案对系统整体效能的改善效果最明显，则卫星S_i将通过卫星S_j对任务M_{i, j}的竞标。

2.3 任务投标流程方法

在卫星进行任务投标前，首先执行以下步骤：

1) 可见时间窗的计算。

受限于卫星姿态机动能力、卫星成像模式、卫星轨道与目标位置关系，卫星对目标的执行时间需满足可见时间窗约束。首先可见时间窗的长度应满足任务给定的持续成像时长，即T_e-T_s>T_Dⁿ。其次，对于满足持续时间要求的时间窗口，要满足开始时间在最晚开始时间之前，即t_mⁿ < T_LSⁿ。

2) 确定任务执行时间。

对满足以上时间约束的时间窗口集合，按照时间顺序选择一个时间窗口，按照以下步骤判断是否能够执行任务，如不能则改换下一顺位时间窗口，迭代进行，直至得出能够执行任务或不能执行任务的结论。

① 准备时间计算。首先根据卫星当前姿态，以及即将执行任务的星体姿态角G_{m, n}，判断卫星是否需要进行姿态机动，计算姿态机动所需时间t_turn，即准备时间。

② 时间约束检验。提取前一观测任务的结束时间，判断在前一观测任务结束后，若要完成姿态机动开始当前任务，当前任务的开始时间和结束时间是否依然满足可见时间窗的要求。

③ 资源约束检验。卫星资源对成像的约束包括：任务消耗电量小于卫星当前可用电量E_mⁿ，任务所需固存小于卫星当前可用存储容量R_mⁿ。通过下式计算电源及存储容量消耗：

$ {{C_E} = t_{{\rm{ turn }}}^j \times \lambda } $

(12)

$ {{C_R} = {T_D} \times \beta } $

(13)

$ {{C_E} < {E_m}} $

(14)

$ {{C_R} < {R_m}} $

(15)

式中：C_E为执行姿态机动动作消耗能量；λ为姿态机动消耗能量系数；C_R为执行观测任务占用存储空间；β为存储图像占用存储空间系数。

通过以上判断，可以确定卫星能够参与竞标，同时能够计算得到卫星对任务的执行时间t_i^j及卫星收益V(M_i^j)。

分布式的任务规划流程如图 5所示。

3 仿真验证及结果分析

为了对本文采用的方法进行验证，进行3个算例的仿真。算例1对4颗卫星10个任务的分配进行规划；算例2对7颗卫星50个任务的分配进行规划；算例3对7颗卫星500个任务的分配进行规划。3个算例均选用敏捷卫星进行验证，即任务的执行窗口可以在可见窗内进行前后移动。

算例1的卫星轨道信息见表 1。

为了得到收益情况，选取10个任务，分别赋予它们不同的时间属性及优先级属性。时间属性以系统开始运行时间为0开始，单位为h。优先级分为1~5级，1级最高。任务发布时间有先有后，用于模拟实际任务需求产生过程的动态特征。

使用以上仿真参数，对买卖合同模式、买卖合同与交换合同结合模式以及本文提出的合同网任务规划模式分别仿真，得到算例1结果如图 6所示。

从结果可以看出，任务作为合同在星间被交互、买卖的次数越多，任务在星间被分配的“合理程度”会越来越高，表现为随着买卖次数的增加，任务分配结果总收益越来越高。相比于其他算法，本文提出算法具有显著的收益优势，表明在相同的合同买卖次数下，采用本文算法能够实现任务的更合理的分配。仿真结果证实了本文提出的基于合同网的分布式遥感卫星任务规划方案是有效的。

算例2采用7颗卫星，任务数量设定为50。轨道参数如表 2所示，观测任务位置如图 7所示。

算例2的规划结果如图 8所示。从图中可以看出，本文提出的算法能够将任务均匀地分配给7颗卫星，分配效果良好。

算例2在验证规划算法的同时，对算法的规划效率进行了验证，对不同场景下的规划时间进行了统计，结果如图 9所示。从图中可以看出，卫星数目和任务数目决定了任务分配过程耗时。

算例3在算例2的基础上，对500个任务进行分配，测试了本文算法针对大规模任务集合的分配情况，分配结果如图 10所示。

从图 10中可以看出，本文所设计的算法在解决大规模任务分配问题时，依然能够得到一个满足约束条件的可行解。说明所设计的算法是可行且有效的。

4 结论

1) 随着合同网络中合同拍卖次数的增加，本文算法和经典合同网算法的总收益指数均呈上升趋势。本文算法较经典合同网算法有5%~10%的收益增加，表现出了更优的分配性能。

2) 多星多任务仿真结果可以看出，在任务位置可见的情况下，各观测任务较均匀的分配到了卫星上，取得了较好的任务规划效果。

3) 任务分配算法运行时间随卫星数量和任务数量增加呈线性增长趋势，能够适应未来大规模星群任务分配需求。