云环境中多目标优化的虚拟机放置算法

蔺凯青　李志华　郭曙杰　李双俐

摘 要：虚拟机放置（VMP）是虚拟机整合的核心，是一个多资源约束的多目标优化问题。高效的VMP算法不仅能显著地降低云数据中心能耗、提高资源利用率，还能保证服务质量（QoS）。针对数据中心能耗高和资源利用率低的问题，提出了基于离散蝙蝠算法的虚拟机放置（DBA-VMP）算法。首先，把最小化能耗和最大化资源利用率作为优化目标，建立多目标约束的VMP优化模型;然后，通过效仿人工蚁群在觅食过程中共享信息素的机制，将信息素反馈机制引入蝙蝠算法，并对经典蝙蝠算法进行离散化改进;最后，用改进的离散蝙蝠算法求解模型的Pareto最优解。实验结果表明，与其他多目标优化的VMP算法相比，所提算法在使用不同数据集的情况下都能有效降低能耗，提高资源利用率，实现了在保证QoS的前提下的降低能耗和提高资源利用率两者之间的优化平衡。

关键词：虚拟机放置;多目标优化;离散蝙蝠算法;数据中心;云计算

中图分类号： TP393.02;TP301.6文献标志码：A

Multi-objective optimization algorithm for virtual machine

placement under cloud environment

LIN Kaiqing， LI Zhihua*， GUO Shujie， LI Shuangli

（School of IoT Engineering， Jiangnan University， Wuxi Jiangsu 214122， China）

Abstract： Virtual Machine Placement （VMP） is the core of virtual machine consolidation and is a multi-objective optimization problem with multiple resource constraints. Efficient VMP algorithm can significantly reduce energy consumption， improve resource utilization， and guarantee Quality of Service （QoS）. Concerning the problems of high energy consumption and low resource utilization in data center， a Discrete Bat Algorithm-based Virtual Machine Placement （DBA-VMP） algorithm was proposed. Firstly， an optimization model with multi-object constraints was established for VMP， with minimum energy consumption and maximum resource utilization as optimization objectives. Then， the pheromone feedback mechanism was introduced in the bat algorithm by emulating the pheromone sharing mechanism of artificial ant colonies in the foraging process， and the bat algorithm was improved and discretized. Finally， the improved discrete bat algorithm was used to solve the Pareto optimal solutions of the model. The experimental results show that compared with other multi-objective optimization algorithms for VMP， the proposed algorithm can effectively reduce energy consumption and improve resource utilization， and achieves an optimal balance between reducing energy consumption and improving resource utilization under the premise of guaranteeing QoS.

Key words： Virtual Machine Placement （VMP）; multi-objective optimization; discrete bat algorithm; data center; cloud computing

0 引言

云数据中心规模的快速增长导致其能耗不断攀升，高能耗成了数据中心亟需解决的主要问题之一[1]。数据中心物理主机的平均CPU使用率只有15%～20%，大部分处于空闲状态[2]。处于空闲状态的主机一般消耗其峰值能耗的70%[3]，因此，关闭空闲主机可有效降低能耗，提高资源利用率。另一方面，虚拟机对资源的请求是随机的，当多个虚拟机同时请求资源时，整个数据中心的资源需求急剧上升，关闭过多的主机又会导致预留资源紧张，虚拟机资源请求得不到满足，从而违背云服务供应商与用户签订的服务等级协议（Service Level Agreement， SLA）。因此“降低能耗、提高资源利用率和保证服务质量”三者相互制约、互相矛盾，实现三者之間的优化平衡是云数据中心资源管理所追求的目标。

