多波束中继卫星任务调度模型的构建方法及装置

摘要

本发明提供一种多波束中继卫星任务调度模型的构建方法及装置，涉及任务调度技术领域。本发明在构建模型时，针对天基骨干网中继卫星系统的多个波束以及多种方向的任务，在存在多个波束的场景下，综合考虑了可见时间窗口、任务属性、资源有限等约束条件，从而使得基于该模型得到的任务调度方案能够在满足上述约束条件的情况下完成中继卫星任务的规划，尽可能地保证优先级更高的任务能够被成功调度，进而提高了任务调度的效率。

说明书

技术领域

本发明涉及任务调度技术领域，具体涉及一种多波束中继卫星任务调度模型的构建方法及装置。

背景技术

随着天基骨干网的不断建设，需要中继卫星服务的用户航天器不断增加，由于中继卫星数量有限，数据服务能力有限，并且与需要中继卫星服务的用户航天器之间存在可见时间窗的约束，因此需要合理的编排调度中继卫星的任务规划来提高中继卫星利用率，进而提高整个空间信息网络的效率。

现有中继卫星系统任务调度研究的主要对象是预约式任务，由于中继卫星任务调度问题的复杂性，现有的中继卫星任务调度的数学模型大多数为NP-hard问题，因此现有的解决方法多为启发式算法。在使用算法进行求解前需要对中继卫星调度系统进行建模。现有的方法主要是：在存在多颗中继卫星且中继卫星之间存在通信链路的情况下，综合考虑了可见时间窗口、任务属性、资源有限用户任务调度的传播时延受限以及通信延迟受限等约束条件，从而使得基于该模型得到的任务调度方案能够在满足上述约束条件的情况下完成中继卫星任务的规划。

然而，现有的中继卫星调度算法在建模中大多只考虑存在单一波束时的场景，无法满足多个波束的任务调度。

发明内容

(一)解决的技术问题

针对现有技术的不足，本发明提供了一种多波束中继卫星任务调度模型的构建方法及装置，解决了现有的模型无法满足多个波束任务调度的技术问题。

(二)技术方案

为实现以上目的，本发明通过以下技术方案予以实现：

第一方面，本发明提供一种多波束中继卫星任务调度模型的构建方法，所述方法包括：

S1、获取预设的各调度任务的方向、任务的优先级、任务所属的航天器、任务被成功执行的最早开始时间以及各中继卫星上为各任务服务的可用时间窗；

S2、根据所述各调度任务的方向、任务的优先级、任务所属的航天器、任务被成功执行的最早开始时间以及各任务可用时间窗，以最大化优先级更高的任务能够被成功调度为目标构建多波束中继卫星任务调度模型；

其中，所述的各调度任务的方向包括前向任务、返向任务以及双向任务。

优选的，所述多波束中继卫星任务调度模型包括适应度函数和约束条件；

所述适应度函数为用于在指定的所述优先级、所述最早开始时间以及在所述约束条件的约束下获得最优任务调度方案的目标函数；所述最优任务调度方案为使得更多高优先级、任务开始时间早的任务能够被成功执行的方案。

优选的，所述适应度函数表达式如公式(1)所示：

其中：J为待执行任务的集合；

优选的，所述约束条件包括：

(1)同一用户航天器同一时刻可执行多个任务，在资源规划时，每个任务分别考虑；

(2)任务需要安排在可用时间窗内，包括：

A)中继卫星与用户航天器之间具有可见时间窗约束；

B)任务指定了允许执行的时间段，允许执行的时间段与可见时间窗的交集为任务的可用时间窗，任务需要安排在可用时间窗内；

C)任务执行时间不允许拆分成多个子时间段；

(3)双向任务需要同时安排发射波束和接收波束，具有强依赖性，需要安排在完全相同的时间段内执行，其数学表达式如公式(2)所示：

t

(4)一个任务只能在一个波束上执行，其数学表达式如公式(3)所示：

(5)同一波束同一时间在特定条件下可执行多个任务，包括：

A)波束同时服务多个任务的前提为：这些任务属于同一用户或轨道相同的同一用户组；

