基于蚁群算法的虚拟机双目标优化部署方法

裴 多

(重庆市综合经济研究院 信息化研究中心，重庆 401147)

0 引 言

云计算的核心技术包括灵活接入的移动终端、硬件技术、海量存储技术、虚拟化技术以及分布式并行计算。云平台灵活高效地资源配置和管理得益于上述各种技术的成熟。其中，虚拟化技术实现对数据中心存在的零散资源进行有效整合，并对虚拟化后的抽象资源进行统一管理、配置和监控，一定程度上改善了云服务提供商资源利用率低和运营成本高的问题。然而，虚拟机的放置是一个从虚拟机到物理主机映射的过程，虚拟机的放置优化问题，是多个目标相互作用相互影响，复杂困难的组合优化问题，因此，解决多目标虚拟机部署策略是云数据中心提高资源利用率[1]和节省能耗[2]的关键。Liu等[3]提出了基于蚁群算法的虚拟机放置算法，该算法通过减少物理服务器的运行数量以及提高物理资源的利用率来降低系统的能耗问题。文献[4]则采用生物物理学的优化方法来放置虚拟机，通过该方法减少资源的浪费以及能耗。文献[5]提出了基于缓存竞争意识的虚拟机放置算法。

线性规划方法是虚拟机放置的传统分析方法。Chen等[6]采用整数线性规划来对虚拟机的放置与迁移进行求解，用于解决云中虚拟机整合时带来的缓存竞争问题。文献[7]以提高链路利用率为目的，采用线性规划来描述路线分配问题，并提出基于多项式时间的虚拟机放置的启发式算法。此外，文献[8]也采用整数线性规划来描述了面向服务的虚拟机放置问题，并使用树算法来得到虚拟机的放置方案，从而降低通信成本以及建设成本。

遗传算法是另外一种虚拟机放置优化算法。Tang等[9]提出了基于遗传算法的虚拟机放置算法，该算法综合考虑了物理机器以及通信网络带来的能源消耗问题。同时，为提高遗传算法的效率，提出了混合的遗传算法。文献[10]研究了动态环境下面向代理服务器的虚拟机放置问题，综合考虑了变化的资源供应、提供商的定价以及租户的动态需求三方面因素，使用遗传算法得到高质量的可伸缩性强的放置方案。

约束规划方法也被用于虚拟机放置。为提高数据的安全性，文献[11]通过研究分析数据存在的安全隐患来构建信息泄露约束条件，在保证满足该约束条件下进行虚拟机的放置。由于之前的虚拟机放置研究没有考虑物理机器拥有多个处理器的情况，导致单个物理机器的调度变得更加复杂。因此，文献[12]采用约束规划来描述物理机器中多个处理机的调度问题，并使用改进后的约束规划方法求解虚拟机的放置问题。

虚拟机部署策略经常被描述为向量装箱问题的变体问题，这是一个NP-hard问题。为了解决这个问题，各种启发式算法被提出。Li等[13]在虚拟机放置问题时，考虑了由网络通信量以及物理机器的利用造成的开销，采用基于二进制搜索算法来确定所需物理机器的个数以及放置问题。文献[14]提出了基于信息改进的烟花算法(IEFWA)。作者以降低数据中心的能耗问题为目的，结合IEFWA算法与基于生物地理学的优化算法(BBO)来求解虚拟机的放置问题。

上述研究成果都把虚拟机部署策略用单一目标实现，然而在云数据中心，为了提高资源利用率和降低能耗，需要考虑多个优化目标。因此，本文提出了基于蚁群智能的虚拟机多目标优化部署策略，首先给出多目标优化问题的描述，然后建立优化目标函数，采用蚁群算法对双目标函数求解，最后与降序首次适应算法进行实验验证。

1 蚁群算法

1.1 基本蚁群系统的机制原理

基本蚁群算法的优化机理包括两个阶段：适应阶段和协作阶段。首先是适应阶段，每只蚂蚁依据自己对信息的累积选择和调整其认为最优的路径，路径上的信息量越大，说明选择该路径的蚂蚁越多；在协作阶段，蚂蚁之间通过信息素共享信息，以便产生更能优化性能的解，与自动机的学习机理一致。

