动态服务请求调度用于移动边缘计算系统

摘要

如今，在终端设备上运行的移动服务（应用程序）正在成为越来越多的计算密集。卸载从终端设备到云计算服务请求可以是一个很好的解决方案，但它将使高负担在网络上。边缘计算是一种新兴的技术来解决这个问题，这在网络的边缘放置服务器。移动边缘计算系统卸载服务请求的动态调度是一个关键问题。它面临着由于动态性和服务请求模式不确定性的挑战。在这篇文章中，我们提出了一个动态服务请求调度（DSRS）算法，这使得请求调度决策，优化调度成本的同时提供性能保证。该DSRS算法可以在网上和分布式的方式来实现。我们目前的数学分析这表明DSRS算法可实现调度成本和性能之间权衡随心所欲。实验还进行了以显示DSRS算法的有效性。

1.介绍

随着资讯科技的迅速发展及终端设备的不断推广[1]，在终端设备上运行的移动服务（应用程序）正变得越来越复杂和计算密集型[2,3.]。然而，终端设备的计算容量和电池寿命通常是有限的，并且这些装置没有能力在本地处理设备上的所有这些服务请求。为了解决这个问题，一些研究提出卸载从终端装置向云计算，其具有更多的计算资源，以及较大的容量[服务请求4- - - - - -8]。然而，云计算通常位于远程即远离终端设备。此外，对终端设备上运行的移动服务的日益普及，调度所有的卸载服务请求到云计算可以把一个显著负担网络[9,10]。为了迎接这一挑战，最近的研究已经提出把边缘服务器与在靠近终端设备的网络边缘的计算能力。移动边缘计算（MEC）是基于这一想法的一种新兴技术[11- - - - - -14，并引起学术界和产业界的广泛关注[15- - - - - -18]。

MEC研究的关键问题之一是如何调度服务请求[2,19,20]:当大量服务请求被卸载时，如何在多个MEC系统之间调度服务请求，以降低调度成本，同时提供性能保证。在调度成本和性能之间存在权衡，这是很直观的。另外，由于多种原因，多个MEC系统之间的服务请求调度问题具有挑战性。首先，终端设备在移动，服务环境随时间变化[21,22，如何根据请求模式的不确定性和环境的变化做出动态请求调度决策是一个很大的挑战[23]。其次，越来越多的推广终端设备和移动服务，包括终端设备和移动服务的数量的大幅上涨，使得服务请求调度问题变得更复杂。

现有的一些研究已经在MEC系统研究的服务请求调度问题。参考文献[24]建模在MEC作为一个服务器 队列。参考文献[2假设已卸载的服务请求根据泊松进程到达MEC系统。这些工作假设请求到达遵循一定的分发。但现实中，请求到达过程是高度动态的，很难获得或准确预测请求到达的统计信息[25,26]。此外，随着终端设备和移动服务的数量不断增加，传统的集中优化技术，如组合优化和动态编程可以从高复杂度受害，导致很长的执行时间。

本文介绍了一种动态在线服务请求调度机制，该机制不需要请求到达统计信息的先验信息。具体地说，多个MEC系统之间的请求调度问题被表述为一个优化问题，其目标是在提供性能保证的同时最小化请求调度成本。基于李雅普诺夫优化技术，提出了一种动态服务请求调度算法。DSRS使用一个参数控制调度成本和队列长度之间的权衡。通过数学分析证明了DSRS是可行的 相对于所述平均调度成本 - 最优，同时仍通过界定平均队列长度 。实验表明，DSRS能够根据环境的变化做出动态控制决策，并在调度代价和队列长度之间实现平衡。

本文的其余部分组织如下。节2在此基础上，提出了多个MEC系统之间动态请求调度的系统模型，并给出了优化问题。节3.基于李雅普诺夫优化技术，提出了一种在线和动态服务请求调度算法。调度算法的理论分析将在第呈现4。实验以评估在第调度算法的效率和有效性5。我们的结论在这篇文章中科6。

2.系统模型

2.1。概观

考虑移动边缘计算（MEC）系统。每个MEC系统具有边缘服务器虚拟化以虚拟机处理的卸载请求来自终端设备的服务种类[25,27]。更具体地说，在MEC系统中的每个边缘服务器上个虚拟机用于将卸载的请求-第一类服务。让为应用程序和的索引的集合是MEC系统中边缘服务器的索引集合。在不丧失通用性的情况下，不同MEC系统中的边缘服务器应该是异构的。我们考虑了一个时间开槽模型，其时间开槽长度表示为 。本节中的主要符号列于表1。

2.2。问题描述

2.2.1。服务请求调度

在每个时间槽中 的多个服务请求类型的服务被卸载。让为服务请求的数量在时间段内卸载到MEC系统 。在我们的文章中，我们需要统计的先验知识 ,这在现实生活中是很难获得或精确预测的。代表服务请求的数量预定要在边缘服务器个MEC系统在时隙 。 是请求调度控制变量。应该满足

在我们的文章，请求调度方法会利用不同的MEC系统的多样性，以减少调度成本的同时提供性能保证提供的服务。

2.2.2。计划成本

让为调度服务请求的单位成本到th MEC系统。不同的服务之间可以不同吗和不同的MEC系统 。它也可以在时间上会发生变化的其他因素，例如交通，无线衰落，可用资源等服务的请求调度成本在时间槽可以计算为 。所有服务的总调度成本可以表示为

相反，研究瞬时调度成本，我们着眼于长期平均成本。在时隙上的时间平均调度成本 可以表示为 是本文请求调度问题的最小化目标。

2.2.3。性能

排队时延是最重要的性能指标之一。根据小定律，排队时延成比例在队列中等待的请求数。因此，我们寻求减少队列长度并保持较低的拥堵状态。让代表服务的队列长度在里面个MEC系统在时隙 。 表示服务请求的数量可以由th MEC系统。因此，队列长度的发展,

为了减少排队延迟和保持系统的稳定性，我们力求绑定的平均队列长度。让我们跨越时间平均队列长度 槽为代表 。本文中的服务请求调度方法界定平均队列长度

2.2.4。统一架构

要结合调度成本和性能，在这篇文章中请求调度问题转化为 受限制(1),(5)。

解决问题 （6离线需要未来的信息(如请求到达信息、调度成本信息)，这些信息在实践中通常很难获得或精确预测。为此，我们提出了一种在线动态服务请求调度算法来解决这一问题，具体算法将在章节中展示3.。

3.动态请求调度算法设计

在本节中，基于李雅普诺夫优化框架[28]，我们分解原始优化问题转化成一系列独立的子问题。然后，我们设计了一个动态服务请求调度算法解决的方式分配这些子问题。

3.1。使用李亚普诺夫技术进行问题转换

基于Lyanuov优化技术，我们定义 作为MEC系统的队列长度矩阵。然后，我们表示作为Lyanuov功能如下，它是在系统中的队列拥塞状态的标量量度，

小值的表示所有MECs的队列长度较小，根据式，表示MEC系统处于低拥塞状态小定律。为了减少队列长度并保持系统稳定性，我们寻求将Lyanuov函数保持在一个小的值。然后，我们定义条件李雅普诺夫漂移 ,

通过减少的值 ,我们可以对较小的值推Lyanuov功能。为了整合在MEC系统调度成本和队列长度，我们定义漂流+成本根据李亚普诺夫优化框架，其表示为

参数可以被认为是调度成本和队列长度之间的折衷参数，其可以由服务提供者或用户可以根据他们的实际应用中的要求来确定。接下来定理1我们表明，漂流+成本是上界，如果服务到达速率可以被上界。

定理1(边界漂移加代价)。在每个时间槽中 ,在任何算法下，对于所有可能的值和的任何参数值 ,如果有退出峰值该上限的请求的数量在每个时隙到达时，漂移加成本可以通过上界 哪里 是一个常数。

证明。通过平方的两侧（4)然后应用这个不等式 ,我们有 然后,我们定义作为服务请求的实际数量服务的个MEC系统在时隙 , 我们可以得到它 并重写（11)如下: 因为 ,我们有 以上的条件期望在双方（14)和总结 和 ，它可以得到 因为它认为 和 ,我们有 此外，我们定义的上界在所有的时间段。我们可以得到它 通过添加两边和让取值 ，它可以得到 用(2)转至(的右手边(R.H.S.)18），我们可以得到（10)。

