云平台下基于粒子群优化算法的虚拟机迁移模型

田祥宏 徐胜超

1(金陵科技学院计算机工程学院 江苏 南京 211169) 2(广州华商学院数据科学学院 广东 广州511300)

0 引 言

虚拟机迁移是云服务提供商构造节能云计算环境的常见技术[1-3]。物理主机状态检测、虚拟机选择和虚拟机放置等都是虚拟机迁移的重要步骤[4-7]。物理主机状态检测的含义是通过监视云平台的所有主机的物理资源使用状态来判断，采用一定的算法或者策略，把那些运行异常(超负载或低负载)的物理节点选择出来，形成候选迁移物理主机列表。虚拟机选择的含义是从异常的物理主机上选择出合适的虚拟机，形成候选迁移虚拟机列表。虚拟机放置的含义是将虚拟机选择阶段中选择出来的候选虚拟机列表按照一定的算法重新放置到云平台其他的正常状态下的物理节点。

从上述分析可以看出物理主机状态异常检测、虚拟机选择、虚拟机放置应该属于三个不同的过程，这三个过程都可以通过算法进行优化。物理主机状态检测可以通过物理资源使用率阈值管理策略等来进行优化；虚拟机选择可以通过考虑虚拟机尺寸与粒度、主机能量消耗情况、虚拟机迁移时间长短等策略进行优化；虚拟机放置，有些文献把它称为多目标优化问题或者称为经典装箱问题BPP(Bin Packing Problem)[8]，该过程也有很多智能算法进行优化，例如蚁群优化算法[9]、萤火虫群优化算法[10]、贪心算法[11]、稳定匹配算法[12]、蛙跳算法[13]、遗传算法[14]等。已提出的方法只能在云平台的总体能量消耗、虚拟机迁移次数、SLA违规率等目标指标上取平衡[9-14]。

结合虚拟机迁移的三个阶段，本文提出了基于粒子群优化的虚拟机迁移模型PSO-VMM，PSO-VMM在确定云平台的能量消耗的时候，考虑物理主机的硬件维度从单一的处理器扩展到内存大小、磁盘大小和网络带宽等。由于目前以Beloglazov等为团队开发的Cloudsim项目及其后续研究在云平台的虚拟机迁移模型研究方面处于世界领先地位[4-7]，所以PSO-VMM参考了Cloudsim中的开发思路和性能测试指标。配合前面的物理主机状态检测阶段的鲁棒局部归约检测LRR方法和虚拟机选择阶段最小迁移时间选择MMT的优化方法，构成了一个完整的新型虚拟机迁移模型PSO-VMM。PSO-VMM虚拟机迁移模型通过Cloudsim来实现和仿真,仿真结果表明通过粒子群算法PSO-VMM优化策略形成新的虚拟机迁移模型之后，它比常见的BenchMark虚拟机迁移策略可以更好地节省云平台的能量消耗,减少了虚拟机迁移次数。

1 虚拟机迁移的相关工作

目前学术界在利用虚拟机动态迁移的手段来节省云数据中心的能量消耗、构建绿色云计算环境方面进行了大量的研究。

早期的虚拟机迁移相关文献在设计云平台能量消耗模型时往往会考虑比较单一的物理资源维度，例如单一物理资源:CPU利用率或者处理器温度发热;后续考虑问题的维度扩展到了内存利用率,磁盘空间大小等。近三年来还有考虑更多的因素,例如网络带宽因素、网络设备接口能量消耗等。但是在虚拟机迁移的时候它们并没有考虑到虚拟机迁移的内部逻辑、数据依赖关系、软件因素[15]。

近五年来开始出现大量的采用新型的算法进行优化虚拟机迁移过程的文献，例如基于贪心阈值边界[16]、温度感知[17]、安全检测[18]、稳定匹配[12]、任务映射[19]、数据依赖[20]、萤火虫群优化[10]、虚拟机关联性[21]等的虚拟机迁移策略。这些文献在研究思路、测试指标等方面大部分都参考了Cloudsim项目,分别有：以降低能量消耗为最终目标；以减少SLA违规率为目标；以降低虚拟机迁移次数为目标或者其中几个。本文的基于粒子群优化的PSO-VMM虚拟机迁移策略也是参考了Cloudsim项目的研究思路，在能量消耗模型、智能算法优化等方面进行了改进，PSO-VMM以降低能量消耗为目标函数。