B)不满足同时服务多个任务的情况下，同一波束同一时间只执行一个任务，其数学表达式如公式(4)所示：

其中：J为待执行任务的集合；U

优选的，所述最优任务调度方案的求解方法包括：

通过人工蜂群算法改变任务的顺序计算适应度值，求解所述中继卫星预约任务调度约束规划模型的最优解，得到最优任务调度方案。

优选的，所述通过人工蜂群算法改变任务的顺序计算适应度值，求解所述中继卫星预约任务调度约束规划模型的最优解，得到最优任务调度方案，包括：

S201、设定算法参数和初始化种群，其中，算法的参数包括：任务数N，种群的规模m，阈值Lf，二次邻域搜索循环次数U，迭代次数L；初始化种群包括：随机生成m个初始解x

S202、从当前解中抽取一个任务，然后随机插入一个位置，为种群中每个解生成一个邻域解

S203、根据解的二次邻域搜索循环次数U，进行U次二次邻域搜索操作；

S204、根据S203得到的解邻域集合，对每个解的邻域集合进行判断；若某个解的邻域集合是非空的，即

S205、记录本次迭代中出现的最优解x

S206、判断每个解连续无更新邻域搜索次数是否超过阈值Lf；如果l

S207、输出mf，mf即为预约任务最优解，根据最优解得到最优任务调度方案。

优选的，所述适应度值的计算过程如下：

a、获取任务i的任务方向，判断任务由那种波束服务；

b、获取任务i在波束k所属卫星上的可用时间、波束k被占用的时间段；依次处理这个任务在波束k上的每个可用时间以及被占用的时间段，找到可用的最早的时间窗，若有，则标记任务i可调度并记录该时间段以及所属波束，转至步骤e，否则，转至步骤c；

c、判断是否还有未处理的波束，若有，则进入下一个波束转至步b；否则转至步骤d；

d、判断任务是否可调度，若不可调度，计算任务i的适应度值

e、对每个波束上的分配时间进行比较，找到任务排布最早的时间段，记录这个波束和开始时间，并计算

f、更新剩余波束资源，判断是否有剩余任务，若有，转入a，对下一任务进行处理，若没有，输出

第二方面，本发明提供一种多波束中继卫星任务调度模型的构建装置，所述装置包括：

获取模块，用于获取预设的各调度任务的方向、任务的优先级、任务所属的航天器、任务被成功执行的最早开始时间以及各中继卫星上为各任务服务的可用时间窗；

模型构建模块，用于根据所述各调度任务的方向、任务的优先级、任务所属的航天器、任务被成功执行的最早开始时间以及各任务可用时间窗，构建多波束中继卫星任务调度模型；

其中，其中所述的各调度任务的方向包括前向任务、返向任务以及双向任务；所述前向任务由发射波束提供资源、返向任务由接收波束提供资源、双向任务由发射波束和接收波束提供资源且分配的时间需要保持一致；所述多波束中继卫星任务调度模型包括适应度函数和约束条件，所述适应度函数为用于在指定的所述优先级、所述最早开始时间以及在所述约束条件的约束下获得最优任务调度方案的目标函数；所述最优任务调度方案为使得更多高优先级、任务开始时间早的任务能够被成功执行的方案。

第三方面，本发明提供一种计算机可读存储介质，其存储用于多波束中继卫星任务调度模型的构建的计算机程序，其中，所述计算机程序使得计算机执行如上述所述的多波束中继卫星任务调度模型的构建方法。

第四方面，本发明提供一种电子设备，包括：

一个或多个处理器；

存储器；以及

一个或多个程序，其中所述一个或多个程序被存储在所述存储器中，并且被配置成由所述一个或多个处理器执行，所述程序包括用于执行如上述所述的多波束中继卫星任务调度模型的构建方法。

(三)有益效果

本发明提供了一种多波束中继卫星任务调度模型的构建方法及装置。与现有技术相比，具备以下有益效果：

