利用蚁群算法完成虚拟机放置的优化

陈 艳，周天绮，徐胜超

(1.桂林航天工业学院 计算机科学与工程学院，广西 桂林 541004；2.浙江医药高等专科学校 医疗器械学院，浙江 宁波 315100；3.北部湾大学 电子与信息工程学院，广西 钦州 535011)

0 引 言

物理资源利用效率充分利用与低能量消耗是云数据中心构造的2个主要目标[1-3]，目前主要靠虚拟机迁移技术来实现。在虚拟机迁移过程中，最重要的是虚拟机放置策略[4-6]，该过程有很多智能算法进行优化，例如增强学习算法[7]、花授粉算法[8]、基于数据依赖的优化算法[9]、基于温度感知群优化算法[10]、基于任务映射的优化算法[11]、基于萤火虫群的优化算法等[12]、蚁群算法[13]、家族遗传算法[14]、混合遗传算法、改进的遗传算法[15]。

本文依托于Cloudsim云平台工具，在物理主机状态检测和虚拟机选择过程都采用Cloudsim中默认的优化策略；着重考虑采用蚁群算法的方式来优化虚拟机放置过程[13]。提出一种基于蚁群算法优化的虚拟机放置方法ACO-VMP(ant colony optimization based virtual mac-hine placement)。在虚拟机放置优化过程中涉及的物理资源描述的维度方面，ACO-VMP考虑了物理主机的处理器、内存大小、网络带宽等多个因素。与其它的虚拟机放置优化算法比较起来，ACO-VMP采用向量代数的方式描述云数据中心的多维的物理资源，综合考虑整个大数据中心的总体能量消耗和多维物理资源的充分利用这2个目标。

1 ACO-VMP虚拟机放置建模

(1)

这里x表示虚拟机v到物理主机p的放置矩阵xi,j， 定义如下：如果第j个虚拟机vj被重新放置到第i个物理主机pi, 则xi,j=1， 否则xi,j=0。 这里也描述了物理主机分配向量y， 如果yi上面至少有一个虚拟机放置，则yi=1， 否则yi=0， 公式如下

(2)

(3)

图1显示了ACO-VMP虚拟机放置策略的工作场景。

图1 ACO-VMP虚拟机放置策略的工作场景

ACO-VMP虚拟机放置优化策略的最终的目标如下：

(1)活动物理主机的资源利用效率最大化，而且这种最大化应该是在处理器、内存、磁盘空间等多个维度的。

(2)物理主机的能量消耗最小化。这也是大部分虚拟机迁移研究的文献上指出的关键问题，所以这里我们把目标函数f定义为单一变量的最小化函数

(4)

(5)

下面的公式可以保证每个虚拟机vj至少可以分配到一个物理主机之上

(6)

2 ACO-VMP相关术语描述

2.1 资源的利用效率的启发式信息

在虚拟机放置过程中，建立云数据中心的物理主机在多个维度的物理资源描述模型及资源利用效率模型是一个关键因素。如果只有一个维度的资源利用效率提高(比如处理器或内存大小)而其它维度的资源处于空闲，也不能算是充分利用资源。为了平衡好各个维度的物理资源利用，在ACO-VMP中提出了基于向量代数的多维资源描述。

在ACO-VMP中认为处理器、内存大小与网络带宽都是可用物理资源的一部分，在向量代数中，资源能力通过一个单元立方体来表示，该立方体有3个方面的维度，分别表示了3个不同类型的物理资源。RCV和RUV分别表示资源提供能力和资源利用效率情况。这里为了获得整个主机物理资源的利用效率的平衡，定义一个资源平衡向量(resource imbalance vector，RIV)，RIV表示了RCV和RUV之间的关联性。

这里H=(C+M+I)/3。 当放置一个虚拟机到物理主机上时，虚拟机会让magRIV的取值最小，这样就可以平衡各个维度的物理资源。magRIV的计算公式如下

(7)

