基于多智能体元强化学习的车联网协同服务缓存和计算卸载

宁兆龙，张凯源，王小洁，郭磊

（1.重庆邮电大学通信与信息工程学院，重庆 400065；2.大连理工大学软件学院，辽宁 大连 116620）

1 引言

随着5G 时代的到来和互联网设备的普及，万物互联的概念逐渐走进人们的生活，这推动了大量时延敏感型的移动应用，如增强现实、实时导航以及自动驾驶等[1-2]。虽然云技术逐渐成熟，但是随着移动设备的指数性增长，单纯依靠中央云服务器来控制广域网存在时延难以保证的瓶颈[3]，从而难以保证时延敏感型应用的服务质量。因此，移动边缘计算应运而生，成为目前解决上述问题的一种可靠方案。移动边缘计算将计算资源和存储资源以分布式的方式部署在距离用户层更近的边缘节点上，使这些边缘节点就近处理其覆盖区域内的相关业务，从而减轻回程链路的传输压力，并节约相应的服务响应时间。相对于中央云服务器的可扩展性，轻量化的边缘服务器存在资源容量受限和资源利用不均等问题[4-5]。尤其是随着移动应用的多样性增强，其所需的资源也具有很强的异质性，这导致资源利用率低的问题日益凸显。

人工智能和机器学习技术的不断发展，以及其在多个领域的成功应用，使其正成为解决移动边缘计算瓶颈问题的关键技术[6-7]。和传统技术相比，人工智能技术对于环境的动态变化拥有更强大的感知能力。作为其重要分支，深度强化学习在资源分配方面已经得到一定的应用，文献[8-12]都表明基于强化学习的车联网资源分配解决方案具有较好的准确性和稳健性。随着用户需求的动态变化以及多方主体（设备节点、边缘节点和云服务器）的参与，车联网系统需要一种效率高、均衡性强的任务调度和资源分配方法。同时，由于边缘节点的资源有限，需要轻量化、分布式的机器学习技术与其进行适配，从而完成高效的学习过程。

车联网作为万物互联时代的重要一环，由于车辆的高移动特性和车辆应用需求的时变性，车辆应用的处理存在着更突出的难度[13]。为了更好地服务车辆用户和建设智慧城市，需要部署大量装配边缘服务器的路侧单元（RSU,road side unit）来更好地处理其覆盖区域内的车辆应用。因此，车辆、RSU和云服务器构成了常见的三层车联网框架[14]。然而实际情况下城市中车流分布通常是不均匀的，这导致一些RSU 没有足够的资源缓存车辆应用所需的服务，从而需要将计算任务卸载到云服务器；另一些RSU 还有很多剩余的缓存空间没有得到利用，这就导致车联网系统的整体时延增加[15]。因此，为了充分利用车联网中的缓存和计算资源，需要网络运营商挖掘RSU 之间的合作能力，从而提升车联网的服务效率。

车联网中的计算卸载和服务缓存得到学术界和工业界的广泛关注，因为通过制定相应策略可以更好地提升网络性能并减少能耗[16-17]。文献[16]提出一种多时间尺度的强化学习框架来进行缓存和计算资源的分配来最小化车辆应用的服务时延。文献[18]考虑了用户的移动性和网络连通性来进行内容缓存，从而能够缩短用户对内容的获取时间。文献[13]在能耗限制的情况下，通过计算卸载的方式满足了所有基站的能耗约束。很多研究关注车联网中的合作机制，文献[19]中，当车联网需要处理计算密集型任务时，多个边缘服务器会共同合作处理相关应用。文献[20]研究多接入车联网，将资源丰富的车辆与云服务器相结合，构建协同计算架构。也有很多相关研究利用车辆用户的属性，比如社会信任、位置区域等构建相应的车辆应用处理集群[5,14]。然而，这些研究大多集中在用户与服务器、用户与用户间的合作，缺少对于边缘节点之间合作的研究来提升车联网的整体服务性能。

