移动设备随机任务的迁移算法在MEC(mobile-edge computing)系统中扮演着重要的作用，决定着移动设备的计算效率和计算性能^[1].近年来一些研究将一个确定的任务划分为一组有数据依赖关系的计算组件，通过一些优化策略将部分计算组件迁移到MEC服务器，加快移动设备任务的执行，同时节约能耗^[2].然而，确定任务的优化策略不适用于真实多任务环境下任务随机到达时最优迁移策略生成的问题.另一些研究考虑多个独立的随机任务调度迁移策略的优化，通过将到达但是尚未执行的任务暂存入缓存队列，利用马尔可夫决策过程(MDP, markov decision process)理论、lyapunov优化技术或者博弈论理论等对系统建模，生成任务迁移策略来最小化移动设备能耗和执行时延^[3-4].但是，在真实场景中，部分任务由于需要与用户交互或者访问本地I/O设备等原因无法迁移到MEC服务器，导致其执行效率无法达到预期.笔者提出了一种基于机器学习的随机任务迁移算法，通过将确定任务划分为N个与系统调用无关的可迁移组件和2个需要进行系统调用的不可迁移组件，利用深度学习算法和强化学习中Q学习算法可以在真实环境下高效生成随机任务最优迁移策略.该算法充分利用机器学习算法的学习能力和泛化能力，随着处理任务数量的增多，通过持续的训练神经网络，不断提升其产生策略的精度.

1 系统模型

考虑单用户MEC系统中移动设备随机多任务场景下的任务调度问题，单用户MEC系统包含1个移动设备和1个MEC服务器，如图 1所示.其中移动设备运行多个计算密集和时延敏感的独立应用，由MEC服务器辅助执行计算任务. MEC服务器部署在移动接入网络侧，通过无线信道与移动设备通信.移动设备包含2个逻辑执行单元：本地中央处理器(CPU, central processing unit)和传输单元，设备可以通过一定的策略将应用的一部分计算任务置于本地执行，一部分发送到MEC服务器执行，加快任务执行速度的同时节约移动设备的电池电量.

1.1 任务模型

假设移动设备有M个独立的计算任务在缓存队列中等待处理，将这个队列用符号表示为Q={T₁, T₂, …, T_i, …, T_M}，其中每一个计算任务分为2个不可迁移组件和N个可迁移组件，表示为T_i={C₀, C₁, …, C_j, …, C_N, C_N+1; u_j}，其中：T_i为第i个计算任务，C₀与C_N+1为不可迁移组件，C₁~C_N为可迁移组件，u_j为该任务执行1 bit数据需要的CPU转数^[4].不可迁移组件主要由于任务开始执行和执行结束后需要调度系统驱动或显示设备等原因必须在设备端执行，如果有多个不可迁移组件，可将其合并为2个部分.对于可迁移组件，设定其组件数为N，便于对任务建模.如果一个任务可迁移组件数小于N, 可以将多余组件数据置0；如果一个任务可迁移组件数大于N，可合并相关组件使组件数等于N.任务的第j个组件表示为C_j={n_j, w_j}，其中：n_j为该组件的总输入数据量；w_j={0，1}为任务执行指示器，w_j=0表示任务在移动设备CPU执行，w_j=1表示任务迁移到MEC服务器执行.对于一个确定的计算任务，将任务分为N+2个组件的同时必须考虑各个组件之间的数据相关性，为便于建模，构建确定任务组件的数据依赖关系为平行依赖关系^[5]，如图 2所示，即2个不可迁移组件在移动端执行，其他可迁移组件选择性地在移动端执行或迁移到MEC服务器端执行，在之后的研究中会扩展到一般依赖关系的任务建模.

1.2 计算模型

假设移动设备配备单核CPU和一个数据传输天线，在执行一个任务时，CPU执行频率为f_loc，并且其功率为P_loc.移动设备传输单元一次传输一个任务组件，其无线发射功率为P_tx，根据香农公式，信道最大数据传输速率^[3]可以表示为

$R\left(p_{\mathrm{tx}}\right)=\omega \operatorname{lb}\left(1+\frac{g_{0}\left(L_{0} / L\right)^{\theta} P_{\mathrm{tx}}}{N_{0} \omega}\right) $

(1)

其中：ω为系统信道有效带宽，L₀为参考距离，g₀为参考距离损失常量，θ为路径衰减指数，L为移动设备与MEC服务器的距离，N₀为信道高斯噪声功率.

