多智能体边缘计算任务卸载

赵庶旭，元 琳，张占平

兰州交通大学 电子与信息工程学院，兰州 730070

随着智能终端的飞速发展和逐渐普及，以及第五代移动通信网络（5G）的成功部署，网络中的数据量正在成指数式增长[1-2]。网络拥塞已成为无人驾驶、高清视频直播、虚拟现实和增强现实等低能耗、低时延需求的任务所面临的问题。而终端设备的计算能力有限，计算密集型任务会消耗大量能量，导致设备续航能力极速下降[3]。另一方面云计算平台由于地理位置距终端设备存在一定距离，数据在物理链路上的传输时延较长，无法满足低时延任务的实际要求[4]。因此，终端设备自身和云计算都无法高效地解决此类问题，移动边缘计算（mobile edge computing，MEC）应运而生[5-6]。MEC将计算资源和存储资源部署在靠近终端设备或靠近数据源一侧，来满足任务在实时处理、数据安全和隐私保护方面的需求，极大地提高了用户体验与服务质量，同时缓解了网络拥塞和带宽压力[7-8]。虽然MEC可以将计算卸载到边缘端，但边缘服务器在单位时间内处理数据的能力是有限的。因此，需要设计一种高效的卸载方案，在统筹时延、能耗和成本的基础上，决定任务是在本地执行还是卸载到边缘服务器上执行，以及卸载到哪一台边缘服务器上，以提高整个MEC系统的资源利用率。

1 相关研究

近年来，国内外各大互联网、通信公司和众多学者对MEC任务卸载开展了大量的研究工作[9-11]。文献[12]利用马尔可夫决策过程，提出了一种一维搜索算法求解功率受限的延迟最小化问题，是一种最优搜索算法。但该方法需要预先获得集群的信道质量以及任务到达率等精确信息，在实际应用中存在一定的局限性。文献[13]提出了一种基于博弈论的卸载算法，将卸载博弈转换为势博弈，通过分布式博弈寻找纳什平衡解。但该方法是建立在单边缘服务器场景下的，没有考虑实际应用中多服务器计算资源受限情况。文献[14]利用序列二次规划法优化后的结果训练深度神经网络，以减少时延和能耗，但该方法也受限于单边缘服务器场景下。文献[15]提出了一种多平台卸载资算法，利用K邻近算法选择云计算、边缘计算或是本地计算，之后通过强化学习优化资源分配，但其更侧重于时延的优化，忽略了设备能耗。另外，许多文献利用启发式算法解决边缘计算卸载问题。文献[16]提出了一种新型网络设计方案，并使用Lyapunov随机优化工具解决了受延迟和可靠性约束的计算和发射功率最小化问题。文献[17]使用首次适应、在线优先以及线性规划等启发式算法来优化能耗和时延问题。利用启发式算法解决大规模任务卸载问题时，由于问题维度过高，导致生成卸载决策的时间过长，因此无法满足任务实时处理的需求。目前大多数边缘计算卸载策略都是基于先验分布或历史数据的，由于MEC中任务卸载通过无线传输，可用资源都是随着信道质量、任务到达率以及能量等因素动态变化的，因此先验分布或历史数据预测算法很难应用于真实场景中。基于上述研究的不足，定义卸载场景为多智能体多边缘服务器场景。并同时考虑时延、能耗以及花费因素，提出多智能体完全合作关系，在保证最大时延的前提下，降低能耗和花费，提高边缘服务器集群的资源利用率。引入深度强化学习，将强化学习的决策能力与深度学习的感知能力相结合，依靠强大的深度神经网络的表示学习来解决高纬度动态任务卸载问题。首先，根据问题提出目标函数，建立数学模型，包括任务建模、时延模型、能耗模型以及花费模型。随后，构建马尔可夫决策模型，利用DRQN对模型进行求解。最后，进行上述算法与本地执行、随机卸载、DQN等算法在时延、能耗、花费方面的对比实验，仿真实验结果验证了多智能体环境下基于DRQN卸载策略的有效性和可靠性。

2 系统建模

2.1 网络建模

本文所建模型为多智能体多边缘服务器模型，为边缘计算任务卸载场景。如图1所示，模型中包括N个边缘服务器（edge server，ES）和M个智能体（smart device，SD），其中ES部署在基站上，SD通过无线链路传输数据。SD上的任务根据时延和能耗需求可以选择在本地执行，也可以选择在ES上执行；在ES计算资源允许的情况下可以选择在一台ES上执行，也可以选择在多台ES上执行，ES和SD是一种多对的关系。

图1 网络模型图Fig.1 Network model diagram

2.2 任务建模

