中继卫星任务调度约束规划模型的构建方法及装置

摘要

本发明实施例提供了一种中继卫星任务调度约束规划模型的构建方法及装置，该方法在构建模型时，针对天基骨干网中继卫星系统的前向链路，即地面站——中继卫星——用户航天器，或者地面站——中继卫星——中继卫星——用户航天器，在存在多颗中继卫星，且中继卫星之间存在通信链路的情况下，综合考虑了可见时间窗口、任务属性、资源有限用户任务调度的传播时延受限以及通信延迟受限等约束条件，从而使得基于该模型得到的任务调度方案能够在满足上述约束条件的情况下完成中继卫星任务的规划，尽可能地保证优先级更高的任务能够被成功调度，进而提高了任务调度的效率。

说明书

技术领域

本发明实施例涉及通信技术领域，具体涉及一种中继卫星任务调度约束规划模型的构建方法及装置。

背景技术

由于中继卫星数量有限，数据服务能力有限，并且与需要中继卫星服务的用户航天器之间存在可见时间窗的约束，因此如何合理的编排调度中继卫星的任务规划是提高中继卫星利用率，进而提高整个空间信息网络的效率的关键技术。现有中继卫星系统任务调度研究的主要对象是预约式任务，由于中继卫星任务调度问题的复杂性，现有的中继卫星任务调度的数学模型大多数为NP-hard问题，因此现有的解决方法多为启发式算法。第一种算法利用人工蜂群算法解决任务规划问题，其首先建立了中继卫星调度的数学模型，给出了适应度函数以及各种约束条件，并且利用人工蜂群算法来搜索并得到较优的任务调度方案。第二种算法建立了存在多中继卫星条件下的任务调度模型，并且利用基于种群联合进化的资源分配算法进行求解。

然而，在实现发明创造的过程中，发明人发现，原有的中继卫星调度算法在建模中大多只考虑存在单一中继卫星时的场景，例如第一种算法。第二种算法考虑存在多中继卫星的场景，但是其忽略了中继卫星之间存在通信链路的情况，实际上由于中继卫星间存在通信链路，因此当某个用户航天器任务需要某个特定中继卫星为其服务时，其不但可以直接与这个中继卫星联系，而且能通过中继卫星中继的方法与这个中继卫星间接的联系。

同样，现有的建模中(例如上述第一种以及第二种算法)并未考虑任务的时延要求，由于中继卫星间，中继卫星与用户星间距离漫长，因此数据传输时延明显，许多时延敏感类任务，例如测控信号的传输对数据传输时延有着严格的要求，这使得现有的模型无法满足这一要求。

发明内容

本发明实施例的目的在于提供一种用于中继卫星任务调度约束规划模型的构建方法及装置。

第一方面，本发明实施例提供了一种中继卫星任务调度约束规划模型的构建方法，包括：

获取预设的各调度任务的优先级、各任务被成功执行的最早开始时间、所有任务的最大延迟时间以及各中继卫星上为各任务服务的可用时间窗；

根据所述各调度任务的优先级、各任务被成功执行的最早开始时间、所有任务的最大传播时延以及可用时间窗，构建所述模型的适应度函数及约束条件；

其中，所述可用时间窗，为在满足中继卫星与用户航天器的可见性基础上，符合执行预设任务的时间段；所述模型的适应度函数，为用于在指定的所述优先级、所述最早开始时间以及所述最大传播时延下、在所述约束条件的约束下获得最优任务调度方案的目标函数；所述最优任务调度方案为使得更高优先级、传播时延更小的最多任务能够被成功执行的方案。

第二方面，本发明实施例提供了一种中继卫星任务调度约束规划模型的构建装置，包括：

获取单元，获取预设的各调度任务的优先级、各任务被成功执行的最早开始时间、所有任务的最大延迟时间以及各中继卫星上为各任务服务的可用时间窗；

构建单元，用于根据所述各调度任务的优先级、各任务被成功执行的最早开始时间、所有任务的最大传播时延以及可用时间窗，构建所述模型的适应度函数及约束条件；

