基于边缘计算的新型任务卸载与资源分配策略*

薛建彬,安亚宁

(兰州理工大学计算机与通信学院，甘肃 兰州 730050)

1 引言

随着移动互联网和大数据技术的不断发展，终端用户需要运行越来越多的资源和计算密集型应用，如远程医疗、图像处理等[1]，但由于终端用户本身的局限性，无法满足密集型任务低时延、低功耗的需求，因此，为了提高终端用户的满意度，需要为终端用户提供大量的计算和存储资源。移动边缘计算MEC (Mobile Edge Computing)通过在无线网络边缘为用户提供计算、存储和处理能力，由于MEC的邻近性、低时延等优势，MEC在时延敏感、实时性要求高、数据量大等场景中的应用中尤为常见[2]。但是，由于边缘服务器的计算处理能力有限，在实际应用中，当有大量用户和任务请求计算时，单个边缘服务帮助终端处理任务时，将不足以为用户提供计算资源，同时还产生了额外的开销，从而无法满足用户体验。因此，研究多个边缘服务器协作，将计算资源进行合理分配，具有重要的现实意义。

针对边缘计算中的任务卸载和资源分配,许多学者做了相关研究。Lin等人[3]提出一个D2D(Device-to-Device)协作的计算卸载和资源分配系统，以最小化任务执行成本。文献[4]通过考虑二进制卸载模型，研究了终端设备的计算模式选择、系统传输时间分配的联合优化问题,旨在最大化所有终端设备的计算速率。文献[5]研究了卸载决策和资源分配的联合优化问题,目的是降低系统的总能耗。Wang等人[6]在延迟约束条件下，提出一种有效的卸载方案，通过联合优化AP(Access Point)的能量波束成形、CPU周期数、卸载的任务数大小以及分配给每个用户的时间，最小化AP端能耗。文献[7]在延迟约束条件下，建立4个时隙协作协议下的三节点模型，通过联合优化任务分配，最小化用户和助手的总能耗。

文献[3-7]仅研究了单个服务器的MEC系统，在此基础上，有学者研究了多个MEC协作的系统。其中，文献[8]提出了一种新的卸载方案，通过多个MEC-BS(Mobile Edge Computing Base Station)的协作进一步将额外任务卸载到与其连接的其他MEC-BS来增强MEC-BS的计算卸载服务，提高了终端的收益。Yang等人[9]提出一种由微基站和宏基站组成的双层体系架构，用户通过将计算任务卸载到微基站或由微基站中继到宏基站来完成任务执行，有效降低了系统能耗。虽然文献[8,9]在降低时延和能耗方面有良好的效果，但只考虑将终端的任务进行单一的划分。进而，文献[10]研究了将终端用户的任务分割成多个子任务，并选择卸载到边缘的多个AP节点上的情况，通过联合优化任务分配决策及其CPU频率以最小化其能耗和任务的执行延迟，有效地降低了设备能耗和延迟。Wu等人[11]设计了无线供电的多用户MEC系统，用户将其计算任务划分为多个部分，分别进行本地计算和边缘计算，以最大化用户的计算速率，即特定时间块上的计算位数。

尽管上述关于MEC中任务卸载和资源分配的研究都有独特解决方案，但仍存在一定的局限性。现有研究大多仅考虑单节点计算卸载和资源分配，对多节点协作计算的资源分配鲜有研究；同时，大多数研究仅考虑全部卸载或者单一任务划分的部分卸载模型，对细粒度任务划分很少涉及。基于此，本文提出一对多的广播系统任务分配问题，即将每个终端用户所需要计算的任务划分为多个子任务，分别在自身设备和不同的AP上并行执行，在延迟约束条件下，设计了一种基于拉格朗日乘子法的任务分配优化算法，对用户本身和不同参数的AP进行合理的任务分配，以联合优化任务分配和执行时延，实现最小化系统开销。

2 系统模型

图1搭建了一个协同计算卸载任务分配系统，假设考虑系统中的一个具有可分割的待处理密集型任务的终端用户，一个协助终端用户处理任务的AP集合N={1,…,N},称之为代理集合，第i(i∈N)个AP称为代理i，表示为Ai。终端用户UE通过本地计算和利用无线网络将自身的任务卸载到代理AP进行任务处理，AP帮助计算处理之后将结果返回给用户。

Figure 1 System model图1 系统模型

2.1 传输时间模型

本文考虑具有持续时间T的一个特定时间块，终端用户和N个AP之间的计算卸载采用频分多址FDMA(Frequency Division Multiple Access)协议，如图2所示。终端用户和AP之间的通信分配有带宽为B的正交频带。对于每个代理Ai(i∈N)，该时间块T被分为3个时隙，表示为τi1，τi2和τi3，分别用于终端用户将计算任务Oi卸载到Ai，Ai进行远程计算以及Ai将计算结果下载到终端用户。考虑到卸载任务经过Ai处理之后，任务量大小远远小于原始任务量大小，因此本文忽略Ai将计算结果下载到终端用户的时延τi3，即τi3=0。因此，时延必须满足：

