英语原文共 9 页
移动云计算中的能量高效的动态卸载和资源调度
摘要：移动云计算作为一种新兴的、前瞻性的计算范式，通过将计算密集型任务从资源受限的智能移动设备（SMDs）转移到资源丰富的云上，可以显著提高智能移动设备的计算能力，节约能源。然而，如何在应用程序完成时间的严格约束下实现有效的负载计算仍然是一个难题。为了应对这一挑战，本文提供了一种高效的动态加载和资源调度（eDors）策略，以降低能耗并缩短应用程序完成时间。我们首先在满足任务依赖性要求和完成时间期限限制的条件下，将eDors问题转化为能源效率成本（EEC）最小化问题。为了解决优化问题，提出了一种分布式eDors算法，该算法由三个子算法组成，分别是计算卸载选择、时钟频率控制和传输功率分配。更重要的是，我们发现：卸载选择的计算不仅取决于任务的计算工作量，还取决于其直接前任务的最大完成时间以及移动设备的时钟频率和传输功率。最后，我们在一个真实的实验台上的实验结果表明，eDors算法可以通过在本地计算中基于动态电压和频率缩放（DVFS）技术优化调整SMDs的CPU时钟频率，使传输功率适应云计算中的无线信道条件，从而有效地降低EEC。
关键字：移动云计算、能源效率成本、流量计算、资源分配。
I.引言
目前，智能移动设备（SMD），例如智能手机和平板电脑，都获得巨大的人气，由于他们的便携性和紧凑性，SMDs被视为在未来具有统治性的计算设备，以用来支撑计算密集型的应用，如互动游戏、图像/视频处理、电子商务、在线社会性网络服务[ 1 ]，[ 2 ]。这样的复杂应用要求SMDs拥有更高的计算能力，内存和电池寿命[ 3 ]。但是，由于物理尺寸的限制，是一般的移动设备的资源是有限制的。特别是，对于SMDs来说，电池的有限能源供应已成为一个具有挑战性的设计问题 [ 5 ]，[ 7 ]。
随着无线通信技术的发展，如Wi-Fi和3G，4G，移动云计算（MCC）被预测是一个有前途的方法来处理这个挑战。MCC的目标是扩展资源丰富的云端的强大的计算能力到资源受到约束的SMDs，以用来增强SMDs的计算潜能。为了实现这一目标，MCC需要通过无线介入将资源密集型计算从SMDs迁移到云端，称为计算卸载，在MCC中的移动应用程序被分割为一系列任务，这些任务可以是在本地的移动设备上执行，被称为是本地计算/执行，或在云端的设备上执行，成为云计算/执行。显然，MCC可以使SMDs有能力去执行那些由于SMDs上资源不足够，而不能独自使用SMDs来处理的复杂的任务，如感知应用程序[ 4 ]。 MCC的另一个优势，就是可以通过对应用中的任务有选择地卸载到云端服务器上来提高移动设备的性能，此外，MCC是有利于移动设备的节能进而延长可操作时间。
虽然基于计算卸载技术的MCC可以显著提高SMDs的计算性能，但开发可靠的MCC系统仍然是具有挑战性。一个关键的挑战是如何实现高效能耗的计算卸载。为了实现MCC在移动设备节能和性能改进方面的预期效益，我们应该考虑以下问题：（i）应用程序的哪些任务应该被卸载到云服务器上？（ii）本地计算中每个任务应分配多少CPU时钟频率？（iii）在云计算中，应使用多少传输功率来实现任务的卸载？
为了回答上述问题，本文重点研究了计算卸载与资源调度问题的联合计算，其中有三个关键问题需要解决：
bull;当任务依赖性要求和应用程序完成时间限制都被强制执行时，任务的选择卸载计算会发生什么？强制是必要的，因为任务之间通常存在一定的先例，应用程序完成时间对于延迟敏感的应用程序来说是一个严格约束。
bull;在定义2中的能源效率成本（EEC）是否可以在本地执行中通过DVFS技术[8]对移动设备的CPU时钟频率进行优化控制，从而达到最小化。
bull;在满足云执行中的任务优先级要求的同时，是否可以通过优化分配给每个计算卸载的数据传输功率来最小化EEC？
本文的目标是通过最小化移动设备中完成应用的计算所需的EEC消耗，来提供一个最佳的动态卸载和资源调度（eDors）策略。
与之前的论文[8]–[12]相比，本文有几点贡献。
首先，通过考虑任务优先级对计算完成时间的影响，分别用本地计算和云计算中的能耗和计算完成时间来表征EEC。其次，在应用完成时间和任务优先要求的约束下，将eDors问题转化为EEC最小化问题。 在公式中，应用程序的最大完成时间（即完成时间期限）要求，是用来强迫满足不同类型的应用程序，如延迟敏感应用程序和延迟容忍应用程序。第三，为了解决优化问题，我们提出了一种分布式eDors算法，用于计算卸载选择、时钟频率控制和传输功率分配策略。更重要的是，我们发现，卸载计算的选择决策不仅取决于任务的计算工作量，还取决于它的直接的前任务的最大完成时间以及移动设备的时钟频率和传输功率。第四，我们在一个由20台安卓智能手机和一台云服务器组成的真实试验台上实施了提出的eDors策略，实验结果表明，与现有的策略[8]、[9]、[11]相比，EDORS策略可以有效地降低能耗和应用完成时间。
据我们所知，这是首个通过考虑本地计算中的CPU时钟频率控制和在云计算中传输功率分配，在完成时间期限限制和任务优先级要求下，将能耗和应用程序完成时间降到最低的动态卸载和资源调度的论文。
II.相关工作
论文中对计算卸载问题做了大量的工作，并提出了多种计算卸载的策略这些政策可分为两类：（i）基于性能的卸载策略[4]、[10]、[13]–[16]和（i i）基于能耗的卸载策略[8]、[11]、[12]、[17]、[18]。
基于性能的卸载策略的目标是通过利用云资源在执行/完成时间和吞吐量方面提高移动设备的性能。 因此，资源密集型计算将被加载到云端。 Chun等人在[13]中提出了一个克隆云，该克隆云可以自动地将应用程序分割成合适大小。在[10]中，基于克隆云，Yang等人通过将运行在智能手机上的部分安卓代码动态的卸载到云端，优化了总体执行时间。在[4]中，Satyanarayanan等人提出了一种使用虚拟机概念的模型，该虚拟机运行在受信任且资源丰富的计算机上，或者是一个名为cloudlet的计算机集群上。Yang等人在[14]，[15]中研究了多用户计算分区，以优化数据流应用的分区，使应用程序具有最大吞吐量。然而，上述工作既不关注能源效率最小化问题，也不考虑任务依赖性对卸载策略计算的影响。
另一方面，基于能量的卸载策略旨在降低移动设备的能耗。这是通过计算卸载来减少任务的计算开销来实现的。因此，计算密集型任务在云中执行。在[18]中，通过使用李雅普诺夫优化，Huang等人提出了一种移动设备节能的动态卸载算法。在[11]中，Zhang等人提供了随机无线信道下的能量优化移动云计算框架。此外，他们在[12]中还提出了一个针对移动任务的协同任务执行框架。但是，上述工作没有考虑采用CPU时钟频率控制来降低能耗。Lin等人在[8]中提出了一种任务调度算法，以最小化应用程序的总能耗，但它并没有考虑到卸载任务决策中的能量分配问题。
据我们所知，在多个SMD的设置下，只有很少的工作能够解决卸载问题的计算：以最小化能耗和应用程序完成的时间。在[9]中，Chen将SMD中的分散计算卸载问题表述为一个分散的博弈。但是，与我们的工作相比，他们在计算加载策略时没有考虑任务优先级和资源调度。
III.系统及计算模型
本节概述了MCC的系统模型，并公式化了本地计算和云计算中的EEC。
A系统模型
我们假设在一个区域内有n个智能移动设备（SMD），由一组n=1,2，hellip;，n表示，每个都有一个计算密集型移动应用程序要完成。MCC中的每个移动应用程序被划分为m个任务序列，由一组m=1,2，hellip;，m表示。SMDs以两种方式将计算卸载到云端，即通过移动网络（电信网络）或访问点，如图1所示。在移动网络情况下，移动设备（如移动智能手机）通过基站（BS）通过3G或LTE连接到移动网络。在接入点情况下，SMD通过Wi-Fi连接到接入点。 本文采用[15]中的动态分区方案来实现移动应用程序的分区。其原因在于，该方案是考虑了包含在云资源上的卸载计算的调度的多个用户计算的分区。当然，本文中的其他分区方案对于我们的设计也是可行的。我们使用一个有向无环任务图g=（v，e）来描述这些任务之间的关系，如图2所示。g中的每个节点iisin;v表示一个任务，有向边e（i，j）表示任务i和j之间的优先约束，这样任务j在完成其先前任务i之前是不能开始执行的。
由于通信和计算模型在移动云计算中起着关键作用，接下来我们将详细介绍通信和计算模型。
图1 演示移动云计算与多个移动设备
图2 任务之间关系的简单示例
B通信模型
我们首先介绍无线接入的通信模式。除非另有规定，无线接入点可以是WiFi接入点，也可以是蜂窝网络中的基站。从SMD n到接入点S的信道遵循准静态衰落信道模型。我们让表示移动设备n的任务m的卸载决策的计算，具体来说，表示SMD n 选择通过无线接入将任务m的计算卸载到云端，而表示SMD n决定在自己的设备上本地执行任务m。此外，我们用,表示所有移动设备的所有任务的决策概率。对于一个给定的决策方案，我们可以计算上行链路数据率，用于计算移动设备n的任务m的流
量，如下所示：
式中，是SMD n的卸载任务m向无线接入点s的传输功率。表示在发送任务 m时，由于路径损耗和阴影衰减，从SMD n到接入点s的信道增益，表示与链路（n，s）相关的热噪声功率，W表示信道带宽。
我们可以从（1）中观察到，如果许多移动设备同时通过无线接入卸载计算，可能会导致严重的干扰和低数据速率。
C 计算模型
我们让表示与SMD n中的计算任务m相关的计算输入数据的大小（例如，程序代码和输入参数），用表示完成SMD n中的任务m所需的计算工作量，即CPU周期总数。让，，和分别表示本地执行的完成时间、无线任务传输时间（即任务已完全加载到云端）、云端执行时间和SMD n的任务k的无线接收时间。接下来，我们从本地和云计算的能耗和应用完成时间方面讨论计算开销。
- 本地计算：让表示任务m上SMD n的计算能力（即CPU芯片的时钟频率）。这里我们允许不同的移动设备具有不同的计算能力，并且对于一个SMD在不同的时钟频率下执行不同的任务。给出了SMD N任务M的局部计算执行时间：
移动设备的能耗由下式表示：
其中，k是有效的开关电容，取决于芯片结构。我们设置k=从而使能耗与[19]中的测量值一致。很明显，我们可以通过使用DVFS技术来调整CPU芯片的时钟频率，从而在移动设备上实现最佳的计算时间和能耗。
在开始执行任务m之前，它的所有直接前置任务都必须已执行。接下来，我们给出任务准备时间的定义[8]。
定义1（准备时间）。任务的就绪时间被定义为任务的所有直接前置任务完成执行的最早时间。因此，在本地计算中，SMD n的任务m的就绪时间，用表示，由下式给出：
其中pred(m)表示任务m的直接前置任务集。
与现有的工作[9]，[18]相似，我们忽略了从云端将计算结果返回到移动设备的时间和能量消耗，因为对于许多应用程序（例如图像处理），返回结果的能耗和时间的大小通常比输入数据的小得多。基于这个假设，（4）可以改写为：
这意味着，如果不考虑通过无线信道接收任务k的结果的时间，则只有在任务k完成执行后，任务m才能开始执行。
显然，SMN n上任务m的本地执行完成时间是本地计算执行时间和本地计算中就绪时间的总和，即：
根据（2）和（3），我们可以通过以下定义计算能源效率成本（EEC）
定义2（能源效率成本（EEC））。能源效率成本（EEC）被定义为执行任务的能耗和计算完成时间的加权总和。因此，在本地计算中，SMD n任务m的EEC由下式给出：
式中，0le;le;1和0le;le;1分别表示SMD n对任务m做出决策所消耗的能量和计算完成时间的权重。
为了满足用户的特定需求，我们允许不同的SMD在决策过程中选择不同的权重。例如，电池电量低的设备在决策时要选择较大的来节省更多的能量。当移动设备运行一些延迟敏感的应用程序（如在线电影）时，它可能更倾向于设置更大的来减少延迟。
- 云计算：对于云计算，移动设备n将其计算任务m卸载到云服务器上。然后云服务器将执行计算任务并将结果返回到移动设备n，很明显，云服务器中任务m的执行包括三个阶段，依次为：（i）发送阶段；（i i）云计算阶段；（i i i）接收阶段。
根据第III-B节中的通信模型，我们可以分别计算SMD n卸载任务m的传输时间和能耗为：
和
此外，我们还可以通过云计算得到SMD n任务m的执行时间：
其中表示云端处理任务元的时钟频率。我们假设是固定的，并且在计算过程中不会改变。
在本文中，我们不考虑在云上执行SMD n的任务m所消耗的能量，这是合理的，因为云服务器通常由交流电供电，并且有足够的能量来执行卸载的任务。
与第III-C1节类似，在考虑任务之间的依赖性的情况下，任务m在云上的就绪时间，由表示：
我们可以观察到，如果任务m的直接前置任务k在本地执行，那么=0。因此在公式（11）中是将所有卸载到云上的任务m的直接前置任务执行完成的时间。此外，我们可以发现只有在任务m完全加载到云端或任务m的所有直接前置任务已完全在云端执行，任务m才能开始执行，即：
特别是，如果我们忽略了接收任务m的结果的时间，那么SMD n的任务m的云执行完成时间就是SMD n的任务m在云上的执行时间与就绪时间之和，即：
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