本文考虑了车联网中RSU 之间的合作来解决车辆应用处理过程中的服务缓存和任务调度问题。解决这一问题存在如下几个挑战：1) 车辆服务缓存和任务调度具有耦合性，车辆服务缓存决定任务调度的决策空间，任务调度的结果反映服务缓存的表现；2) 任务计算和传输的权衡，RSU 间合作会减少任务的计算时间，从而增加系统内的传输时间，如何在两者之间进行权衡得到最优解也是一个挑战；3) RSU 行为平衡，即RSU 间合作能够降低系统时延，但求解过程中需避免陷入每个RSU 的局部最优，而是求解全局最优策略。

本文主要的研究工作如下。

1) 本文构建了多边合作的车联网服务模型，它联合了任务缓存和边缘任务调度问题，在可用资源约束的情况下，最小化系统时延。本文将车联网服务问题建模成一个混合整数非线性规划问题，并证明求解该问题需要非多项式的计算复杂度。

2) 本文提出了一种双层的多RSU 协同缓存框架求解上述问题，它采用多智能体元强化学习框架为RSU 缓存车辆应用提供所需服务。每一个RSU作为一个本地智能体计算其对应状态下的缓存决策，云服务器作为元智能体，采用长短期记忆（LSTM,long short-term memory）结构的神经网络来平衡本地智能体的决策，并维护自己的状态信息来进行更快的策略学习。

3) 在缓存策略确定的情况下，本文提出一种自适应的RSU 协同卸载算法，它采用拉格朗日乘子法来求解最佳协同卸载策略。本文通过二分迭代搜索的思想搜索最优拉格朗日乘子，从而调度系统中每一个RSU 的计算任务，实现系统中所有RSU 的工作量负载均衡。

4) 本文采用杭州交通流数据进行实验，结果表明本文提出的算法具有良好的效能和实用性。与其他3 种基准算法相比，本文提出的算法能够获得更低的系统时延，并且能在大规模任务流下拥有相对稳定的表现。

2 系统模型

本文构建的多边车联网服务系统由N个RSU和一个提供服务的云服务器组成，如图1 所示。

图1 多边车联网服务系统模型

RSU 分布在城市中的不同区域，并配置边缘服务器为其相应区域内的车辆提供计算服务，不同的RSU 之间通过局域网连接，且具有计算功能和服务缓存功能。车辆用户会和其邻近RSU 通过无线通信的方式，将计算任务上传到对应的边缘服务器上，考虑它们之间的连接采用正交频分复用技术，因此多个车辆可以在不考虑干扰的情况下和同一个RSU 通信。为了完成不同类别的车辆应用，系统需要从服务商处下载不同的服务，例如视频转码服务和障碍物识别服务等，设 S={1,2,…,S}表示系统提供的服务集合，且缓存服务所需的存储空间为ps，Fn和Cn分别表示RSUn拥有的计算能力和缓存能力，M={1,2,…,M}和 N={1,2,…,N}分别表示车辆用户和RSU的集合。假设RSUn接收车辆应用任务是一个泊松过程[20]，且任务接收速率为，处理一个任务所需的计算资源（CPU 周期数）服从期望为h的指数分布。本文主要变量及其含义如表1所示。

表1 主要变量及其含义

2.1 服务缓存模型

由于车辆资源有限，并且车辆应用对于处理时延具有严格要求，因此需要通过计算卸载的方式上传到RSU 进行实时处理。此外，为了处理车辆任务，RSU 需要从中央云服务器上缓存任务所需的服务；否则，RSU 需要将任务上传到云服务器上进行处理。中央云服务器拥有充足的计算能力和缓存能力，因此，如果在云服务器上处理任务，时延主要由从RSU 上传到云端的传输时延Tcloud造成。设表示服务的缓存策略，表示RSUn的缓存策略。由于RSU 的缓存能力有限，因此对于每一个RSU，不等式成立。同时，由于同一个服务可能缓存在多个RSU 上，不同的RSU 处理应用所需的服务可能缓存在其他RSU 上，因此，系统需要根据服务缓存情况进行协同卸载，从而更好地利用系统中的空闲资源。

2.2 任务计算模型

在协同卸载过程中，本文假设计算任务在服务器间只能卸载一次，即如果计算任务从RSUi卸载到RSUj，那么任务将在RSUj上的服务器上执行，而不会再卸载到其他RSU。设表示系统的协同卸载策略，其中表示t时刻由RSUi卸载到RSUj的计算任务数量，表示RSUi自身处理的任务数量，则RSUi在t时刻处理的任务数量可以表示为。RSU 接收任务的过程是一个泊松过程，本文采用M/M/1 排队系统来为任务处理建模[21]，车联网系统的计算时延可以表示为