τi1+τi2≤T,∀i∈N

(1)

Figure 2 FDMA-based computing offloading protocol图2 基于FDMA的计算卸载协议

2.2 计算模型

每个用户具有一个可分割的计算任务，可以任意地将计算任务划分为(N+1)个部分，以便分别在用户自身和代理AP处并行执行。为了便于分析，将终端用户总的计算任务量表示为L(Mb)，用l表示用户进行本地计算的任务量，用Oi表示第i个代理Ai分配的任务量。因此，计算任务量满足以下约束：

(2)

(1) 终端用户在整个时间块T执行本地计算任务l时，用C0表示终端用户计算单位比特卸载任务所需要的CPU周期数,因此本地计算的能耗为：

(3)

其中，k0表示有效电容系数，取决于设备的CPU结构。

进一步，本地能耗开销表示为：

(4)

其中，0<ω0<1为本地能耗惩罚因子。

(2) 当用户选择将任务卸载到边缘代理时，通过无线网络传输会产生相应的传输时延和能耗开销。故用户端到代理Ai端的传输速率为：

(5)

因此，终端用户卸载到Ai的任务量可表示为：

Oi=riτi1,∀i∈N

(6)

在第1时隙，终端用户将计算任务上传到AP，在上传过程中，产生的传输能耗为：

(7)

对式(5)～式(7)化简可得：

(8)

所以，终端用户(EU)传输、卸载任务总的能耗开销为：

(9)

其中，0<ωi<1为传输能耗惩罚因子。

在第2时隙，每个AP对终端用户上传的任务进行远程计算，Ci表示Ai计算单位比特卸载任务数所需要的CPU周期数，故Ai处理Oi任务消耗的能量为[6]：

(10)

其中，ki表示有效电容系数，取决于设备芯片结构，本文令ki=10-21。

因此，所有代理AP为终端用户远程计算任务总的能耗开销为：

(11)

其中，0<αi<1为远程执行任务时的能耗惩罚因子。

2.3 收益模型

系统的收益来自于边缘代理，边缘代理AP通过为用户提供服务获得收益，因此系统的收益函数与用户的资源需求量密切相关，任务需求量越大，获得的收益也越多。本文采用在移动云计算和无线网络通信中普遍使用的对数函数表示计算任务卸载的效用收益[12]，因此终端用户将Oi任务卸载到Ai获得的收益表示为：

Gi=φfpilog2(1+Oi)

(12)

其中，fpi表示Ai的计算能力；φ是一个大于0的参量，与用户QoS需求有关。

3 问题描述

根据上述分析，通过优化分配的计算任务量{l,Oi},i∈N，根据当前的网络环境选择为哪些AP卸载多少计算任务以及为本地分配多少任务量等，并优化自身时延分配策略{τi1,τi2}，从而最小化系统开销。本文给出了优化目标函数如式(13)所示，将问题描述为(P1)：

(13)

s.t.τij≥0,j∈{1,2},∀i∈N

(13a)

0≤l≤L

(13b)

0≤Oi≤L,∀i∈N

(13c)

式(1)和式(2)

(13d)

其中，式(13a)表示时延约束，式(13b)、式(13c)是任务量约束。

4 资源分配方案

根据上述分析，终端用户为了提高自身的任务处理效率，节省系统能耗，缩短时延，将会根据自身设备和不同的边缘代理的属性及信道环境，为不同代理和自身分配不同量的任务，以使系统开销最小。

4.1 基于拉格朗日乘子法的任务和时延分配优化

本节通过拉格朗日分解方法简化模型对问题进行求解。拉格朗日松弛算法已经成功应用于许多优化问题，如网络优化问题、生产调度问题及整数优化问题等。首先证明所提优化问题是一个凸问题。

定理1目标函数U是优化变量(l,Oi,τi1,τi2)的凸函数。

证明首先，对目标函数U求各优化变量的一阶偏导，可得：

(14)

(15)

(16)

(17)

其次，对目标函数U求各优化变量的二阶偏导，可得：

(18)

(19)

(20)

(21)

显然，目标函数U是各优化变量的下凸函数，因此定理1成立。

□

由于约束条件式(13a)～式(13d)是线性函数，所以(P1)问题是凸优化问题。本文采用拉格朗日对偶方法来获得问题(P1)的最优解。λ≥0和μi≥0分别表示关于约束式(1)和式(2)的拉格朗日乘子，因此构造拉格朗日函数为：

(22)

(P1)问题的对偶函数为：

(23)

所以，(P1)问题的对偶问题表示为(P2)：

(24a)

s.t.λ>0,μ≥0

(24b)

因为(P1)问题是凸问题并且满足Slater条件，因此原始问题(P1)和对偶问题(P2)存在强对偶性，因此，可以通过求解(P1)问题进而获得(P2)问题的解。利用KKT条件可以得到：

(25a)

(25b)

(25c)

(25d)

(25e)

(25f)

(26a)

(26b)

(26c)

(26d)

4.2 次梯度算法优化拉格朗日乘子

