改进深度强化学习算法的计算卸载策略

葛海波，弓海文，宋 兴，李 顺，孙 奥

(西安邮电大学 电子工程学院，陕西 西安 710121)

随着智能手机、平板电脑等移动设备的数量急剧增加，诸如图像识别、增强现实、虚拟现实等任务密集型、时延敏感型的应用程序大量增长[1]。这些移动应用常常需要大量的计算资源，而受限于计算能力与电池容量的移动设备越来越无法支持这些应用[2]。为了克服这一问题，移动云计算(Mobile Cloud Computing,MCC)作为一种新的分布式计算模型被提出[3]，MCC允许终端从云计算中心借用计算和存储资源，满足资源需求型应用程序的需要[4]。尽管MCC可以节约本地的计算资源，但是，从移动设备到基站或云服务器的长距离传输可能会导致严重的时间延迟和额外的传输能耗[5-6]。

针对MCC存在的问题，欧洲电信标准化协会(European Telecommunications Standards Institute,ETSI)提出了移动边缘计算(Mobile Edge Computing,MEC)技术[7]。由于MEC卸载策略具有非确定性多项式难题(Nondeterministic Polynominal-Hard,NP-Hard)，大多数卸载策略都采用启发式算法[8]。例如，文献[9]提出了一种单用户的MEC系统优化框架，该框架采用一种基于线性规划松弛和半确定松弛方法的卸载决策算法，降低了执行延迟和能耗。文献[10]设计了一种基于遗传算法的任务卸载策略，减小了系统的总开销。文献[11]将MEC模型中的任务卸载问题描述为非线性问题，并提出了一种卸载算法来减少任务延迟并提高用户设备(User Equipment,UE)的电池寿命。文献[12]提出了一种基于能量消耗和等待时间的任务分担算法，其能耗和等待时间加权总和较低。文献[13]提出了一种基于改进遗传算法的边缘卸载策略，将每个卸载策略作为一条染色体，每条染色体上的基因对应一个计算任务，以降低系统总开销。但是，随着MEC应用程序和网络架构的日益复杂，导致启发式算法生成决策的时间过长，特别是在多用户的MEC环境下如何减少计算卸载的系统总时延和系统总成本，还需进一步研究。

为了减少生成决策的时间、降低系统总成本，研究人员开始通过深度强化学习(Deep Reinforcement Learning,DRL)的方法来解决MEC卸载决策问题。DRL结合了强化学习与深度学习理论，更适用于处理复杂系统中的决策问题[14]。例如，文献[15]提出了一种基于深度Q学习网络(Deep Q-Learning Network,DQN)的自主算法，以最小化分布式边缘网络中的网络延迟和功耗。文献[16]使用DQN方法处理新颖的网络知识，产生了近似的最优调度容忍机制，减轻了对反馈的严格要求。文献[17]提出了一种基于DQN的设备级和边缘级任务卸载联合优化方法，获得了接近最优的任务延迟性能。文献[18]提出了一种基于强化学习计算的车联网边缘计算架构的任务卸载策略，并采用双深度Q学习网络(Double Deep Q-Learning Network,DDQN)方法处理任务卸载问题，以克服用户移动引起的网络状态实时变化，提高了该策略的收敛性。文献[19]提出了一种利用DDQN方法在给定当前环境状态的情况下输出卸载决策。文献[20]分别利用DQN算法和深度确定性策略梯度(Deep Deterministic Policy Gradient,DDPG)算法研究了任务的最佳卸载比例、局部计算功率和传输功率，以最小化执行延迟和UE能耗。但是，目前利用DRL对MEC中卸载问题的研究仍存在两个方面的不足：一方面，MEC服务器的计算资源有限，同时卸载太多任务会导致排队延迟；另一方面，经典DRL方法在训练过程中存在训练速度慢、收敛不稳定等问题，影响了卸载计算的效率。