本发明实施例提供了一种多波束中继卫星任务调度模型的构建方法，首先获取预设的各调度任务的方向、任务的优先级、任务所属的航天器、任务被成功执行的最早开始时间以及各中继卫星上为各任务服务的可用时间窗；然后根据所述各调度任务的方向、任务的优先级、任务所属的航天器、任务被成功执行的最早开始时间以及各任务可用时间窗，以最大化优先级更高的任务能够被成功调度为目标构建多波束中继卫星任务调度模型。所述的各调度任务的方向包括前向任务、返向任务以及双向任务；所述前向任务由发射波束提供资源、返向任务由接收波束提供资源、双向任务由发射波束和接收波束提供资源且分配的时间需要保持一致。本发明在构建模型时，针对天基骨干网中继卫星系统的多个波束以及多种方向的任务，在存在多个波束的场景下，综合考虑了可见时间窗口、任务属性、资源有限等约束条件，从而使得基于该模型得到的任务调度方案能够在满足上述约束条件的情况下完成中继卫星任务的规划，尽可能地保证优先级更高的任务能够被成功调度，进而提高了任务调度的效率。

附图说明

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

图1为本发明实施例中一种多波束中继卫星任务调度模型的构建方法的框图。

具体实施方式

为使本发明实施例的目的、技术方案和优点更加清楚，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

本申请实施例通过提供一种多波束中继卫星任务调度模型的构建方法及装置，解决了现有的模型无法满足多个波束的任务调度的技术问题，实现满足满足多个波束的任务调度，合理的编排调度中继卫星的任务规划，提高中继卫星利用率。

本申请实施例中的技术方案为解决上述技术问题，总体思路如下：

现有的中继卫星调度算法在建模中大多只考虑存在单一波束时的场景，由于现有的中继卫星存在多个波束，包括发射波束、接收波束且不同种类的波束支持不同种类的任务，这使得现有的模型无法满足这一要求。针对上述问题，本发明实施例提出了一种多波束中继卫星任务调度模型的构建方法，该方法在构建模型时，针对天基骨干网中继卫星系统的多个波束以及多种方向的任务，在存在多个波束的场景下，综合考虑了可见时间窗口、任务属性、资源有限等约束条件，从而使得基于该模型得到的任务调度方案能够在满足上述约束条件的情况下完成中继卫星任务的规划，尽可能地保证优先级更高的任务能够被成功调度，进而提高了任务调度的效率。

为了更好的理解上述技术方案，下面将结合说明书附图以及具体的实施方式对上述技术方案进行详细的说明。

本发明实施例提供一种多波束中继卫星任务调度模型的构建方法，如图1所示，该方法包括S1～S2：

S1、获取预设的各调度任务的方向、任务的优先级、任务所属的航天器、任务被成功执行的最早开始时间以及各中继卫星上为各任务服务的可用时间窗；

S2、根据所述各调度任务的方向、任务的优先级、任务所属的航天器、任务被成功执行的最早开始时间以及各任务可用时间窗，以最大化优先级更高的任务能够被成功调度为目标构建多波束中继卫星任务调度模型；

其中，所述的各调度任务的方向包括前向任务、返向任务以及双向任务；所述前向任务由发射波束提供资源、返向任务由接收波束提供资源、双向任务由发射波束和接收波束提供资源且分配的时间需要保持一致。

本发明实施例提供了一种多波束中继卫星任务调度模型的构建方法，该方法在构建模型时，针对天基骨干网中继卫星系统的多个波束以及多种方向的任务，在存在多个波束的场景下，综合考虑了可见时间窗口、任务属性、资源有限等约束条件，从而使得基于该模型得到的任务调度方案能够在满足上述约束条件的情况下完成中继卫星任务的规划，尽可能地保证优先级更高的任务能够被成功调度，进而提高了任务调度的效率。

下面对本发明实施例的具体过程进行详细描述：

在步骤S1中，获取预设的各调度任务的方向、任务的优先级、任务所属的航天器、任务被成功执行的最早开始时间以及各中继卫星上为各任务服务的可用时间窗。具体实施过程如下：

