摘  要： 为提高数据中心的资源利用率并降低能耗，提出了面向低能耗的虚拟机部署和迁移策略，包括虚拟机初始部署算法BT-MPA和虚拟机动态迁移算法MMT-MMA。BT-MPA算法基于回溯法实现虚拟机集合和主机集合的最优初始映射，MMT-MMA算法基于最小迁移时间策略实现虚拟机动态迁移。仿真验证了所提出策略能够在降低数据中心总能耗的同时避免了不必要的迁移开销。

　　关键词： 数据中心；虚拟机；动态部署；低能耗；动态迁移

0 引言

　　随着云计算的快速发展，数据中心能源成本不断上涨[1]。在2011年，我国数据中心总耗电量已经占到全社会用电量的1.5%[2]。高能耗的主要原因在于设备数量增加和资源使用率低[3]。

　　目前数据中心常用的节能技术有：动态电压频率调整（Dynamic Voltage and Frequency Scaling，DVFS）和虚拟化技术[4]。其中虚拟化技术能够将一个服务器虚拟成多个服务器，提高资源的利用率，降低成本[5]。

　　目前有许多关于虚拟机部署和迁移算法的研究。参考文献[4]提出了一种面向系统能耗优化的虚拟机部署算法，该算法能够有效降低能耗，但最终部署结果不是最优结果。参考文献[6]为了降低能耗给出了一种节能算法，并提到迁移时间的概念，但在迁移虚拟机时没有考虑迁移时间。参考文献[7]提出一种虚拟机放置方案，该方案能够优化能源效率，但没有涉及迁移问题。

　　基于当前研究，本文提出了面向低能耗的虚拟机部署和迁移策略，目的是在最小化数据中心能耗的同时保证服务质量。该策略一方面利用回溯法部署虚拟机，使开启物理机的数量最小；另一方面为了适应虚拟机的动态变化和避免资源过度聚合，根据最小迁移时间策略动态迁移虚拟机，最小迁移时间策略通过贪心算法和动态规划算法实现。

1 虚拟机动态部署

　　1.1 虚拟机部署问题

　　可将虚拟机部署问题描述为：数据中心有n台主机和m台等待部署的虚拟机，每台主机和虚拟机均配置k种资源，目标是完成部署后总能耗最小，其中虚拟机的资源总和不能超越主机的资源上限，虚拟机最多只能被部署到一个主机上。

　　以上描述等价为：D=（H1，…，Hn），Hi=（hri1，…，hrik），V=（vm1，…，vmm），vmj=（vrjl，…，vrjk），其中1≤i≤n，1≤j≤m。

　　其中，h（j）是虚拟机j被分配到的主机，vrjl是虚拟机j的第l种资源量，hril是主机i的第l种资源量，powi是主机i的能耗。对于集成DVFS技术的主机，开启时可根据参考文献[8]提出的能耗模型计算powi：

　　powi=pmin+（pmax-pmin）×ui（2）

　　其中，ui是主机i的CPU利用率，pmin是空闲状态下的能耗，pmax是ui最大时的能耗。

　　1.2 基于回溯法的虚拟机动态部署算法

　　虚拟机部署问题大多是基于贪心算法进行优化，但该问题不具有贪心选择性质，通过一系列局部最优选择并不能得到整体最优解。为了最小化能耗，本文基于回溯法提出了一个虚拟机部署算法BT-MPA。回溯法在虚拟机部署问题的解空间子集树中按照深度优先策略搜索，若搜索过程中当前的扩展节点不满足不等式（1）则跳过，否则进入该子树继续搜索，直至找到最优解[9]。

　　BT-MPA的步骤是：首先将主机按照开启关闭状态排序，相同状态的主机按照可用资源大小降序排列；接着依次选择主机，用回溯法从虚拟机集合中选出最优子集部署到主机中；然后从集合中移除已被部署的虚拟机，继续以上步骤直至虚拟机集合为空。

2 虚拟机动态迁移

　　虚拟机迁移问题可分为两个子问题：何时触发迁移和选择哪些虚拟机迁移。

　　2.1 触发迁移

　　本文设定资源利用率上限阈值Tup和下限阈值Tdown，当主机处于以下情况时触发迁移：（1）资源利用率大于Tup，说明主机处于过载状态，需迁出某些虚拟机，以避免降低用户体验；（2）资源利用率小于Tdown，需迁出所有虚拟机并关闭主机，以降低能耗。由于虚拟机对CPU的竞争最为激烈，故迁移时仅考虑CPU资源，用MIPS指标来衡量。

　　2.2 选择虚拟机

　　过载主机中虚拟机的选择有随机和最小迁移时间（Minimum Migration Time，MMT）两种策略。MMT策略是选择迁移时间最小的虚拟机集合迁出，它等价于选择一组总迁移时间最大的虚拟机集合留在主机上：

　　其中，uj（cpu）是虚拟机j使用的CPU和主机总CPU的比值[7]，mtj是迁移时间，用虚拟机内存与所在主机空闲带宽的比值衡量[3]。式（3）具有最优子结构性质，能够使用贪心和动态规划算法来解决。

