基于改进量子粒子群算法的虚拟机放置方法

邓生君　张晓哲　肖立权　姬琳

摘要：针对云计算中虚拟机的放置问题，本文通过对量子粒子群算法的分析，提出一种改进量子粒子群的放置算法。该算法以优化数据中心能耗为目标函数，根据粒子当前的位置和全局最优位置的关系，采用自适应调整收缩-扩张因子和粒子权值的方法，对量子粒子群算法的关键参数指标进行了改进，提高算法的收敛速度及粒子寻找最优解的能力。通过云计算仿真平台CloudSim 的测试，表明改进后的算法在保证满足用户请求的前提下，既提高了搜索效率，又降低了电源损耗。

关键词：云计算 虚拟机放置 量子粒子群优化算法

中图分类号：TP301.6 文献标识码：A 文章编号：1007-9416（2016）08-0152-03

Abstract：For the virtual machine placement problem in Cloud Computing ， an improved quantum particle swarm placement algorithm is proposed by analyzing the quantum particle swarm algorithm. The proposed algorithm models data center power consumption as the objective function. According to the relationship between current position and the global best one， an adaptive adjustment of contraction-dilation factor and particle weights method is adopted to improve the key parameter in quantum particle swarm algorithm，improving the convergence speed and the ability to find the optimal solution particle. Through the tests on CloudSim that is a cloud computing simulation platform， results show that under the premise to satisfy users requests， the proposed algorithm not only improves the search efficiency， but also reduces the power consumption.

Key Words：Cloud Computing； Virtual Machine Placement； Quantum-behaved Particle Swarm Optimization

1 引言

近年来，云计算已经融入到计算机技术的各个领域，它与5G、物联网、移动互联网和大数据分析等都有相当紧密的联系，是未来信息产业的重要支撑和关键性技术。随着云计算的不断发展和壮大，底层的基础设施规模也日益增大，如何在具有动态性和异构性的复杂云计算环境下，保证每个用户需求的同时，合理有效的分配物理资源给虚拟机，已成为云计算领域研究的一个重要问题。

云计算资源调度是一个NP难的问题，现有的云计算资源调度算法更多的是关注成本控制或资源使用率，采用动态的资源调度策略，实现了SLA（Service-Level Agreement）和运营成本两者之间的平衡；文献提出一种基于遗传算法的负载均衡调度方法，根据系统当前状态预测出放置后系统的结果，以此来选出最优的放置方案，但这些方法忽略了分配过程中涉及的能耗因素。研究表明物理主机的电源消耗与CPU的使用率是呈线性关系的， 当物理主机的CPU利用率增大时，物理主机节点的电源消耗呈线性增长。本文将资源分配和能耗结合在一起考虑，提出一种改进量子粒子群的放置算法（Adaptive Quantum-behaved Particle Swarm Optimization-Mapping，AQPSO-M），从而在虚拟机放置的过程中实现放置效率和节能。

2 问题描述

2.1 基本定义

定义1：底层的Q台物理主机被形式化为集合

，单个主机host有三个种资源描述（CPU、内存和带宽），表示为；n台虚拟机被形式化为集合，其中每台虚拟机有三种资源描述（CPU、内存和带宽），表示为。

定义2：映射矩阵，也可以被称为虚拟机的放置方案。其中，表示第i个虚拟机没能成功映射到物理主机节点j上，表示第i个虚拟机被成功映射到第j台物理主机节点上。

定义3：向量表示物理主机的资源利用率用。

定义4：定义物理主机的能耗率为，其中是物理主机当前的能耗，是物理主机j满负载的最大功耗。

2.2 目标函数及约束条件

目标函数为完成虚拟机放置后

当越大，相应的电能损耗率也越大，在极限情况下，当物理主机节点的CPU利用率为100%时，该物理主机节点的电能损耗率为1。

3 算法的改进思想

3.1 确定粒子权值

4 基于改进算法的虚拟机放置步骤

AQPSO-M算法的虚拟机放置步骤为：

步骤1：初始化粒子群规模、迭代次数和解空间维数；

步骤2：对云计算资源进行编码，每一个粒子对应着一种资源调度方案；

步骤3：计算各个粒子的权值系数以及目标函数适应度值，以及所有粒子的目标函数适应度值的平均值；

步骤4：确定粒子个体平均最优位置；

