基于蚂蚁群体智能的多目标虚拟机合并优化

李玉萍 陈丽娜

(商丘师范学院信息技术学院 河南 商丘 476000)

0 引 言

数据中心由数以万计的物理主机PM组成，这些物理资源会导致大量能耗，不仅会增加运营成本，还会导致巨大的碳排放[1]。同时，数据中心的高能耗主要是由资源利用不充分导致的[2]。虚拟化使性能独立的虚拟机VM可共享同一主机，以改善资源利用率，而虚拟机合并及空闲主机的休眠或低功耗转换则可以进一步改善资源利用率和能耗。虚拟机合并是改善数据中心能效的最有效方式[3]，利用动态的虚拟机迁移的合并技术可以将虚拟机部署于数量更少的主机上。虚拟机合并主要通过迁移手段实现，在不同主机间的虚拟机迁移可以关闭闲置主机[4]。虚拟机合并的性能度量指标主要包括：释放的主机数量(需最大化)、虚拟机迁移次数(需最小化)以及算法运行时间(需最小化)。虚拟机合并问题本身是NP问题，求解技术如混合整数线性规化方法[5]，但其寻优时间达到指数级。其次是元启发式方法，可在多项式时间复杂度内有效搜索可行解空间。

自适应元启发式蚂蚁群体智能优化方法是求解虚拟机合并的有效方法，已有的研究多集中于通过单目标单群体的聚合目标函数AOF来联立多目标[6]，AOF方法的好处在于可以降低时间复杂度，通过限制可行解的子空间搜索来改善算法运行效率。然而，该方法的不妥之处在于无法准确地赋予各个目标需要考虑的权重，仅能通过主观意识赋值。且AOF可能无法以恰当的方式联立优化目标。已有的蚂蚁群体虚拟机合并算法的AOF均未对优化目标进行优先关系排序。

本文设计了一种最大化主机释放量且虚拟机迁移量最小的虚拟机迁移方法实现虚拟机合并，其主要贡献在于：1) 实现了多目标多群体优化。算法扩展已有虚拟机合并单目标单群体优化思想，实现多目标多群体的蚂蚁群体优化。2) 降低了搜索空间。算法通过设置约束在未降低解质量前提下排除了合并过程中的部分迁移方案，使得算法更快收敛，可扩展性增强。

1 相关工作

蚂蚁群体优化ACO启发式方法受蚂蚁觅食行为启发，其从食物源至蚂蚁巢的食物运输会跟随路径上的信息素这类化学物质进行追踪。该方法允许蚂蚁之间直接通信以寻找起始点最优的路径。虽然每个蚂蚁可以找到一个可行解，但高质量解是来源于间接通信和蚂蚁之间的全局协作得到的结果。ACO算法的类型包括蚂蚁系统AS、蚂蚁群体系统ACS以及最大最小蚂蚁系统MMAS，其中，ACS是当前最优的解决方案。已有虚拟机部署和合并研究中，文献[7]利用ACO解决了非线性资源分配问题，得到受限资源下任务的最优分配。文献[8]利用改进的ACO进行多目标资源分配求解。文献[9]利用单目标单群体MMAS算法求解虚拟机合并问题。文献[10]将向量代数机制整合到ACS中，优化了资源利用率。文献[11-12]设计了单目标单群体ACS算法进行虚拟机合并求解。文献[13]利用多目标ACS解决两个目标优化问题：能耗最小和资源浪费最小，但方法并没有进行虚拟机迁移，仅在初始部署考虑优化目标。

已有ACO的虚拟机合并方法与本文算法的不同在于：已有方法趋向于利用AOF的单目标单群体ACO算法尝试联立多目标，而本文算法直接利用相互独立的两个蚂蚁群体设计多目标的ACS算法。群体一最大化释放主机数量，群体二最小化虚拟机迁移量。并且在解空间的搜索上通过设计三种约束进行了优化，极大地降低了最优解的搜索时间。

