一种基于强化学习的多节点MEC计算资源分配方案*

2019-12-11余萌迪唐俊华李建华

通信技术 2019年12期

余萌迪，唐俊华,2，李建华,2

（1.上海交通大学网络安全技术研究院，上海 200240；2.上海市信息安全综合管理技术研究重点实验室，上海 200240）

0 引言

2006年，“云计算”（Cloud Computing）由Google率先提出。通过虚拟化技术把许多计算机资源集合为资源共享池，即“云”。用户通过网络可以按需申请使用这些计算机资源，以此来执行超出终端设备能力外的各类型任务，如计算型任务和存储型任务等。对于计算型任务，计算能力有限的终端用户可以打包这些数据运算需求大的任务上传到中心云，中心云执行任务并返回计算结果给用户，此过程称为计算卸载技术。云计算为终端执行计算型任务提供了手段，但是终端与中心云之间的长距离不可避免地引入了较大时延。现在即将迎来5G时代，数据流量急剧增长，且5G系统中有着各种各样对时延要求高的应用，如实时在线游戏、虚拟现实、超高清视频流等[1]。传统的云计算不仅无法负担庞大的流量造成的核心网压力，而且其较长传输距离不能满足应用对于时延低的要求。为了解决这两大问题，移动边缘计算（Mobile Edge Computing，MEC）应运而生。它的基本设计思想是将云服务从遥远的数据中心移至用户边缘[2]。

MEC大大缩短了任务执行时延。传统云计算中，计算任务需要经过无线接入网、回传链路到达位于核心网的中心云服务器。MEC将边缘服务器部署在无线接入网侧，任务卸载无需经过回传链路与核心网，极大得降低了时延开销。同时，边缘服务器的处理能力远大于移动设备，可满足用户对于计算资源的需求。

计算卸载作为MEC的关键技术，主要包含卸载决策和计算资源分配两个问题。卸载决策决定用户终端是否需要卸载、卸载多少以及卸载什么。计算资源分配则决定将计算任务卸载到哪个MEC节点。近年来，已有许多学者围绕卸载决策进行了相关研究[3-4]，本文针对用户已经做出计算卸载决策后面临的计算资源分配问题进行研究。具体考虑如图1所示的5G场景下MEC的双层网络架构[5]，家庭基站通过光纤等联结多个微蜂窝基站。MEC服务器部署在微蜂窝基站上，因此家庭基站节点不仅为用户设备提供了无线接入服务，还承担了将用户卸载的任务分发给多个MEC服务器的功能，即完成MEC计算资源的分配。

多节点MEC计算资源分配的难点主要在于各MEC节点的工作负载强度。由于大量用户设备不规律的任务卸载呈现出动态变化且难以准确预测，而资源分配不合理会导致某些MEC节点出现严重的任务过载，造成用户等待时延过长。针对这个问题，本文提出了一种基于多Agent强化学习的分布式计算资源分配算法。家庭基站按照该算法，通过学习自主决策，将卸载任务分发到合适的MEC节点，实现MEC服务器负载均衡，从而在不增加额外通信开销的情况下满足用户的低时延需求。最后，通过仿真实验对算法进行验证，将其与其他方法进行比较，分析其有效性。

图1 带有MEC功能的双层网络架构

1 MEC系统模型

如图1所示，用户通过无线链路接入家庭基站，家庭基站与微蜂窝基站之间、微蜂窝基站与核心网之间的通信链路利用有线的光纤，MEC服务器部署在微蜂窝基站。当终端用户的应用产生计算任务后，移动设备运行自己的卸载决策算法决定何时以及要卸载哪些计算任务。用户将需要卸载的计算任务打包上传给家庭基站，家庭基站依据资源分配算法将收到的计算任务转发给特定的带有MEC功能的微蜂窝基站。来自多个家庭基站的计算任务到达MEC服务器后，首先进入缓存队列中排队。MEC服务器按照先到先服务（First Come，First Serve，FCFS）的策略执行任务。任务处理完成后，MEC服务器将任务完成结果返回给家庭基站，家庭基站再转发给用户。本文聚焦于延迟敏感型任务，因此不考虑计算任务需要进一步上传到核心网的中心云服务器这种情况。假设用户设备与家庭基站的无线带宽以及家庭基站与MEC服务器之间的带宽充足，避免MEC服务器出现拥塞是本文的主要设计目标。

