基于粒子群优化算法的虚拟机部署策略

doi:10.11772/j.issn.1001-9081.2016.01.0117

计算机应用 ›› 2016, Vol. 36 ›› Issue (1): 117-121.DOI: 10.11772/j.issn.1001-9081.2016.01.0117

基于粒子群优化算法的虚拟机部署策略

杨靖, 张宏军, 赵水宁, 占栋辉

解放军理工大学仿真与数据中心, 南京 210007

收稿日期:2015-07-27 修回日期:2015-09-15 出版日期:2016-01-10 发布日期:2016-01-09
通讯作者: 杨靖(1991-),男,江西鹰潭人,硕士研究生,主要研究方向:服务计算、计算机网络
作者简介:张宏军(1963-),男,江苏泰州人,教授,博士,主要研究方向:军用数据与知识工程;赵水宁(1971-),男,江西南昌人,副教授,博士,主要研究方向:服务计算、计算机网络;占栋辉(1988-),男,江西上饶人,博士研究生,主要研究方向:智能算法、数据挖掘。

Virtual machine deployment strategy based on particle swarm optimization algorithm

YANG Jing, ZHANG Hongjun, ZHAO Shuining, ZHAN Donghui

Center of Simulation and Data, PLA University of Science and Technology, Nanjing Jiangsu 210007, China

Received:2015-07-27 Revised:2015-09-15 Online:2016-01-10 Published:2016-01-09

摘要/Abstract

摘要： 针对云计算基础设施即服务(IaaS)中的虚拟机部署问题,提出一种基于粒子群优化(PSO)算法的部署策略。由于PSO算法在处理虚拟机部署这类大规模复杂问题时,具有收敛速度慢且容易陷入局部最优的缺点,首先,引入多种群进化模式提高算法收敛速度,并在此基础上加入高斯学习策略避免局部最优,提出了一种多种群高斯学习粒子群优化(MGL-PSO)算法;然后,根据部署模型,使用轮询(RR)算法对MGL-PSO进行初始化,进而提出了一种以负载均衡为目标的虚拟机部署策略。通过在CloudSim中进行仿真实验,验证了在解决虚拟机部署问题时,MGL-PSO相比PSO算法,具有更快的收敛速度,并且负载不均衡度降低了13.1%。在两种实验场景下,所提算法相比随机负载均衡(OLB)算法,其负载不均衡度分别平均降低了25%和15%;相比贪婪算法(GA),使负载不均衡度分别平均降低了19%和7%。

关键词: 虚拟机部署, 粒子群优化, 负载均衡, 高斯学习, 多种群进化

Abstract: To solve the virtual machine deployment problem in Infrastructure as a Service (IaaS) of cloud computing, a virtual machine deployment strategy based on Particle Swarm Optimization (PSO) algorithm was proposed. Since the PSO algorithm has weaknesses of having a slow convergence speed and falling into local optimum easily when dealing with large-scale and complex problems like virtual machine deployment, firstly, a Multiple-population Gaussian Learning Particle Swarm Optimization (MGL-PSO) algorithm was proposed, with using the model of multiple population evolution to accelerate the algorithm convergence, as well as adding Gaussian learning strategy to avoid local optimum. Then according to the deployment model, with using Round Robin (RR) algorithm to initialize the MGL-PSO, a virtual machine deployment strategy aiming to load balancing was proposed. Through the simulation experiment in CloudSim, it validates that MGL-PSO has a higher convergence speed and load imbalance degree is reduced by 13% compared with PSO algorithm. In the two experimental situations, compared with the Opportunistic Load Balancing (OLB) algorithm, the load imbalance degrees of the proposed algorithm decrease by 25% and 15% respectively, and compared with the Greedy Algorithm (GA) the load imbalance degrees decrease by 19% and 7% respectively.

Key words: virtual machine deployment, Particle Swarm Optimization (PSO), load balancing, Gaussian learning, multiple population evolution

中图分类号:

TP311
TP18

杨靖, 张宏军, 赵水宁, 占栋辉. 基于粒子群优化算法的虚拟机部署策略[J]. 计算机应用, 2016, 36(1): 117-121.

YANG Jing, ZHANG Hongjun, ZHAO Shuining, ZHAN Donghui. Virtual machine deployment strategy based on particle swarm optimization algorithm[J]. Journal of Computer Applications, 2016, 36(1): 117-121.

参考文献