步骤5：计算粒子在第t次迭代时的局部最佳位置和粒子种群的全局最优位置，并计算收缩扩张系数δ；

步骤6：更新粒子随机点的位置和最新位置；

步骤7：根据约束条件进行判断，当前所求的解是否满足约束条件，若满足则输出云计算资源调度的最优解，否则跳到第3步继续搜索直到满足条件的解或达到最大迭代次数为止。

5 实验及结果分析

5.1 实验环境

为了验证AQPSO-M算法在虚拟机映射时资源调度的有效性，本文采用的实验仿真平台是Cloudsim，对其进行了扩展，修改了VirtualMachine 类， VMAllocationPolicy 类和 DataCenterBroker类中相关方法和属性，并与LFF（Least Full Fit）算法、PSO算法、QPSO算法进行对比。实验的参数设置如下：

仿真的硬件环境： InterCoreTM i5-2450M@2.50GHz，，8GB内存，500G硬盘。软件环境：windows 7操作系统，Eclipse8.6和javal.7.0语言开发工具。

在相同实验条件下，PSO算法中c1和c2设为2，PSO、QPSO和AQPSO三种算法的种群规模设置为10，迭代次数设置为300次。

模拟的物理主机节点的参数配置如表1所示。

当物理主机节点的CPU利用率为100%时耗电量记为250W；当物理主机节点的CPU利用率为0%时，损耗的电量是175W。

模拟的虚拟机的参数配置如表2所示。

5.2 实验结果与分析

5.2.1 任务完成时间的比较

通过对图1任务完成时间的分析，可以看出：LFF算法在放置虚拟机时花费的时间自始至终都最多，PSO、QPSO和AQPSO算法在虚拟机请求数量较少时，三种算法完成虚拟机放置的时间没有太大差别；随着虚拟机请求数量的增加，三种算法得到最优放置方案的时间差距逐步增大。

5.2.2 负载和能耗的对比

如图2所示：AQPSO-M算法比其他三种算法选出的放置方案中物理主机的CPU利用率和耗电率都较优，这是因为算法关键参数的自适应的优化调整及目标函数中对能耗的考虑，从而在一定程度上提高了搜索效率，并降低了电源损耗。

6 结语

本章主要针对云计算虚拟机放置过程中资源调度的问题，引入量子粒子群算法，根据粒子当前的位置和全局最优位置的关系，采用自适应调整收缩-扩张因子和粒子权值的方法，对量子粒子群算法的关键参数指标进行了改进，提出一种改进量子粒子群的映射算法AQPSO-M，算法以优化数据中心能耗为目标。通过仿真实验和分析，验证了AQPSO-M算法在搜索效率和节能方面的优势。

参考文献

[1]唐红，徐光侠.云计算研究与发展综述[J].数字通信，2010，（6）：23-28.

[2]孙香花.云计算研究现状与发展趋势[J].计算机测量与控制，2011，19（5）：998-1001.

[3]Armbrust M， Fox A， Griffith R， et al. A view of cloud computing [J].Communications of the ACM， 2010，53（4）： 50-58.

[4]刘鹏.云计算[M].北京：电子工业出版社，2015.

[5]任崇广.面向海量数据处理领域的云计算及其关键技术研究[D].南京：南京理工大学计算机科学与工程学院，2013.

[6]Van H N， Tran F D， Menaud J M. Autonomic virtual resource management for service hosting platforms[C]/ICSE Workshop on Software Engineering Challenges of Cloud.2009：1-8.

[7]Hu J， Gu J， Sun G， etal. A scheduling strategy on load balancing of virtual machine resources in cloud computing environment [C]. Parallel Architectures， Algorithms and Programming （PAAP）， 2010 Third International Symposium on. IEEE， 2010： 89-96.

[8]Chen Y， Das A， Qin W， etal. Managing server energy and operational costs in hosting centers [C]. ACM SIGMETRICS Performance Evaluation Review. ACM， 2005， 33（1）： 303-314.

[9]Kusic D， Kephart J O， Hanson J E， etal. Power and performance management of virtualized computing environments via lookahead control [J]. Cluster computing， 2009，12（1）： 1-15.

[10]孙俊，方伟，吴小俊等.量子行为粒子群优化；原理及其应用[M].北京：清华大学出版社，2011：31-42.