摘 要：随着越来越多数据中心的构建和部署，能耗问题成为研究热点。作为一种有效的节能策略，虚拟机整合受到了研究人员和业界的关注。针对传统的虚拟机放置策略的不足，利用化学反应优化算法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 引 言
大多研究主要将虚拟机放置问题建模为装箱问题并采用贪婪算法去寻找一个近似最优的方案，常用的贪婪算法主要有：首次适配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）是一种有效的迁移机制，已经在一些服务器中得到了应用。
3.2 基本化学反应操作的设计
CRO有4种分子反应，即无损器壁碰撞、无损分子间碰撞、分解和合成。
1）无损器壁碰撞
在这个反应中，一个分子将撞击容器并导致分子结构发生局部改变。通过这个反应，原始的解w′将从它的邻域w1中得到一个新的结构w，相当于局部搜索。为了提高分子加快算法的收敛速度，本文使用禁忌搜索算法实现无损器壁碰撞，具体步骤如下。 （1）给定算法参数，每一次迭代都把当前分子w′作为禁忌算法的当前解，置禁忌表为空，藐视准则定义为：当前解的物理机使用个数少于best so far，则忽视禁忌表属性，用当前解代替best so far。；
（2）判断算法终止条件是否满足？若是，则结束算法并输出优化结果；否则，继续以下步骤；
（3）利用当前解的邻域函数产生其所有（或若干）邻域解，并从中确定若干候选解；
（4）判断候选解是否满足藐视准则？若满足，则用满足藐视准则的最佳状态y替代x成为新的当前解，即x=y，并用与y对应的禁忌对象替换最早进入禁忌表的禁忌对象，同时用y替换“best so far”状态，然后转步骤6；否则，继续以下步骤；
（5）判断候选解对应的各对象的禁忌属性，选择候选解集中非禁忌对象对应的最佳状态为新的当前解，同时用与之对应的禁忌对象替换最早进入禁忌表的禁忌对象元素；
（6）转步骤（2）。
2）分解反应
3）无损分子碰撞反应
无损分子碰撞是两个分子碰撞后发生微小的变化又分开。这个反应有点类似无损器壁碰撞，但是不同的是这个反应涉及到两个分子，并且没有分子动能（KE）丢失到中央能量缓冲区。我们用OX算子实现这个反应。
4）合成反应
3.3 算法描述
在算法开始之初，需要初始化如下参数：PopSize， KELossRate， MoleColl， buffer， InitialKE，α，β。其中PopSize表示种群大小，KELossRate表示动能丢失率，MoleColl取值为[0，1]，是每次迭代时判断单分子碰撞和多分子碰撞的参数。α，β分别代表单分子碰撞和多分子碰撞选择的极限值。当一个分子的撞击次数超过α后，它的优越性还没提升则会发生分解反应。β代表一个分子所拥有的最小的动能，如果低于这个值则会发生合成反应。目标函数值就等价于分子的势能值，要找最小的函数值就得找到最稳定的势能最小的分子。
迭代开始之后，会随机产生一个[0，1]之间的整数K，当K大于MoleColl时则发生单分子碰撞，反之则发生多分子碰撞。迭代过程会一直继续直到达到停止标准，最终输出一个近似最优解。
4 实验与分析
4.1 实验环境设置
4.2 实验结果与分析
图3显示不同虚拟机数目情况下4种放置算法得到的能耗比较情况。随着虚拟机数目的增多，四种算法得到的能耗也逐渐增大。与FFD和ACO算法相比，CRO算法在能耗指标上平均降低了13.5%和9.9%。而与CRO算法相比，CROTS算法在能耗指标上平均降低了3.1%。这主要因为物理服务器的使用数目与数据中心的能耗有直接的关系，CRO和CROTS算法相对于FFD和ACO算法来说，能够获得更优的放置解。
图4比较了不同虚拟机配置数目情况下四种算法得到的物理服务器的数目比较。随着虚拟机数目的增多，四种算法的物理服务器的数目也在增大。其中，FFD算法的性能最差，其所需要的平均物理服务器数目分别是ACO、CRO、CROTS算法的1.04、1.09、1.13倍。表明算法CROTS相对于其他三种算法，具有最好的求解能力。而且从图4中可以看出当虚拟机规模越大，CROTS算法的性能越好，这是因为CROTS适合求解大规模优化问题。
为了进一步说明CROTS算法的求解效率，实验对ACO、CRO以及CROTS三种算法的收敛性情况进行了实验比较。
从图5可以看出CROTS混合算法的收敛速度要比ACO和CRO快，因为在CRO算法无损器壁碰撞反应中加入禁忌搜索，使得解的收敛速度更快，在60000次评估左右就基本上达到稳定。表明CROTS在寻找最优解方面具有明显优势。 5 总 结
随着数据中心基础设施规模的增大，能耗问题越来越突出。虚拟机整合能够有效的降低能耗，本文提出基于CROTS的虚拟机放置策略。通过CRO与禁忌搜索算法相结合，进一步提高了CRO算法的性能。实验结果与传统的贪婪算法和ACO相比，所提出的混合算法能够有效的减少物理结点的使 用数量，从而达到节约能耗的目的。下一步的工作将考虑多目标同时优化以及CROTS算法在解决虚拟机放置问题上的各个参数的最优设置。参考文献
[2] VERMA A，AHUJA P，NEOGI A. pmapper： power and migration cost aware application placement in virtualized systems[C]. In proceedings of 9th ACM/IFIP/USENIX international conference on middleware， 2008，243-264.
[3] Bo Li， Jianxin Li， Jinpeng Huai， et al. Enacloud： An energysaving application live placement approach for cloud computing environments[C]. In proceedings of international conference on Cloud computing， 2009.
[4] BELOGLAZOV A，BUYYA R.Adaptive thresholdbased approach for energyefcient consolidation of virtual machines in cloud data centers[C]. In proceedings of the 8th workshop on Middleware for Grids， Clouds and e-Science. 2010， 41-46.
[7] KHAN S U，ARDIL C.Energy efficient resource allocation in distributed computing systems[C]. In proceedings of International Conference on Distributed， High Performance and Grid Computing， 2009， 667-673.
[9] STILLWELL M，SCHANZENBACH D，VIVIEN F，CASANOVA H.Resource allocation algorithms for virtualized service hosting platforms[J].Journal of Parallel and Distributed Computing， vol.70， no.9， pp. 962-974， 2010.