基于改进粒子群算法的虚拟机放置策略研究

唐忠原，何利文，黄 俊，袁 野

(南京邮电大学 计算机学院，江苏 南京 210046)

0 引 言

云计算[1]是由分布式计算、网格计算及并行计算等技术发展而来的，将大量计算、存储和软件等资源融合在一起，构成超大规模且高性能、可扩充性的虚拟IT资源池，再通过服务器接口向广大云用户提供按需计费的独特商业服务模式[2]。随着云服务的发展，数据中心变得异常庞大，巨大的数据中心需要消耗大量的能源；而根据IBM公司的统计表明，能源成本占数据中心总运营成本的50%，而中国的数据中心能耗已达三峡的年发电量[3]。耗能问题成为目前数据中心最具挑战性的问题；同时，数据中心的通信流量也不断增大，若不进行优化，会造成网络流量聚集，形成链路热点，甚至导致通信阻塞，严重影响数据中心的运行效率与云计算服务的服务质量[4]。

降低数据中心的能耗与通信流量的常用策略有虚拟机初始放置[4-6]和虚拟机迁移[7-8]。虚拟机迁移会花费一定的时间、消耗大量的资源，并且会影响服务器上其他虚拟机的运行，导致系统性能下降。另外，实现迁移还需要额外的网络存储系统和高速通信网络的支持。若云计算系统中出现大量的虚拟机迁移，将导致无法满足服务等级协议(service level agreement，SLA)。因此，降低数据中心的能耗与通信量的最简单最直接的方式就是优化虚拟机的初始放置。

对于虚拟机放置问题，文献[9]采用能源感知的粒子群优化算法优化数据中心的能耗问题，该文对粒子群优化算法进行了改进，使用新的编码策略使其适合解决离散优化问题。文献[10]提出了多资源的能耗模型，在该模型下提出了基于粒子群算法的高效能虚拟机放置策略，可以有效提高系统资源的利用率。文献[11]根据分析不同虚拟机的负载特征，提出并实现了一个基于负载特征的虚拟机放置策略，利用各种虚拟机负载的互补性，进行多次配对，得到由多台虚拟机组成的配对组，对配对组统一分配服务器；同样文献[12]以利用虚拟机负载的历史数据作为分析的依据，提出了一种基于虚拟机负载高峰特征的虚拟机放置策略,通过更好地复用物理主机资源来实现资源共享。文献[13]使用能源感知、流量感知的策略重点对三种常见的数据中心网络拓扑(Fat-tree，VL2，VL2N-Tree)的通信链路的能耗进行优化，该文首先通过流量感知对虚拟机进行分组，使得通信量较大的虚拟机成为一组，再通过距离感知策略将各组虚拟机群放置在合适的服务器上。

在上述研究的基础上，文中提出了一种改进粒子群算法的虚拟机放置策略，首先对原始粒子群算法的参数进行相应的重定义或修改使其适合解决离散优化问题，再通过突变策略增强粒子群的多样性以避免微粒因早熟而陷于局部最优的问题。

1 模型设计

1.1 场景描述

目前数据中心的设计与操作很少考虑到系统的能耗与网络拥塞，容易造成数据中心的能耗与全网通信量过大、网络拥塞严重等问题。为了应对通信链路故障与网络峰值，通常是使用大量冗余链路并扩大链路的带宽，但该方式容易导致大量的资源浪费。文中重点考虑Fat-tree树形结构网络拓扑，具有较强的网络容错性、较大的吞吐量、便于扩展等特点，广泛应用于数据中心的构建；其交换机常用普通商用设备而非高性能交换设备，可以大幅度降低网络通信设备开销；该结构主要分为三个层次，即Core层、Aggregation层与Edge层，同一层次的交换机与相邻层次的交换机进行链接，便于实现网络通信的路径多样化。其Aggregation层与Edge层的交换机构成一个Pod，假设Fat-tree拓扑包含的Pod数目为k,每个Pod连接服务器的数量为(k/2)2个，每个Pod内Edge层交换机数目与Aggregation层交换机数目都为k/2个，Core交换机数目为(k/2)2个，若网络中每个交换机的端口数目为k,则该数据中心可以容纳服务器的总数为k3/4台，足够满足普通数据中心的需求。

