多接入边缘计算(MEC, multi-access edge computing)将边缘计算的接入方式从电信移动网络进一步延伸至其他无线接入网络(如WiFi)，并通过这项技术将网络控制、存储和服务推向网络边缘(例如基站和接入点)^[1]，移动设备可以通过异构无线网络接入MEC服务器，且接入侧都部署有计算资源，因此在对用户的计算任务进行卸载决策时需要综合考虑这些异构的通信和计算资源，优化资源调度，从而保证用户的使用体验^[2].近年来，一些研究工作对多用户MEC下的任务卸载策略及资源调度问题有许多研究成果.一些研究提出一个基于博弈论的分布式任务卸载方案，在优化能耗的同时使得用户间的博弈最终达到纳什均衡的状态，但是需要每个用户频繁地从MEC服务器获取通信资源和计算资源的信息，这将对移动设备形成很大的能耗负担^[3].另一些则考虑在多用户场景下利用分布式合作算法，并结合无线电力、MEC服务器资源分配和通信资源分配来减少用户的能耗和时延成本^[4-7].但是这些方式所造成的额外计算资源消耗和时延成本也很高.

在多用户场景下，MEC边缘侧的资源状态变化对任务卸载决策有很大的影响，可以通过将任务卸载决策导致的MEC边缘侧资源变化过程抽象为一个马尔可夫决策过程，根据资源变化情况制定任务卸载策略，任务卸载策略优化问题可以通过找到最佳的计算资源分配策略来解决，但是该优化问题是非凸的，并且MEC边缘侧资源的状态空间为无限大，强化学习这种启发式算法对于解非凸优化问题具有快速、高效的特点，同时利用深度神经网络可以很好地拟合资源环境的变化并学习强化学习作出的决策.因此，通过建立一个计算任务卸载和异构资源调度的联合优化模型，利用深度强化学习(DRL, deep reinforcement learning)的方法最小化移动设备的能耗、任务执行时延及用户付费，并综合考虑了2种异构的无线接入方式，即移动网络和WiFi，这样可以为用户提供更适合的通信和计算资源，同时该模型可充分利用神经网络的学习能力和泛化能力，随着用户任务数量的增多，算法生成的策略获得的收益将更高^[8].

1 系统模型

多接入边缘计算系统场景如图 1所示，用户设备可以将本地任务卸载到MEC服务器上运行来降低设备消耗^[9]，MEC服务器提供了移动网络和WiFi 2种无线接入方式，并且接入侧分别有V^cell和V^wifi个虚拟机来为用户服务^[10].集合表示为V^cell={V_n^cell:V^cell=1, 2, …, n}, V^wifi={V_m^wifi:V^wifi=n+1, n+2, …, m}.假设MEC服务器周围用户均有向MEC发送任务卸载请求，MEC可选择拒绝任务卸载请求或选择一种异构资源为用户提供服务，并且在一个任务卸载期间内，信道质量保持稳定.

1.1 通信模型

MEC服务器可以为接入侧周围的用户提供服务，这些有计算任务需要执行的用户用i(i=1, 2，…, N)表示，且每个用户在当前时隙内只有1个任务需要执行，用户i的任务表示为X_i，任务X_i的卸载决策表示为a_i, 即任务是卸载到MEC服务器执行还是在本地执行. a_i=0表示任务在本地设备执行，a_i>0表示任务卸载到MEC服务器执行该任务.任务决定卸载到MEC服务器执行时，需要选择接入方式，其中a_i∈V^cell表示任务通过移动网络卸载到基站侧MEC服务器执行，a_i∈V^wifi表示任务通过WiFi卸载到WiFi接入点侧MEC服务器执行，则用户卸载策略的集合为a_i={0}∪V^cell∪V^wifi.卸载决策为a_i>0的用户传输任务的传输速率为

$ {R_i}\left( A \right) = Clb\left( {1 + \frac{{{P_i}{H_i}}}{{{N_0} + \sum\limits_{j \in I,j \ne i} {{P_j}} {H_j}}}} \right) $

(1)