3.2。动态请求调度算法

继李雅普诺夫优化技术的设计原理，我们设计一个高效的动态服务请求调度（DSRS）算法，以尽量减少上界漂流+成本在每个时间槽中 。通过分解上限问题的最小化到一系列独立的子问题，我们DSRS算法优化分布式的方式平均调度同时成本。此外，它会被证明DSRS算法可以实现即任意接近最佳值，同时保持MEC系统的稳定性的长期时间平均调度成本。

在每个时间槽中 ,基于当前队列长度矩阵MEC的系统中，DSRS算法使得请求调度决策以最小化上限R.H.S.的的（10)。自和可以看作是在优化问题不断，我们可以重写最小化的上限为 受

作为请求调度决定不同的服务之间是独立的，上述集中最小化问题(19）可以被分解成以下子问题（21)每项服务 即 受

问题（21)可以看作是一个广义的最小权值问题，其中调度到MEC系统的请求数量由的值来加权 。因此，对于每个服务 时，最优解是调度所有的请求到MEC系统的最小值 ;也就是说, 哪里 对所有 。

备注。MEC系统在调度成本和队列长度之间存在权衡。将所有的服务请求以较低的成本调度到MEC系统中，可以降低总体调度成本;然而，MEC系统的队列长度可能非常大。DSRS算法将调度代价和队列长度结合起来 可以看作是对每个MEC系统的惩罚因子。回想起那个表示调度成本与队列长度之间的权衡。通过DSRS算法得到的最优调度策略的直觉是最小化MEC系统在每个时隙的罚函数。这样，DSRS算法可以降低调度成本和队列长度。另外，通过改变的值 ,DSRS算法可以在调度代价和队列长度之间实现任意的折衷。