1.2 基本蚁群系统的数据模型

蚂蚁在探索路径的过程中，依据各条路径上信息量的多少决定其跳转的方向。禁忌表tabk用于标记第k只蚂蚁已经走过的元素，随着蚂蚁对路径的不断探索，禁忌表tabk进行动态调整。在向最优路径进化的过程中，蚂蚁依据各条路径上积累的信息量和路径的自身的启发信息来权衡当前路径是最优路径的概率。

1.3 改进的蚁群算法

蚁群系统具有方便和其它算法相结合，较强的鲁棒性等优点，但是算法探索时间长、容易收敛于局部最优解是尤为明显的缺点。

精英策略的蚂蚁系统[15](elitist ant system，EAS)，基于排列的蚂蚁系统[16](rank-based AS，ASrank)，最大最小蚂蚁系统[17](MAX-MIN ant system，MMAS)都对AS进行了少量的修改而获得了更好的性能。1997年，蚂蚁算法的创始人M.Dorigo又提出了一种具有全新机制的蚁群算法[18](ant colony system，ACS)，这是蚁群算法发展史上的又一新突破。

ACS和AS之间存在以下3方面的不同：

(1)采用一种伪随机比例规则确定下一个要选择的元素，在开发当前路径与探索新路径之间权衡。

(2)信息素全局更新规则只在当前探索的最优路径上消耗与释放信息素。

(3)蚂蚁每次跳转到一个元素后，按照信息素局部更新规则，都会挥发该边上一定量的信息素，以此来增大其它蚂蚁探索剩余路径的概率。

与AS相比，蚁群系统ACS重新定义了状态转移规则，信息素全局更新规则以及信息素局部更新规则。

(1)状态转移规则

一只位于元素i的蚂蚁要确定下一个移动到的元素，应用式(1)和式(2)给出的规则，即伪随机比例规则

(1)

其中

(2)

式中：η(i,j)为启发函数，代表蚂蚁从元素i跳转到元素j的期望程度值。β为期望启发式因子，用于调整启发信息在路径选择时的重要性，反映出蚂蚁在探索路径的过程中启发信息在蚂蚁选择路径中的受重视程度，β值越大，表示蚂蚁偏向于贪心规则选择路径的可能性越大。集合(C-tabk)是第k只蚂蚁下一步可以选择的元素集合。q为在[0,1]区间均匀分布的随机数，q0是决定了利用先验知识与探索新路径之间的相对重要性。

(2)信息素全局更新规则

ACS运用了更加大胆的规则确定路径上的信息，即只增大全局最优路径上的信息素

τij(t)=(1-ρ)×τij+ρ×Δτb(i,j)

(3)

其中

(4)

式中：ρ是信息素挥发参数，取值范围为：0<ρ<1，Cb为从寻路开始到当前为止全局最优的路径长度。

(3)信息素局部更新规则

ACS引入了负反馈机制，每当一只蚂蚁由一个元素跳转到另一个元素时，该路径上的信息素将依据式(5)挥发掉一部分，实现信息素的局部更新，以此降低已经走过的路径再次被选定的几率

τij=(1-ξ)×τij+ξ×τ0,0<ξ<1

(5)

ACS算法[18]在搜索时间长、易陷于局部最优解两个方面都有明显改善。

2 双目标优化模型的建立

虚拟机放置优化问题是一个多目标优化问题。根据前面对多目标问题描述，我们首先给出两个优化目标：资源模型和能耗模型。

资源模型主要考虑两种资源CPU和内存。物理主机资源利用率和虚拟机放置有很大关系，为了实现多维资源综合利用[19]，下面给出计算资源未利用模型

(6)

式中：wj为第j台物理主机的资源浪费率，P表示CPU资源，M表示内存资源，l是未利用资源比例，T是主机最高资源利用率。