假设MEC服务器的CPU频率为f_ser，数据处理和传输均需排队，计算资源充足，可同时处理多个任务组件而无需排队，不需要考虑MEC服务器上的等待时延，并且假定计算结果很小，可以忽略反馈时延.因此，任务T_i的可迁移组件完成时延t(m_t)可以表示为

$ t\left( {{m_t}} \right) = \max \left\{ {\begin{array}{*{20}{l}} {\sum\limits_{j = 1}^N {\frac{{\left( {1 - {w_j}} \right){n_j}{u_j}}}{{{f_{{\rm{loc}}}}}}} , \quad {\rm{LCU}}为0}\\ {\sum\limits_{j = 1}^N {{w_j}} \left( {\frac{{{n_j}{u_j}}}{{{f_{{\rm{ser}}}}}} + \frac{{{n_j}}}{{R\left( {{p_{{\rm{tx}}}}} \right)}}} \right), \quad {\rm{LCU}}为1} \end{array}} \right. $

(2)

其中：m_t表示任务可迁移组件当前所处的状态；逻辑计算单元(LCU, logic computing unit)为0表示移动设备计算单元，其时延为移动设备计算单元的计算时延；LCU为1表示MEC服务器计算单元，其时延为任务组件传输时延与MEC服务器计算时延之和.在处理任务T_i时，2个LCU并行计算，故取时延较大者作为S_t状态下任务编号为1-N组件的整体计算时延t(m_t).任务T_i整体计算时延表示为

$ t\left(S_{t}\right)=\frac{n_{0} u_{0}}{f_{\mathrm{loc}}}+t\left(m_{t}\right)+\frac{n_{N+1} u_{N+1}}{f_{\mathrm{loc}}} $

(3)

其中S_t表示任务T_i所有组件当前所处状态.

相应地，移动设备执行单个任务的能耗表示为

$ e\left( {{m_t}} \right) = {\mathop{\rm sum}\nolimits} \left\{ {\begin{array}{*{20}{l}} {\sum\limits_{j = 1}^N {\frac{{\left( {1 - {w_j}} \right){n_j}{u_j}{p_{{\rm{loc}}}}}}{{{f_{{\rm{loc}}}}}}} , \quad {\rm{LCU}}为0}\\ {\sum\limits_{j = 1}^N {\frac{{{w_j}{n_j}{p_{{\rm{tx}}}}}}{{R\left( {{P_{{\rm{tx}}}}} \right)}}} , \quad {\rm{LCU}}为1} \end{array}} \right. $

(4)

其中：LCU为0表示移动设备计算单元，其能耗为移动设备计算单元执行时的能耗；LCU为1表示MEC服务器计算单元，笔者仅关注移动设备自身的能耗，故其能耗仅包含移动设备的传输能耗.单个任务的整体能耗为两部分能耗之和，所以任务T_i的整体能耗可表示为

$e\left(S_{t}\right)=\frac{n_{0} u_{0} p_{ \mathrm{loc}}}{f_{\mathrm{loc}}}+e\left(m_{t}\right)+\frac{n_{N+1} u_{N+1} p_{\mathrm{loc}}}{f_{\mathrm{loc}}} $

(5)

2 随机任务迁移算法 2.1 Q学习算法

Q学习是一种基于随机动态过程的不依赖模型的强化学习方法^[6].在Q学习中，一个智能体通过MDP与环境进行交互，并从环境中获得延迟奖励来学习最优的控制策略^[7].在智能体与环境交互的过程中，智能体需要观察到环境在时刻t的状态S_t，选择一个动作(随机或者通过Q表选择)执行，获得下一个时刻状态S_t+1和该动作执行的即时奖励r_t，通过式(6)更新Q表，并且将S_t+1设置为当前状态S_t，不断循环这个过程直到Q表可以被近似为Q^*函数，Q值的更新公式为

$\begin{array}{l}{Q_{t+1}\left(s_{t}, a_{t}\right)=Q_{t}\left(S_{t}, a_{t}\right)+\eta\left[r_{t}+\right.} \\ {\left.\gamma \max Q_{t}\left(S_{t+1}, a_{t+1}\right)-Q_{t}\left(S_{t}, a_{t}\right)\right]}\end{array} $

(6)

其中：η为学习率，控制Q值更新的速度；γ为折扣因子，表示学习系统的远视程度.当Q表收敛时，Q_t(S_t, a_t)的值等于在状态S_t执行a_t所获得的奖励，即r_t+γmax Q_t(S_t+1, a_t+1).因此，一旦Q^*的值被学习到，最优策略也随之确定.

在本文中，确定任务的MDP模型表示为

1) 状态空间

定义确定任务T_i在t时刻到达时的状态空间S_t包括MEC系统2个逻辑计算单元当前的忙闲状态S_c和任务的N个可迁移组件的分配状态S_i，即任务迁移策略的一个可行解.状态S_c中c的取值集合为{0, 1}, 分别表示移动设备计算单元和移动设备传输单元与MEC服务器组成的逻辑计算单元的编号, 故S_c={s₀, s₁}，其中S_c={0, 1}表示当前编号为c的逻辑计算单元的状态为{空闲, 忙碌}；用w_j表示任务T_i第j个组件逻辑计算单元的分配状态，所以S_i={w₁, w₂, …, w_N}.因此，状态空间可以用S_c和S_i表示为

$ S_{t}=\left[S_{c}, S_{i}\right]=\left[s_{0}, s_{1}, w_{1}, w_{2}, \cdots, w_{N}\right] $

(7)

任务T_i的状态转移就是在策略解空间上的搜索.

2) 动作空间

