基于多分支深度Q网络模型的卫星通信任务调度方法

班亚明，马 宁，王玉清，孙文宇*，王宝宝，刘秀芳，贾慧燕

(1.中国电科网络通信研究院，河北 石家庄 050081；2.航天系统部装备部军事代表局驻石家庄军事代表室，河北 石家庄 050081)

0 引言

在卫星资源有限的前提下,如何实现卫星通信任务的快速高效调度,最大限度满足地面通信任务对星上资源的需求是天基网络面临的关键问题之一[1-3]。而随着卫星通信任务需求量的增长,特殊情况下有限卫星资源无法满足所有用户需求,此时需要通过任务调度方法尽量提高满足率。

在当前的卫星通信任务调度问题研究中,一是大多数研究使用运筹学模型和启发式算法进行卫星通信任务调度,但是当实际中调度问题的约束较多时,会导致对需要求解的变量与复杂度的激增,而过多的求解变量使得上述算法和模型难以高效收敛至较优的局部最优解;二是随着强化学习技术的发展[4-6]以及卫星通信系统感知能力的提升,越来越多的经验数据被保存,而深度强化学习由于自身特性可以有效利用这些数据从中发现规律、学习策略,因此基于强化学习的方法在任务与资源调度中被更多地研究[7-8],并适用于卫星通信中的任务调度问题。

基于上述背景,本文基于深度强化学习网络的任务调度方法,针对卫星通信系统的场景提出了一种多分支深度Q网络模型,主要研究内容和贡献如下:

首先,提出了一种基于深度强化学习模型的任务调度方法,该模型通过引入了任务列表分支网络(TL分支)和资源池分支网络(RP分支),多分支深度Q网络能够同时对卫星资源池状态和卫星任务状态提取特征。随后拼接特征嵌入,并将其输入价值分支网络(Value分支)计算动作价值函数,并依据最优动作价值函数进行任务选择动作和优先级选择动作。多分支深度Q网络具有很多优秀的特性。其次,基于深度强化学习的解决方案在决策过程相比启发式算法非常高效。虽然强化学习策略的训练非常耗时,但是这些训练工作可以离线进行,实际中只需要利用训练好的模型进行推理,因而在绝大部分情况下可以做到近似实时决策。最后,使用强化学习的方法并不需要显式地对未来进行预测,模型可以从交互经验、海量数据中发现规律、学习策略,从而帮助作出合适的决策。

1 卫星通信任务调度问题

任务调度过程在基于透明转发器的卫星通信系统中被广泛应用,尤其是频率和时间资源的调度中,基于透明卫星转发器的任务调度过程如图1所示。一般情况下,使用卫星通信网络的用户需要提前对任务需求进行提报,将其使用的带宽资源与时间一起提交至宽带通信卫星的运行控制中心。运行控制中心为卫星的每个转发器维护一个分配的资源表,转发器中每个资源段的任务时间记录在该表中,并在多个星地综合网络之间共享。随后,运行控制中心将在表中找到满足需求提报者任务的空闲资源段,更新相应的任务时间段,并将分配结果通知需求提报者。最后,需求提报者利用分配的卫星转发器资源建立卫星通信网络。

透明卫星转发器任务调度过程如果依赖于人工,只有在任务需求量较少的情况下才可行。随着任务需求的强度不断加大与任务资源需求的灵活变化和多样性提升,任务调度过程造成的卫星转发器频率碎片化的现象日益严重,对人工搜索空闲资源段进行任务需求调度和维护带来了相当大的挑战。这些挑战增加了任务的复杂性和对运行控制中心的技术要求以及卫星系统的运营成本,并且由于其经验性质,手动搜索很难保证资源的最佳利用。此外,当高优先级任务的需求无法立即得到满足而需要抢占低优先级任务的现有资源时,如何选择抢占对象以保证影响最小也是决策过程需要考虑的问题。

通过对任务和资源进行合理快速调度,卫星通信任务调度方法能够在多约束的条件下提高卫星转发器资源(频率和占用时间)的使用率,通过多分支深度Q网络(Deep Q Network,DQN)提高卫星资源占用率的示意如图1所示。多约束条件下任务调度问题已经被证明是NP问题[9-10],一些传统运筹学算法[11-12]、贪心算法[13]和启发式算法[14-16]已经被应用在了卫星通信任务调度领域和其他任务调度领域中。

