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

移动云系统中的成本感知服务放置和负载调度

摘要：

随着智能手机的激增和越来越多的云服务，用户在移动设备端请求云服务是很普通的一件事。从互联网数据中心直接获取数据会导致极高的延迟，由于长的往返时延（RTT）和广域网的可能的拥塞。为了降低时延，一些研究者提出把服务缓存在边缘云或者是在更接近于终端用户而不是互联网云的智能路由器上。尽管缓存是一个理想的技术，但是，最小化用户获取延迟和服务提供商的成本来放置服务和调度用户的需求不会很远了。在这片论文中，我们研究了在移动云系统中的服务部署和负载调度的联合优化。我们认为这个问题对传统的移动网络的缓存问题和内容分布式网络的内容分配是独特的。我们为服务提供商开发了一系列有效的算法来达到在移动用户要求的平均延迟的协定，和服务提供商的成本。我们的解决方案使用了用户移动模式和服务访问模式来预测用户未来的需求分布，之后基于这些预测来适应性在线进行的服务部署和负载调度。我们通过仿真实施了广泛的追踪。结果显示我们的解决方案不仅达到了比直接从远程云中获取服务更低的延迟，也在延迟、成本和算法运行时间上胜过其他的经典的基准算法。

关键词：

移动云计算，服务放置，负载调度

1 介绍

在移动生态系统中云服务的应用使一个新兴的移动计算范例成为可能，也就是移动云计算（MCC），在典型的MCC系统模型中，移动用户直接与互联网上的中央云相接。但是，由于长的往返时延和广域网中可能的拥塞，MCC模型使服务直接从中央互联网数据中心获取的同时也造成了极高的延迟。这种延迟可能会符合一些应用程序的要求，例如网页浏览，但是对延迟敏感的应用程序会产生不好的用户体验，比如说高质量视频流，手机游戏，增强现实等等。

为了解决这个问题，一些研究员提议在终端设备和传统的网络数据中心之间加入另一个命名为微云或者是雾云的抽象层，这个抽象层提供计算、存储和网络资源，使得云更接近于移动用户。部署微云的可能地方是无线接入网络。微云能够被固定在于无线接入网络相连的基础设施上，或者是无线接入网络中的增强型的路由器和交换机上。移动用户通过低延迟的wlan和3G/4G网络与微云相连。尽管将云服务缓存在中间的微云层仍然是一个预期的降低服务访问延迟的技术，但是怎样在微云上放置服务和调度用户的需求负载已经可以被研究了。

考虑到移动服务发展的很快和微云在无线接入网络中的广泛部署，我们首要的目标是帮助服务提供商最小化服务移动用户从微云的要求负载时的访问延迟。同时，我们也会降低服务提供商的成本，这些成本包括微云上的资源使用和在微云上更新服务放置的成本。下面来解释这些目标：

• 最小化延迟 用户感知延迟是最重要的标准，考虑到微云的地理分布，从不同的微云和从互联网云上请求服务有不同的延迟。我们的目标是最小化所有用户请求负载的平均延迟。
• 最小化微云上的资源利用 通常应用提供商需要从微云提供商那购买资源来在微云上缓存服务。从服务提供商的角度来看，我们致力于使用最低的微云资源来使移动用户获得最好的应用性能。
• 最小化服务放置转换 我们把服务放置转换定义为位置随时间的改变。随时间的放置转换需要服务的相关数据在微云和云之间的传送。为了降低数据传送成本，我们需要限制服务放置转换。

重要的是，我们发现在一个复杂的决策过程中只最优化一个因素不能满足提供商的要求，需要的是一种权衡访问延迟、资源利用和服务放置转换三者的方法。

这是一个困难的问题。尽管微云上服务放置和负载均衡可以在两个独立的进程中分别被最优化，但是最好的决策要求负载均衡和服务放置的复杂的联合优化。此外，由于用户的移动性，请求负载可能在空间和时间领域频繁显著的变化。高度动态的请求负载意味着定期地更新决策是必须的，记住当前的性能和可承受的成本和预期的未来负载。这些内在的复杂性在最近的工作中没有被定位，这些工作只是分别优化了服务放置和负载均衡两者之一[10], [11], [12], [16], [17], [18], [19]，或者在传统的数据中心工作负荷上而不是在高度动态的移动工作负荷上来研究联合的最优化[8], [9], [22], [23]。

