基于改进的花授粉算法的虚拟机分配策略

田海梅，徐胜超

（1.金陵科技学院计算机工程学院，南京211169；2.广州华商学院数据科学学院，广州511300）

引 言

低能量消耗与高服务质量是绿色云数据中心的主要性能目标，目前国内外的研究主要采用虚拟机迁移技术来达到这2个目标［1-3］。虚拟机迁移的过程非常复杂，涉及物理主机负载检测、虚拟机选择与虚拟机重新分配及优化等3个阶段。虚拟机分配及优化阶段是最重要的一个阶段，属于多目标优化问题或者装箱问题［4］，它没有最优解，只能在目标函数中得到一定程度的最优，目前针对虚拟机分配及资源优化过程有很多智能算法对其进行优化，例如遗传算法［5］、贪心算法［6］、粒子群优化算法［7］、蚁群算法［8］、强化学习优化算法［9］、萤火虫群优化算法［10］以及蛙跳算法［11］等。这些智能优化方法都不同程度地存在早熟和收敛速度慢的问题，同时已有的智能虚拟机分配算法在硬件上往往都只考虑了一维的因素（处理器的温度或者主频，内存利用率或者磁盘大小），其实云数据中心的能量消耗模型是一个多维的非线性数学模型，需要综合考虑多个因素；另外云客户端的资源访问模型也需要重新设计。基于此，本文提出了新型的虚拟机分配及优化策略。花授粉算法（Flower pollination algorithm，FPA）也是近年来新提出的一种解决多目标优化的智能算法，它将局部最优解搜索和全局最优解搜索结合起来，具有良好的性能。针对上述虚拟机分配及优化的特点和花授粉算法的比较，本文提出了云数据中心基于花授粉算法优化的虚拟机分配策略（Flower pollination algorithm based virtual machine allocation，FPA-VMA）。

1 花授粉算法与虚拟机分配

1.1 花授粉算法

目前关于花授粉算法的文献比较多［12-14］，它是一种模拟生物的交叉授粉的智能算法，具有参数少、实现简单和容易调节的优点，已经广泛应用到NP-hard的多目标组合优化领域。某些研究者已经实现了花授粉算法的离散搜索和连续搜索空间，结论表明它比其他常见的智能算法性能优异。

花授粉算法在理想的情况下包括下面4个步骤：（1）带花粉的传粉者通过莱维Levy飞行进行的全局授粉过程；（2）非生物自花授粉的局部授粉过程；（3）花的常性可以被认为是繁衍概率，繁衍概率与参与的两朵花的相似性成比例关系；（4）转换概率p∈[0，1]控制全局授粉和局部授粉之间的转换，由于物理上的邻近性和风等其他因素的影响，在整个授粉活动中，p是局部授粉一个非常重要的部分。

假设每颗显花植物只开一朵花，且每朵花仅产生一个花粉配子。因此一朵花或一个配子就对应于优化问题中的一个解，类似于虚拟机到物理主机的映射与分配。基于以上阐述，文献［15］描述了基本的花朵授粉算法实现步骤。

1.2 FPA‑VMA工作环境

云计算环境下分配可用的资源给云客户端具有各种不同的模式，这些模式都可以被认为是针对云数据中心资源池的一种基于服务的访问，虚拟机技术是将云客户端的请求封装成虚拟机的形式来分配与访问。图1显示了FPA-VMA分配优化策略所运行的资源分配模型，它由3个主要步骤组成：（1）云客户端提交请求；（2）服务提供者处理请求；（3）云数据中心资源分配与管理。

图1 FPA-VMA优化的绿色云计算框架Fig.1 Optimized green cloud computing framework of FPA-VMA

图1 中，首先云客户端提交请求到云服务提供者，代理将返回该结果到右边的云数据中心资源管理模块。云资源管理将查询该请求，与可用资源池的资源进行比较，并作出决策。云资源管理对云客户端请求的接受都是基于系统的资源可用性，如果超过了资源的可用能力，云资源管理将会把该请求传递到资源分配模式，寻找全局可用资源，该资源分配方法被传递到资源管理模块，里面包含了FPA-VMA等虚拟机分配与优化的相关操作。

1.3 FPA‑VMA数学建模

1.3.1 云客户端请求模型

云客户端请求资源通过代理或者云服务提供者来请求各种应用。云客户端的请求可以定义为VMs，定义用户的请求为UR。UR按照先来先服务的方式来访问云数据中心的物理资源。Ai表示虚拟机VMs的组成部分。虚拟机的组成部分包括：处理器需求内存需求；磁盘空间需求其中i和s表示资源的数量和它们各自的资源提供能力。因此，可以把资源请求表示为Ai⊂UR并且故有

