一种基于先验信息的中高轨卫星遥测任务资源调度方法*

王官龙,宋建国,陈慧伟,范志勇,侯光华

(西安卫星测控中心,西安 710043)

0 引 言

中高轨卫星轨道类型差异大,可见时间窗口长,使得中高轨卫星在遥测、遥控、测轨、数传等任务类型需要的设备类型、跟踪时长存在明显的差异,同时多个弧段、不同任务类型之间还有关联约束要求,再叠加上设备支持能力存在差异,导致中高轨卫星资源调度问题求解复杂度相比低轨卫星呈指数级上升。中高轨卫星所需任务需求中,遥测数据接收任务占用设备跟踪时长最多,通常需要多套设备通过接力跟踪完成,单个弧段的跟踪时长和切换时刻自由度较大,且跟踪时间窗口没有确定的时刻,进一步增加了调度计算的自由度。中高轨卫星因可见时间长造成相同时段有多个设备可选,使得多个卫星抢同一点位设备的冲突更为明显。以上这些因素都增加了中高轨卫星遥测任务调度的复杂性。

关于资源调度算法研究,以往研究以低轨卫星资源调度较多[1-4],以美国空军卫星控制网的调度系统研究最有参考价值,其中遗传算法、启发式算法(Spider Wasp Optimizer,SWO)、随机本地搜索算法(Random Local Search,RLS)的性能较好,在应对超量需求的调度问题(需处理的调度申请数量超过资源最大满足数)时,启发式算法在保持较好性能时算法实现复杂度度较低[1,5]。但已有的调度算法基本只针对固定弧长的调度模型,并不能较好地解决中高轨卫星遥测任务调度时中面临的设备时长和切换时刻都存在自由度的资源调度难题。

本文以中高轨卫星遥测任务需求整体满足率最大和算法复杂度低为设计目标,基于从人工安排中高轨遥测任务测控工作计划的经验数据中提取的先验信息,提出一种基于先验信息的中高轨卫星遥测任务资源调度算法。结合我国测控站布站的实际情况,从中高轨卫星任务对资源的需求开始,建立中高轨卫星的遥测任务需求模型,在给定的可用设备范围内,研究中高轨卫星遥测任务资源调度算法,配合优化迭代,使该算法能兼顾较好的调度效率和调度质量。

1 调度需求模型

通常资源调度问题模型可用以下要素描述:一组卫星及其需求的任务类型、时间窗口、约束条件,一组测控资源及设备能力和可见预报,以及调度优化目标。在需求侧一个典型的中高轨卫星资源需求可以模型化为(S,C,L,RW),其中,S表示卫星代号,C表示该卫星需求的任务类型(遥测、遥控、测轨、数传或其组合),L表示卫星S需求的最小服务时长,R表示该卫星的可用资源(支持卫星需求任务类型,上标W表示卫星S对资源R的可见窗口,包括一个开始时间和一个结束时间)。卫星S在资源R的时间窗口内,满足最小服务时长L的弧段可能有K个(K的数量取决于当前可见窗口长度包含最小服务时长的数量),将其中每个满足的弧段定义为一个可行解f=(S,C,L,RW)k,0≤k

中高轨卫星遥测任务可行解模型如图1所示。假定有3颗中高轨卫星S1、S2、S3(S1代表MEO类卫星典型遥测接收任务需求,S2和S3代表IGSO类卫星典型遥测接收任务需求),卫星的遥测跟踪需求窗口如图中竖实线所示,虚线框表示R1、R2、R3、R4设备在需求窗口内的可用时长。多个卫星对同一个设备存在竞争,如设备R1对卫星S1、S2和S3都是可用资源,依据人工制定遥测跟踪计划的经验,R1最好的分配策略是优先分配给S2或S3卫星,然后S1和S2(或S3,取决于R1优先用于S2或S3)卫星继续在R2、R3和R4设备上进行拼接来满足需求,而且每个分配弧段的长度不是一个唯一的固定值。

