基于分层强化学习的中继卫星网络任务动态调度方法.pdf

2023 年 7 月 Journal on Communications July 2023 第 44 卷第 7 期 通 信 学 报 Vol.44 No.7基于分层强化学习的中继卫星网络任务动态调度方法 刘润滋1，马天赐1，吴伟华2，要趁红1，杨清海3（1.西安建筑科技大学信息与控制工程学院，陕西 西安 710399；2.陕西师范大学物理学与信息技术学院，陕西 西安 710119；3.西安电子科技大学通信工程学院，陕西 西安 710071）摘 要：近年来，随着各类紧急任务数量的不断增长，如何在控制对常规任务影响的同时保障系统的收益已成为中继卫星网络任务动态调度的巨大挑战。针对这一问题，以最大化紧急任务总收益和最小化常规任务破坏程度为目标，提出了一种基于分层强化学习的中继卫星网络任务动态调度方法。具体而言，为了兼顾系统的长期与短期性能，设计了由上、下级 DQN 实现的双层调度框架，上级 DQN 从长期性能出发决定临时优化目标，下级 DQN根据优化目标决定当前任务的调度策略。仿真结果表明，与传统的深度学习方法以及部分处理动态调度问题的启发式方法相比，所提方法能够在降低常规任务破坏程度的同时提升紧急任务总收益。关键词：中继卫星网络；任务调度；深度强化学习；多目标优化；动态调度 中图分类号：TN92 文献标志码：A DOI:10.11959/j.issn.1000436x.2023130 Dynamic task scheduling method for relay satellite networks based on hierarchical reinforcement learning LIU Runzi1,MA Tianci1,WU Weihua2,YAO Chenhong1,YANG Qinghai3 1.School of Information and Control Engineering,Xian University of Architecture and Technology,Xian 710399,China 2.School of Physics and Information Technology,Shaanxi Normal University,Xian 710119,China 3.School of Telecommunications Engineering,Xidian University,Xian 710071,China Abstract:In recent years,with the increasing number of various emergency tasks,how to control the impact on common tasks while ensuring system revenue has become a huge challenge for the dynamic scheduling of relay satellite networks.Aiming at this problem,with the goal of maximizing the total revenue of emergency tasks and minimizing the damage to common tasks,a dynamic task scheduling method for relay satellite networks based on hierarchical reinforcement learn-ing was proposed.Specifically,in order to take into account the long-term and short-term performance of the system at the same time,a two-layer scheduling framework implemented by upper-level and lower-level DQN was designed.The up-per-level DQN was responsible for determining the temporary optimization goal based on long-term performance,and the lower-level DQN determined the scheduling strategy for current task according to the optimization goal.Simulation results show that compared with traditional deep learning methods and the heuristic methods dealing with dynamic scheduling problems,the proposed method can improve the total revenue of urgent tasks while reducing the damage to common tasks.Keywords:relay satellite networks,task scheduling,deep reinforcement learning,multi-objective optimization,dynamic scheduling 收稿日期：20230518；修回日期：20230704 通信作者：马天赐， 基金项目：国家自然科学基金资助项目（No.61701365,No.61801365,No.61971327）；陕西省自然科学基础研究计划基金资助项目（No.2023-JC-YB-566,No.2023-JC-YB-542）；陕西省重点研发计划基金资助项目（No.2021GY-066）；陕西省高校科协青年人才托举计划资助项目（No.20200112）；陕西省博士后科研基金资助项目（No.2018BSHEDZZ47)Foundation Items:The National Natural Science Foundation of China(No.61701365,No.61801365,No.61971327),Natural Science Basic Research Program of Shaanxi(No.2023-JC-YB-566,No.2023-JC-YB-542),Key Research and Development Program of Shaanxi Province(No.2021GY-066),Young Talent Fund of University Association for Science and Technology of Shaanxi Prov-ince(No.20200112),Postdoctoral Foundation of Shaanxi Province(No.2018BSHEDZZ47)208 通 信 学 报 第 44 卷 0 引言 数据中继卫星（以下简称中继卫星）网络是在航天器与地面站之间提供实时服务和数据测控的系统，一般位于地球静止轨道，从上到下覆盖用户航天器，有效解决了地面站轨道覆盖率低、航天器数据回传难的问题1。中继卫星任务通常分为常规任务和紧急任务，常规任务通常分批次、分时段到达，由中继卫星周期性地统一规划，而紧急任务具有突发性和不确定性，并且有效期短、优先级高2-3，需要中继卫星中心实时动态调度。两类任务在到达与调度时间上的差异导致紧急任务到达时网络中部分资源已经分配给了常规任务。而紧急任务的优先级较高，在其调度过程中往往会因资源不足抢占已分配好的常规任务资源，这极大地影响了常规任务的服务质量和用户体验。近年来，卫星等各类航天器在各种自然灾害4、事故等突发事件中起到越来越重要的作用，突发数据的实时回传需求不断增加，如何实现紧急任务的高效动态调度以保障全网收益成为中继卫星网络中亟待解决的问题。然而，现阶段中继卫星网络的研究工作大多致力于常规任务的静态调度5-6，仅有部分工作研究紧急任务的动态调度7-9。He 等7提出了一种基于滚动时域的中继卫星混合任务调度方法，通过在动态调整的规划中同时调度紧急任务与常规任务，降低了紧急任务对常规任务的影响。然而，在该方法中紧急任务响应速度受限于规划周期的长度，导致实时性要求高的任务难以获得保障。Deng 等8提出了2 种紧急插入策略，分别考虑了对常规任务的移动与拆分。类似地，Dai9提出了紧急任务直接插入、间接插入和重新规划 3 种策略。文献8-9的方法以保障当前紧急任务成功调度为出发点设计，与 He等7的方法相比可以更有效地保证紧急任务的服务质量，但是这些方法一方面对常规任务造成了较大的影响，另一方面忽视了紧急任务之间的资源冲突和网络的长期收益，不适用于紧急任务数量较多且连续到达的场景。综上所述，现阶段中继卫星网络任务的动态调度在提升长期收益与降低对常规任务的影响方面仍有较大的研究空间。由于现有工作缺少在长期收益与对常规任务破坏方面的研究，本文基于分层强化学习设计了一种中继卫星网络任务动态调度方法。具体而言，首先建立以最大化系统收益和最小化常规任务的破坏程度为目标的多目标优化模型。其次，设计了一种基于双层深度 Q 网络（DQN,deep Q-network）的动态调度框架，其中，上级 DQN 负责从长期性能出发调整下级 DQN 的临时目标，下级 DQN 负责根据临时目标决策当前时间点的调度策略。在此基础上，本文设计了 4 种调度策略，并提出了分层 DQN 训练算法和基于分层 DQN 的任务动态调度算法。最后通过仿真分析验证了所提方法的有效性。1 系统模型介绍 1.1 网络模型 考虑如图 1 所示的中继卫星网络场景，其包含3 层结构：骨干网层、用户层和地面网层。其中，骨干网层由中继卫星组成，用于向用户层提供数据中继服务。中继卫星集合记为12,kRr rr Kr，其中，kr表示第k个中继卫星，K 表示中继卫星的数目，每个中继卫星上装载一套用于提供中继服务的单址天线。用户层由低轨用户卫星组成，用户卫星集合记为12USus,us,us,i，其中，usi表示第i个用户卫星。地面网层主要包括地面站、用户卫星管理中心和数据中继卫星管理中心。中继卫星网络中存在两类任务，分别是紧急任务和常规任务。常规任务时延容忍性高、优先级低，紧急任务实时性高、优先级高。中继卫星网络的工作机制如下10-11。1)提交任务请求。用户卫星管理中心通过用户任务请求链接向数据中继卫星管理中心提交任务请求，以请求数据中继服务。图 1 中继卫星网络 第 7 期 刘润滋等：基于分层强化学习的中继卫星网络任务动态调度方法 209 2)生成调度方案。对于常规任务，数据中继卫星管理中心周期性地统一规划收集到的任务请求，即根据任务需求调度周期内的传输资源，生成调度方案并发送给用户卫星管理中心和中继卫星执行。对于紧急任务，数据中继卫星管理中心一旦接收到紧急任务的请求，则立即为该任务分配尽可能早的传输资源，生成调度方案并发送给用户卫星管理中心和中继卫星执行。3)执行调度方案。用户卫星管理中心通过测控链路将调度方案发送到用户卫星12。根据调度方案，当用户卫星进入中继卫星的覆盖区域时，将任务数据传输给中继卫星。数据将通过传输链路传输到地面。1.2 问题描述 本文重点关注中继卫星网络中紧急任务的动态调度。假设调度周期S内存在若干已分配资源的待执行常规任务，紧急任务动态到达网络，数据中继卫星管理中心按照紧急任务请求的先后顺序实时调度。调度周期S内的常规任务集合表示为12MCmc,mc,mc,n，其中mcn表示第n个常规任务。类似地，调度周期S内到达的紧急任务集合表示为12MEme,me,me,i，其中mei表示第 i 个紧急任务。每个紧急任务可表示为一个五元组，即me(,Pr,us)iiiikiia dp。对于mei，ia表示紧急任务mei的到达时刻，id表示最晚结束时刻，ikp表示mei在中继卫星kr上所需的传输时长（即执行时长），Pri表示mei调度完成后可获得的最大收益，usi表示发起请求的用户卫星。由于紧急任务的紧迫性，其完成越快，用户满意度就越高，实际获得收益也就越大。因此用is表示mei的实际开始时刻，SHPri表示mei的实际收益，iz表示mei调度成功后的实际结束时刻，,miniz表示mei可能的最早实际结束时刻，因此SHPri可表示为 ,min,minSHPrPre iiiizzdzii(1)当一个紧急任务到达时，数据中继卫星管理中心根据当前资源状态为其分配一颗中继卫星上的一段时间窗口用于完成数据传输。由于紧急任务具有较高的优先级，动态调度过程中可能会抢占已安排的常规任务资源，保障紧急任务在有效期内执行完毕。对于被破坏的常规任务，数据中继卫星管理中心会尝试为其调度剩余的空闲资源，尽可能减少紧急任务对常规任务的影响。为了保障紧急任务收益的同时保障常规任务的服务质量，数据中继卫星网络紧急任务动态调度的目标为最大化紧急任务收益的同时最小化常规任务破坏程度。调度需要满足的约束如下。1)每颗中继卫星同一时刻只能为一颗用户卫星提供服务。2)为紧急任务分配的传输资源满足紧急任务的时效要求。3)为紧急任务分配的传输资源满足中继卫星与用户卫星的可见性要求。4)每个紧急任务的数据传输过程不会被中断。1.3 问题建模 用12,TWtw,tw,i ki ki k表示在调度周期S内用户卫星usi与中继卫星kr之间的可见时间窗口集合。其中，,twst,etllli ki ki k为用户卫星usi与中继卫星kr之间的第l个可见时间窗口，,stli k为窗口的开始时间，,etli k为窗口的结束时间。为了建立数据中继卫星网络任务动态调度的优化模型，定义决策变量,li kX和,i j kY分别表示执行紧急任务的可见窗口和紧急任务在中继卫星上的执行顺序，具体为 ,1,me 0 ikli krlX紧急任务 在中继卫星 上的第 个 可见窗口内执行，其他 ,1,1,memememekiji j kkjiYrr中继卫星 上紧急任务在 之前执行中继卫星 上紧急任务在 之前执行 用MCE表示因紧急任务抢占资源而导致分配方案改变的常规任务集合，MCP表示因紧急任务抢占资源导致执行失败的常规任务的集合。为了保障紧急任务收益的同时降低对常规任务的破坏程度，将中继卫星网络任务动态调问题建模为如下优化模型 ,12TWME,111TW1,112TW3,111FTMCEMCPSHPrmaximize s.t.C:1,1ME C:,1ME C:,1ME SYPi ki ki kKli kikilKli kkliili kiilXXiasiXzdi :210 通 信 学 报 第 44 卷 ,4,TWTW5,11TWTW,11 C:stet0 1ME,1,1TW C:1 10 1Mj ki kj ki kllli kii ki kii klmjikii kj ki j klmlmijkji kj ki j klmXszikRlapaXXYapaXXYi E,1 kR (2)优化问题P中存在 2 个优化目标，分别为最大化总收益SY以及最大化常规任务破坏程度FT的倒数。其中，常数1和2分别为改变和取消常规任务的权重因子，且满足210。约束 C1表示每个紧急任务只能在一颗中继卫星上的一个可见窗口内调度一次；约束 C2表示紧急任务的传输开始时刻要大于任务到达时刻；约束 C3表示紧急任务的传输结束时刻要小于任务的最晚结束时刻；约束C4表示任务传输过程在用户卫星与中继卫星的可见窗口内进行；约束 C5则表示同一中继卫星上执行的任务之间不发生冲突。2 基于分层强化学习的双层调度框架设计 2.1 调度框架概述 传统中继卫星资源动态调度问题已被证明为NP（non-deterministic polynomial）难问题13，难以在多项式时间内获得最优解。本文对收益与常规任务破坏程度目标的追求进一步提高了该问题的复杂度，使系统基于数学模型求解方法很难获得低复杂度的动态调度策略。同时，卫星沿轨道周期性运动，使可见窗口分布也有一定的周期性，且紧急任务长期到达率分布也具有一定的统计规律。不同于传统基于数学模型的求解方法，机器学习方法能够有效利用往期经验数据，通过提前训练的方式实现性能与复杂度的有效折中。考虑到本文方法的调度既要基于大时间尺度的网络性能14，又要基于小时间尺度的任务到达状态，本文提出了一种基于分层强化学习的任务动态调度框架。如图 2 所示，本文所设计的任务动态调度框架由上级控制器、下级控制器和调度策略集组成，其中 2 个控制器各由一个 DQN 实现，具体原理简述如下。1)上级控制器负责从网络的长期性能与状态出发，调整下级控制器当前阶段的临时目标，上级控制器的控制策略表示为 up,up,:;Utttg(3)其中，up,t表示上级控制器的输入特征，由网络长期状态特征（其具体定义将在2.2节介绍）构成；up,t表示上级控制器（即上级 DQN）的参数；tgG表示选择的临时目标；G表示临时目标集合。2)下级控制器负责在每个调度点上根据当前网络状态、任务参数和临时目标，从调度策略集中选择调度策略来完成当前任务调度。具体而言，下级控制器的控制策略表示为 lowlow,:;L,ttta(4)其中，low,t表示下级控制器的输入特征，其包括网络短期状态特征、当前任务特征（其具体定义将在2.2 节介绍）和tg，low,t表示下级控制器（即下级DQN）的参数，taA表示选择的调度策略，A为调度策略集，调度策略集中的调度策略均满足1.3 节中模型的约束条件。图 2 基于分层强化学习的任务动态调度框架 第 7 期 刘润滋等：基于分层强化学习的中继卫星网络任务动态调度方法 211 上述动态调度框架一方面可以通过提前训练DQN 学习往期训练数据经验，缩短调度所需时间，从而实现调度复杂度与性能的有效折中；另一方面，分层强化学习可以使决策方式在不同的时间尺度上进行不同量级的调整，以更好地适配紧急任务到达率分布变化并保障网络长期性能。2.2 网络状态特征 如图 2 所示，本文所提框架中的上、下两级DQN 需要根据网络状态做出决策。为了提高该框架的有效性和通用性，本节设计了 13 个网络状态特征参数作为分层 DQN 的输入特征，具体如下。1)当前紧急任务mei的最大收益Pri。2)当前紧急任务mei的紧张程度UCT，表示为 PrUCTiiida(5)3)调度周期内紧急任务的平均到达率ave。4)调度周期内紧急任务的到达率方差std。5)t时刻紧急任务的到达率t。6)0,t时间区间内系统总收益SY()t。7)0,t时间区间内系统对常规任务的破坏程度FT()t。8)t时刻中继卫星长期资源平均利用率aveUL()t，表示为 1aveULUL()()KkkttK(6)其中，UL()kt表示0,t时间区间内中继卫星k上已安排任务的资源利用率。9)t时刻中继卫星短期资源平均利用率aveUS()t，表示为 1aveUSUS()()KkkttK(7)其中，US()kt表示,DT()ktt时间区间内中继卫星k上已安排任务的资源利用率，DT()kt表示t时刻kr上已安排未完成的紧急任务最晚结束时刻。10)t时刻中继卫星紧急任务长期资源平均利用率aveUEL()t，表示为 1aveUEL()UEL()KkkttK(8)其中，UEL()kt表示0,t时间区间内中继卫星k上紧急任务资源利用率。11)t时刻中继卫星紧急任务短期资源平均利用率aveUES()t，表示为 1aveUES()UES()KkkttK (9)其中，UES()kt表示,DT()ktt时间区间内中继卫星k上紧急任务资源利用率，并且UL()kt、US()kt、UEL()kt与UES()kt相同，均可在动态调度过程中统计计算得到。12)t时刻中继卫星紧急任务长期资源利用率方差stdUEL()t，表示为 2ave1stdUEL()UEL()UEL()KkktttK(10)13)t时刻中继卫星紧急任务短期资源利用率方差stdUES()t，表示为 2ave1stdUES()UES()UES()KkktttK (11)以上网络状态特征中，aveUL()t、aveUEL()t、stdUEL()t、ave、std、SY()t和FT()t为长期特征，aveUS()t、aveUES()t、t和stdUES()t为短期特征，Pri和UCT为当前任务特征。为了避免短视性，使算法能够获得全局最优解，上级控制器通过长期特征确定当前阶段的临时目标tg，下级控制器通过短期特征和当前任务特征，根据选定的临时目标确定具体调度策略ta。具体地，上级控制器输入特征表示为 up,aveavestdavestd(UL(),UEL(),UEL(),SY(),FT()tttttt(12)下级控制器输入特征表示为 low,aveavestd (US(),UES(),UES(),Pr,UCT,)titttttg(13)2.3 任务调度策略 本文所提的双层调度框架中，下级控制器负责根据当前网络状态与临时目标做出调度决策。然而，中继卫星任务调度问题的解空间是无限且非连续的，既无法枚举，又难以通过一个连续的函数表示，为下级DQN的设计带来了极大的挑战。为了降低训练复杂度，本文用调度策略集作为下级DQN的动作空间，即下级控制器根据low,t与tg从调度策略集中选定调度策略并执行，完成当前紧急任务的212 通 信 学 报 第 44 卷 动态调度。本文根据调度目标和紧急任务的动态调度特性设计了4个调度策略。本节后续内容首先介绍任务的可行调度窗口，再对4个调度策略分别进行介绍。2.3.1 任务的可行调度窗口 如图3所示，在当前紧急任务mei动态调度过程中，传输窗口的选择既受限于任务最晚结束时间id和与中继卫星的可见窗口,st,etlli ki k，又要避免与已调度的紧急任务mej发生冲突。为了降低调度策略的复杂度，基于传输窗口选择约束定义任务的可行调度窗口集合，将紧急任务动态调度资源调度问题转化为可行调度窗口选择问题。具体地，用,1OWOWKii kk表示紧急任务mei的可行调度窗口集合，12,OWow,ow,ow,owhhi ki ki ki ki k，,hho i ko i ks te t表示紧急任务mei在中继卫星kr上的第h个可行调度窗口，其中，,ho i ks t为窗口的开始时间，,ho i ke t为窗口的结束时间。对于任意,owhi k，其需要满足以下条件。1),twTW,lhhi ki ko i ko i ks te t，有,st,et lli ki k。2),hho i ko i kiis te tad。3),hho i ko i kike ts tp。4),swSW sw,hhjjo i ko i ks te t，有，其中swsst,est jjj表示已调度未执行任务mej的传输窗口，SW表示已调度未执行的紧急任务传输窗口集合。图 3 可行调度窗口 2.3.2 调度策略1 调度策略1的目标是任务结束时刻最早。对紧急任务而言，结束时刻越早越有利于获得更高的收益，同时也越有利于避免与后续任务发生冲突。用k表示紧急任务mei分配的中继卫星序号，调度策略1具体如算法1所示。算法 1 结束时刻最早优先调度策略 1)初始化OWi；2)if OWi then 3)计算t时刻存在任务mei的可行调度窗口的中继卫星序号集合()iK t；4)1,argminio i kikk Ktks tp；5)1,ioi kss t；6)else 7)任务mei调度失败；8)end if 2.3.3 调度策略2 调度策略2优先将紧急任务分配到当前时段资源利用率最低的中继卫星上，一方面有利于避免对常规任务造成影响，另一方面中继卫星资源利用均衡有利于后续任务的完成。令,FT owhi k表示当前任务mei在窗口,owhi k内传输对常规任务的破坏程度，调度策略2具体如算法2所示。算法 2 最低利用率中继卫星优先调度策略 1)初始化OWi和US()kt；2)if OWi then 3)计算t时刻存在任务mei的可行调度窗口的中继卫星序号集合()iK t；4)argminUS()ikk Ktkt；5),1OWargmin FT owi khi khh；6),hioi kss t；7)else 8)任务mei调度失败；9)end if 2.3.4 调度策略3 当紧急任务到达时，调度策略3可以帮助当前任务寻找所有可行调度窗口中对常规任务影响最小的窗口，以保障常规任务的服务质量，各窗口对常规任务的破坏程度采用优化问题P（即式(2)）的目标中FT的定义方式计算，调度策略3具体如算法3所示。算法 3 最小破坏程度优先调度策略 1)初始化OWi；2)if OWi then 3),owOW,argminFT(ow)hi kihi kkh；第 7 期 刘润滋等：基于分层强化学习的中继卫星网络任务动态调度方法 213 4),hioi kss t；5)else 6)任务mei调度失败；7)end if 2.3.5 调度策略4 调度策略4将紧急任务分配到当前时段紧急任务占用资源数最少的中继卫星上，从而使各中继卫星中的紧急任务分配均匀，有利于降低当前紧急任务之间的冲突，提升后续紧急任务分配成功的概率，调度策略4具体如算法4所示。算法 4 最低紧急任务资源占用率中继卫星优先调度策略 1)初始化OWi和UES()kt；2)if OWi then 3)计算t时刻存在任务mei的可行调度窗口的中继卫星序号集合()iK t；4)argminUES()ikk Ktkt；5),1OWargmin FT owi khi khh；6),hioi kss t；7)else 8)任务mei调度失败；9)end if 2.4 奖励函数 本文提出的基于分层强化学习的双层动态调度框架中，上、下级控制器均由DQN实现。DQN的训练需要设计奖励函数，好的奖励函数有利于加快强化学习的收敛速度，使之更快地逼近训练目标。上级DQN基于长期特征对系统做出长时间尺度决策，面向调度长期目标避免短视性。因此上级DQN奖励函数Ur表示为 12SY(1)SY()FT(1)FT()eettttUr (14)其中，SY()t和FT()t分别为0,t时间区间内紧急任务总收益和常规任务破坏程度，常数1与2分别为紧急任务总收益和常规任务破坏程度的权重因子，且满足210。下级DQN基于上级临时目标做出决策，因此其奖励函数基于临时目标设计。上级控制器中包含3个临时优化目标，即1,2,3g，分别对应紧急任务总收益、常规任务破坏程度和资源利用率方差。因此下级DQN奖励函数Lr表示为 stdstdSY(1)SY()FT(1)FT()L(1)()1,11,21,3ttttttUtUttegregeg(15)其中，std()Ut为,()kt DTt时间区间内中继卫星已安排任务的资源利用率的方差，表示为 2ave1stdUS()US()()KkkttUtK(16)3 基于分层 DQN 的任务动态调度算法 3.1 DQN 结构设计 调度框架中的2个DQN都使用深度神经网络代替Q函数。上级DQN是由6个全连接层组成的深度神经网络，其中包括一个含有7个节点的输入层（对应up,t中7个状态特征）、4个每层有200个节点的隐藏层，以及一个含有3个节点的输出层（对应于3个临时目标）。下级DQN与上级DQN类似，同样使用深度神经网络代替Q函数，由6个全连接层组成，包括一个含有7个节点的输入层、4个每层有200个节点的隐藏层，以及一个含有4个节点的输出层（对应于4个候选调度策略）。上、下级DQN都使用ReLU函数作为激活函数。3.2 分层 DQN 训练算法 算法5展示了分层DQN整体的训练流程，其中T为调度点的集合，在本文中，调度点所在位置为一个紧急任务的调度开始或结束时刻。upD与lowD分别为上级DQN和下级DQN的数据缓存区，分别用于存储各自的历史数据。为了保证训练过程的稳定性，避免Q值更新产生振荡，上、下两级DQN分别引入了目标网络upQ和lowQ，两者计算原理相同，计算方式分别为 upUupupupupupup,argmax,;gyrQQg (17)lowLlowlowlowlowlowlow,argmax,;gyrQQg (18)为了避免网络陷入“探索利用窘境”，本文采用-贪婪算法作为动作选择策略，使网络在探索与利用之间达到较好的折中15，从而获得最大奖励。算法 5 分层DQN训练算法 1)初始化上、下级DQN的参数up、low和数 214 通 信 学 报 第 44 卷 据缓存区upD、lowD；2)令upup，lowlow；3)for epoch1:L do 4)初始化网络特征并确定上级DQN输入特征up,0；5)初 始 化 当 前 阶 段 的 临 时 目 标0up,0up-greedy(;)g；6)令U,00r,L,00r；7)for 1:tT do 8)确定当前网络特征并确定下级DQN输入特征low,t；9)确定low,low-greedy(;)tta并执行对应的调度策略；10)更新网络特征并计算奖励值U,tr与L,tr；11)确定上级网络输入特征up,1t；12)if 1(1)%0tM then 13)更新下一阶段的临时目标 1up,1up-greedy(;)ttg；14)else 15)令1ttgg；16)end if 17)确定下级网络输入特征low,1t；18)将up,U,up,1(,)ttttg r存储进upD，将low,L,low,1,tttta r存储进lowD；19)if upD和lowD中数据量达到2M then 20)从upD和lowD中分别随机选取部分样本up,U,up,1,ffffgr和low,L,low,1,ffffar 21)计算upy和lowy并执行梯度下降法更新参数up和low；22)end if 23)每训练C步更新参数upuplowlow,24)end for 25)end for 3.3 任务动态调度算法 基于训练得到的双层DQN参数up和low，可以得到中继卫星网络任务动态调度算法。如算法6所示，当任务请求到达时，将当前网络状态特征输入训练好的双层DQN模型，即可得到应执行的调度策略。算法 6 基于分层DQN的任务动态调度算法 1)while在调度周期S内 2)t时刻收到任务请求；3)确定当前上级DQN的输入特征up,t；4)确定当前阶段的临时目标tg，如果需要更新则令upup,upargmax,;tgtgQg；5)确定下级DQN的输入特征low,t；6)确定调度策略lowargmaxtaaQ；low,low,;ta 7)执行at对应的调度策略 8)end while 4 仿真分析 本节通过仿真验证所提出的基于分层DQN的任务动态调度算法的性能。考虑一个包含3颗中继卫星和50颗低轨用户卫星组成的中继卫星网络。任务调度周期为24 h。随机生成500组任务集合，其中350组作为训练样本，150组作为测试样本。每组任务集合包含紧急任务与常规任务各100个，紧急任务的最大收益在10,12内服从均匀分布，且任务到达时刻在0,T内服从泊松分布，最晚结束时刻则在到达时刻ai之后的23 h内服从均匀分布。紧急任务mei在中继卫星rk上所需的执行时长在10,20 min内服从均匀分布，且随机选择承载的用户卫星。使用卫星工具包（STK）软件搭建仿真场景并获取调度周期中继卫星与用户卫星之间的可见窗口，通过Python3.6实现分层DQN的训练以及任务动态调度算法。4.1 收敛性分析 DQN中的学习速率代表网络训练时权重更新的步长。学习速率过大会导致损失函数收敛速度较快，此时的模型更容易接近局部最优；学习速率过慢难以保证收敛。本文的双层调度框架中，上、下级DQN的训练目标、输入的特征以及输出的动作均不相同，因此尽管2个网络同时训练，其学习速率的设置也是相互独立的。为了分析不同的学习速率对深度Q学习训练收敛性的影响，图4和图5分别展示了当紧急任务和常规任务数均为100时上级DQN和下级DQN训练损失随训练步数的变化曲线。第 7 期 刘润滋等：基于分层强化学习的中继卫星网络任务动态调度方法 215 图 4 上级 DQN 训练损失随训练步数的变化曲线 由图4可以看出，上级DQN的学习速率越大，训练过程收敛速度越快。当学习速率为0.000 1时，训练速度过于缓慢，从而影响算法效率，而当学习速率为0.01时，虽然收敛速度优于0.001时的收敛速度，但是容易陷入局部最优。由图5可以看出，当下级DQN的学习速率为0.001时，收敛速度明显小于0.01时的收敛速度，而当学习速率为0.1时，容易陷入局部最优。因此，后续仿真中将上级DQN的学习速率设置为0.001，将下级DQN的学习速率设置为0.01。图 5 下级 DQN 损失随训练步数的变化曲线 4.2 对比实验分析 为了验证本文所提的基于分层DQN的动态调度算法T-DQN（即算法6）的性能，将其与以下算法进行仿真对比。1)实时动态调度（RTDS,real-time dynamic scheduling）算法。通过动态插入机制完成紧急任务的调度工作，优化目标为最大化当前紧急任务收益，未考虑系统长期性能。2)基于多代理的动态调度（ABDS,agent-based dynamic scheduling）算法。基于多代理机制和轮盘机制为紧急任务选择合适的中继卫星以及可行调度窗口，仅关注当前紧急任务收益，不考虑紧急任务对常规任务的影响；3)深度强化学习算法（DQN）。采用单层DQN优化收益，通过系统和当前任务特征确定调度规则并执行，不考虑紧急任务对常规任务的影响。本文根据紧急任务总数的不同分别设计了4组对比仿真实验，其中紧急任务总数分别为25、50、75和100，4组实验中常规任务总数均为100，为了确保实验结果的可靠性，采用蒙特卡罗实验方法对每组实验进行测试，测试轮数为100。图6和图7分别展示了紧急任务收益和调度成功率随紧急任务数量增长的变化情况。从图6和图7中可以看出，随着紧急任务数量的增长，紧急任务收益随之增大，调度成功率随之减小。而紧急任务数量较少时，4种算法在收益和调度成功率方面的差异并不明显，这是因为此时紧急任务之间的冲突较少。然而随着紧急任务数量增长，T-DQN与其他3种算法在紧急任务收益方面的差异逐渐增大，这是因为在安排紧急任务时，T-DQN会根据当前情况尽可能选择较早的开始时间，保证该任务能够尽快完成；而且RTDS和ABDS算法仅考虑系统短期性能，在安排当前任务时没有考虑紧急任务的长期到达规律，以至于后来的紧急任务会与已安排好的紧急任务产生冲突，使部分后续紧急任务无法尽早安排或没有可行调度窗口，DQN算法虽然考虑了长期性能，但是与T-DQN相比，没有对资源利用率进行优化，很难保证长期负载平衡。这也是T-DQN算法紧急任务调度成功率大于其他3种对比算法的原因。图 6 紧急任务收益随紧急任务数量增长的变化情况 216 通 信 学 报 第 44 卷 图 7 紧急任务调度成功率随紧急任务数量增长的变化情况 图8展示了常规任务破坏程度随紧急任务数量增长的变化情况，从图8中可以看出，紧急任务数量增长，紧急任务对常规任务的破坏程度也随之增长。而紧急任务数量较少时，4种算法的破坏程度差异并不明显，因为此时紧急任务的可行调度窗口较多，且时段范围较广，很难对常规任务产生较大影响。当紧急任务数量较多时，T-DQN算法的破坏程度明显小于其他3种对比算法，这是因为RTDS和ABDS算法仅考虑了系统短期性能，DQN算法虽然以系统的长期性能为出发点，但也没有考虑紧急任务对常规任务的影响，而T-DQN在追求紧急任务收益的同时考虑了紧急任务对常规任务的影响，在安排紧急任务的同时最大限度地降低了对常规任务的破坏