所以当云客户端只发送1个请求到1个资源之上时，可以表示为

当i=1时，UR1则表示了资源的需求只有1个，即

如果客户端的请求超过1个时，可以表示为

1.3.2 云数据中心能量消耗模型

假设云数据中心中所有虚拟机集合为VM={VMi，i=1，2，3，…，n}，它们将被分配到多个物理主机PMj之 上，PM={PMj，j=1，2，3，…，m}。每 个 虚 拟 机 的 多 维 资 源 需 求 都按 照d维 的 向 量 来 表示［16］，VMi=(Ai，1，Ai，2，…，Ai，d)，其中Ai，s为虚拟机VMi的资源请求向量。类似地，每个物理主机的多维资源提供能力也可以按照d维的向量来表示［17］，PMj=(Bj，1，Bj，2，…，Bj，d)，其中Bj，s为物理主机PMj的资源能力提供向量。本文描述的FPA-VMA策略中各种物理主机资源主要包括CPU资源、内存资源和磁盘空间，因此这里d=3。

虚拟机分配与优化都有开始时间和结束时间，每个虚拟机VMi在一个固定的时间Sti开始，需要一个执行时间Eti，因此整个虚拟机分配的时间跨越可表示为Sti+Eti。整体来讲云数据中心的资源分配问题有下列约束条件：（1）所有资源必须有能力提供给云客户端的请求；（2）所有的虚拟机的资源请求必须小于等于整个物理主机的资源提供能力；（3）假设aj(t)是被分配到PMj上的一个虚拟机，则每个虚拟机只能分配到一个具体的物理主机上；（4）对于∀s=1，2，…，d，有

假设一个最优的虚拟机分配方式RA为二元组(VMi，PMj)，∀i∈{1，2，…，n}，∃j∈{1，2，…，m}，RA目标函数是尽量地提高整体物理资源的利用效率（RUDC），同时降低整体云数据中心的能量消耗首先必须试图最大化单台物理主机的资源利用效率有

则整个云数据中心物理主机的资源利用效率为

假设每个PMj都可以容纳任何虚拟机，而且物理主机的能量消耗模型变量P(t)具有线性关系［18］，云数据中心的能量消耗模型的部分参数可描述为

式中：U(t)j表示在给定时刻t的物理资源利用效率；ECj为物理主机PMj在[t1，t2]内的能量消耗，i∈{1，2，…，n}，j∈{1，2，…，m}，t∈[0，T]。整个云数据中心的能量消耗模型可以描述为

综上所述，整个云数据中心的资源利用效率UR的最大值RA和整个云数据中心的能量消耗利用效率可以描述为

2 FPA‑VMA策略描述

2.1 FPA‑VMA简介

IAAS云平台的异构性导致虚拟机规模越来越大，因此虚拟机资源分配算法需要的时间也越来越长。本文提出一种基于问题特征的搜索操作来重新设计花授粉算法中的动态切换概率（Dynamic switching probability，DSP）过程，以便适应云数据中心的能量消耗模型，同时改善整个物理资源的利用效率。

本文的FPA-VMA在局部搜索办法中也需要授粉者，其目的是为了在算法规定的搜索空间内快速搜索和寻找到局部最优解。第一步主要是对目标函数的当前解进行改进，只要满足约束条件的问题解都可以算是一个当前解，对每一个生成的当前解而言，它们之间必须有一个差异值，用来体现这些当前解是如何满足全局的目标函数需求。云数据中心的资源分配的总体目标是把客户端的n个虚拟机请求分配到m个可用的物理主机资源之上，以便在采用最小的物理资源条件下完成用户的需求。

2.2 初始化阶段

FPA-VMA的第一阶段是初始化，根据目标函数的当前解，发现一个可能的局部解，只要满足目标函数约束条件的资源分配办法，都可以认为是一个局部最优解。云客户端使用能量感知的目标函数来代替随机的资源分配办法，这样可以尽量地提高物理资源的利用效率。如果当前的需求不能满足，FPA-VMA优化算法将继续进行下一步。整个过程反复迭代，直到指定的时间到达或者寻找到全局最优的资源分配办法，此时的资源分配办法是在最后种群中最好的花。算法1为FPA-VMA优化算法中目标函数RA的初始化过程，按照1.3节所描述的云数据中心的能量消耗模型来完成资源的分配［19］。