图1 中高轨卫星遥测任务需求的可行解空间模型

2 调度算法设计

2.1 提取先验信息

基于中高轨卫星资源调度问题的复杂性,中高轨卫星遥测数据接收任务资源调度往往采用人工制定计划的方式,由此积累了大量历史计划数据,从 这些历史计划数据中提取出人工制定中高轨卫星遥测数据接收计划的有价值信息,作为中高轨卫星遥测任务资源调度中优先分配设备的初始先验信息。IGSO卫星轨道重复周期为24 h,其遥测数据接收的需求具有明显的周期特征,因此在特定时间段的可见设备也有一定的周期特征。基于以上这些重要的先验信息,对某个卫星的遥测任务需求在调度算法中按先验信息给出的设备使用优先级进行分配,多颗卫星在分配到同一套设备时按照优先级顺序竞争使用,可在工程实践中达到较好的调度效果和降低算法复杂度的平衡。

2.2 资源调度算法流程设计

基于提取的先验信息为每个卫星的遥测任务需求配置可用设备优先级,在资源调度时按照配置的设备优先级进行资源调度。中高轨卫星遥测任务初始先验信息如表1所示,表中设备代号后括号中数值为该设备用于当前卫星遥测数据接收任务的优先使用顺序,优先级数值越小,代表优先级越高。基于给出的设备使用优先级使用信息,同步设计了相应的资源调度算法流程,如图2所示。

表1 中高轨卫星遥测任务先验信息

图2 中高轨卫星遥测任务资源调度算法流程

Step1 设每一个需求窗口为一个目标区间W,该窗口区间的可行解集合为∑Qn,t,构建所有卫星的可行解空间∑∑Qn,t。

Step2 计算各目标窗口区间的资源覆盖率,即计算该窗口的可行解集合∑Qn,t对窗口区间W的覆盖性,方法是将n个可行解与窗口W的时长比值相加,即为该目标窗口的覆盖率P。

Step3 选取覆盖率P最小的目标区间W,即从资源满足率最小的目标窗口开始,使冲突资源优先分配给可用资源最少的目标。

Step4 在选定的目标区间W,计算其每一个可行解Qn,t在解空间∑∑Qn,t中的有衔接和冲突概率Pc,计算该可行解与解空间所有弧段重叠时间,从中选出优先级最高的可行解。

Step5 更新目标区间W可行解集合,调整可行解集合∑Qn,t中与当前选择弧段时间重叠的弧段开始或结束时间,即逐步缩小目标区间W的长度,直到目标区间W小于等于零时,将该区间的所有剩余可行解全部清除。

Step6 更新其他目标窗口的可行解集合∑Qn,t,即调整该目标区间的可行解集合,消除与当前选择弧段设备冲突弧段的开始和结束时间。

Step7 重新计算各目标区间的资源覆盖率,回到Step 2,从中选出下一个优选弧段。

对按一定优先级和顺序调度处理后,仍有冲突而未分配的需求,可在已制定的无冲突计划基础上使用窗口滑动、设备交换、需求变更[6-8]等方式进行优化处理,完成最终计划的制定。

中高轨卫星可见时间窗口较长,各种任务的需求区间时长小于可见窗口长度,需求区间可在可见窗口内进行较大范围的滑动,具有可移动性。单遥测类任务的需求区间虽然不能滑动,但中高轨卫星因轨道高度高,同一需求区间可能有多套设备可见,可将单遥测类计划交换到其他设备。通过对选定的目标设备时间区间内已分配计划的滑动、交换,将冲突的任务插入。图3所示为当前占用资源R1的任务队列S1,S2,S3…按任务开始时间顺序排列。假设选定在弧段S2_R1和S3_R1之间插入冲突弧段S5_R1,在S2_R1和S3_R1之间的空闲时长不满足弧段S5_R1的需求区间时长时,考虑将S2_R1及其之前的弧段向前、S3_R1及其之后的弧段向后滑动,或者交换到其他设备。

