MEC多服务器启发式联合任务卸载和资源分配策略

路 亚

(重庆电子工程职业学院人工智能与大数据学院 重庆 401331)

0 引 言

随着移动应用程序和物联网的快速增长，对云基础设施和无线接入网络(如超低延迟、用户体验连续性和高可靠性)的要求也越来越高[1]。为了将电信、IT和云计算结合起来，直接从网络边缘提供云服务，移动边缘计算概念应运而生[2]。与传统云计算系统不同，MEC服务器为网络运营商所有，并直接在蜂窝基站或本地无线接入点通过通用计算平台实施，这使得MEC可以在靠近最终用户的地方执行应用程序，从而大大减少端到端的延迟，减轻回程网络的负担[3-4]。

由于MEC的出现，资源受限的移动设备可以将计算任务卸载到MEC服务器上，从而使其支持各种新的服务和应用，如增强现实、物联网、自动驾驶和图像处理[5]。由于设备与MEC服务器之间在上行链路无线信道中的通信需要，任务卸载在延迟和能耗方面会产生额外的开销。此外，在一个拥有大量卸载用户的系统中，MEC服务器上有限的计算资源严重影响了任务执行延迟。因此，卸载决策和执行资源分配成为实现高效计算卸载的关键问题[6]。

文献[7]提出一种完全卸载优化算法，采用将边缘设备中的任务全部卸载到MEC服务器上的策略，减少了任务执行的时间和能耗。文献[8]提出一种部分卸载优化算法，采取将部分满足条件的计算任务卸载到云服务器，剩余任务在边缘设备执行的方式实现能耗和时间的优化。文献[9]虽然考虑了多用户系统中的联合任务卸载和资源优化问题，但是这种方法只能应用在具有单个MEC服务器的系统上。文献[10]在移动边缘计算环境中提出一种多重资源计算卸载能耗优化模型，在计算卸载时综合考虑边缘设备、边缘服务器与云数据中心的负载情况，利用粒子群任务调度算法，降低移动终端能耗。文献[11]提出建立一个设备(D2D)框架，其中网络边缘的大量设备利用网络辅助D2D协作进行计算和通信资源共享，但是只考虑了任务分配问题。

与上述方法不同，本文在多MEC服务器辅助网络中设计一个整体的解决方案，对联合任务卸载和资源分配进行优化，从而最大限度地提高用户的卸载收益。首先把每个用户的卸载效用建模为任务完成时间和设备能耗改进的加权和；然后将联合任务卸载和资源分配(Joint Task Offloading and Resource Allocation，JTORA)问题作为一个混合整数非线性规划(Mixed Integer Non-linear Program，MINLP)，采用Tammer分解方法将高复杂度的原始问题转化为等效的主问题和一组复杂度较低的子问题；最后利用本文提出的低复杂度启发式算法，以次优解的方式解决JTORA问题，实现共同优化任务卸载决策和用户上行链路传输功率的目标。

1 移动边缘计算

国际标准组织ETSI提出的移动边缘计算(MEC)是基于5G 演进架构的一项新技术，为减少网络延迟，确保高效的网络运营和服务交付，并提高用户体验，通过借助边缘计算中心在无线接入网(Radio Access Network,RAN)内提供IT服务环境、云计算和存储功能。

1.1 MEC基本架构

移动边缘计算的关键要素是集成在RAN元素上的移动边缘计算IT应用服务器。MEC的基本框架如图1所示，该框架从一个比较宏观的层次出发，对MEC架构下不同的功能实体进行了网络层、移动边缘主机层和移动边缘系统层的划分。其中：MEC主机层包含主机(ME host)和相应的主机层管理实体(ME host-level management entity)，ME主机又可以进一步划分为 ME平台(ME platform)、ME应用(ME application)和虚拟化基础设施(virtualization infrastructure)；网络层主要包含 3GPP 蜂窝网络、本地网络和外部网络等相关的外部实体，该层主要表示MEC工作系统与局域网、蜂窝移动网或者外部网络的接入情况；最上层是 ME系统层的管理实体，负责承载应用程序及MEC系统的全局掌控。