虚拟机整合是云数据中心资源管理的主要手段。虚拟机整合包括过载物理主机检测、虚拟机选择、虚拟机放置和低负载物理主机关闭四个子过程[3]，其中虚拟机放置是虚拟机整合的核心，旨在解决虚拟机“从哪里来到哪里去”的问题。传统的虚拟机放置算法大多将虚拟机放置建模为装箱问题[3-4]，并使用降序首次适应（First Fit Decreasing， FFD）[3]算法或降序最佳适应（Best Fit Decreasing， BFD）[4]算法等启发式算法对其进行求解，其主要目的是通过最小化活动物理主机的数量来降低能耗。但大规模云数据中心虚拟机放置是NP-hard问题[4]，传统算法存在容易陷入局部最优的不足[5]。因此文献[6-8]使用智能算法求解该问题：文献[6]将最小化活动物理主机的数量和最小化主机剩余资源作为优化目标并建立优化模型，通过遗传算法与首次适应算法结合求解该优化模型，但该方法仍把虚拟机放置看作多维装箱问题，且执行放置后会导致部分主机负载过高反而影响服务质量;文献[7]使用蚁群算法来求解该问题，将最小化迁移次数和活动主机的数量作为优化目标，目的是优先将虚拟机放置在资源利用率高的物理主机中，达到降低能耗的目的，但该方法会导致剩余活动主机的资源利用率过高，增加了主机发生过载的风险;文献[8]建立了最小化能耗和最小化主机剩余资源的优化模型，并采用离散萤火虫算法求解该优化模型，有效改善了数据中心的资源利用率且降低了能耗。总之，文献[6-8]均采用线性加权将多目标问题转换为单目标优化进行求解，但在多目标问题中，一个目标的优化往往会导致另一个目标的劣化，因此，需要求出一组Pareto最优解，即对一个或多个目标不可能进一步优化而对其他目标不至于劣化的最优解的集合。

针对以上研究工作中存在的不足，本文提出了基于离散蝙蝠算法的虚拟机放置（Discrete-Bat-Algorithm-based Virtual Machine Placement， DBA-VMP）算法。首先，通过分析云数据中心负载数据的特征，建立了以最小化能耗和最小化资源剩余率为优化目标的多目标优化模型;同时，对经典蝙蝠算法进行离散化改进，用改进后的蝙蝠算法求解该模型的Pareto最优解，即最佳虚拟机放置方案;另外，在算法中引入了蚁群算法的全局信息素更新规则，为整个种群提供正反馈机制，加速算法进化。实验结果表明，DBA-VMP算法在保证服务质量的前提下，在降低能耗和减少资源浪费两者之间取得了理想的平衡。

1 虚拟机放置优化模型

1.1 数据中心描述

假设数据中心部署在物理主机hj（1≤j≤n）中的所有虚拟机集合为Vj。主机的资源使用量是该主机上部署的所有虚拟机请求量的总和，则hj的某类资源利用率可表示為式（1）：

Urj=1Crj ∑vmi∈Vjdri（1）

其中：r∈RS且RS={cpu，mem，bw}是主机资源类型（CPU、内存和带宽资源）的集合;Urj是主机hj的r类资源利用率;Crj为hj的r类资源配置容量;dri表示虚拟机vmi（1≤i≤m）请求的r类资源。

物理主机的功率与CPU利用率可近似为线性关系[4]，且可表示为式（2）：

P（Ucpuj）=（Pfullj-Pidelj）×Ucpuj+Pidelj（2）

其中：Pfullj和Pidelj分别代表主机hj在满载和空载时的功率;Pj（Ucpuj）代表hj在CPU利用率是Ucpuj时的功率。

整个数据中心的能耗可定义为式（3）：

f1（X）=∑nj=1[∫ t 1t0P（Ucpuj（t）） dt]（3）

其中：矩阵X=（xij）m×n表示虚拟机与物理主机之间的映射关系且xij∈{0，1}，如果虚拟机vmi放置在物理主机hj上则xij=1，否则xij=0。 ∫ t 1t0P（Ucpuj（t）） dt表示hj在t0至t1时间段内的能源消耗[4]，Ucpuj（t）表示t时刻hj的CPU利用率。

1.2 问题定义

当具有不同资源需求的虚拟机集合放置在某台物理主机上时，有可能会使主机的某类资源利用率过高，而其他资源还有大量剩余，导致主机负载不均衡，造成资源浪费。本文使用Wj表示负载不均衡造成的主机资源剩余的代价函数，定义为式（4）：

Wj=max Rrj-min{Rcpuj，Rmemj，Rbwj}; r∈RS（4）

其中：Rrj表示hj的r类资源剩余率。使用式（1）和式（4）来建立资源利用率的目标函数，使得主机在提高利用率的同时保证剩余资源的负载均衡。

式（5）表示整个数据中心资源利用率的优化目标函数：

f2（X）=∑nj=1[∑r∈RS（Trj-Urj）-|lg Wj|]（5）

