基于图卷积网络的强化学习在多接入边缘计算中的任务卸载

摘要

为实现计算密集型应用的高质量服务，提出了多接入边缘计算（MEC）将任务卸载至MEC服务器。近年来，基于强化学习的任务卸载策略引起了研究人员的关注，但其中不完整的马尔可夫模型导致性能提升有限。本文提出一种基于图卷积网络的强化学习（GRL-based）方法，以增强在多接入边缘计算中的强化学习任务卸载能力。通过将任务集视为有向无环图，引入图卷积网络从任务中提取特征，进而构建用于卸载策略的完整马尔可夫模型。在所提出的基于GRL的方法中，决策过程部署于用户层，而训练过程部署于云层。采用一种离策略强化学习方法——软演员-评论家（soft actor-critic）来训练卸载策略，从而实现采样与训练的分离。多个仿真实验表明，所提出的基于GRL的方法优于基线方法，且能够高效地实现任务卸载的连续决策。

关键词 多接入边缘计算 · 图卷积网络 · 强化学习

1 引言

第五代（5G）[5]的出现正在推动许多新的应用和用例，例如现代物联网（IoT）[37], 自动驾驶汽车[38], 和智慧城市[30]。这些场景需要更强的计算能力和更长的电池寿命，而现有的智能手机和可穿戴设备无法满足。一种可能的解决方案是将计算和存储重新部署到云服务器[9], 并通过下行链路接收结果。

随之而来的问题是，云服务器距离本地设备较远，需要大量中间节点来保证及时流量。

发展多接入边缘计算（MEC）的目的是为计算密集型应用实现低能耗下的高质量服务（QoS）[2]。相较于云计算的优势，MEC服务器以分布式方式部署在网络边缘，使得各种计算密集型应用能够在多个MEC服务器上运行，从而减少拥塞。此外，将任务卸载到更近的MEC服务器可降低端到端延迟，该延迟主要由任务传输延迟和计算延迟组成[1]。通常，一个MEC应用有多种可用的计算资源，包括部署在不同设备上的MEC服务器、本地处理器以及远程云服务器。对于MEC应用而言，一种低能耗且低卸载延迟的任务卸载策略至关重要[39]。一个令人满意的卸载策略可以通过为每个任务选择最合适的计算资源来减少延迟，这一过程通常被视为旅行商问题（TSP）[8]。由于其具有非确定性多项式（NP）难解性，大多数现有方法采用启发式算法来优化卸载策略[36]。随着计算资源和系统复杂性的增加，启发式方法在适应不同场景方面表现不足。尽管将任务卸载建模为多目标优化问题是 MEC卸载的一种直观解决方案[23], 但优化函数可能是非凸的，且优化过程需要大量的计算资源和时间，尤其是在大规模MEC网络中[42]。因此，需要一种更合适的方法来进行实时卸载决策。

机器学习技术的兴起为新型颠覆性应用[21]铺平了道路。作为人工智能中的典型技术，机器学习技术[4]在各种场景下优于启发式算法[3]。在机器学习中，强化学习（RL）是策略优化最有效的方法[19], 并因深度学习而重新焕发活力。受深度强化学习算法在连续决策任务中优异表现的启发，研究人员尝试将深度强化学习（DRL）[11]应用于移动边缘计算任务卸载。强化学习通过与环境交互不断优化策略以最大化期望奖励，这要求严格的马尔可夫模型，即智能体的下一个状态与过去行为无关，仅受当前状态和动作的影响。深度神经网络被引入强化学习中用于近似策略或值函数，从而使强化学习能够应对连续或大规模状态空间的情况。尽管现有的基于深度强化学习的卸载方法在一定程度上提升了移动边缘计算应用的性能[22], 但在建模任务卸载时仍存在若干挑战。一些已有的基于深度强化学习的方法针对的是独立任务[16], 其中任务和服务器的状态无需编码器即可形成潜在状态空间。然而，在现实世界中任务通常是相互依赖的。例如，在人脸识别应用中需要两个任务：人脸检测和人脸分类，而分类依赖于检测结果。因此，在构建任务卸载的强化学习模型时应考虑这种依赖关系。Wang等人将依赖关系建模为有向无环图（DAG）[39], 并利用编码器-解码器从该有向无环图中提取特征，进而为强化学习模型构建潜在状态空间。但由此引发一个问题：对有向无环图进行编码和解码使得训练变得困难，并且由于将有向无环图转换到欧几里得空间导致状态空间维度增加，从而需要更多的计算消耗。此外，现有的基于强化学习的方法缺乏完整马尔可夫模型，即状态转移信息缺失，且由于状态表示不当，模型无法扩展到连续任务。

