基于分层优化的卫星测控任务调度方法、装置和设备

本申请涉及航天测控网资源调度技术领域，特别是涉及一种基于分层优化的卫星测控任务调度方法、装置和设备。

随着各种功能、不同轨道卫星数量快速增长，为卫星提供测控支持的地面设备数量并不能同步增长。因此，在有限资源情况下如何实现更高效的资源调度是需要研究的关键问题，但以往对资源调度问题的研究基本针对低轨卫星，所设计的调度模型，例如：一些在低轨卫星资源调度中讨论较多的算法，如遗传算法、启发式全局搜索算法等，在用于中高轨卫星的资源调度时的调度效率和调度结果并不令人满意。

中高轨卫星和低轨卫星因轨道类型不同，资源调度模型涉及的基本条件存在明显差异，例如包括：卫星可见时间窗口长(一般在数小时甚至24小时可见)、同一时间多个地面设备可见(尤其是国内布站情况下)、多种任务类型需分别调度(低轨卫星通常遥测、遥控和测轨一体调度，而中高轨卫星遥测、测轨和遥控通常分别调度，尤其是遥测需求时间较长)、多个测控需求因存在关联约束而需要一体调度，这些导致中高轨卫星调度对象的最优可行解的选择自由度过大，使用已有调度方法到最优解变得非常困难。在实现本发明过程中，发明人发现随着卫星导航、通信等中高轨卫星的大量增加，需要研究适合中高轨卫星的大规模资源调度方法，目前，传统的卫星资源调度方法仍存在着中高轨卫星例行测控任务调度效率不高的技术问题。

基于此，有必要针对上述技术问题，提供一种基于分层优化的卫星测控任务调度方法、一种基于分层优化的卫星测控任务调度装置以及一种计算机设备，能够大幅提高中高轨卫星例行测控任务的调度效率。

为了实现上述目的，本发明实施例采用以下技术方案：

一方面，本发明实施例提供一种基于分层优化的卫星测控任务调度方法，包括步骤：

基于收到的资源使用申请，建立统一模型的中高轨卫星资源需求对象集合、设备能力对象集合和卫星对设备的可见预报集合；

对需求对象集合进行预处理和解耦关联约束，生成各调度分层的新需求对象集合；

根据新需求对象集合、设备能力对象集合和可见预报集合，依次串行调用设计的分调度层进行资源分层调度，生成分层调度初始解集合；分调度层包括连续跟踪任务调度层、单遥测限定设备调度层、一体化测控数传调度层、测轨/遥控需求调度层和单遥测补全处理调度层；

调用设计的优化调度层，根据需求对象集合对分层调度初始解集合进行关联约束重建与优化调度处理，生成分层调度优化解集合；分层调度优化解集合用于指示资源使用申请对应的中高轨卫星资源调度结果。

另一方面，还提供一种基于分层优化的卫星测控任务调度装置，包括：

集合建立模块，用于基于收到的资源使用申请，建立统一模型的中高轨卫星资源需求对象集合、设备能力对象集合和卫星对设备的可见预报集合；

集合分层模块，用于对需求对象集合进行预处理和解耦关联约束，生成各调度分层的新需求对象集合；

分层调度模块，用于根据新需求对象集合、设备能力对象集合和可见预报集合，依次串行调用设计的分调度层进行资源分层调度，生成分层调度初始解集合；分调度层包括连续跟踪任务调度层、单遥测限定设备调度层、一体化测控数传调度层、测轨/遥控需求调度层和单遥测补全处理调度层；

优化调度模块，用于调用设计的优化调度层，根据需求对象集合对分层调度初始解集合进行关联约束重建与优化调度处理，生成分层调度优化解集合；分层调度优化解集合用于指示资源使用申请对应的中高轨卫星资源调度结果。

又一方面，还提供一种计算机设备，包括存储器和处理器，存储器存储有计算机程序，处理器执行计算机程序时实现任一项的上述基于分层优化的卫星测控任务调度方法的步骤。

上述技术方案中的一个技术方案具有如下优点和有益效果：

上述基于分层优化的卫星测控任务调度方法、装置和设备，通过基于收到的资源使用申请，建立统一模型的中高轨卫星资源的三大数据集合，然后对需求对象集合进行预处理和解耦关联约束，生成各调度分层的新需求对象集合，进而根据新需求对象集合、设备能力对象集合和可见预报集合，依次串行调用设计的分调度层进行资源分层调度，生成分层调度初始解集合，最后再调用设计的第六个分调度层(优化调度层)进行关联约束重建与优化调度处理，生成最终的分层调度优化解集合，即可得到资源使用申请对应的中高轨卫星资源调度结果。

采用了统一的中高轨卫星资源需求模型和设备能力模型，在保证整体调度满足率的前提下，以分层调度优化方法使得中高轨卫星资源调度过程可以极大地缩小可行解空间搜索的数量级，提高到最优解的时间效率，降低调度算法计算复杂度，达到了较好的调度满足率和调度效率。与现有技术相比，上述方案能够收集中高轨卫星测运控用户提交的测控资源使用申请，以整体满足率最大为目标，用分层调度优化的方法快速生成中高轨卫星例行测控任务调度结果。

图1为一个实施例中基于分层优化的卫星测控任务调度方法的流程示意图；

图2为一个实施例中连续跟踪任务调度法实现的调度处理流程示意图；

图3为一个实施例中单遥测任务调度法实现的调度处理流程示意图；

