基于深度强化学习的多基站计算卸载策略

葛海波，陈旭涛，刘林欢，李 顺

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

0 引 言

过去十年移动通信设备和移动应用程序快速发展成为人们生活中不可或缺的一部分。手机、掌上电脑等设备为用户提供多种数字服务如增强现实[1]、虚拟现实[2]等，这些任务往往需要大量的计算资源和较高的服务质量。移动设备由于自身的电池和计算能力的限制，计算任务需要通过网络传输到远程服务器，经过处理后传回移动设备，这就是云计算[3]。由于移动设备的数量疯狂增长和网络带宽资源的不足，这种方法存在较高的延迟和不稳定性。针对这些问题，移动边缘计算[4](mobile edge computing，MEC)应运而生。MEC将移动用户所需的计算资源下沉到接近用户的位置，在移动设备附近部署边缘服务器，MEC网络中的移动设备可以将其任务卸载到附近的边缘服务器，并在处理后立即收到结果。

现在我们已经进入到第五代(5G)移动网络，需要进行超密集组网(ultra-dense network，UDN)部署超密集小蜂窝网络。每个移动设备的通信范围内会有密集的小型基站，可以为MEC网络提供边缘服务器和通信条件[5]。然而当移动设备附近有多个MEC服务器时，移动用户的计算任务是否需要卸载？如何进行卸载？选择哪个MEC服务器进行卸载？不同的卸载决策会导致移动设备的不同服务质量。因此，如何在密集基站下对移动设备进行卸载决策制定非常重要。当大量的计算任务卸载到同一个边缘服务器时，会造成信道堵塞，服务器负载过高，导致任务的处理时间和等待时间更长造成较差的服务质量。因此我们在考虑卸载决策的制定时，不可简单将计算任务卸载到距移动设备较近的边缘服务器，需要充分考虑移动设备、边缘服务器计算能力、信道带宽大小等。

1 相关工作

考虑MEC网络单边缘服务器。对于单个移动用户的MEC网络，文献[6]建立了以分时传输和截止时间为约束条件的优化问题，最小化系统总能耗，使用块坐标下降法求解优化问题。文献[7]联合优化了无线电和计算资源的分配，最小化用户的能量消耗。对于具有多个移动用户的MEC网络，文献[8]针对资源受限的MEC卸载问题，联合时延、能耗及卸载费用建立卸载效益模型，提出一种基于遗传算法优化的卸载决策与计算资源分配方法对其进行求解。文献[9]提出了一种基于分布式深度学习的卸载算法，可以有效地为该MEC网络提供几乎最优的卸载决策。文献[10]研究了具有能量收集功能的多用户MEC系统中的能耗问题，将电池队列稳定性和服务质量约束下的功耗最小化问题表示为随机优化程序，使用李雅普诺夫优化方法解决稳定性约束问题。

考虑到具有多个边缘服务器的MEC网络。文献[11]为提高移动边缘计算任务卸载方案性能，构建云、边、端三层MEC网络架构，提出一种基于二进制粒子群优化算法的任务卸载策略。文献[12]考虑了具有多个边缘服务器的MEC系统，并提出了两种方法，基于线性松弛和基于半定义松弛的方法来最小化总任务的执行延迟和用户的能量消耗。文献[13]还考虑了多个边缘服务器的情况，得到了服务器之间的最优计算分布。

我们根据表1中的任务、用户和服务器的数量对这些相关工作进行了分类。

表1 移动边缘计算中计算卸载的相关工作

上述研究部分考虑的是单边缘服务器对行单一任务卸载的情况，部分考虑了多边缘服务器对多用户进行多任务或单任务卸载的情况，但是都没有考虑到基站重复区域下用户的边缘计算服务器选择问题以及多用户多任务的卸载问题。本文针对多基站、多用户、多任务场景，提出了用户基站选择、卸载决策联合优化算法。针对该场景下的用户基站选择，本文采用基于博弈论的匹配算法，在得到用户接入的基站以及卸载问题的优化目标后，采用基于深度强化学习的双延迟深度确定性策略梯度(twin delayed deep deterministic policy gradient，TD3)算法对其求解。仿真结果表明本文所提出的与匹配博弈论结合的双延迟深度确定性策略梯度(game theory-twin delayed deep deterministic policy gradient，GT-TD3)算法能有效降低用户进行任务卸载时的能耗及时延。