在本研究中，我们旨在构建一个更适用于移动边缘计算中任务卸载的深度强化学习模型，该模型同时考虑了依赖关系和连续卸载。从马尔可夫决策过程的角度出发，我们综合考虑了任务依赖关系和服务器状态，并建立了连续卸载的状态转移模型。此外，通过将依赖关系视为有向无环图，引入图卷积网络（GCN）[40]来提取其深层特征。本工作的主要贡献可总结如下：

– 我们提出了一种用于移动边缘计算中任务卸载的新型强化学习模型，该模型构建了一个完整的马尔可夫决策过程以实现连续卸载。
– 我们利用图卷积网络来增强深度强化学习模型，从而去除了冗余编码器和解码器。我们方法中的图卷积网络显著提升了深度强化学习模型的性能，同时降低了训练成本。
– 我们通过仿真实验将我们的方法与基于深度强化学习的方法和启发式方法进行了比较。结果表明，我们的方法优于基线方法。

本文的其余部分组织如下。第2节介绍相关工作，包括图卷积网络和深度强化学习。提出的方法的架构在下一节中描述。在第4节中，我们介绍了该方法的详细设计。第5节给出了仿真结果，并与基线方法进行了比较。在第6节中，给出了结论和未来的工作。

2 相关工作

2.1 移动边缘计算

在5G当前的发展趋势下，MEC被提出用于实现互联网与移动通信技术的融合[25, 26]。作为影响边缘服务器接入延迟的重要因素，MEC中的资源分配问题已被众多研究者探讨，以实现服务率优化和传输延迟降低[27]。一些研究聚焦于边缘服务器的最优部署，通过优化边缘网络服务体系结构来实现最小接入延迟[28]。然而，大多数研究旨在直接改进任务卸载策略，即将部分移动计算工作负载迁移到资源更丰富的MEC服务器上[10]。任务卸载的关键讨论在于卸载成本与本地处理成本之间的权衡。

在使用传统技术构建移动边缘计算网络[24]时存在许多局限性。例如，在自组织移动边缘计算网络[29], 中，分布式任务调度算法和分布式设备协调应具备灵活性和可扩展性，且任务卸载策略应能够同时处理大量任务。传统的启发式方法（如遗传算法和蚁群算法）无法立即处理这些情况[3], 而其他动态规划方法和优化理论通常会陷入局部最优[23]。一些研究人员已提出利用机器学习技术来提升移动边缘计算的性能[17]。其中，深度学习是最为突出的技术。主要原因在于深度神经网络具有出色的泛化能力，并且训练过程与执行相分离。前者意味着深度学习在经过有效训练后可以处理未知情况[31], 而后者意味着即使在大规模移动边缘计算网络中，也能立即响应任务。这两种特性正是移动边缘计算所期望的，这为优化移动边缘计算带来了新的方向[43]。

2.2 深度强化学习与图卷积网络

与监督学习或无监督学习不同，强化学习在训练过程中不需要标签，因为奖励由环境[7]返回。基于马尔可夫决策过程（MDP），强化学习模型可以描述为一个元组(S, S′, A, R, γ), 其中 S是状态空间，A是动作空间，γ是折扣因子，S′ ← S × A表示状态转移函数，R ← S × A表示奖励函数。无模型强化学习方法[12]可分为基于策略的[15]和基于价值的算法[33]。前者直接更新智能体的策略，而后者在训练过程中不断调整值函数。新兴的强化学习算法大多采用演员-评论家框架[20], 该框架结合了基于策略和基于价值算法的优点。演员-评论家框架同时学习策略和值函数，其中演员根据评论家估计的奖励来调整其参数。