图4为一个实施例中局部搜索选优调度法实现的调度处理流程示意图；

图5为一个实施例中优化调度层实现的优化调度处理流程示意图；

图6为另一个实施例中基于分层优化的卫星测控任务调度方法的流程示意图；

图7为一个实施例中基于分层优化的卫星测控任务调度装置的模块结构示意图。

为了使本申请的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本申请进行进一步详细说明。应当理解，此处描述的具体实施例仅仅用以解释本申请，并不用于限定本申请。

除非另有定义，本文所使用的所有的技术和科学术语与属于本申请的技术领域的技术人员通常理解的含义相同。本文中在本申请的说明书中所使用的术语只是为了描述具体的实施例的目的，不是旨在于限制本申请。

另外，本发明各个实施例之间的技术方案可以相互结合，但是必须是以本领域普通技术人员能够实现为基础，当技术方案的结合出现相互矛盾或无法实现时，应当认为这种技术方案的结合不存在，也不在本发明要求的保护范围之内。

本发明调度是指将某一套地面设备(下文简称设备)的某一段工作时间分配给一个需求对象，主要指两个方面：一方面是该设备分配的时间窗口在该卫星对该设备的可见预报范围内，该设备在分配的时间窗口内被卫星独占，即一套设备在同一时间只能被一颗卫星独占，该设备跟踪其它卫星的时间窗口不能与该分配时间窗口有重合。

另一方面是设备能力特征(设备能力统一模型对象的属性)与需求对象的要求(需求对象统一模型的属性)相匹配，包括：该设备分配的时间窗口和设备不可用时段没有重合，该设备支持需求对象要求的任务类型、频率，该卫星在该设备的支持卫星列表中，该设备在分配时间窗口内跟踪卫星时在设备要求的最低仰角和最高仰角范围内，此外分配给该卫星的设备时间窗口还要向前增加跟踪准备时间、向后增加跟踪结束退出时间。

调度后某个设备被某颗卫星独占的一个时间窗口即构成一个解。调度过程中可能有多套设备能满足一个需求对象，往往在一个需求对象要求的时间窗口(称作可见窗)内，只需要分配一段满足需求对象最小服务时长但长度远小于需求对象要求的时间窗口(称作可分配窗，一个可分配窗口即为一个可行解)，则一个需求对象要求的可见窗内同一套设备通过窗口滑动可以生成多个可行解(时间窗滑动间隔越小，可行解数量越多)，多套设备可见窗口构成该需求对象的可行解集合。

一套设备的能力可满足多个需求对象的要求，但一套设备在一个时间窗口只能被一颗卫星占用，因此就会有多个需求对象的可行解之间有冲突(多个需求对象的同一套设备的可分配窗在时间上有冲突)，调度即是在该需求对象的可行解集合中到最合理的一个可行解作为需求对象的解。在调度过程中，越先分配的可分配窗对其它未分配的可见窗的影响越大，如果先分配的可见窗不合理，将导致后面待处理的需求对象的可分配窗分配越困难，甚至没有可行解，降低整体满足率。对同一颗卫星，其可调整的时间窗口相比分配窗口比例越大、满足其要求的可用设备越多，则生成的解空间越大，同时不同卫星可用设备相互交叉越多，则调度计算越复杂，到其最优解的计算量和复杂度将成指数级增加。因此工程实现中需尽量降低调度过程中的计算量，并控制复杂度，在可接受时间范围内到好的调度解。

请参阅图1，在一个实施例中，本发明提供一种基于分层优化的卫星测控任务调度方法，包括如下步骤S12至S18。

S12，基于收到的资源使用申请，建立统一模型的中高轨卫星资源需求对象集合、设备能力对象集合和卫星对设备的可见预报集合。

可以理解，收到的资源使用申请可以但不限于是中高轨卫星测控、运控等卫星用户单位提出的设备使用申请。基于收到的资源使用申请，可以建立采用统一模型的需求对象集合、设备能力对象集合和卫星对设备的可见预报集合。

为方便描述与理解前述内容，可以对前述集合分别结合可选的如下描述示例进行说明。建立统一模型的需求对象集合卫星si的一个需求对象的主要属性包括：卫星标识(可唯一标记该卫星si，以与其它卫星区别，可使用字符串编号)，任务类型{遥控(TC)，遥测(TM)，测轨(P)，一体化测控数传(INT)中的一种任务类型或者两种任务类型以上的组合任务类型}，时间窗口{窗口数量3个以内}及最小服务时长要求，优先级，测控频率，期望使用设备列表，设备可调整标记，弧段可拆分标记以及必须连续跟踪标识等；

此外，若一个需求对象需要多个任务类型的弧段或者多个时间窗口的组合同时满足，则构成关联需求对象。关联需求对象的属性包括：关联模式代号、最少满足弧段数、最少满足时间长度、相邻弧段见最大时间间隔、相邻弧段设备变更需求标记、是否需要多设备同时跟踪等。

建立统一模型的设备能力对象集合资源rj具备的主要属性包括：设备标识(可唯一标记该设备，能与其它设备区别，可使用字符串编号)，支持的任务类型(支持遥控(TC)、测轨(P)、遥测(TM)、一体化测控数传(INT)四种任务类型中一种或两种以上的组合)，支持的频率范围，支持的卫星列表(该设备配置有支持卫星的基本参数信息)，跟踪准备时间，跟踪结束退出时间，最低仰角或最高仰角限制，不可用时段，所在点位等。在转换为统一模型对象时，可将原始的时间值映射为以某一时间为起始时刻的秒计数值，将字符串常量映射为数值常量，便于提高后续步骤S16和步骤S18资源调度中的大量值比较、时间值处理的速度；同时，为每个需求对象建立唯一的需求序号进行标识。