其中： Trj表示主机hj的r类资源使用率的阈值。由式（4）可知，Wj∈[0，1]，但对数函数在零点未定义，所以本文将Wj的值域定义在[0.001，1]内，使得|lg Wj|与∑r∈RS（Trj-Urj）属于相同值域。则虚拟机放置的多目标优化模型可描述为式（6）：

min F（X）=（f1（X）， f2（X））

s.t.∑nj=1xij=1; i=1，2，…，m

∑vmi∈Vjdri

其中：第一个约束条件表示一台虚拟机只能放置在一台物理主机中;第二个约束表示主机中虚拟机请求的r类资源不能超过物理主机r类资源的总容量。

Pareto 优化的目的是找到对一个或几个目标函数不可能进一步优化而对其他目标不至于劣化的最优解的集合。设xA，xB是多目标优化问题min y=（f1（x）， f2（x），…， fm（x））T的可行解，若i∈{1，2，…，m}， fi（xA）≤fi（xB），且 j∈{1，2，…，m}， fj（xA）

2 离散蝙蝠算法

蝙蝠算法（Bat Algorithm， BA）[10]是根据微型蝙蝠的回声定位行为，并结合一些现有群体智能算法的优点提出的一种具有全局优化能力的算法。该算法首先初始化一组随机解，然后通过迭代搜索寻找当前最优解，并运用随机飞行在最优解附近寻找局部最优新解，提高了算法的局部搜索能力。与粒子群算法和遗传算法相比，BA结构简单、参数少，且在有效性和准确性方面有明显优势[10]。 BA的随机飞行机制有助于在最优解与可行解之间找到一个平衡，其全局寻优能力可实现在整个解空间中搜索到最佳的虚拟机放置方案。针对虚拟机放置问题，本文提出了一种改进的离散蝙蝠算法（Discrete BA， DBA）。

2.1 BA的离散化

BA的离散化操作包括两部分：对种群个体的离散化操作和对迭代公式的离散化。

首先，对每个个体进行离散化操作。蝙蝠b在第t次迭代后所处的位置Xtb=（xb，i， j）m′×n表示虚拟机和物理主机之间的映射关系，其中，m′表示待迁移虚拟机队列长度，n是整个数据中心物理主机的数量，蝙蝠b通过迭代不断调整自己的位置来搜索新的解空间，同时不断更新整个群体Xt={Xt1，Xt2，…，XtN}经历过的最好位置的集合PS。

其次，对迭代公式进行离散化操作。每只蝙蝠b都有其自身的速度Vtb=（vtb，i， j）m'×n，在經典BA算法中，蝙蝠b根据式（7）来更新第t次迭代后的速度：

Vtb=Vt-1b+（Xt-1b-X*）fb（7）

其中：Xt-1b表示第t-1次迭代中蝙蝠b所处的位置;X*∈PS是蝙蝠种群目前找到的全局最优解。初始化时每只蝙蝠随机分配一个脉冲频率fb并根据式（8）来更新：

fb=fmin+（fmax-fmin）β（8）

其中：β∈[0，1]是服从均匀分布的随机变量。本文遵循经典BA的迭代更新思想，对式（7）进行了离散化操作如式（9）所示。

vtb，i=xor（vt-1b，i，xt-1b，i）， fb≥rand

xor（vt-1b，i，x*，i），其他 （9）

其中：行向量vtb，i表示Vtb的第i个分量，行向量xt-1b，i是Xt-1b的第i个分量，即蝙蝠b在第t-1次迭代后虚拟机vmi的部署向量。 xor表示异或操作，由于一台虚拟机只能放置在一台物理主机上，为了确保这个约束条件，本文使用异或操作对速度进行更新，并对该操作作了相应的改进，假设S1和S2是两个p×q的映射矩阵，行向量s1，i和s2，i分别表示S1和S2的第i个分量，则xor操作如式（10）：

xor（s1，i，s2，i）=0， s1，i=s2，i

s1，i，s1，i≠s2，i & r≥rand

s2，i，s1，i≠s2，i & r