计算机获取预设的各调度任务的方向、任务的优先级、任务所属的航天器、任务被成功执行的最早开始时间以及各中继卫星上为各任务服务的可用时间窗。

各调度任务的方向包括包括前向任务、返向任务以及双向任务，前向任务需要发射波束提供资源、返向任务需要接收波束提供资源、双向任务需要上述两种波束提供资源且分配的时间需要保持一致。可用时间窗，为在满足中继卫星与用户航天器的可见性基础上，符合执行预设任务的时间段。

在步骤S2中，根据所述各调度任务的方向、任务的优先级、任务所属的航天器、任务被成功执行的最早开始时间以及各任务可用时间窗，以最大化优先级更高的任务能够被成功调度为目标构建多波束中继卫星任务调度模型。具体实施过程如下：

多波束中继卫星任务调度模型包括适应度函数和约束条件，所述适应度函数为用于在指定的所述优先级、所述最早开始时间以及在所述约束条件的约束下获得最优任务调度方案的目标函数；所述最优任务调度方案为使得更多高优先级、任务开始时间早的任务能够被成功执行的方案。

在具体实施时，可以理解的是，上述步骤一中构建模型的适应度函数以及约束条件可以通过多种方式来实施，下面对其中一种可选的实施方式进行介绍。

模型的适应度函数的构建

模型的适应度函数表达式如公式(1)所示：

其中：J为待执行任务的集合；

约束条件包括：

(1)同一用户航天器同一时刻可执行多个任务，在资源规划时，每个任务分别考虑，即资源规划的对象为任务而非用户。

(2)任务需要安排在可用时间窗内。

A)中继卫星与用户航天器之间具有可见时间窗约束，即任务的执行时间必须在中继卫星与用户航天器之间的可见时间窗内。

B)任务指定了允许执行的时间段(由最早开始时间、最晚结束时间构成)，允许执行的时间段与可见时间窗的交集为任务的可用时间窗，任务需要安排在可用时间窗内；

C)任务执行时间不允许拆分成多个子时间段，所以只能选择时间长度比任务持续时间长的可用时间窗。

任务i在波束k上的可用时间窗用W

(3)部分任务之间具有依赖性。

双向任务需要同时安排发射波束和接收波束，具有强依赖性，需要安排在完全相同的时间段内执行，其数学表达式如公式(2)所示：

t

(4)一个任务只能在一个波束上执行，也就是说，任务执行时不能切换波束，其数学表达式如公式(3)所示：

(5)同一波束同一时间在特定条件下可执行多个任务

A)波束同时服务多个任务的前提为：这些任务属于同一用户u

B)不满足同时服务多个任务的情况下，同一波束同一时间只执行一个任务，即同一波束上的不同任务执行时间不能重叠，其数学表达式如公式(4)所示：

其中：

J为待执行任务的集合；C

需要说明的是，在本发明实施例中，可通过人工蜂群算法改变任务的顺序计算适应度值，求解所述中继卫星预约任务调度约束规划模型的最优解，得到最优任务调度方案。其具体实施过程如下：

S201、设定算法参数和初始化种群，包括：

设定算法的参数：任务数N，种群的规模m，阈值Lf，二次邻域搜索循环次数U，迭代次数L。

初始化种群：随机生成m个初始解x

S202、从当前解中抽取一个任务，然后随机插入一个位置，为种群中每个解生成一个邻域解

S203、根据解的二次邻域搜索循环次数U，进行U次二次邻域搜索操作。具体包括：

