云计算环境下基于蜜蜂觅食行为的任务负载均衡算法

doi:10.11772/j.issn.1001-9081.2015.04.0938

计算机应用 ›› 2015, Vol. 35 ›› Issue (4): 938-943.DOI: 10.11772/j.issn.1001-9081.2015.04.0938

云计算环境下基于蜜蜂觅食行为的任务负载均衡算法

杨石¹, 王艳玲¹, 王永利²

1. 长春财经学院信息工程系, 长春 130122;
2. 哈尔滨工业大学计算机科学与技术学院, 哈尔滨 150001

收稿日期:2014-11-11 修回日期:2015-01-05 出版日期:2015-04-10 发布日期:2015-04-08
通讯作者: 杨石
作者简介:杨石(1982-),男,吉林磐石人,讲师,硕士,主要研究方向:云计算、服务计算; 王艳玲(1965-),女,吉林长春人,教授,主要研究方向:云计算、分布式计算; 王永利(1976-),男,吉林长春人,副教授,博士,主要研究方向:云计算、服务计算。
基金资助:
国家自然科学基金资助项目(61103143);中国博士后科学基金资助项目(2012M512008)。

Load balancing algorithm of task scheduling in cloud computing environment based on honey bee behavior

YANG Shi¹, WANG Yanling¹, WANG Yongli²

1. Department of Information Engineering, Changchun University of Finance and Economics, Changchun Jilin 130122, China;
2. College of Computer Science and Technology, Harbin Institute of Technology, Harbin Heilongjiang 150001, China

Received:2014-11-11 Revised:2015-01-05 Online:2015-04-10 Published:2015-04-08

摘要/Abstract

摘要：

针对云计算环境下的任务调度程序通常需要较多响应时间和通信成本的问题,提出了一种基于蜜蜂行为的负载均衡(HBB-LB)算法。首先,利用虚拟机(VM)进行负载平衡来最大化吞吐量;然后,对机器上任务的优先级进行平衡;最后,将平衡重点放在减少VM等待序列中任务的等待时间上,从而提高处理过程的整体吞吐量和优先级。利用CloudSim工具模拟云计算环境进行仿真实验,结果表明,相比粒子群优化(PSO)、蚁群算法(ACO)、动态负载均衡(DLB)、先入先出(FIFO)和加权轮询(WRR)算法, HBB-LB算法的平均响应时间分别节省了5%、13%、17%、67%、37%,最大完成时间分别节省了20%、23%、18%、55%、46%,可以更好地平衡非抢占式独立任务,适用于异构云计算系统。

关键词: 云计算环境, 任务调度, 蜜蜂觅食行为, 负载均衡, 虚拟机, 非抢占式

Abstract:

For the problem that task scheduling program in cloud computing environments usually takes high response time and communication costs, a Honey Bee Behavior inspired Load Balancing (HBB-LB) algorithm was proposed. Firstly, the load was balanced across Virtual Machines (VMs) for maximizing the throughput. Then the priorities of tasks on the machines were balanced. Finally, HBB-LB algorithm was used to improve the overall throughput of processing, and priority based balancing focused on reducing the wait time of tasks on a queue of the VM. The experiments were carried out in cloud computing environments simulated by CloudSim. The experiment results showed that HBB-LB algorithm respectively reduced average response time by 5%, 13%, 17%, 67% and 37% compared with Particle Swarm Optimization (PSO), Ant Colony Optimization (ACO), Dynamic Load Balancing (DLB), First In First Out (FIFO) and Weighted Round Robin (WRR) algorithms, and reduced maximum completion time by 20%, 23%, 18%, 55% and 46%. The result indicates that HBB-LB algorithm is suitable for cloud computing system and helpful to balancing non-preemptive independent tasks.

Key words: cloud computing environment, tasks scheduling, Honey Bee Behavior (HBB), load balancing, Virtual Machine (VM), non-preemptive

中图分类号:

TP391.9

杨石, 王艳玲, 王永利. 云计算环境下基于蜜蜂觅食行为的任务负载均衡算法[J]. 计算机应用, 2015, 35(4): 938-943.