2 多目标虚拟机合并蚂蚁算法MOACS

2.1 基本说明

本文提出一种多目标虚拟机合并蚂蚁算法MOACS，算法的第一个目标是最大化释放主机的数量|PR|，第二个目标是最小化虚拟机迁移数量nM。由于拥有更大主机释放数量的全局最优迁移方案Φ+总是优于较低主机释放量的迁移方案Φ+的，即使该方案中的虚拟机迁移量大于后一迁移方案，即最大化|PR|优先于最小化nM。本文用到的其他相关符号及说明如表1所示。

表1 符号说明

2.2 算法基本原理

MOACS算法结构如图1所示，算法通过协调两个不同单目标优化种群的运行，实现最终双目标的同步优化。优化主机释放量通过群体ACS|PR|进行优化，优化虚拟机迁移量通过群体ACSnM进行优化。两个群体独立运行并利用独立的信息素和启发值，但两个群体会协作产生全局最优迁移方案Φ+。

图1 算法结构

虚拟机合并中，每个主机p上可寄宿多个虚拟机v。至少寄宿一个虚拟机的主机称为潜在源主机，主机和虚拟机均具有资源利用率属性，包括CPU利用率和内存利用率。MOACS算法还引入了主机邻居概念。邻居表示相互排斥的P的子集。一个邻居是一个抽象实体，代表数据中心中位于邻近位置的主机集合，那么，数据中心的主机可以构成主机的一个邻居。一个虚拟机可被迁移至任意邻居N的其他主机上。因此，源主机的邻居内的和以外的其他主机也是一个潜在目标主机，也具有资源利用率属性。基于此，MOACS算法建立一个元组集合T，每个元组t∈T由三个元素组成：源主机pso、虚拟机v及目标主机pde。

T=(pso,v,pde)

(1)

算法1Multi-objective Ant Colony System-MOACS算法

1. While until a stopping criterion is met do

2.Φ+=∅

//全局最优迁移解赋空集

10. consolicate VMs according to Φ+and terminate released PM

11. end while

算法1的时间复杂性分析。算法的计算时间主要取决于元组|T|的数量，为了降低计算时间，MOACS设计了三种约束，可通过移除部分元组降低搜索空间。第一重约束确保仅未充分利用的主机可作为源主机，第二重约束仅允许未充分利用主机可作为目标主机，即排除从利用充分的主机上迁移和迁移至充分利用的主机上两种情况，这可以防止已利用充分的主机出现超载。而从利用充分主机上进行虚拟机迁移也不可能导致源主机的终止，进而不会降低总主机请求数量。第三重约束通过防止邻居内迁移进一步限制|T|的大小。因此，作为通用规则，一个虚拟机仅能被迁移至其源主机的邻居内的主机上。该规则唯一例外是一个邻居仅有一个主机，此时，该主机上的虚拟机可被迁移至任意邻居的任意主机上。通过这三种规则的定义与利用，可以在不降低解质量的同时极大地缩短算法的计算时间。

算法1的空间复杂度分析。MOACS算法空间复杂度为O(|T|)。而且，最差空间复杂度对应于具体的虚拟机合并场景，与主机的利用程度无关。此时，每个主机可视为一个目标主机。最差情况下元组的最大数量计算为：

max|T|=|P||V|(|N|-1)

(2)

式中：|P|为主机数量，|V|为虚拟机数量，|N|为邻居大小。由于实际的虚拟机合并场景中通常包括一个或多个充分利用的主机，而所提算法可以排除从该类主机进行的迁移，故元组数量|T|通常小于最差场景中的数量。

2.3 基于PM释放量最大化的优化算法ACS|PR|

ACS|PR|的目标是优化主机释放量|PR|，即算法目标函数为：

maxf(Φ)=|PR|

(3)