基于卫星对设备的可见预报构建可见预报集合表示卫星si对设备rj在时间窗口内可见，可见窗口的开始时间和结束时间表示卫星相对设备在一定仰角(如10度)以上时的入境和出境的时刻。

S14，对需求对象集合进行预处理和解耦关联约束，生成各调度分层的新需求对象集合。

可以理解，在该步骤中，对需求对象集合中的需求对象进行基本约束合理性预处理，对有关联约束的需求对象进行解耦，将有关联约束要求的需求对象拆分为非关联需求对象，对没有关联约束的需求对象按新需求对象的统一模型属性要求进行映射，即将原需求对象集合T变换为新的需求对象集合T′。

新需求对象是在原需求对象基础上构建的，但增加了全局统一的申请(需求)序号、子申请(需求)序号，增加的申请序号和子申请序号是为了建立原需求对象和新需求对象的关系。解耦了原需求对象中的关联约束，以降低调度分层的处理复杂度，但这些关联约束仍是必须要遵守的，因此在最后一个分调度层就需要用到原需求对象的约束信息，对分调度层输出的一些不满足关联约束的解会进行二次调度(也即最后一个分调度层的优化调度)。

在一些实施方式中，关于上述步骤S14，具体可以包括如下处理步骤：

检查需求对象集合中原需求对象的设备约束、时间约束和关联约束参数的合理性；

对有关联约束的原需求对象进行关联约束解耦；

以需求对象集合中无关联约束的原需求对象及解耦后的原需求对象为模板，建立需求序号共用的新需求对象并为每个新需求对象添加子需求序号。

可以理解，首先，对需求对象集合中原需求对象进行的基本约束合理性预处理，包括检查资源需求的设备约束(某些卫星的特定任务类型只能申请特定设备)、时间约束(时间窗口不能超出计划周期时间窗口，时间窗口长度要大于最小服务时长要求，时间窗口长度要大于调度系统基本弧长约束)，以及各需求参数间的关联约束参数的合理性等，不满足预处理条件的需求对象无需建立相应的新需求对象。

然后，按顺序对各个原需求对象进行处理，基于原需求对象建立相应的新需求对象，并添加需求子序号(例如默认填1或其他标识值)，与需求序号一起作为新需求对象的唯一性标识；需要注意的是，这里新需求对象的序号包括两个部分：与相应原需求对象的需求序号相同的需求序号(也即前述所指的需求序号共用)，以及其被添加的子需求序号。

在一些实施方式中，关于上述以需求对象集合中无关联约束的原需求对象及解耦后的原需求对象为模板，建立需求序号共用的新需求对象并为每个新需求对象添加子需求序号标识的步骤，具体可以包括如下处理过程：

将新需求对象的需求序号设置为相应原需求对象的需求序号；

将无关联约束的原需求对象相应的新需求对象的子需求序号设置为固定标识值；

对同一原需求对象解耦后生成的各原需求对象分别对应的各新需求对象，设置从设定标识值开始呈顺序排列的各相应子需求序号。

可以理解，以原需求对象为模板，建立新需求对象并为每个新需求对象增加子需求序号标识。为保持新需求对象模型统一，没有关联约束的需求对象的子需求序号标识设置为固定标识值，例如填1或者其他数值；有关联约束的原需求对象，以该原需求对象为模板按其关联条件要求的关联数量新建多个新需求对象(关联多少即新建多少个)，新建的各新需求对象也添加相应的子需求序号。

新建的各新需求对象的需求序号与原需求对象使用同一个需求序号。需求序号是唯一化的，该需求序号作为原需求对象和新需求对象的映射，在最后一层的优化调度层可通过该需求序号，提取相应原需求对象的关联约束条件作为判断所分配解是否满足用户需求的依据。对应于同一原需求对象解耦后生成的各原需求对象的各新需求对象，其子需求序号的设置方式则可以是：从一个关联对象拆分出的新需求对象的子需求序号从设定标识值(例如1或者其他数值)开始按顺序增加或递减，或者按照其他有序变化的排列顺序的数值编排各新需求对象的子需求序号，只要能够有效区分从一个关联对象拆分出的各新需求对象即可。

具体的，对存在关联约束的需求对象(典型对象如为测轨关联需求对象)进行解关联约束拆分，以关联约束的原需求对象为模板新建多个独立需求对象(例如：由拆分得到的新需求对象)，新需求对象数量基于原需求对象的关联条件要求给出，新需求对象的需求序号保留原需求对象的需求序号(也即需求序号共用)，而子需求序号则例如但不限于可以从1开始，按顺序增加(每增加一个新需求对象其子需求序号增1)。最终，新建的所有新需求对象，与非关联约束的原需求对象对应的、设置了固定子需求序号的新需求对象一起生成新的需求对象集合

在一些实施方式中，上述基于分层优化的卫星测控任务调度方法，还可以包括如下数据准备的步骤：

根据新需求对象集合中需求对象的任务类型和特征标识，将新需求对象集合拆分为多个子需求对象集合；特征标识是指必须连续跟踪标识为是，多个子需求对象集合包括连续跟踪任务需求子集合、单遥测任务需求子集合、一体化测控数传任务需求子集合和测控/测轨任务需求子集合；