我们把magRIV定义为ACO-VMP优化策略中的多维物理资源利用效率的启发式信息。

2.2 物理资源利用效率的消耗

(8)

2.3 云数据中心的能量消耗

(9)

Eidle和Efull分别表示物理主机在CPU的空闲和满负载时候的能量消耗，同时也认为在物理主机在关闭状态或睡眠状态的能量消耗为0。通过上面的计算，那么整个云数据中心的能量消耗为

(10)

3 ACO-VMP的虚拟机放置过程描述

3.1 ACO-VMP自适应性

ACO-VMP虚拟机放置优化策略参考了蚁群算法的思路，在蚁群算法中假设有大量的蚁群觅食的行为，在寻找最优解的过程中不断交换一种称为信息素的参数。

ACO-VMP具体参考了蚁群算法的后续改进版本，并且把每个虚拟机-物理主机的映射对(VM-to-PM pairs)作为一个问题解的组成部分。信息素的级别与所有虚拟机-物理主机的映射对都相关，并且信息素表示了一个期待的最优的虚拟机-物理主机的映射方法，例如式(11)和式(12)，这里信息素强度变量为τ0

τ0∶=PEFFDL1Norm

(11)

PEFFDL1Norm可以称为装箱的效率，当装箱效率高的时候，虚拟机的尺寸比较小，也就是说一个物理主机上容纳了很多个虚拟机。

τv,p是虚拟机-物理主机映射对中相关的当前信息素变量

τv,p∶=(1-δ)*τv,p+δ*Δτv,p

(12)

变量δ的含义是全局信息素延迟参数，0<δ<1， Δτv,p是应用到每个虚拟机-物理主机映射对的信息素强度参数。

在每个虚拟机-物理主机的映射中，这些启发式的值被动态更新，并且考虑到了式(14)中的整个云数据中心的多维物理资源的负载均衡与充分利用。

3.2 ACO-VMP算法描述

ACO-VMP优化策略的总体算法的伪代码如下算法1所示：信息素级别的实现通过一个n*m的矩阵的τ来实现，每个蚂蚁都通过一个空的寻优办法开始，一组物理主机和一组虚拟机随机的初始化(代码第(6)行-第(12)行)。

在循环的过程中，根据式(16)中的概率比例规则，在大量所有可能的虚拟机中，一个蚂蚁被随机选择出来并允许被选择一个虚拟机放置其到它当前的物理主机之上(代码第(11)行-第(22)行)。如果当前的物理主机是充分利用或者没有更多的物理资源来容纳虚拟机，系统将重新启动一个新的物理主机(代码第(14)行-第(16)行)。

当所有的蚂蚁都已经完成对它的路径寻优，即完成局部最优解的获取，循环中所有的局部最优解将与全局最优解(global-best-solution，GBS)进行比较，判断其是否达到式(4)中提到的目标函数条件，所有的这些局部最优解如果能够使得f的值最小，那么该办法将作为全局最优解(代码第(23)行-第(28)行)。

信息素强度变量(pheromone reinforcement amount)通过式(19)完成统计，每个虚拟机-物理主机的映射的信息素级别完成更新，经过式(18)，它可以模拟信息素的进化和分解过程(代码第(29)行-第(34)行)。

ACO-VMP优化算法中，信息素强度变量值主要体现在虚拟机-物理主机的映射过程中，并且处于全局最优解中。接下来，整个搜索新的局部最优解的过程不断重复，该算法在达到一定的循环次数nCycleTerm或者时间后，或者一直没有更优的全局最优解出现后结束(代码第(35)行)。

算法1： The ACO-VMPAlgorithm.

(1)Input:SetofPMs,setofVMs,setofantsantSet,Setofparameters

(2)Output:Global-best-solutionGBS

(3)Initialize,setpheromonevalueτv,ptoτ0,GBS∶=Φ，;nCycle∶=0

(4)repeat

(5)forallant∈antSetdo