目前研究表明能耗和CPU利用率是线性关系[20]，为了节省能耗，物理主机的能耗忽略不计。第j台物理主机的能耗可以表示为

(7)

式中：u为资源利用率。

上面给出了资源模型和能耗模型，为了提高资源未使用利用率和降低能耗，我们建立如下目标优化函数。r表示请求资源，v表示第v台虚拟机，S表示放置在第j台主机上的虚拟机的集合

(8)

(9)

约束条件：①每台虚拟机只可以放置在一台物理主机上；②各个虚拟机请求资源的总和不可以超过最高资源利用率；③每个虚拟机的资源请求不会超过最高资源利用率。

3 双目标优化模型求解算法描述

该小节寻找提高资源利用率和节省能耗的虚拟机放置方案，提出基于ACS双目标虚拟机放置(bi-objective VM placement ACS，bi-OVMPACS)算法。

3.1 信息素和启发信息定义

设有m台虚拟机放置到n台物理主机，为了记录虚拟机分配到物理主机的信息素定义一个m行n列的矩阵τm×n,τij表示虚拟机i放置到主机j的信息素。在初始化阶段，τm×n的值为

(10)

其中

(11)

定义矩阵ηm×n记录虚拟机放置到主机的启发信息，ηij表示虚拟机i放置到主机j的启发信息。虚拟机放置到主机要同时考虑资源利用率和能耗两个优化目标，因此

(12)

(13)

(14)

3.2 虚拟机选择规则

根据ACS的伪随机比例状态转移规则，定义虚拟机选择规则

(15)

其中

(16)

式中：q为[0,1]之间的随机数，q0是[0,1]之间的一个常数，α为信息素和启发信息的相对重要程度，ppej是选择某个虚拟机的概率，Ωj则是待放置虚拟机可以放置到主机j的集合。

3.3 信息素更新规则

信息素更新规则是影响虚拟机放置的重要部分，蚂蚁经过的路径信息素增加，同时信息素随时间挥发，因此信息素可能增加可能减少。信息素的挥发有利于避免算法快速收敛于局部最优，同时扩大搜索空间。该算法信息素更新包括两部分：信息素局部和信息素全局更新。

式(17)表示虚拟机i放置到主机j后信息素局部信息素更新规则，β表示局部信息素挥发参数

τij(t)=(1-β)×τij(t-1)+β×τ0

(17)

当所有的蚂蚁都找到了一条路径之后，按照上文介绍的比较规则，选择最优路径H进行信息素全局更新，更新规则如下

(18)

4 实验结果与分析

4.1 蚁群行为和参数对算法性能影响的分析

在蚁群算法中，参数是影响算法求解性能和效率的关键因素之一。目前，蚁群算法中的参数设置暂且没有系统的理论依据和通用的操作方法，一般情况下依据经验和大量实验数据确定参数值。下面就bi-OVMPACS算法中的参数α，β，γ，antNum对性能的影响进行简要分析。

(1)参数α。信息素是表示先验信息的载体，而启发信息是表示未来信息的载体[21,22]。参数α并不用来影响信息素和启发信息，而是用以控制二者之间的相互作用。根据式(15)、式(16)可知，当α=0时，演变为无信息素影响的bi-OVMPACS算法；当α=1时，演变为无启发信息影响的bi-OVMPACS算法。

(2)参数β，γ。在蚁群算法中，各只蚂蚁之间通过信息素进行合作，以增大迅速发现最优解的概率。在bi-OVMPACS算法中，参数β和参数γ都与信息素更新密切相关。信息素局部更新规则运用负反馈机理，以信息素局部更新因子β，局部调整信息素，减小再选择已经走过路径的概率，增大对新路径探索的概率。信息素全局更新规则运用“精英策略”，只对当前状况下最优路径上的信息素进行调整，而其它路径上的信息素不变。如果信息素全局更新因子γ过大，会造成算法的随机性和全局搜索能力，而且已探索过的路径再次被选定的几率太大；如果γ太小，虽然算法的随机性和全局探索能力有所增强，但是探索到最优路径的时间消耗太多。