其中，所述可用时间窗，为在满足中继卫星与用户航天器的可见性基础上，符合执行预设任务的时间段；所述模型的适应度函数，为用于在指定的所述优先级、所述最早开始时间以及所述最大传播时延下、在所述约束条件的约束下获得最优任务调度方案的目标函数；所述最优任务调度方案为使得更高优先级、传播时延更小的最多任务能够被成功执行的方案。

第三方面，本发明的又一实施例提供了一种计算机设备，包括存储器、处理器以及存储在存储器上并可在处理器上运行的计算机程序，所述处理器执行所述程序时实现上述第一方面所述方法的步骤。

第四方面，本发明的又一实施例提供了一种计算机可读存储介质，其上存储有计算机程序，该程序被处理器执行时实现如第一方面所述方法的步骤。

本发明实施例提供了一种中继卫星任务调度约束规划模型的构建方法，该方法在构建模型时，针对天基骨干网中继卫星系统的前向链路，即地面站——中继卫星——用户航天器，或者地面站——中继卫星——中继卫星——用户航天器，在存在多颗中继卫星，且中继卫星之间存在通信链路的情况下，综合考虑了可见时间窗口、任务属性、资源有限用户任务调度的传播时延受限以及通信延迟受限等约束条件，从而使得基于该模型得到的任务调度方案能够在满足上述约束条件的情况下完成中继卫星任务的规划，尽可能地保证优先级更高的任务能够被成功调度，进而提高了任务调度的效率。

附图说明

通过阅读下文优选实施方式的详细描述，各种其他的优点和益处对于本领域普通技术人员将变得清楚明了。附图仅用于示出优选实施方式的目的，而并不认为是对本发明的限制。而且在整个附图中，用相同的参考符号表示相同的部件。在附图中：

图1是本发明实施例提供的一种中继卫星任务调度约束规划模型的构建方法流程图；

图2是本发明提供的一种中继卫星任务调度约束规划模型的构建装置实施例结构示意图；

图3是本发明提供的一种计算机设备实施例结构框图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

第一方面，本发明实施例提供了一种中继卫星任务调度约束规划模型的构建方法，如图1所示，包括：

S101、获取预设的各调度任务的优先级、各任务被成功执行的最早开始时间、所有任务的最大延迟时间以及各中继卫星上为各任务服务的可用时间窗；

S102、根据所述各调度任务的优先级、各任务被成功执行的最早开始时间、所有任务的最大传播时延以及可用时间窗，构建所述模型的适应度函数及约束条件；

其中，所述可用时间窗，为在满足中继卫星与用户航天器的可见性基础上，符合执行预设任务的时间段；所述模型的适应度函数，为用于在指定的所述优先级、所述最早开始时间以及所述最大传播时延下、在所述约束条件的约束下获得最优任务调度方案的目标函数；所述最优任务调度方案为使得更高优先级、传播时延更小的最多任务能够被成功执行的方案。

本发明实施例提供了一种中继卫星任务调度约束规划模型的构建方法，该方法在构建模型时，针对天基骨干网中继卫星系统的前向链路，即地面站——中继卫星——用户航天器，或者地面站——中继卫星——中继卫星——用户航天器，在存在多颗中继卫星，且中继卫星之间存在通信链路的情况下，综合考虑了可见时间窗口、任务属性、资源有限用户任务调度的传播时延受限以及通信延迟受限等约束条件，从而使得基于该模型得到的任务调度方案能够在满足上述约束条件的情况下完成中继卫星任务的规划，尽可能地保证优先级更高的任务能够被成功调度，进而提高了任务调度的效率。

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

(一)模型的适应度函数的构建

模型的适应度函数表达式为：

