中继卫星单址链路调度模型与算法研究.pdf

中国空间科学技术2007年4月

52CHINESESPACESCIENCEANDTECHNOLOGY第2期

中继卫星单址链路调度模型与算法研究

陈英武方炎申顾中舜
(国防科学技术大学,长沙410073)

摘要中继卫星的任务规划与调度是空间资源管理的重要内容之一,目的在于为中继
卫星系统的任务计划编制提供科学合理的决策手段与依据。中继卫星单址链路调度问题的
重要特点在于,中继卫星与用户航天器之间并非时时可见,因此通信任务存在可见时间窗
口约束。只有在可见时间窗口内,通信任务才可能执行并完成。在进行合理假设的基础
上,建立中继卫星单址链路调度问题的约束规划模型。对基本遗传算法进行改进,提出了
基于有效基因路径表示的改进遗传算法。应用结果表明,基于约束规划理论建立中继卫星
单址链路调度模型并采用基于有效基因路径表示的遗传算法求解是合理的。
关键词遗传算法调度约束规划跟踪与数据中继卫星

1引言

跟踪与数据中继卫星系统(TDRSS,TrackingandDataRelaySatelliteSystem)是为中、低轨道
的航天器与航天器之间、航天器与地面站之间提供数据中继、连续跟踪与轨道测控服务的系统[1]。
中继卫星系统通常包括中继卫星(TDRS,TrackingandDataRelaySatellite)、用户航天器与地面站
三个部分。
中继卫星系统的应用主要集中在用户航天器与中继卫星之间进行数据传输时,如何根据给定任
务集做出有效规划,科学合理的分配中继卫星系统资源,并在资源冲突时进行优化调度,以完成尽
可能多的任务。目前,国内外关于中继卫星系统的应用研究大多注重于中继卫星系统的链路分析,
主要是中继卫星与用户航天器之间、不同的中继卫星之间的通信链路研究,包括天线的捕获跟踪与
伪随机码的捕获,采用的方法多为模拟仿真方法。关于中继卫星调度问题的模型与算法方面的研
究,可参见文献[2]、[3]。
中继卫星单址链路调度问题可以看作具有时间窗口约束的单机调度问题。目前,关于具有时间
窗口约束的单机调度问题的研究主要包括:
1)所有任务具有公共的时间窗口约束,表现形式是所有任务具有公共交货期[4-6];
2)每个任务具有不同的时间窗口约束,表现形式是每个任务具有自己的交货期,并且每个任
务具有的可见时间窗口数量有且仅有一个[7]。
中继卫星单址链路调度问题的重要特点在于任务安排调度时具有可见时间窗口约束,并且在一
定的调度时间段内时间窗口的数量往往具有多个。本文根据中继卫星系统及其应用的特点,建立了
中继卫星单址链路调度问题的约束规划模型,并提出了基于有效基因路径表示的遗传算法。

收稿日期:2006-03-23。收修改稿日期:2006-06-16
2007年4月中国空间科学技术53

2中继卫星单址链路调度问题的特点

对于中继卫星系统的某一单址链路(如S波段单址链路),中继卫星与用户航天器之间并非时时
可见,而是具有时间窗口限制,即中继卫星与用户航天器之间的通

信任务在可见时间窗口内才能进行,如图1所示。STWi表示时间
窗口的开始时刻,ETWi表示时间窗口的结束时刻,di表示通信任
务ji的持续时间。
图1通信任务的时间窗口约束
中继卫星单址链路调度问题中,如果通信任务安排调度过程中
不能被中断(非抢占式调度),并且某个时间窗口长度小于通信任务的执行时间,则时间条件不满
足,通信任务不能在这个时间窗口内安排调度,应考虑其他的时间窗口(见图2)。

图2时间窗口长度小于通信任务的执行时间

1
图2中,|TWi|表示通信任务ji的时间窗口数量,STWi表示通信任务ji的第1个时间窗口的
1|TW|
开始时刻,ETWi表示通信任务ji的第1个时间窗口的结束时刻,STWii表示通信任务ji的
|TW|
第|TWi|个时间窗口的开始时刻,ETWii表示通信任务ji的第|TWi|个时间窗口的结束时刻。
中继卫星单址链路调度问题具有以下特点:
1)中继卫星与用户航天器之间具有可见时间窗口约束,因此通信任务往往具有时间窗口约束,
这是中继卫星单址链路调度问题的一个重要特点。
2)对于中继卫星与用户航天器之间的某一单址链路,同一时间最多只能有一个通信任务由该
链路完成。因此,任务与任务之间不能并行执行,只能根据任务的优先级与通信时间按一定的先后
顺序进行优化排序。
3)对于中继卫星单址链路调度,不能采用一般的线性规划方法建立调度模型,可以考虑采用
人工智能中的约束规划方法建立调度模型。

3中继卫星单址链路调度问题的约束规划模型

中继卫星单址链路调度问题可以看作一类约束满足问题,使用人工智能中的约束规划技术进行
求解。约束满足问题是计算机科学和人工智能研究的核心问题之一。现实生活中的许多组合、调度
优化问题都可以描述为约束满足问题。