PSO-VMM是一种既考虑了硬件因素，也考虑了软件因素的虚拟机迁移策略。硬件方面其考虑的问题维度也是常见的处理器使用率、内存使用率、网络带宽大小；软件方面考虑了粒子群算法的优势等,它是一种考虑了软硬因素结合的带智能算法优化的虚拟机迁移策略。

2 PSO-VMM的工作背景与相关术语

2.1 PSO-VMM的能源消耗模型

云平台主要由大量的物理主机组成，所以其能量消耗主要由物理主机的所有部件的能量消耗组成。文献[22]中认为一个物理服务器(双核CPU、四条内存、一个磁盘、两个PCI插槽、一个主板等)所消耗的能量大约为CPU占41%，内存占18%，磁盘占7%,PCI插槽占23%，主板占12%。基于这个思路，PSO-VMM策略中设计的物理主机的能量消耗数学模型如式(1)-式(6)所示。

E(Ucpu)=Eidle+(Emax-Eidle)Ucpu

(1)

(2)

E(Umem)=Eidle+(Emax-Eidle)Umem

(3)

E(Udisk)=Eidle+(Emax-Eidle)Udisk

(4)

E(Ubw)=Eidle+(Emax-Eidle)Ubw

(5)

Ehost=E(Ucpu)+E(Umem)+E(Udisk)+E(Ubw)

(6)

其中：Ucpu(t)、Umem(t)、Udisk(t)、Ubw(t)表示物理主机在t时刻的CPU使用率、内存使用率、磁盘使用率、网络带宽使用率，0≤Ucpu(t),Umem(t),Udisk(t),Ubw(t)≤1。Eidle表示物理主机CPU、内存、磁盘空间、网络带宽在空闲时的能量消耗，即Ucpu(t)=0、Umem(t)=0、Udisk(t)=0、Ubw(t)=0的时候。Emax表示物理主机在满负载时的能量消耗，即Ucpu(t)=100%、Umem(t)=100%、Udisk(t)=100%、Ubw(t)=100%的时候。mipsi,c是第i个虚拟机VMi的第c个处理单元的mips请求情况。MIPSj,c是第j个物理主机Mj的第c个处理单元的整体的MIPS计算能力。pei表示虚拟机VMi的处理单元的数量，PEj表示物理主机Mj的处理单元的数量，rj(t)表示分配到物理主机Mj的虚拟机的索引集合。

一个虚拟机请求的MIPS的数量是随着应用程序变化而变化的，所以物理主机的资源使用率也应该是随着应用程序的变化而变化，因此统计物理服务器的能量消耗必须在一定的时间段内，这样根据式(1)可以演化为式(7)。

Ehost(t)=E(Ucpu(t))+E(Umem(t))+

E(Udisk(t))+E(Ubw(t))

(7)

这样第j个物理主机在[t0,t1]时间段的总体能量消耗Ehost可以按照式(8)来计算。

(8)

整个云平台的能量消耗为式(9)。

(9)

2.2 云平台的SLA违规比率

PSO-VMM采用了2个方法来评价SLA违规。

(1) 单活动主机SLA违规时间SLA violation Time per Active Host(SLATAH)。

(2) 虚拟机迁移后的性能降低情况Performance Degradation due to Migrations(PDM)。

所以最终SLA违规的具体值可以通过式(10)来计算。

SLAV=SLATAH×PDM

(10)

式中：SLATAH是活动主机的CPU具有100%的使用率所占的比例；PDM是整个系统因为虚拟机迁移后的性能降低情况。

2.3 SLA违规比率及能量消耗联合指标