根据设备能力对象集合中设备承担的任务及支持的任务类型，将设备能力对象集合拆分为多个设备子集合；多个设备子集合包括只支持单遥测的设备子集合，支持一体化遥测数传、测轨及遥控的设备子集合以及支持测轨与遥控的设备子集合。

具体的，为下一步进行分层调度做数据准备，以新需求对象为元素构建新需求对象集合，根据新需求对象的任务类型和需求的重要特征(此处是指必须连续跟踪标识为是)生成多个子需求对象集合T′＝{{Tcontinue}，{TTM}，{TINT}，{TP，TC}}，分别是：连续跟踪任务需求子集合Tcontinue、单遥测任务需求子集合TTM、一体化测控数传任务需求子集合TINT以及测控/测轨任务需求子集合TP，TC。

对设备能力对象集合R按主要承担的任务、支持的任务类型分为多个设备子集合，即R＝{{RTM}，{RINT,P,TC}，{RP,TC}}，分别表示：只支持单遥测的设备子集合{RTM}，可支持一体化遥测数传、测轨及遥控的设备子集合{RINT,P,TC}，支持测轨与遥控的设备子集合{RP,TC}。

S16，根据新需求对象集合、设备能力对象集合和可见预报集合，依次串行调用设计的分调度层进行资源分层调度，生成分层调度初始解集合；分调度层包括连续跟踪任务调度层、单遥测限定设备调度层、一体化测控数传调度层、测轨/遥控需求调度层和单遥测补全处理调度层。

可以理解，分层调度的基本设计构思是将任务类型相近的需求尽量放在同一调度层，便于应用统一的基于约束满足的调度模型(不同任务类型的调度分层应用的约束满足模型不同)、降低调度处理的复杂度，提高最优可行解搜索效率，同时在保证分调度层的可用设备数量足够的前提下，使先调度的层对后调度的层的影响概率尽量小，从而从总体上提高调度效率。

在本申请的方案的中，设计了6个分调度层，依次为：连续跟踪任务调度层、单遥测限定设备调度层、一体化测控数传调度层、测轨/遥控需求调度层、单遥测补全处理调度层和优化调度层。其中：

连续跟踪任务调度层的输入信息是：连续跟踪需求对象子集合{Tcontinue}，支持测轨与遥控的设备子集合{RP,TC}，可见预报集合V。

单遥测限定设备调度层的输入信息是：单遥测任务需求子集合{TTM}，只支持单遥测的设备子集合{RTM}，可见预报集合V。

一体化测控数传调度层的输入信息是：一体化测控数传任务需求子集合{TINT}，支持一体化遥测数传、测轨及遥控的设备子集合{RINT,P,TC}，可见预报集合V。

测轨/遥控需求调度层的输入信息是：测控/测轨任务需求子集合{TP,TC}，支持一体化遥测数传、测轨及遥控的设备子集合{RINT,P,TC}，支持测轨与遥控的设备子集合{RP,TC}，可见预报集合V。

单遥测补全处理调度层的输入信息包括：单遥测任务需求子集合{TTM}，支持一体化遥测数传、测轨及遥控的设备子集合{RINT,P,TC}，支持测轨与遥控的设备子集合{RP，TC}，可见预报集合V。

优化调度层的输入信息是：一体化测控数传任务需求子集合{TINT}，测控/测轨任务需求子集合{TP,TC}，支持一体化遥测数传、测轨及遥控的设备子集合{RINT,P,TC}，支持测轨与遥控的设备子集合{RP,TC}，可见预报集合V。同时，为提高满足率，该优化调度层会对单遥测(单遥测限定设备调度层+单遥测补全处理调度层)、一体化测控数传调度层、测轨/遥控需求调度层的初始解集合进行二次调整)，各分层的执行顺序按照上述顺序依次串行调度。优化调度层最后调用，以进行调整优化，保证需求的关联约束得到满足并综合优化已分配解集合提高整体满足率。

其中，将单遥测需求分为两个调度层(单遥测限定设备调度层+单遥测补全处理调度层)的目的，是优先在功能较为单一的设备(单遥测设备)上分配弧段，以提高设备有效利用率，减小与一体化测控数传、遥控/测轨需求的多功能设备的冲突。具备一体化遥控数传能力的设备都支持遥控/测轨功能，但反过来支持遥控/测轨功能的设备不一定具备一体化测控数传能力，因此，将一体化测控数传任务需求与测轨/遥控任务需求分为两个调度层，并且一体化测控数传优先调度，可以保证一体化测控数传需求的满足率。

S18，调用设计的优化调度层，根据需求对象集合对分层调度初始解集合进行关联约束重建与优化调度处理，生成分层调度优化解集合；分层调度优化解集合用于指示资源使用申请对应的中高轨卫星资源调度结果。

可以理解，各分调度层调度结束时的初始解添加到总初始解集合(也即分层调度初始解集合)，在优化调度层，即可基于总初始解集合进行优化调度，生成最终的分层调度优化解集合。

上述基于分层优化的卫星测控任务调度方法，通过基于收到的资源使用申请，建立高轨卫星需求统一模型的中高轨卫星资源的三大数据集合，然后对需求对象集合进行预处理和解耦关联约束，生成各调度分层的新需求对象集合，进而根据新需求对象集合、设备能力对象集合和可见预报集合，依次串行调用设计的分调度层进行资源分层调度，生成分层调度初始解集合，最后再调用设计的第六个分调度层(优化调度层)进行关联约束重建与优化调度处理，生成最终的分层调度优化解集合，即可得到资源使用申请对应的中高轨卫星资源调度结果。