其中，μi=Fi/h。为了满足任务队列处理的稳定性，≤μi需要得到满足以确保每一个RSU 的服务性能。

由于网络带宽有限，协同卸载会导致额外的拥塞时延。系统的拥塞时延由网络中的全部任务数量决定，系统中的总任务数量为，其中=表示RSUi卸载到其他RSU 的任务数量。根据M/M/1 排队模型相关理论[18]，系统的拥塞时延为

其中，τ表示在带宽充足情况下通过局域网传输一单位计算任务的时延。

2.3 问题描述

综上所述，系统时延主要由3 个部分组成，分别是计算时延、拥塞时延和（从RSU 上传到中央云服务器的）传输时延。系统时延sT为

其中，wos≥0表示系统中需要服务s且需要上传到云服务器上处理的任务数量。

本文联合考虑服务缓存策略和服务器间的协同卸载策略，目标是最小化车辆任务的处理时延，得到如下优化问题。

其中，约束C1 保证每个RSU 缓存的服务不能超过其缓存能力；约束C2 保证每个RSU 协同卸载的任务数量不能超过其接受的车辆任务数量；约束C3保证每个RSU 处理的任务数量不超过其计算能力。

定理1优化问题P1是一个混合整数非线性规划，求解其需要非多项式的计算复杂度。

证明效用函数凸凹性

通过2 种简化情况来分析优化问题P1 的计算复杂度。

1) RSU 不进行协同卸载。当RSU 不进行协同卸载时，不同服务所对应的计算任务只能由接收任务的RSU 进行本地计算或者上传到云服务器上。因此，系统时延不仅由RSU 的计算能力决定，也高度依赖于RSU 的服务缓存能力。这时，优化问题P1 可以转化为服务缓存问题和任务流输出问题，类似于文献[13]。文献[13]已经证明这个问题是一个混合整数非线性规划问题，并且拥有非多项式的计算复杂度。

2) 所有计算任务需要同一种服务。当所有计算任务需要同一种服务时，在计算资源充足的情况下，服务会被缓存在任一个缓存空间充足的RSU。因此，该种情况可以被看作一个协同卸载问题，即在计算资源约束的情况下，进行计算任务的分配，类似于文献[18]。文献[18]已经证明求解这一问题拥有非多项式的计算复杂度。

通过上述分析，2 种简化情况都具有非多项式的计算复杂度。因此，求解本文的优化问题P1 也具有非多项式的计算复杂度。证毕。

3 算法设计

由于求解优化问题P1 具有非多项式的计算复杂度，本文提出一种双层的多RSU 协同缓存算法（MPO,mutli-RSU service caching and peer offloading algorithm），外层采用多智能体元强化学习框架来为RSU 缓存车辆应用所需的服务；内层在缓存策略确定的情况下，在缓存同一种服务的RSU 间进行协同卸载，本文提出一种自动任务适应算法来求解系统的协同卸载策略。算法流程如图2 所示。

图2 算法流程

3.1 基于多智能体学习的缓存分配策略

本文提出一种多智能体元策略的强化学习（MAMRL,multi-agent meta reinforcement learning）框架进行RSU 的缓存分配，算法架构如图3 所示。

图3 多智能体元策略的强化学习框架

和传统的强化学习相比，MAMRL 框架包含2 种智能体：一种是本地智能体，它配置在每一个RSU上，根据任务量和RSU 上的可用资源并利用强化学习算法进行自身缓存资源的分配；另一种是元智能体，它配置在云服务器上，根据每一个本地智能体学习到的信息和任务量的信息，利用LSTM 进行全局缓存资源分配。MAMRL 减轻了因任务产生和资源需求带来的维度灾难，同时减少了RSU 和云服务器之间的消息传递（本地智能体只需向元智能体上传其处理过的信息而不是全部信息），从而提供一个计算和通信复杂度更低的缓存分配方案。

其中，γ∈(0,1)为折扣因子。在状态sti下采取动作定义为一个策略πθi，它是由参数θi决定的。策略πθi决定了状态转移函数Γ:S ti×Ati↦St′i，以及相应的奖励值函数ri(s ti,a ti):S ti×Ati↦R。因此，在给定状态sti下，策略的状态值函数可以表示为