其中：r和rand都是区间[0，1）的随机数，当s1，i和s2，i相同时，则通过xor操作更新为零向量;否则随机选择某一个向量作为运算结果。经典BA通过将Vtb和Xt-1b相加得到第t次迭代后蝙蝠b的位置Xtb，本文对Xtb的离散化改进如式（11）所示。

xtb，i=vtb，i， r

xt-1b，i，其他 （11）

其中： 行向量xtb，i表示蝙蝠b在第t次迭代后虚拟机vmi的部署向量;vtb，i是第t次迭代后的速度向量; r∈[0，1）是随机数;R是常数。

在每次迭代中，都会产生一个随机数rand1，如果rand1的值大于脉冲发射率rb，则进行局部搜索，从而加速解空间的搜索过程，提高最优解的质量，本文将局部搜索过程离散化为式（12）：

xnew，i=xor（xo1，i，xo2，i）（12）

其中：行向量xnew，i是矩阵Xnew的第i个部署向量;矩阵Xo1和Xo2是最优解集合PS中的任意两个最优解，xo1，i和xo2，i分别表示矩阵Xo1和Xo2中虚拟机vmi的部署向量。 Xnew是产生的新解。如果新解优于旧解且产生的随机数rand2的值小于响度值Ab，则接受新解，更新响度Ab和脉冲发射率rb，如式（13）和式（14）。

Atb=αAt-1b（13）

rtb=r0b[1-exp（-γ（t-1））]（14）

其中： α和γ是常数，0<α<1且γ>0。r0b∈[0，1]是蝙蝠b的初始脉冲速率。

2.2 信息素矩阵

在利用DBA求解虚拟机放置的过程中，本文引入了蚁群算法的信息素矩阵Τt=（τtij）m×n，保留迭代过程中获得的历史经验，让所有蝙蝠可以共享搜索过程中积累的信息，加快算法的收敛速度。τtij表示第t次迭代中虚拟机vmi放置在hj上积累的信息素。在种群迭代过程中，信息素矩阵的更新如式（15）所示。

τtij=

φ·τt-1ij+（1-φ）·（Fmaxpower-f1（X*）），x*，i， j=1

τt-1ij，其他 （15）

其中：φ∈[0，1]为权重参数，用来调节第t-1次迭代后积累的信息素与第t次迭代后产生的信息素所占的比重;Fmaxpower是整个数据中心的最大能耗值，如果第t次迭代后，在最优映射矩阵X*中vmi放置在hj上，即x*，i， j=1，则更新τtij;否则保持第t-1次迭代中的信息素值。

2.3DBA

本文将种群的迭代过程分为两部分：随机迭代搜索和启发式迭代搜索。在每次迭代中，蝙蝠b随机选择某一种迭代方式来搜索最优解。在随机搜索中，蝙蝠b根据式（10）来更新自身的速度;在启发式搜索中，蝙蝠b的速度更新公式如式（16）所示。

vtb，i=

xor（vt-1b，i，xt-1b，i）， ∑nj=1xt-1b，i， j·τt-1ij>∑nj=1x*，i， j·τt-1ij

xor（vt-1b，i，x*，i），其他 （16）

如果在矩阵Xt-1b中，虚拟机vmi放置在了物理主机hj上，则xt-1b，i， j=1;否则xt-1b，i， j=0。如果矩阵Xt-1b中虚拟机vmi部署积累的信息素值大于矩阵X*中vmi部署积累的信息素值，则对向量vt-1b，i和xt-1b，i进行异或操作。

式（17）表示了在启发式搜索中第t次迭代后，主机和虚拟机的映射关系矩阵Xtb。

xtb，i=vtb，i， ∑nj=1vtb，i， j·τt-1ij>∑nj=1xt-1b，i， j·τt-1ij

xt-1b，i，其他 （17）

算法1详细说明了DBA迭代寻找最优解的总体框架。其中，Xt-1表示第t-1次迭代后所有蝙蝠的位置的集合，PS是种群当前的Pareto最优解的集合，ran，rand1，rand2∈[0，1）是随机数。

算法1 DBA。

输入 Xt-1，PS;

输出 Xt 程序前

for all Xt-1b∈Xt-1 do

if ran

use equation（9） to update Vtb and equation（11） to generate Xtb

else

use equation（16） to update Vtb and equation（17） to

generate Xtb

end if

if rand1>rt-1b then

random select a solution from PS as Xo1， Xo2

use equation （12） to generate Xnew

end if

if rand2

accept Xnew and use （13） （14） to updatertb， Atb

end if

end for

return Xt程序后

3 基于DBA的虚拟机放置方法

根据主机的资源使用情况，数据中心的活动物理主机分为低负载、正常以及过载三类[3]。本文使用Ho表示过载物理主机集合，Hn表示正常负载的主机集合，Hu表示低负载主机集合，Hs表示休眠主机集合。

图1为基于离散蝙蝠算法的虚拟机放置（DBA-VMP）算法的流程。算法2是伪代码描述，其中：X*表示迭代完成后主机和虚拟机的最终映射关系，Vmig表示Ho中需要迁移的虚拟机集合。DBA-VMP为Vmig集合中的每台虚拟机找到合适的目的主机hd，且hd∈Hn∨Hu∨Hs，及时解除Ho中所有主机的过载风险。在低负载物理主机关闭过程中，Vmig表示某台低负载主机hu∈Hu中部署的全部虚拟机集合，如果DBA-VMP能为所有的虚拟机找到目的主机hd，且hd∈Hn∨Hu，则将hu关闭;否则不执行迁移操作。在迭代过程中，本文使用了文献[11]提出的非支配排序和拥挤距离算法来求解Pareto解集。

在算法2的复杂度分析方面，因为算法1的时间复杂度是O（m·n2），其中m表示种群的数量，n代表待迁移虚拟机的长度;非支配排序和拥挤距离（non-dominated sorting and crowding distance）的时间复杂度分别为O（m2）和O（2m log（2m）），迭代次数为I，所以整个算法的时间复杂度为O（I·m·（n2+m））。

算法2 基于离散蝙蝠算法的虚拟机放置。

输入 Vmig ;

输出 X*。程序前

initialize X0b，PS，V0b （b=1，2，…，N）

initialize objective functions f1（X0b）， f2（X0b）

while t

use Algorithm 1 to generate Xtb

use equation （3）～（4） to update f1（Xtb），f2（Xtb）

use non-dominated sorting and crowding distance to update Pareto

solutions PS

use equation（15） to update Τt

select a solution X* from PS

return X* 程序后

4 实验与结果分析

4.1 评价指标

本文采用六种性能评价指标[4]來评价DBA-VMP算法的性能：服务等级协议违例率（SLA Violations， SLAV）、能源消耗（Energy Consumption， EC）、虚拟机迁移次数（Virtual Machine Migrations， VMM）、物理主机的服务等级协议违例时间（SLA violation Time per Active Host， SLATAH）、迁移虚拟机导致的虚拟机性能下降（Performance Degradation due to Migrations， PDM）、服务质量和能耗的综合评价指标（Energy consumption and SLA Violations， ESV）。

SLATAH用来衡量主机提供的服务质量，如式（18）所示：

SLATAH=1n∑nj=1TsjTaj（18）

其中： n代表活动物理主机的数量;Taj代表活动主机hj运行的时长;Tsj表示hj的CPU资源过载产生的SLA违背的时长。PDM表示虚拟机因迁移导致的性能下降程度，如式（19）所示：

PDM=1m∑mi=1ccpuidcpui（19）

其中： m代表虚拟机的数量;dcpui代表虚拟机vmi请求的CPU资源容量;ccpui代表因迁移导致的vmi未被满足的CPU资源容量。

SLAV综合评价单日内数据中心的服务质量，如式（20）所示：

SLAV=SLATAH×PDM（20）

ESV指标如式（21）所示：

ESV=EC×SLAV（21）

其中，EC代表整个数据中心一天的能源消耗，EC值越低代表数据中心运维成本越低。

4.2 实验配置

CloudSim是一种云环境的开源仿真工具[12]。本文模拟了一个由800台异构物理主机组成的数据中心，根据资源配置的不同分为Hp ProLiant ML110 G4（Intel Xeon 3040 2cores 1860MHz，4GB）和Hp ProLiant ML110 G5（Intel Xeon 3075 2cores 2260MHz，4GB）两种。此外，该平台还创建了四种不同类型的虚拟机，分别是High-CPU Medium Instance（2500MIPS，0.85GB）、Extra Large Instance（2000MIPS，3.75GB）、Small Instance（1000MIPS，1.7GB）和Micro Instance（500MIPS，613MB）。本文采用的实验数据来自Bitbrains[13]数据集和Alibaba Cluster Data V2018[14]数据集。

4.3 实验结果及分析

本文将DBA-VMP同FFD[3]、多资源组合排序的首次适应遗传算法（Combinatorial Order First-Fit Genetic Algorithm， COFFGA）[6]、使用蚁群系统的虚拟机放置（Ant Colony System-based VMP， ACS-VMP）算法[7]和资源使用率预测感知的最适降序（Utilization Prediction-aware BFD， UPBFD）算法[15]这四种虚拟机放置算法进行对比。为了获得有效的对比结果，将5种放置算法结合四分位距（InterQuartile Range， IQR）[4]、过载概率估计（Estimation of Overloaded Probability， EOP） [1]两种物理主机过载检测算法和随机选择（Random Selection， RS）[4]、过载概率下降的迁移选择（Overloaded Probability Decreasing Migration Selection， OPDMS）[5]两种虚拟机选择算法进行实验，并将过载检测和虚拟机选择算法组合成IQR-RS、EOP-OPDMS两组。每次整合时首先执行EOP（或IQR）算法对主机进行过载检测，再通过OPDMS（或RS）算法将过载主机中的部分虚拟机迁出直至主机不再过载，再通过虚拟机放置算法给这些虚拟机找到合适的目的主机，最后将部分低负载主机中的全部虚拟机迁出将其切换至休眠状态。实验参数的初始化如下：N=10， fmax=1， fmin=0，R=0.7，r0b、A0b、α和γ的值为0.95，φ=0.3，iter=8。

4.3.1有效性

有效性主要是用来验证算法在六种性能评价指标中的表现。图2（a）为不同虚拟机放置算法运行Bitbrains数据集得到的能耗值。其中，使用EOP-OPDMS作为过载检测和虚拟机选择算法时，DBA-VMP的能耗值最低，约为ACS-VMP能耗的82%，这是由于该算法将能耗指标作为了优化目标，且算法通过随机迭代可抑制贪心选择使算法陷入局部最优，因此算法有很好的节能效果;ACS-VMP和COFFGA的目的都是最小化活动主机的数量，当采用不同的过载检测和虚拟机选择策略时，能耗值变化幅度很大，表明这两种算法有可能陷入了局部极值，导致活动主机数量增加，能耗增大。

图2（b）为不同算法运行Alibaba Cluster数据集得到的能耗值， Alibaba Cluster的资源请求量比Bitbrains大但变化幅度小，所以运行时产生的能耗值大且不同算法得到的能耗值差距小。在使用EOP-OPDMS的前提下，DBA-VMP的平均能耗值比FFD高4%左右，因为DBA-VMP在进行目的主机选择时偏向资源配置大的主机，以减小主机的过载风险，确保服务质量;在使用IQR-RS的前提下，COFFGA的平均能耗值比FFD高16%，再次证明了算法可能会陷入局部极值。

图3为几种算法运行不同数据集得到的平均迁移次数，虚拟机迁移会造成短暫的停机影响服务质量。在使用不同的过载检测和虚拟机选择算法的情况下，DBA-VMP的迁移次数保持稳定且远远低于其他算法，因为算法考虑了不同资源间的负载均衡，使得主机有足够的预留资源应对虚拟机请求的急剧增加，避免主机发生过载，减少不必要的虚拟机迁移;ACS-VMP的迁移次数变化幅度大，运行Bitbrains时，在选择EOP-OPDMS的前提下ACS-VMP比DBA-VMP低1%左右，但选择IQR-RS的前提下ACS-VMP比DBA-VMP高85%左右，再次说明了：算法有可能陷入局部极值使活动主机的数量增加，从而降低迁移次数;而当算法找到全局最优解时，又导致主机负载过高造成迁移次数增加。

圖4（a）为不同算法运行Bitbrains数据集得到的SLATAH值。在使用EOP-OPDMS的前提下，DBA-VMP算法略高于ACS-VMP和COFFGA，结合图3（a）可知，这三种算法的迁移次数相对较少，但DBA-VMP比其他算法时间开销大，从而造成虚拟机请求的响应时间长，导致服务质量略低于其他算法。使用IQR-RS的情况下，DBA-VMP的SLATAH值最低，因为该算法的迁移次数远低于其他算法。

图4（b）为不同算法运行Alibaba Cluster得到的SLATAH值。在使用不同的过载检测和虚拟机选择算法的情况下，算法DBA-VMP和COFFGA的SLATAH值都保持领先，因为DBA-VMP算法的迁移次数少，COFFGA在运行该数据集时，时间开销小，FFD仅次于这两种算法，因为算法的时间开销小。ACS-VMP略高于FFD，因为算法通过迭代来寻找最优解，因此算法的响应时间长，UPBFD的迁移次数远超于其他算法，因此SLATAH远高于其他算法。

图5为不同算法的PDM值。图5（a）是Bitbrains的运行结果。其中使用EOP-OPDMS的前提下，DBA-VMP算法的PDM值仅次于算法ACS-VMP和COFFGA，因为这三种算法迁移次数少，但DBA-VMP算法时间开销较大，虚拟机请求的响应时间长，使服务质量受到影响;FFD算法的迁移次数多但时间开销小，所以仅次于DBA-VMP算法。图5（b）为Alibaba Cluster数据集的运行结果，在选择不同过载检测和虚拟机选择算法的情况下，DBA-VMP的PDM值都优于其他算法，因为该算法通过合理的虚拟机放置稳定了主机负载，使迁移次数远低于其他算法，有效保证了服务质量。

图6为不同算法的服务质量指标值，SLAV受SLATAH和PDM的综合影响，因此，在使用不同过载检测和虚拟机选择算法的情况下，DBA-VMP的SLAV值在不同的数据集上都有很好的表现。ESV指标受服务质量和能耗的影响，因此，结合图2和图6可知，在选择EOP-OPDMS情况下，运行Bitbrains数据集后，DBA-VMP的ESV平均值仅次于ACS-VMP和COFFGA，且比ACS-VMP高36%左右;运行Alibaba Cluster数据集后， DBA-VMP的ESV平均值比COFFGA高18%左右。在选择IQR-RS情况下，DBA-VMP运行不同的数据集得到的ESV值都最低。可见，DBA-VMP的ESV值在不同的数据集上都有很好的表现，进一步验证了DBA-VMP算法的有效性。

通过以上分析可知，DBA-VMP算法在处理不同的数据集时都可以有效降低能耗，保证数据中心的服务质量。

4.3.2高效性

本节以IQR-RS作为过载检测和虚拟机选择算法，通过对比不同算法运行Bitbrains数据集后，数据中心活动主机的资源利用率为例，来验证DBA-VMP算法的高效性。图7（a）为不同算法CPU资源的利用率对比，横坐标表示虚拟机的整合周期，虚拟机整合每隔5min进行一次，每天整合288次。

由图7（a）可知，UPBFD的CPU利用率最高且维持在80%左右，这是因为算法优先将虚拟机放置在综合负载高的物理主机上，导致主机预留资源紧张，结合图6可知，该算法未考虑数据中心的服务质量;CPU利用率过高会增加主机的过载风险，导致虚拟机频繁的迁移，影响服务质量。DBA-VMP算法的CPU使用率维持在70%左右，从而能进一步提升服务质量。

图7（b）为内存资源的利用率对比。UPBFD算法整合前期内存利用率低于其他算法，这是因为算法优先考虑综合负载高的物理主机且未考虑主机的不同资源之间的负载均衡，造成资源浪费，DBA-VMP算法的内存使用率维持在70%左右，因为算法在优化时考虑了不同主机内的负载均衡，可有效减少资源的浪费。

图7（c）为不同算法的带宽资源利用率情况，Bitbrains数据集中带宽资源的请求量低，所以每种算法的带宽资源使用率相近。

通过以上分析可知，DBA-VMP算法可有效提高主机的资源利用率并考虑到了不同资源之间的负载均衡，还同时兼顾了数据中心的服务质量。

5 结语

本文建立了能耗和资源利用率的优化模型，并提出了DBA-VMP算法来求解该模型的Pareto最优解。实验结果表明，DBA-VMP算法在保证服务质量的前提下，有效降低了数据中心能耗并提高了资源利用率。然而本文算法没有对服务质量作出改善，改善服务质量可以提高用户体验，因此，在“降低能耗、提高资源利用率和改善服务质量”三者之间取得优化平衡的多目标虚拟机放置算法是我们进一步的研究工作。

参考文献 （References）

[1]LI Z， YAN C， YU X， et al. Bayesian network-based virtual machines consolidation method [J]. Future Generation Computer Systems， 2017， 69： 75-87.

[2]BIRKE R， CHEN L Y， SMIRNI E. Data centers in the cloud： a large scale performance study [C]// Proceedings of the IEEE 5th International Conference on Cloud Computing. Piscataway： IEEE， 2012： 336-343.

[3]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（5）： 755-768.

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

[5]LI Z， YAN C， YU L， et al. Energy-aware and multi-resource overload probability constraint-based virtual machine dynamic consolidation method [J]. Future Generation Computer Systems， 2018， 80： 139-156.

[6]HALLAWI H， MEHNEN J， HE H. Multi-capacity combinatorial ordering GA in application to cloud resources allocation and efficient virtual machines consolidation [J]. Future Generation Computer Systems， 2017， 69： 1-10.

[7]FARAHNAKIAN F， ASHRAF A， PAHIKKALA T， et al. Using ant colony system to consolidate VMS for green cloud computing [J]. IEEE Transactions on Services Computing， 2015， 8（2）： 187-198.

[8]DING W， GU C， LUO F， et al. DFA-VMP： an efficient and secure virtual machine placement strategy under cloud environment [J]. Peer-to-Peer Networking and Applications， 2018， 11（2）： 318-333.

[9]朱占磊，李征，趙瑞莲.基于线性权重最优支配的高维多目标优化算法[J].计算机应用，2017，37（10）：2023-2827.（ZHU Z L， LI Z， ZHAO R L. Many-objective optimization algorithm based on linear weighted minimal/maximal dominance [J]. Journal of Computer Applications， 2017， 37（10）： 2023-2827.）

[10]YANG X. A new metaheuristic bat-inspired algorithm [C]// Proceedings of the 2010 Nature Inspired Cooperative Strategies for Optimization， SCI 284. Berlin： Springer， 2010： 65-74.

[11]DEB K， PRATAP A， AGARWAL S， et al. A fast and elitist multiobjective genetic algorithm： NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary Computation， 2002， 6（2）： 182-197.

[12]CALHEIROS R N， RANJAN R， BELOGLAZOV A， et al. CloudSim： a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms [J]. Software： Practice and Experience， 2011， 41（1）： 23-50.

[13]SHEN S， VAN BEEK V， IOSUP A. Statistical characterization of business-critical workloads hosted in cloud datacenters [C]// Proceedings of the 15th IEEE/ACM International Symposium on Cluster， Cloud and Grid Computing. Piscataway： IEEE， 2015： 465-474.

[14]CHANG Z H. Alibaba cluster trace program [EB/OL]. [2018-12-25]. http：//github.com/alibaba/clusterdata.

[15]FARAHNAKIAN F， PAHIKKALA T， LILJEBERG P， et al. Utilization prediction aware VM consolidation approach for green cloud computing [C]// Proceedings of the IEEE 8th International Conference on Cloud Computing. Piscataway： IEEE， 2015： 381-388.

This work is partially supported by the Ministry of Industry and Information Technology Intelligent Manufacturing Project （ZH-XZ-180004）， the Production-Study-Research Forecasting Project of Jiangsu Science and Technology Department （BY2013015-23）， the 111 Base Construction Project （B2018）.

LIN Kaiqing， born in 1993， M. S. candidate. Her research interests include cloud computing， distributed computing.

LI Zhihua， born in 1969， Ph. D.， associate professor. His research interests include cloud computing， information safety.

GUO Shujie， born in 1994， M. S. candidate. His research interests include cloud computing， parallel computing.

LI Shuangli， born in 1992， M. S. candidate. Her research interests include cloud computing， distributed computing.

收稿日期：2019-05-13;修回日期：2019-06-03;录用日期：2019-06-10。

基金项目：工业和信息化部智能制造项目（ZH-XZ-180004）;江苏省科技厅产学研前瞻项目（BY2013015-23）;111基地建设项目 （B2018）。

作者简介：蔺凯青（1993—），女，山西吕梁人，硕士研究生，CCF会员，主要研究方向：云计算、分布式计算; 李志华（1969—），男，湖南保靖人，副教授，博士，主要研究方向：云計算、信息安全; 郭曙杰（1994—），男，江苏常州人，硕士研究生，主要研究方向：云计算、并行计算;李双俐（1992—），女，河南新乡人，硕士研究生，CCF会员，主要研究方向：云计算、分布式计算。

文章编号：1001-9081（2019）12-3597-07DOI：10.11772/j.issn.1001-9081.2019050808