采用了统一的中高轨卫星资源需求模型和设备能力模型，在保证整体调度满足率的前提下，以分层调度优化方法使得中高轨卫星资源调度过程可以极大地缩小可行解空间搜索的数量级，提高到最优解的时间效率，降低调度算法计算复杂度，达到了较好的调度满足率和调度效率。与现有技术相比，上述方案能够收集中高轨卫星测运控用户提交的测控资源使用申请，以整体满足率最大为目标，用分层调度优化的方法快速生成中高轨卫星例行测控任务调度结果。

面向航天测控网中高轨卫星的例行测控任务调度需求，本申请的上述方法兼顾整体满足率和调度效率的平衡，在充分利用现有启发式调度方法研究成果基础上提出了分层调度的方法，在最优解选择时综合考虑需求优先级、设备优先级、可选资源的紧张程度和可行解选择的收益和代价，精心选择分调度层的需求对象集合和分调度层的调度顺序，尤其是把单遥测任务需求分为两个调度层处理，既防止单层调度占用过多其它需求的资源，又提高了对有限资源的利用率，首次实现了中高轨卫星资源调度自动化，获得了较高的任务调度满足率，工程意义明显。

在一个实施例中，连续跟踪任务调度层采用连续跟踪任务调度法进行资源调度，单遥测限定设备调度层和单遥测补全处理调度层采用单遥测任务调度法进行资源调度，一体化测控数传调度层和测轨/遥控需求调度层采用局部搜索选优调度法进行资源调度。

可以理解，针对上述5个分调度层，本申请共设计了3种基于约束满足模型的调度方法，分别为：连续跟踪任务调度法、单遥测任务调度法以及局部搜索选优调度法。连续跟踪任务调度法用于实现连续跟踪任务调度层的调度处理。单遥任务调度法用于实现单遥测限定设备调度层和单遥测补全处理调度层的调度处理。局部搜索选优调度法用于实现一体化测控数传调度层以及测轨/遥控需求调度层的调度处理。其中，在分调度层中，连续跟踪任务调度层、一体化测控数传调度层、测轨/遥控需求调度层和单遥测补全处理调度层的可用设备范围没有限制条件，但单遥测限定设备调度层的可用设备有限制条件，其只能在一个限定的设备范围内进行调度，具体限定范围可根据实际的全网资源情况给定。

具体的，连续跟踪任务调度层以连续跟踪任务需求子集合Tcontinue为输入，调用连续跟踪任务调度法(可以算法程序形式存在)，生成连续跟踪任务调度层的初始解集合并添加到分层调度初始解集合。

单遥测限定设备调度层以单遥测任务需求子集合TTM为输入，调用单遥测任务调度法(可以算法程序形式存在)，单遥测限定设备范围根据中高轨卫星实际可用设备情况配置，此处限定为单遥测设备，生成单遥测限定设备调度层的初始解集合并添加到分层调度初始解集合。

一体化测控数传调度层以一体化测控数传任务需求子集合TINT为输入，调用局部搜索选优调度法(可以算法程序形式存在)，生成一体化测控数传调度层的初始解集合并添加到分层调度初始解集合。

测轨/遥控需求调度层以测控/测轨任务需求子集合TP,TC为输入，调用局部搜索选优调度法，生成测轨/遥控需求调度层的初始解集合并添加到分层调度初始解集合。

单遥测补全处理调度层以单遥测任务需求子集合{TTM}，支持一体化遥测数传、测轨及遥控的设备子集合{RINT,P,TC}，支持测轨与遥控的设备子集合{RP，TC}和可见预报集合V为输入，调用单遥测任务调度法，可用设备范围包含所有(单遥测+加多功能)有剩余空闲时段的设备，在单遥测限定设备调度层的初始解集合基础上生成单遥测初始解集合并加入分层调度初始解集合。

分层调度初始解集合中每个解对象的主要信息可包括：用户代号、卫星代号、设备代号、需求序号(来自需求对象的需求序号)、子需求序号(来自需求对象的子需求序号)、跟踪开始时间、跟踪结束时间和任务类型等。

在一个实施例中，如图2所示，连续跟踪任务调度法，可以包括如下调度处理的步骤：

将连续跟踪任务需求子集合中的连续跟踪需求对象按优先级降序排序；

判断连续跟踪需求对象是否遍历完毕；

若是，则结束连续跟踪任务调度；

若否，则载入一个连续跟踪需求对象；

判断已分配计划是否满足最小服务时长需求；

若是，则返回判断连续跟踪需求对象是否遍历完毕的步骤；

若否，则基于支持测轨与遥控的设备子集合载入连续跟踪需求对象的期望设备列表；

基于连续跟踪需求对象时间窗口，根据可见预报集合载入期望设备的可见预报；

构建满足连续跟踪需求对象的可行解空间；

判断可行解对象是否遍历完毕；

若是，则返回判断连续跟踪需求对象是否遍历完毕的步骤；

若否，则载入一个可行解对象；

取跟踪结束时间与载入的可行解对象的跟踪开始时间相接的计划；

基于选取的计划建立跟踪结束时间延伸到可行解对象的跟踪结束时间的新计划对象；

删除选取的计划并将新计划对象加入已分配计划集合；

判断已分配计划是否满足最小服务时长需求；

若是，则返回判断连续跟踪需求对象是否遍历完毕的步骤；