状态值函数可作为评论家的角色来评判每一个动作在该状态下的表现。因此，对于状态sti下的最佳策略(ati|sti)，可以由该状态的值函数最大值确定，即最大的状态值函数可以获得其对应的最佳策略，最优值函数为

通过式(7)可以选择出每一个决策智能体i的最佳策略。采用时序差分（TD,temporal difference）法求解最优值函数和最优策略，采取策略iθπ的优势函数（TD 误差）定义为

其策略梯度为

通过式(9)可以将网络中每一个RSU 的缓存决策离散化求解。在所有状态信息已知的情况下，本文可以采用集中式的解决策略，它的时间复杂度为O(Si Ai|N|2T)，这需要消耗大量的计算资源。同时，由于集中式的解决策略忽略了其他智能体的决策，导致强化学习过程中的探索和开发出现不平衡的现象，因此本文提出一种元策略的强化学习框架来解决上述困难。

2) 元策略强化学习模型

元智能体由LSTM 结构的神经网络组成，设它的网络参数为φ，且由4 个门层来计算出下一个状态st'i的最优决策和其对应的优势函数，4 个门层分别为遗忘门Ft'、输入门It'、单元状态层和输出层Zt'。元智能体的具体实现为

其中，遗忘门Ft'负责确定哪些信息需要抛除；输入门It'负责确定哪些信息需要更新；单元状态层使用tanh(·) 函数产生新的候选值向量，并通过公式更新单元状态层；输出层Zt'决定哪些信息输出，通过公式计算单元输出，并将最终的输出利用softmax 函数输出最佳策略。因此，元智能体的损失函数是由本地智能体的分布所决定的，其损失函数的期望可以表示为

因此，MAMRL 框架将元智能体的学习参数传递给本地智能体，以便每个本地智能体更新自身的学习参数来计算出最优的缓存分配策略。其参数更新式为

MAMRL 框架可以理解成一个多参与人（N-player）的马尔可夫博弈模型。根据当前对多人马尔可夫博弈模型的研究[22]，MAMRL 模型至少存在一个纳什均衡点来保证最佳的缓存分配策略。因此，对于MAMRL 模型求解的最优性，有命题1 成立。

命题1对于RSUi，其最佳的缓存分配策略是一个纳什均衡点，且其纳什均衡值为。

证明对于RSUi而言，是综合考虑所有RSU 动作后产生的纳什均衡的最优策略。因此，BSi无法采取更优的策略来提升，则对于式(10)，有如下不等式成立

通过上述不等式可知，MAMRL 模型中的元智能体Mt'(Ot';φ)能够在RSUi采取策略时达到纳什均衡，且RSUi的最优值为

因此，最优策略是缓存分配问题的一个纳什均衡点。证毕。

对于MAMRL 模型的收敛性，有命题2 成立。

命题2对于式(10)的梯度估计，可以建立估计值θiL(θi)和真实值∇θiL(θi)之间的关系为

证明对于RSUi在时刻t采取动作ati的概率可以表示为

考虑单个状态的情况下，策略梯度的估计量可表示为

因此，RSUi的期望奖励可以表示为

上式说明，在求解过程中，梯度步长朝着正确的方向移动，且随着RSU 数量的增加而呈指数级下降。证毕。

MAMRL算法的伪代码如算法1和算法2所示，其中算法1 为本地智能体训练过程，算法2 为元智能体训练过程。

算法1本地智能体训练

算法2元智能体训练

3.2 RSU 协同计算卸载算法

当所有RSU 的缓存策略确定后，优化问题P1将转换为车辆任务在缓存同一服务的RSU 之间进行协同计算卸载的子问题P2

将式(1)～式(3)代入优化问题的目标函数中，可以得到