定义动作空间A由任务T_i的N个可迁移组件C_j的执行位置表示，对于状态S_t，动作空间中动作数为N，第j个动作(1≤j≤N)表示把第j个组件迁移到下一个逻辑处理单元中.因此，动作空间可以表示为

$ A=\{a | a \in\{1, 2, \cdots, N\}\} $

(8)

3) 即时回报

考虑到任务T_i的学习过程就是在解空间上的搜索过程，搜索的目的是找到任务分配策略的最优解，任务在状态S_t时的处理时延为t(S_t)，能耗为e(S_t)，由于时延与能耗的计算结果可能不在同一量级，使用函数$ \operatorname{sig}(x)=\frac{1}{1+e^{x}} $分别对时延与能耗进行放缩，所以定义即时回报为

$ \begin{aligned} R\left(S_{t}, a_{t}\right) &=\operatorname{sig}\left(t\left(S_{t+1}\right)\right)+\mu \operatorname{sig}\left(e\left(S_{t+1}\right)\right)-\\ & \operatorname{sig}\left(t\left(S_{t}\right)\right)-\mu \operatorname{sig}\left(e\left(S_{t}\right)\right) \end{aligned} $

(9)

其中：μ为权重，即在状态S_t下采取动作a_t所获得的即时回报，为下一个状态的时延与能耗加权和与当前状态时延能耗加权和的差.当状态S_t+1的时延和能耗比状态S_t大时，R(S_t, a_t)的值为负数，即在状态S_t下采取动作a_t使状态变差，给予该动作负向惩罚；当状态S_t+1的时延和能耗比状态S_t小时，R(S_t, a_t)的值为正数，即在状态S_t下采取动作a_t使状态变优，给予该动作正向奖励.

4) 值函数Q(S_t, a_t)的更新公式由式(6)确定.

5) 终止条件：当处于S_t状态时，采取N个动作时转移到状态S_t+1时所获得的即时回报均为负，即当前状态为一个局部最优解时当前情节终止.

根据以上描述，Q学习算法包括以下步骤.

步骤1  初始化Q(S_t, a_t)，设置情节数n=0和情节设定值N和贪婪策略上限值epi；

步骤2  随机初始化状态S，并使其满足组件C_j同一时间只分配给一个逻辑处理器的原则，步骤数step=1；

步骤3  计算状态S_t是否满足终止条件，如果满足终止条件，返回步骤2；

步骤4  根据贪婪策略，从动作空间A中选取当前状态S_t的值函数Q(S_t, a_t)最大的动作a_p，若Q(S_t, a_t)为最大的数量超过2，则随机从对应的几个动作中选取一个a_t作为a_p；

步骤5  产生[0, 1]之间的随机数ε，如果ε < min(epi, (1+step)/(10+step))，则a=a_p，反之从有效动作空间A中随机选取一动作a_r，使a=a_r；

步骤6  执行动作a，进入下一状态S_t+1，获得即时奖励r；

步骤7  由式(6)更新Q(S_t, a_t)；

步骤8  S_t=S_t+1，step=step+1，如果S_t不满足终止条件，转步骤4，否则S_t为当前情节的终态，当前情节结束，并令n=n+1；若情节数n达到设定值N，算法结束；否则，返回步骤2继续执行.

2.2 深度前馈神经网络

采用深度全连接前馈神经网络构造多任务部分迁移策略生成器，其输入维度为N，代表确定任务的N个可迁移组件数据量；由于每一个组件均有可能在移动设备CPU执行或者迁移到MEC服务器执行，所以任务分配过程中的总策略数为2^N，输出维度为2^N，其激活函数使用“sigmoid”；隐藏层数为H，其激活函数使用“ReLU”.深度神经网络的策略生成过程本质上是多分类的过程，将任务的N个可迁移组件数据经过正规化后输入神经网络，经过前向传播得到输出结果并利用softmax算法进行概率转换得到每一个分类的概率，将得到的结果使用交叉熵损失函数计算代价，为避免过拟合，使用L2正则化损失函数并使用反向传播算法更新神经网络参数，不断训练，使神经网络产生较高的准确率.