1.2 能耗模型

数据中心的网络拓扑可以看作一个无向图G(V,E'),其中V是数据中心节点集合，包括交换机集合Y与服务器集合Z，即V=Y∪Z，E'是连接节点之间的通信链路集合。计算能耗时，要分别考虑服务器与通信设备的能耗。

服务器的能耗依赖于服务器的CPU、内存、磁盘与网络的利用率，其中CPU是服务器中最重要的耗能部件。服务器的能耗与服务器的CPU的利用率是成比例的线性关系，即CPU的利用率越高，服务器的能耗也就越大。同时文中还得出，一个空闲的服务器消耗的功率大约是服务器最大功率的70%，由此得出服务器功率消耗的公式：

(1)

在通信链路的能耗方面，很多研究中网络设备(交换机、路由器等)的能耗往往被忽略，其实网络设备的能耗占整个数据中心能耗的10%～20%[13-14]，网络设备在闲置时的能耗为最大功率的85%。文中仅考虑数据中心中网络设备的能耗与网络设备的数量正相关。

(2)

(3)

所以，数据中心的能耗模型E为：

(4)

其中，Ps为交换机的额定功率。

1.3 全网流量模型

由云计算系统中的“监控模块”可以得到当前数据中心中虚拟机间的通信量，接着由“预测模块”预测将来某段时间的虚拟机间通信量，由此形成数据中心的通信方阵C，如下所示：

(5)

其中，cii=0，n表示虚拟机的总数量，cij表示单位时间内虚拟机i向虚拟机j发送的数据量。

在数据中心，服务期间的物理距离对网络传输时延的影响是很大的，在同一台服务器上的虚拟机间的通信时延可以忽略，因此实际测试中将不在同一台服务器上的虚拟机间的距离由通信过程中经过的通信设备(如交换机、路由器)的数量与拥堵状况决定，同一台服务器上虚拟机间的距离设置为0(如VM1与VM13)，不同服务器上的虚拟机间的距离设置为路过交换机的个数，由此构成了虚拟机间的距离方阵Distance，如下所示：

(6)

该方阵为对称方阵，dii=0，dij表示虚拟机i与虚拟机j之间的距离。

数据中心的通信总流量就是在单位时间内，经过通信链路的所有通信流量之和，其公式如下所示：

(7)

1.4 约束模型

文中将用所需要的CPU、内存与带宽来描述一个虚拟机。文中没有考虑虚拟机对磁盘资源的需求量，因为网络连接存储(NAS)技术已经广泛运用于服务器集群，即虚拟机可以方便地使用其他服务器的磁盘资源。设定服务器中各项资源利用率的阈值为70%，设定阈值的好处在于：首先，一定的资源剩余可以满足部分应用在特定时刻对资源需求量突然增大的情况；其次，通常虚拟机在运行过程中对资源的需求量是逐步上升的，一定的资源剩余给其提供了上升空间，减少了虚拟机的迁移。为了使优化更好地进行，根据CPU、内存与带宽，给出以下约束函数：

(8)

1.5 目标函数

文中的优化策略就是为了求得目标函数的最小值，目标函数如下所示：

minFitness=min(E,Con)=r*E+(1-r)*Con,r∈[0,1]

(9)

其中，r为调节因子，以适应优化不同的数据中心。若重点考虑降低数据中心的能耗，则可以适当增大r的值；若重点考虑降低全网通信流量，提高通信效率，则可以适当降低r的值。

为了平衡能耗与全网通信流量对适应度值的影响，使用传统的容限值法来计算r值，计算方式如下：

(10)

其中，E0为在单目标情况下能耗的最优值；Con0为在单目标情况下全网通信流量的最优值。

2 基于改进粒子群算法(MPSO)的虚拟机放置策略

微粒群优化算法(particle swarm optimization，PSO)是一种基于群智能的全局优化进化算法，其概念简单，并有个体数目少、计算简单、鲁棒性好等优点，在求解复杂问题时具有较强的优越性。然而传统的PSO算法仍然有很多缺点，并不能很好地解决该虚拟机放置问题，原因如下：首先，传统的PSO算法是用来解决连续性优化问题，并不能解决离散优化问题，所以必须把粒子群算法的各项参数进行重新定义；其次,粒子群优化算法的一个重要问题就是容易陷入局部最优解，从而失去了全局最优解。为了解决上述问题，必须对传统的PSO算法进行改进。

PSO算法根据微粒对环境的适应度值的不同，种群中的微粒不断向解空间进行搜索并向最优解靠拢，最终停留在最优解处。对于全局优化问题P的多个可行解组成一个集合，这个集合就是一个种群(swarm)，种群中的每个元素(将所有虚拟机放置到服务器上的一种可行的解决方案)成为一个微粒(particle)，微粒的总数量就是种群的大小。种群中的每个微粒都有一个位置矢量和速度矢量，为了可以将粒子群算法用于解决该优化问题，文中用以下方法对粒子群算法的各个参数进行修改：

位置定义：用向量Xi=[xi1,xi2,…,xin]表示第i个粒子的位置矢量，xi1表示第i个微粒中虚拟机1放置的位置，该矢量表示将所有虚拟机放置到服务器上的一个可行解。

速度定义：用向量Vi=[vi1,vi2,…,vin]表示第i个微粒的速度矢量，该矢量决定相应节点位置的调整。

同理，种群中的微粒i在搜索过程中经历的最优位置叫做个体最优解，记为Pbi=[pi1,pi2,…,pin]，种群中所有微粒经过的全局最优位置叫做全局最优解，记为G=[g1,g2,…,gn]。种群就根据式11和式12不断更新自己的位置和速度：

(11)

(12)

其中，i∈[1,m]，m为种群大小，n为虚拟机总数；k为迭代次数；c1,c2为学习因子；r1,r2为0～1间的随机数；w为惯性权重。

学习因子c1,c2是增强全局搜索能力避免局部最优解的重要指标。在搜索前期，要求全局搜索能力很强，可以防止局部最优；在搜索后期，要求局部搜索能力加强，加快收敛速度。c1,c2的计算方法如下：

(13)

(14)

其中，i为当前迭代次数；N为最大迭代次数；c1max,c1min分别为c1的最大值与最小值；c2max,c2min分别为c2的最大值与最小值。

为了使粒子群优化算法更好地解决虚拟机放置问题，文中在原始粒子群优化算法的基础上添加了突变策略：粒子群在根据式11与式12进行迭代时，如果微粒的适应度小于粒子群的平均适应度，则以一定的概率M进行突变，其表达式为：

(15)

其中，Mmax为最大突变概率；i为迭代次数；N为最大迭代次数；b为突变步长随世代下降的曲线形状因子；p为突变控制因子，控制转换突变策略的时机，即在迭代前期突变概率较大，有利于扩大粒子群的解空间，避免局部收敛，在迭代后期突变概率变小，使粒子快速收敛。

算法流程描述如下：

Step1:初始化各参数，包括学习因子c1与c2的范围、目标函数的调节因子r、最大迭代次数N、突变控制因子p、突变曲线形状因子b、最大突变概率值Mmax。

Step2：计算种群中各个粒子的目标函数值Fitness、个体最优解Pb(实验首次迭代时等于初始种群)以及全局最优解G。

Step3:按照式11和式12在约束的条件下进行迭代，在迭代过程中，若出现微粒群X中的某个某台虚拟机所在的服务器编号xij≥k+1时，即结果越界，则将该虚拟机改为原来的服务器；若发现不满足约束函数，则将合适的虚拟机放置到一台可行的服务器，并不断更新各粒子的Fitness、Pb和G。

Step4:计算种群的平均适应度值avg_fitness，如果Fitnessi

Step5：如果迭代次数等于N，转至Step6，否则转Step3。

Step6：输出最优的目标函数值与最优的虚拟机放置方案，算法结束。

3 实验及结果分析

采用澳大利亚墨尔本大学的网络实验室和Gridbus项目提出的云仿真平台CloudSim作为实验仿真工具。仿真时使用交换机的功率为50 W，服务器分为普通服务器(CPU：8核，memory：16 GB，bandwidth：1 000 Mbps，peak energy consumption：330 W)与高性能服务器(CPU：12核，memory：24 GB，bandwidth：2 000 Mbps，peak energy consumption：500 W),虚拟机的型号分为CPU密集型(CPU：4核，memory：4 GB，bandwidth：200 Mbps)、内存密集型(CPU：2核，memory：8 GB，bandwidth：200 Mbps)、带宽密集型(CPU：2核，memory：2 GB，bandwidth：500 Mbps)与普通型(CPU：2核，memory：4 GB，bandwidth：200 Mbps)。

为了达到可信的效果，必须说明以下事实，数据中心的虚拟机间的流量分布是很不均匀的，虚拟机间产生的流量各不相同，但是大部分虚拟机在一段时间内产生的流量是相对稳定的，大约有80%的虚拟机间的通信流量少于15 kb/s，然而仅有4%的虚拟机间的通信流量高达150 kb/s[13-15]，因此在生成通信方阵时80%的虚拟机间的通信流量为0～20 kb/s，16%的虚拟机间的通信流量为20～150 kb/s，4%的虚拟机间的通信流量为150～500 kb/s。

为了验证MPSO算法在虚拟机放置问题上的可行性，使用PSO、随机算法(random algorithm)与首次适应算法(first fit algorithm)进行对比。

在CloudSim平台上按照表1中的实验数据进行模拟。实验时，序号1、2的测试数据集的初始种群中粒子个数为50个，最大迭代次数为300代；3、4的测试数据集的初始种群为100个，最大迭代次数为500代。其他参数如下：学习因子最大值与最小值分别为3与1；惯性权重w为0.5；初始速度vij设为1，最大突变概率Mmax为0.2，突变步长随世代下降的曲线形状因子b取2，突变控制因子p一般取最大迭代次数的一半。为了平衡功率与总流量对适应度函数的影响，调节因子r经计算取0.02。PSO算法的参数与改进粒子群算法所用的参数相同。为了减少实验误差，每组实验做三次，取其平均值。

图1是选取的第一组测试数据所得的测试结果，由PSO算法与MPSO算法通过多次迭代求得的适应度值随迭代次数变化的曲线。

表1 四种仿真数据

图1 适应度值与迭代次数对比

由图1可得，未经优化的PSO算法前期的收敛比较快，但是迭代到90次时，下降速度逐渐减弱，最后趋于水平，说明未经优化的PSO算法的全局搜索能力有限，容易达到局部收敛。MPSO算法在前期有较强的突变概率，全局搜索能力比较强，故曲线下降速度较慢；但是迭代后突变概率减弱，该算法以较快的速度收敛于最优解，在240代时已基本寻找到良好的部署方案。该实验说明，带有突变的粒子群算法达到了理想的结果。

图2～5从多个方面展示了四种优化算法在四组实验数据中的优化效果图。可以看出，在流量优化方面，使用MPSO算法的四组实验数据中的全网流量与主干网流量都优于其他三种算法；在耗能方面，使用MPSO算法的放置策略中使用的服务器与网络设备的数量都不高于其他三种算法，因此数据中心总功率的消耗也低于其他三种放置算法。

图2 多目标优化的全网通信流量对比

图3 多目标优化的主干网流量对比

图4 多目标优化的服务器使用台数对比

图5 多目标优化的数据中心总功率对比

4 结束语

文中提出了一种改进粒子群算法的虚拟机放置策略，以缩小全网的通信量，降低数据中心的能耗。首先对粒子群算法的各个参数进行修改，使其适合解决离散优化问题，接着给出了三维空间(CPU、内存与带宽)约束模型来约束服务器的资源使用情况，最后为粒子群算法添加突变策略并给出了一个突变函数，提高了粒子群的多样性。实验结果表明，该虚拟机放置策略很好地解决了云环境中的虚拟机放置问题，在云环境这种大规模分布式并行计算中有很大的研究价值以及可观的应用前景。