系统中家庭基站的数量为I，用APi,i∈{1,…,I}来表示家庭基站。用xi(t)表示时刻t时家庭基站APi中需要转发的计算任务，任务xi(t)所需计算量为ωi(t)（比特），其中ωi(t)为0表示待处理队列为空。MEC-微蜂窝基站数量为J，用Ej, j∈{1,…,J}代表MEC-微蜂窝基站。MEC-微蜂窝基站Ej当前的缓存任务队列长度由Qj(t)表示，单位为比特。Ej的处理能力用Rj表示，单位为b/s。用完成任务所需时间来量化MEC服务器的负载强度，则MEC-微蜂窝基站Ej当前负载强度Lj(t)=Qj(t)/Rj。每个家庭基站以分布式方式选择执行任务的MEC-微蜂窝基站。定义一个I×J的决策矩阵[γji(t)]表示时刻t的计算任务卸载选择策略，γji(t)∈{0,1}，γji(t)=1代表在时刻t家庭基站APi选择将计算任务转发到MEC-微蜂窝基站Ej上完成具体计算。如果家庭基站APi不选择MEC-微蜂窝基站Ej，则γji(t)=0。

决策矩阵[γji(t)]给定后，可以得到各个MEC-微蜂窝基站的负载状态。假设家庭基站与MEC-微蜂窝基站间的传播时延很小，不考虑传播时延给MEC-微蜂窝基站负载带来的影响，则MEC-微蜂窝基站Ej的负载变为：

为了达到MEC服务器端的负载均衡，在多用户多MEC节点场景下，计算资源分配的优化目标函数可以表示为：

移动边缘云计算平台由多个MEC计算节点组成，负载均衡可以使得每个计算节点都能够得到充分有效的利用，防止部分机器长期满负荷运行或者空闲所带来的故障和资源浪费问题，保障计算任务的低时延。

2 基于强化学习的计算资源分配算法

在本文的网络场景中，由于整个系统中不存在中心调配器，家庭基站需要通过分布式决策选择合适的MEC节点，以实现服务器端的负载均衡。根据目标函数的特性，最小化MEC-微蜂窝基站负载的标准差是个NP问题。因此，为了有效得到全局次优解，本文受多臂赌博机的启发[6]，提出了一种基于强化学习的计算资源分配算法。各个家庭基站利用该算法，基于过往经验评估当前各MEC-微蜂窝基站的状态从而进行独立决策。

由于算法操作对于每个家庭基站都是相同的，以下阐述省略下标APi的下标i。家庭基站AP维护两张评估表格——MEC节点评分表S(t)和MEC节点归一化时延表β(t)表，作为分布式决策的依据。因此，以下从S表的学习、β表的学习和决策流程3个方面，介绍设计的基于强化学习的MEC资源分配算法。

2.1 MEC节点评分表（S表）的学习

如表1所示，S(t)表是家庭基站对各个MEC节点的评分（初始分数为0）。评分越高，表示该MEC节点负载越轻，在分发新任务时基站会优先考虑这些节点。

表1 MEC节点评分表（S表）

AP维护一个列表Table(t)，用以记录正在执行该AP分发的任务的所有MEC节点。具体来说，当一个新任务被分发给某个MEC节点时，把该MEC节点标号插入列表。当计算结果返回时，把对应的MEC节点标号从列表中删除。

在为一个新任务选择MEC节点之前，采用下列方法更新评分表S(t)。对于Table(t)中的所有MEC节点，表示在新任务到来之时旧任务尚未完成，因此认为该节点负载较重。为此，引入一个惩罚值punish，对Table(t)中的所有MEC节点Ej，将其评分表中的评分减少一个惩罚值punish，即Sj(t+1)=Sj(t)-punish其中punish为一个预先设置的正整数值（通常设为1）。

2.2 MEC节点归一化时延表（β表）的学习

如表2所示，β表记录各个MEC节点的归一化时延，初始为0。

表2 MEC节点归一化时延（β表）

当任务x(t)的执行结果从节点返回AP时，计算结果到达时间与任务发出时间之间的时延为Dj(x(t))。归一化时延定义为：

其中ω(t)是任务x(t)的计算量。上述定义中，除以ω(t)是为了更好地衡量由MEC节点的负载状态差别带来的对任务处理时延的影响，消除计算任务本身需求计算量大小不同带来的时延差别。β表中βj(t)表示Ej完成任务的平均β值。当βj(x(t))产生时，分别对S表和β表进行如下更新。

（1）定义 reward=sign(βj(t)-βj(x(t)))，Sj(t+1)=Sj(t)+reward。

