一种新的蚁群算法优化的虚拟机放置策略

(广州华商学院 数据科学学院, 广州 511300)

0 引言

大数据中心的构造与建设是近年来政府与云服务提供商越来越关注的问题，为了节省企业成本，这类数据中心的构造主要目标是绿色节能与物理资源的充分利用[1]。为了达到这2个目标，云计算中大多都使用了虚拟机迁移技术[2-3]。目前以Cloudsim云模拟器工具包及其研究思路为背景的大部分文献在虚拟机迁移研究方面处理世界领先地位，它将虚拟机迁移过程划分为物理主机状态检测、虚拟机选择、虚拟机放置3个步骤[4]，这3个步骤既具有独立性又互相关联，而且都可以通过算法进行优化[5-8]。

本文着重考虑采用智能算法的方式来优化虚拟机放置过程。虚拟机放置有些文献把它称为多目标优化问题或者装箱问题[9]，该过程有很多智能算法进行优化，例如遗传算法[10]、贪心算法[11]、粒子群优化算法[12]、萤火虫群优化算法[13]、蛙跳算法[14]等。本文依托于Cloudsim云平台工具包，在物理主机状态检测和虚拟机选择过程都采用Cloudsim中默认的优化策略；然后着重考虑采用蚁群算法的方式来优化虚拟机放置过程[15]。提出一种新型蚁群算法优化的虚拟机放置方法ACA-VMP。

ACA-VMP虚拟机放置优化策略参考了蚁群算法的思路，在自适应的蚁群算法中假设有大量的蚁群觅食的行为，在寻找最优解的过程中不断的交换一种称为信息素强度的参数，这样在一定程度上可以避免多目标优化算法中的局部最优解的“早熟”问题[16-17]。

ACA-VMP虚拟机放置策略考虑了物理主机的处理器、内存大小、网络带宽等多个资源维度的因素。与其他的虚拟机放置优化的智能算法比较起来，ACA-VMP的目标函数综合考虑整个大数据中心的总体能量消耗和云服务器端的服务质量Qos提高等目标[18-20]。

1 ACA-VMP建模与工作场景

1.1 虚拟机放置的问题描述

物理主机的描述向量如下：Pj=(idj,cpuj,memj,networkj)，M表示了物理主机的标识符，cpuj表示了物理主机的处理器的计算能力，有时候也用(Millions of Instructions Per Second, MIPS)来表示，memj表示了物理主机的可用内存大小，networkj表示了物理主机所拥有的网络带宽大小，每个虚拟机也可以通过下面的向量来表示：Vi=(idi,cpui,memi,networki)，idi表示了虚拟机的标识符，cpui表示了虚拟机的表示了对处理器的需求能力，memi表示了虚拟机对内存的需求能力，networki表示了虚拟机对网络带宽的需求能力。

虚拟机放置问题的含义是寻找一个最优的虚拟机到物理主机的映射，就把虚拟机迁移过程中前一虚拟机选择阶段的大量的虚拟机重新分配到大量物理主机之上，图1描述了这种在云客户端访问大数据中心的时候平台的虚拟机迁移机制开始工作后的场景。在这种最优映射条件下满足物理主机的资源利用效率是最高；或者整个云数据中心的能量消耗最小；或者是保证云数据中心的服务质量Qos较好，最好的情况是达到Pareto最优解。

图1 云数据中心虚拟机放置问题描述

1.2 ACA-VMP的工作场景

ACA-VMP依托了Cloudsim模拟器工具包，该工具包在运行模块中主要包括：全局代理Global Broker、本地代理Local Broker、虚拟机管理器Virtual Machine Manager[5]。

图2 ACA-VMP蚁群虚拟机放置优化策略实现模块

2 ACA-VMP的虚拟机放置过程描述

对于一个上面容纳了多个虚拟机的物理主机，它随时都可能成为源主机Pso。所有的源主机和源虚拟机都通过它们自身的物理资源利用效率进行描述：比如处理器、内存大小、网络带宽大小。类似的每个虚拟机都也可能成为潜在的源虚拟机，根据它自身的资源利用率情况，每个物理主机也可能成为潜在的目标物理主机Pde。所以ACA-VMP优化算法给每一次虚拟机放置动作都设计了一个元组，该元组由3个参数组成。

T=(pso,v,pde)

(1)

由于虚拟机放置这里元组可以类似于分布式旅行商问题中的连接各个城市的边。为了降低ACA-VMP优化算法的运行时间，必须降低的|T|值。所以在构造元组的时候，必须注意两个约束条件为真：

(2)

(3)

根据蚁群觅食寻优路径的分析，ACA-VMP优化算法的目标函数是：

(4)

M表示的是整个虚拟机迁移过程，Ps表示的是在执行虚拟机迁移过程M后，可以转入睡眠模式的所有物理主机的集合，根据|M|，γ是与睡眠数量Ps的相关的参数，它可以设置为常量。由于最终的目标是降低活动物理主机的个数，ACA-VMP的目标函数的定义可以根据睡眠主机数|Ps|来确定。