[1] OSTERMANN S, IOSUP A, YIGITBASI N, et al. A performance analysis of EC2 cloud computing services for scientific computing [C]// CloudComp 2009: Proceedings of the First International Conference on Cloud Computing. Berlin: Springer, 2010: 115-131.
[2] WICKREMASINGHE B, CALHEIROS R N, BUYYA R. CloudAnalyst: a CloudSim-based visual modeller for analysing cloud computing environments and applications [C]// Proceedings of the 2010 24th IEEE International Conference on Advanced Information Networking and Applications. Piscataway, NJ: IEEE, 2010: 446-452.
[3] KLEINBERG J, TARDOS É. Algorithm design [M]. Upper Saddle River, NJ: Pearson Education, 2006: 352-367.
[4] NAKADA H, HIROFUCHI T, OGAWA H, et al. Toward virtual machine packing optimization based on genetic algorithm [C]// IWANN 2009: Proceedings of the 10th International Work-Conference on Artificial Neural Networks: Part II: Distributed Computing, Artificial Intelligence, Bioinformatics, Soft Computing, and Ambient Assisted Living. Berlin: Springer, 2009: 651-654.
[5] CARON E, DESPREZ F, LOUREIRO D, et al. Cloud computing resource management through a grid middleware: a case study with DIET and Eucalyptus [C]// Proceedings of the 2009 IEEE International Conference on Cloud Computing. Piscataway, NJ: IEEE, 2009: 151-154.
[6] MILOJICIC D, LLORENTE I M, MONTERO R S. OpenNebula: a cloud management tool [J]. IEEE Internet computing, 2011, 15(2): 11-14.
[7] GAO Y, GUAN H, QI Z, et al. A multi-objective ant colony system algorithm for virtual machine placement in cloud computing [J]. Journal of computer and system sciences, 2013, 79(8): 1230-1242.
[8] 袁爱平,万灿军.云环境下基于改进遗传算法的虚拟机调度策略 [J].计算机应用,2014,34(2):357-359.(YUAN A P, WAN C J. Virtual machine deployment strategy based on improved genetic algorithm in cloud computing environment [J]. Journal of computer applications, 2014, 34(2): 357-359.)
[9] KENNEDY J, EBERHART R. Particle swarm optimization [C]// Proceedings of the 1995 IEEE International Conference on Neural Networks. Piscataway, NJ: IEEE, 1995: 1942- 1948.
[10] JEYARANI R, NAGAVENI N, RAM R V. Design and implementation of Adaptive Power-Aware Virtual Machine Provisioner (APA-VMP) using swarm intelligence [J]. Future generation computer systems, 2012, 28(5): 811-821.
[11] XU B, PENG Z, XIAO F, et al. Dynamic deployment of virtual machines in cloud computing using multi-objective optimization [J]. Soft computing, 2014, 19(8): 2265-2273.
[12] WOOD T, SHENOY P J, VENKATARAMANI A, et al. Black-box and gray-box strategies for virtual machine migration [C]// Proceedings of the 4th USENIX Symposium on Networked Systems Design and Implementation. Berkeley, CA: USENIX Association, 2007: 17-17.
[13] TIAN W, XU M, CHEN Y, et al. Prepartition: a new paradigm for the load balance of virtual machine reservations in data centers [C]// Proceedings of the 2014 IEEE International Conference on Communications. Piscataway, NJ: IEEE, 2014: 4017-4022.
[14] ZHAN Z H, ZHANG J, LI Y, et al. Adaptive particle swarm optimization [J]. IEEE transactions on systems, man, and cybernetics, part B: cybernetics, 2009, 39(6): 1362-1381.
[15] CALHEIROS R N, RANJAN R, BELOGLAZOV A, et al. CloudSim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms [J]. Software: practice and experience, 2011, 41(1): 23-50.
[16] Amazon EC2[EB/OL]. [2015-06-20]. http://aws.amazon.com/ec2/.

基于粒子群优化算法的虚拟机部署策略

Virtual machine deployment strategy based on particle swarm optimization algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	张闻强, 邢征, 杨卫东. 基于多区域采样策略的混合粒子群优化求解多目标柔性作业车间调度问题[J]. 计算机应用, 2021, 41(8): 2249-2257.
[2]	张盟, 郭健全. 需求和回收不确定的闭环供应链渠道结构选择[J]. 计算机应用, 2021, 41(7): 2100-2107.
[3]	杨翎, 姜春茂. 基于三支决策的虚拟机节能迁移策略[J]. 计算机应用, 2021, 41(4): 990-998.
[4]	许红亮, 杨桂芹, 蒋占军. 基于软件定义网络的数据中心自适应多路径负载均衡算法[J]. 计算机应用, 2021, 41(4): 1160-1164.
[5]	李萍, 汪芬, 陈祺东, 孙俊. 求解多目标社区发现问题的离散化随机漂移粒子群优化算法[J]. 计算机应用, 2021, 41(3): 803-811.
[6]	唐延强, 李成海, 宋亚飞. 基于改进粒子群优化和极限学习机的网络安全态势预测[J]. 计算机应用, 2021, 41(3): 768-773.
[7]	王泽昆, 贺毅朝, 李焕哲, 张发展. 基于新颖S型转换函数的二进制粒子群优化算法求解具有单连续变量的背包问题[J]. 计算机应用, 2021, 41(2): 461-469.
[8]	樊小毛, 熊红林, 赵淦森. 带约束的清洁排班问题模型及其求解[J]. 计算机应用, 2021, 41(2): 577-582.
[9]	郭秀婷, 朱昶胜, 张生财, 赵奎鹏. 分形插值在风速时间序列中的应用[J]. 计算机应用, 2020, 40(9): 2628-2633.
[10]	罗斌, 于波. 移动边缘计算中基于粒子群优化的计算卸载策略[J]. 计算机应用, 2020, 40(8): 2293-2298.
[11]	曾明华, 全轲. 双层规划的改进混合布谷鸟搜索量子行为粒子群优化算法[J]. 计算机应用, 2020, 40(7): 1908-1912.
[12]	周文峰, 梁晓磊, 唐可心, 李章洪, 符修文. 具有拓扑时变和搜索扰动的混合粒子群优化算法[J]. 计算机应用, 2020, 40(7): 1913-1918.
[13]	施晓倩, 陈祺东, 孙俊, 冒钟杰. 变分布的量子行为粒子群优化算法求解工程约束优化问题[J]. 计算机应用, 2020, 40(5): 1382-1388.
[14]	霍晴晴, 郭健全. 基于改进遗传算法的生鲜多目标闭环物流网络模型[J]. 计算机应用, 2020, 40(5): 1494-1500.
[15]	许洋, 秦小林, 刘佳, 张力戈. 多无人机自适应编队协同航迹规划[J]. 计算机应用, 2020, 40(5): 1515-1521.