面向云数据中心的虚拟机部署时延优化算法研究

摘要

This paper investigated the problem of minimizing the latency of VM placement on data centers with the considerations of physical machine capacity and multi-type resource.First,it strictly formulated and proved the problem to be an NPC problem.Then,based on genetic algorithm,it proposed an efficient VM placement algorithm by integrating with greedy scheme.The main distinct of the proposed algorithm was as follows:to obtain the optimal results,it combined with the greedy algorithm for individuals' initialization,selection,crossover and mutation.Also the crossover was taken place between the individual with odd and even number to avoid the repeat crossover and trap-in local optimum.Besides,it designed a method to check the collision in the process of crossover (VMs were overloading on certain server).Finally,it compared the proposed algorithm with the latest algorithm VMPDN and particle swarm optimization(PSO).The results show that the proposed algorithm outperforms than that of the other algorithm in minimizing the latency.Moreover,with different type of resource,various number of iteration and size of population,the proposed algorithm still demonstrates better performance than that of the other algorithms.%考虑了服务器内资源容量及虚拟机多类型资源需求时虚拟机部署最优化时延问题.首先将最优化虚拟机部署时延问题进行了形式化建模,并证明了该问题为一个NPC问题;然后通过遗传结合贪心策略提出了一种高效的虚拟机部署算法优化时延.该算法的主要特点在于:结合了贪心策略指导个体在初始化、选择、交叉、变异时形成最优解,并且在交叉过程中采用奇、偶数位个体交叉的方式形成新个体,既避免了个体间的重复交叉,又通过多样化的新个体形成使得算法的解不会陷入局部最优.另外,由于遗传算法在交叉过程中会存在交叉冲突问题(服务器容量超载),还设计了一种交叉冲突检查方法,避免了交叉冲突后非法个体的生成.最后,通过实验比对,将提出的算法分别与最新研究成果VMPDN、粒子群优化算法等进行比较,结果表明提出的算法有效地缩短了虚拟机的部署时延.同时通过不同资源类型数量、迭代次数及种群大小的情况下,分析和考察了算法性能,结果表明提出的算法性能仍优于其他的算法.