图1 MEC架构示意图

1.2 MEC部署方案

由于具备计算和存储功能的MEC服务器为边缘计算提供服务，因此MEC服务器在网络中的部署位置是至关重要的。4G网络中边缘服务器部署存在多种方案：小基站云(Small Cell Cloud，SCC)部署方案、移动微型云(Mobile Micro Cloud，MMC)部署方案、快速移动私人云(Fast Move Personal Cloud，FMPC)部署方案和漫游云(Follow Me Cloud，FMC)部署方案。各个部署方案的优缺点对比如表1所示。MEC服务器部署方案的选择是根据物理部署约束、可扩展性以及性能指标的综合考虑。图2给出了FMC部署方案示意图，该方案主要是通过在分布式的数据中心位置部署服务器来提供边缘服务。

表1 边缘服务器部署方案对比

图2 FMC部署方案示意图

5G网络在根本架构上不同于4G网络，所以为了让MEC更好地融合5G网络，需要根据需求重新设计MEC部署方案，如图3所示。MEC处在接入网与核心网融合的部分，通过NEF接入5G 网络。该方案根据平台应用相关信息，通过5G控制面的应用功能(AF)直接或者间接地将MEC用户面应用传递给策略控制功能模块(PCF)，控制会话管理功能模块(SMF)进而影响用户面功能模块(UPF)的选择。

图3 5G MEC融合架构示意图

2 多服务器MEC系统的JTORA建模及启发式整体优化方案

多服务器MEC系统是指在每个基站都配备一个MEC服务器，为资源受限的移动用户(如智能手机、平板电脑和可穿戴设备)提供计算卸载服务的平台。每个MEC服务器可以是物理服务器，或者是网络运营商提供的具有中等计算能力的虚拟机，通过相应的BS提供的无线通道与移动设备连接通信。每个移动用户都可以通过附近的BS将计算任务卸载到MEC服务器。

本文主要有两点创新。一是将联合任务卸载和资源分配问题表述为一个混合整数非线性规划问题，通过对任务卸载决策、用户上行链路传输功率和计算资源分配的共同优化来实现卸载效用的最大化；二是提出一种低复杂度启发式算法来解决任务卸载最优值问题，可以在多项式时间内达到次优解。

2.1 多服务器MEC建模

本文将移动系统中的一组用户和MEC服务器分别表示为u={1,2,…,U}和s={1,2,…,S}。多服务器MEC系统如图4所示。

图4 多服务器MEC系统

2.1.1本地计算任务

假设单个用户u∈U每次只有一个计算任务，即Tu，它是原子的、不可分的。每个Tu由两个参数du、cu组成，其中：du表示将程序执行(包括系统设置、程序代码和输入参数等)从本地设备传输到MEC服务器所需的请求数据量；cu表示完成任务的计算量。每个任务可以在用户设备上执行本地卸载，或者卸载到MEC服务器。如果将计算任务卸载到MEC服务器，移动用户能够节省执行任务的能量，但是将任务请求发送到上行链路需要消耗额外的时间和能量。

(1)

2.1.2任务上载

(2)

(3)

(4)

(5)

2.1.3MEC计算资源

每个BS上的MEC服务器能够同时向多个用户提供计算卸载服务。每个MEC服务器提供给关联用户共享的计算资源由计算速率fs进行量化。服务器从用户接收到卸载的任务后，代表用户执行该任务，完成后返回输出结果给用户。将计算资源分配策略定义为F={fu,s|u∈U,s∈S}，其中fu,s>0是BS分配给卸载任务Tu的计算资源量。因此，当∀u∉Us时，fu,s=0。此外，一个可行的计算资源分配策略必须满足计算资源约束，表示为：