2 系统模型

如图1所示，我们考虑由边缘服务器(基站)K，移动用户N组成的MEC网络。我们假设每个移动用户有独立的任务M，其中每个任务可以由移动用户进行本地计算，或者卸载到边缘服务器处理。我们将移动用户的集合表示为N={1，2，3，…，N}， 任务集合为M={1，2，3，…，M}， 边缘服务器集合为K={1，2，3，…，K}。

图1 系统模型

卸载决策变量αnm∈{0，1} 表示用户N是否决定卸载其中任务M，αnm=1表示用户N决定将其任务M卸载至边缘服务器，αnm=0表示用户N中的任务M只能在本地终端进行处理。用户N将任务M进行卸载时需要在基站K中选择一个作为其任务处理基站，定义K=(k1，k2，…，kn×m) 为用户需要卸载时的最佳服务器列表。

假如用户N选择将任务M进行卸载处理，则其接入基站k的数据传输速率表示为

(1)

式中：移动用户向基站k发送计算任务数据时的高斯白噪声为σ2；移动用户与其连接的基站k之间的信道带宽为Bk；移动用户向基站k传输计算任务数据时的功率为Pnk；通信信道增益为hnk。

2.1 计算模型

(1)本地计算

(2)

(3)

本地计算总花费表示为

(4)

其中，λ1和λ2表示为完成用户N任务M的时延和能耗成本的权重。任务计算过程中权重保持不变，0≤λ1≤1、 0≤λ2≤1、λ1+λ2=1。

(2)卸载计算

移动用户N选择将计算任务M进行卸载处理，则所消耗时间分为3部分：计算任务M上传时间、MEC服务器处理任务M时间、处理结果回传到移动用户时间。通常情况处理结果远小于计算任务上传大小，所以忽略第三步所耗时间。

根据上述步骤，卸载计算第一步所需的时间是传输时延

(5)

完成第一步的能耗为

(6)

对于卸载计算的第二步所需时间为MEC服务器的计算任务M的时延

(7)

其中，fnmk是边缘计算服务器为计算任务M所分配的计算资源。

(8)

根据式(5)～式(8)用户N将其任务M进行卸载计算所需的时延和能耗分别为

(9)

(10)

结合时延和能耗公式可以得出卸载计算的总花费为

(11)

最后可以得出MEC系统计算任务M的总代价为

(12)

2.2 优化问题

将MEC系统的卸载决策向量和资源分配向量结合得到一个优化问题。优化目标是最小化所有任务的总延迟以及执行这些任务的总能耗。该优化问题如下

(13)

在求解这个优化问题之前，我们首先需要计算出用户与基站的最佳匹配关系即用户最佳卸载服务器策略K=(k1，k2，…，kn×m) 将其代入到优化问题(13)中，这样可以将该优化问题改写为

(14)

其中，A={α11…，α1M，α2M，…，αNM} 为卸载决策向量，F=(f1，f2，…，fN) 为边缘计算服务器的资源分配向量。约束C1表示无论是通过本地计算还是卸载计算处理其计算任务，计算时间都不可以超过最大可容忍时延；约束C2表示计算任务只能在本地计算或者卸载到服务器进行计算；约束C3表示分配给处理每个任务的计算资源都是非负的；约束C4表示分配到所有任务的总体计算资源小于所有MEC服务器的计算资源之和。P定义为所有服务器的计算资源之和。

3 基于博弈论的用户与服务器匹配策略

在MEC系统中移动用户往往会选择距离较近的边缘计算服务器进行卸载，但是这种情况会使边缘计算服务器群中一部分服务器负载较高，另一部分服务器空载，这样会降低移动用户的服务质量。为了让系统的总花费在约束条件下达到最小，我们需要让移动用户与基站之间达到最佳的匹配。