　　2.2.1 贪心选择策略

　　使用贪心算法解决MMT问题的步骤是：首先将虚拟机按照迁移时间与MIPS的比值非降序排列，然后依次选择虚拟机加入迁出队列，直至主机的CPU利用率不大于Tup。该算法的时间复杂度为O（nlogn）[9]。

　　2.2.2 动态规划选择策略

　　动态规划将问题分解成若干子问题，通过结合子问题的解得到最终解[9]。假设F（j，ri）是子问题的最优解，则可以建立如下递归关系：

　　F（j，ri）=max{F（j-1，ri），F（j-1，ri-mj）+mtj}，ri≥mjF（j-1，ri），                     ri<mj（4）

　　其中，F（j，ri）指的是当主机CPU值为ri，虚拟机集合为1，…，j时的最大迁移时间，mj是虚拟机j的CPU资源值。

　　该策略能得到式（3）的最优解，最优解对应的虚拟机就是留在主机上的最优集合。该算法的时间复杂度是O（2n）[9]。

　　2.3 虚拟机迁移算法

　　本文基于以上策略提出了虚拟机迁移算法MMT-MMA，具体步骤是：周期性地检测开启主机的CPU利用率，如果大于Tup，则使用虚拟机选择策略得到迁出虚拟机集合，将其加入迁出队列；如果小于Tdown，则将其上的虚拟机全部加入迁出队列，最后将迁出的虚拟机队列按照BT-MPA算法重新部署。

3 仿真实验和分析

　　3.1 实验环境

　　为验证本文提出算法的有效性，进行了两组仿真实验，每组实验均进行15次，取平均值作为最终结果。实验设置Tup为0.8，Tdown为0.2。

　　首先在仿真系统中建立1个数据中心和20台主机，主机的资源根据表1随机配置。

　　系统中需部署的虚拟机数量范围是[10，80]，增加步长为10，虚拟机的资源根据表2随机配置。

　　虚拟机上运行的应用负载按照占用虚拟机资源的比例可分为轻、中、重三型，不同型号虚拟机上运行负载的概率空间相同，如表3所示。

　　3.2 实验结果

　　图1是使用本文提出的BT-MPA算法与基于贪心算法的Greedy-MPA进行虚拟机部署后的能耗比较图，从图可知BT-MPA在节能方面优于常用的Greedy-MPA，数据中心总能耗相对于Greedy-MPA算法平均降低9.7%，达到了更好的节能效果。

　　图2是使用不同的虚拟机选择策略进行动态迁移的结果。从图可看出，基于MMT选择策略的迁移时间远远低于RC策略，贪心选择策略的迁移时间相对于RC策略平均减少48%，动态规划选择策略相对于RC策略平均降低57%，动态规划相对于贪心选择策略平均降低18%。这也与理论相符合，动态规划较贪心选择策略结果更优，但时间复杂度更大，因此数据中心可综合考虑迁移时间和计算时间来选择具体策略。

4 结论

　　为降低数据中心的能耗，本文提出了虚拟机部署算法BT-MPA和虚拟机迁移算法MMT-MMA。通过仿真验证了BT-MPA能够有效降低数据中心总能耗，实现节能减排的目的，同时表明了MMT-MMA能够有效减少虚拟机迁移时间，避免不必要的迁移开销。本文在触发迁移时使用的是固定阈值，为了更灵活地应对负载变化，接下来将针对自适应阈值展开研究。

参考文献

　　[1] SCHULZ G. 绿色虚拟数据中心[M].韩毅刚，李亚娜，王欢，译.北京：人民邮电出版社，2010.

　　[2] 王肇国，易涵，张为华.基于机器学习特性的数据中心能耗优化方法[J].软件学报，2014，25（7）：1432-1447.

　　[3] BELOGLAZOV A， BUYYA R. Optimal online deterministic algorithms and adaptive heuristics for energy and performance efficient dynamic consolidation of virtual machines in cloud data centers[J]. Concurrency and Computat-ion： Practice and Experience， 2012（24）：1397-1420.

　　[4] 王加昌，曾辉，何腾蛟，等.面向数据中的虚拟机部署及优化算法[J].计算机应用，2013，33（10）：2772-2777.

　　[5] 高林，宋相倩，王洁萍.云计算及其关键技术研究[J].微型机与应用，2011，30（10）：5-7.

　　[6] 周舟，胡志刚.云环境下面向能耗降低的虚拟机部署算法[J].华南理工大学学报，2014，42（5）：109-114.

　　[7] 董健康，王洪波.IaaS环境下改进能源效率和网络性能的虚拟机放置方法[J].通信学报，2014，35（1）：72-81.

　　[8] BELOGLAZOV A， ABAWAJY J， BUYYA R. Energy-aware resource allocation heuristics for efficient management of data centers for Cloud computing[J]. Future Generation Computer Systems， 2012（28）：755-768.

　　[9] 王晓东.计算机算法设计与分析[M].北京：电子工业出版社，2012.