在ACA-VMP优化算法快结束的时候，它可以通过把虚拟机迁移到已经存在的正常状态的活动物理主机上从而降低整个云数据中心的物理主机数量，因为这个时候睡眠模式的物理主机可以进入关闭状态。这里有一个新的约束条件：

Ps={∀p∈P|Vp=φ}

(5)

该条件可以保证当所有的虚拟机都被迁移出去之后，物理主机将被切换到睡眠模式。

ACA-VMP算法中蚁群的信息素被分解成元组。每个蚂蚁使用一个状态比例规则完成对下一个元组的选择，该原则在蚁群算法中称为伪随机比例规则。蚁群算法中根据这个规则，第k个蚂蚁根据下面的公式选择一个元组：

(6)

q是均匀分布在区间[0,1]之间的随机数，q0是在区间[0,1]的一个参数。τ描述了信息素变量，η是与元组T=(pso,v,pde)相关的当前启发式参数值。β是一个用来确定信息素变量和启发式参数值的相关性的一个非负参数。Tk⊂T表示了经过了第k蚂蚁路径寻优之后的剩余的元组的集合。S是一个根据公式(6)的概率分布来确定的随机变量。第k个蚂蚁选择元组s的概率表示为ps，它可以通过公式(7)来计算：

(7)

一个元组的启发式参数值ηs可以根据蚁群算法[21-22]中的规则定义如下公式(8)：

(8)

Cpde表示了目标物理主机的整体资源提供能力；Upde表示了目标物理主机的整体资源利用效率；Uv表示了元组s上的虚拟机的利用效率；这里ηs是一个多维物理资源利用效率向量，它支持通过虚拟机迁移的方式完成低负载物理主机数量的降低。Upde+Uv≤Cp de这个约束条件可以避免虚拟机迁移之后目标物理主机的超负载。ACA-VMP优化算法中包括3个维度的物理资源：处理器、内存大小和网络带宽大小，根据蚂蚁群算法的公式(6)和公式(7)的条件完成优化之后，基本可以保证高信息素变量的集中和大量的物理主机资源释放。

在公式(7)中，指数函数有利于局部最优路径的快速收敛，保证了一个广泛的搜索路径。根据经典的蚁群优化算法，ACA-VMP采用了全局最优解和局部信息素更新规则，全局最优解采用更新规则，经过多次迭代后，蚂蚁路径的多次寻优，保证这个虚拟机放置优化策略的完成。信息素强度变量的更新规则如下：

(9)

(10)

变量α的含义是全局信息素延迟参数，0<α<1，M+表示了蚁群算法的虚拟机放置全局最优解。局部最优解也采用更新规则，规则如下：

τs=(1-ρ)*τs+ρ*τ0

(11)

变量ρ的含义是全局信息素参数α类似的参数，0<ρ<1，τ0是初始信息素级别变量，计算的公式如下：

τ0=(|M|*|P|)-1

(12)

ACA-VMP虚拟机放置优化算法的伪随机比例规则和全局信息素强度变量更新法则的目的都是要使得蚂蚁的搜索更加直接，伪随机比例规则更趋向于使虚拟机-物理主机元组T能够获得更高的信息素级别和高的启发式参数值。因此，蚂蚁就可以在更加邻近的区域寻找它们的全局最优解。

另外一个方面，局部信息素强度参数更新可以补充蚂蚁其他局部最优路径的寻找，这样也可以使得ACA-VMP虚拟机放置优化算法更快的接近全局最优解。这是因为无论何时蚁群在利用元组寻优的过程中，元组将失去它们自己的信息素，同时对其他的蚂蚁缺少更多的吸引力。因此这样它就有利于避免对局部最优解的”早熟”的情况。

ACA-VMP虚拟机放置优化算法的伪代码如下面的Algorithm1所示:

Algorithm 1 ACA-based VM placement

1:M+=φ,MS=φ

2: ∀t∈T|τt=τ0

3: fori∈[1,nI] do

4: fork∈[1,nA] do

6: fort∈Tdo

7: generate a random variableqwith a uniform

Distribution between 0 and l

8: ifq>q0then

9: computeps∀s∈T by using (7)

10: end if

11: choose a tuplet∈Tkto traverse by using (6)

13: apply local update rule in (11) ont

14: update used capacity vectorsUpsoandUpdeint

17:Mk=Mk∪{t}

18: else

20: end if

21: end for

22:MS=MS∪{Mk}

23: end for

24:M+=argmaxMk∈MS{f(Mk)}

25: apply global update rule in (9) on alls∈T

26: end for

最后在迭代过程中当所有的蚂蚁完成它们的路径寻优步骤后，程序将转入到MS虚拟机迁移过程中。每一次循环，Mk∈MS都要经过公式(4)的目标函数进行评估；M+表示了全局最优的虚拟机放置步骤。全局信息素参数规则根据公式(9)和公式(10)完成更新，当所有的迭代完成或者运行特定的时间之后结束，算法将输出全局最优问题解M+。为了描述方便，算法Algorithm1中涉及到的公式与符号都在表1中详细列出。

表1 ACA-VMP虚拟机放置策略的相关符号描述

3 仿真实验与性能分析

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

