英语原文共 8 页，剩余内容已隐藏，支付完成后下载完整资料
一种基于多适应度遗传算法的云计算资源调度策略
摘要：在IaaS（基础设施即服务）的云计算环境下，由于系统规模的扩大和虚拟机迁移等原因，很容易造成物理资源碎片化，资源利用率低等问题。 这些后果导致互联网数据中心内的高能耗。在本文中，我们提出基于三个负载维度的预迁移策略； CPU利用率，网络吞吐量，磁盘I / O速率，这些在算法中被认为是互补的。为了得到一个近似最优解，我们采用混合遗传算法结合具有多重适应性的背包问题，并进行实验验证算法的有效性。实验结果表明，该算法能够有效实现云计算环境下提高资源利用率，降低能耗的目标。
关键词：云计算；虚拟机；负载均衡；资源调度；遗传算法；实时迁移
- 绪论
如今，云计算已经成为一个非常有前途的行业。 在“基础设施即服务（IaaS）”的云计算环境下，用户虚拟机的需求是不同的，因此虚拟机显示的负载特性也不同。 一种非常常见的分类方法将计算机分为三类：CPU密集型，磁盘I / O密集型和网络密集型。 如果特定物理机上承载的所有虚拟机处于相同类别（例如CPU密集型），则它们将在CPU工作时隙上竞争，同时其他资源的利用率将非常低。 其结果是由于竞争导致服务质量不够高。 由于总体利用率低，一些资源也浪费了，因此能源面临着不必要的损失。
通常情况下，一台普通的300W服务器每年的能耗约为2628KWH，同时需要额外的748KWH的电能来制冷[1] [2]。 在云计算环境下，降低能源消耗和节约能源成本对互联网数据中心和云计算服务提供商来说意义重大。
为了解决上述问题，我们提出了一种负载互补算法，以最大限度地利用资源并潜在地降低能源成本。 在算法中，作为一个组成部分，我们也创新地采用了多适应度的遗传算法来考虑不同的方面。 传统上，在遗传算法中只考虑一个适应度值。 在本文中，我们考虑三个子适应值，这可以使结果更加灵活和精确。 通过这种算法和实时迁移相结合，资源利用率可以达到理想状态，从而可以节省一些额外的能源。
本文的主要贡献如下：
- 我们提出了一种新的云计算资源调度策略，可以显着提高Internet数据中心的资源利用率和节约能源。
- 我们使用三个特定的负载维度，而不是整体负载，以获得算法中的最佳布局方案。 细化的维度意味着该算法更深入到负载互补框架中。 当考虑到虚拟机在云中是异构的时候，这将得出更准确的结果。
- 此外，我们改进了长历史-遗传算法，使其与多重适应和背包问题同时关联。 这种改进会使算法更精确地计算，因此调度策略更加复杂和合理。
本文的其余部分安排如下。 我们在第2章回顾一些相关的工作。 在第3章中，我们将介绍系统模型并详细描述算法。 第四章描述实验并显示实验结果。 最后，在第5章中，我们总结本文并提出一些未来的工作。
- 相关工作
最近在学术和工业领域，云中的资源管理和调度一直是一个热门话题。 优化调度云中资源的问题对于大规模部署云非常重要。 良好的资源调度策略将显着提高资源利用率和节约能源成本。 相关论文的研究方法和渗透点各不相同，各有特点。
在文献[3]中，Luiz et.al. 提出了基于服务器的总体能耗提出负载均衡策略。文献[4]提出了基于网络吞吐量感知的虚拟机放置策略。本文和这些论文的区别在于，本文中我们没有考虑物理机器的整体负载，而是考虑三个更具体的负载尺寸。文献[5] [6]考虑了多价电力市场下服务器优化布局和节能问题。 由于本文专注于特定云环境中的资源调度，因此排除了这些外部因素。 但是在实际操作环境下，文献[5] [6]中的想法可以与本文结合起来进行更深入的资源调度。
与本文类似，文献[7]中提出了一种优化的调度算法，以实现云调度问题的优化或次优化。他们调查了以一种灵活的方式放置虚拟机的可能性，以在允许最大限度地利用资源的前提下提高寻找最佳分配的速度。文献[8]着眼于同样的问题，他们提出了一种新的云计算框架，而不是仅仅调度资源。在本文中，他们提出了一个新的框架，可在可扩展的云计算架构内提供高效的绿色增强功能。使用功耗感知调度技术，可变资源管理，实时迁移和最少的虚拟机设计，整个系统效率将在基于数据中心的云中大大提高，并且性能开销最小。与本文大致相似，文献[9]涉及资源利用率最大化问题，它还考虑了三个负载维度：存储，带宽和CPU周期。然而，文献[9]只关注P2P流媒体服务的数据中心，因此它只能用于很小的范围。相比之下，在本文中，我们并未预先对云数据中心的应用程序做出任何假设。
除了上述文件外，还考虑了各种不同的方法来解决云中的资源调度问题。在文献[10]中，采用了基于市场的资源分配方法。他们提出了这样的市场机制，有效地为参与者分配服务。该机制使用户（1）能够订购用于工作流和共同分配的服务的组合，并且（2）在远期/现货市场中预留未来/当前服务。在其他一些论文中，重点是通过重新安排任务和工作流程来优化资源利用率。在文献[11]中，他们提出了一种基于粒子群优化（PSO）的启发式方法来调度云资源上的应用程序，该方法考虑了计算成本和数据传输成本。在文献[12]中，他们使用基于信用的调度决策来评估任务队列中的整个任务组，并且找到所有任务的最小完成时间，其中已经生成成本矩阵作为要被分配的任务的公平趋势资源。
以上研究是对全局负载均衡和能耗的研究。在本文中，我们将整体负载分为三个特定的负载维度。通过更具体地划分总体负载，该算法将获得关于虚拟机放置的更精确的结果。 此外，这些论文考虑了电力市场和网络拓扑等外部因素，这使得情况更加复杂。在本文中，我们只考虑云中的内部因素。虽然相关工作与本文相比具有相似的目标，但重点略有不同。 更纯净的内部实验环境将导致更少的干扰和更明显的迁移计划。
- 基于负载均衡的资源调度策略框架
- 系统模型
在这里，我们提出了一种基于多适应度遗传算法的云计算资源调度策略，主要目的是解决云内资源优化问题。为了验证算法的有效性，我们还提出了一个典型的云计算模型，这个模型很常见，与其他一些云计算环境很相似。参考一些已经实现的云管理系统，例如Eucalyptus [13]，一个典型的云计算拓扑如下面的描述，这也是我们实验中的原型系统模型。
有一个云管理器作为管理所有物理资源，存储系统等的云管理入口点。在每台物理机器上安装称为管理程序的虚拟化层，并在管理程序上创建所有虚拟机。在云管理器的边缘，提供了一些用户界面，用户可以通过界面访问底层资源。 本文提出了一种混合遗传算法（以下简称HGA），它作为云管理器中的一个独立模块。该调度策略模块定期执行，结果包含一组合理的虚拟机迁移方案。 结果可以用作管理员的参考，也可以直接用于自动迁移虚拟机。 概念拓扑如图1所示，其中PM表示物理机器，VM表示虚拟机：
图1 典型云计算环境的概念拓扑图
如图1所示，在云管理器下面放置几台物理机器，每台物理机器放置几台虚拟机。云管理器由网络模块，图像模块，认证模块等几个模块组成。HGA模块与这些模块并行并与它们结合以提供服务。上述模块由各种云管理系统实现，本文仅着重于HGA---a调度策略模块。 在此概念拓扑图中，并非所有物理机器和虚拟机都标出。标点符号#39;...#39;表示更多未识别的物理机器或虚拟机。
图2 资源调度策略的流程图
资源调度策略流程图如图2所示。首先，系统应该获取下一阶段所有虚拟机的负载信息和原始放置信息。然后执行HGA模块，这将在下面的章节中介绍。其次，HGA模块的结果应与原始放置信息进行比较，以确定结果是否足够满足。判断标准可以是将要节省的物理机器数量的阈值，或者如果利用率提高到某个水平等等。由于重点不同，门槛可能不同。最后，应该进行另一个判断，即判断迁移成本是否高于调度的收益。只有在迁移成本足够低的情况下才能实现迁移。但是，迁移成本高度依赖于硬件环境，这在本文中没有考虑到。
- 算法概述
该算法的基础是可以匹配和计算三个负载维度：CPU负载，网络吞吐量和一台特定物理机器上运行的所有虚拟机的磁盘I / O负载，以获得最佳迁移建议。因此，系统必须监控三个维度，这些维度将在执行算法时从监控数据库中提取。
该算法基于多适应度遗传算法实现。在该算法的设计中，采用了三个子适应度函数。 子适应度函数1表示虚拟机的负载互补。子适应度函数2表示迁移后物理机器的数量最小。 子适应度函数3表示需要迁移的虚拟机的数量是最小的。前两个子适应度函数的组合将保证最大限度地利用资源，而最后一个子适应度函数考虑偏移的成本。为了得到最优结果，如果采用枚举法，计算复杂度为O（nn）。因此采用概率搜索法，即遗传算法在可控时间内得到近似最优解。
为了消除遗传算法中大量的无效基因，我们采用集成在该算法中的内存容量部署贪婪算法。 因此，该算法本质上是一种结合贪心算法的混合遗传算法。 以下部分详细介绍了算法设计。
- 遗传算法设计框架
为了便于处理约束条件，我们假设CPU核心数量和内存总量之间存在一定比例。 例如，如果将物理内核设置为与2G内存对应，并且物理内核拥有两个虚拟内核，则具有8个物理内核的物理机可以容纳16个虚拟内核，因此总内存量固定为16G。这样，CPU和内存的约束条件可以降低到CPU或内存，其中之一。 在这个算法中，唯一的限制因素是内存的数量，也就是说，虚拟机的内存总和不能超过承载它们的物理机器的内存量。
在这种混合遗传算法中，采用符号编码进行染色体编码。对于物理机器，使用随机选择：1,2,3,hellip;m，每个数字表示物理机器，数字和物理机器是它们之间的一对一映射。虚拟机的编码稍有不同。为了与贪婪算法相结合，所有的虚拟机应该首先按照内存大小按降序排列。按此顺序，虚拟机可以精确地从1到n编码，而数字和虚拟机也是一对一的映射。此时，可以定义染色体。染色体可以被看作是一维数组，其长度等于虚拟机的数量。数组的每个下标代表虚拟机的代码，数组中的每个值代表物理机器的代码。例如，染色体的代码就像19871126，这意味着VM-0放置在PM-1上，放置在PM-9上的VM-1，...，放置在PM-6上的VM-7上，等等。因此，每个染色体代表一个迁移计划。混合遗传算法的处理是通过选择，交叉和变异程序在群体中产生最优个体。最优个体代表了最佳的虚拟机迁移方案。
该算法需要在特定时间根据历史监控数据获取平均CPU负载，网络吞吐量和磁盘I / O负载。 为了便于处理，三个维度被归一化。 获取平均值取决于隐含的假设，即历史载荷处于平衡状态，这意味着它很少遇到阵风的负载变化。 同时，该算法还需要在开始时获得原始的放置条件以便与结果进行比较。
算法1：算法流程
1. 生成初始人口P
2. 重复：
3. 对于每个在P中的个体i
4. 计算子适应值-1
5. 计算子适应值-2
6. 计算子适应值-3
7. 计算i的总体适应值
8. 将当前最好的个体直接留在后代人群中
9. 根据适应值对P进行选择功能
10. 对P进行交叉功能
11. 交叉后修改无效染色体
12. 对P进行突变功能
13. 修改突变后的无效染色体
14. 将人口P更新为新一代
15. 如果达到最大进化代数，转到16，否则转到2
16. 输出当前最佳个体作为最佳结果
在遗传算法的演化过程中，需要定义选择函数，交叉函数和变异函数。选择功能被定义为个体可能根据其适应值演进到下一代的可能性。适应度值由适应度函数计算得出，适应度函数来自三个子适应度函数。交叉函数随机选择一个单点交叉点，两个个体分别交换分段染色体。突变功能以非常小的概率随机突变染色体中的每个等位基因。突变的方式是将物理机器的代码随机替换为另一个代码。这意味着虚拟机被设置为放置在另一台物理机器上。将突变概率设置为小于0.01，以防止一些良好特征的个体由于冗余突变而受到损害。初始种群也是随机生成的，这意味着在算法开始时，每个虚拟机应该随机选择一台物理机器放置。算法的过程总结在算法1中。
在生成初始种群和随后的进化过程中，一个非常重要的过程就是修改无效染色体的操作[14]。由于内存大小的限制，上述程序可能会产生一些无效的染色体。当一个染色体的代码指示某个虚拟机放置在一台物理机器上时，这种情况就会发生，但虚拟机的内存大小总和超过了物理机器的内存限制。根据贪婪算法[15]的思想，考虑到虚拟机已经被列为减少内存大小，算法选择虚拟机作为内存大小按降序保持不变。达到内存大小限制时，
全文共14201字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[15146]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