参考了Cloudsim中的ESV(Energy and SLA Violations)方法来评价整个云平台的性能,ESV的计算公式如下：

ESV=E×SLAV

(11)

式中：E是云平台的整体能量消耗；SLAV是式(10)中所表达的SLA违规情况,ESV体现了能量与SLA违规的平衡。

3 PSO-VMM的虚拟机迁移策略描述

3.1 PSO-VMM虚拟机迁移约束条件

假设有n个虚拟机的集合{VMi|i=1,2，…，n}在虚拟机放置阶段要重新分配到云平台的m个物理主机{Mj|j=1,2,…,m}上运行，每个虚拟机都请求pei个处理单元，请求包括mipsi个计算需求，那么启发式算法的搜索空间为mn。本文把能量消耗模型的考虑因素不限制于物理主机的CPU使用率这个单一维度上，扩展到物理资源的维度包括内存大小、磁盘空间大小、网络带宽大小等。

PSO-VMM算法的目标是发现最优的能量消耗的解决方案，文献[23]指出，必须把整个云平台的所有多维度的物理资源的使用效率提高到最佳才是最优的解决方法，所以本文定义了欧几里得距离如下：

(12)

这个欧几里得距离δ体现了多维物理资源利用率和总体能量消耗的平衡。如果能够使得δ的值最小，则整个云平台的能量消耗也最小最节能，所以粒子群优化方法的目标函数如下：

(13)

(14)

为了满足其他的资源限制，每个维度的资源还必须满足下面的约束条件：

(15)

(16)

(17)

(18)

3.2 PSO-VMM虚拟机迁移策略描述

粒子群算法的每个粒子根据自身记忆和群体知识搜索整个解空间，通过迭代方式寻找并收敛到最优解。本文把粒子群算法应用到云平台的虚拟机放置过程中，其目标函数为整体能量消耗最小，PSO-VMM方法可以使整个云平台的物理资源得到公平的分配与使用。

3.2.1粒子群优化算法

在粒子群算法中，潜在的解决办法称为粒子，该粒子通过沿着当前的最佳粒子在解空间之间移动。粒子因为具有记忆能力，保持了它们之前的一些状态，利用式(19)，粒子群算法可以使每次的位置越来越接近解空间。

(19)

(20)

每个粒子都有一个初始的随机飞行速度，粒子的移动受两个随机的权重因素所影响：个体性和社会性。个体性决定了粒子有返回到之前的位置的趋势，社会性决定了粒子具有飞到相邻的最好位置的趋势。由于粒子群算法很少需要调整参数，所以它被广泛应用到各个科学领域，粒子群算法的符号具体含义见表1。详细的关于粒子群算法的定义这里不再赘述，本文主要讨论其如何应用到虚拟机放置过程中。

表1 基于粒子群算法的虚拟机放置方法相关符号

3.2.2粒子定义

(21)

3.2.3位置更新

PSO-VMM在第t次迭代的过程中，有如下：

(22)

(23)

(24)

(25)

可见，局部最优的概率和全局最优的概率都应该大于平均概率，所以0.5

整个粒子群算法的位置更新可以按照下面的步骤完成：

1.r=rand();

根据虚拟机放置的目标函数，适应度函数通过式(12)所提到的欧几里得距离δ来表示。

3.3 PSO-VMM策略的具体工作流程

本文基于粒子群算法优化的虚拟机迁移策略PSO-VMM的具体流程如图1所示。

图1 PSO-VMM虚拟机重新分配的运行流程

主要有四个步骤：

步骤1初始化粒子：随机产生n个虚拟机的序列，在每个序列中，该虚拟机按照首次适应算法完成资源的第一次分配；那么这n个序列形成了一个粒子群。

步骤2评价每个粒子的适应度函数，根据每个粒子的初始位置，完成每个粒子的pbesti和gbesti的位置的初始化。

步骤4如果迭代的次数大于指定的数值，则循环停止，否则继续执行步骤2到步骤3，图1形象地表示了基于粒子群优化的虚拟机重新分配过程。

4 仿真实验与性能分析