每次二次邻域搜索操作如下：从该种群中随机抽取两个解(x

S204、根据S203得到的解邻域集合，对每个解的邻域集合进行判断。若某个解(x

如果

S205、记录本次迭代中出现的最优解x

S206、判断每个解连续无更新邻域搜索次数是否超过阈值Lf。如果l

S207、输出mf，mf即为预约任务最优解，根据最优解得到最优任务调度方案。

适应度值的计算过程如下：

a、获取任务i的任务方向，判断任务由那种波束服务；

b、获取任务i在波束k所属卫星上的可用时间、波束k被占用的时间段；依次处理这个任务在波束k上的每个可用时间以及被占用的时间段，找到可用的最早的时间窗，若有，则标记任务i可调度并记录该时间段以及所属波束，转至步骤e，否则，转至步骤c；

c、判断是否还有未处理的波束，若有，则进入下一个波束转至步b；否则转至步骤d；

d、判断任务是否可调度，若不可调度，计算任务i的适应度值

e、对每个波束上的分配时间进行比较，找到任务排布最早的时间段，记录这个波束和开始时间，并计算

f、更新剩余波束资源，判断是否有剩余任务，若有，转入a，对下一任务进行处理，若没有，输出

本发明实施例还提供一种多波束中继卫星任务调度模型的构建装置，该装置包括：

获取模块，用于获取预设的各调度任务的方向、任务的优先级、任务所属的航天器、任务被成功执行的最早开始时间以及各中继卫星上为各任务服务的可用时间窗；

模型构建模块，用于根据所述各调度任务的方向、任务的优先级、任务所属的航天器、任务被成功执行的最早开始时间以及各任务可用时间窗，构建多波束中继卫星任务调度模型；

其中，其中所述的各调度任务的方向包括前向任务、返向任务以及双向任务；所述前向任务由发射波束提供资源、返向任务由接收波束提供资源、双向任务由发射波束和接收波束提供资源且分配的时间需要保持一致；所述多波束中继卫星任务调度模型包括适应度函数和约束条件，所述适应度函数为用于在指定的所述优先级、所述最早开始时间以及在所述约束条件的约束下获得最优任务调度方案的目标函数；所述最优任务调度方案为使得更多高优先级、任务开始时间早的任务能够被成功执行的方案。

理解的是，本发明实施例提供的多波束中继卫星任务调度模型的构建装置与上述多波束中继卫星任务调度模型的构建方法相对应，其有关内容的解释、举例、有益效果等部分可以参考多波束中继卫星任务调度模型的构建方法中的相应内容，此处不再赘述。

本发明实施例还提供一种计算机可读存储介质，其存储用于多波束中继卫星任务调度模型的构建的计算机程序，其中，所述计算机程序使得计算机执行上述所述的多波束中继卫星任务调度模型的构建方法。

本发明实施例还提供一种电子设备，包括：一个或多个处理器；存储器；以及一个或多个程序，其中所述一个或多个程序被存储在所述存储器中，并且被配置成由所述一个或多个处理器执行，所述程序包括用于执行上述所述的多波束中继卫星任务调度模型的构建方法。

综上所述，与现有技术相比，具备以下有益效果：

本发明实施例提供了一种多波束中继卫星任务调度模型的构建方法，该方法在构建模型时，针对天基骨干网中继卫星系统的多个波束以及多种方向的任务，在存在多个波束的场景下，综合考虑了可见时间窗口、任务属性、资源有限等约束条件，从而使得基于该模型得到的任务调度方案能够在满足上述约束条件的情况下完成中继卫星任务的规划，尽可能地保证优先级更高的任务能够被成功调度，进而提高了任务调度的效率。

需要说明的是，通过以上的实施方式的描述，本领域的技术人员可以清楚地了解到各实施方式可借助软件加必需的通用硬件平台的方式来实现。基于这样的理解，上述技术方案本质上或者说对现有技术做出贡献的部分可以以软件产品的形式体现出来，该计算机软件产品可以存储在计算机可读存储介质中，如ROM/RAM、磁碟、光盘等，包括若干指令用以使得一台计算机设备(可以是个人计算机，服务器，或者网络设备等)执行各个实施例或者实施例的某些部分所述的方法。

在本文中，诸如第一和第二等之类的关系术语仅仅用来将一个实体或者操作与另一个实体或操作区分开来，而不一定要求或者暗示这些实体或操作之间存在任何这种实际的关系或者顺序。而且，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者设备不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者设备所固有的要素。在没有更多限制的情况下，由语句“包括一个……”限定的要素，并不排除在包括所述要素的过程、方法、物品或者设备中还存在另外的相同要素。

以上实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的精神和范围。