基于优化粒子群算法的虚拟机部署策略*

董德坤 张亚钦 徐克祥

（中国石油大学（华东）计算机科学与技术学院 青岛 266580）

1 引言

云计算是一种利用互联网实现随时随地、按需便捷地访问共享资源池（如计算设施、存储设备、应用程序等）的计算模式，本文关注的是物理服务器的虚拟化。由于云基础设施依赖于虚拟化技术，云计算的大规模使用将增加更多的虚拟机请求，从而增加虚拟化基础设施的压力，因此需要一个有效的虚拟机调度策略。

本文提出一种改进的粒子群算法，该算法迭代过程初期引入混沌策略，使粒子群分布有着良好的遍历均匀性；使用随机分组策略，作为改进粒子群的核心过程，设置两个目标函数，利用欧氏距离寻求多目标粒子群优化算法的最优解。将改进后的算法应用到云计算虚拟机部署，以物理机资源利用率、虚拟机迁移量为目标函数。

2 相关工作

虚拟机部署是将虚拟机映射到物理机的过程。由于云基础设施是完全虚拟的，虚拟机的部署成为云系统的核心问题。为此，人们进行了大量有关优化虚拟机部署的研究工作，Xu等［1］针对云计算环境下虚拟机的动态部署问题，提出了虚拟机动态部署的多目标综合评价模型和改进的多目标粒子群优化算法（IMOPSO）。胥小波等［2］提出了一种新的混沌粒子群优化算法，不同于已有的混沌粒子群算法的简单粒子序列替换，该算法将混沌融入到粒子运动过程中，使粒子群在混沌与稳定之间交替运动，逐步向最优点靠近。朱亚会等［3］提出一种基于资源利用率均衡的虚拟机调度模型。该模型将虚拟机调度问题抽象为不定维向量装箱模型。杨靖等［4］引入多种群进化模式提高算法收敛速度，并在此基础上加入高斯学习策略避免局部最优，提出了一种多种群高斯学习粒子群优化（MGL-PSO）算法。张笑燕［5］等提出了一种虚拟机部署方案，该方案的目的是减少主机上的资源碎片。曹盟盟等［6］在算法中引入分组思想，通过对初始种群进行随机分组，避免算法陷入早熟现象。经典的智能算法有蚁群算法、遗传算法、微分进化算法等，Garg［7～9］等利用遗传算法（GA）、蚁群算法、微分进化（DE）相结合的粒子群优化算法，保持了多种算法的优点。 Zhao［10］提出了一种基于PSO 的改进算法，根据云计算环境中资源的使用成本来解决任务调度问题。Dashti等［11］利用粒子群优化（PSO）在过载的PMs 中重新分配vm，并合并负载不足的PMs 以节省电能。

3 资源浪费模型

3.1 问题描述

本文的研究内容是基于粒子群算法提出一种虚拟机部署方案，通过合理地部署虚拟机以减少云系统能耗。在云系统中，虚拟机分为已部署的虚拟机和新请求的虚拟机，系统图如图1所示。

图1 系统图

本文提出的虚拟机部署方案对物理主机CPU、内存和网络带宽三种资源的负载情况进行监控。假设云环境中有n 个物理机，物理机阈值表示为。m 个虚拟机，虚拟机需求表示为。虚拟机的部署情况由矩阵Xmxn表示，xij值为1表示第i个虚拟机部署在第j个物理机上。

3.2 目标函数和约束函数

目标函数如下：

约束函数如下：

其中，式（1）表示虚拟机利用率。式（2）表示虚拟机的迁移数量。式（3）表示同一虚拟机只能部署在同一物理机上。式（4）、（5）、（6）分别表示多个虚拟机部署在物理机上时，虚拟机CPU、内存、带宽资源需求量不超过物理机CPU、内存、带宽阈值。

4 改进算法设计

4.1 传统粒子群算法

粒子群算法是进化算法的一种，在每一次迭代中，粒子通过跟踪两个“极值”来更新自己。式（7）为粒子速度更新公式，式（8）为粒子位置更新公式。在d 维空间的第i 个粒子，位置表示为Xid=(xi1,xi2,…,xid)，速度表示为Vid=(vi1,vi2,…,vid)。

4.2 改进的多目标粒子群算法设计