为了更好地利用MEC系统资源，降低系统成本，提高系统的效率，拟设计一种适用于MEC环境的二进制计算卸载策略。在有效减小UE和各计算节点的能耗与时延的基础上，决定任务是否应该卸载至边缘服务器执行，以提高MEC系统的效率。在任务卸载执行的时延中引入排队时延的计算，以最小化能耗与时延加权和作为计算卸载的目标，利用优先经验重放对DRL算法进行改进，对比改进前后不同用户设备数量和任务数据大小的系统成本以及改进前后系统的平均时延，以提高其在解决实际问题时的效率及稳定性。

1 系统模型

考虑到移动边缘计算中具有多服务节点和多用户的系统模型，建立一个多边缘服务器和多用户的MEC系统通信模型。该模型由一个包含多个边缘服务器的基站(Base Station,BS)和m个UE组成[20]，UE与BS间通过无线网络通信，MEC系统示意图如图1所示。

图1 MEC系统示意图

MEC系统中包含UE1,UE2,…,UEm等m个用户。设时间为一组相等间隔的时隙t(t=1,2,…,z)，任务产生的时间间隔服从泊松分布[21]。UE生成的任务i(i=1,2,…,I)可以建模为一个具有4个元素的元组{Di,bi,Ci,Ti,max}，其中，Di表示任务i数据的大小，bi表示计算任务i每一位数据的CPU周期，Ci=Di·bi为任务i的总CPU周期，Ti,max表示用户可接受的最大容忍时延。

定义任务i的二进制计算卸载决策变量为ψi∈{0,1}。当ψi=0时，表示任务i在本地执行；ψi=1时，表示任务i卸载至边缘服务器执行。

1.1 本地计算

移动UE具有一定的计算能力。假设移动UE一次只能执行一个任务。假设第k个(k=1,2,…,m)用户设备UEk的容量为Uk,C，任务开始前每个时隙设备k的剩余能量为Ek,re，执行任务i的能量消耗为Ei,k。若满足Di≤Uk,C和Ei,k≤Ek,re，则任务在本地执行。

本地计算模型的执行时间仅包括计算时间，不包含传输时间。在本地执行任务i的时间成本[19]为

(1)

式中，fk表示UEk的CPU频率，即UEk的每秒CPU周期，反映了其计算能力。

在UEk上执行任务i的能量消耗[19]为

Ei,k=κ·fk·Ci

(2)

式中，κ表示芯片中的有效开关电容，其大小取决于器件的芯片架构。

1.2 卸载计算模型

用户移动设备的计算资源有限，执行某些资源密集型应用时会产生较高的时延与能耗。当本地资源不足时，将任务卸载到MEC服务器上处理。

由于任务计算完成后传回UE的数据量通常远小于其原始数据，因此传回的时间可忽略不计。传输时间仅为从UE向MEC服务器上传任务数据的时间成本，根据香农公式，UEk与BS的通信速率[22]为

(3)

式中：W表示UEk和BS之间的通信带宽；pk是UEk的发射功率；N0是BS的噪声功率谱密度；gk,B表示UEk和BS之间的信道增益[22]，其计算表达式为

(4)

式中：dk,B表示UEk与BS之间的距离；σ为路径损耗指数。

发送任务i的数据产生的延迟[22]为

(5)

在MEC服务器上执行任务i的延迟[22]为

(6)

式中，fs,k表示服务器s分配给UEk的计算资源。

任务i卸载至MEC服务器进行处理的能耗为上传能耗和计算能耗的总和。其中任务i上传能耗Ei,tr与MEC服务器执行任务i的能耗[22]Ei,mec分别定义为

Ei,tr=pk·Ti,tr

(7)

Ei,mec=Di·es

(8)

式中，es表示服务器s在BS上计算的每个数据位的能耗。

2 PERDDQN的卸载策略

