基于单用户和分类任务的MEC任务卸载策略及性能优化

李小良，李 伟，金顺福,*

(1. 开滦集团 信息与控制中心，河北 唐山 063018；2. 燕山大学 信息科学与工程学院，河北 秦皇岛 066004)

0 引言

随着移动设备使用数目的增加以及5G技术的飞速发展，人们开始对数据计算等有了更高的要求。根据互联网数据中心(Internet Data Center, IDC)报告[1]，预计到2025年，全球数据总量将会超过163 ZB，这其中有超过40%的数据将在网络边缘处理。面对网络新时代，传统的云计算平台暴露出了实时性差、阻塞率高、能耗开销大等诸多不足[2]。为了用户的网络服务体验，移动边缘计算(Mobile Edge Computing, MEC)的范式应运而生[3-4]。MEC平台下的任务卸载策略问题成为相关领域的研究热点。

为了制定合理的任务卸载策略，近年来，国内外诸多学者已经进行了大量工作。Kuo等[5]搭建了关于MEC的能量消耗模型，提出了一种系统级方法用于找寻任务卸载过程中最佳的节能方案。为了使MEC中能耗达到最优水平，Long等[6]提出了一个边缘云协作架构，并将框架中计算卸载问题建模为一个带有约束的NP难题，应用贪心算法以及模拟退火算法得出了最佳计算卸载方案。龙隆等[7]提出了一种基于博弈论的计算卸载与资源分配的联合优化算法，用于解决MEC中移动终端产生的高时延问题。上述文献对MEC系统卸载策略问题的研究均局限于一个度量角度，不能够全面地提升用户体验。

针对不同应用情景下的MEC服务，研究人员搭建出了各具特色的MEC系统框架。为了研究MEC环境下车辆的能耗和延迟等问题，Yang等[8]搭建了一个由多台同构虚拟机组成的车辆MEC框架，并设法解决任务卸载决策和计算资源分配的联合优化问题。Delfin等[9]搭建了一个由用户层、雾计算层和云层等三部分组成的雾计算框架。通过在雾计算层配备多台同构虚拟机，缩减了用户的请求响应时间。Li等[10]提出了一种由边缘和云共同组成的边缘云架构，云负责管理和监视边缘中的资源和服务，而边缘则负责处理分配给自己的服务请求。上述文献所构建的MEC系统框架考虑的均为同构边缘。然而，在实际MEC情景中，边缘往往是异构的，即分布在MEC边缘处的计算资源种类多样，计算能力存在一定差异。

本文对整体智能家居等专用MEC应用情景中的卸载问题进行研究，考虑不同任务的处理需求，提出一种基于单用户和任务分类的MEC任务卸载策略。搭建带有异构边缘的MEC系统框架，建立由M/M/1、M/M/c和M/M/∞等经典排队组成的系统模型，评估基于单用户和任务分类的MEC任务卸载策略的系统性能，并进行系统实验。以最小化系统成本为目标，应用卡罗需-库恩-塔克(Karush-Kuhn-Tucker, KKT)条件方法，给出任务卸载策略联合优化方案。

1 MEC系统框架及任务卸载策略

1.1 MEC系统框架

在整体智能家居等专用MEC应用场景中，家庭网关通常会同时收到来自家庭内部的多种数据任务[11]。这些任务或者直接在本地处理，或者被卸载到网络边缘和云端。结合整体智能家居等专用MEC的应用特点，在MEC系统中，引入分类处理机制，将任务划分为低速、中速和高速等三类。为了充分满足各类任务的处理需求，搭建基于单用户和任务分类的MEC系统架构，如图1所示。

图1 基于单用户和任务分类的MEC系统架构Fig.1 Architecture of a MEC system based on single-user and tasks classification

图1所示的MEC系统架构由本地端、基站、边缘端和云端四部分组成。本地端和边缘端分别部署了一台任务调度器，用来实施任务的卸载策略。通过调节任务调度器上的任务卸载策略参数，实现各类任务在MEC系统中的合理分配。

在本地端，考虑一名用户(单台移动设备)的接入。本地端配备有本地调度器、本地处理器、本地发送端口和本地接收端口等装置，分别用于实现任务在本地端的决策、处理、发送和接收等功能。本地处理器、本地发送端口和本地接收端口各自带有一个容量不限的缓存空间。当本地处理器、本地发送端口或本地接收端口被占用时，新到来的任务会在缓存区中排队等待。

