(绍兴职业技术学院, 浙江 绍兴 312000)

0 引言

近年来随着网络带宽的提高及通信流量成本的降低，各类大型IT企业都已经逐步建立了自己的基于云的大数据中心，其消耗的电力能源也与日俱增，政府与企业都在开始研究云数据中心的低能耗问题，倡导低碳环保生活与绿色云计算[1-3]。云数据中心的虚拟机迁移策略是目前提高云端资源利用效率和降低能量消耗的主要技术，它能够将应用服务封装在虚拟机之中，在服务请求减少的情况下，将云端的多个虚拟机迁移到一个物理服务器，关闭空闲服务器或者使空闲服务器进入睡眠模式[4-7]；当服务请求增加时，重新唤醒空闲服务器[8]。

目前学术界利用云端的虚拟机迁移策略来节省云端的能源消耗,进行了大量的研究。虚拟机迁移早期的技术有预复制Pre-copy,后复制post-copy,混合复制等, 这些主要是应用在单虚拟机迁移领域(single virtual machine migration)或者非云端的虚拟机迁移。随着云端服务规模的扩大，目前大多都是多虚拟机迁移模式[9-11]。Luo等人[12]从CPU维度对虚拟机的动态配置问题进行建模，并利用改进的蛙跳算法进行求解。Xu[13]等人提出了PS-ABC算法，该方法能够在长期服务项目的局部时间段内实现较好节能效果，但是在服务项目全局的能耗优化问题上，效果并不理想。Zhao等人[14]在此基础上提出了PS-ES启发式算法，不仅实现了当前场景的能源优化，而且也有效降低了长期服务项目总体的能源消耗，但其考虑的维度较单一。Cao等人[15]在Beloglazov研究的基础上提出SLA违规算法，引入最小能源最大利用率策略，进一步优化虚拟机配置方法; 上述这些方法的主要目的是应用虚拟机动态迁移技术实现云端服务的负载均衡，容错,优化服务器的电力能量管理等,最终是为了改善云端的服务质量QoS,减少SLA违规, 但是考虑的物理资源使用情况的维度比较少，例如只考虑CPU或者内存情况，没有考虑网络带宽及虚拟机本身的资源需求等情形。

总体来说云计算环境下的虚拟机的迁移优化问题可以被描述为类似多维装箱的问题，即将物理服务器抽象为箱子，箱子的容量是服务器资源的大小，包括CPU、内存、硬盘和网络带宽；虚拟机抽象为装入的物品，其所用的资源就是物品的大小；资源的种类被抽象为装箱问题的维度[21]。此类问题是一个基于多约束的整数规划问题，同时也是一个NP-hard问题，唯一和装箱问题不同的是，该装箱问题是处于动态变化之中，即当前的物品装箱状态是基于前一次的状态，因此，还需要优化物品的移动成本。根据以上分析，本文的研究点就转化为基于多约束的多目标优化问题，并求其近似最优解,为此本文提出一种云计算环境下的虚拟机动态迁移策略DMS-VM(Dynamic Migration Strategy for Virtual Machine)。

1 问题描述与建模

在云计算环境下，由于用户的弹性需求，导致虚拟机中的工作负载也同样处于动态变化之中，为了提高资源利用率，需要利用虚拟机迁移技术来整合各工作负载。一般情况下，动态虚拟机迁移的目标主机可能由多个，而且选择不同的目标主机会产生不同的能源消耗，DMS-VM被设计一种高效节能的虚拟机迁移策略，使得虚拟机在迁移时能够被部署在合适的物理服务器上。如图1所示，可以将云计算环境下虚拟机迁移问题描述为：

图1 虚拟机放置示意图

考虑云数据中心包含m台同构的主机PM={PM1,PM2,……PMm}和n台虚拟机VM={VM1,VM2,……VMn}，VM有w种类型，同时满足w

为了实现应用的隔离性和虚拟机的有效性，假定每个虚拟机中只运行一种应用程序，即将应用程序封装在虚拟机之中，实现虚拟机与应用程序一对一的绑定，因此应用程序与虚拟机个数相同，应用程序可表示为A={A1,A2,……An}，其中Ai只处理Qesi类型的应用请求，根据Qesi请求量Qi的动态变化产生不同的负载占用虚拟机资源的比例表示为ri={ricpu,rimem,ristore,ribw}，因此ri随着时间的推移也在动态变化。主机上运行的虚拟机状态可表示为(Xij)nxm，Xij值域为{0,1}，当Xij=1时，表示在主机PMj上已启动虚拟机VMi，相反，当Xij=0时，表示虚拟机VMi不在主机PMj上。

根据以上的场景假定和变量的定义，云计算环境下的虚拟机迁移策略可以抽象为类似多维装箱的问题，不同点在于每一次的物品装箱，都要在物品前一次的状态基础上进行。因此，建立如下所示的虚拟机迁移模型：