4.1 仿真环境的设置

因为PSO-VMM基于粒子群优化的算法是在虚拟机迁移过程中运用的，所以进行PSO-VMM实验分析必须构造云平台的虚拟机迁移场景。本文参考了Cloudsim工具包，采用的物理主机的能量消耗模型如2.1节所描述的,Cloudsim3.0是基于Java的开发平台,其实现过程中有一个称之为Local Agent本地代理的模块,通过更改这个模块的代码,即可以实现粒子群优化的PSO-VMM策略。

被模拟的云平台主要由四类物理服务器组成，物理服务器总数为800个，由于虚拟机迁移时考虑的问题维度包括CPU、内存、磁盘空间及网络带宽，所以物理服务器配置如表2所示。在粒子群算法的初始参数中，设置资源类型维度为：d=4,ubest1=0.5，ubest2=0.7，ubest3=0.5，ubest4=0.5，粒子群中粒子最大个数为20，迭代更新的次数为30。

表2 云平台的物理服务器配置

虚拟机迁移周期设置为10分钟一次，一共运行24个小时,每次统计一天内的能量消耗,在一周内重复运行五次，一周内每天虚拟机请求的个数如表3所示。

表3 一周内不同的虚拟机请求个数

云客户端运行的可以是一个Web应用程序或者其他一个具有不同类型工作负载的应用程序,整体来讲包括四类不同虚拟机，如表4所示。

表4 虚拟机类型配置

4.2 评测标准与比较对象

前面提到PSO-VMM是一种虚拟机迁移过程中的组合策略，它必须与虚拟机迁移的其他阶段的算法组合起来使用，得到新的虚拟机迁移策略，它的主要评价指标：(1) 总体的欧几里得距离比较;(2) 云平台的总体能量消耗;(3) 云平台的虚拟机迁移次数;(4) 云平台的SLA违规率分析;(5) 能量与SLA违规的联合指标ESV,这五个指标可以体现节能的虚拟机迁移策略的性能好坏。

目前在虚拟机迁移技术中，相关文献已经表明局部回归检测方法LRR在物理主机状态检测阶段最优,最小迁移时间选择方法MMT在虚拟机选择阶段最优,再结合递减装箱方法完成虚拟机放置,我们称之为LRR-MMT-BFD策略,它的实现结果在Anton Beloglazov博士的相关文献都有发表,见文献[5，7]，它应该作为本文的PSO-VMM策略的首要比较对象。

我们还与近年来的其他虚拟机放置策略进行了比较，例如萤火虫群优化GSO-VMM[10]、稳定匹配Stable-Matching[12]、遗传算法GA-VMM[14]、蚁群优化的虚拟机放置ACS-VMM[9]等，分析这些智能计算优化方法对云平台的性能改变情况。综上所述，本实验一起涉及到的虚拟机迁移模式如表5所示。包括PSO-VMM、LRR-MMT-BFD、GSO-VMM、Stable-Matching、GA-VMM、ACS-VMM一共6个虚拟机迁移模式。

表5 PSO-VMM虚拟机迁移策略的性能比较对象

4.3 仿真结果与性能分析

4.3.1欧几里得距离分析

欧几里得距离可以根据式(12)完成计算，δ值越小，表明云平台的物理资源利用效率越高。如图2所示，随着虚拟机个数的增加，δ值缓慢的增加。

图2 PSO-VMM虚拟机迁移的欧几里得距离比较

与LRR-MMT-BFD递减装箱虚拟机放置方法比较起来，粒子群优化方法PSO-VMM的δ值明显要低，而且当虚拟机个数增到50到100个时，δ值增加得更慢，LRR-MMT-BFD的δ值的增加已经接近线性。从这里可以看出粒子群优化的虚拟机放置方法性能优于传统的启发式经典装箱虚拟机放置方法。

4.3.2云平台的总体能量消耗