许多研究以各种方式改进强化学习。异步优势演员-评论家（A3C）[6]通过采用分布式智能体打破经验之间的相关性。近端策略优化[13]是最先进的同策略强化学习算法，其中引入了重要性权重以改善优化。

传统神经网络作用于矩阵或张量，二者均存在于欧几里得空间[35]。尽管深度神经网络具有惊人的拟合能力，但当输入为非欧几里得结构数据时，额外编码是前提条件。因此，图神经网络被提出用于处理非欧几里得结构[34]。

基于谱的图卷积网络（GCN）[18]受到卷积神经网络（CNN）中卷积操作的启发，但图上的卷积作用于邻近顶点。使用GCN处理拓扑数据具有两个显著优势：一是GCN可以在无需额外编码的情况下直接处理输入，从而将输入映射到更可行的特征空间；二是GCN能够更准确地从图中提取特征，并且随机初始化参数也能在未训练的情况下捕获可用特征。

3 基于图卷积网络的强化学习框架用于移动边缘计算

本文提出了一种基于图卷积网络的强化学习框架（GRL-based）用于移动边缘计算中的任务卸载，其中通过带有GCN的强化学习模型来学习最优卸载策略。在本节中，我们首先给出任务卸载问题的建模，列出卸载连续任务所面临的挑战，然后详细描述所提出的基于GRL的方法的框架。

3.1 移动边缘计算中的任务卸载

在MEC系统中，用户设备中的计算密集型应用需要将其计算和存储资源卸载到部署在网络边缘的边缘计算服务器上。

在一个具有边缘服务器集合{N1, N2,…, Nn}的移动边缘计算网络中，所有服务器部署在不同位置且具有不同的CPU核心。该移动边缘计算网络包含一个集中式云服务器和一个用户设备。需要执行的任务为τ1, τ2,…。第 i个任务由一个元组〈di, li, ui, ki〉表示，其中 di是第 i个任务的依赖关系，li表示由上行和下行引起的所需延迟，ui表示执行该任务的工作负载（周期），ki是任务的等待时间。对于一个边缘服务器Nj= 〈wj, fj〉，wj表示当前哪个任务被卸载到该服务器或服务器是否空闲，fj表示周期/秒或MHz。我们的目的是找到一种策略 π以最小化总等待时间K=∑i ki。

3.2 提出的框架

在提出的方法中，存在两个策略网络。目标策略网络部署在用户层，其中包含一个图卷积网络用于提取任务特征，一个全连接层用于捕获边缘服务器的特征，以及一个用于输出策略的策略网络，这些部分将在后文详细描述。每当用户设备提交新任务或某个任务完成时，任务集发生变化，任务有向无环图也随之更新。在该有向无环图中，每个顶点表示一个任务，顶点的特征为(li, ui, ki)。DAG中的边表示任务间的依赖关系，从顶点 vi到顶点 v j的有向边意味着 v j是 vi的前驱任务。与其它基于强化学习的方法不同，本方法还将边缘服务器状态输入至策略网络。卸载调度器通过从输出分布中采样生成，并被发送至用户层以执行任务卸载。当新增任务或任务完成时，奖励根据等待时间 K计算，并将一个体验元组传送到云层以更新训练策略网络。训练策略网络的参数在设定的时间间隔内被送回用户层，用于更新目标策略网络。

4 基于图卷积网络的强化学习模型

在本研究中，构建了一个完整的用于任务卸载的强化学习模型。与以往的研究不同，我们考虑了由于新任务或应用程序导致的任务集变化。在本节中，我们首先描述具有GCN的强化学习模型，然后介绍训练的详细过程。

4.1 针对可变任务集的强化学习模型

