英语原文共 8 页，剩余内容已隐藏，支付完成后下载完整资料

移动边缘计算系统的延迟优化计算任务调度

Juan Liu，Yuyiensp;Mao，Zhang Zhang，Khaled B. Letaief

摘要：移动边缘计算（MEC）作为一种新的技术应运而生，提高了移动设备的计算体验的质量。然而，MEC系统的计算任务调度策略的设计不可避免地遇到具有挑战性的双时间尺度随机优化问题。具体而言，在较大的时间范围内，在云计算中应确定是任务在移动设备本地执行还是将任务卸载到MEC服务器以进行计算，而在较小的时间范围内，任务输入数据的传输策略应适应于频道边信息。在本文中，我们采用马尔可夫决策过程方法来处理这个问题，其中计算任务是根据任务缓冲区的排队状态进行调度，即本地处理单元的状态，以及传输单元的状态。通过分析每个任务在移动设备上的平均延迟和平均功耗，我们制定了功率约束的延迟最小化问题，并提出了一种有效的一维搜索算法来寻找最优的任务调度策略。通过仿真结果可以证明所提出的最优随机任务调度策略与基线策略相比实现更短的平均执行延迟的能力。

关键词：边缘计算、任务调度、计算卸载、执行延迟、QOS、马尔科夫策略

一、引言

随着智能计算机的普及，计算机上的各种密集型的应用，如：在线游戏，视频会议、三维建模等,这些应用程序变得越来越普遍。然而，移动设备通常拥有的资源有限，移动设备电力不足，计算能力低等问题，这些会导致移动设备计算体验的结果不尽如人意。移动边缘计算的出现解决了这些问题，通过将任务迁移到物理配置较高的边缘服务器上执行，这使得计算体验，减少电能消耗，任务执行的延迟等都得到了有效的提高[1][2]。

计算卸载策略是边缘计算性能的关键，他决定了任务执行能达到的效果和可实现的计算性能，具体来说，由于云计算需要通过无线链路来数据传输，选择最优任务迁移策略时应考虑到数据通过无线传输的传输时间的波动，在[4]中，提出了一种适应无线信道条件的随机控制算法来确定了卸载软件的组件，在[5]中提出了一种多用户MEC系统的卸载方法[5],将系统卸载方法扩展到[6]中多单元设置,除此之外，分别在[7]和[8]中采用李亚普诺夫优化技术，研究了具有异构计算任务类型和多核移动设备的云计算系统的能量延迟权衡问题。此外，在[9]中还提出了可再生能源驱动的移动设备MEC系统的动态计算卸载策略。

对于大多数移动应用程序，执行时间在范围为几十毫秒，这比通道块的持续时间长得多，通道块的典型值为几毫秒。换句话说，执行过程可能会经历多个通道块，这使得计算卸载策略设计成为一个极具挑战性的双时间尺度随机优化问题。特别是,在较大的时间尺度下，需要决定是否将任务卸载给MEC服务器，而在较小的时间尺度下，应用程序输入数据的传输策略应该适应瞬时无线信道条件。为了解决这一问题，我们在[10]中进行了两阶段计算卸载策略设计的初步研究。忽略执行单个计算任务的能量消耗和多个任务引起的排队延迟。此外，利用MEC，应充分挖掘并行执行多个任务的潜力，有效利用本地和云计算资源，最大限度地提高计算体验的质量。

在本文中，我们将研究一个允许在移动设备和MEC服务器上并行执行计算任务的MEC系统。在移动设备上运行的计算任务的执行和计算卸载过程可能跨越多个通道块，生成但尚未处理的任务正在任务缓冲区中等待。首先利用马尔可夫链理论分析了给定计算任务调度策略下各任务的平均时延和移动设备的平均功耗。然后，我们提出了功率受限的延迟最小化问题。提出了一种有效的一维搜索算法来寻找最优的随机计算卸载策略。仿真结果表明，提出的随机计算任务调度方法与基线方案相比是可行的，策略实现了执行延迟的显著减少。

本文的其余部分组织如下。第二部分介绍了系统模型，平均执行延迟以及移动设备在给定计算卸载策略下的功耗队列状态数据队列处理单位分析了随机计算任务调度策略，在第三节和第四节中，提出了一个功率受限的延迟小-多目标优化问题，并给出了相应的优化任务得到调度策略。仿真结果在第五节，结论见第六节。

图1 带有移动设备和MEC服务器的MEC系统