在此篇论文中，我们研究了移动云系统中服务放置和负载均衡的联合最优化问题，尤其是在高度动态的移动工作负荷条件下。我们的主要贡献如下：

• 就我们所知，这个工作是第一个研究移动云系统中的服务放置和负载均衡的工作。我们首先规范了拍快照问题，命名为基本服务放置问题（BSPP），这个问题目的是在微云容量限制的条件下最优化访问延迟。我们发现BSPP问题很难解决，它对一些经典问题来说是唯一的，例如设施定位（FLP）、移动计算中的数据缓存和内容分布式网络（CDNs）。
• 然后，我们为BSPP设计一个有竞争力的启发式算法，它在访问延迟和算法运行时间方面明显优于一组基准算法。
• 我们进一步将BSPP扩展到一个更实用的模型，目的是从服务提供商的角度优化访问延迟，资源利用和服务放置转换之间的平衡。 我们为这个模型开发了一个在线算法，可以直接在实际系统中部署。
• 我们使用真实世界的城市交通数据集和Youtube数据集来评估我们的在线算法。 结果表明，在线算法在访问延迟和服务提供商成本两方面都能达到很好的性能。

2 系统模型和问题公式化

2.1 术语

我们考虑了一个典型的移动云系统，包含是哪个层次：云、微云和移动设备。移动用户通过低延迟高带宽的无线局域网（WLAN）和微云相连。为了方便描述，首先解释被用在整篇论文中的下列术语。

• 云与微云 云是指互联网上的集中式数据中心，而微云是在云和终端用户之间地理分布的。该系统包括唯一的云和多个微云。我们也将云和微云命名为资源节点。
• 服务（或数据） 服务是由资源节点托管由移动用户请求的应用程序的抽象。它可以是视频流，社交游戏，导航，增强现实等。服务通常与数据相关联。在微云上放置服务需要在其上存储相关的数据。 因此，我们可以互换地使用术语服务和数据。
• 负载（或请求） 负载或请求是指请求服务的移动用户的数量。服务通常有不同的负载。服务的负载在地理上分布，随时间变化。
• 服务（或数据）放置 服务放置是决定对每个服务应该放置到哪一个微云上。每一个服务被允许放到多个微云上。所有的服务要提前被放在云上。
• 负载均衡 负载均衡是指在微云和云上分配负载。

2.2 基本服务放置问题

图1 BSPP的解释

图1说明了系统模型。我们考虑了一个部署了一组微云的二维区域，微云的数量是N，每个微云有一个覆盖区域或区域。假设二维区域完全被N个微云覆盖，而且微云的覆盖区域之间没有重叠。因此，我们可以将整个二维区域分为N个微云覆盖的N个区域。我们用i来索引区域，j来索引微云。 i和j满足i[1,N]、j[1,N]。假设服务提供商有一组K个服务要放置在微云上。k来索引每一个服务，1 k K。我们使用 来代表区域负载，表示区域i中请求服务k的用户数量。表1显示了本文中的数学符号。

我们定义了一个N(N 1)的矩阵[]来代表区域i到微云或者云j上的服务的负载延迟。为了方便起见，我们允许j=N 1，代表互联网上的云，而1 j N代表微云。注意[]是具有以下属性的常量：

i，在j=i的条件下，有最小值；而在j=N 1时，有最大值。这个属性表明用户请求的服务在附近的微云上的服务，延迟最低；如果用户请求在远处的微云上的服务，延迟会增加；最糟糕的情况是用户请求互联网云上的服务，此时延迟最大。

表1 本文中的数学表示

定义1 基本服务放置问题。考虑到来自每个区域的负载，问题是要为每个微云决定应该放置哪些服务，和为每个用户的请求决定应该调度和服务哪个微云，以使得所有请求的平均延迟最小化，同时满足每个微云的容量约束。