若否，则返回判断可行解对象是否遍历完毕的步骤。

在一个实施例中，如图3所示，单遥测任务调度法，可以包括如下调度处理步骤：

判断单遥测任务需求子集合中需求对象是否遍历完毕；

若判断单遥测任务需求子集合中需求对象未遍历完毕，则执行如下步骤：

载入一个单遥测需求对象；

将单遥测需求对象的期望设备列表载入可用设备列表；

基于时间窗口从可见预报集合中取可用设备的可见预报数据；

构建满足单遥测需求对象的可行解空间；

构建单遥测可行解空间；

返回判断单遥测任务需求子集合中需求对象是否遍历完毕的步骤；

若判断单遥测任务需求子集合中需求对象遍历完毕，则执行如下步骤：

判断需求对象是否处理完毕；

若是，则结束单遥测资源调度；

若否，则载入优先级最高的单遥测需求对象的可行解空间；

判断可行解空间的可用可行解是否为零；

若是，则返回判断需求对象是否处理完毕的步骤；

若否，则载入设备期望值最高的可行解；

判断可行解是否满足需求约束；

若否，则将可行解从当前单遥测需求对象的可行解空间删除并返回判断需求对象是否处理完毕的步骤；

若是，则计算当前单遥测需求对象在可行解分配后的剩余需求时间窗口；

更新单遥测可行解空间并返回判断需求对象是否处理完毕的步骤。

在一个实施例中，如图4所示，局部搜索选优调度法，可以包括如下调度处理步骤：

载入需求对象集合；需求对象集合包括一体化测控数传任务需求子集合和测控/测轨任务需求子集合；

判断需求对象是否遍历完毕；

若需求对象未遍历完毕，则执行如下步骤：

载入一个需求对象；

载入需求对象的可用设备列表；

根据支持一体化遥测数传、测轨及遥控的设备子集合，支持测轨与遥控的设备子集合以及可见预报集合，基于时间窗口和取可用设备的可见预报；

在空闲弧段内以最小服务时长为长度单位，滑动构建满足需求对象的可行解空间；

构建需求对象集合的可行解空间并返回判断需求对象是否遍历完毕的步骤；

若需求对象遍历完毕，则执行如下步骤：

对需求对象的优先级赋值；

判断优先级组是否处理完毕；

若是，则结束局部搜索调度；

若否，则载入一组需求对象的可行解空间集合；

判断载入的组需求是否处理完毕；

若是，则返回判断优先级组是否处理完毕的步骤；

若否，则载入代价最小的需求对象的可行解空间；

载入冲突概率最小的可行解；

判断冲突概率最小的可行解是否满足需求约束；

若否，则将冲突概率最小的可行解从当前需求对象的可行解空间删除，返回判断载入的组需求是否处理完毕的步骤；

若是，则将当前需求对象的调度状态设为满足；

更新需求对象集合的可行解空间，返回判断载入的组需求是否处理完毕的步骤。

在一个实施例中，如图5所示，优化调度层进行关联约束重建与优化调度处理的过程，可以包括如下调度处理步骤：

将需求对象集合中的需求对象按优先级降序排序；

判断所有需求对象是否检查完毕；

若是，则调度结束；

若否，则载入一个需求对象及分层调度初始解集合中相应的计划集合；

判断需求对象是否为关联对象；

若判断需求对象不是关联对象，则执行如下步骤：

判断已分配计划是否达到最小服务时长要求；

若是，则返回判断所有需求对象是否检查完毕的步骤；

若否，则调用中高轨卫星单对象调度方法进行二次调度；

判断调度结果是否达到最小服务时长要求；

若是，则将调度结果加入已分配计划集合；

若否，则返回判断所有需求对象是否检查完毕的步骤；

若判断需求对象是关联对象，则执行如下步骤：

已分配计划满足总服务时长要求时，判断已分配计划是否满足最小弧段数量要求；

若是，则返回判断所有需求对象是否检查完毕的步骤；

若否或已分配计划不满足总服务时长要求，则载入不满足约束的子需求对象；

调用中高轨卫星单对象调度方法进行二次调度；

将调度结果加入已分配计划集合；

判断子需求对象是否有已分配计划；

若否，则返回判断所有需求对象是否检查完毕的步骤；

若是，则从计划集合中删除对应已分配计划，返回判断所有需求对象是否检查完毕的步骤。

可以理解，基于上述步骤S16中生成的分层调度初始解集合，并回溯到原需求对象集合T中的关联约束要求(各分调度层生成的解的属性中包括需求序号和子需求序号)，根据原需求对象的关联约束重建分层调度初始解集合中对象的关联约束，对不满足关联约束的初始解进行二次调度(也即优化调度处理)，分配满足关联约束的解并代替分层调度初始解集合中的相应初始解，完成关联约束重建与优化调度处理后即生成分层调度优化解集合。

在一个实施例中，如图6所示，上述的基于分层优化的卫星测控任务调度方法，关于步骤S12之前，还可以包括步骤S11：

S11，获取卫星测运控用户发送的资源使用申请。

可以理解，调度系统可以在在线接收卫星测运控用户发送的资源使用申请，然后基于卫星测运控用户发送的资源使用申请，建立中高轨卫星统一模型的需求对象集合等。一个典型卫星si在一个计划周期内(例如7天)会有多个申请(对应形成多个申请文件)，基于每个申请文件建立一个独立的需求对象，基于原申请序号和用户信息为需求对象添加一个在中高轨卫星调度系统中具有唯一性的需求序号，每个需求对象在一个时间窗口或者多个时间窗口申请资源，每个时间窗口有对应的最小服务时长要求。