因为ACA-VMP基于蚁群算法优化的虚拟机放置是在虚拟机迁移过程中运用的，所以进行ACA-VMP实验分析，必须构造云数据中心的虚拟机迁移场景，本文参考了Cloudsim3.0工具包，同时依据图2中的功能模块，实现了基于Java语言的局部代理，根据Algorithm1在该代理中实现了蚁群算法的优化的代码。

ACA-VMP依托于Cloudsim云平台工具，在物理主机状态检测和虚拟机选择过程都采用Cloudsim中默认的优化策略:鲁棒局部回归物理主机状态检测(local regression robust, LRR)策略和最短时间虚拟机选择策略(minimum migration time，MMT)；

为了体现蚁群智能优化虚拟机放置策略的高效性与优秀性能，与ACA-VMP同时做性能比较的虚拟机放置的智能优化算法包括如下：

1)遗传算法GA优化的虚拟机放置[10]；

2)粒子群算法PSO优化的虚拟机放置[12];

3)萤火虫群算法GSO优化的虚拟机放置[13]；

4)自适应的最大最小蚁群算法MMVMC[24]；

被模拟的云数据中心物理服务器总数为800个，物理服务器配置如表2所显示。

表2 云数据中心物理服务器硬件配置

虚拟机迁移周期设置为10分钟一次，一共运行24个小时,每次统计一天内的能量消耗,在一周内重复运行五次取平均值，一周内每天虚拟机请求的个数如表3。

表3 ACA-VMP虚拟机放置策略测试环境

虚拟机的放置中有一个装箱效率的概念[19]，可以认为是虚拟机粒度，我们设置为至少4个，一共4个类型，装箱效率分别为10，6.75，5，4，这样设置的原因是为了体现云平台有不同资源需求大小尺寸的虚拟机来访问云数据中心。例如装箱效率如果为10，这样说明这个虚拟机尺寸比较小，一个物理主机上最多可以容纳10个虚拟机，那么最理想装箱效率就为10。ACA-VMP蚁群算法的其他参数初始化设置如表4。

这里比较了4个主要性能指标：1)云数据中心的能量消耗；2) 装箱效率；3)虚拟机迁移次数；4)云数据中心的SLA违规率；

3.2 仿真结果与性能分析

3.2.1 云数据中心的能量消耗和装箱效率

为了实验测试的需要，表5显示了在1 000个虚拟机个数情况下ACA-VMP蚁群优化的虚拟机放置算法与4个优化算法的能量消耗、装箱效率的性能比较结果：从表5可以但是随着虚拟机粒度参数的变化，在比较小(粒度为10和6.75)的资源需求参数情况下，ACA-VMP优化算法优化的性能超过MMVMC优化算法和GSO算法，性能提高比例比较大。在比较大的资源需求参数情况下(粒度为5和4)，ACA-VMP优化算法性能超过粒子群优化PSO算法的比例比较大。

表4 ACA-VMP虚拟机放置优化策略参数设置

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

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

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

3.2.2 虚拟机迁移次数和SLA违规率

表6显示了在4种虚拟机粒度下ACA-VMP的虚拟机优化策略的迁移次数低于PSO策略、GSO迁移策略、MMVMC策略，随着粒度的增强，虚拟机迁移次数逐渐减少；而遗传算法GA优化的策略虚拟机迁移次数在某些条件下还要小于ACA-VMP策略。

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

原因是ACA-VMP策略中设计的能量消耗模型考虑问题的维度比较广泛，包括处理器、内存、磁盘和网络带宽，局部和全局的信息素强度更新变量可以使得虚拟机放置过程不断优化，提高了资源的利用效率，使得负载比较均匀的放置在各个活动物理主机之上，迁移次数降低。但是在这个过程中也不一定是最优的，ACA-VMP优化策略立足于能量消耗最小而不是立足于迁移次数最小，所以遗传算法GA的迁移次数少于ACA-VMP优化策略也是可以接受的。

当一个云客户端提交作业到云计算平台的时候，如果云平台没有提供合适的物理资源，就会出现服务等级协议(Service Level Agreement,SLA)违规。从表6可以看出，不同虚拟机粒度条件下，ACA-VMP优化策略的SLA违规率比PSO优化策略、GSO优化策略、MMVMC策略要低，随着粒度的增强，SLA违规率逐渐减少；有这样的实验结果的原因是ACA-VMP中的各类资源约束条件在物理主机状态检测阶段尽量避免物理资源使用率超过100%的情况，从而间接的避免SLA违规事情的发生。大粒度虚拟机访问一次需要稳定的资源，云服务器虚拟机迁移次数少，SLA违规率自然降低。

4 结束语

本文采用蚁群优化启发式智能算法，针对云数据中心的绿色节能和高服务质量两个目标，提出了一种新的蚁群算法优化的虚拟机放置方法ACA-VMP。实验结果表明和常见的智能优化的虚拟机放置策略比较起来， ACA-VMP在总体能量消耗、装箱效率、虚拟机迁移次数，SLA违规率等方面性能较好。ACA-VMP 策略的目前只是在虚拟机放置阶段，它还可以和虚拟机选择阶段的优化策略结合起来使用，这个是本文的后续工作。