其中：P_i为设备的传输功率，N₀为信道内的高斯噪声功率，C={C^cell，C^wifi}为接入网络提供的带宽(接入移动网络时用C^cell表示，接入WiFi时C^wifi用表示)，H_i为MEC服务器与用户i之间信道的信道增益参数，从式(1)可以看出，当多个用户使用同一信道时，会使得数据的传输速率降低.

1.2 计算模型

假设MEC服务器接入侧周围的每个用户都有任务需要执行，用户i的任务可表示为一个三元组X_i={D_in(i), Y(i), D_out(i)}^[11]，D_in(i)表示任务的输入数据量，单位为(kbit)，Y(i)表示任务的负载量，单位为(cycle)，D_out(i)表示任务的输出结果数据量，单位为kbit.用户设备可通过应用调度图分析技术得到任务的三元组.在获得任务三元组后便可建立多用户任务卸载的本地计算模型和异构资源计算模型.

1.2.1 本地计算模型

当任务X_i在本地执行时，用f_i^l表示用户i的移动设备CPU频率，单位为(GHz)，T_i^l表示任务X_i在本地的执行时间，单位为(ms), 表示为

$ T_i^l = Y\left( i \right)/f_i^l $

(2)

任务X_i在本地执行时，η_i表示移动设备的计算能耗系数, E_i^l表示任务X_i在本地的执行的移动设备能耗，单位为(J), 表示为

$ E_i^l = {\eta _i}Y\left( i \right) $

(3)

根据式(2)和式(3)可得出任务X_i在本地执行时的消耗为

$ \begin{array}{*{20}{c}} {W_i^l = \alpha _i^tT_i^l + \alpha _i^eE_i^l}\\ {{\rm{s}}.\;{\rm{t}}.\;\;\alpha _i^t,\alpha _i^e \in \left[ {0,1} \right]} \end{array} $

(4)

α_i^t表示时延的权值，α_i^e表示能耗的权值，可以针对每个用户的需求来动态调整时延和能耗在总消耗中的比重，当用户任务对时延敏感时，可以调高α_i^t的值，当用户任务对能耗敏感时，则可以调高α_i^e的值.

1.2.2 异构资源计算模型

当任务X_i卸载到MEC服务器执行时，有2种异构资源可以提供服务：一种是通过移动网络接入MEC服务器端的虚拟机执行任务；另一种是通过WiFi网络接入MEC服务器端的虚拟机执行任务，f^s={f^cell, f^wifi}表示MEC服务器CPU执行频率(移动网络侧的MEC服务器CPU执行频率用f^cell表示，WiFi网络侧的MEC服务器CPU执行频率用f^wifi表示)，单位为GHz，T_i^s表示任务X_i在MEC服务器的执行时间，单位为ms.

$ T_i^s = Y\left( i \right)/{f^s} + \left( {{D_{{\rm{in}}}}\left( i \right) + {D_{{\rm{out}}}}\left( i \right)} \right)/R\left( a \right) $

(5)

当任务X_i卸载到MEC服务器执行时，P_i表示移动设备的传输功率，移动设备的传输能耗为

$ E_i^s = {P_i}\left( {{D_{{\rm{in}}}}\left( i \right) + {D_{{\rm{out}}}}\left( i \right)} \right)/R\left( a \right) $

(6)

当MEC服务器端的虚拟机数量不足时，上传的任务将进入等待队列，T_i^line表示任务X_i在MEC服务器的排队时间，表示为任务X_i之前执行的任务执行时间总和，单位为(ms)，T_j^s表示队列中在任务X_i之前执行的任务执行时间.

$ T_i^{{\rm{line}}} = \sum\limits_{j \in {\rm{queue}},j = {a_i}} {T_j^s} $

(7)

当任务X_i卸载到MEC服务器执行时，P_idle表示移动设备的传输功率，移动设备的空闲能耗为

$ E_i^s = {P_i}\left( {{D_{{\rm{in}}}}\left( i \right) + {D_{{\rm{out}}}}\left( i \right)} \right)/R\left( a \right) $

(8)

