《中继卫星系统的多星多天线动态调度方法》由会员分享，可在线阅读，更多相关《中继卫星系统的多星多天线动态调度方法（7页珍藏版）》请在金锄头文库上搜索。
1、 4 9 2 清 华 大 学 学 报 ( 自 然 科 学 版) 度 。文 9 提出一种任务调度框 架，将 中继卫星的 任务进一步分解为持续时间更短的子任务集合 ，但 仅针对单个空间目标的可分解任务调度 。上述预约 式任务调度的研究均没有考虑空间任务的容忍延时 能力 ， 且主要集中在 2 个方面 ：1 )从空间任务本身 出发，考察任务 内容的可分解性 、 相关性和冲突特 性 ， 寻求任务 调度的最大收益 ；2 )从 时间特性 出 发 ，问题被归结为任务冲突检测 ， 最终转变成优先 级判决问题。此外 ，文 5 假设空间任务之 间相互 独 立 ，建立 了一种 并机 调 度模 型 ， 但 忽 略 了单
2、 址 接 入 ( s i n g l e a c c e s s ，S A) 天 线 和 多 址 接 人 ( mu l t i p l e a c c e s s ， MA) 天线 之 间的差异 。 针对 上述 问题 ，本文 构建 了中继卫 星系 统 的多 星多天线服务模型 ， 并提出了一种动态的空间任务 调度 方法 ， 仿 真试 验表 明 ： 该 方 法 能够 有 效提 升 中 继卫星系统的空间任务完成能力 ， 更好发挥多星多 天线资源效能。 1 中继卫星系统服务建模 中继卫 星搭 载 有 S A 和 MA 这 2种 天线 。S A 天线是机械转动的，天线转动时间与转动角度成正 比， 转动所
3、需时间为分钟级别_ 1 。MA天线采用数 字波束成形技术 ， MA天线波束指向的调整时间是 常量 ， 调整 所需 时 间小 于 1 S 。此 外 ， S A 天 线 的 传输速率大于等于 MA 天线，因此对于 同一任务 J o b 采用 S A天线 的处理时间小于等于采用 MA天 线 的 ，即有 ： s A d 假设当前任务集合 J一 J o b ， J o b z ， J o b ， 有 M 个相互 独立 的中继卫 星服 务链 路 。 J o b 的 时 间 窗 口为 t W f ： ， b 1 ， 其中a 和 b 分别是 J o b 的最 早起始 时间和最 晚终 止 时间 ， 且 在 t
4、w 内 J o b 有 个链 路可 以提供 服务 ， 则可 服务链 路集合 NP 可 以 表示 为 N P M 一 M k一 1 ， 2 ， ， ) ， 链路 M 独立处理任务 J o b 的持续时间为d 。 此 外 ，还需 定义 以下几 个变 量 ： 1 ) 3 2 为任务 序列 化变 量 ， 如 果 在 上 J o b 被调 度在 J o b 之后 则 一 1，否则 z 矾 一 0。该 变量满足以下约束条件 ： 班 1 JJ J O bl M NP Mj 2 ) 为服 务链 路标记 变量 ， 如果调 度 M 服务 J o b 则 y 一 1， 否则 y 一 0。该变量满足以下约 束 条件
5、： 1 M NP M 3 ) s 为天 线准 备 时 间变 量 ， 表 示 M 由 J o b 切换至 J o b 所属天线需要的准备时间， 需要满足以 下约 束条件 ： 矾 0 4 ) 为链路空闲时问变量， 表示 从 J o b 结 束到 J o b i 开始的空闲时间， 需要满足以下约束条件 ： 叫 0 5 ) t 为任 务 调 度开 始 时 间变 量 ，表 示 J o b 在 M 上 的调度 开始 时间 。 中继卫星系统任务调度问题被建模成如下多星 多天 线服 务模 型 ： 1 3 2ax ， ( 1 ) J八 J o b NP s t z 1 ； ( 2 ) J 八 J o b Mk
6、N P M1 z 一 Y ( 3 ) J E 八 J o b N P M J A E N P M J z 一0 ； ( 4 ) Jf J o b i E NP MJ i E 八 J o b j ENPM a i ya *， V E ，； ( 5 ) M NP M ( 一7O 一d ) b ； ( 6 ) E NP M ( 叫 一 ) 0 ( 7 ) M NP Mj 目标 函数式 ( 1 ) 的 物理 含 义 是最 大 化 中继 卫 星 系统的任务调度收益 ， 其中 C O 是 J o b 的收益权重 。 约束式 ( 2 ) 用 于保 证 任 一任 务 只 能服 务 一 次 ，避 免 任务 重复
7、 服务 ； 约束 式 ( 3 ) 用于保证任一任务 只能被 一个 中继 卫星链 路 服务 ， 避免 重复 服务 ； 约 束式 ( 4 ) 用于保证在任一服务链路 的调度序列 中，任意任务 的前者 和后者 均 由该 链 路 提 供 服务 ；约 束 式 ( 5 ) 和 ( 6 ) 分别用于保证任一任务的服务开始时间必须晚于 其 时间窗 口的起 始 时 间，服 务结 束 时 间必 须早 于 其 时间窗口的终止时间 ； 最后，约束式( 7 ) 用于保证相 邻 2 个任务之间的等待时间要大于天线准备时间。 2 空间任务动态调度方法 2 1 拓扑 动态变 化 的利用 依据空间网络拓扑结构的动态变化 ， 在
8、时间上 对调度过程进行细分 ，减小每次调度 的规划时长和 任务数量 ， 进而达到动态的空间任务调度效果 。 假设某一 中继卫星在时刻 i 存在 个可视 目 标 ，当时 刻 可视 目标 发生 变 化 ， 则 定 义 时刻 i 的 规 划时 隙为 林鹏 ，等 中继卫星系统的多星多天线动态调度方法 4 9 3 S 一 ， J一1 ， i J ， U l “ ， 令 T为最小的规划时隙门限，当某一规划时隙 小于该门限时， 需与后一个规划时隙进行合并 ， 则有： f ， J 一1 ， J i A T ， U i U j ； l E i ， k 一1 ， 一i A T k i ， 地U j 在时 间上 依
9、 次做 递进 处理 ，可 以将 整个 时 间轴 细分 为多 个持 续 时间较 短 的规划 时 隙。 2 2调 度方 法 基于上述拓扑结构 的动态变化特征 ，提 出了一种 动态的空间任务调度方法， 具体实现步骤如图 1 所示。 厂 是 l 霾 I l 堕 笙 垒 I t 调度是否结束 空 间任务 的 可服务性分析 多星多天线服务模型 资源 分配算法 输 出空间任务 调度方案 厂 图 1 空 间任 务动 态 调 度方 法流 程 图 已知空间任务调度 的时间范围为 I T ， T o ， 对 个 中继 卫 星分别 划 分规 划 时 隙 ， 第 个 中继卫 星 划 分 出 的规 划 时 隙 依 次 为
10、 S ， S ， ， S l ， 。在 具 有 最早 起 始 时 间 的规 划 时 隙 S 内进行 中继 卫 星 系 统 资源 分配 ，此时有 ： S 一 mi n ( S i )， J一 1 ， 2， ， r 选 取 当前规 划 时隙 S 内可服务 任务 的集 合 ， 其 中任 一 J o b 的 t w 需 要满 足 ： f f t w n S f f ， 即 t w 与 S 的交集需 要 大于 d 。结 合各 个 中继卫 星的覆盖范围，逐个对任务进行可服务性分析 ， 得 到 J o b 的 NP M 和任务的容忍延时约束集合 D 一 D f k一 1 ， 2 ， m )。其 中， J o
11、 b 在第 k个链路 上 的容忍延 时上界 为 D 一 I l t w n S I I d 在 当前规划时隙 s 内，结合 中继卫星 2种天 线资源差异 ， 建立 中继卫星系统的多星多天线服务 模 型 。 最 后 ，求解 中继卫 星 系统 的最 优资 源分 配结 果 即空 间任务 的调 度方 案 。 3 中继 卫星 系统资源分配算法 3 1 算法流程 为 了充 分 利用 空 间任 务 的容忍 延 时特性 ，提 出 了一种基于种群联合进化 的中继卫星系统资源分配 算法 ， 算法实现流程如图 2所示 。 否 否 否 开始 选取规划时隙 内需 服务任务 的集合 任务优先级递归 是否结束 是 l 可服
12、务链路递归 是否结束 是 l 独立构造多个解 竺 束 是 I 随机构造初始解 ， 求解当前最优解 拈 求解当前最优解集合 目 ， 1 ， 2 ， 输出 的当前最优解集合 ， 1 2 ， M ( 竺 ) 图 2 中继卫星 系统资源分配算法流程 图 首先 ， 确 定在 当前 规 划 时 隙 S 内 可 服务 的 空 间任务集合 J。假设空间任务分为 D 个优先级 ， 则 按照优先级从高到低 的顺序逐级调度。尝试将集合 J中优 先级 为 q的 任 务 插 入 到 当前 服 务链 路 k中 ， 4 9 4 清 华 大 学 学 报 ( 自 然 科 学 版 ) 构造 初始解 P ， 重 复 N 次 上述
13、过 程 随机 构 造一 组初始解集合 P J： 1 ， 2 ， N)。 然后 ，对 P ， ， J一 1 ， 2 ， N执行种群联 合进化 ， 通过邻域搜索实现对初始解集合的优 化， 得 到进 化种群 中的当前最 优解 。 最后 ， 遍 历 p 个 优 先级 和 M 条 服务链 路 ， 得 到 中继卫星系统资源分配结果 P ， k= 1 ， 2 ， M， 即为任务调度的当前最优解。 3 2解的构造 针对空间任务具有容忍延时的特性 ，提出一种 自适应任务子序列调整算法。当 J o b 尝试插入 到 当前服务链路 k的任务链 P ， 中时 ，可以通过灵 活调 整 已调 度任 务 的起 止时 间 ，
14、进 而构 造 出更 优 的 解 ， 如 图 3所 示 。 靠 ，_ _、 ： 甄 ： 时间轴 口 _ 1 - J L W a fl k D 2 图 3 空间任务插入任务链的示意图 图 3中 当 叫 d 时 ， J o b 无法插 入 到 J o b 和 J o b 。 之 间 。假 设 J o b 。和 J o b 。具 有 容 忍 延 时 能 力 ， J o b 开 始时 间可 以前 移 即 A D 0， J o b 开 始时 间 可 以后 移 即 D 0， 如 果有 叫错 + 2 d ) + D d + 叫 + 伽社 ， 则 J o b 插入 到 J o b 。 和 J o b 之 间成
15、功 ，从 而构 造 出 更优 的任 务链 。 当选择不 同的相邻任务对进行任务插入时，得 到的任务链也是不同的，因此 ，问题转化如何选择 最优的任务对 ( J o b ， J o b )。选用的 目标 函数是最 大化空 闲 时间 ： 1 T I O Xfk ( J o b ， J o b ， J o b 口 )， f ( J o b ， J o b ， J o b 口 ) ： 叫嘏 + D +D 一 d 一 L Ic ek 即 当任 务插 入完成 后 ， 得 到的新 的任务链 在 J o b 前 后具 有最 大 的空闲 时间 。 3 3 解 的邻域 搜索 针对 空 间 任务 调 度 中任 务链