Kennedy 认为，具有大邻域的粒子群优化算法在处理简单问题时表现得更好，而具有小邻域的粒子群优化算法在处理复杂问题时表现得更好［12］。本文对传统粒子群算法进行改进，首先引入混沌算法对粒子群初始化，迭代过程使用随机分组策略。

1）混沌映射

利用混沌映射初值敏感性、遍历性特点，随机初始化一个粒子，并通过混沌映射得到多个粒子的初始值，改变初始粒子群的提取过程。利用混沌映射扩大初始粒子群，得到寻优粒子群，使得种群粒子多样化。Tent 映射结构简单，具有很好的遍历性，公式如下。

2）惯性权重w

w 是影响算法搜索结果和收敛速度的关键参数，w 过大有利于全局寻优，w 过小有利于局部寻优。根据w 取值对搜索结果的影响，本文采用线性递减方式设定w值。如下所示。

3）随机分组

粒子群算法迭代过程通过随机分组策略更新，3 个粒子组成一个小群体，每隔5 代各小群体间粒子进行随机重组。群体间两个粒子不足以构成一个良好的群体，而五个粒子具有较好的局部搜索能力和较弱的全局搜索能力。三个粒子实现了它们之间的平衡，群体显示出更好的全局搜索能力［13］。

4）最优解设计

通过欧氏距离法［1］更新目标函数和粒子群，策略步骤表示如下。

（1）群体内粒子利用组内信息更新速度和位置。目标函数f1 和f2 单独更新，从每次迭代结果中，选择两个群体最优值f-Opt［1］和f-Opt［2］。

（2）计算两个群体最优间的距离。

（3）个体最优值的确定。

如果dl[i]

如果dl[i] >df，取二者平均值作为个体最优。

（4）更新至迭代结束。

5）虚拟机编码

粒子群算法中，设共有p 个粒子。云系统中，将粒子的速度和位置维数设置为物理机数目n，并将物理机编号为1到n。粒子的位置向量的每一项表示虚拟机i 在该物理机上，粒子位置向量的值表示虚拟机的一种部署策略。

5 实验

本文选择CloudSim仿真平台进行仿真实验，用基本CloudSim 类中的继承类实现EPSO 算法。实验环境如下，编译环境JDK 1.8，编译软件Eclipse 4.6，仿真云计算环境CloudSim 3.0，物理机的数量为100，虚拟机的数量为200。所有服务器都有相同的资源分配：10个处理单元的CPU、20GB内存和100M 带宽。设计仿真实验，与经典粒子群算法进行对比。

我们比较了多目标粒子群算法与传统的粒子群算法PSO，分别从资源利用率f1，虚拟机迁移数f2 两方面进行对比分析。其中PSO 对两个目标的关注度一致。在CloudSim平台上，进行仿真实验记录相关数据，将实验结果数据进行对比分析，最后得出两种算法的实验效果分布图。

图2 表示了在不同服务请求下算法的资源利用率，证明我们提出的改进算法是有效的，资源利用率高于其他算法。图3 表示了虚拟机的迁移次数，PSO算法下虚拟机迁移了73次，EPSO算法下虚拟机迁移了51 次，所提出的算法在虚拟机迁移次数上少于PSO算法。

图2 两种算法下的资源利用率

图3 两种算法下的迁移次数

实验结果表明，由于初期粒子群分布更有遍历性和均匀性，保持种群多样性等优点，使用小群迭代更新，这些小群被频繁地重新组合以在群之间交换信息。在不失去稳定性的情况下，通过欧式距离方法选择帕累托最优解，帕累托最优解有更好的分布性和收敛性。该算法与经典算法相比，资源利用率、迁移次数均取得了更好的结果。

6 结语

云计算通过使用虚拟机技术提高了数据中心的资源利用率。虚拟机放置算法作为云计算的关键技术，具有重要研究意义。本文提出了优化的粒子群算法，通过平衡资源利用、虚拟机迁移优化数据中心性能。EPSO 算法首先混沌初始化粒子群，使群体分布具有遍历性和均匀性，使用小群迭代更新，这些小群被频繁地重新组合以在群之间交换信息。设计仿真实验，将我们的改进算法与经典PSO算法进行比较，验证了改进后的方法的可行性和有效性。实验结果表明，该算法平衡了资源利用、虚拟机迁移，优化了数据中心性能。