工程科学与技术，国际期刊20（2017）616完整文章基于ACO元启发式算法的云数据密集型应用虚拟机分配和数据放置优化T.P. Shabeera S.D.Madhu Kumar，Sameera M.Salam，K.穆拉利·克里希南计算机科学与工程系，国家技术学院卡利卡特，喀拉拉邦673601，印度阿提奇莱因福奥文章历史记录：2016年11月18日在线发布关键词：MapReduce云计算虚拟机虚拟机放置数据放置A B S T R A C T如今，用于处理大数据的数据密集型应用程序正在云中托管由于云环境为计算提供了虚拟化资源，并且数据密集型应用程序需要在计算节点之间进行通信，因此虚拟机（VM）的放置和数据的位置会影响整体计算时间。目前文献中报道的大多数研究工作都将放置数据和虚拟机的物理节点的选择视为独立的问题。本文提出了一种同时考虑虚拟机放置和数据放置的方法。主要目标是通过将所需数量的VM和数据放置在物理 上 更 接 近 的 物 理 机 （ PM ） 中 来 减 少 跨 网 络 流 量 和 带 宽 使 用 本 文 定 义 了 虚 拟 机 和 数 据 放 置 问 题（MinDistVMDataPlacement问题），并证明了该问题是NP-困难的。本文提出并评估了一种基于蚁群优化（ACO）的元启发式算法，该算法选择一组相邻的PM来放置数据和VM。数据分布在所选PM的物理存储设备根据每个PM的处理能力，在这些PM上放置一组VM来处理存储在其中的数据我们使用模拟来评估我们的算法。实验结果表明，该算法能够选择邻近的虚拟机，且在虚拟机上执行的任务数优于其他分配方案。©2016 Karabuk University. Elsevier B.V.的出版服务。这是CCBY-NC-ND许可证（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍云计算以按使用付费的方式按需提供高度可扩展的弹性服务。 如今，云计算的可接受性非常高，并且日益增加。从社交网络到传感器网络，云计算对我们的日常生活产生了重大影响。智能设备的广泛使用增加了云模型的使用。云数据中心的数量和规模正在迅速增长。基础架构和存储成本大幅降低，但带宽是当今云计算中最稀缺的资源之一思科全球云指数[1]预测，到2017年，与进出数据中心的数据相比，超过三分之二的数据中心流量将发生在云数据中心内的设备之间。思科全球云指数[2]预测，到2018年，超过四分之三（78%）的工作负载将被处理*通讯作者。电 子 邮 件 地 址 ： shabeera@gmail.com （ T.P. Shabeera ） ， madhu@nitc.ac.in（ S.D.Madhu Kumar ） ， shemi. gmail.com （ S.M.Salam ） ， kmurali@nitc.ac.in（K.Murali Krishnan）。由Karabuk大学负责进行同行审查只有22%将由传统数据中心处理。思科全球云指数[1]还预测，服务器虚拟化（在一台物理服务器上运行多个虚拟服务器在虚拟化环境中，可以通过有效地放置虚拟机（VM）来有效地管理云数据中心中可用的带宽云数据中心的主要目标是通过提高性能同时最小化成本来实现利润最大化[3]。通过有效地管理数据中心的带宽，云提供商可以提高性能，从而使利润最大化。设置和管理大数据管理基础设施与在云中托管相同基础设施相比成本更高MapReduce[4]由Google提出的Hadoop及其开源实现[5，6]是当今最流行的大数据管理框架。通过将大数据及其处理转移到云端，个人和企业可以专注于其他盈利想法。在当前可用的商业云中，数据存储在存储云中，并且计算通过计算云完成。Amazon Elastic MapReduce（Amazon EMR）就是一个例子。在Amazon EMR中，数据存储在Amazon Web Services（ AWS ） 数 据 存 储 中 ， 例 如 Amazon Simple Storage Service（Amazonhttp://dx.doi.org/10.1016/j.jestch.2016.11.0062215-0986/©2016 Karabuk University.出版社：Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。可在ScienceDirect上获得目录列表工程科学与技术国际期刊杂志主页：www.elsevier.com/locate/jestchT.P. Shabeera等人/工程科学与技术，国际期刊20（2017）616617S3）和Amazon DynamoDB。计算由Amazon Elastic Compute Cloud（Amazon EC2）实例执行这种情况的问题是，在开始执行之前，需要将数据从存储位置复制到必须开始计算的实例。根据传输数据的大小，这将需要时间。如果允许远程访问，而不是复制，对同一数据的多个请求可能会导致存储节点上的瓶颈。在MapReduce集群中，数据在执行期间在集群中的节点之间移动。在MapReduce云中，集群是用VM建立的，在执行时这些VM之间发生数据传输。MapReduce由Map和Reduce组成。执行Map的VM可能是独立的，但应移动这些VM中的数据到启动Reduce任务的VM在Join类任务的情况下，VM可能需要在其间传输数据在所有这些情况下，数据传输延迟随着距离的增加而增加距离可以根据网络延迟或跳数来定义。跳数是数据在源和目的地之间传递的中间设备的数量[8]。由于每一跳都增加了存储和转发以及其他延迟，因此源和目的地之间跳数的增加意味着更多的数据传输延迟。因此，在创建MapReduce集群时，集群应该由更接近的VM组成，这样可以最大限度地减少数据传输延迟，从而减少作业完成时间。云资源分配的主要缺点是过度配置。如果虚拟机没有被最佳地放置在物理机（PM）中，则将存在资源浪费，并且这些虚拟机将消耗更多带宽。目前的研究工作大多集中在能源效率和服务器利用率。但在MapReduce类应用程序的情况下，如果VM托管在远程PM中，数据传输时间将更多，带宽使用率将很高。针对云环境中数据密集型应用，提出了一种将虚拟机放置和数据放置相结合的资源分配算法。该算法采用流行的蚁群优化（ACO）元启发式。给定作为输入的VM和数据的数量，所提出的算法选择一组最小化数据传输延迟的PM。根据PM可以托管的VM数量，决定要复制到该特定服务器的数据块。将数据复制到相应服务器的物理存储中，并在该服务器上启动给定数量的VM。论文的其余部分组织如下：第二部分详细介绍了文献综述。第3节概述 了 系 统 架 构 的 概 述 。 第 4 节 描 述 了 这 个 问 题（MinDistVMDataPlacement问题），并表明这个问题是NP难的。第5节介绍了算法，第6节给出了实验评估。第七节是论文的结论。2. 文献综述MapReduce[4]是一个流行的编程框架，用于处理大量分布式数据。它主要包括两个功能，即Map和Reduce。计算是根据键/值对进行的。Map阶段需要一些键值对作为输入并产生中间键/值对。Reduce阶段采用中间键/值对并产生最终键/值对。在Map和Reduce阶段之间有一个shuffle阶段。Hadoop[5]是MapReduce的开源实现，具有用于存储数据的分布式 文 件 系 统 分 布 式 文 件 系 统 被 称 为 Hadoop 分 布 式 文 件 系 统（HDFS）[9]。Hadoop被广泛接受用于处理大数据。Hadoop集群中有两种类型的节点：存储数据的数据节点和执行计算的计算节点由于数据大小数据量巨大，计算量很小，目前的趋势是将计算移到数据的位置在HDFS中，大型数据被分割成固定大小的块，并分布在数据节点上。计算槽可以在相同的数据节点或不同的节点上启动。如果可能，调度程序会尝试在数据节点上调度Map任务。为了处理大数据，最终用户需要创建所需大小的Hadoop集群。一些用户可能需要它有些可能需要很长时间，但集群的大小可能会有所不同。在这种情况下，人们通常会创建最大所需大小的聚类。但大多数时间资源浪费将在那里。管理集群对于最终用户来说也是一项繁琐的任务。云计算提供基础设施、平台、软件等作为服务，以按需付费的模式提供给用户[10]。云计算的应用在包括铁路技术在内的各个领域显著提高了生产率并节省了成本[11]。在移动云计算中，卸载是一种流行的方法，其中所需的计算在云中远程进行。但是，何时卸载、节能作业调度、云内部的资源管理、选择适当的微云来卸载应用、选择关于低功率和低延迟的应用特定的微云是移动云计算的公开挑战[12]。云中的资源几乎是无限的，并且可以按需扩展。MapReduce云按需提供MapReduce集群。提供MapReduce作为云服务有不同的选择[7，13一个是为集群分配具有存储的VM。数据被上传到这个虚拟机，并由MapReduce处理，结果可以带回给用户或存储到存储云。第二种选择是将数据存储在存储云中，并为MapReduce集群分配一组VM。在开始处理之前，将来自存储云的数据复制到VM，并且将结果存储回存储云。在第三个选项中，为MapReduce集群选择一组PM数据存储在服务器的物理存储中，并根据其容量在这些PM上启动一组VM。数据由VM处理，结果存储回物理存储介质。与前两个方案相比，最后一个方案有许多优点。在第一个选项中，如果VM被删除，所有内容都将丢失。在第二个选项中，在将数据复制到VM时存在延迟。这种延迟取决于数据的大小文献中发现的大多数研究工作分别考虑数据放置和VM放置VM放置（将VM放置在PM上）是一个广泛研究的主题。这些研究的主要目的是整合服务器上的虚拟机，以提高能效和服务器利用率[17Ahmad等人[24]分析了云数据中心的VM迁移和不同的VM整合框架但在MapReduce之类的应用程序中，如果VM托管在远程PM中，数据传输时间将更多，带宽使用率将很高[25]。在IaaS云的资源管理调查中，Manvi和Shyam[26]观察到延迟，带宽开销，计算开销，可靠性，安全性和体验质量等性能指标必须考虑在内-在设计资源管理方案的同时。[27-31] 中提出的网络感知VM放置算法参考文献[14，32但是作者假设数据已经分布在存储云中，并且这些工作优化了关于数据位置的VM放置。参考文献[13，16，38]考虑数据和VM放置。Cura[15]为MapReduce集群分配预集群的VM。但这里的问题是资源的过度配置。具有完全相同数量虚拟机的群集可能不可用618T.P. 沙贝拉 其他/工程 科学和 技术，国际 期刊20（2017）616所有的时间.这种过度供应可能导致其他一些请求的饥饿Alicherry和Lakshman[32]提出了分布式云中的资源分配算法在这里，作者也只考虑VM的分配他们提出了将虚拟机放置在更近的数据中心的近似算法Alicherry和Lakshman[14]提出了在云环境中放置VM的算法，优化了数据访问权限。数据的位置已经是可用的，并且它们试图最小化VM间距离和VM-数据节点距离。但是如果不优化数据放置，仅优化VM放置可能不会得到好的结果。[36]解决了能源效率和网络负载最小化问题。作者提出了应用程序感知的工作负载整合算法，分别考虑能源效率和网络负载最小化以及一起。但在这些算法中，作者考虑了一个具有初始布局的云环境，并试图通过迁移来优化虚拟机的布局，以实现能量效率和网络负载最小化。作者考虑了相互依赖的虚拟机，并试图合并成一个PM，最大限度地减少能源利用。但在提供数据密集型应用程序即服务的云环境中，VM迁移会导致额外的开销。创建MapReduce群集所需的VM数量可能无法整合在一台物理服务器上。He等人[39]通过将虚拟机视为可模制的来解决虚拟机整合以节省能源的问题可塑造的虚拟机可以在整合过程中更改其资源容量，而不会危及QoS。与刚性虚拟机相比，可成型虚拟机可整合到更少数量的物理节点这里不考虑VM间通信和数据传输Shabeera和MadhuKumar[40]提出了在MapReduce云中分配VM的算法。他们提出了基于贪婪、随机和PAM的VM分配算法在所有这些情况下，没有考虑数据的放置。Di Martino等人[41]调查了云计算支持大数据的最新发展。这些作者还强调了与分布在多个基于云的数据中心的数据密集型应用程序的开发相关的挑战和早期结果。Remedy[37]是一种基于VM迁移的方法，用于数据中心中的网络感知VM管理具有网络感知功能的智能VM迁移可避免网络热点，而不会降低网络中其他流的网络性能迁移VM的目标主机根据迁移成本进行排名，迁移成本根据迁移期间生成的额外网络流量、迁移可用带宽和迁移后的结果带宽进行建模。Purlieus[13] 通 过 将 数 据 放 置 与 虚 拟 机 放 置 相 结 合 来 提 高MapReduce云中的数据本地性。它们将数据存储在MapReduce集群的物理存储上，计算VM在相同或附近的物理服务器上启动。这里没有提到物理节点的初始选择。Purlieus主要集中在Map和Reduce调度部分，而不是节点的初始选择。他们假设PM通过局域网相互连接。但在云环境中，由于其高度分布性，节点的最优选择本身就是一个NP难题。CAM[16]通过考虑存储利用率、变化的CPU负载和网络链路容量，对数据和VM放置使用最小成本流模型。这种方法同时考虑VM迁移和延迟调度。但是这两种技术给系统增加了额外的开销。耦合放置顾问（CPA）[38]是一个用于在数据中心中耦合放置应用程序存储和计算的框架。在这种方法中，数据和计算是基于计算节点和存储节点的邻近性和亲和性关系来放置的。大数据分析的输入数据由TB或PB级数据组成。为了处理这些，需要许多VM。因此，为了提高数据局部性，输入数据需要多个PM来存储它们的数据，这取决于它可以容纳的VM数量。数据密集型应用程序的执行时间取决于群集中VM之间的数据传输延迟。因此，资源的分配应尽量减少虚拟机和它们正在处理的数据之间的距离（网络延迟或跳数），以缩短作业完成时间。3. 系统架构分布式云由分布在世界各地的多个数据中心组成。每个数据中心由不同类型的服务器机架组成。这些服务器被虚拟化以提高资源利用率。处理由虚拟机完成，虚拟机的类型和数量根据作业的性质和数据大小决定。除此之外，对于数据密集型应用，数据存储要求该云的用户通过提交数据和要对数据执行的作业来从服务提供商与使用单独的存储云和计算云的传统服务器是虚拟化的，这些虚拟机构成了计算云的集群数据基于服务器的VM分配能力分布在服务器的物理存储设备 图 1说明了本文讨论的云场景。在这个体系结构中，第一个阶段是概要分析阶段。当一个作业被提交时，它会经历分析阶段[42]。此阶段分析作业和数据，并决定要分配的VM类型和群集大小（VM数量），以处理输入数据的作业。由于我们的系统目前考虑同构VM，因此分析器输出所需的VM数量。Star-fish[43]是一个创建分析器的开源工具。根据群集大小，必须将VM放置在PM中。下一个阶段是从可用资源池中选择PM。这个阶段就是资源分配阶段。此阶段选择可以容纳所需数量的VM的PM更新可用资源池然后，根据VM分配容量将数据复制到PM的存储位置，并在VM上启动作业作业完成后，将结果发送回用户。在由多个数据中心组成的云环境中，在分配VM时，分配可能跨越相距甚远的不同数据中心上的PM因此，在资源分配时，必须选择PM，使得VM分配容量的总和至少是VM的所需需求，并且它们在物理上更接近。本文阐述了这个问题，找到相邻的PM，可以容纳所需数量的虚拟机，并提出了一种算法，同样，也提高了作业完成时间。4. 问题描述和硬度考虑分布式云环境，其中云数据中心由具有足够存储容量和预定义数量的VM的PM机架组成PM之间的距离表示访问延迟或跳数，假设其较早已知。两个PM之间的距离是通过测量它们之间的网络设备数量来计算的。我们认为PM之间的距离为交换机的处理延迟 * 它们之间的交换机数量。例如，如果两个PM在同一机架中，则存在连接PM的ToR交换机。因此，该距离将是该ToR开关的处理延迟。如果PM位于两个不同的机架中，则会有两个ToR交换机T.P. Shabeera等人/工程科学与技术，国际期刊20（2017）616619PPPð 2019-04-25XX¼ðÞN1/1我 我2;1/1我我XFig. 1. 系统架构。以及一个或多个更高级别的交换机，这取决于底层云网络架构。云服务提供商使用的资源分配算法对应用程序的性能以及云服务提供商的利润和资源利用率有很大的影响。在我们考虑过的MapReduce即服务云架构中，资源分配阶段根据VM托管容量选择一组PM此阶段的输入是所需的VM数量在选择PM之后，将输入数据存储在PM的物理存储设备这些数据由放置在相应PM上的VM处理这些VM可以在处理数据时彼此交互。因此，资源分配器应该选择减少跨网络流量和访问延迟的PM。本 文 给 出 了 用 于 放 置 数 据 和 虚 拟 机 的 PM 选 择 问 题（MinDistVMDataPlacement problem）的形式化定义，并证明了其困难性。4.1. MinDistVMDataPlacement问题给定P;N;d;k，其中P^f1; 2; 3;. ng是PM的集合，Nini表示第i个PM可以容纳的VM的数量，dijP0定义PMi和PMj之间的距离（假设对于所有i都是dii0），并且需求kP1，MinDistVMDataPlace问题是挑选子集P0P，使得i2P0niPk，给定一溶液到这问题xω2 f 0; 1 gn;Opt G i：x i1表示拾取的节点，并将其称为最佳解决方案。请注意，这个问题不同于加权团问题及其变体[44]。下一节通过最小背包问题的简化证明了问题的4.2. 从最小背包问题到MinDistVMDataPlacement问题的本 节 显 示 MinKnapsack[45] 可 以 在 多 项 式 时 间 内 简 化 为MinDistVMDataPlacement。众所周知，背包问题是NP完全问题[44]。因此，MinDistVMDataPlacement问题是NP难的[46]。定义1.最小背包实例I<$n;N;S;k由n个项目组成，{1; 2. ;n}，其中N为整数值P0，大小为S为整数值S i P0;16i6n和需求k。 问题是要找到Tf 1; 2;. ;ng，其最小化在T中选择的项的和，所述项经受j2Tn jP k [47]。最小背包问题的公式是：Xfi;jg<$P0dij最小。这个问题可以重新表述为：给定正整数k和a加权完全图G∈V;E;N;d∈ N，其中V∈ f1; 2;...ngsuch受尽量减少1/1我是我ð2Þ该顶点i表示PM i，每个i 2 V与表示PM i中的VM的可用数量的值dij相关联，每个边dij;j与权重dij相关联，即，d：V×V！R[f0g，theMinDistVMDataPlacement Problem转换为查找UV，n n：xPk;xi2 f0; 1g 16i6n的符号，选择性碘化丙啶i：x i<$1 g为一给定溶液P i Un iPk和Pi jUd ij是最小值。yω2 f0; 1gn表示所挑选的项目，这被称为最佳选择。malsolutionnn最小化dij xi xj联系我们受Xn nxPk;x2f0;1g16i6nð1Þ4.2.1. 减少给定MinKnapsack问题的一个实例，In;N;S;k，其中。N：F1... ng！ N [f 0 g，使得Nin i，S：f1.ng！ R [f 0 g，使得Sis i，nMinDistVMDataPlacement问题的公式是：620T.P. 沙贝拉 其他/工程 科学和 技术，国际 期刊20（2017）616<$fg <$fgP001-2000德国20ðÞP PPð Þþp是最小值。uu2X0电子邮件：info@martina.com萨夫格FGFG[f]FG1/1ð Þ ðþ Þi 2 Op t00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000Pj2Op tIsj。 则Pi2Op tIiPj2 fn1;n2;.. . ;2ngsjij0否则< Pi Opt Isi Pjn 1N 22nsj。这与假设相G的需求被设置为nM k。下面的引理是选择需求值nM_k的直接结果。引理1.G中的需求nMk不能被满足，直到所有节点fn1;n 2;. ; 2 ng被拾取。下面的定理建立了OptI和OptG之间的精确对应。定理1. 选项G选项In1;n2.; 2n，哪里这个联盟是分裂。证据1.通过引理1，选项G 应包含N1;n2.;2n.这些元件供应nM.然后到满足需求nMPk;OptPk应包含X0PkX，使得Pu2X0nuPk和表1MinKnapsack实例。项目大小值130721083204450652056405因此，选择权G选择权I选择权[fn nn n1;nnn n 2;... ;2ng.推论1.1。S1; 2;... ;n是MinKnapsack问题的最优解当且仅当Sn1; n2;.;2 n是MinDistVMDataPlacement问题的最优解。推论1.2. MinDistVMDataPlacement问题是NP难问题。证 据 2.MinKnapsack 问 题 是 多 项 式 时 间 可 约 化 的MinDistVMDataPlacement问题。已知MinKnapsack问题是NP-完全问题。因此，MinDistVMDataPlacement问题是NP难的。4.2.2. 例如考虑一个Minknapsack实例，其中包含项目1，2，3，4，5，6.它们的值和尺寸如表1所示。要求= 20。一个恐惧-对于给定的例子，可能的解是f1; 2; 5g。构造一个完全图与顶点{X1;X2;X3;X4;X5;X6;Y1;Y2;Y3;Y4;Y5;Y6}将项目i的值分配给顶点Xi，将M1/436分配给Yi16i6n。需求nM k为236。图2中示出了所得到的曲线图 。 在 此 图 形 上 应 用 MinDistVMDataPlacement 。 最 优 解X1;X2;X5;Y1;Y2;Y3;Y4;Y5;Y6与成本= 60。Minimum KnapSack中对应的项为1; 2; 5。这是最小背包的最佳解决方案。图二. 将MinKnapsack简化为MinDistVMDataPlacement。T.P. Shabeera等人/工程科学与技术，国际期刊20（2017）616621×4.3. 如何解决MinDistVMDataPlacement问题？我 们 已 经 证 明 了 MinDistVMDataPlacement 是 NP 难 的 。MinDistVMDataPlacement是一个子集选择问题，对于大型数据中心来说在计算上是不可行的。子集选择问题是从一组初始对象中寻找可行的对象子集的问题。启发式算法是解决此类问题的一种选择。启发式方法找到“蚁群优化（ACO）元启发式算法已成功用于解决子集选择问题，如最大团，多维背包，最大布尔可满足性，最大约束满足，最小顶点覆盖，边加权k-基数树等[48]。Brugger等人[49]证明了蚁群算法在处理大型问题时优于遗传算法。根据Solnon等人的研究[48，50]，对于子集选择问题，ACO优于遗传算法、禁忌搜索、模拟退火在下一节中，我们提出了基于蚁群算法的选择PM的子集来放置VM和数据，考虑PM之间的距离之和5. 求解MinDistVMDataPlacement问题如第2节所述，文献中的大多数作品都将VM放置和数据放置视为单独的问题。实际上，在数据密集型应用中，数据和虚拟机的位置都会影响数据处理时间。分配用于处理数据的虚拟机应靠近数据。在这里，我们考虑了具有分布在多个数据中心的物理服务器机架的云环境。这些服务器同时充当数据节点和计算节点。假设这些服务器具有足够的存储容量和固定的VM放置容量。数据存储在服务器的物理存储空间中，并且服务器上的VM对相应的数据执行计算。给定VM和数据的数量，将为群集选择物理上更接近的PM集合。将云环境映射到加权完全图，其中顶点表示PM，并且顶点上的权重表示PM的VM放置容量。边缘上的权重表示对应PM之间的距离。必须选择PM的子集，使得所选顶点的权重之和至少等于所需需求，并且所选顶点之间的边权重之和最小。上一节证明了这个问题是NP-Hard的。这一秒-提出了一种算法来选择一组相邻的PM，使VM放置容量的总和等于所需的VM数量。蚁群优化（ACO）元进化算法[51，52]适用于求解VM和数据云环境中的布局问题。在选择之后在物理服务器中，数据被复制到服务器中，并且启动VM以对这些数据执行计算。算法1给出了蚁群优化算法的伪代码。在MinDistVMDataPlacement问题中，顶点的期望值不是独立的.顶点的选择取决于已选择顶点的子集因此，算法1遵循非对称信息素策略[48]。在集团信息素策略中，信息素值与每对顶点相关联。边上的信息素的量表示在相同的顶点内选择顶点Vi和Vj两者的学习到的合意性。溶液信息素成分存储在一个n矩阵中，其中n是顶点的数量。一组蚂蚁尝试建立基于这些信息素值的解决方案。具有更多信息素值的路径具有更大的选择概率。在每个解决方案构建阶段之后，信息素值被更新。这些蚂蚁构建的最佳解决方案被全局保存。此过程重复固定次数。该算法的输入● PM组（P）● 虚拟机需求（vmdmnd）● 距离矩阵（D）622T.P. 沙贝拉 其他/工程 科学和 技术，国际 期刊20（2017）616DJ JJ j ω J JJ J2j;半]和一组ACO特定参数● a：决定信息素因子重要性的参数（s因子）● q：信息素持续率● smin：February 2009● smax：最大信息素踪迹● nbAnts：蚂蚁● 的否 循环：循环次数最初，与每个边i，j，j，j相关联的信息素踪迹将是wi，j，其中wi和wj分别是顶点i和j的权重。IJ其中dij是顶点i和j之间的距离。最佳可行解和每个蚂蚁的解被初始化为空。PMSetk保持由antk选择的PM的集合。最初，它是空的，并逐渐添加顶点到集合的基础上的概率过渡规则。集中的第一个顶点是选定范围-多姆利。一个新的顶点v j 从基于以下的候选集中选择概率转移规则概率转移规则包含信息素因子（s因子），其取决于每对顶点上的信息素的和，使得Vi 是已经在PMSet中的顶点。特定节点v j的s因子被计算为：X启发式因子g基于蚂蚁到目前为止构建的解决方案来评估对象的承诺这对于信息素策略是有用的但我们遵循的是集团信息素策略。在集团信息素策略中，信息素值与每对对象相关联，而不是与每个对象相关联。在该算法中不考虑启发式因子，因为已经发现对于团信息素策略，最好不使用启发式因子[48，54]。该算法的计算成本分析如下。5.1.计算成本算法中的蚂蚁数量为nbAnts，每个蚂蚁构建解决方案。如果主机的数量由P表示，则距离矩阵的大小将为P P。在解构建过程中，创建信息素踪迹矩阵，其也具有jPj ω jPj的大小。第3-39行算法1的第3每个蚂蚁的候选集合是PM的集合，所以第12行到第20行的while循环最多执行P次。这个while循环对每个蚂蚁重复。因此，第6第28s因子vj;PMSetk¼vi2PMSetksvj;vi：4信息素更新期信息素更新阶段OjPj ω jPj时间。因此，算法来自具有最高概率的候选集合的顶点被添加到PMSet，直到它们的权重之和变得至少等于所需需求（vmdmnd）。用于将顶点pi选择到由PMSetk表示的蚂蚁k的集合中的概率函数为是O个循环的个数，其中n是{{nbAnts}{nbAnts}{ω j}Pj}{nbAnts}{ω j}Pj}。因为jPjnbAnt s，所以这是Ono个周期ωjPjωjPj <$，也就是O<$jPj<$。该算法的时间复杂度为O P2，因此计算成本主要取决于云中的主机数量。pp PMSet1/2sfactorpi;PMSe tk]a一ð5Þ6. 实验评价与讨论Impj2候选人k1/2s因子[Pi;PMSetk]在MapReduce集群中，数据传输发生在不同的作业执行阶段我们已经进行了实验，其中P0是控制s影响的ACO特定参数。a决定了多样化。降低a的价值强调多样化。所以必须选择a这取决于解决问题的可用时间。当量5找到候选集合中每个顶点的概率，并且具有最高概率的一个将被选择用于包括在集合中。每个蚂蚁都是这样构建解决方案的。在此阶段之后，如果找到比全局最佳解决方案更好的解决方案，则全局最佳解决方案将使用此新集合进行更新。算法1中的下一阶段是信息素更新。根据以下等式更新信息素值以用于后续迭代spi;pj1/4spi;pj ： 1-q1/4dspi;j;fPMSet1...;PMSetnbAntsgiven6个月其中q是信息素蒸发速率。信息素蒸发用于降低信息素值。信息素蒸发的目的是避免信息素值的无限制增加，并允许蚁群忘记之前做的糟糕选择[53]。增加q值也通过使信息素蒸发缓慢来强调多样化。因此，就像a一样，q的值也必须根据解决优化问题的时间可用性来选择。Phero-mone trail被限制在smin;smax内，以避免所有蚂蚁一次又一次地构造相同的解决方案而没有找到任何更好的解决方案的情况。在下一次迭代中，蚂蚁基于这个新的信息素值构建解决方案。该过程根据作为输入给出的循环的数量来迭代。但是在每次迭代中，每当从候选集合中选择顶点时，顶点的权重与需求vmdmnd一致。如果它至少等于vmdmnd，则返回单个顶点作为解决方案。研究分配的VM之间的距离对作业完成时间的作用虚拟机之间的距离实际上取决于网络设备的数量、处理延迟以及它们之间链路的带宽如果有n个VM，则将每对VM之间的更高的总距离意味着当在VM之间通信时，涉及更多数量的更高级别的交换机，并且这导致更高级别的交换机中的拥塞和作业完成时间的延迟两个VM之间的距离是托管两个VM的PM之间的基础网络延迟和带宽如果VM位于同一PM上，则它们的距离为零。否则，距离取决于托管VM的PM之间的交换机和链路为了研究VM之间的距离对作业完成时间的作用，使用VM创建了三个Hadoop集群。每个群集有四个VM。每个群集由在IBMSystem 3100 M4中创建的虚拟机组成，该虚拟机具有Intel XeonE3-1220处理器、16 GB RAM和1 TB硬盘，虚拟机的配置为2 GBRAM、2个核心和20 GB磁盘。如果VM在更近的PM中，则可以最小化网络延迟和数据传输成本。如果VM处于相同PM，则VM之间的延迟可以忽略，并且这些VM之间的距离可以取为零。可能需要较少数量的VM，可以在单个PM上容纳。可以放置在PM中的VM数量取决于其配置和要放置的所需VM的配置。例如，如果服务器的配置为32核、512 GB RAM和16 TB磁盘，而VM配置为2 GB RAM、2核和128 GB磁盘，则可以在此服务器中放置16个VM如果请求10个VM，则可以在此单个服务器中创建10个VM的群集在这种情况下，数据传输延迟可以忽略不计。如果PM的配置是16核、15 GBRAM、2 TB硬盘T.P. Shabeera等人/工程科学与技术，国际期刊20（2017）616623虚拟机的配置是2核，4 GB RAM和100 GB磁盘。这里，尽管PM具有16个核，但是PM最多可以放置5个VM，因为RAM大小是16 GB。因此，如果客户端需要的VM数量超过单个PM的VM放置容量，则无法将其放置在该PM中，并且需要多个PM。在这种情况下（如果需求大于单个PM），必须选择PM使得它们彼此靠近。虚拟机之间的数据传输所需的时间取决于交换机和链路的数量及其延迟。为了研究虚拟机的接近程度对作业完成时间的影响，我们创建了三个集群。在群集1中，所有VM都在单个PM中。对于群集2和3，每个PM仅部署一个VM，但它可以容纳更多VM。在群集2中，四个VM分布在机架中的4个PM上。在群集3中，选择驻留在四个不同机架上的四个PM来放置VM。两个基准MapReduce程序，即TeraSort和WordCount在这三个集群上执行。 图 3 b显示了TeraSort在这三个集群中使用1 GB和10 GB数据的执行时间。图3a示出了在具有1GB和10GB数据的这三个集群中WordCount的执行时间。从这些结果可以得出结论，如果VM在相同或附近的PM中，则可以减少作业完成时间。我 们 制 定 的 VM 和 数 据 放 置 的 问 题 ， 称 为MinDistVMDataPlacement，并提出了一种基于ACO元启发式算法。将蚁群算法与FFD算法和距离感知FFD算法进行了比较我们使用基于模拟的评估，比较所提出的元启发式算法与文献中现有的算法，即FFD和距离感知FFD的性能。这些算法已经在流行的云模拟平台CloudSim[55]中进行了模拟，并基于Benson等人给出的拓扑数据进行了评估[56]第50段。我们已经考虑了图4所示的数据中心拓扑。主机到交换机的链路为1 GigE，交换机之间的链路为10 GigE。我们假设所有交换机的延迟都是一致的。我们通过添加机架的概念扩展了CloudSim[55]不是将主机直接添加到数据中心，而是将多个机架添加到数据中心并将主机分配给机架。因此，每台主机都有机架ID和数据中心ID。FFD和距离感知FFD都是贪婪方法。这两个算法按照虚拟机分配容量的降序对主机进行排序。FFD从排序列表中选择主机，直到它们的权重之和至少等于所需的VM数量。FFD不知道拓扑。距离感知FFD是FFD的修改版本。距离感知FFD从排序列表中选择第一个主机，并根据与已选主机的距离添加其余主机，直到满足所需需求。这是一种拓扑感知贪婪方法。三个输入数据集给这些算法。第一个是UnivCloud，基于大学数据中心拓扑（Univ1）。Uni- vCloud由18个机架组成。每个机架由40台服务器组成。总共有720台服务器第二个数据集基于私有数据中心拓扑（Prvt1），我们将其命名为PrvtCloud。PrvtCloud由两个DC组成，每个DC有25个机架，每个机架由40台服务器组成。PrvtCloud中有2000台服务器第三个数据集是MultiDCCloud，由10个DC组成，每个DC有25个机架。有些机架