边缘端配备有MEC调度器、MEC服务器和MEC发送机等装置，分别用于实现任务在边缘端的决策、处理和发送。MEC服务器是异构的，它由三簇物理机构成。这些物理机分别被命名为簇1、簇2和簇3，每簇物理机的数目不尽相同。处在同一簇中的物理机具有相同的任务处理速率且共享一个缓存。处在不同簇的物理机具有不同的任务处理速率：簇1中物理机任务处理速率相对较低，适合于低速类任务；簇2中物理机的任务处理速率居中，适合于中速类任务；簇3中物理机的任务处理速率相对较高，适合于高速类任务。

云端上部署着大量云服务器，这些服务器有着强大的计算能力，用于处理卸载到云端的全部任务。同时云端还拥有众多大功率发送机，用于发送被云服务器处理完毕的任务。

1.2 MEC任务卸载策略

结合1.1节所搭建的MEC系统架构，提出一种基于单用户和任务分类的MEC任务卸载策略。

在移动设备上生成的任务被划分为低速、中速或高速中的某一类。根据本地调度器上设定的此类任务卸载策略参数，该任务以一定概率送到本地处理器，以一定的概率送往本地输出端口。任务在本地端接受处理时，不会进行类别的区分。

送往本地输出端口的任务卸载到边缘端或者云端进行处理。卸载的任务在离开本地发送端口后，进入传输信道，经过附近基站的转发，最终抵达边缘端。任务在抵达边缘端后，根据MEC调度器上设置的此类任务卸载策略参数，该任务以一定的概率在MEC服务器上接受处理，以一定的概率卸载到云端进行处理。根据任务类别，在MEC调度器的控制下，MEC服务器上的任务被分配到相对应的物理机簇上接受处理。各类任务在物理机上处理结束后，由MEC发送机统一发送。发送后的任务经过传输信道再次回到本地端，并由本地接收端口进行接收。

如果任务被卸载到云端进行处理，那么任务在离开边缘端后会再次经过传输信道传输到云端。考虑到云服务器数目众多且计算能力强大，任务在云端处不再进行种类区分，全部由云服务器进行处理。各类任务在处理完毕后，由云发送机发送到传输信道返回本地端，由本地接收端口进行接收。

2 系统模型

2.1 本地计算模型

抽象任务在基于单用户和分类任务的MEC任务卸载策略下的行为，将不同类任务看作多类顾客，本地处理器、本地发送端口、本地接收端口、物理机、MEC发送机、云服务器和云发送机等看作服务台，将对任务的处理、发送和接收等过程看作对顾客的服务过程。根据任务在各处服务台上的服务特点，将基于单用户和任务分类的MEC任务卸载策略建模为一个具有单输入流与多类顾客的排队模型。

(1)

其中，θ为一个任务包含的平均数据量。

(2)

被卸载的任务首先需要经过本地发送端口的发送。假设任务在本地发送端口上的发送时间服从相同的负指数分布。那么任务在本地发送端口上的发送过程可以看作是一个M/M/1排队。

令rop表示本地发送端口单位时间内发送的数据量，则rop的表达式为

(3)

根据M/M/1排队的理论分析结果，可以得出任务在本地发送端口的平均逗留时间top如式

(4)

卸载处理的任务经过MEC发送机或云发送机返回本地端，并由本地接收端口进行接收。假设各个任务在本地接收端口的接收时间服从相同的负指数分布，那么任务在本地接收端口的接收过程可以看作是一个M/M/1排队。令rrp表示本地接收端口单位时间内接收的数据量。任务在本地接收端口的平均逗留时间trp为

(5)

2.2 边缘计算模型

(6)

其中，s1为本地端与边缘端之间的信道长度，v是任务在信道中的传输速率(m/s)。

MEC服务器上的三簇物理机各司其职，分别用来处理低速类、中速类和高速类等三类任务。假设任务在同一簇物理机上的处理时间服从相同的负指数分布，那么任务在MEC服务器上的处理过程可看作一个M/M/c排队。设簇i(i=1,2,3)中有ci台物理机，每台物理机的处理速率均为μi。根据M/M/c排队的理论分析结果，任务在簇i物理机上的平均逗留时间ti为

(7)