图2展示了所提出的基于GRL的任务卸载方法的策略网络，其中使用全连接层从边缘服务器状态中提取特征(w1, f1),(w2, f2),…,(wn, fn)，其中 n为边缘服务器的数量。采用图卷积网络（GCN）从任务有向无环图中捕获特征，其中第 i个顶点为 (li, ui, ki)。所有数据均被归一化以便于处理。从边缘服务器状态和任务有向无环图在时刻 t提取的特征分别为 gs t和 gd t，它们被输入到长短期记忆网络（LSTM）[14]以获得潜在状态ht，随后送入执行者网络和评论家网络。

提出的方法的状态空间由服务器状态和任务属性组成。前者是(wi, fi)，存在于欧几里得空间中，因此我们使用全连接层来提取特征。后者(di, li, ui, ki)被转换为一个有向无环图，其中 di表示边，(li, ui, ki)是第 i个顶点。当发生状态转移时，会有新任务添加到任务集中且任务有向无环图发生变化，或有任务完成且服务器状态发生变化。在本研究中，st=((wt, f),(Vt, Et))表示在时间 t的状态，其中wt表示在时间 t的(w1, w2,…, wn)，(Vt, Et)是时间 t时的任务有向无环图。

提出的方法的动作空间是 n维的。执行者网络的输出是πt= Ot ∈[0, 1]m∗n，表示将任务集中的 m个任务（任务最大数量）卸载到 n个服务器上的概率分布，其中Oi,j ∈[0, 1]表示第 i个任务卸载到第 j个服务器的概率。卸载调度器at ∈[0, n]n从 Ot中采样得到，其中 ai是要卸载到第 i个服务器的任务的索引。

该方法中的奖励函数定义为总等待时间的负值：−Kt= −∑i ki,t。为了惩罚无效卸载，即任务被卸载到工作中的服务器或该任务的前驱任务未完成的情况，我们对奖励给予负反馈。因此，奖励函数设计为：
$$
rt= −Kt − αe= −∑i ki,t − αe, \quad (1)
$$
其中 e是无效卸载数量和依赖关系，而 α是惩罚系数。

4.2 训练和更新

卸载策略的训练发生在云层。当发生状态转移时，一个体验元组 $< s_t, s_{t+1}, a_t, r_t >$ 被发送到云层并添加到经验缓冲区，这些体验用于通过软演员-评论家算法更新训练策略网络的参数 $\theta_t = (\theta_v, \theta_a, \theta_c)$，其中 $\theta_v$ 是评论家网络的参数，$\theta_a$ 表示执行者网络的参数，而LSTM、图卷积网络和全连接层中的参数由 $\theta_a$ 表示。

评论家网络的损失函数定义为其输出 $V(s_t)$ 与奖励 $r_t$ 之间的均方误差：
$$
L(\theta_v, \theta_c) = \frac{1}{2}(r_t + \gamma V(s_{t+1}) - \mu \log(\pi(a_t|s_t)) - V(s))^2, \quad (2)
$$

执行者网络的梯度为
$$
J(\theta_a, \theta_c) = \log\pi(a_t|\text{vert}s_t) - A(s_t, a_t), \quad (3)
$$

其中优势函数 $A(s_t, a_t)$ 通过以下方式计算
$$
A(s_t, a_t) = Q(s_t, a_t) - V(s_t) = r + \gamma V(s_{t+1}) - V(s_t), \quad (4)
$$

在此训练中，$\theta_c$ 与 $\theta_v$ 和 $\theta_a$ 一起更新，从而使评论家和演员网络共享一个公共特征空间，并减少了参数大小和存储空间。

对于用户层，目标策略网络中的参数 $\theta_u$ 通过复制 $\theta_t$ 进行更新。经过一轮训练后，$\theta_t$ 被传输到用户层。由于软演员-评论家是离策略的，因此目标策略网络的工作与训练策略网络的训练之间不存在冲突。

