一种基于遗传算法的虚拟机优化放置方法

摘要：—近些年“云计算”受到越来越多的关注，随着研究和实践的加深，它从早些时候的概念变成了实际。在云环境中基础设施即为服务（IaaS）是一个重要的组成部分，它将基础设施转化成虚拟资源，通常为虚拟机(VMs)提供给用户使用，虚拟机的放置策略是成功实施IaaS的重要环节。该文提出了一个可预知的虚拟机负载平衡的放置问题，并给出了一个改进的遗传算法来解决该问题，实验结果证明该算法有效。

关键词：云计算；虚拟机放置；负载平衡；离线调度；0-1整数规划；改进遗传算法

中图分类号：TP311文献标识码：A文章编号：1009-3044(2012)07-1595-03

1简介

如今云计算受到越来越多的关注。它并不是一个全新的技术，而是大规模的分布式计算范例，它能通过互联网将系统内部的池化的计算资源共享给用户[1]。在这里计算资源是一个广义的定义，包含存储设备，计算能力，平台和软件资源等。在云计算中上述的种种资源都将被视为可访问的服务提供给外界的用户使用。上述资源一般能被分为三种服务：IaaS，PaaS和SaaS[2]。IaaS（Infrastructure as a Service，基础架构即服务）可以提供服务器、操作系统、磁盘存储、数据库等资源来供用户使用，降低了用户本身的硬件维护成本；在云计算模型下IaaS是基础部分[3]，它可以提供伸缩性的计算资源来满足用户多变的需求，云环境设施中的一个核心特征就是弹性[4]，即对于某一个有服务品质协议(SLAs)的服务，根据不同的任务负载，云环境在有能力自动和快速的扩张或缩小分配给服务的资源，

本文主要关注于工作负载可被预测的弹性场景，通过预订虚拟机来实现弹性扩张。可预测的工作负载场景很常见，如在线银行的月末高峰结算，流媒体服务站点夜间容易出现高负载，且通过一些对服务的虚拟机用量历史数据的记录的手段，也可以预先得到需要的虚拟机个数[5]。提前获知虚拟机的需求量可以极大的方便服务方以及云设施方，因为通过事先进行虚拟机放置策略，从而快速分配虚拟机同时减少虚拟机的创建、移动等开销。

虚拟机在云设施中的放置策略通常不同的标准，如减少能耗，提高性能，增加资源使用率，这些都是根据不同的目标驱动的。在一个IaaS提供设施内，物理机间能力不同，它们之间的负载率相差会很大，而有的服务应用需要在运行的期间尽量保持各物理机的负载是平均的[7]，处理这样的问题，需要最小化最大负载的机器负载，并且保持整个系统负载平衡。

虚拟机放置通常可以看成是一个多约束K背包问题，它是一个NP难问题，通常有很多近似算法解决。而本文主要着重研究该负载平衡问题的本身，针对问题给出一个0-1整数规划公式，并提出一个改进的遗传算法进行有效的解决。

本文剩余部分由以下几个部分组成：第二部分是问题具体描述和问题公式；第四部分针对问题给出了一个改进的遗传算法；第五部分给出了仿真实验结果；第六部分是总结和展望。

2问题描述和问题公式

研究场景如图1所示，可预测的工作负载由不同类的虚拟机装载，并被请求到云设施提供商处，每一个虚拟机集请求描述为VMR = {VMRId,VMset,Start,End}，每个虚拟机集VMSet = {a1,a2,a3,..,an}, ai表示装载某类应用的虚拟机的个数，虚拟机类型是由服务商事先定制[8]，每个虚拟机有自身不同的属性，例如CPU个数，内存大小，硬盘大小等；Start表示该请求内虚拟机运行时间；End表示结束时间。目标是负载平衡即在整个请求周期T内，通过虚拟机的放置，使得某台物理机最大负载率最小。某物理机在T内最大负载公式：

3基于遗传算法的虚拟机放置方法

为了解决上节提出的规划问题，在规模很大时采用传统解法会十分慢，所以本文给出一个改进的遗传算法。先给出一个原始遗传算法。它的适应值函数为

实验结果发现，直接使用自然编码，即将所有的虚拟机按次序表示，并且取值范围为物理机的个数，由于请求数量会非常大，资源数也十分庞大，解空间高达N=PMnum^VMnum，随机产生种群会有大量非法解，往往得不到很优秀的解，对初始种群很敏感。