针对任务粒度[18]大小，从资源利用率和计算复杂度考虑，本文采用细粒度划分任务。即智能体上的每个任务都可以被划分为k个子任务，不同的子任务可以在不同的ES上执行，也可以在本地执行，从而缩减计算时延。任务集合定义为其中，表示第i个智能体上第j个子任务输入的数据量，包括代码和输入参数；Cij表示执行第ij个子任务所需的计算资源。这里的计算资源是指CPU，假设任务在本地智能体CPU上执行和卸载到ES的CPU上执行所需的计算资源是相同的；表示第ij个子任务计算完成后所得的结果数据；表示执行第ij个子任务的最大时延约束。本文的卸载目标是在满足最大时延约束的条件下，尽可能地降低能耗和缩减费用，并得到如下决策矩阵：

其中，x∈{0,1,2,…,p,…,N}，当x=0时代表本地执行，当x=1时代表子任务将被卸载到序号为1的ES上执行。同理，当x=p时代表子任务将被卸载到序号为p的ES上执行。

2.3 时延模型

假设本地处理任务的时延有且只由CPU产生，定义为：

其中，Cij为上文中提到的Rij所需的计算资源，这里具体为执行Rij所需的CPU时钟周期数，fSDi表示智能体i的CPU主频。

若Rij需卸载到ES上执行，则需要从发送时延、传播时延和处理时延三方面对在ES上的时延进行分析，定义为：

综上所述，当子任务之间存在依赖关系时，总时延为在本地执行的子任务时延之和加在边缘服务器上执行的子任务时延之和：

当子任务之间相互独立时，总时延为第i个智能体上所有子任务时延的最大值：

2.4 能耗模型

这里的能耗是指智能体端的能耗，假设在本地执行的任务所产生的能耗只与CPU有关，能耗模型定义如下：

2.5 费用模型

费用是指用户使用运营商提供的计算资源所支付给运营商的费用，所以费用只在卸载后产生，不涉及本地执行部分。本文使用基于计算资源剩余量的费用模型，即计算资源剩余越多用户支付的费用越低，定义如下：

其中，uES表示边缘服务器单位时间的价格，表示服务器p计算资源的使用率，表示服务器p计算资源的总量。

2.6 目标函数

多智能体边缘计算任务卸载问题是一个最优化问题，本文的目标是在保障时延的前提下，最小化能耗和费用，在提升整个MEC系统的资源利用率的同时延长智能体的续航时间，目标函数定义如下：

其中，α和β分别是能耗和费用所占权重。

3 模型求解

为求解上述模型，本文提出一个部分可观测的、多智能体完全合作的基于深度强化学习的边缘计算任务卸载算法。在实际应用环境中，由于底层物理链路的不稳定性，边缘服务器的状态存在不能被完整观测的可能性，称其为“部分可观测”。在多智能体强化学习中，每一个智能体都是自主、可交互的[19]，它们独立地接收边缘服务器的状态信息，根据自身的策略函数决定当前采取的卸载方案。同时，智能体之间相互通信，共同优化目标值，整体的卸载效果通过一个综合的标准来评判。

强化学习是一种具备自学习能力、能做出最优决策的算法[20]。它将问题抽象为智能体不断在环境中试错的过程，在每一个时间步长中，智能体都会收到环境的状态信息，并根据状态信息作出响应动作。在下一个时间步长中，会根据环境的反馈给该智能体一个相应的奖励值。若是期望的结果，则给一个正奖励，反之，则给一个负奖励[21-22]。目标是最大化累积奖励[23]。但强化学习局限于低维度问题，在大规模状态、动作空间问题中，存在“维度灾难”。因此，引入深度学习，将强化学习的决策能力与深度学习的感知能力相结合，依靠强大的深度神经网络的表示学习来解决高维卸载问题。

图2 模型结构图Fig.2 Model structurediagram

3.1构建MDP

马尔可夫决策过程（Markov decision process，MDP）一般包含状态空间（state space，S）、动作空间（action space，A）和奖励函数（reward function，R）。状态空间S定义如公式（10）所示，包含资源剩余向量U，决策矩阵X，目标函数G。

其中，U=[ ]u1,u2,…,up,…,uN，up表示序号为p的ES可使用的计算资源。

动作空间A表示在每一个状态下可以采取的所有动作，定义如下：

其中，γ为第i个智能体上第j个子任务的卸载方案，γ∈{0,1,2,…,p,…,N}。

奖励函数R表示智能体执行动作、状态转移后，根据环境反馈获得的奖励，定义如下：

其中，Gt为t时间段内的目标函数值，Gt+1为智能体在状态St下作出响应动作At后t+1时间段内的目标函数值，GSD为任务在本地执行时的目标函数值。上述三个目标函数值均根据公式（9）计算。注意，在本地执行时，目标函数不存在费用部分（等于零），只有能耗部分和时延限制。当Gt+1＞Gt时，即执行动作At后，G变大，即能耗和花费增大，向不期望的方向发展，给予负奖励。反之，给予正奖励。

3.2 基于DRQN的任务卸载算法