此外，关于步骤S18之后，还可以包括步骤S20和S22：

S20，根据分层调度优化解集合生成资源使用申请对应的申请结果；

S22，将申请结果发送至卫星测运控用户端；申请结果用于指示中高轨卫星资源调度结果。

可以理解，卫星测运控用户端也即申请用户用于向资源调度系统发送资源使用申请的终端设备。分层调度优化解集合作为本次中高轨卫星例行测控任务调度的最终的解集合，依据该解集合生成申请结果，然后使用约定格式的申请结果文件发送给申请用户，告知申请用户申请满足的情况，对申请用户的每个申请给出是否满足的答复，对满足的结果还包含分配的设备以及该设备工作时间窗口，从而向申请用户直观指示本次中高轨卫星例行测控任务调度的结果。

在一个实施例中，为了更直观且全面地说明上述基于分层优化的卫星测控任务调度方法，下面是上述方法的一种可选的仿真应用示例：

仿真环境建立大规模中高轨卫星调度场景，包含60颗中高轨卫星的例行测控任务和可用设备数量30套，共建立的中高轨卫星需求对象集合包含独立对象423个，解耦关联约束后新建需求对象集合包含独立申请对象1161个，共申请设备时长需求为3366小时，其中单遥测申请时长2220小时。表1给出了中高轨卫星申请资源时长统计情况，表2给出了可用中高轨卫星可用设备的能力统计情况，表3给出了测试环境参数配置。

表1

表2

表3

基于上述基于分层优化的卫星测控任务调度方法开展上述需求调度后，表4给出了调度结果：共分配弧段1309个，分配弧段时长3326小时，设备切换占用时长142小时，其中单遥测分配时长2215小时。表5是单遥测任务在单功能设备和多功能设备的分布情况，在15套单遥测设备分布占比达到97.7％，平均每台单遥测设备的利用时长达到145小时。按表3给出的测试环境配置，基于本申请设计的调度方法，调度耗时约10分钟，在可用设备中度紧张的条件下整体调度成功率达到98.8％(不满足情况主要集中在一体化遥测数传需求，不满足原因是可用设备数量不足)。本申请的上述方法以仿真实例验证了在航天测控设备地域布站约束的情况下，首次实现了中高轨卫星例行测控任务的自动化调度，达到了较高的调度满足率。

表4

申请类型 申请时长(小时) 分配时长(小时) 满足率 连续跟踪 504 504 100％ 单遥测 1884 1879 99.7％ 一体化测控数传 417 382 91.7％ 遥控/测轨 560.58 560.58 100％

表5

单功能设备 多功能设备 数量(套) 15 10 跟踪总时长(小时) 2170 50 跟踪总时长百分比 97.7％ 2.3％ 单套设备平均时长(小时) 144.68 5.03

应该理解的是，虽然图1-图6流程图中的各个步骤按照箭头的指示依次显示，但是这些步骤并不是必然按照箭头指示的顺序依次执行。除非本文中有明确的说明，这些步骤的执行并没有严格的顺序限制，这些步骤可以以其它的顺序执行。而且图1-图6的至少一部分步骤可以包括多个子步骤或者多个阶段，这些子步骤或者阶段并不必然是在同一时刻执行完成，而是可以在不同的时刻执行，这些子步骤或者阶段的执行顺序也不必然是依次进行，而是可以与其它步骤或者其它步骤的子步骤或者阶段的至少一部分轮流或者交替地执行。

请参阅图7，在一个实施例中，还提供了一种基于分层优化的卫星测控任务调度装置100，包括集合建立模块11、集合分层模块13、分层调度模块15和优化调度模块17。其中，集合建立模块11用于基于收到的资源使用申请，建立统一模型的中高轨卫星资源需求对象集合、设备能力对象集合和卫星对设备的可见预报集合。集合分层模块13用于对需求对象集合进行预处理和解耦关联约束，生成各调度分层的新需求对象集合。分层调度模块15用于根据新需求对象集合、设备能力对象集合和可见预报集合，依次串行调用设计的分调度层进行资源分层调度，生成分层调度初始解集合；分调度层包括连续跟踪任务调度层、单遥测限定设备调度层、一体化测控数传调度层、测轨/遥控需求调度层和单遥测补全处理调度层。优化调度模块17用于调用设计的优化调度层，根据需求对象集合对分层调度初始解集合进行关联约束重建与优化调度处理，生成分层调度优化解集合；分层调度优化解集合用于指示资源使用申请对应的中高轨卫星资源调度结果。

上述基于分层优化的卫星测控任务调度装置100，通过各模块的协作，基于收到的资源使用申请，建立高轨卫星需求统一模型的中高轨卫星资源的三大数据集合，然后对需求对象集合进行预处理和解耦关联约束，生成各调度分层的新需求对象集合，进而根据新需求对象集合、设备能力对象集合和可见预报集合，依次串行调用设计的分调度层进行资源分层调度，生成分层调度初始解集合，最后再调用设计的第六个分调度层(优化调度层)进行关联约束重建与优化调度处理，生成最终的分层调度优化解集合，即可得到资源使用申请对应的中高轨卫星资源调度结果。

