基于多目标优化的虚拟机放置方法

发布时间：2021-10-09 13:45

　　在虚拟机放置问题中,传统启发式方法不能完全适用于复杂的云计算环境,采用智能算法的研究又缺乏对时间开销的考虑。针对上述问题,提出一种基于Memetic算法的虚拟机放置（Memetic algorithm-based virtual machine placement MAVMP）方法。MAVMP方法针对云数据中心运营情况建立了最小化能耗、最小化运行时服务等级协议违例率（service level agreement violation time per active host, SLATAH）以及最大化资源利用率的多目标优化模型,将虚拟机按照资源请求情况进行分类,并利用该分类方法改进了Memetic算法,利用改进后的Memetic算法求解多目标优化模型,得到虚拟机放置方案。仿真实验结果表明,仿真数据中心利用MAVMP方法进行虚拟机放置后,其在能耗、资源利用率以及服务质量的评价指标上都有着良好表现。并且,MAVMP方法与已有的基于智能算法的虚拟机放置方法相比计算时间也大幅下降。 

【文章来源】：重庆邮电大学学报(自然科学版). 2020,32(03)北大核心CSCD

【文章页数】：12 页

【部分图文】：

CPU利用率与功率关系

在Memetic算法中,每个个体代表问题的一个解,由不同个体组成的解的集合称为种群。个体利用不同基因组成表示不同的解结构。云计算资源调度中生成一次合理的放置方案需要确定虚拟机与物理主机的映射关系。合理的映射关系必须满足(12)式的约束,即一台虚拟机只能放置在一台物理主机上,同一台物理主机可以放置不同的虚拟机。根据以上条件,可以对个体进行如图2的编码。其中,个体中基因数量等于待放置的虚拟机数量。个体上第i个基因存储了虚拟机i所放置的物理主机编号。例如,图2中VM(N-1)放置在编号为10的物理主机上。采用这种编码方式产生的个体显然可以满足(12)式的约束。种群初始化时需要确定待放置的物理主机集合。为了缩小解空间,提高算法效率,首先将资源利用率不超过70%的物理主机加入可用物理主机集合。为了避免出现物理主机不能满足虚拟机资源请求的情况,再将一部分空闲主机加入可用物理主机集合。空闲物理主机的数量应保证可以满足所有待放置虚拟机的资源请求。然后,对集合中的物理主机进行编号。对于个体上的每个基因,利用随机的方法为其选择物理主机,判断随机得到的物理主机是否满足(13)式的约束。如果满足约束则将该物理主机编号填入基因位,否则重新选择物理主机。智能算法中种群规模一般与问题规模相当。但由于Memetic框架的特性,使得Memetic算法相比其他智能集群算法种群规模小。本文将种群规模设置为20。

本文将物理主机分别以3种资源的剩余可用量降序排列。物理主机的3种序列使得局部搜索时有3种不同的搜索策略。不同的搜索策略对局部搜索性能有着重要的影响。图3展示了一台以CPU为主要资源的虚拟机按照不同的搜索策略产生的搜索路径。图3标示了物理主机各个资源的剩余量和虚拟机各个资源的实际请求量以及当前利用率,图中上方物理主机按照CPU资源降序排列,下方物理主机按照RAM资源降序排列。由图3可知,该虚拟机按照CPU资源序列进行搜索只需进行一次尝试,而利用RAM资源进行搜索时则需进行4次尝试。根据分析,如果将虚拟机分类融入到局部搜索过程,那么局部搜索的效率能够得到改善。本文利用虚拟机分类思想改进了Memetic算法的局部搜索策略,多资源约束的Memetic局部搜索策略如算法1。该策略针对个体中的每个基因,首先判断该基因位所代表的虚拟机的主要资源,然后将待放置物理主机按照主要资源的可用量降序排列,最后将序列中第1个满足虚拟机资源请求的物理主机编号存入该基因位。

【参考文献】：
期刊论文
[1]多虚拟机动态迁移情景下的服务功能链调整方法[J]. 古英汉,伊鹏.  小型微型计算机系统. 2017(05)
[2]异构云环境多目标Memetic优化任务调度方法[J]. 李智勇,陈少淼,杨波,李仁发.  计算机学报. 2016(02)
[3]基于DEA的能耗感知虚拟机资源分配算法[J]. 陈小娇,陈世平.  小型微型计算机系统. 2015(01)



本文编号：3426502