DRL对于复杂系统的感知决策问题有较强的解决能力[23]，但是，在MEC场景内实际应用时往往由于很难学习到有用的经验，导致无法得到合理卸载策略。为此引入了一种基于优先经验重放(Prioritized Experience Replay,PER)改进的DDQN算法(Prioritized Experience Replay Double Deep Q-Learning Network,PERDDQN)来求解最优的卸载模式。

2.1 问题的建模

任务卸载执行时，移动设备用户会对有限计算资源的竞争而产生排队延迟。设MEC服务器中可用的计算资源Vmec，则任务i等待执行产生的排队时延为

(9)

联合式(5)、式(6)和式(9)，UEk将任务i卸载到BS上的服务器s处理所产生的时间成本为

Ti,off=Ti,tr+Ti,que+Ti,mec

(10)

根据式(7)和式(8)可得，任务i卸载执行的能耗为

Ei,off=Ei,tr+Ei,mec

(11)

MEC系统中存在多个用户，每个用户都遵循二进制卸载决策完成计算任务。根据式(1)与式(10)，MEC系统执行全部任务的总时延为

(12)

当ψi=0时，Ti=Ti,k；当ψi=1时，Ti=Ti,off。

同理，执行所有任务的总能耗为

(13)

当ψi=0时，Ei=Ei,k；当ψi=1时，Ei=Ei,off。

为了同时考虑能量消耗和延迟，总计算成本根据能量消耗和任务延迟线性加权进行量化。联合式(12)和式(13)，系统总成本可以表示为

(14)

式中，ω∈(0,1)表示为UE的执行延迟加权参数，可以根据用户的需求进行调整，例如，执行时延敏感型应用程序时可适当增大ω的值。考虑到时延敏感型应用程序，ω取0.8[24-25]。

多计算节点多用户卸载问题的目标是在满足用户最大容忍时延的条件下，最小化系统总成本，该问题是具有耦合约束的多目标优化编程。目标函数建模为

(15)

式中：fk,max表示UEk的最大计算功率；pk,max表示UEk的最大发射功率；Fs,max表示服务器s的最大计算频率；C1表示选择任务在本地执行或卸载至边缘服务器执行；C2表示执行任务的能耗不能超过UE当前剩余能量，若能量不足则任务需卸载执行；C3表示设备计算频率最大限制；C4表示传输功率最大限制；C5表示服务器分配的计算资源不能超过其最大计算资源；C6表示任务需要在可容忍时延内完成。

2.2 MDP模型的构建

强化学习的过程中，将计算卸载问题重新表述为马尔科夫决策过程(Markov Decision Process,MDP)模型。典型的MDP模型由具有5个元素的元组{S,A,P,R,γ}组成。其中，S代表状态空间，A为有限动作空间，P为状态转移概率，R代表奖励函数，γ∈[0,1]是未来奖励的折扣因子。MDP模型元组中每个元素对应的含义如下。

1)状态空间。状态空间中的每个状态都包含一些从环境中观察到的信息。将模型中时隙t的状态s(t)表示为s(t)={fk,Ek,re,Uk,C,W,Di}。

2)动作空间。为了确定任务是否应卸载到计算节点上执行，动作空间与卸载决策应呈对应关系。动作空间的定义为

A={a(1),a(2),…,a(z)}

(16)

在时隙t(t=1,2,…,z)，a(t)=0表示任务在本地执行，a(t)=1表示任务卸载至边缘服务器执行。

3)奖励函数。在执行动作a(t)后，将获得奖励r(s(t),a(t))，UE选择要执行的动作a(t+1)。奖励函数通常与目标函数相关，为了高效判断任务是否需要卸载执行，将目标函数定义为实现最小化任务执行时间与能耗的加权和。强化的目标是获得最大奖励，为此定义奖励值R与系统总成本C的大小负相关，即

R=-C(t)

(17)

4)转移概率。给定用户采取的操作a(t)，转移概率P{s(t+1)|s(t),a(t)}表示环境状态在下一个时隙中从s(t)转换为s(t+1)的概率。