目标函数：

(1)

(2)

式(1)表示执行第k次迁移策略之后，启动的物理主机数目最少；式(2)表示执行第k次迁移策略所移动的虚拟机次数最少。

约束条件：

(3)

Yj(k) ∈{0,1}表示执行第k次迁移策略之后，主机PMj中是否存在运行的虚拟机。如果Yj(k)=0，表示主机PMj中没有运行的虚拟机，即处于关机或者待机，相反Yj(k)=1，表示主机PMj中有虚拟机运行，即处于激活状态。定义迁移变量如下:

(4)

为了降低迁移的复杂度，假定每次执行迁移操作时，每个虚拟机最多只能迁移一次，即Mi(k)∈{0,1}，Mi(k)=1表示执行第k次迁移策略之后，VMi已经迁移，相反，Mi(k)=0表示VMi没有迁移。

(5)

式(5)表示第k次迁移完成之后，PMj没有超负荷运行。假定迁移过程中，任何一台主机不能既迁入虚拟机同时又迁出虚拟机。

2 DMS-VM算法设计与实现

根据前面的分析, DMS-VM算法转化为多目标优化问题. 它一般不存在单一最优解，需要从一组非劣解中选择一个满意解，因此对于解的满意选择就存在一种偏好问题。一种简单的方法就是引入一个权重变量将多个目标求解转化为单目标求解。而遗传算法是一种模拟自然选择机制和自然遗传进化过程的计算模型，不仅可以高效地搜索最优解，并且其具有的并行性能够适应大规模组合优化问题。因此本节引入多目标遗传算法求解虚拟机迁移问题。DMS-VM中利用遗传算法求解的具体步骤如下：

(1)染色体编码。

染色体编码的选择是影响遗传算法搜索效率和效果的重要因素，其实现的是从问题的解到染色体的映射。根据模型所示，虚拟机和主机是多对一的关系，因此，本文运用分组编码的方式对染色体进行编码，即染色体基因位上数字表示分组的主机号，每个分组中包含一串子基因，该子基因号表示主机中的虚拟机编号。

(2)种群初始化。

种群初始化是遗传算法最基本的步骤，本文DMS-VM中遗传算法求解的是虚拟机动态迁移问题，种群的初始化需要基于虚拟机和主机迁移前的状态，因此，根据虚拟机编号，随机产生一组虚拟机序列，按照当前染色体编码、本文约束条件和多维优先适应的原则，将虚拟机分配到运行的主机中，若运行的主机不满足约束条件，则将虚拟机分配到编号最小的待机状态主机，使主机处于运行状态。

(3)适应度函数。

适应度函数Fitness是由目标函数转换而成的，根据权重值W，将多目标转变单目标,如公式(6)。

(6)

(4)选择操作。

本文DMS-VM遗传算法中的选择操作为轮盘赌法，即基于适应度比例的选择策略，以此来选择出合适的个体进行后续的交叉和变异操作，为了防止当前群体的最优个体在下一代发生丢失，导致算法不能收敛到全局最优解，在选择操作前，需要保留g个最优个体。选择操作中每个个体xi的选择概率为Pi：

式中，Fi为个体xi的适应度值，由于选择的适应度是模型目标函数最小值，因此其值越小越好，所以在个体选择前对适应度值求倒数，k为系数，size为种群个体数目。

(5)交叉操作。

在种群中随机选择两个染色体chromosomei和chromosomej，设置交叉概率Pc，并对两个父个体随机产生交叉位置，将第一个父个体的交叉位基因插入第二个父个体的染色体最前端，删除第二个父个体中重复出现的虚拟机及其所在的主机，根据多维优先适应的原则，从新分配无主虚拟机，并且在满足约束条件的前提下，根据虚拟机迁移数最小原则，将染色体最前端新插入的基因替换删除的主机基因，若不满足约束，则将新基因替换最小编号的空闲主机基因。交叉操作的实例如图2所示。

图2 DMS-VM中利用遗传算法的交叉操作

(6)变异操作。

首先，以较小的概率Pm获得需要变异的染色体chromosomei，随机产生一个存在于chromosomei中的整数M∈ [0,m)，即运行的主机号，将主机中的所有虚拟机按照多维优先适应的原则进行从新分配。

(7)精英保留。

根据适应度函数，重新计算新种群中个个体适应度F={F1,F2,……Fd}，令精英个体适应度G={G1,G2,……Gg}，将F和G进行混合排序，选取其中最优的d个个体作为新一代种群。

3 仿真与结果分析

3.1 仿真环境与配置

