基于多目标优化的虚拟机放置策略研究.docVIP

基于多目标优化的虚拟机放置策略研究 　　摘要：虚拟机放置是云数据中心资源管理的一个重要问题。提出了基于多目标优化的蚁群算法，通过建立服务器CPU进程损耗和内存资源消耗模型，定义一个多目标优化的虚拟机放置问题。通过改进蚁群算法获得一组非支配解来有效处理大规模数据中心潜在的较大解空间问题。在不同数量虚拟机情况下进行实验，证明该算法有着最低的资源消耗。 　　关键词：云计算；虚拟机放置；蚁群算法 　　DOIDOI：10.11907/rjdk.161857 　　中图分类号：TP301 　　文献标识码：A文章编号2016）010000703 　　0引言 　　解决云数据中心能源开销庞大问题的一种有效方法是优化虚拟机放置。本文提出基于蚁群算法多目标优化的虚拟机放置策略，将虚拟机放置问题转化为一个多目标优化问题，以优化存储器资源和CPU处理器资源。 　　1蚁群算法与多目标优化问题 　　蚁群优化算法是由Dorigo等[1]提出的一种基于蚂蚁觅食行为的模拟进化算法。多目标优化问题[2]也称为多标准优化问题。一般多目标优化问题由n个决策变量参数、k个目标函数和m个约束条件组成，多目标优化问题 　　的Pareto最优解是一个集合。 　　云环境下有许多服务节点池，虚拟机放置方案将影响CPU进程和内存资源损耗，基于蚁群算法的虚拟机放置算法在处理CPU和内存资源时作为一个单独的目标函数。本文中，资源损耗处理在一个多目标条件下进行，一个目标函数处理进程资源，另一个目标函数处理内存资源。为了完全利用现有资源，采用公式（1）计算潜在的CPU进程资源，公式（2）计算潜在的内存资源。因此，虚拟机放置问题即最优化的CPU进程损耗和内存资源损耗。 　　Wpj=Tpj-UpjUpj（1） 　　Wmj=Tmj-UmjUmj（2） 　　其中，Wpj和Wmj分别表示第j个服务器CPU进程资源消耗和第j个服务器的内存资源消耗。Tpj代表第j个服务器的CPU进程利用阈值， Tmj代表第j个服务器的内存利用值，Upj表示第j个服务器总的CPU进程，Umj表示第j个服务器总的内存资源。 该算法的目标是Wpj和Wmj尽可能减少。 　　2基于改进蚁群算法虚拟机放置策略 　　把n个虚拟机放置到m个物理机上，总共有mn个可能的虚拟机放置方案。例如， 把15个虚拟机放置到10个物理机上可能得出1015个解决方案，即使每秒可以评估一百万解决方案，检查1015个可能的解决方案也要超过31年[3]。因此，完整的枚举不可能找到最好的解决方案。应用ACO算法可有效寻找好的解决方案。定义VMPACO算法的伪代码如下： 　　Input： Set of VMs and set of hosts with thresholds of resources utilizationOutput： The Pareto set of best solutions for VMs placement （1） Initialize：Set t=0. Set Pareto set empty. Set Initial value for τij（t）=τ0 for each path between VM and host. （2）For k=1 to NOA （number of ants） do Sort the host list in random order. Do ants_trip while any VM isn’t placed. Get the new host from the host list. For each remaining VM that can be placed into the current host. Compute the probabilistic transition rule to select VM to be placed according to probabilistic transition rule. End For End Do Compute the value of the two objectives for the current solution. If the current solution is not dominated by any other solutions in Pareto set Then Add this solution to Pareto set Eliminate the solutions dominated by the added one from Pareto set. End If End For （3）Apply local pheromone up