二、系统模型

我们考虑如图1所示的移动边缘计算(mobile-edge computing, MEC)系统，其中移动设备在MEC服务器的帮助下运行计算密集型和延迟敏感的应用程序。这个MEC服务器可以是一个安装在无线接入点的小型数据中心。通过构建与移动设备相关联的虚拟机，MEC服务器可以代表移动设备[10]执行计算任务。移动设备上的CPU和传输单元(TU)具有特殊的意义，它们可以在本地和外部执行计算任务将计算任务的输入数据分别传输到MEC服务器进行云计算。此外，由于电池尺寸有限，为了延长设备寿命，我们假设移动设备的平均功耗受到的限制。

1. 任务队列模型

我们假设时间被划分为等长时间槽，时间槽长度记为∆。在每个时间段的开始,概率alpha;,生成一个新任务。计算任务可以由本地CPU在移动设备上执行，也可以卸载到移动设备上用于云计算的MEC服务器。到达但尚未执行的任务将在一个容量足够大的 Q 1任务缓冲区中排队。表示v L [t]，v C [t]isin;{0,1}为第t个时隙的计算任务调度决策指标，即，如果决定将任务发送到第t个时隙中的本地CPU (MEC服务器)，v L [t] = 1v C [t] = 1);否则，v L [t] = 0 (v C [t] = 0)。,V = {(V L [t] C [t]) | (0, 1), (1,0)、(1, 1), (0,0)}。在每个时隙中，由移动设备做出决策，任务缓冲区的动态可以表示为:q [t 1] = min{(q [t] minus; v L [t] minus; v C [t]) a[t],Q},t = 1,··· ,(1),式中(x) ， max{x,0}， q [t]为计算次数第t个时间槽开始时缓冲区中的任务，和a[t]isin;{0,1}是任务到达指示器，即，如果任务到达在第t个时隙处，有[t] = 1;否则,我们有一个[t] = 0。

1. 计算模型

1)局部计算模型:假设在执行任务时，移动设备上的CPU运行频率为f loc (Hz)，功耗为P loc (W);否则，本地CPU处于空闲状态，不消耗任何电能。成功执行任务所需的CPU周期数记为C，这取决于移动应用程序[11]的类型。换句话说,N =lceil;Cf loc∆rceil;时段需要完成的任务。我们使用c L [t]isin;{0 1, Nminus;1}表示本地CPU的处理状态,其中c L [t] = 0意味着本地CPU空闲,而c L [t] = N (1le;Nle;Nminus;1)表明,在处理一个任务在本地CPU、和Nminus;N多的时段要求完成任务。例如，cl [t] = N - 1表示任务将在时间间隔结束时完成，从(t 1)个时隙开始的新任务将使用本地CPU。

2)云计算模型:为了将计算任务卸载到MEC服务器上，任务的所有输入数据都要通过无线信道成功地传递到MEC服务器上。在不失一般性的前提下，我们假设每个任务的输入数据由M个大小相等的数据包组成，每个数据包包含R位。为了简单起见，采用开关电源控制。我们假设通道一侧可在移动设备的信息,因此一个包可以成功传输到MEC服务器如果实现吞吐量在t时间槽,r(gamma; [t],P tx ),没有小于数据包大小,即。 r(gamma; [t],P tx ) = B log 2（1 gamma;[t]P tx/)ge;R,在t时间槽时gamma;[t]通道功率增益,P tx表示传输能量,B是系统带宽和是接收机的噪声功率谱密度;否则，发射机将是无声的，不消耗电力。

我们使用 c T [t] isin; {0,1,··· ,M}表示TU状态，当e c T [t] = 0时意味着你可以卸载任务MEC服务器,和c T [T] = m (1le;le;m)意味着第m个数据包传输的一个任务计划时间T。当所有输入位成功收到,MEC服务器开始执行这个任务。假设MEC服务器配备了多核CPU，因此可以同时执行多个任务。类似于本地计算,N云=lceil;Cf ser∆rceil;时段在MEC完成任务所需的服务器,f ser表示在MEC服务器cpu周期的频率。此外，我们将反馈计算结果的延迟表示为t r，它被视为一个常数。

1. 随机计算任务调度和马尔可夫链规划