定义1描述了基本的服务放置问题，我们现在用公式(1)来公式化这个问题。这个问题有两类决策变量，第一个是一个二进制变量表示服务k是否被放置到微云j上，这里j[1,N]。第二个是一个连续变量表示区域负载被分配到由微云/云j服务的部分，这里j[1,N 1]；i，(0,1)， 。

接下来，我们对微云的容量约束进行建模。微云受它的存储和计算能力约束。由于存储有限，每个微云可以放置数量有限的服务。我们用表示服务k相关数据的大小，在微云上放置服务k需要 的存储资源。我们定义了一个常量矢量[]代表每一个微云j的存储容量。由于计算能力有限，每个微云能够服务有限数量的负载，因此，定义一个常量矢量[]代表每个微云j可以服务的最大负载。为了简单起见，我们假设服务一个请求需要的计算资源对于所有的服务是相同的，我们用下面的公式来公式化BSPP：

BSPP致力于最小化所有负载的平均延迟，公式(2)表明负载只能被均衡到有被请求的服务放置的微云上，公式(3)和(4)分别表示存储和计算能力的约束

2.3 成本感知服务放置问题

我们现在考虑一个更实际的问题，称为成本感知服务放置问题（CSPP）。在这个问题上，我们将服务提供商的成本考虑在内。它包括两部分：云和微云中的资源使用成本，以及随着时间的推移微云上的服务转换所引起的成本。服务提供商的成本和用户请求的平均延迟是两个相互冲突的目标。在微云上放置更多的服务副本可以降低负载的平均延迟，同时也增加了微云上的资源使用。CSPP旨在实现它们之间的最佳平衡。

• 资源使用成本 资源使用成本来源于微云上的存储和计算成本，以及云上的计算成本。为了简化问题，我们假设资源节点上每单位数据的存储成本是相同的。在资源节点上，各种服务的每个请求的计算成本是相同的。我们假设这些服务已经被提前放置于云上。 因此，总资源成本取决于微云上的服务放置。
• 随时间的服务放置转换成本 我们考虑时间维度，研究一定时期内来自多个地区的负载可能发生变化的服务放置。考虑到连续两个时间段服务放置转换所带来的额外成本。服务放置转换需要将与添加到微云上的服务相关的数据进行传输，传输会在云和微云之间或在微云中造成大量的带宽成本。因此，从应用提供商的角度来看，我们需要限制服务放置转换，以降低运营成本。

定义2 （成本感知服务放置问题）考虑到在一定时期内每个时间t的区域负载，问题是在每个时隙决定每个微云应该放置哪个服务，并且针对每个用户的请求决定调度哪个微云服务这个请求，使得整个周期的延迟，资源使用成本和服务放置转换成本的加权总和最小，同时满足每个微云的容量约束。

• 公式化CSPP 令t表示时隙，一个时隙的持续时间可以是几分钟到几个小时，这取决于区域负载随时间变化的频率。在现实世界的系统中，这个频率受二维区域微云的空间密度、移动用户的移动速度和用户服务访问模式的影响。我们将对这些因素如何影响负载变化建模，并且在第4部分中描述我们的负载预测方法，我们将时间指标t分配给问题(1)中的记号。例如， 表示在时间t时区域i请求服务k的负载数；和是在时间t时的决策变量。下面，我

  全文共25721字，剩余内容已隐藏，支付完成后下载完整资料

  ---

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

您可能感兴趣的文章

• 管理信息系统外文翻译资料
• 老年人的营养和营养需求外文翻译资料
• 试卷自动生成系统的设计与实现外文翻译资料
• JSP的技术发展历史外文翻译资料
• 微软.NET平台的介绍外文翻译资料
• 设置一个Servlet和JSP环境外文翻译资料
• Java Servlet外文翻译资料
• 基于递归神经网络的会议识别语言建模外文翻译资料
• 基于社区结构的推荐算法和用户的信任外文翻译资料
• 边缘路径绑定：一种不太模糊的边缘绑定方法外文翻译资料