文摘
移动计算边缘(MEC)为移动设备提供云计算服务将身体近端MEC服务器密集型计算任务。在这篇文章中,我们考虑一个多服务器系统,一个移动设备要求计算卸载到附近的多个服务器。我们制定这个卸载问题的联合优化计算任务分配和CPU频率缩放,以最小化任务执行时间和移动能源消耗之间的权衡。由此产生的问题是组合优化本质上,和最优解一般只能通过穷举搜索与极高的复杂性。利用马尔可夫近似技术,我们提出一种轻量级算法能证明地收敛到一个有界算法的解决方案。仿真结果表明,该算法能够生成算法和超越其他基准算法的解决方案。
1。介绍
近年来,移动设备(MDs)已经成为不可或缺的通信工具,信息,娱乐节目在我们的日常生活中。然而,有限的电池容量和有限的计算资源带来棘手的挑战为满足用户体验的需求。计算卸载被认为是一种很有前途的解决方案来应对这样的问题,通过计算任务从移动设备通过无线访问迁移到更强大的服务器(1]。移动云计算(MCC)已经被认为是一个可能的解决方案。一般认为,MCC的实现依赖于数据交换通过广泛的区域网络(与集中的云2]。然而,MCC对移动网络,带来了巨大的交通负载高通信延迟由于长途MDs的云。
移动计算边缘(MEC)部署MEC服务器直接基站使用generic-computing平台,是一个新提出的上述问题的解决方案。在这种范式,它和云计算服务提供接近移动设备(3]。通过赋予无处不在的无线接入网络(例如,宏单元和小细胞基站)与资源丰富的计算基础设施,MEC是设想提供无处不在的计算和敏捷增加服务的时间和地点是必要的。MEC的概念提出以来,欧洲电信标准协会(ETSI),它从学术研究者已经吸引了越来越多的关注。特别是,MEC的关键设计问题之一是资源分配(3]:一个计算任务应该处理本地MEC的MD的CPU或远程服务器,如果选择后者,应该多少资源分配给这个任务吗?这个问题源于基本任务卸载的成本之间的权衡和任务执行时间的减少带来的卸载。虽然概念上很简单,但它是具有挑战性的最优决策由于许多因素耦合和解决方案空间非常大。提出了各种方法来解决资源分配问题在各种场景中(3,4]。他们中的一些人专注于单用户情况下,而其他人则集中在多用户情况下。然而,在这些研究中,医学被认为是只有单个MEC服务器相关联。与小细胞/毫微微蜂窝基站的期望在未来大规模部署网络,MD可以选择将其任务到多个附近MEC服务器的计算能力,除了只有一个MEC服务器(5]。
本文在系统优化场景一个MD可以扩展其CPU频率和计算任务分配到多个MEC服务器。具体来说,我们利用多样性的任务分配和CPU频率最优控制决策,以最小化任务执行时间之间的权衡和移动能源消耗。我们制定这样一个组合优化问题,np难问题。灵感来自马尔可夫近似框架提出了(6),我们设计了一种有效的近似算法,算法的性能。总之,本文的主要贡献如下:(1)我们建议开发任务分配决策和计算扩展能力,共同优化在一个多服务器MEC系统延迟和能量之间的权衡,然后制定这种非线性组合优化问题。(2)我们设计一个近似算法基于马尔可夫近似框架(6有效地解决提出的问题。该算法可以找到算法解决方案通过实现一个马尔可夫链对所有可行的配置和执行状态转换(6- - - - - -8]。然后,我们研究设计了马尔可夫链的关键特征和分析算法的性能最优,近似差距,和错误的鲁棒性。(3)我们进行仿真实验证明性能马尔可夫approximation-based算法不同参数设置下。仿真结果表明,该算法可以生成算法和显著优于其他基准算法的解决方案。
本文的其余部分组织如下。部分2评审相关工作。部分3给出了系统模型和问题定义。然后,提出了马尔可夫approximation-based算法中引入部分4。部分5展示了仿真结果。最后,部分6总结了结论,概述了未来的工作。
2。相关工作
从计算的角度来看,MEC提供一项新的服务环境特点是近距离、效率、低延迟、高可用性,使得MDs[计算卸载一个有前途的范式3]。为此,必须考虑三个重要的问题,即资源配置、数据分区,优化目标。
由于卸载引入了额外的通信开销,关键技术面临的挑战是如何分配计算和通信资源,平衡能效权衡和支持用户体验的要求(4]。近年来越来越多的研究进展在资源配置为单用户9- - - - - -11)和多用户MEC系统(12- - - - - -14]。王等人。9]调查计算卸载MEC的联合优化MD的CPU速度、传输功率,和卸载率来实现两个不同的设计目标,即。,减少能源消耗和减少执行时间,MD。刘et al。10]采用马尔可夫决策过程的方法来解决在MEC电量有限延时最小化问题,在MD时间表基于队列的大小,其计算任务执行状态和频道信息。你等。11)提出了一个框架,一个医学博士不仅可以处理计算任务在本地CPU或卸载他们MEC服务器也从基站获取能量的微波功率转移(MPT)。在多用户情况下的卸载问题是更复杂的比,在单用户情况下。你等。12]研究了最优多用户MEC系统资源分配与时分多址(TDMA)和正交频分多址(OFDMA)。陈等人。13游戏)提出了一个理论方案计算卸载决策问题在多用户情况下,证明了设计的游戏总是承认一个纳什均衡。Sardellitti et al。14)设计了一种基于连续凸迭代算法近似技术来最小化整体用户的能耗和延时约束MIMO多单元的系统。然而,上面介绍的工作只考虑一个医学博士的情况只有同事一个边缘服务器。自未来的移动网络将异构由于基站密集部署具有不同的功能3),我们可以利用这种多样性提供更多卸载选项和足够的资源能力为保证MDs低服务延迟和令人满意的用户体验(15]。
一般来说,计算卸载可以执行两个时尚,即。,完整的卸载和部分卸载(9]。完全卸载,移动应用程序必须执行作为一个整体在MEC在MD本地或远程服务器(14]。与完整的卸载相比,部分卸载利用MD和MEC服务器之间的并行性,所以它更能满足严格的延时要求。然而,现有的工作9,16)通常假定数据分区的粒度,即。,the offloaded data could be partitioned as small as possible. In practice, a mobile application may contain some indivisible tasks or files that cannot be separated into parts of any size [5]。
计算卸载影响移动能源消耗和任务执行时间。一方面,在MD与对延迟敏感的应用程序的情况下对能耗有严格的要求,必须应用latency-oriented解决方案(9,10,17)有效地利用有限的能源,尽可能缩短执行时间。另一方面,为了延长MD的一生,能源化解决方案(9,11,12,14)提出了MDs的整体能源消耗降到最低,同时保证移动应用程序的延迟要求。据我们所知,只有少数研究[5,13,15)都集中在这两个指标同时优化。
虽然认识到它们的重要性,我们的工作不同于和补充现有研究。我们调查的联合优化任务卸载和计算在一个多服务器MEC系统可伸缩性问题的目的减少延迟和能量之间的权衡。除此之外,在系统建模,我们考虑许多实际方面失踪或被忽视的以前的工作调查相关问题。我们最好的知识,提出问题之前并没有探索工作。
3所示。系统模型和问题公式化
3.1。系统模型
让我们考虑一个医学博士,有一组任务要处理。它可以选择在本地CPU处理这些任务或卸载他们中任何一个附近MEC服务器 。我们假设无线基站使用正交无线频道,其中任意两个不会互相干扰。我们利用二进制变量 , ,和 ,代表任务分配,即
一个任务必须在本地或远程处理,即。,上述任务可以分为分离集。为了确保这一点,我们对以下约束:
一个计算任务米特点是三个数组参数, ,在哪里表示的总数量的CPU周期需要完成的任务米,而和表示计算输入数据的大小(位)和输出数据(比特)。在这项工作中,我们假定MD可以应用离线测量等方法(18)和调用图分析(13获得的值 , ,和 。我们现在分析计算开销方面的执行时间和能源消耗为本地和卸载方法。(1)本地计算医学博士:如果选择本地计算方法,它将执行计算任务米在本地使用自己的CPU。让计算能力(即。CPU周期每秒)of the MD. Given the decision profile和 ,计算一批任务的执行时间在当地的CPU是由
计算能源,我们有 在哪里表示的计算能力。在[19),θ范围从2到3,和是参数取决于芯片架构。它们的值可以通过测量的方法19]。使用动态电压频率扩展(dvf)技术(4,14,19),MD可以自适应地调整缩短执行时间或减少能源消耗。例如,Nexus S智能手机有6个CPU速度的水平,每个匹配与一些特定的电压(19]。在这项工作中,我们假设以一些有限和离散值 ,在哪里和最小和最大CPU频率的医学博士。(2)MEC卸载医学博士:如果选择了MEC卸载方法,它将出售计算任务米通过无线访问一个MEC服务器。这个选择服务器将执行的任务米代表。这种计算卸载会带来额外的开销方面的时间和精力为传输计算输入和输出数据。我们假设每个MEC服务器n可以为医学提供了固定的服务速率(即。CPU周期每秒) ,决定根据MEC计算服务合同订阅的MD的移动运营商(13]。平均利率上行和下行数据,用和 ,也假定为已知的医学博士之前任务处理应用中的方法(1,5]。为简单起见,数据传输和处理的任务被认为是不重叠的,干扰彼此(这意味着上传、下载步骤进行计算和顺序(5]。考虑到决策分布图 ,计算的总执行时间一批任务MEC服务器n可以给
MD的能源消耗在无线传输可以计算的 在哪里和分别表示传输和接收功率。
3.2。问题公式化
在这项工作中,我们希望优化两个指标,即。,the tasks’ execution time and the MD’s energy consumption. Because the MD and MEC servers process tasks in parallel, the time metric can be given by
可以由能源消耗指标
然而,这两个目标是耦合的 , ,和 ,所以他们不能单独和同时进行优化。研究它们之间的权衡,我们构建一个统一的目标函数(或系统实用程序) 在哪里表示执行时间的权重参数和能耗。通过这种方式,可以采取延迟和能量指标同时决策,和反映它们之间的相对重要性。如果医学运行一些应用程序对延迟敏感,它可以设置和在做决定。如果MD低电池状态和更关心能源消耗,它可以设置和在做决定。这样一个加权和的方法已被广泛用于建模类似的多目标优化问题(2]。
总之,是制定优化问题
开始时间约束(2),
这个问题本质上是一个混合整数非线性规划,这被称为赋权。此外,这也是一个组合优化问题,全局最优解的决策对于每个计算任务和MD的CPU。由于没有计算有效的方法得到精确的最优解,我们建议开发一种快速多项式近似算法,解决了问题基于马尔可夫近似框架(6]。
4所示。马尔可夫近似和算法设计
马尔可夫近似是一个最近提议的技术解决组合网络优化问题(6]。一般来说,这一框架包括两个步骤:log-sum-exp近似和构造问题特定的马尔可夫链,产生高效的并行实现近似求解问题。对马尔可夫近似最优性和收敛性的证明已经在(6]。
4.1。Log-Sum-Exp近似
让是一个可行的解决方案的问题 ,在哪里表示所有可行的解决方案,满足约束(2)。此外,我们表示效用系统的目标函数对应于给定配置f,所以问题可以表示为 。因此,相当于最低重量独立集(MWIS)的问题是 的概率表示的时间百分比系统配置f。关于的重量f,问题是寻找一个加权最小配置。马尔可夫近似后框架(6),的log-sum-exp近似收益率 在哪里β是一个积极的常数影响逼近性能。让是集的大小 ,近似精度是如下:
很明显, ,近似差距趋于0,从而近似变得精确。
根据(6),log-sum-exp近似(13)相当于解决以下问题 :
自是一个凸的问题,我们可以解决Karush-Kuhn-Tucker(马)条件20.),获得最优解
然而,很难解决的问题因为这需要完整的信息这通常是未知的,由于大范围的解决方案。然而,如果我们可以样品的配置空间从分布在(16),即。,time-sharing among different configurationsf根据他们的部分 ,我们解决问题因此问题约[7]。对这个问题,关键是要设计一个问题特定的马尔可夫链,模型可行的配置状态,达到平稳分布 ,并允许之间的平行结构任务。
4.2。马尔可夫链设计
事实证明,至少存在一个连续时间倒流遍历马尔可夫链的平稳分布在(16)和(6]。构建这样一个倒流马尔可夫链,我们让两种状态的马尔可夫链和使用状态转换速率f来 。它可以设计确保以下两个条件:(一)任何两个国家互相联系,和(b)详细的平衡方程是满意,也就是说, , 。上述两个足够需求允许大空间设计一个马尔可夫链状态空间结构和转移矩阵的设计。
首先,任何两个国家之间的转换速度可以设置为零,如果他们仍然可以从任何其他州。我们只允许两个国家之间的直接联系,只能通过执行一个任务迁移。
第二,两个作业直接转换,例如,f和 ,我们设计它们之间的转换速率 在哪里是一个常数表示状态转换的平均时间6]。
4.3。马尔可夫Approximation-Based算法
根据马尔可夫近似(6),在我们的系统中,一个配置f由计算任务使用一个本地配置。如果所有任务运行单个连续时间时钟时间和等待performance-dependent切换本地配置,我们可以实现目标马尔可夫链之间的这种转变只发生两种构型f和当他们彼此不同于只有一个任务的本地配置。
实现基于我们的设计显示了马尔可夫链的算法1。这个算法解释如下。MD初始化一个专用线程的计算任务。首先,每个线程随机选择一个满足约束条件的可行的目标设备(2) 。此外,CPU频率也是随机挑选的候选人吗 。在阶段1中,每个线程与指数分布随机数的意思等于γ根据这个号码和数量。在第二阶段,当计时器的任务米到期,专用线程第一次将重置信号发送给其他线程通知他们即将到来的潜在的过渡然后随机生成一个新的配置在任务分配和变频。线程米将运输的概率或者呆在当前配置f的概率 。在第三阶段,当任务的专用线程服务接收到一个复位信号,它终止当前的倒计时过程,然后通过第一阶段。由于潜在的马尔可夫链的性质,该算法将在概率收敛算法配置足够数量的时期。
|
根据在算法1,我们有两个典型的过渡场景如下。首先,如果 ,然后 。第二,如果和 ,然后 。因此,设计的在(17)可能会导致系统配置最小化目标的问题 。
证明。从建设统治状态马尔可夫链的结构,我们可以知道所有配置可以达到彼此在一个有限数量的转换,所以生成的马尔可夫链是不可约。此外,它是一个有限状态遍历马尔可夫链和一个独特的平稳分布。现在,我们表明,马尔可夫链的平稳分布是(16)。
在算法1的跃迁概率的任务米从f来是
。然后从系统来看,过渡的可能性由于单个任务的选择米从任务集是
。此外,由于任务分配根据倒数计时器被激活的机制γ从国家,它遵循过渡率f来是
使用(16)和(18),我们可以得到
,
;也就是说,细致平衡方程。最后,我们知道了马尔可夫链是倒流,及其平稳分布是(16根据定理1.3和定理1.14)(21]。
4.4。履约保证
在实践中,它是可能的,我们只能获得一个不准确的测量或估计的对于任何 ,由于不精确的测量或当地估计(8]。结果,摄动马尔可夫链可能不收敛到期望的平稳分布 ,但非最优稳态分布。这个观察激励我们学习的性能差距的存在扰动误差。
为每个配置与 ,我们假设相应的扰动误差属于有界区域 ,在哪里是不绑定的。然后,摄动需要的只有一个离散值 ,在哪里是一个积极的常数。此外,随着概率 ,的摄动需要的值 , 和 。
在分析基于摄动误差(22),我们有以下结果。
定理2(一个)。摄动马尔可夫链的平稳分布 在哪里 。
定理2 (b)。最优的差距没有和扰动错误如下所示: 在哪里是最佳的系统实用程序的问题 , 是预期的系统实用程序与原完美的马尔可夫链,是预期与摄动系统应用马尔可夫链,然后呢是最大扰动误差。
(一)证明。我们认为每个州的一个扩展马尔可夫链f是扩大到州
,
用以下转变:
在哪里
,
规模扩大州和的概率是多少
。这个扩展马尔可夫链有一个独特的平稳分布,因为它是不可约的,只有有限数量的州。表示由
,
,
是美国的平稳分布在这个扩展马尔可夫链。根据(22)和细致平衡方程
,我们有:
在哪里指的是国家f没有错误。
使用
,由此可见,
表示由
。使用(24),我们终于有了
证明(b)。首先,我们证明了最优界限的差距原来的马尔可夫链。让 ,狄拉克分布, 自在(16)的最优分布问题 ,我们有 詹森不等式,我们可以获得 结合(27)和(28)的收益率 因此, 接下来,我们证明了边界摄动的马尔可夫链对最优性差距。通过部分(a),概率分布可以被视为最优解问题通过替代效用函数通过 。从(20.),我们有 插入的值到(31日),我们得到 根据的定义 ,很容易知道 因此, 结合(32)和(34)的收益率 为 ,我们有 因此, 一般来说,给计算任务,MEC服务器和MD的本地CPU频率的水平,可用配置的总数是有界的 最后,通过堵塞(38)(30.)和(37),我们证明定理2的部分(b)。
5。仿真结果和分析
5.1。仿真设置
在本节中,我们评估我们的马尔可夫approximation-based算法的性能(用MA)模拟基于引用的参数(5,23,24]。表1列出了仿真参数的默认值在我们的实验中,如果不是另有规定。
马为了评估算法的性能,我们比较它与以下三个基本方法:(1)穷举搜索(ES):找到最优解,列举所有可能的配置,从而导致高计算复杂度和小型问题的唯一可行的。(2)随机分配(RA):解决方案是通过随机分配计算任务和设置CPU频率。(3)本地处理(LP):所有计算任务的CPU处理医学博士和频率分配是最优的。
消除随机性的影响,马的实验,RA和LP是独立进行多次为每个给定的设置。为清晰的比较,我们选择显示结果的平均值或导致数据的范围。类似于(7),马的收敛时间被定义为的时间不超过连续两个值之间的差别 。
5.2。绩效评估
5.2.1。马的收敛算法
首先,我们检查马不同设置下的收敛性。图1显示了马的融合方法在低负荷的情况下的任务 。结果表明,马50迭代收敛迅速接近最优状态后,独立问题的大小。计算复杂度远低于列举所有ES方法组合的可能性。我们进一步研究马的性能在不同的比率和 。的价值选择这样 ,在哪里 。图2表明,改变这两个标量权重没有马对收敛的影响,证实了近似差距的存在(14)。
随着问题规模变得更大(例如, ),ES需要大量时间(例如,几个小时甚至更多)来搜索最优解选项,而马迭代收敛后约1100。在这样一个高负载的情况下,我们比较与ES马,以及最好的结果RA和LP从多个独立运行。如图3,不管有多少MEC服务器使用(即,马或4),可以逐步收敛到最优迭代生长。很明显,更多的MEC服务器可以提供更多的卸载选项,进一步提高能源和延迟性能。尽管RA在图的最佳结果3方法找到的最优效用,RA毫无实用价值,因为它通常是无法保证确定的输出。在四个方法,LP最大效用值,表明MEC卸载对于缩短执行时间和降低能耗是至关重要的在这种情况下。
5.2.2。链接速度的影响
在图4,我们比较算法的性能对不同数据传输条件。利率控制在三个不同范围的联系,也就是说,低利率(0.5 Mbps∼1 Mbps),中等速度(2 Mbps∼10 Mbps)和高速率(20 Mbps∼50 Mbps)。从图4,马算法总能收敛,收敛时间减少链接率增加。从图我们也可以观察到4(一)马收敛于相同的结果作为LP,不管有多少MEC服务器使用。这是因为链接时利率很低,几乎所有在本地处理的任务通过卸载以来的MD的CPU成本对能源和延迟远高于本地计算。随着利率的联系增加,把成本降低,因为较低的传输时间,让它更比卸载任务MEC服务器通过使用我们的马算法(如图4 (b)和4 (c))。
(一)
(b)
(c)
5.2.3。参数的影响β
图5显示的影响β对系统效用和收敛时间。不同颜色的虚线箭头人物5表明收敛的迭代时间是通过马与给定参数β。结果表明,β增加从4到50,马最终会获得一个近似获得的效用更接近最优值,但相应的收敛时间会变得更长。这让我们做出灵活的选择,各种权衡点之间的系统优化和收敛时间。这些观察结果如图5是一致的(20.定理2中)。
5.2.4。摄动误差的影响
就像前面提到的4所示。4在实践中,我们通常获取不准确由于估计错误。验证(21定理2中),我们进行实验研究扰动误差对马的性能的影响。要做到这一点,我们添加不同程度的随机误差( ,均匀分布)和对所有n。在实验中,我们让马控制决策基于摄动链接率但使用实际值来计算目标效用。我们发现马确实可以收敛到一个次优的解决方案,即使扰动存在错误。描述最优的差距,我们选择最优结果ES没有扰动的错误作为基线和使用此基线检查最坏的(即。马,最大)实用程序通过在多个独立运行。图6显示了不同比率的实用程序在不同的错误率。从图中,我们发现出错率不同来 ,最优的差距不断增加来 。这些结果进一步证实了定理2的估计是正确的价值观,贫穷的性能达到。然而,当错误率小于阈值(例如, ),最优的差距非常小。
5.2.5。延迟和能量之间的权衡
在图7,我们学习任务执行时间之间的权衡和马移动能耗算法。正如我们在图中所做的一样2,完全的11种不同的组合和选择比较的图吗7。为每个曲线在图7,标记了从左到右的顺序ω。相应地,最左边的标记对应的条件 ,和最右边标记对应的条件 。从这个图中,它是可行的优化两个标量权重为实现一个理想的延迟和能量之间的权衡。不过,我们可以注意到,当ω增长大于某个阈值(例如,当 ),能源消耗的减少趋势变得光滑而执行延迟不断增加。因此,的值和应该仔细选择达到一个令人满意的energy-latency权衡。另一方面,增加导致延迟和能量,显著减少,曲线转移到手机的左下角时情节。这个观察证实,它有利于提供多个MEC服务器任务卸载的MD。然而,性能改进逐渐减少的时候变得更大。
6。结论
本文地址计算卸载问题在多服务器移动边缘计算场景中,一个医学博士可以卸载多个MEC服务器的计算任务。我们制定这个问题作为任务分配的联合优化和频率扩展,旨在最小化之间的权衡MD的能耗和总任务的执行时间。为了解决这个np难度问题,马尔可夫approximation-based算法设计找到一个算法解决方案,结果只有一个小和有界与最优。通过仿真实验与许多实际问题,我们确认我们的算法能够收敛算法性能,确保理想的鲁棒性和可伸缩性。此外,该算法明显优于其他基准算法等详尽的搜索和本地处理。
对未来的工作,我们将检查我们的马尔可夫approximation-based与多个MDs方法获得更普遍的结论。进一步,我们将我们的方法扩展到一个在线的情况下,问题可以解决与MDs的动态到达和离开。这也是值得评估的工作在实际试验台移动计算边缘。
数据可用性
实验数据用于支持本研究的发现可以从相应的作者。
的利益冲突
作者宣称没有利益冲突。
确认
这项工作是基础研究基金支持的中国中央大学授予2016年jbz006和CETC联合基金拨款6141 b08020101之下。