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

IEEE TRANSACTION ON COMPUTERS, OCTOBER 2013

对于延迟敏感的移动云应用的多用户计算分区

Lei Yang, Jiannong Cao, Senior Member, IEEE,

Hui Cheng, Member, IEEE, and Yusheng Ji, Member, IEEE

摘要：移动设备和云计算之间的计算弹性分割是一个重要且具有挑战性的研究话题移动云计算。现在研究重点放在单用户的计算分区，其目的是优化应用程序的完成时间为一个特定的单个用户。但是，这些假定云总是有足够的资源立即执行的计算，当他们加载到云中。然而，这种假设不成立为大规模的移动云应用。在这些应用中，由于在大量争夺云资源用户，加载计算可能会让云有一定的调度延迟执行。单用户划分的没有考虑到云中的调度延迟可能会产生显著的性能下降。在本文中，我们第一次研究多用户计算划分问题（MCPP），它考虑的多个用户的分区计算与云计算资源加载计算的进程安排在一起。而不是追求最低的申请完成时间为每一个用户，我们的目标是实现最小平均完成时间为所有用户的基础上，配置的资源在云的数量。我们表明，MCPP 与经典作业不同且难度较大。我们设计了一个离线的启发式算法，即SearchAdjust，去解决MCPP 的问题。我们通过展示这SearchAdjust 都优于单用户划分方法和经典的作业调度方法标准降低在应用延迟平均10％。基于SearchAdjust ，我们还设计了一个在线算法MCPP在实际系统中可以很容易地部署。我们用真实世界的负载痕迹验证在线算法的有效性。

关键词：移动云计算;加载;计算分区;作业调度

1.介绍

传感器在智能手机上的扩散使一种新型的移动应用，比如对象/手势识别，移动生物体，健康监测或诊断，移动增强现实等等。这些应用通常需要持续采样和处理率很高的传感器像加速度计，全球定位系统，麦克风和摄像机。这些计算密集型的分类算法应用程序通常导致在计算能力有限的移动设备的表现欠佳。为了解决这个问题，计算负载近年来已经成为研究的重点。计算负载的基本思想是将移动设备的某些任务转移到云计算中实行。在强大的处理器云可以更快地运行计算密集型任务。

通过负载技术的使用，一个基本的问题是在移动设备和云之间的应用程序分区涉及的计算。它被命名为计算划分问题。鉴于该应用程序由一组的依赖任务，计算分割问题是决定每个任务是在移动设备上执行还是在云端执行，以使得成本被最小化。近期的工作[3] - [11]上的计算划分问题在他们的成本差异。他们认为是这些因素所导致的诸如移动设备的能耗，应用延迟和数据传输量网络，或这些因素的组合。

然而，这些工作主要集中在分割一个无关用户模型，其中，计算被分配给单个用户但是分区结果不影响其他用户。假定云总是具有足够的资源去无延误地完成加载任务，不管有多少其他用户在使用加载在云的计算。然而，从应用程序提供者的角度来看，假设是不实际的，由于下面的两个的原因。首先，应用提供商需要到平衡ANCE 从云的IaaS 租用的资源数提供商和所述应用程序的性能，以便降低其运营成本。其次，由于大规模移动用户的数量难以预料云应用程序数量，该应用程序供应商不能保证所有的资源足够来满足移动用户的加载请求。因此，有必要去解决计算分割问题云资源受限数目。我们称这个问题为多用户计算分区问题（MCPP）。

MCPP 比已经存在的计算划分问题更有挑战性。在MCPP 中，用户的分区结果取决于与他们对云计算重新竞争源。例如，一个用户的是否决定加载任务，不仅取决于它的保存计算成本和通信成本，但还取决于很多其他用户如何加载任务到云中。用户加载任务数到云计算代表了云计算的负载。如果负载提高，好处是可以牺牲等待花费的时间提供云资源负载。一个最佳解决方案需要为MCPP 所有用户的计算统一安排到他们的移动设备和云资源。

在本文中，我们研究了MCPP的延迟敏感的移动云应用。问题是要安排上制约了负载计算云中的资源数目以及对于所有的用户分割移动端和云端之间的计算，使得平均应用延迟被最小化。选定的性能指标是应用程序的平均延迟/延迟，因为它是最关键的一个延迟敏感的移动云应用程序。此外，我们研究如何应用与配置的云化性能的变化资源和系统上的负载，并且因此构建一个性能资源负载（PRL）模型。该PRL模型提供应用程序的性能和云资源成本之间的最佳平衡，相信模型可以帮助应用提供商实现的成本控制及有效利用云资源。从而节省运营成本，是这项工作的主要工作如下：