匹配博弈论是一种非常有效的方法，可以让两个参与者在某种条件下达成有利于双方的策略。移动用户N和边缘服务器K往往会在有利于自身条件的情况下选择用户任务或服务器进行任务卸载，应用匹配博弈论可以使双方在某些限制条件下达到双赢，找到对移动用户及边缘服务器都有利的匹配策略[14]。在本文的MEC网络系统中，移动用户只可选择一个服务器进行卸载，边缘服务器可以接收多个用户的卸载请求。定义移动用户n与边缘服务器k满足以下条件

(1)ψ(n)∈Kn
(2)ψ(k)∈N
(3)ψ(n)≤1
(4)k∈ψ(n)⟺n∈ψ(k)

(15)

条件(1)表示移动用户n所连接的服务器属于边缘计算服务器Kn之一；条件(2)表示连接到服务器k的用户n必须是所有移动用户N中的某一位；条件(3)表示移动用户与服务器必须保证一对一连接；条件(4)表示移动用户可以选择边缘服务器同样边缘服务器也可以选择用户建立连接。

在移动用户与移动边缘计算服务器进行匹配时需要考虑到移动用户和服务器自身的偏好因素，为了达到最佳匹配需要根据各自偏好因素进行匹配。

移动用户效用函数：移动用户在多个服务器中选择卸载时，会综合自身情况比如用户与基站之间的距离、信道带宽、环境中噪声干扰等。用户会首先选择信道带宽较高、干扰较少，传输速率相对最快的服务器，这样可以降低卸载计算中第一步的时延

(16)

边缘计算服务器效用函数：移动用户与边缘计算服务器的选择是双向的。服务器在选择用户时，为了有效降低系统的总花费，会选择卸载任务较小的用户。这样可以降低服务器处理任务的时间，并且可以降低后续卸载任务的等待时间

(17)

多基站博弈算法具体描述如下：

多基站博弈算法具体实现步骤见表2。

4 基于深度强化学习的卸载策略优化算法

由于优化变量之间的耦合关系，必须将原始问题分解为子问题，然后利用一些替代的凹面搜索算法来解决这些问题。然而，由于子问题之间的交替处理，导致解决时间过长，随着MEC服务器服务区域下的用户数量和任务数量的增加，求解时间将进一步增加。因此，我们将上述问题建模为马尔可夫决策过程(Markov decision process，MDP)，然后采用深度强化学习(deep reinforcement lear-ning，DRL)方法进行求解。DRL体系结构由代理和环境相互交互组成。该代理由安装在每个MEC服务器上的控制器实现，并且控制器之外的所有内容都被视为环境。通过学习最佳策略(称为将环境状态映射到资源分配决策的资源分配策略)以最大化累积的总奖励，可以直接解决上述问题。

本文建模了多用户多任务多服务器移动边缘计算系统中任务卸载、服务器资源分配问题，目标是最大化用户对服务的体验质量，最小化移动用户成本。由于这是一个混合整数非线性规划问题，为了求解这个问题，本节提出一个基于TD3算法的多基站多用户卸载算法，最小化移动用户总花费。

TD3算法是一种面向连续动作空间基于Actor-Critic架构的深度强化学习算法[15]，在深度确定性策略梯度(deep deterministic policy gradient，DDPG)算法基础上，对policy网络和value网络进行改进，优化了Q-Value的过高估计问题。算法由Critic网络和Actor网络组成。TD3算法框架如图2所示。

图2 TD3算法框架

TD3算法中定义四元组 (S，A，rt，γ)， 把连续的时间分为离散的多个时刻t，每个状态s都储存在状态空间集合S中，每个动作都储存在动作空间集合A中，rt表示当前时刻的奖励。每个时刻采用π策略的智能体都会根据状态s选择相应的动作a，然后与环境交互，得到这一步的收益r，以及下一步的状态s′。总回报被定义为收益的折扣总和

(18)

γ∈(0，1) 是一个用于确定短期奖励优先级的折扣因子。