针对问题本身发现，对于不同时段的虚拟机是可以共享同一个物理机资源，而对于整个T时间段内，所有的虚拟机集请求可以得到每一个最大重叠集合，即如图2所示，得到重叠集合有{(1,2,3),(1,2,4),(2,4,5)}。所以对于每一个物理机负载计算公式可以将公式内的T修改为每一个重合集合的开始时间T’= OverLap.StartTime。然后针对每一个T’得出(1)，约束(2),(3)。

首先下面给出所有最大重叠集合的伪代码，利用滑动时间窗口的方法进行计算，该算法具有O(n)计算复杂度。

交叉运算和变异运算采用默认方法。当迭代次数完成后，对于每一个OverLapSet内虚拟机放置的染色体进行成长操作，即讲它变成原问题的一个特殊染色体，如果有4个请求，每个请求包含1个虚拟机，3台物理机，某染色体若为OverLapSet{1,3}的较优解为{4, 5}，则该染色体成长为{4,-1,5,-1}。得到所有成长染色体后进行合成操作，即使其成为一个原问题合法染色体,若另有一条染色体为{1,3,-1,2},则合成操作后可分别得到两个子染色体，{4,3,5,2}和{1,3,5,2}都是原问题的合法染色体。随后将得到的染色体加入到原问

4仿真实验分析

仿真实验采用JGAP进行代码编写，使用了JGAP的框架结合了上节提到的适应值函数和染色体变化的方法。为了数据明显性，实验只考虑了CPU个数的负载，对于其他的限制条件可以直接添加，并无影响。

实验的数据设定如表1：

表1

实验与一个近似的贪心算法进行了比较，即每次寻找最小负载且能装入虚拟机的物理机进行虚拟机装载，且如果虚拟机生命周期结束，若虚拟机仍在物理机上预留则将其删除，直到所有虚拟机被装载完成，得到一个放置调度结果，以及原始的遗传算法和改进后的遗传算法。初始种群大小都设成50，且最大的迭代数设为50。得到如下结果图3，IGA计算出的放置方案在全过程中一直处于比较低的负载率，说明改进后的遗传算法是有效的。

5结论和下一步工作

本文研究了一种在给定了可预知的虚拟机请求情况下的放置问题，目标是负载平衡，将该问题描述成了一个0-1整数规划问题，并给出了一个改进型的遗传算法进行求解，得到了较好的效果。虚拟机的放置问题的目标非常丰富[8]，本文仅针对了负载平衡问题进行求解，且仅在了一个提供商内进行调度放置，以后的可能方向需要加入更多的条件进行研究，且考虑当虚拟机请求集远远超出物理机能力时，如何进行选择性的放置。

参考文献：

[1] Foster I,Zhao Y,Raicu I,et al.Cloud Computing and Grid Computing 360-degree compared[C].in Grid Computing Environments Workshop, 2008:1-10.省略,“What is Cloud Computing?”[EB/OL].,2008.

[3] Vaquero L M,Merino L R,Caceres J,Lindner M.A Break in the Clouds: Towards a Cloud Definition[C].ACM SIGCOMM Computer Communication Review,January 2009:50-55.

[4] Armbrust M,Fox A,Griffth R,et al.Zaharia. A view of cloud computing[C].Communications of the ACM,April 2010:53:50-58,

[5] Stage A,Setzer T,Bichler M.Automated capacity management and selection of infrastructure-as-a-service providers[C].Integrated Network Management-Workshops,2009.IM ’09.IFIP/IEEE International Symposium on.

[6] Sivadon Chaisiri,Bu-Sung Lee,et al.Optimal Virtual Machine Placement across Multiple Cloud Providers[C].Services Computing Conference,2009.APSCC 2009.IEEE Asia-Pacific.

[7] Tang C,Steinder M, Spreitzer M,et al.A scalable application placement controller for enterprise data centers[C].In Proceedings of the 16th international conference on World Wide Web, WWW’07,ACM,2007:331-340.

[8] Breitgand D,Marashini A,Tordsson J.Policy-driven service placement optimization in federated clouds[R].Technical report,IBM Haifa Labs,2011.