调度决策后是确定的，队列长度根据更新（4)。算法中给出了详细的算法1。

4.算法分析

在本节中，我们对我们的DSRS算法的时间平均队列长度和调度代价的边界进行了数学分析。实验证明，该算法在保持MEC系统稳定性的同时，可以使调度代价任意接近最优值。让表示长期时间平均队列长度，

我们在引理中呈现2如果到来是独立同分布的（独立同分布）随着时间的推移时隙，存在一个随机化策略它可以实现成本的最低在定义（3.），其中控制决策遵循一定的固定的概率分布独立于队列长度矩阵的 。

引理2。对于任何服务请求到达率 ,在那里是该系统的容量区域，如果到达是独立同分布随着时间的推移插槽，存在一个随机政策其确定控制决策在每个时间槽中并达到以下： 哪里表示到达率下的最小时间平均成本 。

证明。引理2可以通过右端是Carathéodory的定理被证明[28]，我们在这里省略了详细的证明为了简单和简洁。

因为假设存在上界服务请求到达率也存在上限和下界的目标 。然后，给出了基于引理的DSRS算法的队列长度边界和调度代价2。

定理3。假设存在满足 ，之后，在我们的DSRS算法，可对参数的任何值 ,的时间平均队列长度限定在（24）有界作为 此外，时间平均的系统调度成本可以为(27)，说明我们的DSRS算法可以通过增加参数来逼近最优值 。这里，这个常数在定理中有定义吗1。

证明。因为它认为 ，我们可以得到存在随机化策略满足(28)和(29)根据引理2。 由于我们DSRS算法可以实现的R.H.S的最小值（10)在所有可行的政策中(包括政策)），它能够获得 用(28)和(29）进入R.H.S.的（三十)，两边都有期望，然后使用迭代的期望，我们就可以产生结果 移动到R.H.S.的（31），它能够获得 一般情况下，我们假设队列长度为空 。通过双方总结（32）在 并应用事实 ，则可得 除两侧（33）通过并采取了LIM作为 让 （26)。
通过双方总结（31）在 并应用事实 中，可以得到 除两侧（34）通过 ,我们有 取(的lim35), ，应用勒贝格控制收敛定理，并让 让 （27)。

