基于边缘计算的计算资源分配和偏分任务卸载算法

王喜鸿，王良成，张小波

（1三亚理工职业学院 海南 三亚 572000）

（2三亚学院 海南 三亚 572000）

0 引言

随着移动设备和应用的飞速增加，对无线网络的吞吐量、低延时提出了更高的需求[1]。为了解决用户超低延时和用户设备更低能耗的需求，欧洲电信标准协会（European Telecommunications Standard Institute，ETSI）提出了移动边缘计算（mobile edge computing，MEC），其是在无线网络内为附近用户提供基础IT和云服务。另外，还出现了许多中边缘计算方式，如微云（cloudlets）、移动云计算（mobile cloud computing，MCC）、雾计算（fog computing）等。虽然概念十分相似，但是在技术上存在着非常大的差别。

1 MEC的概念

MEC是一种能够解决资源受限移动设备和资源密集型应用的技术，其具有MEC的数据中心，且在无线接入点或蜂窝基站部署了云资源，从而使终端设备用户和公有云数据中心的延迟得到了有效降低。MEC与MCC对比情况见表1。

表1 MEC与MCC对比情况

2 MEC的相关研究

当前关于MEC的相关研究包括资源分配、任务卸载两个方面，因此主要研究目标主要集中以下几方面。

2.1 降低任务处理时间

为了避免相同资源分配方案与用户状态的重复学习，采用多叠强化学习（reinforcement learning，RL）算法，同时对于频谱分配、传输功率分配进行优化，以此来实现用户之间的传输延迟最小化。也有非合作博弈方法，通过分布式迭代算法解决MEC任务，最小化任务执行延迟。

2.2 降低设备处理任务的能耗

胡锦天等[2]研究了MEC系统中时延敏感应用的节能任务接纳，并且提出了约束条件下总能耗最小化边缘服务器的计算资源和延迟。在时间截止、传输错误率等约束条件下，还提出了一种最小化移动设备能耗的卸载决策方法，并且该方法在可接受试验和通信质量下具有良好的效果。

2.3 在设备能耗间和任务处理时间的平衡

MEC应用程序的任务卸载功能能够提高移动设备的处理能力，并降低能耗，但其前提条件需集中在一个系统中。无线信道带宽有限，而设备需要网络资源，彼此之间会互相竞争，导致感染现象，降低数据传输速率，从而进一步延长数据传输时间[3]。另外，在边缘云数据中心计算资源有限时，最佳选择并不是边缘云端将所有应用程序卸载。而是，当前的移动终端设备性能在逐渐提升，在终端中处理部分移动应用程序，在边缘云数据中心处理另一部分，可以降低移动设备间数据传输时间延长的问题，并且对于数据中心计算资源的需求也可以显著下降。

综上所述，当前主要考虑的是任务卸载问题，如任务在本地设备处理、在边缘云处理[4]。因此，针对MEC的边缘云计算资源分配与偏分任务卸载问题开展研究。

3 设置MEC模型