5)折扣因子。折扣因子γ为未来奖励权重。当γ趋于0时，表示主要考虑当前获得的奖励；γ趋于1则表示将更关注后续步骤中的累积奖励。γ的值决定了更倾向于短期回报或长期回报。

2.3 优先级的计算

PERDDQN算法利用PER在训练过程中对样本进行优先级采样，用于加快神经网络的训练速度。PER打破均匀采样，赋予学习效率高的状态更大的采样权重[26]。PER采用时间差分(Temporal-Difference,TD)误差来表示每个转移过渡的重要性。

TD误差为目标Q网络计算的目标Q值和当前Q网络计算的Q值之差。TD误差越大代表预测精度还有很大的上升空间，那么该样本就越需要被学习，优先级就越高，样本j优先级可以表示为

δj=yj,PER-Q(SJ(T),AJ,θ)

(18)

其中：yj,PER为目标的Q值；Q(sj(t),aj,θ)为当前网络的Q值。

为了避免初始的高TD误差转移被经常重放，带有低TD误差的转移在第一次访问时不会被重放，引入了随机采样方法。该方法结合纯贪婪优先化和均匀随机采样，既保证被采样的概率是单一的，也能使低优先级样本采样概率非零。定义样本j的采样概率为

(19)

式中：n表示样本数量；α确定使用多少优先级，当α=0时为均匀采样。

2.4 样本的存储

由于优先级大小会影响被采样的概率，导致PERDDQN算法的经验重放池与其他采用Q学习的DRL算法不同。使用SumTree结构[26]作为带有优先级的经验重放池，用于样本的储存。SumTree结构示意图如图2所示。图中，圈外数字为节点序号，圈内数字为节点值，例如0号节点的节点值为29。图中阴影部分为叶子节点，所有的经验重放样本只保存在叶子节点上，一个节点对应一个样本。0号到2号节点不保存样本数据，只保存自己子节点的优先级值之和。叶子结点下面是样本对应的数值区间，叶子结点数值越大(优先级越高)其区间长度就越大。例如，从区间0～29中均匀抽样一个数据，5号节点的区间为14～26，优先级为12，比其他节点更容易被采样。

图2 SumTree结构示意图

2.5 网络参数的更新

从SumTree中采得样本后，使用均方差损失函数通过神经网络的梯度反向传播来更新Q网络的参数，并计算当前目标Q值。PERDDQN算法的损失函数L(θ)与当前目标Q值yj,PER的计算表达式分别为

PER以一种不受控的形式改变了分布，因此引入了误差，改变了预测会收敛到的解决方案。可以使用重要性采样权重来修正该误差[26]。

网络参数更新完毕后根据状态s′判断整个算法是否结束，若结束则输出最优的卸载决策。根据以上改进的DRL算法，结合MDP模型的MEC计算卸载策略的伪代码如下所示。

3 仿真与结果分析

3.1 实验环境选择及参数设置

为验证提出的DRL算法在MEC环境中的有效性，使用TensorFlow-GPU 1.13.1在Python3.7.4中实现了PERDDQN算法。验证算法的收敛性，并与本地执行(All Local Executing,ALE)、完全卸载(All Offload Executing,AOE)、随机卸载(Random Offloading Executing，ROE)、DDQN[19]和DDPG[20]等算法进行比较，验证在多用户MEC系统中的算法的总成本，反映算法的优劣。

仿真实验模拟的集群包括2个边缘服务器，5～30个移动用户设备。其中，移动用户设备随机分布在距基站150 m范围内，每个边缘服务器的计算能力设置为1 GHz～5 GHz。任务数据的随机大小为100 kb～500 kb。任务的最大可容忍时延在5 ms～30 ms随机选择。