算法1目标函数初始化

（1）For each PM∈collection of PMs do

（2）Utilization of PM：=PM.getUtilization of PM（CPU；Memory；Storage）

（3）Power of PM：=getPower（PM.getUtilization of CPU）

（4）Power of PM：=getPower（PM.getUtilization of Memory）

（5）Power of PM：=getPower（PM.getUtilization of Storage）

（6）Energy of datacenter：=Energy of datacenter+power of PMs（CPU；Memory；Storage）

（7）End for

（8）Evaluation value（Pollen）：=1.0/power of datacenter

2.3 全局搜索策略阶段

在全局搜索阶段，资源分配办法Xi相当于是一个花针对花粉配子的映射。传粉者需要查找整个搜索空间，发现最优的的当前位置。因此全局最优解适应于生物和交叉传粉者，因为它们遵循的是Levy莱茵飞行规则，可以更加有效地飞行很远的距离。在大规模的空间搜索过程中，Levy莱茵飞行规则比Brownian布朗运动更加高效，该过程可以表示为［19］

式中Γ(λ)为标准的Gamma函数。

2.4 局部搜索策略阶段

在获得了全局最优解之后，局部搜索阶段是基于FPA花授粉算法的组成部分。FPA-VMA算法进行更高强度的寻找，以便在相邻的结构中寻找到更加优秀的问题解。FPA需要局部的花粉来搜索，以更好地探索周边的区域，这样可以增加寻找最优解的机会。因为这个阶段可以从当前解中发现改进的问题解，局部搜索可以描述为

2.5 动态切换概率阶段

FPA-VMA中，切换概率p用来在全局传粉和局部传粉之间切换，这里p是一个常量。一般来讲，一个智能优化算法在刚开始执行时，应该多做一些全局搜索，而在最后快结束时尽量少做［17］。因此结合花授粉算法的实际情况，本文提出了DSP方法调整两个不同的传粉过程的比例，平衡全局搜索和局部搜索过程。这里增强的切换概率p可以修改为

式中：Maxiteration为FPA-VMA优化算法的最大迭代次数；t为当前的迭代次数。算法2为FPA-VMA优化算法步骤。

2.6 FPA‑VMA时间消耗分析

FPA-VMA首先以文献［16-17］中的数据作为比较对象，即常见的普通花授粉算法FPA和蚁群虚拟机优化策略ACO的结果。FPA-VMA、FPA和ACO算法都在类似的参数条件下进行测试，调整循环迭代的次数为（100，200，1 000），改变种群的尺寸为（10，20，50）。对于普通的花授粉算法FPA而言，切换概率p=0.8，迭代的次数为1 000。对于蚁群优化算法ACO中，交叉概率为0.95，学习参数为2［20］。

图2 显示了FPA-VMA优化算法运行时间随着迭代次数变化的实验结果。从结果可以看出，随迭代次数的增加，FPA-VMA相对其他两种算法运行时间较少，基本保持了线性的缓慢增加。在FPA-VMA中，每个花都被描述为M维的向量，花的搜索空间被限制在I，I在种群个数中已经指定。可以看出FPA-VMA优化明显优于普通的FPA算法和ACO优化算法，主要原因是FPA-VMA采用了动态的切换概率策略，提高了算法寻优的效率。

图2 FPA-VMA优化算法时间分析Fig.2 Time cost results of FPA-VMA

ACO优化算法在寻最优解上也具有收敛性，尽管如此，出现收敛的时间还是不确定，因为数据都是随机的。综合比较，FPA-VMA策略在所有函数的测试中具有比较好的性能，其主要原因是FPA-VMA在第4阶段采用动态切换概率策略，它可以在局部搜索过程和全局搜索过程中调整，很容易发现满足目标函数的局部最优解，而且它还可以加快发现全局最优解的速度。

3 FPA‑VMA实验与性能分析

3.1 实验环境

因为FPA-VMA基于花授粉算法优化的虚拟机分配是在虚拟机迁移过程中运用的，所以进行FPA-VMA实验分析必须构造云数据中心的虚拟机迁移场景。本文参考了Cloudsim 3.0工具包，同时依据图1中的功能模块，实现了基于Java语言的云资源管理方法，根据算法2在该模块中实现了花授粉算法的优化的代码。表1给出了云数据中心的物理主机和虚拟机的参数配置情况，为了描述简单，这些物理主机都是相同的配置。表2给出了FPA-VMA算法与其他常见的Benchmark智能算法的参数设置。