当任务X_i卸载到MEC服务器执行时，需要向选择的服务器付费，K_i为用户i所选择异构资源的价格，K_i∈{l₁, l₂}，l₁和l₂分别为移动网络接入侧资源和WiFi网络接入侧资源的价格.

$ {K_i} = \left\{ {\begin{array}{*{20}{l}} {{l_1},}&{{a_i} \in {V^{{\rm{cell}}}}}\\ {{l_2},}&{{a_i} \in {V^{{\rm{wif}}i}}} \end{array}} \right. $

(9)

综上所述，任务在MEC服务器执行时，任务X_i的能耗、时延、付费加权和为

$ \begin{array}{*{20}{c}} {W_i^s = \alpha _i^t\left( {T_i^s + T_i^{{\rm{line}}}} \right) + \alpha _i^eE_i^s + {\beta _i}{K_i}}\\ {{\rm{s}}.\;{\rm{t}}.\;{\beta _i} \in \left[ {0,1} \right]} \end{array} $

(10)

其中β_i表示用户对付费的敏感度.

2 MEC任务卸载与异构资源调度

在这一节中，将利用深度强化学习的方法对计算任务卸载和无线资源调度进行联合优化，达到最小化移动设备的能耗、执行时延及用户付费的目的.

2.1 深度强化学习概述

强化学习(reinforcement learning)属于一种无监督的机器学习方法，在与环境交互中进行学习，通过策略迭代学习最大化累计回报来获得最优策略.强化学习中智能体(agent)与环境交互的过程可借助马尔可夫决策过程可形式化表述为{S, A, P_a(s, s′), γ, R}, S表示状态空间，A表示动作空间，P_a(s, s′)表示在动作a下状态的转移概率，0 < γ < 1表示折扣因子，表示agent的远视程度，R表示即时回报函数.

agent从t₁时刻的状态s_t采取动作a_t状态转移到s_t+1并获得即时奖励r_t，价值函数Q^π(s, a)定义了策略π在状态s下作出动作a所获得的期望回报，表示为

$ {Q^\pi }\left( {s,a} \right) = E\left[ {{r_t}|{s_t} = s,{a_t} = a,\pi } \right] $

(11)

当策略π对于所有状态都能使期望回报最大时，策略π为最优策略，最优策略的价值函数为

$ {Q^*}\left( {s,a} \right) = \mathop {\max }\limits_\pi E\left[ {{r_t}|{s_t} = s,{a_t} = a,\pi } \right] $

(12)

当状态和动作空间数量很大时，使用Q表存储状态动作对的概率是一种很低效的做法，因此使用深度神经网络拟合Q表来产生动作，使得相近的状态可以得到相近的动作，其模型的优化目标函数为

$ H\left( \theta \right) = E\left\{ {{{\left[ {r + \gamma \mathop {\max }\limits_{{a^\prime }} Q\left( {{s^\prime },{a^\prime }|\theta } \right) - Q\left( {s,a|\theta } \right)} \right]}^2}} \right\} $

(13)

其中:γ为折扣因子，θ为神经网络模型的权重参数，θ值的更新使用随机梯度下降算法.

在多用户MEC场景中，基于深度强化学习的MEC计算任务卸载与异构资源调度算法(DRL-COHRS)框架如图 2所示.

2.2 状态空间

利用深度强化学习算法对系统环境进行建模的第1步是定义环境模型的状态空间，在定义中要同时考虑MEC服务器侧的资源使用状况和用户的接入方式.环境模型的状态空间由移动网络带宽、WiFi带宽和接入侧虚拟机数量组成，状态空间定义为

$ S = \left\{ {s_1^{{\rm{cell}}},s_2^{{\rm{cell}}}, \cdots ,s_n^{{\rm{cell}}},s_{n + 1}^{{\rm{wifi}}}, \cdots ,s_m^{{\rm{wifi}}}} \right\} $

(14)

s_i^cell代表移动网络接入侧的虚拟机任务队列状态，该虚拟机的CPU频率为f^cell，s_i^wifi代表WiFi网络接入侧的虚拟机状态，该虚拟机CPU频率为f^wifi.

2.3 决策时刻和动作空间

在MEC的场景下，卸载决策的时刻为当有新用户向MEC服务器发出卸载请求的时刻.此时，卸载决策的动作空间可表示为

$ a = \left\{ {0,1,2, \cdots n, \cdots ,m} \right\} $

(15)

其中:a_i=0表示拒绝卸载请求，任务在本地执行；a_i>0表示接受卸载请求；0 < a_i≤n表示任务通过移动网络卸载到MEC服务器；n < a_i≤m表示任务通过WiFi卸载到MEC服务器，当动作为卸载到MEC服务器执行时，则MEC服务器会提供一定的带宽资源和计算资源来执行任务.

2.4 即时回报

即时回报是在某一系统状态下做出某一动作后环境给予的反馈值，表示在该状态下采取特定动作的好坏程度.设定A=[a₁, a₂, …, a_N]为所有用户的卸载策略的决策向量，目标是作出合理的决策向量最小化所有用户设备能耗、时延和付费：

$ \begin{array}{*{20}{c}} {\mathop {\min }\limits_{A = \left\{ {{a_1}, \cdots ,{a_N}} \right\}} \sum\limits_{{a_i} = 0} {\alpha _i^t} T_i^l + \alpha _i^eE_i^l + }\\ {\sum\limits_{{a_j} \ne 0} {\alpha _j^t} \left( {T_j^s + T_j^{{\rm{line}}}} \right) + \alpha _j^eE_j^s + {\beta _j}{K_j}} \end{array} $

(16)

其中：用户对于能耗、时延和付费设定的权重因子分别为α_i^t、α_i^e和β_i，结合式(4)和式(9)奖励函数建模为

$ r\left( {S,{a_i}} \right) = \left\{ {\begin{array}{*{20}{l}} { - W_i^l,}&{{a_i} = 0}\\ { - W_i^s,}&{{a_i} \ne 0} \end{array}} \right. $

(17)

强化学习算法的目标是最大化累计折扣回报的期望，即最小化所有用户设备能耗、时延和付费的加权和，表示为$\max E\left[ {\sum\limits_{i = 0}^N {{\gamma ^i}} {r_i}} \right]$, γⁱ为折扣因子，表示对每个任务卸载决策的即时回报的权重，设置为1，表示每个任务的即时回报对总回报的贡献权值是一样的.

2.5 基于深度强化学习的MEC计算任务卸载与异构资源调度方法

基于深度强化学习的MEC计算任务卸载与异构资源调度方法(DRL-COHRS)的训练过程如算法1所示：S为状态空间，a为动作空间，θ为神经网络的参数，rand( )为随机生成探索新策略的概率，ε为接受探索新策略的阈值. rand(a)在动作空间a中随机选择一个动作，env(a_t)表示环境对执行动作a_t后返回的即时奖励和新的状态.

算法 1  基于深度强化学习的MEC计算任务卸载与异构资源调度方法实现

1 初始化深度神经网络Q，权重参数θ

2 初始化深度神经网络Q′，权重参数θ′=θ

3 初始化样本存储池D

4    for episode=1，M do

5      初始化深度神经网络输入S₁，即当前接入侧的虚拟机任务队列状态，并通过深度神经网络输出一组卸载策略A

6    for t=1, N do

7      if rand( )>ε then

8        a_t=rand(a)

9      else

10        a_t=arg maxaQ(S_t, a|θ)

11      S_t+1, r_t←env(a_t) //执行动作a后，返回环境所给的奖励

12      存储(S_t, a_t, r_t, S_t+1)到D中

13       随机采样D中minibatch个样本(S_j, a_j, r_j, S_j+1)

14 ${y_j} = \left\{ {\begin{array}{*{20}{l}} {{r_j}, \;\;\;\;j = N}&{}\\ {{r_j} + \sum\limits_{i = j + 1}^N {{\gamma ^{i - j}}} \max {Q^\prime }\left( {{S_i}, a_i^\prime |{\theta ^\prime }} \right), }&{j < N} \end{array}} \right.$

15       以(y_j-Q(S_j, a_j|θ))²作为损失函数通过SGD更新θ

16       每隔C步更新Q网络参数为当前网络参数

17    end for

18 end for

3 仿真结果与分析

通过仿真对DRL-COHRS算法与分布式协作算法(DCCO, distributed cooperative computation offloading)^[6]、银行家算法(Bank)、优化控制算法(OACP, optimal admission control policy)^[7]进行了实验对比，仿真参数如表 1所示.

Q表的拟合函数为包含2个隐藏层的全连接神经网络，输入层的维度为7，2个隐藏层的神经元个数分别为256和128，输出层的维度为m，使用Relu函数作为激活函数，并使用L2正则化来防止模型过拟合.训练时采用策略迭代的方式进行训练，仿真实验中动作的选择策略为ε-greedy策略.在训练过程中，ε初始值为1，每迭代50次ε减小0.1，降低至0.1后保持不变，一直以10%的概率进行探索.

深度强化学习中拟合Q表的神经网络模型是后续仿真实验的基础，经过训练才能更好地拟合环境给出的回报及最优策略.根据表 1中任务参数生成1 500个任务，分为10个批次, 其中8个批次作为训练集训练模型，2个批次作为测试集来验证模型的性能.同时在训练集上分别训练能耗、时延和费用的权重依次为{0.1, 0.5, 0.9}的DRL-COHRS算法模型. 图 3为训练过程，可以看出，在训练初期，由于动作的随机选择概率ε比较大，agent处于探索学习阶段，总回报值较低，随着迭代次数的增加，agent由探索学习状态转为利用经验状态，算法快速收敛，总回报值趋于稳定.

图 4所示分别为训练集和测试集中不同算法卸载任务数，用户选择的能耗、时延和费用的权重从集合{0.1，0.5，0.9}中随机选择.从图中看出，随着任务数的增加，OACP算法和DRL-COHRS算法的卸载任务数都在增加，Bank算法在任务数大于20后不再增加，这是因为移动网络和WiFi网络接入侧的虚拟机总数为20，当任务数大于20时，Bank算法便不再进行卸载. OACP算法、DCCO算法和DRL-COHRS算法随着任务数的增加，卸载任务数占总任务数的比例在下降，这是由于任务数增加后，信道干扰增大，信道传输速率下降，传输消耗增大，导致在本地执行任务时总消耗更低. DRL-COHRS算法相比于OACP算法、DCCO算法，不仅考虑了用户信道之间的干扰，还考虑了等待时延和空闲能耗，当任务数量增加时等待时延和空闲能耗都会增大，所以选择卸载的任务数量会比OACP算法、DCCO算法少.

图 5所示为训练集和测试集中不同算法用户的平均回报，用户选择的能耗、时延和费用的权重从集合{0.1, 0.5, 0.9}中随机选择.从图中看出，Bank算法的平均回报在任务数大于20后呈现线性下降，这是由于大量任务在本地执行导致时延和能耗增加从而导致回报线性下降.其他3个算法的平均回报都随着任务数的增加而降低，这是由于任务数量的增加引起传输能耗和等待时延的增加.由于OACP算法只针对当前一个任务进行优化，有陷入局部最优解的问题，导致平均回报低于DRL-COHRS算法. DCCO算法没有对用户付费进行优化，所以整体回报也低于DRL-COHRS算法.结合图 4可以看出，DRL-COHRS算法可以自适应任务的数量及MEC服务器状态，为用户选择合适的卸载策略，有效降低能耗、时延和付费.

4 结束语

提出了一种基于深度强化学习的MEC任务卸载与异构资源优化算法，目标是最大化设备能耗、时延和付费的综合奖励指标，建立了一个联合计算任务卸载和资源调度的优化模型，并在此基础上将MEC边缘侧资源变化过程构建为一个马尔可夫过程决策过程，然后利用深度强化学习对MEC系统环境进行学习，并不断优化卸载决策，最后利用生成的模型对任务卸载作出决策.仿真结果表明，DRL-COHRS算法对MEC场景下计算任务的卸载决策是非常有效的，使设备能耗、时延和付费的综合指标得到了大幅度的提高.未来的研究工作主要包括加入对移动设备无线信道传输功率的控制及用户切换异构资源的考虑等.