备注。定理3.说明我国DSRS算法可以实现 的时间平均调度成本和队列长度之间的折衷。根据 （27），由我们的DSRS得到的时间平均调度成本之间的间隙算法和最优值是内 。通过设置的值足够大时，DSRS算法可以接近最优调度成本。然而，大将导致MEC系统的大量队列积压。然而，我们的DSRS算法得到的队列长度也是有界的(26)。和约束(5）可以通过出租得到满足取值 。

然后，我们分析了DSRS算法的时间复杂度。根据算法1，对于两个内部循环(第5-10行和第11-17行)，DSRS算法遍历每个边缘服务器一次。因此，每个循环在操作,为边缘服务器的数量。对于外部循环(第1-18行)，由于不同服务应用程序的请求调度是独立的，因此它终止于操作。因此，DSRS算法的时间复杂度为 。

5.评价

在本节中，我们进行实验来评价我们的算法DSRS。首先，我们来分析参数的影响。然后，我们目前比较实验，这表明我们的DSRS算法的有效性。

在实验中，我们考虑了4个MEC系统，每个系统都有一个边缘服务器为卸载请求提供服务。异构服务有两种类型。为每个服务 时，根据与到达率泊松分布产生的请求到达过程(29]。请注意，实际上DSRS算法不需要请求到达的统计信息的知识。MEC的系统的计算容量被设置为 哪里 。为了不失一般性，我们假设MEC系统是异构的，具有不同的计算能力。并设定不同MEC系统的单元调度成本与其计算能力成正相关。

5.1。参数分析

5.1.1。权衡参数的影响。

数据1和2表示不同值的MEC系统的时间平均调度成本和队列长度 。在图1，可以看出，调度成本随着的值而降低根据(27在定理3.。这是因为当调度成本增加时，DSRS算法会以较低的单位成本向MEC系统调度更多的服务请求，从而降低总体调度成本。然而,图2表明，队列长度也随着的增加而增加 ,这与一致（26在定理3.。但是，队列长度会逐渐稳定下来，而会有更多的增加 。在一起的数据1和2中，我们可以看到，DSRS算法可以使调度成本和队列长度之间的折衷通过调整值 。

5.1.2。服务请求到达率的影响。

我们分析的服务请求到达率的调度成本和队列长度的影响。在实验中，为每个应用程序 我们扩大了服务请求到达率向上或向下 。我们考虑三种不同的情况，其中= 1，和 ,分别。数据3.和4表明，无论是调度成本和队列长度的增加作为请求到达率增大。然而，队列长度可以与服务请求到达率增加迅速稳定下来。这表明我们的算法DSRS可以根据不同的业务请求抵达地动态调整请求调度决策和维持MEC系统的稳定性。

5.1.3。单位调度成本的影响

为了分析单元调度成本对MEC系统的影响，我们将单元调度成本的大小分别调整为 。我们考虑三种不同的情况，其中= 1，和 ,分别。我们可以从图中看到的5总体调度成本随着单元调度成本的增加而增加，因为每个请求的调度成本增加了。在图6中，我们可以看到，MEC系统的队列的长度也与单元调度成本的增加而增加。其原因是，我们的DSRS算法试图通过调度更多的请求到MEC较小的单位成本调度实现较低成本的调度。然而，这将导致某些MEC系统较大的队列积压。

5.2。比较试验

我们进行对比实验，并比较了DSRS算法和随机算法来评估DSRS算法的有效性。该随机算法调度所有的服务请求到每个MEC系统随机。调度成本和两种算法的队列长度示于图7和8,分别。

我们可以从图中看到的7我们的算法DSRS的调度成本比随机算法，它示出了我们的DSRS的有效性降低成本算法的小。在图8，我们可以观察到随机化算法的队列长度在开始的时候略小于我们的DSRS算法。但随着时间的推移，随机化算法的队列长度会随着时间不断增加。我们的DSRS算法的队列长度稳定得很快，并保持在一个小的水平。这是因为我们的DSRS算法能够根据当前队列积压动态调整调度决策，在MEC系统中保持低拥塞状态。在一起的数据7和8，我们可以看到我们的DSRS算法在优化调度成本和队列长度方面的有效性。

六，结论

本文研究了MEC系统的动态请求调度问题。我们将其表述为一个优化问题，其目标是在提供性能保证的同时优化调度成本。我们提出了求解优化问题的DSRS算法，该算法将优化问题转化为一系列子问题，并以分布式的方式有效地求解每一个子问题。数学分析表明，DSRS算法可以在限定队列长度的情况下达到最优调度代价。通过参数分析实验和比较实验验证了DSRS算法的有效性。

数据可用性

用于支持本文研究的大部分模拟实验数据都包含在本文中。有关数据的更多信息可从通讯作者处获得。

利益冲突

作者宣称，他们没有利益冲突。

致谢

这项工作得到了国家自然科学基金(no. 8)的资助。61370065也没有。61502040)，北京信息科技大学重点科研培育项目(编号:61502040)。北京市优秀教师晋升计划(编号:5211823411)PXM2017 014224 000028)，北京信息科技大学教师辅助支持项目(编号:014224 000028)。5111823401)。