图1 通过多分支DQN提高卫星资源占用率Fig.1 Multi-branch DQN is used to improve satellite resource occupancy

2 基于多分支DQN的调度方法

2.1 强化学习问题定义

用于卫星通信的基于多分支DQN的任务调度方法可以定义如下:在固定的卫星通信系统条件下,将卫星通信系统的卫星任务需求和资源池生成定义为强化学习的环境。在该环境中,状态包括资源池状态srp和任务列表状态stl,t时刻的状态被定义为st,以及一系列用于决策的有效动作集A(s)。多分支DQN控制的智能体会在动作集合A(s)中选择一个有效的动作at∈A(s),并于时间t时在环境中执行动作at以获得奖励rt,之后环境的状态发生转移至st+1。在该方法中,将执行迭代直到环境达到终止条件,即所有分配完成并且资源池没有更多资源可供分配时终止。

2.2 多分支DQN模型建模

使用多分支DQN模型解决卫星通信任务调度问题实质上是找到了比使用启发式算法更好的排序序列,其最终目标是最小化分配结果的资源占用率,缩短卫星任务分配总时间。多分支深度Q网络是一种基于DQN[6]的离线策略(Off-policy)方法,是一种典型的价值优化强化学习算法,详细的网络结构在2.3节进行阐述。

多分支DQN将卫星运控中心建模为智能体(Agent),将任务需求和卫星通信资源建模为环境(Environment)。此外,还将讨论用于卫星通信任务调度问题的多分支DQN模型中定义的强化学习的主要元素,包括状态空间、动作空间和奖励。同时,模型训练阶段的经验回放、目标网络和损失函数的定义也会得到详细介绍。

图2 基于多分支深度Q网络的任务调度方法整体图Fig.2 Overview of the proposed multi-branch DQN based task scheduling method

①状态空间

t时刻下的卫星任务需求和资源池状态st=(srp,stl)t是对该时刻下资源池状态srp和任务列表状态stl的观测。当有新的任务需求时,需要对任务列表状态stl进行格式化并更新任务列表stl的状态,stl可以表示为:

stl={[o1,φ1(t1),φ2(f1)],…,[om,φ1(tm),φ2(fm)], (1)

式中:om表示卫星资源池中第m个任务的分配状态,tm和fm分别表示任务占用的卫星时间和频率资源,φ1(tm)=N×tm/Δt和φ2(fm)=N×fm/Δf为tm和fm的状态重构,使它们符合模型输入的张量大小,tm和fm均在[1,N]内重新表述,Δf和Δt分别表示卫星资源池中的时间资源和频率资源范围。

通过将频率资源和时间资源在各自维度上分别划分N-1次,可以将卫星资源池划分为N×N个资源块。状态矩阵srp用于表示资源池中每个资源块的占用情况。srp的表示如下:

(2)

式中:p(n,n)为(n,n)资源块中卫星资源池的占用指示。

②动作空间

在卫星通信任务调度问题中,可用动作空间A(s)是卫星控制系统的决策空间,根据t时刻的当前状态st从A(s)中选择动作at。可用的操作空间取决于分配的资源的类型和资源的限制,包括优先动作空间Ap和选择动作空间Ac。形式上,A(s)可以定义为:

A(s)={(Ac(i),Ap(j))|1≤i≤m,j=0,1},

(3)

式中:ac=Ac(i)为任务选择动作,表示本轮在列表中选择的任务号;ap=Ap(j)是资源搜索优先级的动作,表示分配时频率搜索或时间搜索的优先级。

动作选择的探索机制直接影响采样性能。因此,在训练阶段,动作选择采用-贪婪策略。多分支DQN以概率从A(s)中随机采样,可以表示为:

(4)

在测试阶段,多分支DQN会选择概率分布Q*(st,at)中概率最高的at。

③奖励

以资源占用率作为算法的优化目标,即网络的奖励值rt,代表对状态st下所选动作at的评价。任务分配后,资源占用率越高,奖励值越高。对于相同资源块大小的任务分配,资源占用率越接近上限,奖励值应该越大。基于上述原则,奖励设计如下式所示:

(5)

式中:非负乘数ε用于避免无穷值。

④经验回放

在训练阶段,同一般DQN方法采用了经验回放(Reply Memory)技巧来消除卫星任务分配系统中与环境交互产生的样本数据的相关性。原因在于深度神经网络要求输入样本不相关,但是对于卫星任务分配系统,任务分配顺序与最终资源占用率之间存在显着的相关性。而且,经验回放保证了一个样本可以多次参与训练,从而提高学习效率。每个训练步骤中生成的四元组et=〈st,at,st+1,rt〉保存在经验回放池中。

⑤目标网络

在训练阶段,本文使用目标网络来计算TD目标,SGD只更新DQN的参数,而不更新目标网络的参数。原因在于,即便卫星任务分配问题中分配动作并非最优,但其奖励通常是正值,并且会出现类似于DQN的高估问题,这会导致每次使用二元组〈st,at〉更新多分支DQN参数ω时,该模型往往会高估〈st,at〉的Q值。TD目标计算如下:

(6)

式中:γ为折扣因子奖励。目标网络的参数ω-定期更新,多分支DQN中目标更新间隔T根据经验设置为100。目标网络的参数通过计算ω和ω-的加权平均值来更新,然后再将值分配给ω-。

⑥损失函数

考虑到Q函数的自洽性,按照最小化Q(st,at;ω)和TD目标yt估计误差的原则更新动作价值函数。在一个训练轮次中,通过模型推理获得状态st和st+1之间的奖励值rt后,可以得到本次状态转移的四元组〈st,at,st+1,rt〉,随后损失函数L(ω)由以下等式计算:

L(ω)=E[(yt-Q(st,at;ω))2],

(7)

式中:yt通过式(6)计算。

2.3 网络结构

本节描述所提出的多分支DQN的网络结构,包括其RP分支、TL分支和Value分支,以及其详细网络结构,如图3所示。

图3 多分支DQN的模型结构示意Fig.3 Structure of the proposed multi-branch DQN model

RP分支是卷积神经网络(CNN),由卷积模块组成,每个模块由卷积层、BN层和ReLU激活组成。卫星资源池状态矩阵srp(根据式(2)计算)的输入大小为N×N,类似于2D图像,因此,RP分支使用CNN的结构更有利于提取卫星资源池状态的判别特征frp。RP分支的作用是从输入srp中提取特征,并将其作为推导动作价值函数的判决条件。TL分支是一个全连接(Fully Connected,FC)神经网络,其输入序列为卫星任务列表stl(由式(1)计算得到)经序列化后通过FC层从中提取特征,输入大小为3×M。TL分支的目标是从输入stl中提取特征,这些特征与frp一起用于估计动作价值函数。RP分支和TL分支是并行的,它们的输出通过Concat层连接起来。然后,将frp和ftl连接起来,生成用于动作价值函数估计的全局特征f,随后将其用作Value分支的输入来计算Q(st,at;ω)。与TL分支类似,Value分支也是基于FC层的神经网络。

TL分支、RP分支和Value分支共同构成了多分支DQN的整体结构,如表1所示。与一般的强化学习模型相比,该模型结合了多种卫星资源类型的特点,更适合不同类型的状态输入,更加关注卫星通信系统的资源状态。特别是,根据要解决的卫星分配问题的复杂性(例如任务数量、资源池块划分的大小),可以利用更深、更复杂的网络作为该模型的骨干。然而,主干结构的选择超出了本文的范围。为了简化,多分支DQN仅采用相对较浅的网络进行调查。

RP分支输入的高度和宽度均为N。在第三个卷积层使用了扩展特征图的技巧(表1中的Conv3)。再改模型中还采用批量归一化和Dropout来缓解ICS与过度拟合问题。在模型训练完成后,进行去BN操作,以提高模型的推理速度,进一步减少卫星通信任务调度时间。

3 实验设置与结果分析

3.1 数据集和实验设置

由于当前缺少公开卫星通信任务调度数据集,本文使用了2种随机生成方法来生成卫星任务列表数据集,并进行深度强化学习模型的训练。第一种方法是零浪费卫星任务列表数据集生成方法[17],可以用于比较不同分配方法之间的性能。第二种是非零浪费数据集生成方法,这种方法更符合卫星任务列表的实际情况。

在所有实验中,批量大小固定为32,使用SGD优化器,针对不同的episode,动量为0.9,权重衰减为0.000 5。在所有卷积和全连接层后添加BN和ReLU层,并通过Kaiming初始化[18]来初始化参数。为了消除随机因素,在训练模型时手动固定随机种子,以确保模型的初始化参数在不同实验运行中保持一致,避免影响对比实验的有效性和合理性。TL分支、Value分支和RL分支的初始学习率分别设置为0.001、0.001和0.01。经验回放池的缓冲区大小设置为1×105,经验回放的超参数设置如下:分别为α=0.3、β=0.5和η=0.000 005。梯度裁剪设置为20,折扣因子奖励γ设置为0.95。目标网络解决了训练阶段的高估问题,目标更新间隔为100。非负乘数ε根据经验设置为0.1。

3.2 实验结果与分析

基于3.1节中生成的零浪费和非零浪费数据集,本文对任务调度性能和运行时间性能进行了对比实验,证明了所提出的多分支DQN模型的有效性。具体来说,本文的对比实验如表2所示,主要比较了本文方法与传统贪婪算法和启发式算法的性能。此外,还分析了实验结果以及基于强化学习的多分支DQN模型如何影响卫星通信任务调度算法。

表2 本文方法与其他算法在零浪费数据集的对比Tab.2 Comparisons of the proposed multi-branch DQN with existing methods on the zero-waste dataset

由表2可以看出,与贪心算法和启发式算法相比,在零浪费数据集上进行测试时,多分支DQN在平均资源占用性能(AOP)和运行时开销(RO)方面都有显着改善。本文方法与贪心算法(Bottom Left[13])相比,可以在时限允许范围内大幅提高AOP指标,并且随着卫星任务数量的增加,本文方法的性能提升更加明显。例如,当M=40时,本文方法的性能(95.1%)明显高于GA-PSO[15](93.9%)。这是由于多分支Q网络模型能够从先前的经验中学习,不同的分支可以准确地学习和提取多状态特征,而不是对每个预测进行启发式探索。特别是对时间复杂度而言,本文方法(1.47 s)可以显著降低完整任务调度过程的运行时开销(32.54 s)。原因在于与GA-PSO等启发式算法相比,基于强化学习的方法消除了迭代过程时间,而多分支Q网络模型的训练过程虽长但可以离线进行,实际中仅使用训练好的模型进行推理。

本文还在非零浪费数据集中进行了对比实验,来更广泛的评估多分支Q网络模型的性能,模型的训练和测试的参数设置相同。实验结果如表3所示,与零浪费数据集上的实验结果相似。由于非零浪费,无法知道该数据集上的最优分配结果,但仍然可以使用AOP来比较每种方法的性能。与GA-PSO相比,本文方法在M=40时,AOP(89.6%)和运行时开销(1.52 s)方面也取得了更好的性能。

表3 本文方法与其他算法在非零浪费数据集的对比Tab.3 Comparisons of the proposed multi-branch DQN with existing methods on the non-zero waste dataset

从表2和表3可以得出结论:① 本文所提出的多分支Q网络模型与Bottom Left和GA-PSO相比,在非零浪费和零浪费数据集均取得更好的AOP,并且随着任务数量的增加,性能的提升变得更加明显。② 与GA-PSO等启发式算法相比,本文模型具有分配运行时间更短的优点,这是由于多分支Q网络模型在推理阶段不需要启发式算法的迭代过程,而大部分时间仅消耗在模型的训练过程上。以上结果证明,训练后的基于多分支的DQN模型能够有效解决卫星通信任务调度问题,TL分支和RP分支能够准确提取卫星资源池状态和卫星任务状态的判别特征。实验结果验证了强化学习算法在卫星通信任务调度问题上的应用效果。

4 结束语

本文提出多分支Q网络模型是一个基于透明转发器的卫星通信任务调度问题的强化学习解决方案。通过在网络中引入TL分支和RP分支,准确提取资源池和任务列表的判别特征。基于DQN的结构,通过Value分支选择包括优先级和任务索引号在内的多种动作价值函数,大大提高了平均占用率和时间消耗的性能。综合实验表明,提出的模型在生成的零浪费任务数据集和非零浪费任务数据集上为比传统的贪婪方法和启发式方法表现得更好。这些实验结果表明了本文方法在解决卫星通信任务调度问题方面的有效性和可靠性。