其中，ρ_i＝P_max-p_i，p_i为用户指定的任务i的优先级，P_max表示任务优先级加权值的最大值加一，取P_max＝11，p_i∈{1,2,3,...,10}，则ρ_i表示任务i的优先级的加权值，用户指定的任务i的优先级越高，即p_i越小，则得到的ρ_i越大，即任务i优先级的加权值越大。如用户指定任务i的优先级为p_i＝1，则任务i的优先级的加权值为ρ_i＝11-1＝10。加权值ρ_i越大，代表任务i优先级越高。

β_i＝D_max-|T_i-e_i|，D_max表示事先指定的所有任务的最大延迟，T_i表示任务i调度成功的开始执行时间，e_i表示用户指定的任务i被成功执行的最早开始时间，|T_i-e_i|表示任务i的延迟，任务的开始执行时间越接近用户指定的任务最早开始执行时间，即|T_i-e_i|越小，则延迟越小，加权值β_i越大。

χ_im＝{0,1},i∈J,m∈M，若χ_im＝1，表明任务i被中继卫星m调度成功；否则，表明调度失败。

该适应度函数表达式的目标是使更高优先级的、延迟更小的、更多的任务被成功执行。(二)模型约束函数的构建

模型的约束条件式为：

(6)

i,j∈J且i≠j,其中i,j∈J且i≠j,δ_ij＝1

其中，式(2)表示若一个任务调度成功，则该任务只能在一颗中继卫星上调度成功，否则认为该任务调度失败。

式(3)中，χ_ijm＝{0,1},i,j∈J,m∈M，若χ_ijm＝1，表明中继卫星m执行完任务i后立即执行任务j。约束条件式(3)表明若任意两个任务在被一颗中继卫星调度到用户航天器上，则执行顺序必须是一前一后，即表明一颗中继卫星在同一时间最多只能为一个任务服务。

式(4)是为了保证在同一颗中继卫星上执行的任务能排成一个有序序列，同时也保证了一颗中继卫星在同一时刻最多只能执行一个任务。

式(5)中，W_im＝B_i∩A_im，B_i表示用户指定的任务i被成功执行的最早开始时间与最晚结束时间构成的时间窗，A_im表示能够为任务i服务的中继卫星m的可见时间窗的集合，W_im表示中继卫星m上能为任务i服务的所有可用时间窗的集合。所谓可用时间窗，就是在满足中继卫星与用户航天器的可见性基础上，符合用户指定的任务执行时间段。若则表明任务i在中继卫星m的可用时间窗w内。约束条件式(5)表明了任务必须满足可见时间窗约束，才可能被调度成功，而且调度成功的任务执行时仅能在一个可用时间窗口内进行。

式(6)中，d_i表示任务i的持续时间，d_i＝d₀+d_i'，d₀为中继卫星服务开始和终止阶段消耗的时间，与天基骨干网中继卫星系统的软硬件设备有关，如在服务准备阶段，地面站需要建立连接，同时配置星间、星地通信链路设备与数据服务器系统，在服务终止阶段，地面站需要断开连接，释放并拆除链路，同时释放卫星资源，d_i'为任务i实际的数据通信时间，由用户根据实际需要进行提交。ε_ijm表示中继卫星m执行完任务i后立即执行任务j的交换时间。i,j∈J且i≠j，表示任务j被成功执行的最早开始时间与任务i被成功执行的最晚结束时间之间的时间段。T_i表示任务i调度成功的开始执行时间。约束条件式(6)表明若两个任务i,j(j在i之后执行)在同一颗中继卫星上执行时，任务j的开始执行时间T_j必须在任务i执行完T_i+d_i+ε_ijm之后，进一步强调一颗中继卫星在同一时刻只能执行一个任务。

式(7)中，ο_ij＝{0,1},i,j∈J，若ο_ij＝1，则表明任务i在任务j之前执行。约束条件式(7)表示一颗中继卫星上的两个任务i,j发生资源冲突时，任务i,j的执行时间是不能有重叠的，即必须是一个在前一个在后执行，也表明了一颗中继卫星在同一时刻只能为一个任务服务。