(6)

给定计算资源分配{fu,s,s∈S}，任务Tu在MEC服务器上的执行时间为:

(7)

2.1.4用户卸载实用程序

(8)

(9)

(10)

2.2 联合任务卸载与资源分配启发式整体优化方案

2.2.1JTORA问题及分解

(11)

式中：λu是权重系数，可以根据用户类型和计算任务的关键性来设置。将联合任务卸载和资源分配问题转化成系统效用最大化问题，即：

(12)

式中：第一和第二约束条件表示每个任务可以在本地执行或者卸载到子带j上的至多一个服务器；第三约束条件表示每个BS在子带j上至多服务一个用户；第四约束条件表示用户的传输功率预算；最后两个约束条件表示每个MEC服务器必须为与其相关联的每个用户分配相应的计算资源，并且分配给所有相关用户的总计算资源不得超过服务器的计算能力。

式(12)中的JTORA问题属于混合整数非线性规划问题。考虑到问题中的变量与用户数量、MEC服务器数量和子带数量呈线性关系，因此，本文通过设计一个低复杂度、次优解决方案，实现联合任务卸载与资源分配的优化。

(13)

(14)

s.t. 00

式(13)中的问题等同于TO问题；式(14)中的问题等同于RA优化问题。

2.2.2JTORA启发式解决方案

联合任务卸载和资源分配的求解问题等效为分别求解任务卸载和资源分配的优化问题，首先解决式(14)中的RA问题，然后使用其解决方案来推导式(13)中TO问题的解决方案。

(15)

(16)

(17)

s.t. 00

由于功率分配pu和计算资源分配fu,s的目标和约束可以彼此分配，因此式(17)可以分解为两个独立的问题：上行链路功率分配(UPA)和计算资源分配(CRA)。

上行链路功率分配问题可以表示为：

(18)

s.t. 0

假设每个BS独立计算其上行链路功率分配，那么

(19)

进而得到了用户u上传到子带j上BS的上行链路信噪比的近似值：

(20)

通过式(20)可以将式(18)中目标函数和对应的用户发射功率约束条件实现分离，因此，式(18)中的目标函数可以近似为：

(21)

s.t. 0

计算资源分配问题可以表示为：

(22)

由于目标函数的Hessian矩阵是正定的，而且约束条件是凸的，因此，式(22)问题是一个凸优化问题，可以采用Karush-Kuhn-Tucker进行求解。

(23)

(24)

根据式(23)、式(24)，式(13)中的TO问题可以改写为：

(25)

考虑到TO问题的组合性质，在多项式时间内求解最优解是一个非常具有挑战性的问题。解决式(25)的一个简单方法是对所有可能的任务卸载决策使用穷举搜索法。然而，由于候选任务卸载决策的总数是2n，n=S×U×N，因此穷举搜索方法显然是不切实际的。

算法1删除和交换操作

3.forw∈S,i∈Ndo

5.end for

6.forv∈Udo

8.end for

算法2启发式任务卸载调度

6. 返回第4步

9. 返回第4步

10.end if

3 实 验

3.1 实验设置

为了评估提出的启发式联合任务卸载调度和资源分配策略(hJTORA)的性能，本文通过仿真实验进行测试。所有实验均在配置为CPU Intel Core i7-4700MQ-2.4 GHz@6 GB RAM的机器上执行，通过MATLAB R2017B进行仿真。考虑一个由多个六角形子区构成的蜂窝网络系统，每个小区的中心都配有一个BS，相邻基站相距1 km。假设用户和BS分别使用单个天线进行上行链路传输和接收。本文的测试中用户的最大发射功率为Pu=20 dBm，系统带宽设置为B=20 MHz，背景噪声方差假设为σ2=-100 dBm。上行链路信道增益是使用距离相关的路径损耗模型生成的，该模型的计算公式为：

