面向低能耗的虚拟机部署和迁移策略

田苗苗，李 俊（中国科学技术大学 自动化系，安徽 合肥 230026）

面向低能耗的虚拟机部署和迁移策略

田苗苗，李 俊
（中国科学技术大学 自动化系，安徽 合肥 230026）

为提高数据中心的资源利用率并降低能耗，提出了面向低能耗的虚拟机部署和迁移策略，包括虚拟机初始部署算法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≤其中，h（j）是虚拟机 j被分配到的主机，vrjl是虚拟机 j的第l种资源量，hril是主机 i的第 l种资源量，powi是主机i的能耗。对于集成DVFS技术的主机，开启时可根据参考文献［8］提出的能耗模型计算powi：其中，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）指的是当主机CPU值为ri，虚拟机集合为1，…，j时的最大迁移时间，mj是虚拟机j的CPU资源值。

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

2.3 虚拟机迁移算法

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

3 仿真实验和分析

3.1 实验环境

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

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

表1 主机配置

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

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

表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％。这也与理论相符合，动态规划较贪心选择策略结果更优，但时间复杂度更大，因此数据中心可综合考虑迁移时间和计算时间来选择具体策略。

图1 虚拟机部署算法比较

图2 虚拟机迁移算法比较

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.

图6 服务器测试视频数据

其中图6（a）是移动监控设备对采集的视频数据经过电子稳像处理过的连续3帧视频数据，图6（b）是与图（a）相对应的未经过设备端稳像处理的视频数据。由图6可以看出电子稳像操作解决了拍摄视频时的抖动问题。将前端移动监控设备在不同的地方进行测试，系统都可以稳定运行。本系统可以广泛地应用于一些无法铺设线路的偏远地区，解决了传统监控系统中难以铺设线路的问题。

参考文献

［1］何岳.移动监控系统研究［J］.信息通信，2012（5）：126-127.

［2］姚楠，余劲.基于云的电力监控视频故障管理系统设计［J］.电子技术应用，2014，40（6）：140-142.

［3］杨阳，胡永辉.移动监控终端无线传输系统的设计与实现［J］.时间频率学报，2011，34（1）：27-32.

［4］梁振涛，樊泽明，任永亮，等.基于单片机的移动监控系统硬件设计［J］.微型机与应用，2014，33（2）：25-30.

［5］葛虎龙，李安平.高清抖动视频的实时稳像算法［J］.信息通信，2013（6）：41-43.

［6］黄九林.基于块匹配和直线特征的视频稳像方法研究［D］.大连：大连理工大学，2014.

（收稿日期：2015-03-28）

作者简介：

杨云龙（1988-），男，硕士研究生，主要研究方向：多媒体数字通信。

孟利民（1963-），女，博士，教授，主要研究方向：无线通信与网络、智能信息系统、网络管理、多媒体数字通信与网络。

Virtual machine deployment and migration strategy for saving energy

Tian Miaomiao，Li Jun
（Department of Automation，University of Science and Technology of China，Hefei 230026，China）

To improve data center′s resources utilization and reduce energy costs，a virtual machine deployment and migration strategy for saving energy has been proposed.The strategy includes a virtual machine deployment algorithm named BT-MPA and migration algorithm named MMT-MMA.BT-MPA achieves initial map from virtual machines to hosts optimally based on backtracking algorithm，MMT-MMA migrates virtual machines dynamically by using the minimum migration time strategy.Simulation results prove the strategy can reduce total energy consumption of data center and avoid unnecessary migration overhead.

data center；virtual machine；dynamic deployment；low energy consumption；dynamic migration

TP391.9

A

1674-7720（2015）18-0023-03

田苗苗，李俊.面向低能耗的虚拟机部署和迁移策略［J］.微型机与应用，2015，34（18）：23-25，31.

2015-04-20）

田苗苗（1991-），女，硕士研究生，主要研究方向：云计算。

李俊（1973-），男，博士，副教授，主要研究方向：网络控制。