为了对本文提出的云计算环境下的虚拟机动态迁移策略DMS-VM进行实验分析，需要应用到大规模的数据中心基础架构， 利用某个企业的一个大规模云数据中心作为测试环境，它包括300个空闲的HP ProLiant ML110 G4物理服务器，这些物理服务器在执行云计算应用程序的时候,划分为虚拟机后的参数配置如表1所示: 我们把本文的虚拟机迁移策略与已经有的MADLVF[16], Buyya[17], Melliti[18]等常见的迁移策略进行了比较。比较的性能参数包括四个: 低负载服务器数量变化情况，虚拟机迁移个数分析，云数据中心能耗分析和SLA的平均违规分析。

表1 实验中的虚拟机参数配置情况

3.2 低负载的服务器数量分析

在测试过程中，当整个应用的虚拟机的请求数量增加的时候，4种迁移策略情况下, 那些负载比较轻的服务器数量都随着增加，这也表明四个虚拟机迁移策略都可以降低负载比较重的服务器的工作压力，把这些负载迁移到低负载的服务器上，而且被增加的这些服务器的数量也是缓慢的增加。与其他几种云计算环境的虚拟机迁移策略比较起来，本文的DMS-VM迁移策略低负载的服务器数目增加是最缓慢的,整个测试结果如图3所显示。

图3 4种虚拟机迁移策略的负载均衡性能比较

3.3 虚拟机迁移次数分析

图4显示了随着云计算应用的虚拟机请求数量的变化,4种策略比较起来虚拟机迁移后的迁移个数比较情况。结果显示本文的DMS-VM迁移策略随着虚拟机请求个数从100到1 000的变化,它的迁移个数从370到2 000左右,大约只有5.0倍的增加。而其他的三个迁移策略的个数都是8.0倍以上的增加。

从这个结果表明, DMS-VM与其它三中策略比较起来，本文的迁移策略能够有效的减少动态虚拟机的迁移个数，这样它间接就减少了云数据中心的能源消耗情况。

图4 4种虚拟机迁移策略的迁移次数比较

3.4 云数据中心的能耗分析

图5显示了随着云计算应用的虚拟机请求数量的变化, 4种策略比较起来云数据中心的电力消耗情况，本文的策略在4种策略中是最节省能源的,在虚拟机个数为100的时候，大约只有4千瓦特小时(KWH)的能源消耗。 但是尽管如此, 云数据中心的能源消耗还是增加比较快， 这个是因为DMS-VM迁移策略了主要目的是为了使服务器的负载虚拟机负载最小和负载均衡，在这个过程中就存在一定的虚拟机迁移动作，这样云数据中心的电力的消耗情况也受到了影响。

图5 4种虚拟机迁移策略的能量消耗比较

3.5 SLA平均违规分析

云计算中，服务质量QoS必须保证,QoS的衡量标准主要通过服务等级协议的SLA Violations(SLA违规)来体现，SLA违规通过最小的吞吐量或者最大响应时间来表示。但是在云计算中针对不同的应用，表示方法也不完全一致,为了研究的需要，我们通过公式(7)来表示SLA违规。

SLAViolations=

(7)

SLA违规值的百分比将表明在客户有服务请求的时候，CPU并没有分配资源的比例，因此,为了云客户端增加QoS,我们的首要目标是减少SLA违规的值。图6显示了随着云计算应用的虚拟机请求数量的变化4种策略比较起来云数据中心的服务等级协议SLA的平均违规比较情况，结果表明随着虚拟机请求数目的增加，4种策略下的SLA的平均违规都是随机的变化，本文的迁移策略处于性能中的中等水平,尽管如此,它的SLA违规都是比较平稳的变化， 这个也表明它可以稳定的保证云平台的QoS。

图6 4种虚拟机迁移策略的SLA平均误差率比较

从上面的四个实验可以看出，DMS-VM虚拟机迁移策略既可以减少能量消耗,也可以使虚拟机均匀的分布到所有的服务器中，使的云数据中心的各个服务器的负载均衡,预防计算资源过于集中和聚集, 和常见的其他策略比较起来，性能处于优势, 这个是因为DMS-VM采用遗传算法的多目标优化问题，引入一个权重变量将多个目标求解转化为单目标求解,最终求出最满意的资源放置策略, 从而达到节省云数据中心的电力消耗与成本。

4 结论

针对云端的多种应用服务请求处于动态变化情形下，本文提出了一种云端的虚拟机动态迁移策略DMS-VM，采用遗传算法的目标优化作为虚拟机的主要迁移策略，并运用实验将本文算法与常见优化算法进行对比分析。实验表明DMS-VM能够有效减少物理主机的使用数量和虚拟机的迁移次数，保证QoS质量,减少SLA的违规, 降低数据中心能耗。未来的工作在虚拟机迁移策略中将考虑物理主机的内存大小，网络带宽和空余磁盘空间情况。