基于PSO-VMM的虚拟机迁移模型一周之内的总体能量消耗比较如图3所示。从图3可以看出，有了粒子群算法优化后，PSO-VMM迁移模型比Cloudsim中的LRR-MMT-BFD迁移策略在总体能量消耗上要节约25%到30%，比Stable-Matching策略、GA-VMM策略和ACS-VMM策略的能量消耗也要低，虽然周一到周五之间的数据有一定的波动，但是整体趋势是PSO-VMM迁移策略最节省云平台的能量消耗。分析原因是通过PSO-VMM最小欧几里得距离的目标函数的优化，反复迭代后，所有物理服务器的总体能量消耗自然减少。

图3 各类虚拟机迁移策略的总能量消耗比较

4.3.3虚拟机迁移次数

图4显示了在一周的五天之内PSO-VMM的虚拟机迁移次数都低于LRR-MMT-BFD策略、GA-VMM迁移策略、GSO-VMM策略；而Stable-Matching策略迁移次数则处于性能中等水平，ACS-VMM策略虚拟机迁移次数最小。

图4 各类虚拟机迁移策略的虚拟机迁移次数

原因是PSO-VMM策略中设计的能量消耗模型考虑问题的维度已经很广泛了，包括处理器、内存、磁盘和网络带宽，所以在物理主机状态检测和虚拟机选择阶段中自然减少了虚拟机迁移次数。

另外GSO-VMM策略、GA-VMM策略和ACS-VMM策略的优化主要在虚拟机放置阶段，要想减少虚拟机迁移次数，必须像Stable-Matching策略在虚拟机选择阶段、物理主机状态检测阶段完成优化。

4.3.4SLA违规率分析

从图5可以看出，周一到周五，PSO-VMM迁移策略的SLA违规率比LRR-MMT-BFD迁移策略要低，有这样的实验结果的原因是PSO-VMM比递减装箱办法的优化能力要强，在物理主机状态检测阶段尽量避免物理资源使用率超过100%的情况，从而间接地避免SLA违规事情的发生。

图5 各类虚拟机迁移策略的SLA违规率比较

GSO-VMM策略、Stable-Matching策略、GA-VMM策略和ACS-VMM策略在虚拟机放置阶段都采用另外的优化算法，这样整个云平台的SLA违规率自然会比LRR-MMT-BFD迁移策略要低，它们的SLA违规率在某些时候还优于PSO-VMM策略，PSO-VMM以降低能量消耗为最终目标函数，所以会牺牲一些SLA违规率的增加。

4.3.5能量与SLA违规的联合指标ESV

ESV指标是体现云服务提供商的高服务质量、低SLA违规比率和总体能量消耗平衡的指标，公式为：

ESV=E×SLAV

从图6中的结果可以看到，PSO-VMM迁移策略的ESV也要低于LRR-MMT-BFD迁移策略。这个实验结果很明显地表明在虚拟机放置阶段中智能算法优化对云平台的物理资源利用效率提高的重要性。GSO-VMM策略、Stable-Matching策略、GA-VMM策略和ACS-VMM策略是近两三年提出的虚拟机放置优化算法，它们虚拟机迁移的各个阶段都有优化，自然比六七年前的LRR-MMT-BFD迁移策略性能优秀，ACS-VMM迁移策略的ESV最低，它比单一目标函数的PSO-VMM迁移策略在ESV方面要低。

图6 各类虚拟机迁移的SLA与能量消耗联合指标ESV

5 结 语

本文建立了针对云平台的虚拟机迁移的多维度物理资源的能量消耗模型。利用粒子群优化算法，以总体能量消耗最小作为目标函数，配合在物理主机状态检测和虚拟机选择阶段的鲁棒回归检测方法LRR及最小时间迁移选择策略MMT，即形成了一个新型的虚拟机迁移模型PSO-VMM。仿真实验表明PSO-VMM比近三年来的虚拟机迁移策略在总体能量消耗、虚拟机迁移次数上有明显优势，SLA违规比率、ESV等指标只有少量的增加，PSO-VMM基于粒子群算法的虚拟机迁移策略可以为其他节能绿色云平台的构造作为参考。