对于拉格朗日求解的算法，证明局部最优解与全局最优解是基本一致的，其中次梯度算法是求解拉格朗日问题的有效方法[13]。因此，本文利用次梯度算法对拉格朗日乘子μi进行不断迭代更新，得到优化变量的最优解。迭代公式为：

(27)

拉格朗日乘子更新算法具体步骤如下所示：

步骤1初始化参数精度ε>0,令t=1,μi(1)>0，根据式(26b)～式(26d)计算(Oi,τi1,τi2)。

步骤2根据式(27)更新拉格朗日乘子μi(t)。

步骤3再根据式(26b)～式(26d)更新(Oi,τi1,τi2)。

步骤4判断迭代是否终止。如果|Oi(t+1)-Oi(t)|<ε，|τi1(t+1)-τi1(t)|<ε，|τi2(t+1)-τi2(t)|<ε或t>Tmax，则终止迭代，所得即为最优解；否则,令t=t+1，返回步骤2。其中，Tmax是最大迭代次数。

5 仿真结果及性能分析

为了验证本文提出的最优任务和时延分配方案对系统性能的影响，采用Matlab仿真并分析所提方案的性能。本文取N=3，即有3个代理协助终端用户处理密集型任务；对于不同的计算任务量，将系统总时延设定为等差数列，即当总任务量L=10时，取T=0.1，当总任务量L=200时，取T=2，任务量越大，执行任务所需要的时间越多。其它仿真参数如表1所示。本文采用2种基准方案作为对比方案，并将本文所提方案与文献[3]所提方案进行对比分析。具体如下：

(1)仅本地计算方案。即传统的任务处理方式，将用户计算任务全部留在用户端进行本地计算而不进行任务卸载，对应于本文参数设置为：l=L，Oi=0，τij=0，∀i,j。

(2)等时间等任务分配方案。即将用户请求计算任务平均分配给本地和边缘代理服务器，以及将时间进行平均分配，对应于本文参数设置为τi1=τi2=T/2，l=Oi=L/4,i∈{1,2,3}。

(3)文献[3]方案。选取与本文所采用参数匹配的参数对文献[3]所提方案进行仿真，并与本文方案仿真结果进行对比分析。

Table 1 Simulation parameter setting表1 仿真参数设置

图3所示是用户端到边缘代理1、代理2和代理3的距离di分别为80 m、60 m和40 m时，用户端计算任务总量与任务分配量的关系。从图3中可以看出，任务分配量随任务总量的增大而增大，由于用户本身具有固定的计算能力，所以随着总任务量的增大，分配给用户本身的任务基本趋于平稳。图3中，距离用户端较远且计算能力较弱的代理1，被卸载较少的计算任务量；而距离用户端较近且计算能力较强的代理2和代理3，会被分配较多的计算任务量，并且随着用户端计算任务量的不断增大，代理2和代理3被分配的计算任务越来越多，而代理1变化较小，其原因在于代理1计算能力较弱且与用户端之间的通信距离较大，造成的通信开销也较大。

Figure 3 Relationship between total number of tasks and task allocation图3 计算总任务量和任务分配关系

图4描述了4种不同方案的系统开销随用户端计算任务总量的变化曲线。如图4所示，任务执行开销均随着输入数据大小的增加而增加，原因在于较大的输入数据需要较长的执行等待时间和较大的能量才能完成任务计算，从而导致较大的任务执行成本。

可以直观看出，本文所提方案明显优于2种基准方案，其原因在于所提MEC系统能实现任务的合理分配，使得本文方案具有较低的系统开销。此外，等时间等任务分配的情况下，均衡任务和时间分配，不是最优的分配方案，因此开销并未最小化；而仅考虑本地计算的情况，由于本地计算能力固定且较小，故所产生的系统开销较大。比较从本文所提方案和文献[3]中获得的结果，可以看到本文提出的方案具有更好的性能，特别是当任务量较小时，任务执行开销基本一致，而随着任务量的不断增大，本文所提方案更优于文献[3]的。

Figure 4 Relationship between total number of tasks and system overhead图4 计算总任务量与系统开销关系

Figure 5 Relationship between total tasks and task allocation under different distances图5 不同距离下总任务量与任务分配关系

图5描述了用户端到代理端的距离不同时，用户总任务量与各个代理任务分配的关系。从图5中可以看出，当距离相等时，计算能力较强的代理分配到的任务较多，其原因在于计算能力越强，帮助终端计算任务的能力越强，从而能耗和延迟较小，系统开销也较小；另外，对于同一代理，分配到的任务量随着距离的减小而增加，这与图3的仿真分析结果相吻合。

6 结束语

本文研究了移动边缘计算环境中，具有可分割的待处理密集型任务的终端用户的计算卸载和资源分配问题。在考虑用户时延的需求下，提出了以最小化系统所有实体开销为目标的优化问题，开销主要由能耗成本和卸载收益组成；然后基于拉格朗日法求解该约束优化问题，并为用户本身和各个代理AP进行合理的任务分配；最后得到了最优的任务和时延分配结果，有效地降低了系统开销，提升了系统整体性能。