L=140.7+36.7lgd[km]

(26)

式中：对数正常阴影衰落的标准偏差为8 dB。

为了验证提出算法的优越性，本文将与其他优秀算法如穷举搜索法、GOJRA(Greedy Offloading and Joint Resource Allocation)、IOJRA(Independent Offloading and Joint Resource Allocation)和DORA(Distributed Offloading and Resource Allocation)等进行对比。

3.2 实验结果分析

3.2.1不同算法平均系统效能对比

首先，将本文算法的结果与穷举法得到的最优解以及其他三种算法进行了比较。由于穷举法搜索所有可能的卸载调度决策，因此对于大量变量，它的运行时间非常长。因此，测试时选择在一个小的网络：设置用户数U=6，单元数S=7，每个单元有N=2个子带。分别设置cu=1 000、1 500和2 000兆周期时，随机生成500个阴影衰落，得到不同算法95%置信区间的平均系统效能结果如图5所示。可以看出，hJTORA算法与最优穷举算法的性能非常接近，但明显优于其他算法，充分体现算法2得到的hJTORA解的次优性。同时，还可以发现，所有方案的性能都随着任务工作量的增加而提高。在所有情况下，hJTORA的平均系统效能都在穷尽算法的0.6%以内，而与DORA、GOJRA和IOJRA方案相比，其平均增益分别为33%、43%和96%。

图5 不同算法的平均系统效能比较

3.2.2用户数量对平均系统效能的影响

图6给出了不同数量的用户在卸载任务时的平均系统效能。测试中每个单元的用户数从1到10不等，并在三个具有不同任务工作负载的场景中进行比较。而且子带数N等于每个单元的用户数，因此当系统中有更多的用户时，为每个用户分配的带宽会减少。可以看出，hJTORA算法性能表现最好，而且当任务的工作量增加时，方案的性能也会显著提高。当用户数量较少时，系统效能随着用户数量的增加而增加；但是，当用户数量超过某些阈值时，系统效能开始降低。这是由于过多用户为卸载任务而竞争无线和计算资源，使得MEC服务器上发送任务和执行任务的开销升高，导致卸载效能降低。

(a)cu=1 000兆周期 (b)cu=1 500兆周期

3.2.3任务配置文件对平均系统效能的影响

本文中的任务配置文件是指请求数据量和工作负载两个方面。根据请求数据量du和工作负载cu来评估系统效能。考虑两种MEC服务器的配置：(1)同构服务器—所有服务器的CPU速度是20 GHz；(2)异构服务器—服务器的CPU速度随机从{10,20,30}GHz中选择。四个算法在不同cu、du值时的平均系统效能如图7、图8所示。可以看出，所有方案的平均系统效能都随任务工作量的增加而增加，随任务请求的增加而减少。这表示，与那些具有大请求量和低工作负载的任务相比，具有小请求量和高工作负载的任务从卸载中获益更多。同构服务器设置中所有方案的性能与异类服务器设置中所有方案的性能之间的差异是微乎其微的。除此之外，在所有方案中，hJTORA方案的性能是最优的。

(a)同构服务器 (b)异构服务器

(a)同构服务器 (b)异构服务器

4 结 语

本文目标是在多MEC服务器辅助网络中设计一个整体的解决方案，对联合任务卸载和资源分配进行优化，从而最大限度地提高用户的卸载收益。首先，为每个用户的卸载效用建模，将JTORA问题转化为MINLP问题。然后，采用Tammer分解方法将高复杂度的原始问题转化为等效的主问题和一组复杂度较低的子问题。最后，利用本文提出的低复杂度启发式算法，以次优解的方式解决JTORA问题，实现共同优化任务卸载决策、用户上行链路传输功率的目标。仿真结果表明，本文提出的优化策略的平均系统效能明显优于其他方案，提出的启发式算法能够很好地实现最优解，显著提高系统的平均卸载效率。