典型的MEC系统，如下图1所示。多个服务器构成的数据中心和N个物联网设备构成了MEC系统模型。MEC系统模型，设物联网设备i∈[1，2，…，N]的任务为i。物联网设备中含有一个延迟敏感（delay-sensitive）、任务需要处理，而任务中需要大量的计算资源。通过本地设备、边缘云数据中心对于任务进行处理。通过基站(base station，BS）实现物联网设备对数据中心计算资源的访问[5]。其中，Di为任务i的大小；F为边缘云数据中心服务器的CPU频率；λ∈（0，1）为任务i本地处理的比例；fi，t为物联网设备任务i的CPU频率大小；Ci为完成任务i所需的CPU周期数。

图1 典型的MEC系统

3.1 本地计算模型

通过物联网终端设备处理移动应用程序。fi，t为设备的计算能力，使用每秒CPU周期来衡量。因此，物联网设备处理任务所需时间（Ti，t）和消耗的能耗（Ei，t）可表示为：

3.2 通信模型

利用无线信道，将应用程序卸载到边缘云，可以获得更多的上行链路传输能量和传输时间。上行传输的数据率（ri）可以表示为：

式中：Bi为分配给物联网设备i的带宽；q1为传输功率；h1为路径损耗；N0为噪声功率。

3.3 边缘云计算模型

数据中心收到任务后重新分配计算资源，对于任务进行处理。假设其计算资源分配采用fi，e表示，那么其在边缘云中的处理时间可表示为：

4 解决算法

4.1 问题构造

为了实现最小化系统计算开销，构造的优化问题可表示为：

4.2 问题解决算法

通过定理1提出解决算法。

定理1 总是有supf（x，y）= supf∽（x，y）成立。其中，supf∽（x，y）= supf（x，y）。

上式表明，当最小化1个函数时，可以对部分变量优先进行优化，然后再对剩余变量进行优化。因此，可以将问题变成2个子问题：子题1边缘云计算开销的最小化；子题2本地计算开销的最小化。其中，子题1可表达为：

其中，因为目标函数为凸函数，所以构造拉格朗日函数，并且基于凸优化中的KKT条件，得到以下结果：

通过式（7）、（8），可以了解到μ＞0，从而获得：

5 基于MEC的负载均衡方案

基于大量密集型部署MEC服务器导致的高能量消耗，推出一种MEC服务器休眠的负载均衡方案。根据M/M/m多服务台排队理论，对于MEC服务器的卸载任务量进行建模，通过集合均值迭代比较算法，将卸载任务量划分成2个不同卸载任务量集的MEC服务器集合，选择卸载任务量较低的MEC服务器，通过休眠操作，降低系统能耗，保证网络负载均衡。

5.1 系统模型

将1个宏基站和M各小区基站构成密集异构网络，在小区基站侧部MEC服务器，网络用户在MEC中卸载计算任务。设定每个MEC服务器的覆盖范围，假设用户随机接入，整个网络的用户卸载任务量会随时间变化而变化[6]。

5.2 方案设计

假设网络中一共有N个活跃状态的MEC服务器，其休眠操作是以T为周期进行循环。在单个周期内操作步骤如下：

步骤1 宏基站获取小区中MEC服务器卸载情况，根据预设卸载任务量阈值，得到MEC服务器休眠操作待选子集。在集合为0的情况下，表示当前周期T内MEC服务器不需要进行休眠操作。

步骤2 对于MEC服务器休眠操作待选子集，随对应的卸载任务量集合排序后，进行MEC服务器休眠操作。

步骤3 执行集合均值迭代比较算法，在第i次进行计算平均卸载任务量的过程中，系统对集合中最后1个MEC服务器中的卸载任务量MEC服务器集合的算数平均值，如果该值大于或等于卸载任务量，则可以认为从MEC服务器开始，集合中各个MEC服务器的卸载任务量均低于平均卸载任务量。因此，该算法可以分为步骤3.1和步骤3.2这2个卸载任务量级别不同的集合，其中步骤3.1为卸载任务量较小的集合，可以将其纳入休眠操作范围；而步骤3.2为卸载任务量较大的集合，继续保持活跃状态[7]。

步骤4 根据步骤3的结果，选择步骤3.1作为需要执行休眠操作的MEC服务器集合，宏基站将休眠信号发送到小区中的MEC服务器之前，详细步骤3.1中的MEC服务器执行休眠操作是否会出现服务质量退化的情况。如果满足该条件，则选择相应的MEC服务器执行休眠操作。

在执行完上述步骤之后，进入单周期内的MEC服务器技术休眠操作流程，在下一个周期到来前，系统从最初步骤开始执行。通常情况下，当系统中的卸载任务量较少时，如果网络中的MEC服务器保持活跃状态的话，会消耗大量的能量，因此需要执行休眠操作，避免卸载任务量过少的空闲MEC服务器而产生大量能耗[8]。当系统中需要MEC服务器处理的卸载任务量增加之后，此时保持活跃状态的MEC服务器所可以服务的卸载任务量会达到上限，随后通知处于休眠状态的MEC服务器进入活跃状态，对于卸载任务量进行高效处理。

6 仿真实验

6.1 设置参数

一个MEC系统中共有N个（N=5）设备，对于物联网的参数设置见表2。本文研究更侧重于部分任务卸载情景。

表2 参数设置

6.2 实验结果

为了对于本文提出的算法有效性进行验证，对于本地任务处理(local)（本地设备端处理所有的任务）和边缘云任务处理（edge cloud）（所有任务均经过边缘云设备端进行处理）进行对比。

物联网设备的任务选择决定如上图2所示，物联网设备的任务是由不同带宽值来选择确定的。其中，0表示任务卸载到了本地设备，而1表示物联网设备将任务卸载到了边缘云。可以看出，如设备1和设备2需要计算资源较少。如果带宽值较小，则物联网设备可以在边缘云卸载任务，然后处理任务。

图2 物联网设备的任务选择决定

随宽带变化的任务处理时间变化情况，如下图3所示。其中，系统代价是以任务处理时间和能耗来进行判断的。网络带宽值较小时，各个方面更大。

图3 随宽带变化的任务处理时间变化情况

本地处理所需时间最小情境下的算法最低能耗如图4所示，本地处理消耗的能量逐渐高于边缘云处理所消耗的能量。

图4 随着宽带变化的任务处理时间的变化

随着网络带宽值的增加，边缘云处理的系统代价要低于本地处理，系统代价更小，证实了算法的有效性。系统代价随着宽带的变化情况，如图5所示。

图5 系统代价随着宽带的变化情况

7 总结

综上所述，因为当前多MEC服务器部署下，考虑到用户和服务器效益，导致卸载和资源分配的难度大大提升。通过研究边缘计算的计算资源分配和任务卸载问题，提出了任务卸载与计算资源分配算法，结果表明可以有效降低任务处理的能耗和延迟。