(3)参数antNum。蚂蚁数antNum值大，能够增加算法的全局探索能力和稳定性，然而antNum值太大，造成大量的曾经被确定的路径上的信息量趋于均值，算法收敛速度减慢。反之，antNum太小，造成未来被探索的路径上的信息量接近于0，减小了全局探索的随机性，虽然收敛速度快，但算法的稳定性较差。

4.2 实验参数

bi-OVMPACS算法实验参数取值见表1。

表1 bi-OVMPACS算法实验参数值

设置虚拟机选择规则中的参数α=0.5，使先验信息素和后验信息素同等重要；信息素更新规则中的参数β=γ=0.4；根据Dorigo M等[18]的研究设置蚂蚁数antNum与虚拟机数之比为2∶3；迭代次数itNum=20。

4.3 实验结果对比及分析

为了验证bi-OVMPACS算法对虚拟机放置目标函数的优化效果和当云数据中心有大规模虚拟机请求时的可扩展性，本文共设计了两组实验方案，分别为虚拟机放置优化目标对比实验和虚拟机放置可扩展性实验。虚拟机放置优化目标对比实验在请求的虚拟机和负载主机情况一致的情况下，与降序首次适应算法比较两个优化目标：能耗和资源利用率。bi-OVMPACS算法的可扩展性实验分别在两种不同类型虚拟机不同请求数量的情况下，对比蚂蚁搜索到一条可行路径的时间。

虚拟机放置优化目标实验，与降序首次适应算法进行实验对比。降序首次适应算法放置虚拟机的主要思想是，先将虚拟机从大到小排序，然后按照排列顺序将虚拟机映射到主机。按主机启用顺序，如果能找到放置当前虚拟机而且是最早启动的主机，则将当前虚拟机放置到该主机；否则，启动另一台主机放置当前虚拟机。FFD算法的主要的运算时间是用来对虚拟机进行排序，故其时间复杂度是O(nlogn)。

虚拟机请求实例采用3.2小节介绍的伪随机方式产生，总共产生200个虚拟机请求。在参数P，stdCPU，stdMem一定的条件下，FFD算法与bi-OVMPACS算法虚拟机放置优化目标对比实验，见表2。

表2 FFD算法与bi-OVMPACS算法优化目标对比实验

上述实验结果表明：在同等条件下，与FFD放置算法相比，bi-OVMPACS算法对虚拟机放置目标有明显改善。当虚拟机请求的CPU和内存平均值一定时，目标函数值随CPU和内存的相关数增大而减小，反映出不同虚拟机类型对目标函数的影响；当虚拟机请求的CPU和内存平均值不同时，目标函数随虚拟机请求值的增大而增大。因此，bi-OVMPACS算法能够在一定程度上实现云数据中心能耗和资源利用率同时优化的虚拟机放置问题。

bi-OVMPACS算法的可扩展性实验，分别对比了虚拟机请求类型为25%和45%，数目从200增加到2000，参数stdP值为0.5的情况下，蚂蚁探索到一条可行路径的时间，实验结果如图1所示。

图1 bi-OVMPACS算法的可扩展性实验

上述实验结果表明：虚拟机请求平均值为25%的探索时间少于平均值为45%，因为承载平均值为45%的虚拟机需要启动更多的主机。随着虚拟机请求数量的增加，蚂蚁探索到一条路径的时间可以在1 min内完成，在人们可以接受的范围内。因此，bi-OVMPACS算法适合大规模数据中心的虚拟机放置。

5 结束语

本文首先对多目标优化问题进行了详细描述，并且介绍了现有的几种虚拟机放置算法，分析了它们在虚拟机放置中存在的问题，并在此基础上综合考虑需要优化的CPU和内存两种资源，提出了基于蚁群智能的优化能耗和资源利用率的双目标虚拟机放置模型。然后简要介绍了基础蚁群系统和改进的蚁群系统，详细阐述了该算法的实现过程。最后，通过对比实验，验证了本文提出的算法在对虚拟机放置优化目标的有效性和该算法的可扩展性上具有一定的优越性。