在考虑系统中,系统状态tau;[t]可以三个一组,即。,tau;[t] = (q [t], c t [t], c L [t])。因此，状态空间S可以表示为S ={0,1，···，Q}times;{0,1，···，M}times;{0,1，···，N - 1}，其中“times;”表示笛卡尔积。在下面，我们将介绍随机计算任务调度策略，利用马尔可夫链理论分析移动设备上各任务的平均时延和平均功耗。

1. 随机任务调度

为了最小化每个任务的平均延迟，满足平均功率约束，移动设备应在每个时隙做出计算任务调度决策，即，确定是调度用于本地计算的任务，还是将其卸载到MEC服务器。描述计算任务调度策略,我们引入一组概率参数，isin;[0,1]，,forall;tau;isin;S,k = 1,2,3,4,这是从系统状态到概率空间的映射。上标k在表示四种可能的决策中的第二部分。其中k =1,2,3,4分别为计算任务调度决策(0,1)，(1,0)，(1,1)，(0,1)，(0,0)。

很简单，每个计算任务只能在本地CPU (TU)空闲时调度到本地计算(云计算)。当任务缓冲区为空时，即，q[t] = 0，没有任务需要调度，即， = 0对于k =1,2,3和 = 1。在下面，我们考虑假设移动设备上CPU和TU的可用性不同，q [t] gt; 0的情况。

情形I: cl [t] = ct [t] = 0。在这种情况下，本地CPU和发射器都是空闲的。因此，最多可以开始处理两个计算任务，即，一个用于本地计算，另一个用于计算卸载。考虑到系统状态tau;[t] = (q [t], c t [t], c L [t]) =(0, 0)(ge;2),计算任务调度策略可以表示为：

当缓冲队列中只有一个任务时，即， i =1，决策(1,1)不可行，因此计算任务调度策略可以表示为：

情形2:cL [t] = 0, c t [t] gt; 0。当发射机被占用时，本地CPU处于空闲状态。因此，移动设备可以决定是开始本地计算一个任务，还是保持空闲。因此,forall;tau;=(我,m, n)(ge;1),计算任务调度策略可以表示为：

情形3:当cL [t] gt; 0和ct [t] = 0。发射机是空闲的，移动设备决定是否通过无线链路向MEC服务器发送一个计算任务。因此，任务调度策略可以表示为：

情形4：当cL[t] gt; 0及cT[t] gt; 0。本地CPU和TU占领,并且Pr{(v C(t), L[t]) = (0, 0)} = = 1。值得注意的是,MEC系统的性能取决于采用计算卸载政策,可表现为参数的集合和最优计算卸载政策，这将在第四部分介绍。

1. 延迟与功率分析

在本节中，我们将通过将MEC系统建模为一个马尔可夫链来分析每个任务的平均延迟和移动设备的平均功耗，设置表示一步状态转换，从状态tau;转换到tau;′状态，可以检查在一个给定的计算任务调度策略。因此,稳态分布可以通过求解以下线性方程集合[12]：

平均延迟:由于每个计算任务到达后经历一个等待阶段和一个处理阶段(本地计算或云计算)，根据Little s定理[12]，平均排队延迟可以表示为：

alpha;表示任务的到达率和，回想一下,当地每个任务的执行时间是N时段,和云计算的处理时间，包括传输数据所花费的时间,在MEC服务器执行需要花的时间,以及反馈计算结果的时间，即时间可以表示为：

每个计算任务的平均传输时间在哪里是由一下公式决定的:

在（9）中表示信道在不停机的概率。因此，每个任务的平均处理时间可以表示为:

eta;表示位置的比例计算任务执行本地移动设备从长远来看,可以按照下列公式计算:

其中状态集(k = 1,2,3)定义为={(i,m,0)|i ge; 1,m isin; {0,··· ,M}}, = {(i,0,n)|i ge;1,n isin; {0,··· ,N minus; 1}} 和 = {(i,0,0)|i ge; 2},因此，每个计算任务的平均延迟为排队延迟与处理延迟之和，可表示为：

平均功耗:

用和分别表示任务在本地计算和成功将任务成功传输到远端服务器上运行所需要消耗的功率和，因此，在移动设备上消耗的功率可以通过一下计算公式计算：

功率系数和中的每个的状态可以用公式（14）和（15）来计算：

功率系数和的推导过程可以在附件B中查询，因此，平均功率计算中参数可以表示为，我们有，平均功率系可以表示为和

1. 最优计算卸载调度

在本节中，我们将制定一个优化问题，以最小化受移动设备平均功率约

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[19861]，资料为PDF文档或Word文档，PDF文档可免费转换为Word