考虑到必须处理连续的本地执行权和卸载传输权，因此采用确定性策略，将动作-状态值函数的Bellman方程写为

Qπ(s，a)=E[r(s，a)+γQπ(s′.μ(s′))]

(19)

为了最大化长期预期的折价报酬，采用相同的时差方法以直接从原始经验中学习，我们可以在每个时间步长t处更新状态-作用函数

Qπ(s′，a′)=Qπ(s，a)+α(r(s，a)+γQπ(s′，a′)-Qπ(s，a))

(20)

式中：r(s，a)+γQπ(s′，a′)-Qπ(s，a) 表示时间差误差，0<α<1表示学习率。

TD3算法使用单独的DNN网络来分别近似Critic网络的估值函数Qθ1，Qθ2和Actor网络中的策略函数πφ。

为了避免估值函数对Q值的过高估计，选择两个估值函数中较小的作为估计值

(21)

在计算Q值时，给Action目标网络加入一个小的随机噪音ε，并采取截断来避免其过多的偏离原始值，经过多个采样后这些噪音会取得近似的平均，在加入噪音后，对干扰因素的抵抗力更强，Critic就能给出更高的Q值，从而让策略输出的更加稳定平滑

(22)

(23)

在Critic网络中，使用时差误差法更新参数θ其损失函数定义为

L(θ)=argminθN-1∑(y-Qθ(s，a))2

(24)

最小化L(θQ) 对Critic网络进行更新。Q(s，a) 代表在s状态下执行动作a得到的最大未来回报。r(s，a) 是在s状态下执行动作a得到的环境所给的现实奖励。Q(s′，π(s′)|θ) 表示在s状态下执行动作a到达下一状态s′后，继续执行下一动作π(s′)，得到的下一个状态s′的最大未来回报。y表示在s状态下执行动作a后，得到的最大未来回报。

将优化问题中各项参数转化为马尔可夫决策过程的三元组 (S，A，R)。S={dnm，cnm，fnmk，P}，A={α11…，α1M，α2M，…，αNM，f1，f2，…，fN} 分别表示状态空间和动作空间。优化问题是求解总成本最小化而强化学习目标是最大化奖励，所以奖励函数R为系统成本加权和的相反数R=-Z。

GT-TD3算法具体步骤见表3。

表3 GT-TD3算法执行流程

5 仿真实验分析

采用python仿真平台对本文所提出的算法进行仿真分析验证。考虑到多用户多基站的移动边缘计算场景，所设环境中用户随机分布信道建模采用l-α， 其中l为用户到基站的距离，α为路径损耗因子，此处取α=3[16]。优化目标中的能耗和时延权重为λ1=λ2=0.5。 MEC服务器的计算能力为10(GHz)，MEC服务器计算1 bit数据所需周期数为200/bit；假设移动用户设备的计算能力相同，移动用户设备的计算能力为1(GHz)，计算1 bit数据所需的CPU周期数为1000/bit。其它仿真参数设置见表4。

表4 参数设置

本文所求系统开销为用户处理任务的时延和能耗的加权和，因此开销无量纲。为验证算法优劣性，将本文所提出算法与TD3算法、LOCAL(用户在本地尽可能多贪婪地执行任务)算法、OFFLAND(用户尽可能多贪婪地将任务卸载执行)算法和DDPG算法在不同场景下进行比较。

图3是在移动设备用户数量不断增加时，LOCAL算法、OFFLAND算法、TD3算法和本文所提出的GT-TD3算法的性能比较。系统中基站内的MEC服务器计算能力为10 GHz，可接入基站数量为15，用户数量从10增加到70。可以看出随着用户数量的增加，系统的总花费呈现上升趋势，在相同用户数量的情况下，本文所提出的GT-TD3算法的系统总花费最小。在用户数量较少时，OFFLAND算法的总花费明显低于LOCAL算法，相较于DDPG算法略高。当用户数量逐渐上升时，OFFLAND算法总花费迅速升高，这表明在用户数量较多的情况下，MEC服务器无法在最大可允许时延条件下完成任务，无线信道也会变得十分拥挤，仅用MEC服务器无法提供有效的计算卸载服务，所以选择合适的卸载决策十分重要。