表1 云数据中心的物理主机和虚拟机的参数设置Table 1 Parameters of physical host and virtual machine in cloud data centers

表2 FPA‑VMA性能分析相关的算法参数设置Table 2 Parameters setup of FPA‑VMA performance analysis

3.2 工作负载类型

实验的虚拟机的相关参数都来最常见的CoMon project，它是由Planetlab实验室开发的一个项目。虚拟机迁移周期设置为10 min一次，一共运行24 h，每次统计1天内的能量消耗，在1周内重复运行5次取平均值，1周内每天虚拟机请求的个数如表3所示，不同的虚拟机尺寸如表4所示。

表3 Planet项目的1周工作负载Table 3 Workloads of a week in Planet projects

表4 CoMon项目不同虚拟机粒度的参数Table 4 Parameter setup of different virtual machine grains in CoMon projects

3.3 物理资源利用率分析

图3 显示了各个智能算法优化针对云数据中心的所有物理主机的处理器资源，内存资源和存储资源的平均利用效率情况，包括云数据中心的所有活跃物理主机情况也进行了分析。图4显示了随着虚拟机请求个数的增加，物理资源利用效率的变化情况。这些实验结果表明，FPA-VMA策略可以使得云数据中心的物理主机资源平均利用率达到95.4%以上。

图3 FPA-VMA多维物理资源利用效率分析Fig.3 Multi-demensional physical resource utilization results of FPA-VMA

图4 FPA-VMA资源利用效率随请求个数的变化Fig.4 Physical resource utilization results of different virtual machine numbers

在相同的软硬配置和虚拟机请求的条件下，GA、ACO、萤火虫优化算法GSO［10］等虚拟机分配优化策略只能使得云数据中心的物理资源达到72%的利用效率，FPA-VMA策略能够高效地利用物理资源主要是得益于在花授粉时采用的DSP策略，它在具体的搜索最优解的过程中停止了局部搜索，选择利用搜索相邻的资源分配方案，提高了效率。

另外一个原因是DSP策略可以改善FPA-VMA资源分配的全局收敛能力。FPA-VMA可以很好地分配虚拟机到目标物理主机。整体来讲，上述实验结果均可证明FPA-VMA是一个可操作的、高效的大规模云资源分配和优化策略。

3.4 能量消耗分析

图5 和图6显示了FPA-VMA、GA、ACO和GSO等虚拟机分配策略在不同的虚拟机请求下的云数据中心的能量消耗情况。总体来说，随着云客户端的虚拟机个数的增加，能量消耗都在增长。与GA、ACO和GSO策略比较起来，FPA-VMA策略的能量消耗最小。

图5 FPA-VMA随请求个数的能量消耗情况Fig.5 Energy consumption results of different virtual machine numbers

图6 FPA-VMA随主机个数的能量消耗情况Fig.6 Energy consumption results of different physical host numbers

因为客户端的虚拟机请求个数的增加，越来越多的物理主机将被分配虚拟机，当活动主机数目不够时，云数据中心还会启动处于睡眠状态的物理主机。FPA-VMA能够获得良好性能也是因为花授粉算法的虚拟机分配优化及该算法在动态切换概率阶段的改进策略。

表5 显示了随着物理主机数量变化，整个云数据中心总体能量消耗和资源利用率的比较情况。从表5中可以看出，在相同的虚拟机请求个数条件下，FPA-VMA策略的最大能量消耗只有104.6 kW·h，GA策略是125 kW·h，ACO策略是129 kW·h，GSO策略是135.2 kW·h，因此FPA-VMA虚拟机资源分配策略比其他优化策略可以节省20%的能量消耗。

表5 云数据中心的总体能量消耗与资源利用情况Table 5 Total energy consumption and resource utilization in cloud data centers

4 结束语

针对目前绿色云数据中心的提高物理资源利用效率和降低能量消耗的需求，本文提出了基于花授粉算法优化的虚拟机分配策略FPA-VMA。本文提出一种云数据中心环境下的绿色云计算框架，并设计了云数据中心的多维物理资源的能量消耗模型和客户端的资源请求模型，将智能计算的花授粉算法应用到虚拟机分配及其优化过程中。真实条件下的实验数据表明，FPA-VMA在物理资源利用效率和整体能量消耗方面比常见的遗传算法、蚁群算法和萤火虫群算法等虚拟机分配策略性优越，可以为企业节能云数据中心的构造提供参考。