（2）βj(t+1)=αβj(t)+(1-α)βj(x(t))(0＜α＜1)。

（1）中比较MEC节点Ej的历史时延βj(t)与当前时延βj(x(t))之间的变化，利用符号函数将两者之差转换为一个奖励信号值reward，再用该reward值更新S表中对应Ej的评分Sj(t)。可见，当前时延减小时，reward值是正值，对应MEC节点的Sj(t)得到增加，提高了该MEC节点在决策阶段被选取的可能性。

（2）中则依据预先设定的参数α，对β表中对应的值进行更新，完成学习的过程。

2.3 资源分配决策流程

用户将需要卸载的计算任务上传给与其连接的家庭基站，计算任务进入家庭基站的待处理任务队列中排队，家庭基站依照如图2所示决策流程完成资源分配。

S1：在每一时隙开始时，家庭基站检查待处理任务队列是否为空。若为空，则不做任何操作；若非空，则取出队列头部任务x(t)。

S2：按照描述的方法更新MEC节点的评分表S表。

S3：家庭基站选择S表中得分最高的MEC服务器。

S4：家庭基站将队列头部任务x(t)转发到S3中选出的MEC服务器Ej。

图2 家庭基站（AP）任务分发决策流程

3 数值仿真结果与分析

通过PYTHON编程仿真方法来具体评估所提计算资源分配算法的性能。在模拟实验网络架构中，家庭基站数量I=300，MEC-微蜂窝基站数量为J=5。家庭基站每个时隙收到计算任务的概率为ρ，计算任务长度服从[ωmin,ωmax]区间的均匀分布，MEC服务器的处理能力为Rj，那么定义系统任务到达强度TI为单位时间需要卸载的任务计算量除以MEC服务器的计算能力，即：

用MEC服务器负载的标准差和平均值两个评价指标衡量算法负载均衡的有效性，并与以下两种资源分配方法进行比较：随机选择（RS）算法，即当家庭基站收到计算任务时，等概地选择一个MEC节点进行任务卸载；SLS[7]算法，该算法中家庭基站像本文所述维护两张表，但收到需要卸载的计算任务不会触发表的更新。当家庭基站收到计算任务时，它直接选择得分最高的MEC节点进行任务卸载。

标准差用来衡量MEC服务器的负载均衡程度：

其中Lj为MEC节点Ej的负载，L-表示所有MEC节点的负载平均值，L-反映了整个系统的负载强度。显然，标准差WB越小，MEC服务器之间工作负载的差异越小。

图3、图4和图5分别展示了当系统任务到达强度为0.5、0.7和0.9时，3种资源分配算法的负载标准差随时间变化的曲线图。其中，DSS（分布式MEC节点选择算法，Distributed MEC-Server Selection）表示本文方案。可以看出，所提方法比RS、SLS两种方法能更好地实现负载均衡，尤其是在高任务到达强度的情况下。图3中RS方法的负载均衡效果同样较好，这是因为RS方法中，每个MEC服务器要处理的任务量相同，最弱处理能力的MEC服务器也能够负担得起这样较小的任务计算量。但如图4和图5所示，当任务强度增大时，弱处理能力的MEC服务器没有办法负荷增大的任务量，任务队列长度不断增加，而强处理能力的MEC服务器还可承担更多的任务，导致一些MEC服务器中过载运行，而其他MEC服务器未被充分利用，所以RS方法在重任务强度时MEC服务器负载出现显著的不均衡。

图3 MEC服务器负载标准差(TI=0.5)

图4 MEC服务器负载标准差(TI=0.7)

图5 MEC服务器负载标准差(TI=0.9)

本文提出的方法中，用户通过记录MEC服务器引起的时延推测队列长度的变化，可以避免选择负载越来越重的MEC服务器。同时，奖励机制是非即时的，新增的惩罚系数能够更好地记录正在执行任务对服务器负载的影响，所以DSS比SLS能更好地实现负载均衡。

用MEC服务器负载的平均值衡量系统的负载强度。如图6所示，当任务强度较大时，服务器的平均负载情况为RS＞SLS＞DSS。这是由于当任务强度较大时，RS和SLS方法中MEC服务器负载均衡性能较差，负载不均衡时一些MEC服务器过载运行，而其他MEC服务器空闲，系统以低速执行计算任务。显然，小的服务器负载带来较低的任务时延，可以提升用户体验。因此，本文提出的方法因其优越的负载均衡性能可以给用户带来更低时延的体验。