云计算中基于包簇映射的多目标蚁群资源分配算法

丁 顺，陈世平



云计算中基于包簇映射的多目标蚁群资源分配算法

丁 顺１，陈世平２

（1. 上海理工大学光电信息与计算机工程学院，上海 200093；2. 上海理工大学信息化办公室，上海 200093）

云计算环境中，虚拟机放置就是将虚拟机映射到物理机的过程，一个最优的放置策略对于提高计算效率和资源利用率是非常重要的。本文中将云计算环境下虚拟机放置问题作为多目标组合优化问题进行阐述，提出一种多目标蚁群优化方法，同时优化运营成本和资源浪费，并将其应用到包簇拓扑结构中，目标是有效地获得一组非支配解，同时最大限度地减少总资源浪费和营运成本。实验将该算法与现有的多目标遗传算法（MGA）和三种单目标算法进行比较。结果表明，本文所提出的算法比其它算法可以达到更优的效果，实现两个目标的折衷。

云计算；多目标优化；支配解；蚁群算法

0 引言

近年来，云计算逐渐成为一个流行的商业计算模型，它可以通过互联网来托管和交付服务[1]。云计算主要有三种类型：基础设施即服务（IaaS）、平台即服务（PaaS）和软件即服务（SaaS）。云计算平台的使用和部署有许多优点，例如可靠性、服务质量和健壮性[2]。对于消费者来说，云似乎是无限的，而且消费者可以购买到满足他们需求的计算力并且响应时间快。从提供者的角度来看，关键问题是通过最小化运营成本来最大化利润，在这个方面，云数据中心的电力管理就变得至关重要了，因为它影响了运营成本。此外，大规模计算机系统的能耗还引发了许多其它严峻的问题，包括二氧化碳和系统的可靠性。云计算的出现在过去的几年里对信息技术行业产生了巨大的影响，像亚马逊、谷歌、IBM、微软以及Oracle等大公司已经开始在世界各地建立新的托管云数据中心来提供冗余度以及确保在应用出错的情况下的可靠性。

云计算中的资源分配就是虚拟机映射到物理机的过程，目前大多数关于虚拟机放置的研究都集中在一个标准上，然而许多现实问题需要考虑多个标准。基于这个原因，最近的研究倾向于关注多目标的情况。因此，在本文中将云计算环境下虚拟机放置问题作为多目标组合优化问题进行阐述，提出一种多目标蚁群优化方法，同时优化运营成本和资源浪费，并将其应用到包簇拓扑结构中[3]，旨在为大规模数据中心处理提供一种有效的解决方案。通过实验对该算法的性能与多目标遗传算法（MGA）和三种单目标算法的性能进行了比较，结果表明该算法比其它算法有更好的效果。

1 研究基础

目前关于云计算资源调度的研究主要有：以提高资源利用率为目标的资源分配策略、以降低数据中心能耗为目标的资源分配策略以及基于经济学模型的资源调度。文献[4]通过监控虚拟机的状态，当虚拟机负载减少时降低处理器的速度来降低能耗。但提出的策略并没有建立能耗减少和应用性能的关系，降低能耗后可能会对应用性能造成不良的影响。文献[5]提出两级调度器：元调度器和虚拟机调度器，通过扩展Cloudsim类库实现启发式调度算法来提高云计算系统的资源利用率。文献[6]设计一个基于遗传基因的价格调节算法来处理市场的供需平衡，但该方法目前只考虑CPU资源，而对内存以及带宽等资源并没有涉及。文献[7]提出了云计算中虚拟机放置的自适应管理框架，提出了带应用服务级目标约束的虚拟机放置多目标优化遗传算法，用于制定框架中的虚拟机放置策略，但是没有考虑能耗问题，没有将资源控制和能耗控制结合起来。

目前云计算中虚拟机放置研究工作虽然取得一定的效果，但是还是存在一些问题。第一，大多数关于虚拟机放置的研究都集中在一个标准上，这样得到的最优放置也只是某一定条件的最优解，无法进行各准则下最优放置的相互比较，然而由于云计算环境的复杂性，单从一个方面的改进并不能很好的满足云资源调度的要求，许多现实问题需要考虑多个标准并进行权衡和折衷。第二，目前大多数调度算法的计算量很大并且缺少普遍性，从而造成用户的等待时间太长，用户满意度低。本文通过对营运成本和资源浪费两个目标的优化，将提出的多目标蚁群算法应用到包簇的拓扑结构中并且取得很好的效果。