图3 系统总花费与用户数量的关系

图4是在移动用户可连接基站数量不断增加时，LOCAL算法、OFFLAND算法、TD3算法和本文所提出的GT-TD3算法的性能比较。系统中基站内的MEC服务器计算能力为10 GHz，移动设备用户数量为30，基站数量从5增加到25。可以看出在基站数量为5时，TD3算法和本文所提出的GT-TD3算法的总花费基本相近，OFFLAND算法和LOCAL算法所花费较大，其中LOCAL算法在基站数量不断上升时系统总花费不变。这是因为贪婪本地卸载计算时不将任务卸载到MEC服务器，所以无论可接入基站数量如何变化其系统总花费保持不变。随着可接入基站数量的不断增加，OFFLAN算法和TD3算法和GT-TD3算法的系统总花费呈下降趋势，这是因为更多的基站和服务器选择使得用户的卸载任务可进行卸载处理的最佳服务器的选择更好，使得系统的总花费不断减小。

图4 系统总花费与基站数量的关系

图5是在移动设备用户所需要处理的任务数量不断增加时，LOCAL算法、OFFLAND算法、TD3算法和本文所提出的GT-TD3算法的性能比较。系统中基站内的MEC服务器计算能力为10 GHz，可接入基站数量为15，移动设备用户数量为10，用户所需要处理的任务数量从10增加到50。可以看出随着任务数量的增加，系统的总花费也在逐步上升。这是因为在移动设备用户数量和MEC服务器计算能力保持不变时，随着任务数量的增加，无线信道干扰增大，信道传输效率下降，这样不可避免地导致较长的传输时间和较高的能耗，系统总花费随之升高。本文所提出的GT-TD3算法在4种算法中的系统总花费为最小，这是因为本文提出的算法可以在用户所有可接入的基站中预先选择出最佳基站，每个用户的任务都最佳分配给基站中的MEC服务器，不会造成用户的任务在需要进行卸载处理时还需等待基站中MEC服务器处理上一个用户的任务，这样可以很好地降低系统的总花费。

图5 系统总花费与任务数量的关系

图6是在移动设备用户所需要处理的计算任务大小不断增加时，LOCAL算法、OFFLAND算法、TD3算法和本文所提出的GT-TD3算法的性能比较。系统中基站内的MEC服务器计算能力为10 GHz，可接入基站数量为15，移动设备用户数量为10，用户所需要处理的任务数为15，任务的大小从300增加到1500。可以看出随着用户发送任务的数据逐渐变大时，系统处理这些任务的总花费呈现全体上升趋势。由于任务的数据变大，无线信道接收数据，系统处理数据需要花费更多的能量和时间，从而导致系统总花费升高。其中LOCAL算法在任务较大时所需的总花费明显高于另外3种算法，这是由于移动设备本身的处理能力时有限的在任务大小一直增加时其所需要的总花费相对于其它算法上升地更快。这表明，在任务数据量较大时，对任务进行卸载处理收益较高。

图6 系统总花费与用户任务数据大小的关系

6 结束语

随着5G超密集基站的部署，移动用户在进行卸载计算时面临基站选择问题。针对多用户、多基站场景下移动用户的计算卸载及资源分配问题，本文提出一种与匹配博弈论相结合的双延迟深度确定性策略梯度算法GT-TD3。以最小化MEC系统总代价为优化目标，首先运用多基站博弈算法解决用户与基站互相匹配问题，然后使用TD3算法对优化问题进行求解，得到最优的卸载策略。仿真结果表明本文所提出的算法相较于4种对比算法可以有效减小MEC系统总花费。并且随着MEC系统中可接入基站数量增多，本文算法的总花费会逐渐减小。

深度强化学习算法由于深度神经网络导致所占内存空间较大，如何减小其所占内存空间，加速算法迭代，使其可以更加方便地在MEC服务器中进行部署，这将是下一步的研究重点。