2.3 基于机器学习的随机任务迁移算法

该算法是前述算法模块的整合与使用，可分为训练阶段和使用阶段.如图 3所示，在训练阶段，算法的执行流程为对每一个随机任务，根据前述规则划分为N个可迁移组件和2个不可迁移组件，利用Q学习算法得到任务的最优执行策略，并将其存入数据库作为训练样本，当数据足够多时，用来训练深度前馈神经网络，以数据驱动的方式不断地循环训练算法得到近似最优迁移策略.在算法使用阶段，可以跳过Q学习寻找单任务最优策略的过程，直接将任务的各个组件参数输入神经网络，经过网络的一次前向传播即可得到随机任务的近似最优迁移策略，使得算法可以高效地生成随机任务的近似最优迁移策略.

3 仿真结果

对提出的算法在python环境中利用tensorflow框架进行了编码实现，并且通过仿真实验对其性能进行了评估.在仿真中，假定深度神经网络中隐藏层数H=2，分别包含1 024个和512个神经元.确定任务的子模块数N=9，任务子模块数据大小和任务的负载量服从均匀分布，即c_i~Unif([0, 2c_avg])，u_i~Unif([0, 2u_avg])，其中：c_avg=10 kbit；u_avg=797.5 cycles/bit.此外，设置移动设备CPU频率f_loc=1 GHz，其功率p_loc=320 mW，MEC服务器的CPU频率f_ser=3 GHz，对于移动设备传输模块，其参数设置为g₀=－40 dB，L₀=1 m，L=100 m，θ=4，ω=3 MHz，N₀=－174 dBm/Hz，P_tx=100 mW^[4].

为验证算法的有效性和泛化能力，引入3种任务调度算法作为对比，包括随机任务随机迁移算法、基于Johnson的最优任务迁移算法^[3]和移动设备本地执行算法.随机生成算法为对所有随机到达的任务，除了不可迁移组件在移动设备执行外，对所有可迁移组件随机分配到移动设备CPU和MEC服务器执行；基于Johnson的最优任务迁移算法对所有随机到达的任务，按照传输时间和执行时间进行任务重新排序，按照排序结果将任务依次迁移到MEC服务器执行；移动设备本地执行算法为将所有任务的所有子模块均在移动设备CPU执行.

在包含1万个任务的测试集上使用基于机器学习的MEC随机任务迁移算法与前述算法在时延能耗加权和上的性能，如图 4~图 6所示.可以看到，随着任务数量的不断增加，移动设备任务完成时延、能耗、时延能耗加权和与任务数量呈类线性增长，但是，不同任务分配策略对时延与能耗加权和的影响也越来越大.在图 4中，所提出的基于机器学习的随机任务迁移算法时延最小，为534.5，比本地执行算法(876.0)时延降低约39%.

图 5展示了4种不同算法在能耗上的表现，可以看到，除了基于Johnson的最优任务迁移算法外，所提出的算法能耗最低.在图 6中，处理完全部1万个任务时，本地执行算法时延与能耗加权和高达1 156.3，基于Johnson的最优任务迁移算法略低，为886.4，随机生成算法比基于Johnson的最优任务迁移算法低94.3，为792.1，基于机器学习的任务迁移算法时延与能耗加权和最低，为715.7，大约比本地执行策略降低38.1%，比最优任务迁移Johnson算法降低19.3%，比随机任务随机生成策略降低9.6%.

4 结束语

提出了在单用户MEC系统中基于机器学习的随机任务迁移算法，通过将随机任务切分成可迁移组件和不可迁移组件，在算法训练阶段，利用Q学习生成该任务的最优迁移策略作为训练样本来训练深度前馈神经网络，完成最优策略的学习.在算法使用阶段，新的随机任务到达时仅经过一次神经网络前向传播就可以生成该任务的近似最优分配策略，极大地加速了最优策略的生成.仿真结果表明，该算法在经过大量任务的训练后非常有效，并且在新任务到达时也能够生成近似最优策略，表现出了很好的泛化能力.未来的研究工作主要包括加入对任务缓存队列优先级的控制、对移动设备无线信道传输功率的控制和将任务组件间数据依赖关系的处理由平行依赖扩展为一般性依赖.