bull;据我们所知，从应用提供商的角度来看，这是首次研究多用户计算分区程序问题（MCPP）。问题共同考虑为每个用户计算和在云中的资源加载计算的日程安排的分区。它可以帮助应用提供商在面对用户的不可预知的数量时，以达到最佳的应用性能。

bull;我们证明了我们的MCPP 是不同的，比现有的作业调度问题，如任务调度问题在异构计算（TSPHC）和分层文件系统（HFS）调度问题更加困难。

bull;我们系统地解决了离线通过MCPP 提出一套具有竞争力的算法。通过基准测试，我们证明了我们的提出的算法，SearchAdjust，在应用程序延迟的期限比现有列表调度算法有更好的性能，提升百分之十。

bull;我们设计的MCPP 在线算法可以在实际系统中进行部署和使用真实世界负载证明其有效性的证据。

2.相关工作

在本节中，我们简要地介绍了相关工作在移动云计算划分问题计算。在作业调度等相关工作问题在3.4节讨论。

云服务在手机中的应用生态系统是新兴的移动计算模式，即移动云计算（MCC）。根据我们之前工作的方法，我们分为三个MCC [3]：A）扩大访问到云移动设备的服务; B）使移动设备以协同工作为云资源供应商[1] [2]; C）使用云资源，例如移动应用程序的执行通过负载选定通过移动应用程序所需的计算任务设备到云中。这将允许移动开发人员可以创建远远超过传统的应用移动设备的处理能力。

大多数在移动云的研究工作使用第三MCC 方法[3] - [11][19]。他们专注于计算划分问题。在[10] [11]的工作，该计算是与本地视图匹配。每个任务/模块加载决定不参与应用程序中的其它任务/模块的全球视野而成。对于每个任务/模块，如果云降低的处理成本比由整个网络的数据传输导致的成本增加较大，那么它将被加载到云中。[10]旨在节省能源消耗，同时[11]旨在最大化的执行时间和吞吐量。

在[3]-[7][19]中的工作，计算是以全球视野来分区。每个任务/模块加载的决策都依赖对方，并与剖析的共同作出所有的任务/模块的信息包含在应用程序。 [4]表明的方法加载优于全球视野的方法。计算分区问题此类别中被建模为一个优化问题。他们在应用程序模型或不同相应的优化目标。在[4][5]，应用/程序被建模为方法图/树，其中每个顶点表示一个方法和加权用其计算和能量成本，每个边表示方法调用和加权与要传送的数据的大小远程。最优化问题，使用解决了整数线性规划。 [6][7]聚焦在其上构成一组服务的应用程序，和目标优化的因素，如延迟之一、数据传输量和能源消耗，或优化的因素定制组合以上。[3]着重于数据流的划分应用程序，并且使用数据流图来建模的应用。遗传算法被用于最大化应用的吞吐量。

我们注意到在计算划分问题[3]-[11][19]该从待机解决的所有工作单个终端用户的点，并且假设在云存储端无限的资源。现有的几个工作研究如何分割的计算当用户数标尺下，从应用提供者的角度来看，目的是节约资源的同时最大限度地提高应用程序的运行成本并且不影响用户体验。在本文中，我们将研究多用户计算分区在考虑云资源的约束问题。

3.系统模型与问题描述

3.1应用程序模型

我们的目标是延迟敏感的移动云应用，这需要良好的用户体验低延迟。这些应用程序常常需要传感数据作为输入，执行操作的一个序列上的数据，然后输出结果。移动增强现实被认为是一个典型的应用。该应用程序使用照相机和或其它传感器来感知用户的环境场景，然后来扩充原始场景的相关信息。这种做法是经常做的是由驱动作为用户的输入。增强现实的核心部分应用程序是基于图像识别物体。图1示出涉及在整个操作基于图像识别物体的过程。注意该SIFT 算法是用于提取特征[12]。

在我们的工作中，应用被建模为一个处理模块序列（如图1）。该模块代表了一种操作上数据与其代表的依赖模块之间。这意味着一个模块未开始运行，直到它的先例模块完成。每个模块允许在本地上运行移动设备或远程的云。另外，应用程序的输入数据被认为是从移动装置的传感器，并且输出数据应该传送回移动设备。性能指标是的执行应用的时间。作为执行时间表示该应用程序的响应延迟/延迟，我们在本文中简单地使用期限延迟或延迟。 延时是所有的计算时间的总和即模块和数据之间传输的时间。

图.1. 基于图像识别物体的功能模块

3.2单用户的计算分区

我们首先描述的单用户计算划分问题（SCPP），其中单一的用户运行申请并请求云负载计算。假设应用程序由n个模块顺序。每个模块可被执行无论是在移动侧或在云一侧。该模块j的执行时间是，如果它被加载在云上（）;否则，它是，其中gt; 。如果两个相邻的模块j和j 1运行在不同侧，数据传输时间为;否则j和之间的数据传输时间当它们在同一侧运行j 1变为零。 至模型，该模型的应用程序的输入/输出数据应该从/到移动装置，我们添加两个虚拟模块0和n 1的入口和出口模块。