(6)an.solution∶=Φ;ant.pmList∶=p

(7)ant.p∶=1;ant.vmList∶=v

(8)Shuffleant.vmList

(9)endfor

(10)antList∶=antSet;nCycle∶=nCycle+1

(11)whileantList≠Φdo

(12)pickanantatrandomfromantList

(13)ifant.vmList≠Φthen

(14)ifFVant(ant.p)≠Φthen

(15)ant.p∶=ant.p+1

(16)endif

(17)ChooseaVMvfromFVant(ant.p)accord.toEq(15)

(18)ant.solution.xp,v∶=1;ant.vmList.remove(v)

(19)else

(20)ant:solution.f∶=p;antList.remove(ant)

(21)endif

(22)endwhile

(23)forallant∈antSetdo

(24)ifant.solution.f

(25)GBS∶=ant.solution

(26)nCycle∶=0

(27)endif

(28)endfor

(29)ComputeΔτ

(30)forallp∈pdo

(31)forallv∈vdo

(32)τv,p∶=(1-δ)*τv,p+δ*Δτv,p

(33)endfor

(34)endfor

(35)untilnCycle=nCycleTerm

下面详细分析该算法主要4个阶段：

(1)信息素与初始信息素强度变量定义阶段:在ACO-VMP算法开始在每个虚拟机-物理主机映射对中，蚂蚁按照一个固定的信息素强度变量进行寻优，由于ACO-VMP沿用了早期的蚁群优化算法，采用一个局部最优解的质量评价办法，即强度基础算法(reference baseline algorithm，RBA)，它也是基于L1均值评测的首次适用递减算法，RBA用来计算初始化的信息素强度变量τ0。PE称为装箱的效率,那么就有

(13)

nVM标识了n个虚拟机，nActivePM表示了n个活动物理主机。装箱的效率就是所有虚拟机数和活动物理主机的个数的比值，装箱的效率有时候和虚拟机的尺寸密切相关，当装箱效率高的时候，虚拟机的尺寸比较小，也就是说一个物理主机上容纳了很多个虚拟机。

(2)启发式信息定义阶段:在全局最优解的寻找过程中，启发式的参数值ηv,p表示了局部最优解的每个虚拟机-物理主机对的映射质量评价情况。

在ACO-VMP算法的一个目标是通过平衡每个箱子中物品的个数，从而对物理主机进行虚拟机均衡放置，所以这里我们可以定义一个支持多维物理资源充分利用和物理资源平衡使用的参数ηv,p

ηv,p=w*|log10magRIVp(v)|+(1-w)Utilizationp(v)

(14)

这里magRIVp(v) 表示物理主机p在容纳了虚拟机v后的式(7)中提到的多维物理资源利用效率的启发式信息。magRIVp(v) 的对数函数Log10magRIVp(v) 是为降低magRIVp(v) 函数的取值范围。Utilizationp(v)表示物理主机p在容纳了虚拟机v后的多维的物理资源利用效率情况

(15)

w表示了权重，用来平衡多维物理资源利用效率的启发式信息和多维的物理资源利用效率。

(3)伪随机比例规则:当在构造一个局部最优解的时候，一个蚂蚁k选择一个虚拟机s放置到物理主机p， 它们采用的是下面的伪随机比例法则

(16)

q是均匀分布在区间[0,1]之间的随机数，q0是在区间[0,1]的一个参数。τv,p是与式(18)中的虚拟机-物理主机映射对相关的当前信息素变量。β是一个用来确定信息素和启发式参数值的相关性的一个非负参数。FVk(p) 定义了蚁群算法中第k个蚂蚁分配给物理主机的可能的虚拟机列表

(17)

当q≤q0的时候，虚拟机-物理主机映射对将出现最高的τv,p*[ηv,p]β值并且被选择出来作为局部最优解，否则的话一个虚拟机v将按照下面的随机比例法则以概率Pk(v,p) 被重新放置

(18)