所提出的基于GRL的方法的工作流程如下：首先，根据任务间的依赖关系从任务集生成有向无环图（DAG），然后将该DAG输入到图卷积网络（GCN）以获取特征 $g^d_t$，同时将服务器的状态输入到全连接层以生成其特征 $g^s_t$。随后，$g^d_t$ 和 $g^s_t$ 与 $h_{t-1}$ 和 $c_{t-1}$（LSTM的前一次输出）一起被送入长短期记忆网络（LSTM），再传递给执行者网络和评论家网络。执行者网络计算策略分布 $\pi_t$，并从中采样得到卸载调度器 $a_t$。根据该卸载调度器进行任务卸载，并依据无效卸载和总等待时间反馈奖励 $r_t$。当一个任务完成或新增一个任务时，发生状态转移，一条经验被传送到云层中的经验缓冲区；如果缓冲区积累了足够的经验，则使用从经验缓冲区中采样的经验对训练策略网络进行训练。此训练过程完成后，缓冲区随机释放部分经验，并将训练策略网络的参数 $\theta_t$ 传送到用户层。最后，目标策略网络通过复制 $\theta_t$ 来更新其参数 $\theta_u$。

5 实验

5.1 基线

在下一段中，介绍了四种流行的任务卸载方法，并将其作为基线用于评估所提出的基于GRL的方法的性能。

基于HEFT的方法 异构最早完成时间（HEFT）是一种针对具有有向无环图工作流任务的启发式算法。HEFT根据任务间的依赖关系，计算每个任务在每台服务器上执行的最早完成时间，然后将每个任务卸载到满足依赖关系且具有最早完成时间的服务器上。

Round-Robin轮询法 按顺序将任务分配给服务器，忽略每个任务的负载和当前状态。轮询法也是一种启发式方法。

基于深度Q学习的方法 基于深度Q学习的方案是一种强化学习方法，利用Q学习来优化目标多接入边缘计算服务器的确定和传输模型选择方案[41]。

基于深度强化学习的方法 [39]中提出的基于深度强化学习的方法利用近端策略优化（PPO）算法来训练卸载策略，其中状态空间为任务有向无环图，动作为决定将任务卸载到服务器还是本地执行。在本研究中，动作为从服务器集合中为每个任务选择一个服务器。

对于卸载增长中的任务，基线方法会在新增任务时调整卸载调度器。

5.2 实验设置

在此仿真实验中，边缘服务器的数量设置为 $n = 5$，任务集中的最大任务数为 $m = [6, 7, 8, 9, 10]$。这些服务器的传输速率相同，5个MEC服务器的计算能力分别为 5GHz，10GHz，15GHz，20GHz 和 25GHz。然后我们实现了一个合成任务生成器来随机生成任务，其中生成的任务依赖于任务集中的若干前驱任务，且传输延迟从均匀分布 $[1,20]$ ms中采样。每个任务所需的CPU周期数在1到10兆周期之间。当当前任务数量少于 $m$ 时，生成器每15毫秒生成一个新任务。

实验在Ubuntu 16.04操作系统上使用Python和TensorFlow工具实现。本实验所用的中央处理器为Intel(R) Core(TM) i7-4790 CPU@3.60GHz，用于训练神经网络的图形处理器为NVIDIA GeForce GTX 1080。Python版本为3.6.9，CUDA版本为V9.0.176。所使用的TensorFlow-GPU版本为2.0.0，Scikit-learn包版本为0.21.3。

对于图卷积网络（GCN），我们利用切比雪夫多项式获得一阶近似，即 $K = 1$。有两个卷积层用于提取有向无环图特征。用于提取服务器特征的全连接层具有 128×64个节点。长短期记忆网络（LSTM）的大小为128，后接一个执行者网络，包含64×30个节点（隐藏层中的64个节点和输出层中的6×5个节点），以及一个评论家网络，包含64×1个节点。折扣因子 $\gamma$ 为0.9，学习率为0.01。云服务器中经验缓冲区的容量为1024，批量大小为64。所提出的基于GRL的方法中的无效卸载包括：将任务卸载到繁忙服务器、对已在服务器中执行的任务进行重新卸载，以及卸载其前驱任务尚未完成的任务。惩罚系数为100。

5.3 结果与分析