采用了统一的中高轨卫星资源需求模型和设备能力模型，在保证整体调度满足率的前提下，以分层调度优化方法使得中高轨卫星资源调度过程可以极大地缩小可行解空间搜索的数量级，提高到最优解的时间效率，降低调度算法计算复杂度，达到了较好的调度满足率和调度效率。与现有技术相比，上述方案能够收集中高轨卫星测运控用户提交的测控资源使用申请，以整体满足率最大为目标，用分层调度优化的方法快速生成中高轨卫星例行测控任务调度结果。

面向航天测控网中高轨卫星的例行测控任务调度需求，本申请的上述方法兼顾整体满足率和调度效率的平衡，在充分利用现有启发式调度方法研究成果基础上提出了分层调度的方法，在最优解选择时综合考虑需求优先级、设备优先级、可选资源的紧张程度和可行解选择的收益和代价，精心选择分调度层的需求对象集合和分调度层的调度顺序，尤其是把单遥测任务需求分为两个调度层处理，既防止单层调度占用过多其它需求的资源，又提高了对有限资源的利用率，首次实现了中高轨卫星资源调度自动化，获得了较高的任务调度满足率，工程意义明显。

关于基于分层优化的卫星测控任务调度装置100的具体限定，可以参见上文中基于分层优化的卫星测控任务调度方法的相应限定，在此不再赘述。上述基于分层优化的卫星测控任务调度装置100中的各个模块可全部或部分通过软件、硬件及其组合来实现。上述各模块可以硬件形式内嵌于或独立于具体数据处理功能的设备中，也可以软件形式存储于前述设备的存储器中，以便于处理器调用执行以上各个模块对应的操作，前述设备可以是但不限于本领域的各型计算机设备或系统。

又一方面，还提供一种计算机设备，包括存储器和处理器，存储器存储有计算机程序，处理器执行计算机程序时可以实现以下步骤：基于收到的资源使用申请，建立统一模型的中高轨卫星资源需求对象集合、设备能力对象集合和卫星对设备的可见预报集合；对需求对象集合进行预处理和解耦关联约束，生成各调度分层的新需求对象集合；根据新需求对象集合、设备能力对象集合和可见预报集合，依次串行调用设计的分调度层进行资源分层调度，生成分层调度初始解集合；分调度层包括连续跟踪任务调度层、单遥测限定设备调度层、一体化测控数传调度层、测轨/遥控需求调度层和单遥测补全处理调度层；调用设计的优化调度层，根据需求对象集合对分层调度初始解集合进行关联约束重建与优化调度处理，生成分层调度优化解集合；分层调度优化解集合用于指示资源使用申请对应的中高轨卫星资源调度结果。

在一个实施例中，处理器执行计算机程序时还可以实现上述基于分层优化的卫星测控任务调度方法各实施例中增加的步骤或者子步骤。

再一方面，还提供一种计算机可读存储介质，其上存储有计算机程序，计算机程序被处理器执行时实现以下步骤：基于收到的资源使用申请，建立统一模型的中高轨卫星资源需求对象集合、设备能力对象集合和卫星对设备的可见预报集合；对需求对象集合进行预处理和解耦关联约束，生成各调度分层的新需求对象集合；根据新需求对象集合、设备能力对象集合和可见预报集合，依次串行调用设计的分调度层进行资源分层调度，生成分层调度初始解集合；分调度层包括连续跟踪任务调度层、单遥测限定设备调度层、一体化测控数传调度层、测轨/遥控需求调度层和单遥测补全处理调度层；调用设计的优化调度层，根据需求对象集合对分层调度初始解集合进行关联约束重建与优化调度处理，生成分层调度优化解集合；分层调度优化解集合用于指示资源使用申请对应的中高轨卫星资源调度结果。

在一个实施例中，计算机程序被处理器执行时，还可以实现上述基于分层优化的卫星测控任务调度方法各实施例中增加的步骤或者子步骤。

本领域普通技术人员可以理解实现上述实施例方法中的全部或部分流程，是可以通过计算机程序来指令相关的硬件来完成的，计算机程序可存储于一非易失性计算机可读取存储介质中，该计算机程序在执行时，可包括如上述各方法的实施例的流程。其中，本申请所提供的各实施例中所使用的对存储器、存储、数据库或其它介质的任何引用，均可包括非易失性和/或易失性存储器。非易失性存储器可包括只读存储器(ROM)、可编程ROM(PROM)、电可编程ROM(EPROM)、电可擦除可编程ROM(EEPROM)或闪存。易失性存储器可包括随机存取存储器(RAM)或者外部高速缓冲存储器。作为说明而非局限，RAM以多种形式可得，诸如静态RAM(SRAM)、动态RAM(DRAM)、同步DRAM(SDRAM)、双数据率SDRAM(DDRSDRAM)、增强型SDRAM(ESDRAM)、同步链路(Synchlink)DRAM(SLDRAM)、存储器总线式动态随机存储器(Rambus DRAM，简称RDRAM)以及接口动态随机存储器(DRDRAM)等。

以上实施例的各技术特征可以进行任意的组合，为使描述简洁，未对上述实施例中的各个技术特征所有可能的组合都进行描述，然而，只要这些技术特征的组合不存在矛盾，都应当认为是本说明书记载的范围。

以上实施例仅表达了本申请的几种实施方式，其描述较为具体和详细，但并不能因此而理解为对发明专利范围的限制。应当指出的是，对于本领域的普通技术人员来说，在不脱离本申请构思的前提下，还可做出若干变形和改进，都属于本申请保护范围。因此本申请专利的保护范围应以所附权利要求为准。