由于虚拟机合并的首要目标是最小化活动主机的数量，目标函数的定义将根据主机释放量进行定义。且当执行迁移方案时，将利用一种约束，通过将迁移限制在仅为释放主机PR集合以外的主机上，以降低虚拟机迁移量nM，即：

pde∈P|pde∉PR

(4)

算法中，当其上的所有虚拟机被迁移后，该主机才视为已释放主机。因此，释放主机集合PR可定义为：

PR={p∈P|Vp=∅}

(5)

式中：Vp表示运行于主机p上的虚拟机集合。因此，当不再寄宿任意虚拟机时，一个主机仅包含于释放主机集合PR中。

虚拟机合并问题中，蚂蚁根据式(1)定义的元组存放信息素。nA个蚂蚁中的任一蚂蚁利用随机状态转换规则选择可穿过的下一个元组，ACS|PR|中的状态转换规则即为伪随机比例规则。根据该规则，蚂蚁k选择下一元组的规则为：

式中：argmax返回[τ][η]β得到其最大值的元组，q∈[0,1]为均匀分布随机变量，q0∈[0,1]为一个参数，S为根据式(7)的概率分布选择的随机变量，蚂蚁k选择元组s穿越的概率probs定义为：

(7)

元组s的启发值ηs定义为：

可知，拥有最小未利用能力的目标主机将获得最高启发值。因此，启发值偏向于导致主机利用不足降低的虚拟机迁移，而Upde+Uv≤Cpde可防止虚拟机迁移带来目标主机pde的超载。

式(6)和式(7)中的随机状态转换规则偏向于选择拥有更高信息素浓度的元组。式(6)中q≤q0的第一种情况选择能够得到[τ][η]β最大值的元组，而第二种情况则根据式(7)选择元组。第一种情况有助于蚂蚁快速的收敛于高质量解，而第二种情况则有助于蚂蚁通过基于宽度的搜索空间拓展避免蚂蚁的搜索停滞。除了随机状态转换规则，ACS|PR|还利用了全局和局部信息素踪迹蒸发规则。全局信息素踪迹蒸发规则利用于所有蚂蚁完成其迁移的一次迭代的结束时，定义为：

局部信息素踪迹更新规则应用于当蚂蚁穿越该元组做出自身的迁移方案时的元组，定义为：

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

(11)

式中：ρ∈(0,1]类似于α，τ0表示初始信息素，计算为主机数量|P|与近似最优解|Φ|的乘积的逆值，即：

τ0=(|Φ|·|P|)-1

(12)

ACS|PR|中伪随机比例规则和全局信息素踪迹更新规则可以使搜索更有指向性，伪随机比例规则偏向于选择更高信息素和更高启发值的元组，因此，蚂蚁可以在迄今全局最优解的极邻近区域搜索高质量解。此外，局部信息素踪迹更新规则可补充搜索与全局最优解相距较远区域中的其他高质量解。这是由于无论何时蚂蚁穿越一个元组，应用局部信息素更新规则，元组信息素均会损耗，对于其他蚂蚁的吸引会变差。因此，这有助于避免所有蚂蚁停滞于搜索相同解或过早收敛于子最优解。

算法2ACS|PR|算法

2.t∈T|τt=τ0

//元组信息素初始化

3. fori∈[1,nI] do

4. fork∈[1,nA] do

7. computeprobsby using (7)

//计算蚂蚁的穿越概率

8. choose a tuplet∈Tto traverse by using (6)

10. apply local update rule in (11) ont

//更新元组

11. if the migration intdoes not overload destination PMpdethen

//元组的迁移未导致主机超载

12. update used capacity vectorsUpsoandUpdeint

15.Φk=Φk∪{t}

//更新蚂蚁k的迁移方案

16.M=M∪{Φk}

18. apply global update rule in (9) on alls∈T

//更新所有元组