定义1单用户计算分区问题（SCPP）：考虑到计算成本和（）和通信成本j（）该SCPP 是确定哪些模块应加载到云，使得该应用程序延迟被最小化。它是由分配

其中是一个二元决策变量。如果模块j被加载到云中=1，否则=0或X0 = = 0。

3.3多个用户计算分区

接着，我们说明多个用户的系统模型计算分区。该系统包括两部分：云计算和移动客户端。在手机客户端，我们有一组请求发送到云为用户应用程序的分区执行。客户端中间件的监控代理收集信息该装置和无线信道条件上。 这些信息与请求到云发送。该在云的PaaS 中间件提供的编程并运行分区和执行时间支持的应用程序。在接收到用户的请求，在PaaS 的中间件的分区是使每个用户做分区决策，即决定该应用程序的哪些模块上所执行的

移动设备和模块加载到云中，并且也安排负载模块到云服务器/虚拟机。在我们的模型中，我们假设该用户请求执行分区的同一个应用程序。但是，我们可以扩展该模型通过考虑用户请求各种应用程序，并轻松应用中的方法第5,6,7进入扩展模型。在我们的论文，我们所关注的划分问题的研究及的是相应的算法的设计在分区实施。

我们考虑，在一个固定的时间周期（0，T）的其中共有多lambda;请求被发送至云。让我表示一个特定的请求和我表示发布时间要求i，其中1le;ile;lambda; 和0le;le;T.为了描述方便，当我们何况用户i或第i个用户在本文中，我们参考哪个用户发出请求。

我们云资源作为一组服务器/虚拟机模型。云资源的数目被表示为r。 如在SCPP 提到的，表示应用程序的第j个模块的远程计算成本（时间）。通常情况下，手机的用户有不同的处理能力和网络带宽。因此，我们使用一个的矩阵W来代表本地计算成本其中，j给出了执行时间来完成第i个用户的移动装置上的模块。Pi;表示lambda;times;（n 1）的通信成本矩阵，其中，，表示数据传输的时间从模块j即j 1对用户i。

我们首先研究了离线多用户分区问题，我们假设上完美的知识从时间0到T.我们制定公布的请求离线算法以及一组有竞争力基于在第4和第5的基准算法离线解决方案，我们在设计一个在线解决方案第6部分。

定义2多用户计算分区问题（MCPP）：lambda;,gamma;,,,和问题是要确定所有用户在该那个设备中（包括移动设备和云），以及在什么时间执行每个模块的服务器，使得该用户的平均申请延迟被最小化。

我们制定MCPP作为一个混合整数线性编程（MILP）问题。在这个公式中，我们定义一个连续变量和三个显示0-1的离散变量，，，。请参考表1为它们的含义。=1，如果模块（i，j）是在机器k执行，否则=0。注意，表示在服务器云一侧，且k =0表示的移动设备。=1，如果两个独立模块，和，在不同的两侧执行，否则=0如果这两个模块都在同一侧;=1如果模块执行先于模块，否则=0。我们还定义了一个积极的常数 IN是一样伟大为无穷大。在MILP 公式可以通过写等式（2）。

图.2. 多用户计算分区系统模型

约束（b）保证了时间顺序执行两个独立模块。 约束（c）表明，每个云服务器，只能一次处理一个模块。换句话说，如果两个模块都安排在同一台设备上，一个模块将不被启动，直到另一结束了。从和是两个辅助变量，约束（d）-（g）表明变量由和约束（H）-（I）决定的。表示的值决定于和。根据我们的系统模型，对输入数据应用的是来自移动设备，所以我们=1对所有的i的约束（k）。需要注意的是代表释放时间。因此，在约束（k）中我们有=。

3.4 MCPP的唯一性

我们比较MCPP 与传统作业调度问题并讨论他们之间的差异。

通过比较TSPSC ，类似MCPP 第一个类型问题是任务调度问题的异构计算（TSPSC）[14]。在这个问题中，应用程序是通过在一个有向非循环图（DAG）表示该节点表示应用程序的任务和边缘代表任务间的数据依赖关系。给定异构机环境，其中该机器具有不同的处理速度，以及数据传送机之间的速度不同，客观问题是要任务地图上的计算机和命令他们执行这样的任务优先级的要求得到满足，并且为了获得最小完成时间。该TSPHC 在一般情况下是处于NP-complete 状态，以及其他各种有效的启发性问题建议参考文献[14][21]。

直观地说，我们可以模拟我们作为类似的问题到MCPP 越好。在我们的问题

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

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