参考

1. 问：你们和W.庄，“分布式和启用互联网的，移动物联网网络的自适应介质访问控制”物联网杂志IEEE互联网第4卷第2期2，第446-460页，2017。查看在：出版商网站|谷歌学术搜索
2. M.佳，曹J.和W梁，“最佳朵云布局和用户在无线城域网朵云分配，”IEEE云计算汇刊卷。5，没有。4，第755-737，2017。查看在：谷歌学术搜索
3. “一种移动计算的层次化边缘云架构”，北京第35届年度IEEE计算机通信国际会议论文集，IEEE INFOCOM 2016，第1-9页，2016年4月查看在：出版商网站|谷歌学术搜索
4. B.-G。“克隆云:移动设备与云计算之间的弹性执行”，台北对计算机系统的第六届ACM EuroSys会议论文集（EuroSys '11），第301-314，ACM，纽约，NY，USA，2011年4月。查看在：出版商网站|谷歌学术搜索
5. S.科斯塔，A. Aucinas，P.辉，R.莫迪埃和X章，“Thinkair：在云中的移动代码卸载动态资源分配和并行执行，”在在IEEE INFOCOM论文集，第945-953，2012年3月。查看在：出版商网站|谷歌学术搜索
6. M. S.戈登，D. A. Jamshidi，S.马尔克，Z. M.毛，和X.陈，“彗星：代码卸载通过透明地迁移运行”，在第十届USENIX操作系统设计和实现会议的会刊，第93-106页，伯克利，加州，美国，2012。查看在：谷歌学术搜索
7. J.郭某，Y.金，李笃，和S.冲，“DREAM：动态资源和任务分配的能量最小化在移动云系统”IEEE通讯选定领域杂志第33卷，no。12, 2510-2523页，2015。查看在：出版商网站|谷歌学术搜索
8. S. Deng, L. Huang, J. Taheri, A. Y. Zomaya，“移动云计算中服务工作流的计算卸载”，IEEE交易在并行与分布式系统卷。26，没有。12，第3317-3329，2015。查看在：出版商网站|谷歌学术搜索
9. 吕永祥，倪，田，等，“基于部分信息的物联网移动边缘计算优化方案”，IEEE通讯选定领域杂志卷。35，没有。11，第2606至2615年，2017年。查看在：出版商网站|谷歌学术搜索
10. J.刘，王S.，A.周，杨楼，和R. Buyya，“在带宽受限数据中心可用性感知虚拟群集配置，”在IEEE服务计算学报，第1-1页，2017年。查看在：谷歌学术搜索
11. W.石，曹杂志，问：张，李Y.，和L.许，“边缘计算：愿景与挑战”物联网杂志IEEE互联网卷。3，没有。5，第637-646，2016。查看在：出版商网站|谷歌学术搜索
12. 余，“移动边缘计算的联合副载波与CPU时间分配”，台北在IEEE全球通信会议论文集（GLOBECOM），第1-6页，2016年12月。查看在：谷歌学术搜索
13. 毛元华，张建华，宋s.h.，“多用户移动边缘计算系统的随机联合无线电与计算资源管理”，IEEE交易在无线通信第16卷，no。第5994-6009页，2017。查看在：出版商网站|谷歌学术搜索
14. S.王，徐J.，N张和Y.刘，“关于服务迁移的调查在移动的计算，”IEEE访问卷。6，第23511-23528，2018。查看在：出版商网站|谷歌学术搜索
15. Y.金，J.郭某和S.冲，“双面优化成本权衡延迟移动边缘计算，”IEEE车辆技术会刊卷。67，没有。2，第1765至1781年，2018。查看在：出版商网站|谷歌学术搜索
16. Y.毛，J.张，和K. B. Letaief，“动态计算卸油移动高端运算与能量收集装置”IEEE通讯选定领域杂志第34卷，no。12, 2016年3590-3605页。查看在：出版商网站|谷歌学术搜索
17. 王s，赵元义，黄l，徐杰，徐志华。移动边缘计算中服务建议的QoS预测，"杂志并行与分布式计算的，2017年。查看在：谷歌学术搜索
18. “移动云计算的动态计算卸载:一种随机博弈论方法”，载移动计算的IEEE交易程序，第1-1页，2018。查看在：谷歌学术搜索
19. 尤志昌、黄光光、蔡宏华及b.h h。《移动边缘计算卸载的节能资源分配》，IEEE交易在无线通信第16卷，no。3，第1397-1411页，2017。查看在：出版商网站|谷歌学术搜索
20. 陈海华、韩志强、李祥祥、刘富昌，“在边缘云中的线上作业分配与调度”，刊于《电子商务》计算机通信IEEE会议 - IEEE INFOCOM 2017年论文集，第1-9，亚特兰大，GA，USA，2017年5月。查看在：出版商网站|谷歌学术搜索
21. S.邓，黄L.，D.胡锦涛，J. L.赵和Z武，“移动启用服务选择的综合服务，”IEEE交易上的服务计算，第9卷，no。3, 2016年第394-407页。查看在：出版商网站|谷歌学术搜索
22. 问：你们和W.庄，“基于令牌的自适应MAC的两跳物联网-的启用MANET”物联网杂志IEEE互联网第4卷第2期2017年，第1739-1753页。查看在：出版商网站|谷歌学术搜索
23. R. Urgaonkar, Wang S.， He T.， M. Zafer, K. Chan，和K. K. Leung，“边缘云中的动态服务迁移和工作负载调度”，绩效评估，第91卷，第205-228页，2015年。查看在：出版商网站|谷歌学术搜索
24. Y.楠，李W.，W宝等人，“自适应能量感知计算卸油物联网系统的云”IEEE访问卷。5，第23947-23957，2017。查看在：出版商网站|谷歌学术搜索
25. 周振华，“论SaaS云计算的性能权衡”，《云计算的性能评估》，北京第32届IEEE会议计算机通信论文集，IEEE INFOCOM 2013，第872-880，意大利，2013年4月。查看在：谷歌学术搜索
26. S.仁，Y.他和F.许，“可证高效的作业调度在地理上分散的数据中心的能源和公平，”在第32届IEEE分布式计算系统国际会议论文集，ICDCS 2012，第22-31，中国，2012年6月。查看在：谷歌学术搜索
27. 李瑞特等人，“网络觅食的即时供应”，台北第11届国际会议上的移动系统，应用程序和服务程序（MobiSys '13），第153-166，纽约，NY，USA，2013。查看在：谷歌学术搜索
28. M. J.尼利，应用于通信和排队系统的随机网络优化，摩根和克莱浦，2010。
29. E. Chlebus和J.火盆，“网络浏览会话到达的非平稳泊松模型，”信息处理快报卷。102，没有。5，第187-190，2007。查看在：出版商网站|谷歌学术搜索|MathSciNet

版权

版权所有©2018陈莹等人。这是下发布的开放式访问文章知识共享署名许可，其允许在任何介质无限制地使用，分发和再现时，所提供的原始工作正确的引用。