图3 回溯算法处理示意

中高轨卫星遥测任务调度回溯算法基于以下规则实现。

1)冲突任务最大可滑动规则

弧段S2_R1最大前向可滑动时长,同时受S2_R1及其之前所有受影响的弧段最大可滑动时长约束。不仅要考虑S2_R1可见预报窗口前沿(S2_R1可见预报前沿S2_BV),还要考虑S2_R1之前任务S1_R1等的可见预报窗口前沿(S1_R1可见预报前沿S1_BV)约束(S2_R1向前滑动到S1_R1后沿的时长不足以插入冲突弧段S5_R1前沿,还需要S1_R1继续向前滑动直到可插入弧段S5_R1的前沿)。同理,弧段S3_R1最大后向可滑动时长,同时受S3_R1及其之后所有受影响的弧段最大可滑动时长约束。

2)可交换任务规则

对最大可滑动策略不满足弧段,或者不能滑动的弧段,可继续尝试将其交换到同需求区间的其他设备。首先确定可交换集和∑Qt。可交换任务Qt的确定应符合以下要求:Qt是已安排的任务计划;Qt不是特殊性质的任务(指定设备)。

将任务交换到Qt后,如果仍不能满足插入弧段的需求区间,对下一个冲突弧段继续执行最大可滑动规则或者可交换规则。例如S3_R1是单遥测弧段,不可滑动,但可在需求区间不变的前提下将其交换到设备R2(S3_R2)。

3)回溯结束规则

处理到可调整出满足需求区间的空闲时段时,本次回溯处理结束。回溯调度处理,直到碰到已达可滑动极限或者不可交换的任务,该选定资源的回溯处理结束。如果当前资源的回溯处理不能满足需求,则转到下一个选定资源进行回溯处理,直到找出可调整的资源或者全部可选资源已回溯处理完。

4)需求降低规则

对回溯处理仍不能满足需求的任务,最后可考虑进行降低需求处理。例如一体化遥测需求的最短服务时长是4 h,在现有设备上已经找不到符合需求的空闲时段时,可考虑将不满足最小服务时长但空闲的时段继续进行分配,以保证满足率最大的目标。

3 软件实例分析

使用本文设计的基于先验信息的中高轨卫星资源调度算法,在一个时间周期(7天)内,卫星任务需求如表2所示,单遥测申请时长2 220.56 h,可用设备情况如表3所示,测试环境配置如表4所示,中高轨卫星资源资源分配情况如表5所示,计划分布情况如表6所示。表3中,12套设备除支持遥测功能外,还同时支持测控数传一体化、遥控测轨;15套支持遥控、测轨功能的设备包括支持测控数传一体化的5套设备和支持C频段的3套设备。

表2 中高轨卫星资源需求情况

表3 中高轨卫星调度可用设备能力情况

表4 测试环境参数配置

表5 中高轨卫星资源分配情况

表6 中高轨卫星单遥测计划在设备分布情况

4 结束语

本文从建立中高轨卫星资源使用需求模型出发,以整体满足率最高为目标,基于有限的可用设备时间、支持的功能,提取人工安排中高轨卫星遥测接收计划的有益信息作为先验信息,为中高轨卫星遥测单收任务可行解赋予设备使用优先级,作为中高轨卫星遥测接收资源调度的基本依据,并开发相应软件进行仿真分析,单遥测申请满足率超过99.7%,单遥测任务在15套单遥测设备分布占比达到97.7%,平均每台单遥测设备的利用时长达到144.68 h,设备负荷率达到86.11%,实现了较好的调度效益。

本文是对中高轨卫星遥测需求调度算法的一个有益工程性尝试,但由于算法只研究了中高轨卫星调度策略,较多考虑工程实现和降低计算量,回溯调整处理未进行多重调度回溯,没有达到最优解。后续将提出更加合理的中高轨卫星资源调度模型,为我国航天器一体化调度算法研究提供参考。