变量和 是2 个独立变量，根据上文定义可知，它们都是由RSU 协同计算卸载策略β决定的，其定义和关系见2.2 节，因此可以通过求解式(14)来确定最优协同计算卸载策略。对于每一个缓存服务s，它与其他的缓存服务之间是独立的。因此，在问题求解过程中，下文以服务s为例，对于子问题P2，本文采用一种迭代的思路搜寻解空间中满足KKT 条件的结果作为优化问题的解。在RSU 协同计算卸载过程中，对于每一个RSU 都有工作量负载均衡等式成立，其中，Ii表示RSUi的接收任务量，Oi表示RSUi的输出任务量。根据定义，有成立。将上述等式代入优化问题，可将优化问题P2 转化为关于变量I和O的优化问题P3

为了求解上述优化问题，本文首先将RSU 处理计算任务分为3 种模式：接收模式、平衡模式、卸载模式。接收模式表示RSU 接收来自其他RSU的计算任务；平衡模式表示RSU 不接收其他RSU的任务也不发送计算任务给其他RSU；卸载模式表示RSU 发送自身的计算任务给其他RSU。RSU 在处理计算任务时，只能选择一种模式。同时，本文定义2 个辅助函数来进行优化问题求解，一是边界计算时延函数

它表示当RSU 处理任务的计算时延的边界值；二是边界网络拥塞时延

定理2RSU 在t时刻的任务处理模式和最优协同计算卸载策略如下所示。

其中，λt*和α是式(17)的解，λt*表示最优网络拥塞时延，α表示拉格朗日乘子，R和 F 分别表示网络中处于接收模式和卸载模式的RSU 集合。

由于直接通过求导来求解α存在较大困难，因此本文采用一种二分迭代搜索的思路来通过工作量负载等式寻找最优解。在每一次迭代中，首先通过初始参数α确定处于接收模式的RSU 以及其接收的任务量λR。然后，令λ=λR来确定网络中处于平衡模式和卸载模式的RSU，并计算卸载的任务量λF。如果λ R=λF，此时的α为最优解；否则，算法更新参数α并进入下一轮迭代。求解算法流程如算法3 所示。

算法3二分迭代协同计算卸载算法

输入RSU 接受任务量,i∈N,t∈T，RSU服务速率μi,i∈N，网络通信时间τ

输出

4 实验结果和分析

本文利用杭州真实的交通流数据模拟任务的产生，验证本文提出的车联网系统的有效性。系统中由一个云服务器和9 个RSU 组成（如图4 所示），每一个RSU 的覆盖区域为200 m×200 m，且为车辆提供8 种类型不同的服务。为了适应不同规模的任务量，RSU 布置在杭州市中心如图4 所示的9 个十字路口，且每一个车辆产生任务服从速率为[0,4]任务/2 分钟的泊松分布。其他参数设定如表2 所示。

图4 车联网系统布置说明

表2 参数设定

本文与3 种基准算法进行比较。1) 非协作卸载算法：RSU 完成缓存分配后，只有RSU 本地处理或上传到云服务器处理2 种情况。2) 单智能体缓存算法：采用单智能体强化学习进行缓存分配，然后采用协同计算卸载进行计算任务分配。3) 贪婪缓存策略：每个RSU 缓存最流行的服务，然后计算任务将在本地处理或上传到云服务器进行处理。

4.1 系统表现

图5 为不同智能体（9 个本地智能体和一个元智能体）获得的奖励值，本文计算每50 次迭代的平均奖励值。在MAMRL 框架中，所有的智能体经过1 000 轮迭代都会得到一个收敛的奖励值，其中，元智能体拥有最高的奖励值（大约为90），所有的本地智能体（RSU）在收敛时大约为80 到85，只有一个RSU 6 收敛时奖励值在70 左右。不同RSU 上的奖励值变化是由RSU 上处理任务的不同和分配资源的不同所导致的，同时也由强化学习中各个本地智能体求解资源分配方案过程中的探索和利用权衡所决定。

图5 多智能体元强化学习中不同智能体的奖励值

图6为本文提出的缓存分配策略在不同探索衰减下的系统表现。探索率表示强化学习过程中对于动作空间的探索概率，从而在探索和利用之间进行权衡搜索到最优的缓存策略。初始情况下，探索率大可以快速探索动作空间中的优秀策略，探索率逐渐衰减可以平衡动作选择过程中的探索利用效率，从而使智能体逐渐搜索到最佳策略（动作）。较大的探索衰减强调动作选取中的探索过程，可以获得更快的收敛速度，但是可能导致智能体对于动作空间探索不够完全；较小的探索衰减则强调动作选取中的利用过程，可能会获得更好的收敛结果，但是不断减小该值可能会影响收敛速度。因此在仿真实验中，本文将探索衰减设置成不同值来观察收敛效果，可以看出，当探索衰减大于1 0−4时，1 000 轮迭代内可以收敛；当探索衰减为0.1 时，收敛时的奖励值较低。