算法2的时间复杂度分析。ACS|PR|的时间复杂度为O(nI×|T|2)，nI表示蚂蚁代数，|T|表示元组数量。从算法2可知，步骤3的主循环需要迭代nI次，步骤4的第二重循环并不会增加时间复杂度，由于蚂蚁会同步建立其迁移方案。步骤5的循环需要迭代|T|次，步骤7的概率计算需要在|T|上进行迭代。综上可得算法的时间复杂度为O(nI×|T|2)。

2.4 基于VM迁移量最小化的优化算法ACSnM

ACSnM的目标寻找虚拟机迁移量更少且至少与Φ+中主机释放量PR相当的迁移方案，即算法目标函数为：

maxg(Φ)=(nM)-1

(13)

由于虚拟机迁移是资源密集型操作，ACSnM的目标函数可定义为迁移量的逆值。

ACSnM中的蚂蚁同样利用式(6)和式(7)的伪随机比例规则选择需穿越的下一元组。且式(8)中的启发值更偏向于拥有更多的已利用能力向量的虚拟机Uv。这样，更可能导致虚拟机迁移量降低的虚拟机迁移操作将得到更高的启发值。因此，式(8)中的启发值支持ACSnM中式(13)定义的目标函数。

ACSnM群体同样利用式(11)中的局部信息素踪迹更新规则，然而，全局信息素踪迹更新规则需要重新定义为：

算法3ACSnM算法

2.t∈T|τt=τ0

//元组信息素初始化

3. fori∈[1,nI] do

4. fork∈[1,nA] do

7. computeprobsby using (7)

//计算蚂蚁的穿越概率

8. choose a tuplet∈Tto traverse by using(6)

10. apply local update rule in (11) ont//更新元组

11. if the migration in t does not overload destination PMpdethen

//元组的迁移未导致主机超载

12. update used capacity vectorsUpsoandUpdeint

15.Φk=Φk∪{t}

//更新蚂蚁k的迁移方案

16.M=M∪{Φk}

//基于式(13)得到全局最优方案

18. apply global update rule in (14) on alls∈T

//更新所有元组

算法3的时间复杂度分析。ACSnM的时间复杂度与ACS|PR|相似，由于ACSnM与ACS|PR|两个群体均是同步且独立运行。

3 仿真实验

3.1 实验说明

本节测试MOACS的性能，对比算法选取同为蚁群系统的优化，包括单目标单群体的虚拟机合并算法Feller-ACO[9]及ACS[8]算法。虚拟机合并的输入参数包括：主机数量、合并虚拟机的数量、虚拟机的CPU利用率、虚拟机的内存需求以及每个虚拟机的当前位置。为了观察算法可扩展性和适应性，在主机上建立四种不同场景测试：1) 低CPU低内存请求；2) 高CPU大内存请求；3) 高CPU小内存请求；4) 低CPU大内存请求。实验利用随机负载、同质虚拟机和同质主机进行测试。实验参数见表2和表3。对于场景1)，合并的虚拟机数量设置为1 000，主机数量为100，比例为10∶1，其他三种场景设置1 000个虚拟机和200个主机，比例为5∶1。邻居规模设置为5，邻居随机选择。表3是与蚁群智能优化过程相关的参数设置。实验中需要考虑的指标包括：合并后最大化的释放主机数量、包装效率(释放的主机数量与总主机数量的比值)、合并后最小化的虚拟机迁移量以及算法的求解时间。

表2 场景设计

表3 蚂蚁群体参数设置

3.2 实验结果

1) 释放主机量与包装效率。

图2是算法在不同实验下得到的释放主机数量的箱形图，表4是相应的数值结果，包括包装效率。结果表明，MOACS算法可以比Feller-ACO多释放25%～37%的主机。在场景1中，MOACS释放了15个主机(10次测试的中位值)，而Feller-ACO仅释放11个主机。由于包装效率需由释放主机量推导，该指标也具有类似的趋势。

图2 释放主机数量