深度递归Q网络（DRQN）是对深度Q网络（DQN）的一种改进，利用递归神经网络（RNN）解决部分可观测马尔可夫决策过程（POMDP），提高DQN性能。在MEC应用场景中，由于底层物理链路的不稳定性和智能体感知的局限性，智能体很难接收到当前时间段内环境的精准状态信息，导致了POMDP问题。DRQN保留先前状态信息，补充当前状态信息，解决缺失值问题。具体实现过程是用长短时记忆递归神经网络（LSTM RNN）代替DQN中卷积层后第一个全连接层，DRQN架构如图3所示。

图3 DRQN架构图Fig.3 DRQN architecture diagram

将边缘服务器ES返回的状态信息作为输入，卷积层对状态信息进行卷积运算，得到特征图，传递给LSTM层，LSTM根据先前记忆补充状态信息，并更新记忆，最后经过一个全连接层输出Q值。其中，ht是上一时间步长网络的返回值，即ht=LSTM(ht-1,at)，作为下一时间步长的输入。

DRQN利用一个权重为θ的神经网络来逼近Q函数，即Q(ht,at;θ)≈Q*(st,at)。损失函数为目标值与预测值的均方差，定义如下：

其中，r为奖励，γ为折扣因数，位于0～1之间，决定了即时奖励和未来奖励的重要性，接近0意味着即时奖励更重要，接近1意味着未来奖励更重要。神经网络通过梯度下降更新θ最小化损失。注意，目标Q的参数是θ′，和预测Q的参数θ不同。DRQN采用一种称为目标网络的独立网络来计算目标值，目标网络与预测网络结构一致，但滞后于预测网络若干时间步长，从预测网络中复制权重θ更新自己的权重θ′。因此，目标Q值与预测Q值具有一定的差异性，进而用来计算损失。

智能体从状态s执行某一动作a转移到状态s′，获得奖励r,＜s,a,s′,r＞就是智能体的一条经验，保存在经验缓存中。DRQN从经验缓存中随机选择一批训练样本，减少经验之间的相关性，提高算法的泛化性。具体算法如下：

4 仿真实验

本文使用Python语言在Anaconda平台上通过比较DRQN与RQN、随机卸载算法在大规模异构集群中能耗、费用以及时延等因素来评价DRQN算法在多智能体任务卸载应用中的优劣。仿真实验模拟的集群包括50个边缘服务器、数量不等的智能体，其中，边缘服务器均匀分布在9个面积相同的区域中，智能体随机分布在距基站150 m范围内。假设带宽20 MHz，智能体的上传速度为5.3 Mb/s，上传功率为1 500 mW，空闲时的放电功率为200 mW，极限CPU主频为2 GHz/s，边缘服务器的极限CPU主频为50 GHz/s。并且R的数据量（单位，Kbit）服从（200，2 000）的均匀分布，所需计算资源服从（1 200，3 000）的均匀分布。设深度强化学习参数，学习率α为0.001，经验缓存大小为6 000，批学习大小BatchSize为32。γ分别取0.7、0.9，对比其在不同任务数量下能耗、花费情况，如图4所示，γ=0.9时在能耗和花费上的表现均优于γ=0.7时，意味着在边缘计算场景中，未来奖励发挥着重要作用，故本文实验γ取0.9。

图4 不同折扣因数DRQN能耗、花费对比Fig.4 Comparison of energy consumption and cost ofDRQN with different discount factors

在满足最大时延的前提下，本文将DRQN、DQN以及随机卸载算法与本地执行的能耗和费用做差再除以本地执行的能耗和费用的比例（energy and cost reduction ratio，ECRR）作为算法的评价指标之一。如表1所示，DQN和DRQN能耗和花费缩减率都达到了50%以上，并且DRQN比DQN提高了近2个百分点。

表1 ECRR对比表Table 1 ECRR comparison table

不同任务数量下的各算法性能研究，任务数量取值范围为[20，100]，以10为步长，画出本地执行、随机卸载算法、DQN以及DRQN在能耗、花费和时延上的对比图。

由图5可以看出，随着任务数量的增加，各算法生成的卸载策略在能耗和花费方面大致呈现上升趋势，DRQN较随机卸载算法、DQN在能耗和花费上表现更佳。本地卸载所消耗的能量最多，这是由于智能体的计算能力远远小于边缘服务器的计算能力造成的。另外，从图5可以看出随机卸载算法具有一定的波动，这是因为算法的随机性造成的。

图5 各算法仿真结果对比图Fig.5 Comparison of simulation results of various algorithms

5 结束语

本文提出了一种利用DRQN记忆先前环境状态信息解决部分可观测多智能体任务卸载问题。通过仿真实验表明DRQN相比其他算法在能耗和花费上具有一定的优势。在本文的基础上还可以进一步研究双向DQN、优先经验回放以及对抗网络等在边缘计算实际应用中的作用。随着许多AI新技术的不断涌现，决策算法经历了从规则到浅层监督学习，到深度学习，再到深度强化学习的转变；从单场景优化到卸载决策与资源分配联合优化。但现有的方法还存在着许多的缺点和不足，更复杂的问题有待解决。相信在未来，多智能体之间的合作与协同将成为发展的主流趋势，互搏与内耗将不断减少，联合优化将会创造更高的价值。