1.1 多目标进化算法

多目标进化算法（MOEAs）是一种随机优化方法，通常是使用基于群体的方法去找到Pareto最优解[8]。大多数现有的MOEAs在选择的时候使用的是支配的概念，因此，我们只关注基于支配的MOEAs这一类问题。“支配”概念的定义如下，在不失一般性的情况下，用m个决策变量参数和n个目标函数来描述多目标最小化问题。

所有没被其它点支配的点都成为非支配点，通常情况下，在解空间中非支配点聚集在一起构成了一个面，并且它们经常被认为是代表一个非支配面。根据定义，在目标空间中，非支配面上的点不会被其它点所代替。因此它们是Pareto最优点（它们组成了Pareto最优面），相应的变量向量被称为Pareto最优解。

上面的概念还可以通过扩展去找到一个非支配解集。让我们假设一个解集中有N个解，每个解都有M个目标函数值，在我们接下来的工作中，使用以下步骤来找到非支配解集[11]。

1）初始化i=1

4）如果解集中的解遍历完，进入到步骤5，否则i加1，进入步骤2

5）所有未标记为支配解的都是非支配解

1.2 包簇分配模型

云计算数据中心传统资源管理方法以虚拟机为中心（VM-Centric）来设计资源分配模型，使用扁平、细颗粒度的资源分配方式。而这种细粒度的管理模型会导致所要解决的计算问题规模巨大，对虚拟机固定的资源分配也不利于资源共享。

为了突破这些限制，文献[3]提出一种包簇资源分配框架，通过分层的抽象模型来降解问题的规模。其中“包”为虚拟机或其他包的集合。这是个递归定义，一个大包可以是许多小包的集合，而这些小包可能是虚拟机的集合，也可能是更小包的集合。一个资源共享的虚拟机组合被模块化为需求包，而多个包又进一步被抽象称一个更高级别的包，进而由虚拟机与包构成一个层次化组织构架。“簇”为数据中心拓扑中位置相近的服务器或更低级别的簇的集合,簇所拥有的资源是其组成部分的资源之和。用包和簇来将虚拟机-服务器映射问题转换成一系列小得多的包-簇映射问题。

2 云计算资源的目标函数构建

2.1 营运成本

2.2 资源浪费

在云计算资源调度的过程中，与其它物理资源相比，主要的能源消耗是CPU和内存，因此在本文中，在提出的包簇映射算法中我们只关注CPU和内存这两种资源，并且如果需要，该算法也可以通过扩展去支持其它资源优化。由于每个簇（服务器）上的剩余资源可能会因为不同的包簇映射策略而不同。因此，为了充分利用多维资源，下面的公式用于计算调度过程中资源浪费的潜在成本。

其中约束如下：

3 多目标蚁群算法描述

蚁群优化算法是一个用于解决组合优化的分布式算法。该算法通过模拟蚂蚁的觅食过程完成调度。首先，蚂蚁随机选择一条路径，当这个蚂蚁达到预期目标时，它们计算这条路径的适应度，蚂蚁根据适应度在路径上设置信息素。最后，为了将蚂蚁集中到高适应度的路径上，并尽可能快的找到最优解，需要进行信息素更新和行为选择。

3.1 信息素定义

3.2 行为选择的转移概率

3.3 适应度函数

当一个蚂蚁经过所有的簇后就形成了一条路径，这条路径就是问题的可行解。为了确保解的质量，避免陷入局部最优状态，而是尽可能保证或得到的解释全局最优解，因此使用一个适应度函数来评价解的优劣性。在优化模型问题的基础上，需要对适应度函数进行定义。根据文中的调度优化模型，其中给出了两个调度目标并将成本最小化。因此公式8的适应度函数也就是评价函数。

3.4 信息素更新

如果路径的适应性很高，那么此路径的信息素就应该加强，从而让更多的蚂蚁找到这条路径。因此，有必要更新路径上每个点的信息素，更新规则如公式：

其中Q是一个常数，它的值被取为100。F(x)和B(x)的值越小，信息素的增量就越大。好的解会被信息素的更新而，同时差的解也会被信息素的更新而减弱。经过几次迭代后，越来越多的蚂蚁将趋向于最佳路径。信息素蒸发因子是用来防止获得到解只能达到局部最优。