图6 不同探索衰减的收敛结果

4.2 性能对比

和其他3 种基准算法（非合作卸载、单智能体缓存、贪婪缓存）相比，本文提出的多RSU 协同缓存算法表现最优，能够得到最低的系统时延。图7 给出了不同缓存大小下不同算法的网络时延。缓存大小对于RSU 缓存内容的选择具有重要的影响，缓存大小为0 则表明所有处理任务的服务需要从云服器上下载，因此所有的缓存策略失去意义；如果缓存大小超过任务所需的服务个数，服务器可以缓存所有的服务，缓存策略也失去意义。因此，本文只讨论缓存大小在区间内不同算法的表现情况。从图7 中可以看出，随着缓存大小的增加，所有算法的系统时延都会有所下降，但是本文提出的算法相比较其他3 种算法表现更加优异；在缓存空间明显不足时，本文提出的算法相较其他3 种算法提升更明显，这说明本文提出的算法能够更好地应对资源有限情况下的缓存分配问题，即能够在有限的资源情况下，最小化系统时延。

图7 不同缓存空间下系统时延对比

图8 说明了不同缓存大小下不同方法中从RSU输出到云服务器处理的任务大小。当RSU 之间无法通过协同卸载来处理用户任务时需要将任务传输到云服务器来处理，这一过程需要相对高的传输时延。因此，输出到云服务器的任务量可以表明不同方法的协同卸载处理情况。从图8 中曲线可以看出，随着RSU 缓存空间的增加，更多的任务可以在RSU 集群内进行处理，因此传输到云服务器的任务数会越来越小，相比其他3 种算法，本文提出的算法因为具有协同计算卸载机制会在RSU 之间进行处理任务，而不是直接上传到云处理器，因此会大幅减少输出任务量；相比单智能体缓存算法，多智能体算法在缓存空间相对不足的情况下，表现更佳，这说明本文提出的算法在受限资源情况下表现更佳。

图8 不同缓存空间下输出任务情况对比

图9 和图10 分别表明了在用户产生不同数量任务的情况下不同方法的系统时延和输出到云服务器的任务数量分布。当用户产生的任务数量增加时，系统的计算压力会增大，导致系统时延增加，同时也需要将更多的任务上传到云服务器上进行处理。如图9 所示，用户产生的任务越多，所有算法的系统时延都呈上升趋势，其中贪婪算法和非协作卸载算法上升趋势明显，因为在缓存资源有限的情况下，依靠单独RSU 来处理对应任务效率低，只有通过多RSU 合作来处理相应任务才能获得更低的系统时延，相对于单智能体缓存算法，多智能体算法同时考虑每一个RSU 的任务情况，因此能够获得更低的系统时延。图10 表明用户产生任务的增加导致更多任务需要上传到云服务器处理。从图10 可以看出，用户任务在3 到6 时增长趋势较缓慢，而当用户任务继续增加后，由于RSU缓存空间有限，所有算法都需要将大量的任务上传到云服务器，因此输出任务数量增长趋势会更加明显。

图9 不同任务数下系统时延对比

图10 不同任务数下输出任务情况对比

5 结束语

本文在车联网边缘计算系统中联合考虑了用户任务缓存和边缘任务调度问题，并将其建模成一个混合整数非线性规划问题，从而最小化系统时延。为了降低问题求解的计算复杂度，本文提出一种双层的多RSU 协同缓存框架将问题进行解耦，其中外层采用多智能体元强化学习方法，在每个本地智能体进行决策学习的同时，采用LSTM 作为元智能体来平衡本地决策并加速学习，从而得到最优的RSU 缓存策略；在缓存策略确定后，内层采用拉格朗日乘子法求解最佳协同卸载策略，实现RSU 间的任务分配。基于杭州真实交通数据的实验表明，本文提出的算法具有很好的能效性能，并且能够在大规模任务流下保持网络稳健性。