式(8)中，为任务i在中继卫星m的可用时间窗w上的开始时间，式(9)中，为任务i在中继卫星m的可用时间窗w上的结束时间，其中，i∈J，m∈M，w∈W_im。约束条件式(8)和式(9)表示任务要想被调度成功，就必须在一个可用时间窗内执行，其中约束条件式(8)表示任务的开始执行时间必须大于或等于该可用时间窗的开始时间；约束条件式(9)表示任务的结束时间必须小于或等于该可用时间窗的结束时间。

式(10)中，t_i表示用户指定的任务i被调度到用户航天器所经历的最大传播时延。v表示电磁波传播的速率，默认v＝3.0×10⁸km/s。s_i表示任务i被调度到用户航天器所经历的总的传播距离，其中，s_n表示地面站与中继卫星n之间的距离，s_mn表示中继卫星m与n之间的距离，表示中继卫星m在可用时间窗w上与用户航天器的距离。φ_i＝{0,1},i∈J，若φ_i＝1，则表明任务i满足传播时延要求。约束条件式(10)表示任务i被调度到用户航天器所经历的最大传播时延不大于用户指定的最大传播时延，即满足传播时延要求。

式(11)中，进一步表明任务要想被成功调度的可执行时间必须在某一中继卫星与用户航天器之间的可用时间窗内，也只有在可用时间窗内才能执行任务。

通过上述构建适应度函数以及约束函数的步骤，即可得到在各种现实条件约束下的多中继卫星系统调度模型。通过适当的优化算法(例如遗传算法等优化算法)得出任务分配方案，可以求出该模型的最优解。其中该最优解为使得模型适应度函数(1)取值最大，同时满足(2)到(11)约束条件的最优解。该最优解即可以作为最优任务调度方案，应用于实际情况下的任务调度中。

第二方面，本发明实施例提供了一种中继卫星任务调度约束规划模型的构建装置，如图2所示，包括：

获取单元201，获取预设的各调度任务的优先级、各任务被成功执行的最早开始时间、所有任务的最大延迟时间以及各中继卫星上为各任务服务的可用时间窗；

构建单元202，用于根据所述各调度任务的优先级、各任务被成功执行的最早开始时间、所有任务的最大传播时延以及可用时间窗，构建所述模型的适应度函数及约束条件；

其中，所述可用时间窗，为在满足中继卫星与用户航天器的可见性基础上，符合执行预设任务的时间段；所述模型的适应度函数，为用于在指定的所述优先级、所述最早开始时间以及所述最大传播时延下、在所述约束条件的约束下获得最优任务调度方案的目标函数；所述最优任务调度方案为使得更高优先级、传播时延更小的最多任务能够被成功执行的方案。

其中，这里的适应度函数以及约束条件的构建可以参照第一方面中对于适应度函数以及约束条件构建步骤的具体过程，在此不再赘述。

在具体实施时，所述装置还包括：

优化单元203，用于基于得到的所述模型，利用预设的优化算法求取所述模型的最优解，其中所述最优解为使得所述适应度函数取值最大且满足所述约束条件的解，并将所述最优解作为所述最优任务调度方案输出。

由于本实施例所介绍的中继卫星任务调度约束规划模型的构建装置为可以执行本发明实施例中的中继卫星任务调度约束规划模型的构建方法的装置，故而基于本发明实施例中所介绍的中继卫星任务调度约束规划模型的构建的方法，本领域所属技术人员能够了解本实施例的中继卫星任务调度约束规划模型的构建装置的具体实施方式以及其各种变化形式，所以在此对于该中继卫星任务调度约束规划模型的构建装置如何实现本发明实施例中的中继卫星任务调度约束规划模型的构建方法不再详细介绍。只要本领域所属技术人员实施本发明实施例中中继卫星任务调度约束规划模型的构建方法所采用的装置，都属于本申请所欲保护的范围。

图3示出本发明实施例提供的计算机设备的结构框图。

参照图3，该计算机设备，包括处理器(processor)301、存储器(memory)302、总线303以及总线接口304；