3.5 算法流程

1）初始化包簇信息素、迭代系数、确定各个子目标函数权重。

2）蚂蚁开始循环，k++

3）随机散布若干只蚂蚁并建立搜索空间

4）计算每只蚂蚁移动到下一个节点的概率，蚂蚁根据计算结果移动到相应的节点上

5）当蚂蚁移动到新节点后，更新其经过路径的信息素，并对禁忌表进行相应的修改

6）重复执行3）~5），直到整个蚁群中的每个个体均找到一个可行路径为止

7）根据云计算资源调度问题的目标函数对所有可行路径进行评价，并选择当前最优路径

8）对所有路径上的信息素进行全局更新操作

9）迭代次数增加，如果迭代次数达到最大迭代次数，则停止搜索，得到云计算资源调度问题的最优解

3.6 实验结果与分析

为了验证本文所设计的蚁群优化算法的可行和有效性，本文采用 Cloudsim[12]平台来进行仿真，我们模拟了一个数据中心，它里面具有不同数量的异构服务器，每个服务器的处理器：1000、2000、3000 MIPS，内存：1T，RAM：8 GB。每个虚拟机对资源的要求为内存：1 GB，RAM:128 GB，CPU：250、500、750或1000 MIPS。在基于包簇的框架下，我们先对虚拟机逐层划分包结构，直到底层的虚拟机；同样的，也对服务器划分簇机构。我们用不同的参数对相同的输入进行多次测试，从而找到问题的最优参数。我们将α，β，ρ，迭代次数，蚂蚁个数分别设置为1，2，0.5，10，5。遗传算法的迭代次数也设置为10，种群的规模为200，Pareto分数为0.7，迁移时间间隔为20，迁移率为0.2。

我们使用降序首次适应算法（FFD）、动态电压调整（DVFS）、逻辑回归（LR）、蚁群算法（ACO）和遗传算法（GA）这五种算法分别测量了包簇映射的营运成本和资源浪费量。FFD算法是一种单目标算法，在该算法中，虚拟机根据请求的利用率进行排序，并将其放入到第一个具有足够资源的物理机中。DVFS是一种电功率管理技术，它通过切割设备的频率来最小化设备的能耗。从而使设备的性能保持稳定。在Cloudsim中，DVFS被用在一个功率感知数据中心，其中虚拟机被分配给第一个具有足够资源的服务器。LR方法通过对数据子集进行回归拟合来建立一个评估原始数据的曲线。为了通过另一种方法来评估我们的ACO多目标方法，我们在具有相同目标函数的Matlab Optimization工具箱中使用了GA。模拟结果的数值如表2所示，在这个表中，我们使用了不同数量的簇，多个包以及不同数量的任务。在运营成本、资源浪费率等方面，使用不同的虚拟机放置算法进行比较。

表1 基于包簇映射结果的比较

Tab.1 Comparison of results based on package cluster mapping

图1表示的是不同的算法在运营成本上的比较。由结果可知，FFD算法产生的成本最大，原因是虚拟机映射到第一个可用的服务器的排序机制没有考虑到其它服务器中可用的资源。图2中表示的是不同的算法在资源浪费上的比较。MACO算法尝试使用所有可用的簇来映射所有的包。结果表明，在所有的目标中MACO可以找到比MGA更好的解决方案。在30个簇、40个包、50个任务中，我们可得到FFD、DVFS、LR、MACO和MGA这四个算法的资源浪费率分别为40%、1.67%、3.33%、0%、21.66% 。在使用FFD的25个簇中，有40%的资源没有被利用，而对于使用MACO的12个簇中，所有的可用资源完全被利用。

图1 营运成本比较

图2 资源浪费比较

4 结语

针对云计算环境的复杂性，特别是云资源动态变化的不确定性，本文提出一种多目标集成的蚁群算法，算法从营运成本和资源浪费两个目标进行优化。通过与单目标和多目标算法进行比较，实验结果表明，该算法能够在使营运成本低、资源浪费少的情况下有效地进行资源调度，是一种可行的、有效的资源调度算法。下一步的工作是结合机器学习算法进一步优化。

[1] Randles M, Lamb D, Odat E, et al. Distributed redundancy and robustness in complex systems[J]. Journal of Computer & System Sciences, 2011, 77(2): 293-304.