场景参数ACSMOACSFeller-ACOChangep-value1中位值91511136%0.005标准差0.630.520.82--包装效率9%15%11%--2中位值7118137%0.005标准差0.670.670.99--包装效率3.5%5.5%4%--3中位值7108125%0.004标准差0.670.520.82--包装效率3.5%5%4%--4中位值7118137%0.005标准差0.880.880.74--包装效率3.5%5.5%4%--

2) VM迁移量。

图3是算法得到虚拟机迁移量结果，表5同步给出数值结果。可以看出，MOACS在此目标上也是优于Feller-ACO的，MOACS仅利用Feller-ACO 虚拟机迁移量的82%即可得到更好的包装效率。在场景1中，MOACS拥有189次虚拟机迁移，而Feller-ACO拥有226次迁移。

图3 虚拟机迁移量

场景参数ACSMOACSFeller-ACOChangep-value1中位值91511136%0.005标准差0.630.520.82--包装效率9%15%11%--2中位值7118137%0.005标准差0.670.670.99--包装效率3.5%5.5%4%--3中位值7108125%0.004标准差0.670.520.82--包装效率3.5%5%4%--4中位值7118137%0.005标准差0.880.880.74--包装效率3.5%5.5%4%--

3) 执行时间与可扩展性。

该指标度量算法搜索全局最优解的执行时间。图4是基于场景2三种算法得到的结果，此时设置的主机数量由50至500以步长50递增，虚拟机数量由250至2 500以步长250递增。可以看出，MOACS优于Feller-ACO，而ACS是优于MOACS的，由于其仅是单目标优化，搜索时间更短，而MOACS需要在两个目标上进行搜索。

图4 算法运行时间

进一步，实验在场景1下利用|P|=1 000和|V|=1 000进行了比较分析，如表6所示。该场景下，ACS得到的时间多少1分钟，比较而言，MOACS几乎运行2分种，而Feller-ACO需要6分种。同时还观察到，时间变量的标准差均是较小的，前两种算法的时间差则差别较大。

表6 场景1下的算法执行时间

4) 结论分析。

总体来看，MOACS在所有测试指标下均优于Feller-ACO，包括释放的主机量、包装效率以及虚拟机迁移量和执行时间。Feller-ACO利用单目标单群体下AOF，联合了两种不同的目标，包括释放主机量和虚拟机迁移量，MOACS利用多目标算法，考虑的是两个独立的蚂蚁群体分别进行优化。Feller-ACO中的AOF利用多个参数决定全局优化过程两个目标的相对重要性，该方法的不足在于：1) 无法准确找到AOF中合适的参数值；2) AOF可能无法做到不同目标间的合理联立。例如：MOACS中最大化释放主机量是占优于最小化虚拟机迁移量的，而Feller-ACO中的AOF不支持目标间的占优关系。此外，MOACS采用了搜索空间的约束机制(三种约束)，可以极大地降低算法的运行时间，且不会影响到解的质量。同时，MOACS与ACS相比，拥有更多的主机释放量和更少的虚拟机迁移量，但其运行较ACS更慢。比较ACS与Feller-ACO，ACS更慢且虚拟机迁移量更少，尽管该算法没有实现相同的包装效率。

4 结 语

本文提出了一种新的多目标蚂蚁群体算法进行数据中心的虚拟机合并，算法可以建立虚拟机迁移方案，通过利用不充分的主机上的虚拟机迁移和合并降低物理主机的请求量。在此过程中，目标函数设置为最大化主机释放量与最小化虚拟机迁移量。以大量的实验对算法进行了验证，并与两种已有的蚂蚁优化算法作对比，所提算法在多种实验场景下的性能均是较优的。进一步研究算法实际的能效，本文仅从优化主机使用数量与虚拟机迁移次数上着手优化虚拟机合并，但虚拟机的具体部署结果也会对能效产生影响，此时需要计算具体的部署时的能效问题，然后再设计能效更高的部署算法。