任务在MEC服务器上处理完毕后，将送往MEC发送机。假设任务在MEC发送机上的发送时间服从相同的负指数分布，那么任务在MEC发送机上的发送过程可以看作一个M/M/1排队。

令res表示单位时间内由MEC发送机发出的数据量。任务在MEC发送机上的平均逗留时间tes为

(8)

2.3 云端计算模型

(9)

其中，v为任务在传输信道的传输速度。

考虑到云服务器强大的计算能力，假设任务在到达云端后，可以立刻在云服务器上接受处理。假设任务在云服务器上的处理时间服从相同的负指数分布，任务在云服务器上的处理过程可以看作是一个M/M/∞排队。此时，任务在云服务器上的逗留时间即为任务在云服务器上的处理时间。

设任务在云服务器上的处理速率为μcd，即单位时间内云服务器处理的任务个数。任务在云服务器上的平均逗留时间tcd为

(10)

任务在云服务器上处理完毕后，由云发送机返回到本地端。考虑云发送机强大的发送能力，假设任务在被送往云发送机后，将立刻进行发送。假设任务在云发送机上的发送时间服从相同的负指数分布，任务在云发送机上的发送过程可以看作是一个M/M/∞排队。此时，任务在云发送机上的逗留时间即为任务在云发送机上的发送时间。

令rcs表示云发送机的发送能力(bit/s)，即单位时间内云发送机发送的数据量。任务在云发送机上的平均逗留时间tcs为

(11)

3 策略性能评估

为了评估MEC任务卸载策略的系统性能，求解各类任务的平均处理时延和各类任务对应的移动设备能耗水平。

在计算各类任务的平均处理时延时，需要同时考虑任务的本地处理、任务的上行和任务的下行三个过程。

(12)

(13)

(14)

移动设备的能耗包含本地处理器处理任务时的能耗、本地发送端口发送任务时的能耗和本地接收端口接收任务时的能耗等三部分。

在实际应用中，任务在本地处理器缓存中等待时的能耗要远小于任务在本地处理器中进行处理的能耗。设本地处理器的功率ηlp为

ηlp=γ1f∂+γ2，

(15)

其中，∂、γ1和γ2均是与本地处理器芯片有关的参数，可由文献[14]方法测量得出。

本地处理器每处理一个任务，移动设备的平均能耗ψlp为

(16)

设本地发送端口的功率为ηop，本地发送端口每发送一个任务，移动设备的平均能耗ψop为

(17)

设本地接收端口的功率为ηrp，本地接收端口每接收一个任务，移动设备的平均能耗ψrp为

(18)

(19)

4 系统实验

进行系统实验，分析任务种类、任务比重以及任务本地处理概率对系统性能的影响。系统实验在MATLAB R2011a环境下进行，文献[15]在保证系统稳定的条件下的设置实验参数如表1所示。

表1 实验参数设置Tab.1 Parameters setting in experiments

利用表1设定的实验参数，针对不同任务比重，给出三类任务的平均处理时延变化趋势，如图2所示。

在图2(a)中，低速类任务在三类任务比重下对应的最小平均处理时延分别为4.403 ms、4.522 ms和4.716 ms；图2(b)中，中速类任务在三类任务比重下对应的最小平均处理时延分别为 4.386 ms、4.508 ms和4.685 ms；图2(c)中，高速类任务在三类任务比重下对应的最小平均处理时延分别为4.368 ms、4.492 ms和4.662 ms。

(a) 低速类任务

从图2实验的数值结果可以看出，在相同的任务到达率下，某类任务比重的增大会引起该类任务最小平均处理时延的增大。此外，在相同的任务比重下，不同种类的任务之间的最小平均处理时延存在差异。任务响应程度越高，最小平均处理时延越小，这是由于MEC服务器对三类种类任务处理速率不同造成的。

此外，通过观察图2中曲线的最低点可以得出，对于同一类型的任务，随着该类任务比重的增大，任务对应的最佳本地处理概率将逐渐减小。相比MEC服务器和云服务器，本地处理器有着较低的任务处理速率。随着任务数目的增多，任务在本地处理器的平均逗留时间成为导致任务平均处理时延增长的主要影响因素，因此，该任务将更有可能以卸载的方式进行处理，最佳的本地处理概率会变小。