其中，所述处理器301以及存储器302通过所述总线303完成相互间的通信，总线接口304用于与外界设备进行信息交互；

所述处理器301用于调用所述存储器302中的程序指令，以执行上述各方法实施例中第一方面所述的方法。

本发明实施例还公开一种计算机程序产品，所述计算机程序产品包括存储在非暂态计算机可读存储介质上的计算机程序，所述计算机程序包括程序指令，当所述程序指令被计算机执行时，计算机能够执行上述各方法实施例第一方面所述的方法。

本发明实施例还提供一种非暂态计算机可读存储介质，所述非暂态计算机可读存储介质存储计算机指令，所述计算机指令使所述计算机执行上述各方法实施例第一方面所述的方法。

在此处所提供的说明书中，说明了大量具体细节。然而，能够理解，本发明的实施例可以在没有这些具体细节的情况下实践。在一些实例中，并未详细示出公知的方法、结构和技术，以便不模糊对本说明书的理解。

类似地，应当理解，为了精简本公开并帮助理解各个发明方面中的一个或多个，在上面对本发明的示例性实施例的描述中，本发明的各个特征有时被一起分组到单个实施例、图、或者对其的描述中。然而，并不应将该公开的方法解释成反映如下意图：即所要求保护的本发明要求比在每个权利要求中所明确记载的特征更多的特征。更确切地说，如下面的权利要求书所反映的那样，发明方面在于少于前面公开的单个实施例的所有特征。因此，遵循具体实施方式的权利要求书由此明确地并入该具体实施方式，其中每个权利要求本身都作为本发明的单独实施例。

本领域那些技术人员可以理解，可以对实施例中的设备中的模块进行自适应性地改变并且把它们设置在与该实施例不同的一个或多个设备中。可以把实施例中的模块或单元或组件组合成一个模块或单元或组件，以及此外可以把它们分成多个子模块或子单元或子组件。除了这样的特征和/或过程或者单元中的至少一些是相互排斥之外，可以采用任何组合对本说明书(包括伴随的权利要求、摘要和附图)中公开的所有特征以及如此公开的任何方法或者设备的所有过程或单元进行组合。除非另外明确陈述，本说明书(包括伴随的权利要求、摘要和附图)中公开的每个特征可以由提供相同、等同或相似目的的替代特征来代替。

此外，本领域的技术人员能够理解，尽管在此的一些实施例包括其它实施例中所包括的某些特征而不是其它特征，但是不同实施例的特征的组合意味着处于本发明的范围之内并且形成不同的实施例。例如，在下面的权利要求书中，所要求保护的实施例的任意之一都可以以任意的组合方式来使用。

本发明的某些部件实施例可以以硬件实现，或者以在一个或者多个处理器上运行的软件模块实现，或者以它们的组合实现。本领域的技术人员应当理解，可以在实践中使用微处理器或者数字信号处理器(DSP)来实现根据本发明实施例的网关、代理服务器、系统中的一些或者全部部件的一些或者全部功能。本发明还可以实现为用于执行这里所描述的方法的一部分或者全部的设备或者装置程序(例如，计算机程序和计算机程序产品)。这样的实现本发明的程序可以存储在计算机可读介质上，或者可以具有一个或者多个信号的形式。这样的信号可以从因特网网站上下载得到，或者在载体信号上提供，或者以任何其他形式提供。

应该注意的是上述实施例对本发明进行说明而不是对本发明进行限制，并且本领域技术人员在不脱离所附权利要求的范围的情况下可设计出替换实施例。在权利要求中，不应将位于括号之间的任何参考符号构造成对权利要求的限制。单词“包含”不排除存在未列在权利要求中的元件或步骤。位于元件之前的单词“一”或“一个”不排除存在多个这样的元件。本发明可以借助于包括有若干不同元件的硬件以及借助于适当编程的计算机来实现。在列举了若干装置的单元权利要求中，这些装置中的若干个可以是通过同一个硬件项来具体体现。单词第一、第二、以及第三等的使用不表示任何顺序。可将这些单词解释为名称。