云环境下基于CROTS算法的虚拟机放置策略

　　摘 要：随着越来越多数据中心的构建和部署，能耗问题成为研究热点。作为一种有效的节能策略，虚拟机整合受到了研究人员和业界的关注。针对传统的虚拟机放置策略的不足，利用化学反应优化算法CRO求解数据中心的虚拟机放置问题，并通过禁忌搜索算法提高CRO算法中器壁无损碰撞对解的勘探能力。仿真实验表明，相对于传统的贪婪放置策略FFD和基于ACO的放置策略，提出的CROTS算法可有效降低数据中心物理机的使用个数，进而降低了数据中心的能耗。
　　关键词：云计算； 数据中心； 虚拟机放置； 能耗； 化学反应优化
　　中图分类号：TP391 文献标识码：A
　　Abstract：More and more data centers are created，and energy consumption becomes the research hotspot. As a kind of effective energy saving strategy， VM consolidation is focused by researcher and industry. Due to the shortage of the traditional VM consolidation，this paper used a new metaheuristic algorithm called CRO（Chemical Reactive Optimization）to solve the VM consolidation problem in data centers and used Local Search to improve the ability of seeking the solutions. Experimental results show that this method is more excellent than other methods， which can decrease the number of servers and can reduce the energy consumption of data centers.
　　Key words：cloud computing； data center； VM placement； energy； CROTS
　　1 引 言
　　云计算是一种新兴的计算模式，然而，在云计算技术促进IT发展并带来巨大经济效益的同时，也消耗了大量的电能。近期分析报告显示[1]：截至2011年，世界范围内的计算中心的年均耗电量已经超过3 兆kW，且其增长呈明显的加速趋势。因此，有效控制数据中心的能耗量已经成为各国科研和应用领域的一个亟待解决的问题。在数据中心，随着虚拟机的不断创建与撤销，分布在物理资源上的虚拟机必将分散，从而导致部分服务器的使用率非常低。如何合理地确定虚拟机到服务器的映射对整体物理资源池的利用率以及能耗有着直接影响，已经成为云计算领域的研究热点。
　　大多研究主要将虚拟机放置问题建模为装箱问题并采用贪婪算法去寻找一个近似最优的方案，常用的贪婪算法主要有：首次适配FFD，最优适配BFD和最差适配WFD（WorstFit Decreasing）三种。例如，IBM的Verma等[2]设计的pMapper采用FFD选择虚拟机的放置位置。文献[3]提出了一种虚拟机迁移框架EnaCloud，采用最优适配BFD的启发式算法确定虚拟机的放置。文献[4]提出了一种改进BFD（BestFit Decreasing）算法并应用到虚拟机放置问题中，通过模拟实验验证了其性能。文献[5，6]在一个同构的计算环境中将虚拟机放置建模为1维装箱问题，只考虑CPU资源，所提出的虚拟机迁移算法没有考虑当前的虚拟机分配情况。类似地，文献[7]和文献[8]也将虚拟机放置问题简化为一维分配问题，仅考虑了CPU和内存资源。除此之外，一些研究将VM放置问题建模为多维装箱问题，即MDBP问题。如文献[9]将异构计算环境下的虚拟机分配问题建模为MDBP，然后通过实验比较了多个贪婪算法的性能。在文献[10]中，李强等人则将能耗感知的虚拟机放置问题归结为多维QoS约束下的最优规划问题，并设计了一个基于遗传算法的求解策略。近期，Albert等人[11]提出了一种新的元启发式方法，称之为化学反应优化算法。该算法模拟化学反应中的分子碰撞，以及分子从高能状态向低能状态不断转变的过程，最终驱使分子进入最稳定的状态。CRO相对于以往的智能算法表现出了更强的问题求解能力。鉴于CRO算法求解的高效性，本文将禁忌搜索算法与之相结合以提高CRO局部搜索的能力，并应用到虚拟机放置问题的求解中，取得了较好的效果。
　　2 问题描述
　　虚拟机配置是数据中心的核心功能之一，其配置过程如图1所示。首先，根据来自用户应用的大量虚拟机配置请求，数据中心内的虚拟机配置规划器根据监控服务器或者通过负载预测获得的服务器负载信息，确定服务器是否过载。然后采用智能算法获得虚拟机配置的全局最优解（本文基于CRO和禁忌算法）。最后，数据中心的迁移规划器根据虚拟机的配置方案确定相应的迁移规划。其中，虚拟机实时迁移（Live Migration）是一种有效的迁移机制，已经在一些服务器中得到了应用。
　　示例图2表示ID为3和4的虚拟机放在1号物理机上，ID为2和7的虚拟机放在2号物理机上，ID为1、3和6的虚拟机放在3号物理机上。
　　3.2 基本化学反应操作的设计
　　CRO有4种分子反应，即无损器壁碰撞、无损分子间碰撞、分解和合成。
　　1）无损器壁碰撞
　　在这个反应中，一个分子将撞击容器并导致分子结构发生局部改变。通过这个反应，原始的解w′将从它的邻域w1中得到一个新的结构w，相当于局部搜索。为了提高分子加快算法的收敛速度，本文使用禁忌搜索算法实现无损器壁碰撞，具体步骤如下。