0. Abstract
卫星网络任务调度时效性问题是实现空地一体化网络（STIN）的关键。传统方法将卫星任务调度问题解释为线性或非线性规划问题，忽略了任务之间的复杂关系。为了提高多卫星和多任务场景中任务调度的及时性，我们研究了解释任务相关性的网络图结构。然后，我们针对具有相似性和相关性特征的任务提出了多层网络图聚合模型。进一步，我们将任务调度问题转化为零一规划问题，设计任务调度算法来解决任务调度时效性问题。最后，我们模拟和模拟真实世界的数据作为实验数据集，用于与三种基线算法进行比较。实验结果表明本文方法具有明显的优势和进步。
1. Introduction
本文的Introduction部分首先介绍了卫星任务调度的背景和意义，指出卫星任务调度是卫星运行中最重要的环节之一，其质量直接影响到卫星系统的性能和效益。然后，介绍了传统方法在多卫星和多任务场景下存在的问题，包括复杂的任务关系、低效的任务调度及时性等。接着，本文提出了一种基于任务网络图聚合的新方法来改善任务调度及时性。该方法将不同卫星上的原子任务聚合成一个整体图，并通过优化算法实现对整体图进行调度。最后，Introduction简要介绍了本文研究内容和结构安排，包括模型构建、算法设计、仿真实验等方面。
我们的贡献可以简要总结如下：
- 我们建立了任务的网络图表示方法，解决了多卫星多任务关系复杂难表示的问题，实现了多任务复杂关系的统一表示。首先，我们根据任务的初始执行时间、资源需求、资源类型、任务操作等任务属性设计了任务的五元组。然后，我们将任务表示为边，任务属性表示为边属性，开始和结束执行事件表示为节点。根据任务执行时间的顺序，将任务之间的关系映射到边之间的关系，构建任务网络图。另外，我们根据资源类型、资源数量、可见时间窗的起止时间属性，设计了卫星的五元组。
- 我们构建了任务网络图的相似性聚合和相关性聚合模型，可以解决相似任务重复执行和相关任务独立分配带来的相互约束问题，实现多任务执行时间的最大压缩.首先，我们构建了多层任务网络图的聚合模型。根据任务之间的相似性和相关性，我们将所有任务网络图重构并聚合成一个大的任务网络图。然后，我们根据网络图和任务网络图中的关键路径计算出每个任务的最早开始执行时间和最晚结束执行时间，即完成所有任务的理论最短时间。
- 我们设计了多星多任务调度优化算法，保证大规模任务网络图能够在最短的理论时间内执行，实现多星多任务调度的高时效性。如果任务网络图中关键路径上的任务按时执行，任务网络图中的其他任务也会在资源充足时执行。因此，我们将多卫星和多任务调度问题解释为一个零一规划问题。然后，我们优先考虑关键路径上任务的资源分配策略，然后基于零一规划模型为剩余任务分配空闲卫星资源。
3. 问题描述&模型构建
3.1 问题描述
原子问题五元组：$\alpha = < t_{start}, r_t, r_n, oper, t_{end}>$,tstart表示原子任务的计划初始执行时间，rt表示原子任务的资源需求类型，rn表示原子任务的资源需求，oper表示原子任务在卫星上的运行，tend表示最新的计划的执行时间。
可用卫星问题五元组：$s = <st_{start}, sr_t,sr_n, s_{oper}, st_{end}>$,ststart表示卫星可见时间窗的开始时间，srt表示卫星当前提供的资源类型，srn表示卫星当前时刻可以提供的资源总量，soper表示卫星运行，stend表示可见时间窗的结束时间。
定义1 原子任务α由卫星直接执行，执行过程中不允许被打断。原子任务是从任务σ中分解出来的。
任务σ的原子任务α具有顺序执行关系，原子任务之间相互包容、相互制约。也就是说，有些原子任务只有在其他原子任务执行完之后才能执行。一般来说，原子任务有不同的资源类型、数量要求和初始执行时间，多个卫星可以满足同一个原子任务的资源需求。根据医院信息网络动态时变环境下原子任务的这些特点，计算多任务原子任务的执行顺序和执行时间，保证任务执行时间最短是关键问题。
3.2 最短时间内完成机载多任务执行顺序动态计算模型
主要解决最小化任务执行时间的问题，假设特定时间段的开始时间为 Tstart ，结束时间为 Tend 。然后，
如式(3)所示，pi表示一个离散的时间段。 C1 表示 Γ 中的任何离散周期时间未被覆盖或重叠。 C2 表示从离散时间 i 到 j 的时间段为 pς 。我们需要计算任务执行在离散时间段Γ内的最短耗时，建立优化模型如下：
如式(4)所示，表示任意时间段Γ内所有原子任务并行执行消耗的最小时间的计算方法。 p(i, j) ∈ Γ 表示在 Γ 中的一个小时间段，p(i, j) 不为零，即 i ≠ j。式(4)中，C1表示任意时间段p(i,j)的有效时间为p(θ,θ‘)。如图1所示，p(i,j)是随机考虑的某个时间段。该时间段包含的任务执行队列中最新任务的执行结束时间不一定严格等于j，即θ为p(i,j)中执行的第一个任务1的开始执行时间。同理，θ为最后一个任务8的执行结束时间。因此，我们取时间段p(i,j)内执行的第一个任务开始执行时间为θ，最后一个任务执行结束时间是θ’，p(θ, θ‘) ∈ τ 表示为 p(i, j) 中的多个任务全部执行完毕的最大起止时间。p(θ, θ’) 包含可以在 K(θ − θ’) 的时间段内完成的完整任务集。在离散时间段(θ,θ‘)中，我们取当前时间段内所有任务执行时间的最大值，max∀k∈K(t) Ct(k)表示所有任务的最大耗时值在时间 t 正在执行的任务。例如，式（4）中的C2表示单位时间的耗时约束。我们假设t是单位时间，那么任务Ct(k)的耗时为1。此时我们可以观察到在任务未执行时Ct(k)的值为0。另外，如果有正在执行的任务，则当前时刻消耗的时间记录为1，因此图1中所有任务消耗的最大时间为θ’-θ-(b-a)。
值得一提的是，式（4）中所有任务最早开始执行和最晚结束执行的时间和执行顺序并不准确，从而导致出现多种组合。不幸的是，当我们遍历所有可能的组合时，这对卫星的计算能力来说将是灾难性的。此外，它消耗了大量的计算时间，导致卫星网络执行任务的时效性差。那么，关键问题是如何快速计算出原子任务的执行顺序，并保证消耗的时间最少。
4. 问题转化和解决方式
将最小化执行时间的问题转化为两个子问题：计算原子任务开始和结束时间的问题以及聚合相似原子任务问题
计算原子任务开始和结束时间的问题：确定原子任务的最早开始和最晚结束执行时间，以减少原子任务执行时间内的组合数量，将多种组合方案减少为少数几种可组合方案。然后，我们计算原子任务的最晚开始执行时间和最早结束执行时间，并结合结果数据确定某些任务的开始和结束执行时间。这个时候，原子任务的执行顺序也已经确定了。
聚合相似原子任务问题：我们根据原子任务之间的相似特征和相关关系特征聚合相似的任务执行，节省重复执行原子任务所消耗的时间。
4.1 基于网络图表示的关键原子任务计算模型与算法
我们给定原子任务的统一表示元组。原子任务作为网络图的边，元组元素作为边的属性。节点表示原子任务开始或者结束执行的事件。原子任务之间复杂的关系由网络图结构进行表示。网络图的计算由两个元素组成：首先，每一个边的最早开始时间和最晚结束时间被用于计算原子任务的执行的时间范围。然后网络图的关键路径被计算，在关键路径上的任务为必要的原子任务。如果原子任务的优先计算得到了保障，那么我们可以得到所有原子任务的最小执行时间。
我们使用网络图数据结构去表示原子任务，然后重新定义了原子任务。原子任务由以下式子表示：
$\alpha’ = <t’_{start}, t_{start}, r_t, r_n, oper, t_{end}, t’_{end}>$
我们添加了原子任务的最早可能开始时间 t′ start 和允许完成执行的最晚时间 t′ end 。一个任务 σ 可以分解为多个原子任务 σ = {α′ 1, α′ 2, α′ 3, … , α′ n}。
4.1.1 任务网络图表示
根据原子任务集合中原子任务的优先级重新分配原子任务的执行顺序，并且获得新的原子任务队列。我们将网络中的边表示为网络图的原子任务。图中的节点表示为原子任务执行的事件。
示意图显示了原子任务之间的依赖关系。子图(a)表示边代表原子任务，子图(b)节点表示原子任务执行的事件。
在构建任务网络图之前，我们需要计算原子任务的计划完成时间。
$P(\alpha’i) = t{end, i} - t_{start, i}$
这个式子里的$P(\alpha’_i)$就是原子任务$\alpha’_i$的计划完成时间。
然后边的属性可以表示为$w_i = (t’{start}, A_i, t’{end})$,而且边的属性的集合为$W = {w_1, w_2, …, w_m}$
4.1.2 任务网络图计算模型
如图所示。$v_1$是任务执行开始的事件，$v_7$是任务执行结束时的事件。图G表示一个特定任务的所有原子任务的依赖关系。节点上的出度边所代表的原子任务可以在节点上的入度边所代表的原子任务完成后执行。边的属性信息W表示原子任务的执行时间、最早执行时间和最晚执行时间。
引理1. 关键路径的引理和证明 略
定理1. T 是关键路径上的关键任务集。除关键路径P的任务集外，其余任务集为Q。C(T) + C(Q) = min(C(G))，其中执行 T 的时间成本是 C(T)，执行 Q 的时间成本是 C(Q)， 时间成本的证明略
从引理 1 可以看出，我们关心的是任务的开始和结束事件最早和最晚发生的时间，网络中最后一个事件的完成时间就是整个图像完成的时间。然而，定理 1 关注的是网络图中所有边所代表的任务执行时间和成本的总和。同时，时间成本是网络图上边的权重。
为了保证提升任务执行效率并缩短任务的执行时间，我们需要计算完成任务所需的最短时间以及对任务执行时间有影响的关键任务。如果我们保证关键任务的正常执行，那么理论上我们可以获得网络图执行的最短时间。对于任务网络图G，是完成最后一个事件Vm和每个原子任务的关键性的最短时间。同时，我们可以参考AOE（Activity on edge network）网络的关键路径计算方法。
te(vj )表示任务事件最早发生的时间，P(ez)表示执行原子任务所需的时间。在约束条件C1中，T是所有以顶点vk结尾的边的头顶点集合，ez代表所有以顶点vk结尾的边。ez 表示所有以顶点 vk 结尾的边。以节点vj的所有原子任务中执行时间最长的原子任务为出度，事件vi最早发生时间之和就是事件vi最早发生时间。
从已完成的顶点vn开始，令l(vn) = e(vn)求拓扑序中剩余顶点的最晚允许出现时间。如式(8)所示，S是所有以vj为头的弧的尾顶点的集合。如约束条件 C2 所示，j 必须满足约束条件 1 ⩽ j ⩽ n − 1。
找出每个原子任务ei的最早开始时间e(i) = e(vj ), 1 ⩽ i ⩽ m，最晚开始时间**l(i) = l(vk) − P (vj , vk)。如果一个弧满足e(i) = l(i)**，那么它就是一个关键任务。
4.1.3 关键原子任务的计算算法
由上述的（8）和（7），我们设计了一个网络图计算算法，算法如下：
算法2的设计参考了AOE网络的关键路径求解方法。首先，算法1被用于创建一个任务网络图并且进行拓扑排序的操作，并且初始化所有时间的发生时间为0.算法 2 以网络图作为输入数据（第 1-3 行），然后根据拓扑排序顺序从前到后更新事件的最早执行时间。用每个顶点的每个相邻点更新e(v)，其值是连接到当前节点和相邻节点的所有边的最大值与当前最早时间之和（第4-9行）。同理，按照拓扑排序顺序，从后向前更新节点最晚出现时间l(v)（第10行），求出每个原子最早出现时间e(edge)和最晚出现时间l(edge)根据 e(v) 和 l(v) 的任务。根据e(edge)和l(edge)是否相等判断原子任务是否为关键原子任务。网络图中最后一个节点的最早出现时间是整个任务的最早完成时间（第 11-22 行）。
4.2 基于原子任务相似特征的多网络图聚合模型及算法
通过考虑原子任务的相似性和相关特征，我们将不同的网络图聚合成一整个图。拥有相似特征的原子任务可以被组合为一个简单的原子任务。同样的，有关联的多原子任务可以被聚合成一个可以在单个卫星完成的不可分解的任务集合。由于多层网络图在聚合过程有环路，会导致计算关键路径失败。因此，我们基于剪枝的思想设计了一种破环算法来实现多层网络图聚合的目的。
基于刚才提出的网络图表示方法，我们可以把多任务表示为多网络图。在网络图之间偶尔会有很多边会被合并从而形成一个大范围的网络图。定义3解释了任务聚合，也就根据特定的规则将多个网络图合并为一个网络图。任务聚合的规则有两方面：依赖聚合关系以及相似聚合关系。定义4解释了依赖聚合关系的定义，定义5解释了相似聚合关系的定义。
定义3 任务聚合是指分析多个任务的原子任务集φ并将满足特定约束的多个原子任务聚合到一颗卫星上执行，或者将多个具有相似特征的原子任务合并为一个原子任务。最终形成一组新的原子任务。聚类后的任务集仍然是原子任务集。
定义4 依赖聚合关系是指原子任务执行顺序之间的相互依赖关系。如果一个原子任务αi的执行结果是另一个或多个原子任务的执行前提，则这些原子任务满足依赖聚合关系。
依赖包括多对一的依赖以及一对一的依赖，如图所示.
定义5 相似聚合关系定义为原子任务之间存在相似的资源需求、任务需求或执行结果。如果同一卫星在同一周期内可以执行多个原子任务，则这些原子任务之间满足相似聚合关系。
如图6所示，子图(a)描述了分散在多颗卫星上的具有相似特征的多个原子任务，子图(b)描述了可以包含其他原子任务特征的原子任务，子图(c)描述了多颗卫星- 原子任务聚合成一个原子任务。
目标原子任务的执行结果数据包含所有源原子任务的执行结果数据。所以目标原子任务可以代替所有源原子任务的执行过程。
4.2.1 相似原子任务聚合模型
为了降低非必要任务执行的影响，我们研究了所有相似和相关任务聚合的方法。所有的原子任务都在集合X上执行，单颗卫星可以独立完成一个原子任务，不需要多颗卫星联合执行。集合Z={R,B,L}中所有具有依赖关系的原子任务记为R。具有相似关系的所有原子任务的集合为B={S,H}，S表示具有相似关系的所有目标原子任务的集合相似关系，H表示具有所有相似关系的原子源任务集合，所有不符合聚合关系的原子任务集合为L，则原子任务集合Z由卫星集合X执行完成所需的总消耗的时间如方程式所示。 (12),
我们将执行具有依赖关系的所有目标原子任务集合R的卫星集合记为A，将执行具有依赖关系的目标原子任务αr的卫星记为xr，则所有具有依赖关系的原子任务聚合后消耗的时间模型如下所示在 (13)
T(R)表示所有具有依赖关系的原子任务集合执行所消耗时间的总和。
把10和9式子放进13中，可得到式14:
我们将执行具有相似关系S的所有目标原子任务的卫星集合表示为B，将执行目标原子任务s的卫星表示为xs。则聚合后所有具有相似关系的原子任务消耗的时间模型如式(15)所示。
C(γ(s), xs)表示目标原子任务s在卫星xs上消耗的执行时间。C1是对目标原子任务集合的距离约束，表示卫星执行原子任务时天线角度或遥感设备角度等操作的转换时间。 C2是具有相似特征的源和目标原子任务之间的约束关系。
所有原子任务集合Z中除相似特征原子任务和原子依赖任务外其余任务的执行耗时可构造为式(16)，
D是执行原子任务集合L的卫星集合，C(γ(l),xl)是执行不可聚合的原子任务所消耗的时间，xl是执行原子任务l的卫星。
综上所述，我们构建了可聚合的原子任务执行时间消耗模型和其他原子任务执行时间消耗模型。 代入方程式。 （14），（15）和（16）进入等式。 (12) 产生执行和完成所有任务 N 所消耗的时间总和。 时间消耗如方程式 (17)所示。
其中C1-C2表示所有可聚合原子任务与其他原子任务的关系和范围，所有任务执行时间T都不为0。C3-C5说明具有可聚合关系的源原子任务和目标原子任务之间的关系和约束。 C6表示原子任务执行过程中卫星完成天线或载荷设备角度调整所消耗的时间，我们默认为一个固定值。
总之，我们对多颗卫星上多任务执行的时间消耗进行建模，如式（17）所示，并求解该式。 𝑇 预先假定需要确定哪些原子任务有资格进行聚合以及选择卫星来执行它们。 一旦确定了这些要求，就可以更新聚合原子任务的网络图表示，然后可以根据算法2求解多任务执行的最小时间消耗。
4.2.2 相似原子任务聚合算法
本节我们基于上述多层网络聚合模型设计相应的求解算法。在多图聚合的过程中，我们发现了多图聚合后产生循环的情况。我们设计了一种聚合后不产生循环的算法，并建立了一种消除任务网络图中循环的方法。
A. 层任务网络图的相似度聚合算法
在图7的a中有两个网络图的初始状态。我们基于原子任务的属性特征不同来计算任务之间的相似度。比如，如果多个观测任务的观测区域重叠，在观测任务的一些原子任务之间就有一个相似度。观察区域覆盖率较大的原子任务就是需要聚合的目标原子任务，我们称之为目标原子任务。观察目标区域较小的原子任务是等待聚合的原子源任务，我们称之为源原子任务。根据这些规则，我们确定要在多图中聚合的目标任务和源原子任务。
值得一提的是，目标原子任务可以有多个源原子任务与之对应，而源原子任务只有一个目标原子任务。如图b，蓝色的边表示目标原子任务，红边表示源原子任务。再决定目标和源原子任务后，我们需要跨越多个图并建立源原子任务和原子目标任务之间的关系。如图c所示，我们通过创建9->3和5->12虚拟边来聚合两个图。尽管多个图可以通过虚拟边聚合为一个图，额外的虚拟边以及属性值的设定影响着多图聚合的效果。因此，我们将虚拟边的属性值设置为0并且用最少的虚拟边将原子目标任务进行连接。子图 (c) 描绘了具有多个源节点 1,8 和多个汇点 7,14 的完整网络图。此时的网络图并没有计算使用算法2的所有任务的最小消耗时间和关键原子任务。因此我们需要把多源多沉没的网络图表示为单源单沉没的网络图。如图d所示，我们增加两个虚拟事件0，-1，虚拟事件0是网络图的源，虚拟事件1时网络图的下沉。同时，我们增加虚拟边0->1, 0->8, 7->-1, 14->-1到网络图中。此外，红色边被蓝色边合并，并且虚拟边被创建去消除原子源任务，消除了完成两个原子任务的需求以实现仅一个目标原子任务的目标。新的逻辑虚拟结点表示一个空的原子任务，它并未被执行。在消除原子源任务9->12后，与其关联的事件9,12也可消除。如图e所示，事件9和3被合并，事件12和5被合并，最终导致一个完整的网络图被聚合。
如图8所示，图a到f描述了拥有一个目标原子任务的多源原子任务的聚合过程。图a描述了两个任务的网络图的初始状态。图b表示聚合关系的计算结果，蓝色边表示原子目标任务，红色边表示要被合并的原子源任务。如图c所示，虚拟边9->3，5->12以及11->3,5->10被添加用目标原子任务去合并两个源原子任务。如图d所示，为了将多源，多下沉网络图转化为单源，单下沉网络图，我们增加两个虚拟事件0，-1，我们添加两个虚拟事件 0、-1，以及虚拟边 0 → 1、0 → 8 和 7 → −1、14 → −1。剔除源原子任务 9 → 12 和 11 → 10 后，事件 9、11、12、10 就没有有意义的存在了。因此，事件9，11需要与事件3合并。同样，事件12，10需要与事件5合并，合并结果如子图（e）所示。我们发现事件 8 和事件 3 之间有两条边，即要执行的两个原子任务。类似地，在事件 5 和事件 14 之间有两个原子任务要执行。如子图 (f) 所示，我们的任务网络图表示中不允许两个相邻事件之间存在两条或更多条边。因此，我们添加两个虚拟事件-2、-3和两个虚拟边缘8→-2和-3→14。目标原子任务的虚拟事件、虚拟边缘和事件3,5之间的关系为8→ −2 → 3 和 5 → −3 → 14 其中 8 → −2 → 3 上的原子任务是随机选择子图 (e) 中事件 5 和事件 14 之间的两个原子任务。同样，5 → -3 → 14 是在事件 5 和事件 14 之间的两个原子任务中的随机选择。最后，根据原子任务相似性，将两个网络图表示为一个完整的网络图。
如图9所示，它描述了具有数据依赖性的原子任务之间的聚合过程。子图 (a) 显示了两个图的初始状态。子图 (b) 描述了两个图中的目标和源原子任务，其中蓝色边表示原子目标任务，两条红色边表示原子源任务。原子任务 4 → 6 的执行需要原子任务 10 → 14 和 13 → 14 的执行。关联原子任务聚合不是消除原子任务，而是将具有关联的原子任务从分散状态转换为集中状态。那么我们需要尽可能将具有相关性的原子任务分配给一颗卫星执行，这样可以减少大量卫星协同处理数据所花费的时间。如图(c)所示，虚拟边14→4连接两个图，虚拟节点0和虚拟边0→1、0→8将图从多源节点转变为单源节点。子图（d）描绘了事件14,4的合并，其中原始事件10→14、13→14被转换为10→4、13→4。原子目标任务和原子源任务没有改变，但它们的关系被改变，使它们更紧凑。根据卫星资源状况，我们可以考虑将新的目标原子任务4→6和原子源任务10→4、13→4在同一颗卫星上执行，减少数据请求和数据传输的耗时。
定理 2. 给定一个单源单汇网络图 G。如果 G 中存在任务 ei，则其属性五元组为 α(ei) = ⟨tei start, rei t, rei n, operei, tei end⟩,以及任务执行时间范围 L(ei) = (tei start, tei end)。存在一个任务 ej，其属性为 α(ej) = ⟨tej start, rej t, rej n, operej , tej end⟩，任务执行时间范围为 L(ej ) = (tej start, tej end)。如果rei t = rej t, L(ei) ∩ L(ej ) ≠ ⊘，则存在一个任务ek 可以替代任务ei 和ej 并且任务ek 的耗时小于任务ei 和ej 的总和。
证明略
根据定理 2，我们构建任务 ek 来替换网络图 G 中的任务 ei 和 ej，并且任务 ek 被执行的时间成本小于任务 ei 和 ej 的总和。
算法3描述了原子任务相似性特征的多任务聚合过程。首先获取原子任务属性数据，然后计算不同原子任务的相似性特征（第 1-7 行）。基于每个原子任务的特征数据，采用K-均值聚类算法计算原子任务在多个网络图中的相似度，选择原子目标任务作为聚类算法的质心。与每个质心相邻的原子任务可视为原子源任务（第 9 行）。我们根据计算结果得到源和目标原子任务的启动和终止事件。然后我们构建一个虚拟链接，它建立在原子源任务的起始节点和目标原子任务的起始节点之间。目标原子任务的终止节点实际上链接到源原子任务的终止节点。最后，删除所有原子源任务（第 10-11 行）。如果两个事件之间存在两个或多个原子任务，则必须重建多个原子任务连接。我们通过构建虚拟节点和虚拟边（第 12-15 行）将额外的原子任务连接到新路径。最后，源原子任务的开始和结束节点与目标原子任务的开始和结束节点合并（第 16-17 行）。
B. 原子任务数据依赖的识别与聚合算法
定理3. 给定一个单源单汇网络图 G。如果 G 中存在任务 ei，则其属性五元组为 α(ei) = ⟨tei start, rei t, rei n, operei, tei end⟩,以及任务执行时间范围 L(ei) = (tei start, tei end)。存在一个任务 ej，其属性为 α(ej) = ⟨tej start, rej t, rej n, operej , tej end⟩，任务执行时间范围为 L(ej ) = (tej start, tej end)。将任务𝑒𝑖和𝑒𝑗的执行过程产生的成本表示为𝜇，当𝑒𝑖是任务𝑒𝑗的入口度边时，任务𝑒𝑖和𝑒𝑗的执行过程产生的成本表示为𝜈，则𝜇⩾𝜈。
证明略。
由定理3可知，将具有相关关系的任务聚合在一起执行所消耗的成本要小于聚合前所消耗的成本。因此，我们根据定理3设计了基于多任务依赖关系的聚合算法4。该算法描述了原子任务相关关系特征的识别和多任务聚合过程。首先，我们获取原子任务属性数据，然后计算不同原子任务的相似性特征（第 1-7 行）。然后，根据每个原子任务的特征数据，我们计算原子任务在多个网络图中的相关性，输入数据是其他原子任务的输出数据，可以将其视为目标原子任务。相反，其输出数据可用作其他原子任务的输入数据的原子任务可被视为源原子任务（第 9 行）。基于计算出的源任务的端点事件和目标任务的起点事件，我们在源任务的端点事件和目标任务的起点之间创建了一个虚拟链接。为了构建单源单汇网络图，创建虚拟节点和虚拟边并将其链接到网络图的多个源和汇，并删除与源原子任务关联的虚拟边，最后将端点源原子任务的起点与目标原子任务的起点合并（代码 10-12）。
C. 消除网络图中多环路的形成
A小节描述的多层网络图的聚合过程属于没有出现环路的情况。然而，现有空间信息网络中任务图的合并过程会产生多个循环。因此，本节C提出了一种消散多层网络图聚合过程中的环路形成的方法，并设计了打破四种环路的算法，以解决多层网络图聚合过程中的环路形成问题。
由待聚合边的源节点的入度边引起的环路解析过程描述如示意图10所示。
子图(a)为循环生成前的状态。边 (a, b) 是目标任务，边 (53, 54) 是要聚合的任务。事件50为已经合并的事件，边(51, 53)为节点53的入度边。子图(b)描述了任务(a, b)和(53, 54)完成合并后的状态已被合并。由于边 (53, 54) 被 (a, b) 替换，因此边 (51, 53) 被移除并添加了新边 (51, a)。同时，图中存在环路。事件50、51、a形成子图(c)所示的循环。如子图（d）所示，为了打破循环，我们添加了一个新的虚拟事件 0 和一条权重为 -w 的边 (0, 51)，从而在不丢失原始边上的权重 w 的情况下打破了原始循环（ 51，a）。此外，我们需要将图的起始节点’start’连接到新的虚拟事件0。类似地，图11描述了由边的源节点的入度边引起的环路解析过程是聚合。子图(a)和(b)描述了边(53, 54)聚合的过程，任务(53, 51)是源53的出度边。子图(c)是之后形成的循环聚合，子图（d）添加虚拟时间0，添加边0,51以打破循环，最后将网络源节点start连接到虚拟节点0。
如示意图12所示，描述了由待聚合边的汇聚节点的入度边引起的环路解析过程。子图(a)为环路生成前的状态，其中边(a, b)为目标任务，边(49, 50)为待聚合任务。子图(b)描述了任务(a, b)和(49, 50)合并后的状态，由于(49, 50)被(a, b)替换，该图形成了一个循环。事件b、52、51形成一个循环，如图(c)所示。如子图 (d) 所示，我们添加了一个新的虚拟事件 0 和一条权重为 -w 的边 (0, 51) 来打破循环，从而在不丢失边 (51, b) 上的权重 w 的情况下打破了原始循环。此外，我们需要将网络源节点“start”连接到添加的虚拟事件0。类似地，图13描绘了由要聚合的边缘的汇节点的出度边缘引起的环路解决过程。子图 (a) 和子图 (b) 描述了边 (49, 50) 聚合的过程。子图(c)表示聚合后形成的环路，子图(d)加入虚拟时间0，加入新的边(0, 51)打破环路，最后将网络源节点start连接到虚拟节点0。
定理 4. 给定一个没有循环的网络图 G 和 G’，要合并的边 e(a, b) ∈ G 和合并后的边 e(c, d) ∈ G’，其中 e( c, d) 是 I(c)，输出边的集合是 O(d)。加入一条新的边e(m, n)连接边e(a, b)和边e(c, d)，合并后的新边为e(a’, b’)。如果合并边e(a, b)和e(c, d)，则得到一个新的网络图G’’，其中生成了环路P。添加事件 v 最早发生时间 ve(v) = ve(m) 和最晚发生时间 vl(v) = vl(m) 的新虚拟节点 v。权重为 w 的虚拟边 ev 和反向虚拟边创建具有权重 −w 的边 e′ v 并用于打破循环。同时，得到无环合并网络图G*。如果在不考虑虚拟边权重的情况下计算网络图的总时间成本，则 **min(C(G∗)) = min(C(G) + C(G′))**。
证明略。
由定理4可知，聚合后多网络图的时间成本消耗小于聚合前原始网络图的时间消耗。然而，聚合网络图不允许环路的存在。为了解决这个问题，我们设计了算法 5 来打破聚合网络图中的循环。该算法描述了消除网络图中循环歧义的过程。首先，我们获得所有聚合边的入度和出度边（第 2-3 行）。如果网络图中存在环路，则判断合并边(source, sink)的源节点source的入边suInEg或出边suOutEg是否在环路路径中。如果它在循环中，它会删除任一条边，中断循环，并添加具有权重的新边，从而保持网络权重不变（第 714 行）。类似地，伪代码（第 16-22 行）中显示了合并边的源节点源（源、汇）的循环中断。
4.3 基于聚合网络图的多星资源分配方法
基于聚合后的网络图，我们需要将网络图上的任务分配给场景中的所有有效卫星。我们将任务调度问题转化为 0-1 规划问题。然后开发了基于聚合网络图的任务调度模型，并设计了求解算法以实现高时间效率的任务调度。
本节基于聚合网络图解决多星资源分配问题，实现多星多任务的高时效调度。为了更方便地描述我们的多卫星和多任务调度模型，我们根据 3.1 节中描述的原子任务和卫星元组表示简化任务集为 σ = σ1, σ2, … , σm，其中 m 是任务。任务的属性集表示为 σi = ai, bi, ci, di, 0 ⩽ i < m，其中 A 表示卫星接触窗口的开始时间，B 表示任务资源需求数，C表示卫星接触窗口的结束时间，D表示卫星资源类型。卫星集合简化为 S = s1, s2, … , sn，其中 n 是卫星的数量。每个卫星属性表示为 sj = ej , fj , gj , hj , 0 ⩽ j < n，其中 E 表示任务开始执行的时间，F 表示任务需要的资源数量，G 表示时间任务完成的时间点，H 表示任务要求的资源类型。
根据上述定义，我们将多星-原子任务的任务执行最小时间记为T=min f(X)，T为任务等待执行时间与任务执行时间之和。我们可以转化多卫星多任务调度问题为 0–1 规划问题。该模型的构造如下：
如方程式 (18)所示。C1为待解矩阵X的描述。 X 是由要求解的值形成的矩阵。矩阵中的元素标识卫星是否被允许参与执行某项任务。 xi,j在矩阵X中的第j列表示任务σj在卫星si上的执行状态。如果 xi,j = 0，则意味着卫星 si 没有资源分配给任务 σj 。
反之，则意味着卫星需要为指定的任务分配资源。 C2是根据任务数量和卫星数量生成的所有已知元素为1的矩阵。 C3表示f(X)的解需要满足任务开始执行时间大于卫星可见时间窗开始时间。 C4表示卫星可见时间窗的结束时间需要大于任务执行的结束时间。 C5是指卫星拥有的资源类型应与任务所需的资源类型相同。 C6表示卫星拥有的资源数量需要大于任务所需的资源数量。
算法6描述了多星多任务的调度过程，我们重点计算任务本身的执行顺序和执行时间的优化。首先，我们根据任务网络图表示算法 1（第 3 行）构建具有多个任务的多个网络图。然后使用算法 3 聚合多图中具有相似特征的原子任务。通过使用算法 4 聚合多图中具有数据依赖性的原子任务，获得由多个任务组成的单源单汇网络图（第 5-6 行） .根据算法 5 消除网络图中的循环。根据算法 2（第 7-8 行）计算无循环网络图中的关键原子任务和整个图要消耗的最短时间。我们使用第三方计算库P uLP 2 根据每个原子任务的最早和最晚执行时间、关键原子任务、聚合的原子任务来计算原子任务。根据每个原子任务的最早和最晚执行时间、关键原子任务、被聚合的原子任务等，为原子任务分配卫星资源。分配卫星资源，使其不超过原子任务的最早或最晚执行时间，并且通常执行关键原子任务（第 9-15 行）。 至此，多任务将在最短时间内完成，无需考虑复杂的资源约束和优化策略，即可计算出多星多任务耗时最短的调度方案。
5. 实验
5.1 算法复杂度分析
我们着重研究了任务执行顺序和执行时间的计算，以克服多个任务混合执行耗时控制的困难，保证任务执行耗时最少。我们研究了原子任务聚合算法，可以节省不必要的原子任务执行时间消耗，进一步提高多任务执行效率。基于多任务网络图聚合的调度方法主要包括五种算法：网络图构造算法、相似原子任务聚合算法、相关关系原子任务聚合算法、网络图关键路径和最小耗时计算算法、多星多-任务调度算法。
算法1将所有原子任务视为网络图的边，将原子任务的开始执行事件和结束执行事件分别视为边的节点。算法输入是一个任务，所以算法的时间复杂度主要体现在该任务的所有原子任务的遍历过程中。如果原子任务的个数是E，那么它的时间复杂度就是O(E)。算法2主要计算特定网络图上的关键任务路径和整个网络图完成执行所需的最短时间。其计算时间消耗主要体现在网络图节点和边的遍历上，时间复杂度为O(E+V)。算法3主要计算多个网络图之间具有相似关系的原子任务的聚合。计算中使用经典的k-均值算法。
对于简单情况，𝑘 − 𝑚𝑒𝑎𝑛𝑠 算法的运行时间界限是 𝑂(𝑑𝐸4𝑀2)。 算法3的时间复杂度主要体现在多个网络图和网络图上边的遍历操作上。 若两个事件的冗余边数为𝑟，网络图数记为𝐺，则算法3的时间复杂度可表示为𝑂(𝐺𝑑𝐸4𝑀2𝑟)。 算法4主要计算多个网络图上具有相关关系的原子任务之间的聚合操作，其时间复杂度主要体现在网络图和边的遍历上。 因此，它的时间复杂度是𝑂(𝐺𝐸)。 算法6主要是在上述算法的基础上完成多图的最小时间和卫星资源分配计算，其时间复杂度为𝑂(𝐺𝐸+𝐸+𝑉+𝐺𝑑𝐸4𝑀2𝑟+𝐺𝐸)。 我们将本文提出的基于网络图聚合的多卫星多任务调度算法的时间复杂度简化为𝑂(𝐺(𝑑𝐸{4}𝑀{2}𝑟 + 𝑉 + 𝐸))。
5.2 实验数据
为研究天基信息网络的任务调度、链路优化、协同计算、网络拓扑发现等关键问题，自主研发了基于天然卫星的空间信息网络通用计算环境仿真工具包（CSTK）3和天基信息网络的共同任务数据。在本系统中，我们模拟了大量的卫星数据，包括卫星载荷数据、卫星轨道数据、星间可见时间窗、星间可见时间窗数据、卫星资源容量、卫星资源数量等。我们模拟了对地观测常见应用场景数据，包括对地观测区域数据、任务执行时间需求、任务资源类型、任务资源需求等。此外，我们开发了CSTK系统所需的多种计算库。在本文中，我们获得了基于CSTK系统的实验数据，并在该系统上实现了本文提出的模型和算法进行计算。本文提出的算法MSRA-TAG的实验数据描述如下，
如表1所示，本文共有六组实验数据。标题“Datasets”表示数据集的名称，标题“Atomic tasks”表示数据集中原子任务的数量，标题“Satellites”表示数据集中卫星的数量。
如表 2 所示，我们总共使用了四个数据集。每个数据集中包含的卫星和任务数量呈梯度增长，其中Scale表示每个数据集中的任务和卫星数量，’Minimum Strat Time’是所有任务的最短开始时间和所有卫星的最短开始时间在可见时间窗内。同样，“最大战略时间”表示所有任务或卫星的可见时间窗口的最大开始时间。 “最短结束时间”表示所有任务和卫星可见时间窗口的最短结束时间。 “最大结束时间”表示所有任务和卫星的可见时间窗口的最大结束时间。 ‘Minimum Resources Num’表示所有任务所需的最少资源数和所有卫星可用的最少资源数。‘Maximum Resources Num’表示所有任务中需要最多资源的任务和所有卫星中能提供最多资源的卫星请求的资源数量。 “资源类型”表示任务所需资源类型和卫星有效载荷的资源类型。 1表示观测资源，2表示存储资源，3表示传输资源。
为了验证 MSRA-TAG 在真实卫星观测场景中的有效性，我们添加了对真实世界数据的模拟，其中包含较少的合成数据。在真实的地球观测场景中，我们研究了两个用于观测地球区域目标的用户任务。用户任务是对用户需求的描述，是粗粒度的任务。观测场景包含两个观测需求，八颗观测卫星和两个用于发送任务指令的地面站。场景时间范围从“2022 年 3 月 5 日 04:00:00.000 UTCG”到“2022 年 3 月 6 日 04:00:00.000 UTCG”，步长为 10 秒。模拟场景如图 14 所示，子图 (a) 和 (b) 显示了两个观测任务的地球观测区域的 3D 和 2D 视图。我们可以观察到两个观测任务的目标观测区域重叠。这意味着两个用户任务被分解为原子任务后，还存在一部分相似或相关的原子任务。子图(c)和(d)显示了卫星轨道、地面站和观测区域的完整场景视图。我们可以从 3D 或 2D 场景观察卫星凌日的时间。
真实观测场景的任务数据详情如表3所示。我们可以观察到’’Real World Dataset’’表示真实世界数据集名称，’’TaskID’’指定用户任务ID，’’Areas’’表示观察区域的经纬度坐标和“离散时间范围”表示观察场景周期离散化的持续时间，以秒为单位。 “Resources Type”字段表示用户任务所需的卫星资源类型，与表1中的类型相同。
观测场景中的卫星详情如表4所示，表中卫星涉及整个观测任务，’’Common Name’’表示卫星名称，’’Launch Date’’表示发射日期卫星的“周期”表示卫星的运行周期（以分钟为单位）。 “倾角”表示卫星相对于地球的倾角，“原子序数”表示卫星上安装的天线数，双线元全称“TLE”表示卫星轨道范围。
5.3 Experimental parameter
本文使用python第三方库sklearn中的Spectral Clustering(Huang et al., 2020)方法完成相似边的查找。在完成多任务聚类后，我们使用线性求解器 P uLP 4 来实现多任务资源分配的解决方案。我们在 P uLP 求解器中使用默认参数设置。 Spectral Clustering方法中的参数设置如下表5所示。
如表5所示，其中参数gamma值在0.01、0.1、1、10范围内选取，参数n_clusters在2、3、4、5、6范围内选取。我们选取最优的聚合结果从上面训练出来的集合，以及聚类完成后默认选择的三个类别的集合。所有任务的默认最短开始时间应大于 0。
我们将本文方法与用于天基信息网络电路任务调度的基线算法进行比较，5 这些算法包括粒子群优化 (PSO)（Chen 等人，2012 年；Kennedy 和 Eberhart，1995 年；Luo 等人，2020 年） ; Xia et al., 2009), Genetic Algorithm (GA) (Gerges et al., 2018; Sun et al., 2010; Xhafa et al., 2012), and Differential Evolution (DE) (Li & Li, 2019; Storn & Price，1997 年；Wu、Wang 等人，2015 年）算法。 在空间信息网络任务调度场景下，这些算法的参数设置如表6所示，其中参数𝑙𝑏表示各自变量的最小值，𝑢𝑏表示各自变量的最大值，参数𝑙𝑏表示各自变量的最大值， 每个变量作为卫星当前拥有的资源数量上线。 𝑝𝑟𝑜𝑏_𝑚𝑢𝑡表示方差概率，𝑝𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛表示算法𝐺𝐴的精度，𝑤表示算法𝑃的惯性权重𝑆𝑂， 𝑐1表示算法𝑃𝑆𝑂的个体记忆，𝑐2表示算法𝑃𝑆𝑂的集体记忆，𝐹表示方差系数 算法𝐷𝐸。
5.4 Experimental results
本节分为三个主要部分来分析和验证我们提出的方法的性能。首先，我们比较和分析了我们的聚合方法的性能。然后对多卫星多任务资源分配性能进行了精确分析。最后，将本文提出的方法 MSRA-TAG 与三个基线模型进行比较，以彻底验证方法 MSRA-TAG 的有效性和优越性。
A. 多任务聚合前后任务执行时间对比
一个任务在整个调度过程中的时间成本消耗包括两个主要部分：任务执行消耗的时间和分配卫星资源时等待执行的时间。在本文中，我们提出的聚合过程发生在卫星资源分配过程之前。因此，我们比较了聚合前后计划执行任务所需的时间，以验证我们提出的相似性聚合和相关性聚合方法的有效性。
如表7所示，我们分别计算了聚合前原始任务和聚合后任务在六个数据集上的计划执行消耗时间。 我们可以观察到原始任务和聚合任务的计划耗时在数据集𝐷1 上是相同的，这表明没有执行聚合过程。 造成这种情况的原因是数据集中的任务数量太少，导致不存在相似的任务或有相关关系的任务。 因此任务无法聚合，导致聚合前后任务计划执行的成本消耗相同。 在数据集𝐷2、𝐷3、𝐷4、𝐷5、𝐷6和𝐷𝑟𝑒𝑎𝑙上，我们可以观察到聚合后任务的耗时小于原始任务的耗时，说明任务集中的某些任务具有相似或相关关系 ，它们聚合在一起并减少了任务大小。
经过上面的分析，我们可以注意到，任务的聚合操作可以减少任务执行时间的消耗，减少任务的数量。此外，如图15所示，聚合后任务总成本的降低率随着数据量的增长而增长。此外，我们可以意识到，当任务数量增加时，具有相似性和相关性的任务数量也会增加，聚合后任务执行时间消耗也会减少。因此，当空间信息网络满足许多任务请求时，我们提出的聚合方法降低的任务执行消耗成本随着任务数量的增加而增加。在真实世界数据的模拟结果中，我们可以观察到任务聚合后任务消耗的估计时间成本减少了 861。聚合后减少的时间消耗比大批量任务场景要小，因为真实数据集中只有两个用户观察任务。因此，更少的任务满足聚合条件。本文提出的任务聚合方法对真实世界数据有效。总之，我们提出的聚合方法可以适应大容量任务请求场景。
B. 关键路径任务优先资源分配与全图分配结果对比
任务聚合后，需要将当前时刻活跃卫星拥有的空闲资源分配给任务。本节给出了本文提出的关键路径任务优先级分配资源方法与全图分配资源结果的对比分析。如4.3节所述，关键路径任务优先分配资源法是指先将资源分配给网络图中关键路径上的原子任务，再分配给关键路径以外的剩余任务，即保证整个网络图可以在理想的时间内执行和完成。全图资源分配是指根据实际卫星资源的数量一次性为网络图中的所有任务分配资源。之后，我们分析了这两种方法的实验结果数据。
如表8所示，关键路径优先分配和整个网络图的一次性分配的成本消耗在D1数据集上是一致的。这表明卫星资源的数量足以执行网络上的所有任务，不存在资源竞争。因此，这两种方法都不会延长关键路径上任务的执行时间。然而，随着D2-Dreal数据集上的任务数量逐渐增加，卫星资源不足导致资源争用。它导致网络地图上关键原子任务的执行按时完成。结果，“一次性分配”方法导致整个网络的时间成本消耗增加。
如图16所示，随着任务的增加，对资源的竞争也越来越激烈。子图描述了与一次性分配方法一致的优先关键路径方法对数据集 D1 的成本消耗。这是因为任务数量少，不会造成资源争用。此外，网络图中关键任务的执行越来越延迟，导致整个网络图中的任务执行成本增加。在真实数据集 Dreal 上，我们可以观察到整图一次性分配方法的成本消耗大于关键路径优先方法的成本消耗。因此，关键路径任务优先执行法实现了显着的成本节约和更理想的结果。随着任务数量的增加，成本节约消耗更加出色。
C. MSRA-TAG 与基线方法的调度结果对比
本节将本文的方法 MSRA-TAG 与基线算法 PSO、GA 和 DE 进行比较。 算法计算成本消耗越小，意味着算法对动态变化的空间信息网络的适应性越强，算法的性能就会提高。如表9所示，PSO、GA、DE算法的成本消耗在数据集D1上是一样的，都是7797。MSRA-TAG相比baseline方法是3657，消耗的时间不到所消耗时间的一半通过基线模型，显着降低了任务执行的成本消耗。但是，我们发现MSRA-TAG大于原任务的计划成本消耗时间2761，这是由于卫星可见窗口、资源数量或分配时卫星功率等任务约束的等待时间造成的任务的卫星资源。此外，我们提出的方法 MSRA-TAG 在数据集 D1 上产生的任务等待时间延迟仅为 896。基线方法GA和DE在数据集D2上的结果相同，PSO算法的结果略高于GA和DE。我们提出的方法 MSRA-TAG 计算所有方法中的次要成本消耗。
在数据集 D3 上，我们提出的方法 MSRA-TAG 计算结果为 51 604.99，远小于原始任务的计划成本消耗 62,665.09，这是由任务集中许多相似任务和具有相关性的任务引起的数据集的数量增加。因此，众多任务的聚合极大地减少了时间成本消耗。在数据集 D3 上，随着数据集数量的增加，任务集中存在许多相似的任务和具有相关性的任务。然而，尽管如此，任务的等待时间仍然存在。在数据集 D5 上，MSRA-TAG 的时间成本为 179,240.64，原始任务的时间成本为 251,749.25，其他基线方法的时间成本分别为 623,999、623 760 和 623 760。原始任务的时间成本为 72,508.61，MSRATAG 节省的其他算法的时间成本为 444,548.61。 MSRA-TAG 相对于其他算法节省了 444,758.36、444,519.36 和 444,519.36。所有数据集上的卫星资源分配过程都存在任务等待时间消耗。 baseline算法的结果大致相同，但都远大于MSRA-TAG方案消耗的时间成本。类似地，数据集 D4、D5 和 D6 上的 MSRA-TAG 显示出随着任务数量的增加任务执行时间消耗减少的增加趋势。总之，我们的方法比基线方法具有绝对优势。
在真实数据集 Dreal 上，我们可以观察到 MSRA-TAG 的成本为 370 064，大约是源任务耗时的 23 倍。种群智能算法 PSO、GA 和 DE 消耗相同的成本 518 400，大约是源任务消耗时间的 33 倍。因此，与所有基线方法相比，MSRA-TAG 的成本消耗较小，可以提高任务调度的时效性。总之，我们的方法 MSRA-TAG 与基线方法相比具有绝对优势。
如图 17 所示，“原始任务成本”表示原始任务的时间消耗。随着任务数量的增加，所提出的方法 MSRA-TAG 的上升幅度远小于基线方法，并且其时间成本在数据集 D3、D4、D5、D6 和 Dreal 上低于原始任务。
为了更清楚地比较多种方法的时间消耗趋势，我们计算了每个算法在不同数据集上固定基数的增长率，计算如下，
如方程式所示。 (19)，我们将算法集 A = {Original Tasks Cost, MSRA-TAG, PSO, GA, DE} 定义为 y = {a1, a2, a3, a4, a5}。定义数据集 D = {D1, D2, D3, D4, D5, D6, Dreal} 为 x = {d1, d2, d3, d4, d5, d6, d7}。 φx(y)表示方法ai计算的任务执行耗时，1≤i≤5在数据集dj上，1≤j≤5。γ(x)表示原始任务在数据集x中的耗时。 f (x, y) 表示算法 x 在数据集 y 上的固定基数的增长率。
如表 10 所示，我们分别使用表 9 中“原始任务成本”列的值作为数据集 D1 −Dreal 的基线。其中，MSRA-TAG方法在数据集D1和D2上的增长率为正，小于baseline方法。这意味着 MSRA-TAG 方法的计算结果对于原始任务的成本消耗具有最低的增长率，即我们提出的任务调度方法需要最少的时间成本消耗。 MSRA-TAG 在数据集 D3、D4、D5 和 D6 上的增长率均为负值，其绝对值小于其他基线算法。这意味着该方法消耗的时间成本低于原任务的计划成本，增长率均低于其他算法。在真实数据集Dreal上，随着任务和卫星数量的增加，MSRATAG成本消耗以2298.65%的速度增长，而基线模型PSO、GA和DE的成本消耗增长率为3260.12%。
通过比较，我们可以观察到 MSRA-TAG 方法具有最慢的成本增长率和较高的任务执行时间。 虽然在真实数据集中只考虑了八颗卫星，但两个用户任务分解后产生的原子任务比数据集𝐷1中包含的原子任务数量要多。 原子任务的数量越多，可聚合的任务就越多，耗时也就越少。 因此，方法 MSRA-TAG 在𝐷𝑟𝑒𝑎𝑙 上的成本增长率小于 D1。
我们提出的方法 MSRA-TAG 随着任务数量的增加使更多的任务聚合在一起执行，从而减少重复执行的大量时间成本。如图 18 所示，算法 PSO、GA 和 DE 的增长率具有相同的值，导致三种算法的增长率倍数重叠。 MSRA-TAG、PSO、GA 和 DE 的增长率在数据集 D1 和 D2 上是有利的。然而，随着任务数量的增加，MSRA-TAG 在数据集 D3、D4、D5 和 D6 上出现了负增长，增长率曲线停滞在-30.37%。 PSO、GA 和 DE 的增长率仍然为正，增长率稳定在 147.87%。 PSO、GA 和 DE 的增长率保持正增长并稳定在 147.87%。我们的方法 MSRA-TAG 显示出正增长率，低于数据集 Dreal 上 PSO、GA 和 DE 的增长率。我们可以观察到MSRA-TAG在所有数据集上相比基线算法的时间成本消耗最少，并且随着数据量的增长增长率逐渐降低，具有优异的性能。
为了验证所有算法在任务数量变化时的性能，我们根据所有算法在数据集 D1 上的基准测试结果，计算了每个算法在数据集 D2、D3、D4、D5、D6 和 Dreal 上的增长率。随着任务和卫星数量的增加，时间成本的增加是不可避免的。因此，我们提出的方法 MSRA-TAG 旨在尽我们所能减少任务的时间成本消耗。如表11所示，原任务的时间成本增长率为1102%。本文提出的算法MSRA-TAG虽然在数据集𝐷2上997%的增长率比基准算法高出900%，但并没有显着差异。 这种情况是因为数据集𝐷2中的任务和卫星数虽然相对于数据集𝐷1增长了1102%，但具有相似关系或相关关系的任务并不多，聚合效果不明显。 但随着数据量的增长，MSRA-TAG的增长率明显低于其他基准算法，这是由于任务和卫星数量的增长，出现了更多具有相似和相关关系的任务，使得MSRA- TAG充分发挥其性能。 如图19所示，随着数据量的增长，MSRA-TAG的增长率明显低于其他基线方法，其增长率曲线的斜率也远小于 其他基线算法。 然而，与其他方法相比，MSRA-TAG 在真实数据集 Dreal 上相对于 𝐷1 的增长率最高。 这是因为𝐷1数据集中的卫星比数据𝐷𝑟𝑒𝑎𝑙中的卫星多。 然而，𝐷1 中的原子任务数量少于𝐷𝑟𝑒𝑎𝑙。 因此，与 𝐷𝑟𝑒𝑎𝑙 相比，它导致 𝐷1 的成本最低，后者更广泛并导致更显着的增长率。
综上所述，我们的方法在处理大批量任务请求时具有出色的性能，并且与其他方法相比，任务越多，我们的时间消耗就会少得多。然而，对于任务数量较少的场景，我们的方法的优异性能并不能得到充分体现。
6. Conclusion
针对空间信息网络中多卫星多任务场景下任务关系复杂、任务调度时效性差的问题，研究多任务聚合方法和多卫星资源分配方法，提出了一种独创的复杂多任务聚合方法，基于合成数据集和真实世界数据，仿真验证了该方法在多卫星、多任务调度场景下的有效性和优越性。我们提出了多任务的网络图表示，建立了相似性和相关关系任务聚合模型，设计了解决多层任务网络图聚合的算法，解决了重复执行多个任务需要大量时间的问题.为了解决多卫星资源分配问题，我们提出了一种基于聚合任务网络图来优先分配关键任务资源请求的方法。我们还建立了多卫星多任务资源分配模型，并设计了算法对关键任务进行优先分配，解决了空间信息网络资源大量被占用和资源利用率低的问题。资源配置不合理。该论文突破了多任务聚合的关键技术难题，实现了空间信息网络中多卫星、多任务的高时效调度。本文通过从多个角度验证本文提出的MSRA-TAG方法的有效性，并将实验的性能与各种基线算法进行比较，验证了我们的想法的有效性和效率。 MSRA-TAG 在最大数据集 D6 上将 95 745.82 个亲属保存到原始任务中。此外，MSRA-TAG相对于其他算法分别节省了560 436.08、560 137.08和560 137.08。 MSRA-TAG方法在所有数据集上其任务和卫星数量较多的时间成本消耗负增长率最高为-30.37%，其他基线算法时间成本消耗数量增长率最高为147.38% . MSRA-TAG 对数据集 D1 的最高增长率为 10 019%，其他基线模型对 D1 的最高增长率为 9904%。因此，本文提出的方法MSRA-TAG具有更强的适应性，在空间信息网络中的多星、多任务场景下具有优异的性能。
未来，卫星信息网络必然向天地一体化网络发展。脱离地基基站的卫星自主任务规划或聚类方法研究必将成为普遍的研究趋势。纵观相关文献，目前的任务规划或聚类方法大多基于图论、强化学习或种群智能方法。然而，在未来几十年，任务规划方法将倾向于基于卫星之间自主协商的星上自主在线规划。因此，下一步将研究卫星间自主协作机制和星上任务在线规划策略，以实现卫星信息网络的智能化和自主化。同时，我们将更倾向于根据卫星网络的时变特性，研究具有高时间效率的多任务在线聚类方法。
论文关键：拥有相似属性的任务可以进行聚合，拥有数据依赖的任务可以进行聚合，原子任务来自于大任务的分解