[2] 卢浩洋, 陈世平. 基于包簇映射的云计算资源分配框架[J]. 计算机应用, 2016, 36(10): 2704-2709.

[3] Laszewski G V, Wang L, Younge A J, et al. Power-aware scheduling of virtual machines in DVFS-enabled clusters[C]// IEEE International Conference on CLUSTER Computing and Workshops. IEEE, 2009: 1-10.

[4] Jeyarani R, Ram R V, Nagaveni N. Design and Implementation of an Efficient Two-Level Scheduler for Cloud Computing Environment[C]// Ieee/acm International Conference on Cluster, Cloud and Grid Computing. IEEE, 2010:585-586.

[5] You X, Xu X, Wan J, et al. RAS-M: Resource Allocation Strategy Based on Market Mechanism in Cloud Computing[M]. IEEE Computer Society, 2009.

[6] Buyya R, Beloglazov A, Abawajy J. Energy-Efficient Management of Data Center Resources for Cloud Computing: A Vision, Architectural Elements, and Open Challenges[J]. Eprint Arxiv, 2010, 12(4): 6-17.

[7] Ikeda M, Barolli L, Koyama A, et al. Performance evaluation of an intelligent CAC and routing framework for multimedia applications in broadband networks[J]. Journal of Computer & System Sciences, 2006, 72(7): 1183-1200.

[8] Deb K, Miettinen K. Multiobjective Optimization: Interactive and Evolutionary Approaches[M]. Springer-Verlag, 2008.

[9] K. Deb, Multi-Objective Optimization Using Evolutionary Algorithms, Wiley, 2001.

[10] Deb K.Multi-objective genetic algorithms: problem difficultiesand construction of test problems.[J]. Evolutionary Computation, 2014, 7(3): 205-230.

[11] Calheiros R N, Ranjan R, De Rose C A F, et al. CloudSim: A Novel Framework for Modeling and Simulation of Cloud Computing Infrastructures and Services[J]. Computer Science, 2009.

[12] 师雪霖, 徐恪. 云虚拟机资源分配的效用最大化模[J]. 计算机学报, 2013, 36(2): 252-262.

[13] 钱琼芬, 李春林, 张小庆, 等. 云数据中心虚拟资源管理研究综述[J]. 计算机应用研究, 2012, 29(7): 2411-2415.

[14] 李强, 郝沁汾, 肖利民, 等. 云计算中虚拟机放置的自适应管理与多目标优化[J]. 计算机学报, 2011, 34(12): 2253- 2264.

Multi-object ant Colony Resource Allocation Algorithm Based on Package Cluster Mapping in Coud Computing

DING Shun1, CHEN Shi-ping2

(1. School of Optical-Electrical and Computer Engineering, University of Shanghai for Science and Technology, Shanghai 200093, China; 2. Network and Information Center Office, University of Shanghai for Science and Technology, Shanghai 200093, China)

In the cloud computing environment, virtual machine placement is the process of mapping a virtual machine to a physical machine. An optimal placement strategy is very important for improving computational efficiency and resource utilization. In this paper, the problem of virtual machine placement in cloud computing environment is described as a multi-objective combinatorial optimization problem. A multi-objective ant colony optimization method is proposed, which optimizes the operation cost and resource waste at the same time and applies it to the cluster topology. Effectively get a set of non-dominated solutions while minimizing the total waste of resources and operating costs. The experiment compares the algorithm with the existing multi-objective genetic algorithm (MGA) and three single-objective algorithms. The results show that the proposed algorithm can achieve better results than other algorithms and achieve the compromise between the two objectives.

Cloud computing; Multi-objective optimization; Non-dominated solutions; Ant colony algorithm

本研究获得国家自然科学基金项目(61472256、61170277); 上海市一流学科建设项目( S1201YLXK);上海理工大学科技发展基金(16KJFZ035、2017KJFZ033); 沪江基金(A14006)等资助。

丁顺，硕士，主要研究领域：计算机网络、云计算；陈世平，教授，主要研究领域：计算机网络、分布式计算、云计算。

TP3

A

10.3969/j.issn.1003-6970.2018.11.001

丁顺，陈世平. 云计算中基于包簇映射的多目标蚁群资源分配算法[J]. 软件，2018，39（11）：01-06