(4)全局信息素强度变量更新:为了支持局部寻优操作，模拟蚂蚁信息素的挥发过程，不断循环迭代接近全局最优解，在虚拟机-物理主机映射对中，ACO-VMP提出了全局更新规则来完成信息素强度变量的更新，规则如下

τv,p∶=(1-δ)*τv,p+δ*Δτv,p

(19)

变量δ的含义是全局信息素延迟参数， 0<δ<1， Δτv,p是应用到每个虚拟机-物理主机映射对的信息素强度参数， Δτv,p的计算公式如下

(20)

4 仿真实验与性能分析

4.1 仿真环境与性能比较对象

参考了Cloudsim3.0工具包，在对应的代理中实现了蚁群算法的优化的代码。与ACO-VMP同时做性能比较的虚拟机放置的智能优化算法包括下面的：①遗传算法GA优化的虚拟机放置；②粒子群算法PSO优化的虚拟机放置；③萤火虫群算法GSO优化的虚拟机放置[12]；④自适应的最大最小蚁群算法MMVMC。

被模拟的云数据中心物理服务器总数为400个，物理服务器配置见表1：云数据中心的虚拟机的设置见表2。

表1 物理主机的硬件情况

表2 虚拟机的配置条件

表3 蚁群优化虚拟机放置算法参数设置

实验中比较了3个主要性能指标：①云数据中心的活动物理主机个数nActivePM； ②获得的装箱效率PE； ③云数据中心的能量消耗情况Etotal。

4.2 总体能量消耗情况与装箱效率

经过实验测试，得到了表4的实验结果，它显示了400个物理主机在1000个虚拟机个数情况下24小时内的ACO-VMP蚁群优化的虚拟机放置算法与4个优化算法的性能比较结果：

从表4可以看出，ACO-VMP优化算法在各个方面都优于其它4个算法。ACO-VMP优化算法的装箱效率PE最接近理想值，这也是物理主机负载均衡的一个重要体现，相对于其它智能优化算法，ACO-VMP优化可以节省大约10%-20%左右的能量消耗。

表4 各类虚拟机放置优化算法的性能比较

但是随着资源需求参数的变化(10%-25%)，在比较小(小VM尺寸)的资源需求参数情况下，ACO-VMP优化算法性能超过了MMVMC优化算法和GSO算法比例比较大。在比较大的资源需求参数情况下(大VM尺寸)，ACO-VMP优化算法性能超过粒子群优化PSO算法的比例比较大。

分析原因是ACO-VMP启发式虚拟机放置算法具有很好的灵活度，很容易把虚拟机尺寸比较小的多个虚拟机放置到同一个物理主机上，如果虚拟机尺寸太大，反而效果不明显。另一方面，在虚拟机尺寸比较大的情况下，萤火虫群优化GSO算法也可以获得比较高的整体物理资源利用效率，需求的活动物理主机个数比较少。

4.3 物理资源利用情况比较

表5显示了ACO-VMP虚拟机放置优化算法在1000个虚拟机个数情况下和其它4个智能优化算法的活动物理主机总体资源消耗比例Wastagep结果。表中实验结果表明，ACO-VMP优化算法可以很好减少物理资源的消耗的比例，这是因为ACO-VMP同其它4个算法比较起来，一直试图改善多个维度的物理资源利用效率，在整个4个不同虚拟机尺寸的情况下，所有维度的资源消耗都不超过21%，那么利用率就超过了79%，这样大部分物理资源都充分利用起来了。

表5 活动物理主机的资源消耗比例性能比较/%

5 结束语

本文提出了基于蚁群优化算法的虚拟机放置方法ACO-VMP。仿真结果表明，ACO-VMP具有很好的节能性能与资源利用效率。ACO-VMP可以作为企业构造节能的绿色大数据中心的参考。下一步的工作是将ACO-VMP与其它的更加多的智能优化的虚拟机分配策略进行性能比较，调整蚁群算法中的参数继续提高系统性能。