对于深度强化学习算法，深度神经网络的输入包括状态值s(t)和动作值a(t)。在实验神经网络的构建中，将s(t)作为输入，输出层是每个a(t)对应的Q值。经验重放池容量为1 000，训练时采用贪婪法选择动作，贪婪策略概率为0.1，批学习大小为32，学习率为0.01，折扣因子γ=0.9。

3.2 算法的收敛性

PERDDQN算法、DDPG算法以及DDQN算法的收敛性能如图3所示。可以看出，3种算法的总奖励都随着迭代次数的增加而增加，直至达到一个相对稳定的值。当迭代次数为分别为50、75和100时，PERDDQN算法、DDPG算法和DDQN算法的奖励值不再增加并趋于稳定值，分别在-20、-25、-30左右。可见，PERDDQN算法是收敛的，且收敛速度比DDPG和DDQN快、奖励值也大于其他两种比较算法，这使得该算法能够更好地应对动态的MEC环境。

图3 3种算法的收敛性

3.3 系统成本

不同数量UE以及不同任务数据量大小的成本不同。6种算法的总成本如图4所示。可以看出，6种算法的总成本随着UE数量和任务数据大小的增加。这是因为，UE数量和任务数据越大，执行时间和传输时间就越长，处理具有较大数据量的任务所消耗的能量也更多。当UE数量为20时，应用PERDDQN算法的系统总成本为2.49，其余算法的系统总成本均超过3.00；当任务数据大小为500 kb时，应用PERDDQN算法的系统总成本为2.42，其余算法的系统总成本均超过2.80。由此可见，在UE数量和任务大小相同的情况下，PERDDQN算法的系统总成本始终是最小的，分别比未改进的DDQN算法减少了17.6%和23.0%。这是因为，与DDQN和DDPG算法相比，PERDDQN算法收敛速度更快，可以更快地获得最优策略，从而系统总成本较低，而ALE和AOE算法不能充分利用整个系统的计算资源，因此，具有较高的成本。

图4 6种算法的总成本

3.4 服务器计算能力对系统时延的影响

图5显示了使用不同的优化算法时，平均时延随MEC服务器计算能力的增加而变化的情况。由于ALE算法不涉及MEC服务器，因此不做讨论。除了ALE之外，其他方法的平均时延均随着MEC服务器计算能力的提升而逐渐降低，这是由于MEC服务器的计算能力逐渐满足所有UE卸载任务的计算需求。当MEC服务器计算能力为1 GHz时，PERDDQN算法、DDPG算法、DDQN算法的平均时延分别为14.01 ms、15.10 ms、16.90 ms；当MEC服务器计算能力增加为5 GHz时，PERDDQN算法、DDPG算法、DDQN算法的平均时延分别为8.21 ms、9.28 ms、9.71 ms。由此可见，与其他两种DRL算法相比，PERDDQN算法的任务卸载解决方案的平均时延较低。因为该算法频繁重放具有价值的样本数据，对于复杂的环境具有更好的适应性，在解决复杂的组合优化问题时的效果较好。

图5 不同MEC计算能力的平均时延

4 结语

针对多移动用户设备和多服务器的MEC环境，在满足用户最大容忍时延的前提下考虑了时延与能耗，提出了一种以最小化系统总成本为目标的任务卸载优化策略。将目标函数建模为MDP模型，提出基于PER改进的PERDDQN卸载决策算法。该算法利用PER对DRL算法进行改进，并对历史经验赋予优先级，优先采样高优先级的经验，以提高学习效率，快速、准确地做出合理的卸载决策。仿真结果表明，PERDDQN卸载决策算法的系统总成本较低、系统的平均时延较小。

研究基于单基站多用户的MEC模型，仅将任务作为一个整体卸载，实际中的MEC系统通常包含多个基站，高复杂度的计算任务也可进一步划分为更小的子任务进行卸载。因此，下一步工作将基于DRL对包含多个基站、多个移动设备MEC系统的细粒度任务卸载问题进行研究。