针对不同的本地处理器时钟频率，给出各类任务对应的移动设备能耗水平随该类任务本地处理概率的变化趋势，如图3所示。由式(19)可知，任务对应的移动设备能耗水平与任务类别无关。这意味着三类任务对应的移动设备能耗水平在该类任务本地处理概率下呈现相同的变化趋势，因此用一张图即可表示对三类任务的实验探究结果。

图3 第i类任务对应的移动设备能耗水平Fig.3 Energy consumption level of mobile device corresponding to the class i tasks

5 策略优化

折衷考虑任务的平均处理时延和移动设备的能耗水平，引入权重系数，建立系统的成本函数，研究基于单用户和任务分类的MEC任务卸载策略联合优化问题。

设任务平均处理时延和移动设备能耗水平所对应的权重系数分别为f1和f2，且存在关系式f1+f2=1。通过加权平均法，得到系统的成本函数F(x)为

(20)

至此，可以得到一个联合优化问题P如式

(21)

为了降低系统成本，应用KKT条件方法优化任务卸载策略。对于优化变量x，需要同时考虑系统稳态条件和任务分配比例自身范围等两种约束。令gk(x)≤0表示优化变量间存在的不等式约束，可以得出gk(x)为

(23)

其中，式gk(x)(k=1,2,…,7)由系统的稳态条件得出，式gk(x)(k=8,9,…,19)由分配比例自身的范围得出。

将优化问题P转换为KKT条件方法的解决形式

(24)

s.t.gk(x)≤0,k=1,2,…,19。

(25)

综合式(20)和式(23)，得到拉格朗日函数W(x)为

(26)

其中，δk(k=1,2,…,19)为拉格朗日乘子，并且满足δk≥0。

根据KKT条件，所要求解的最优变量组合满足

(27)

式中，k=1,2,…,19。

沿用表1中设置的实验参数，考虑不同的任务到达率及任务比重，应用上述KKT条件方法，给出任务卸载策略优化方案，并求解出此时的最小系统成本，如表2所示。

表2 任务卸载策略联合优化结果Tab.2 Jointly optimal results of the task of floading strategy

从表2中的优化结果可以发现，任务到达率λ越大，最小系统成本F(x*)也会越大。因为任务到达率越大，系统阻塞率越高，导致任务在系统中的平均处理时延加大。此外，由于本地处理器、本地发送端口和本地接收端口等装置的功率恒定，时延的增大无疑会导致移动设备的能耗水平提高。任务平均处理时延的增加和移动设备能耗水平的提升，都会使得系统成本增大。

此外，对比表2中数据还发现，在同一任务到达率λ下，随着三类任务比例(α1,α2,α3)的变化，最优任务卸载策略x*将进行适当调整，但是最小系统成本F(x*)却保持不变。在三类任务总到达率保持不变的前提下，一类任务到达率的增大意味着另一类任务到达率的减小。任务到达率的增大将带来更高系统成本，而任务到达率的降低则会带来更小的系统成本。通过调节任务卸载策略，均衡三类任务本地处理和卸载处理的比例，基于单用户和分类任务的MEC系统能够维持稳定，任务处理所产生的平均最小系统成本保持不变。

应用表1中的实验参数，变换任务卸载策略参数，得出不同任务卸载策略下的系统成本，结果如表3所示。

表3 不同任务卸载策略对比Tab.3 Comparison of different task offloading strategy

对比表3中数据发现，相比策略1(三类任务全都在本地端处理)和策略2 (三类任务全都卸载处理)，所提出的任务卸载优化策略能够有效地降低系统成本。

6 结论

针对整体智能家居等MEC应用场景，搭建了由本地端、边缘端和云端组成的系统框架，提出了一种基于单用户和任务分类的MEC任务卸载策略。考虑异构边缘网络，通过建立具有单输入流与多类顾客的排队模型，推导了任务的平均处理时延和移动设备能耗水平等性能指标。实验结果表明，通过设置合理的任务本地处理概率，可以使任务的平均处理时延达到最小。此外，实验结果还揭示出，任务对应的移动设备能耗与任务本地处理概率呈正相关。权衡不同性能指标，构建系统的成本函数，应用KKT条件方法，给出了任务卸载策略的优化方案，实现了系统成本的最小化。

后续的研究中，将考虑边缘端和云端的用户竞争，面向多用户MEC应用研究任务卸载问题。