YANG Shi, WANG Yanling, WANG Yongli. Load balancing algorithm of task scheduling in cloud computing environment based on honey bee behavior[J]. Journal of Computer Applications, 2015, 35(4): 938-943.

参考文献

[1] ZHANG W, ZHANG H, ZHANG D, et al. The research of multiple virtual machines memory collaborative optimization strategy on cloud computing platform [J]. Chinese Journal of Computers, 2011, 34(12): 2265-2277.(张伟哲, 张宏莉, 张迪, 等. 云计算平台中多虚拟机内存协同优化策略研究[J]. 计算机学报, 2011, 34(12): 2265-2277.)
[2] GUO T, LIU F, DU C, et al. Virtual machine deployment strategy optimization in cloud computing environment [J]. Application Research of Computers, 2012, 29(9): 3425-3427.(郭涛, 刘菲军, 杜矗, 等. 云计算环境下虚拟机部署策略的优化[J]. 计算机应用研究, 2012, 29(9): 3425-3427.)
[3] ERDIL D C, LEWIS M J. Dynamic grid load sharing with adaptive dissemination protocols [J]. The Journal of Supercomputing, 2012, 59(3): 1139-1166.
[4] LIU Z, WEN Z, ZHANG H. Cloud computing and cloud data management technology [J]. Computer Research and Development, 2012, 49(1): 26-31.(刘正伟, 文中领, 张海涛. 云计算和云数据管理技术 [J]. 计算机研究与发展, 2012, 49(1): 26-31.)
[5] RANDLES M, LAMB D, TALEB-BENDIAB A. A comparative study into distributed load balancing algorithms for cloud computing[C]// Proceedings of the 2010 IEEE 24th International Conference on Advanced Information Networking and Applications Workshops. Piscataway: IEEE Press, 2010: 551-556.
[6] HU J, GU J, SUN G, et al. A scheduling strategy on load balancing of virtual machine resources in cloud computing environment[C]// Proceedings of the 2010 IEEE Third International Symposium on Parallel Architectures, Algorithms and Programming. Piscataway: IEEE Press,2010: 89-96.
[7] WU H, WANG C, XIE J. TeraPELB: the elastic load balancing algorithm based on prediction in cloud computing [J]. Journal of System Simulation, 2013, 25(8): 1751-1760.(吴和生, 王崇骏, 谢俊元. TeraPELB: 云计算中基于预测的弹性负载均衡算法[J]. 系统仿真学报, 2013, 25(8): 1751-1760.)
[8] RANDLES M, LAMB D, TALEB-BENDIAB A. A comparative study into distributed load balancing algorithms for cloud computing[C]// Proceedings of the 2010 IEEE 24th International Conference on Advanced Information Networking and Applications Workshops. Piscataway: IEEE Press, 2010: 551-556.
[9] YAO J, HE J. A load balancing mechanism based on adaptive colony algorithm in cloud computing [J]. Journal of Computer Applications, 2012, 32(9): 2448-2450.(姚婧, 何聚厚. 基于自适应蜂群算法的云计算负载平衡机制[J]. 计算机应用, 2012, 32(9): 2448-2450.)
[10] LI Q, HAO Q, XIAO L, et al. Adaptive management and multi-objective optimization of virtual machine placing in cloud computing [J]. Chinese Journal of Computers, 2011, 34(12): 2253-2264.(李强, 郝沁汾, 肖利民, 等. 云计算中虚拟机放置的自适应管理与多目标优化[J]. 计算机学报, 2011, 34(12): 2253-2264.)
[11] ZHUO T, ZHAN Y. A resource scheduling model by improving artificial colony algorithm in cloud computing [J]. Microelectronics and Computers, 2014, 31(7):147-155.(卓涛, 詹颖. 改进人工蜂群算法的云计算资源调度模型[J]. 微电子学与计算机, 2014, 31(7):147-155.)
[12] PADHY R P, RAO P G P, Load balancing in cloud computing systems [EB/OL].[2013-10-10]. http://ethesis.nitrkl.ac.in/2545/1/load_balancing_in_cloud_computing_systems.pdf.
[13] REDDY G N, KUMAR S P. Review of load balancing techniques in cloud computing environment: challenges and algorithms[J]. International Journal of Advanced Research in Computer Science, 2014, 5(4):124-133.
[14] LYU L. The research of resource load balancing scheduling algorithm in cloud computing [D]. Urumqi: Xinjiang University, 2010.(吕良干. 云计算环境下资源负载均衡调度算法研究 [D]. 乌鲁木齐:新疆大学, 2010.)
[15] MISHRA R, JAISWAL A. Ant colony optimization: a solution of load balancing in cloud [J]. International Journal of Web and Semantic Technology, 2012, 3(2): 33-50.
[16] LIU Z, WANG X. A PSO-based algorithm for load balancing in virtual machines of cloud computing environment[C]// Proceedings of the Third International Conference on Advances in Swarm Intelligence, LNCS 7331. Berlin: Springer-Verlag, 2012: 142-147.
[17] LI S-H, HWANG J-I G. Bidirectional ant colony optimization algorithm for cloud load balancing[C]// Proceedings of the 2nd International Conference on Intelligent Technologies and Engineering Systems, LNEE 293. Berlin: Springer-Verlag, 2014: 907-913.