图3展示了我们的方法与其他基线方法在平均等待时间（包含执行时间）上的性能表现。实验结果表明，我们的方法在移动边缘计算中的任务卸载表现更优。两种启发式方法，即基于HEFT的方法和轮询法，在处理依赖任务时导致了高延迟。其中轮询法性能最差，原因是忽略了任务间的依赖关系。基于强化学习的方法相比基于HEFT的方法和轮询法表现出更好的性能。其中，基于深度强化学习的方法优于基于深度Q学习的方法，因为它采用了序列到序列模型来进行卸载调度器。然而，与所提出的基于GRL的方法相比，其强化学习模型不完整，因此性能不如基于GRL的方法。

图4显示了边缘服务器每秒的平均空闲时间。这些结果得出了与图3相同的结论：启发式方法无法充分利用计算资源，这在连续任务卸载中更为明显。基于强化学习的方法更适合持续决策。基于深度Q学习的方法比基于DRL的方法和我们的方法更差，因为Q学习是一种基于值函数的强化学习算法，因此值函数的微小变化会显著影响整个策略。平均空闲时间的结果表明，我们提出的基于GRL的方法能够更充分地利用计算资源。

所提出的基于GRL的方法实现了低延迟，这是优秀的卸载策略应具备的特性。然而，可行的卸载策略应保证有效卸载。因此，我们研究了我们的方法与基于深度强化学习的方法的无效卸载率。在本实验中，最大任务数为6。如图5所示，所提出的基于GRL的方法在训练的任何阶段均导致更少的无效卸载，并且比基于深度强化学习的方法具有更快的收敛速度。值得注意的是，在训练初期，所提出的基于GRL的方法明显优于基于深度强化学习的方法，这归因于图卷积网络出色的特征提取能力。当任务集形成有向无环图后，图卷积网络能够更有效地处理该拓扑结构。在训练结束时，基于GRL的方法和基于深度强化学习的方法均可避免无效卸载，但基于GRL的方法能提供更优的卸载策略。基于GRL的方法较低的卸载延迟源于更流畅的连续卸载，而这正是不完整的强化学习模型所缺乏的。这些结果突显了完整马尔可夫模型在移动边缘计算任务卸载中的重要性。

然后构建了一个消融实验以突出GCN的效果。在该实验中，我们将GCN替换为卷积神经网络，DAG以矩阵形式进行编码。修改后的模型命名为对照组。表1为对照组与基于GRL的方法的实验结果，其中GCN的重要性显而易见。从表1可知，在所有实验中，对照组均逊于基于GRL的方法。我们认为，由于额外的编码器存在，对照组需要更多的训练才能收敛。更差的性能表明该额外编码器干扰了特征提取过程。随着任务集中最大任务数的增加，对照组的性能逐渐接近基于GRL的方法。可能的原因是当DAG较小时，编码器会遗漏更多特征；而当任务集足够大时，尽管对照组需要更长的训练时间来优化卸载策略，但其最终性能可与基于GRL的方法相近。

表1 消融实验中的平均等待时间

平均等待时间（毫秒）	m=6	m=7	m=8	m=9	m=10
基于GRL的	893	1125	1390	1768	1832
对照组	1146	1258	1485	1830	2002

6 结论

为了改进移动边缘计算（MEC）中的连续任务卸载，我们提出了一种基于图卷积网络的强化学习（GRL-based）方法。所提出的基于GRL的方法在MEC的任务卸载中构建了一个完整的马尔可夫决策过程，其中利用任务间的依赖关系形成任务有向无环图（DAG）。为了持续卸载新任务，引入图卷积网络从动态有向无环图中提取特征。训练部署在云层中，并通过离策略强化学习算法——软演员-评论家（soft actor-critic），将策略网络的参数传回用户设备。所提出的基于GRL的方法能够高效地从任务有向无环图中提取特征，并实现任务卸载的连续决策。实验结果表明，该方法在移动边缘计算中的任务卸载方面表现出良好的性能。

这项工作仍存在一些局限性，因为我们尚未将临时云服务器和设备增强考虑在内。尽管最直接的方法是将可变的计算资源视为状态转移的一部分，但未来我们仍然计划提供一种可变计算资源与连续任务集的可行组合方案。