云计算环境下基于蜜蜂觅食行为的任务负载均衡算法

Load balancing algorithm of task scheduling in cloud computing environment based on honey bee behavior

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	杨翎, 姜春茂. 基于三支决策的虚拟机节能迁移策略[J]. 计算机应用, 2021, 41(4): 990-998.
[2]	许红亮, 杨桂芹, 蒋占军. 基于软件定义网络的数据中心自适应多路径负载均衡算法[J]. 计算机应用, 2021, 41(4): 1160-1164.
[3]	平凡, 汤小春, 潘彦宇, 李战怀. 不规则任务在图形处理器集群上的调度策略[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3295-3301.
[4]	蔡豪, 袁正道. 云数据中心基于贪心模式的虚拟机选择算法[J]. 计算机应用, 2020, 40(6): 1707-1713.
[5]	郭曙杰, 李志华, 蔺凯青. 云环境下基于模糊隶属度的虚拟机放置算法[J]. 计算机应用, 2020, 40(5): 1374-1381.
[6]	李翠, 陈庆奎. 基于DPDK并行通信的动态监控模型[J]. 计算机应用, 2020, 40(2): 335-341.
[7]	刘智翔, 刘慧超, 黄冬梅, 周丽萍, 苏诚. 多种任务调度混合的IB-LBM并行优化方法[J]. 计算机应用, 2020, 40(2): 386-391.
[8]	李孜颖, 石振国. 面向大数据任务的调度方法[J]. 计算机应用, 2020, 40(10): 2923-2928.
[9]	张译天, 于炯, 鲁亮, 李梓杨. 大数据流式计算框架Heron环境下的流分类任务调度策略[J]. 计算机应用, 2019, 39(4): 1106-1116.
[10]	李祝红, 赵灿明, 闫龙, 张信明. 智能电网中电力线通信网络负载均衡的机会路由协议[J]. 计算机应用, 2019, 39(3): 812-816.
[11]	沙宗轩, 薛菲, 朱杰. 基于并行强化学习的云机器人任务调度策略[J]. 计算机应用, 2019, 39(2): 501-508.
[12]	蔺凯青, 李志华, 郭曙杰, 李双俐. 云环境中多目标优化的虚拟机放置算法[J]. 计算机应用, 2019, 39(12): 3597-3603.
[13]	刘开南. 云数据中心基于贪心算法的虚拟机迁移策略[J]. 计算机应用, 2019, 39(11): 3333-3338.
[14]	孙敏, 叶侨楠, 陈中雄. 云环境下方差定向变异遗传算法的任务调度[J]. 计算机应用, 2019, 39(11): 3328-3332.
[15]	刘鹏飞, 毛莺池, 王龙宝. 基于云雾协作模型的任务分配方法[J]. 计算机应用, 2019, 39(1): 8-14.