基于蜂群算法的多维QoS云计算任务调度

摘要/Abstract

摘要：

针对云计算环境下用户日益多样化的QoS需求和高效的资源调度要求，提出了基于改进蜂群算法的多维QoS云计算任务调度算法，其中包括构建任务模型、云资源模型和用户QoS模型。为了获得高效的调度，引入蜂群算法。针对该算法在后期收敛速度变慢且易陷入局部最优的问题，引入收益比、跟随比概念及当前个体最优值及随机向量，避免“早熟”现象的出现。通过实验仿真，将该算法HEFT与和ABC算法进行比较，实验表明，该算法能获得较高的调度效率和用户满意度。

关键词: 云计算, 任务调度, 蜂群算法, 服务质量（QoS）

Abstract:

In order to meet the users’ Quality of Service(QoS) requirements and the efficient resource scheduling requirements in cloud environment, we propose a multidimensional QoS cloud task scheduling algorithm based on the artificial bee colony algorithm, which includes building a task model, a cloud resource model and a QoS model. In order to achieve efficient scheduling, we introduce an artificial bee colony algorithm. Because of its defects such as slow convergence and easy to fall into local optimization at the later stage, we introduce the profitability ratio, following ratio, current personal best value and random vectors to avoid the premature phenomenon. We compare this algorithm with the heterogeneous earliest finish time(HEFT ) algorithm and the artificial bee colony(ABC) algorithm through simulation, and experimental results show that the proposed algorithm can achieve higher operation efficiency and user satisfaction.

Key words: cloud computing;task scheduling;colony algorithm;quality of service (QoS)

颜丽燕，张桂珠. 基于蜂群算法的多维QoS云计算任务调度[J]. J4, 2016, 38(04): 648-655.

YAN Liyan，ZHANG Guizhu. Multidimensional QoS cloud task scheduling
based on colony algorithm[J]. J4, 2016, 38(04): 648-655.

参考文献［12］

［1］	Rimal B P,Choi E,Lumb I. A taxonomy and survey of cloud computing systems［C］∥Proc of the 2009 5th International Joint Conference on INC,IMS and IDC,2009:4451.
［2］	Wang Fang,Li Meian,Duan Weijun.Cloud computing task scheduling based on dynamically adaptive ant colony algorithm［J］.Journal of Computer Applications，2013，33(11):31603162.(in Chinese)
［3］	Pu Xun, Du Jia, Lu Xianliang. Task scheduling policy for cloud computing based on user priority level［J］.Computer Engineering，2013,39(8):6468.(in Chinese)
［4］	Li Yitong,Lin Yan. Cloud task scheduling based on hybrid particle swarm optimization algorithm［J］.Computing Technology and Automation,2014,33(1):7377.(in Chinese)
［5］	Zhang Qiaolong,Zhang Guizhu,Wu Delong. Multidimensional QoS cloud task scheduling algorithm based on task replication［J］.Journal of Computer Applications,2014,34(9):25272531.(in Chinese)
［6］	Karaboga D. An idea based on honey bee swarm for numerical optimization:Technical Reporttr06［R］. Turkey:Erciyes University,Engineering Faculty,Computer Engineering Department,2005.
［7］	Su Xiaoqin, Sun Hexu, Pan Xuhua. Improved bee colony optimization for TSP［J］.Computer Engineering and Design，2013，34（4）：14201424.(in Chinese)
［8］	Zhuo Tao,Zhan Ying.Scheduling model cloud computing resource based on improved artificial bee colony algorithm［J］.Microelectronics & Computer，2014，31（7）：147150.(in Chinese)
［9］	Teodorovi’D D. Swarm intelligence systems for transportation engineering:Principles and applications［J］. Transportation Research Part C:Emerging Technologies,2008,16(6):651667.
［10］	Chong C S,Sivakumar A I,Low M Y H,et al. A bee colony optimization algorithm to job shop scheduling［C］∥Proc of the 38th Conference on Winter Simulation,2006:19541961.
［11］	Lucic P,Teodorovic D. Vehicle routing problem with uncertain demand at nodes:The bee system and fuzzy logic approach［M］∥Fuzzy Sets Based Heuristics for Optimization. Berlin:Springer Berlin Heidelberg,2003:6782.
［12］	Yao Jing,He Juhou.Load balancing strategy of cloud computing based on artificial bee algorithm［J］.Journal of Computer Applications，2012，32(9):24482450.(in Chinese)
［13］	Wong Lipei,Malcolm Yoke Hean Low，Chin Soon Chong. A bee colony optimization algorithm for traveling salesman problem［C］∥Proc of the 2008 Secend Asia International Conference on Modeling & Simulation,2008:818823.
［14］	Chong C S，Malcolmlow Y H,Sivakumar A I.Using a bee colony algorithm for neighborhood search in job shop scheduling problem［C］∥Proc of Europeean Conference on Modeling & Simulation,2007:10191025.
［15］	Wong L P,Low M Y H,Chong C S. An efficient bee colony optimization algorithm for traveling salesman problem using frequencybased pruning［C］∥Proc of the 7th IEEE International Conference on Industrial Informatics,2009:775782.
［16］	Topcuoglu H, Hariri S, Wu MY. Performanceeffective and lowcomplexity task scheduling for heterogeneous computing［J］.IEEE Transactions on Parallel and Distributed Systems，2002，13(3):260274．
	附中文参考文献：
［2］	王芳，李美安，段卫军.基于动态自适应蚁群算法的云计算任务调度［J］.计算机应用，2013，33(11):31603162.
［3］	蒲汛，杜嘉，卢显良.基于用户优先级的云计算任务调度策略［J］.计算机工程，2013,39(8):6468.
［4］	李依桐，林燕.基于混合粒子群算法的云计算任务调度研究［J］.计算技术与自动化,2014,33(1):7377.
［5］	张巧龙，张桂珠，吴德龙.基于任务复制的多维QoS云计算任务调度［J］.计算机应用,2014,34(9):25272531.
［7］	苏晓勤，孙鹤旭,潘旭华.改进蜂群算法的旅行商问题仿真［J］.计算机工程与设计，2013，34（4）：14201424.
［8］	卓涛，詹颖.改进人工蜂群算法的云计算资源调度模型［J］.微电子学与计算机，2014，31（7）：147150.
［12］	姚靓，何聚厚.基于自适应蜂群算法的云计算负载平衡机制［J］.计算机应用，2012,32(9):24482450.

[1]	李卫平1,2，武海燕2，杨杰1. 基于效益博弈的云计算资源动态可协调分配策略研究[J]. J4, 20160101, 38(01): 57-61.
[2]	温瑞林, 樊春, 马银萍 , 王政丹, 向广宇 , 付振新. SlurmX：基于Slurm使用面向对象设计方法重构的任务调度系统[J]. 计算机工程与科学, 2022, 44(09): 1532-1541.
[3]	李文佳, 史岚, 季航旭, 罗意彭. 面向Flink的负载均衡任务调度算法的研究与实现[J]. 计算机工程与科学, 2022, 44(07): 1141-1151.
[4]	杨柏蔼, 赵山, 刘芳. 无服务器计算技术研究综述[J]. 计算机工程与科学, 2022, 44(04): 611-619.
[5]	庄鹤林, 杨火根, 夏小云, 廖伟志. 关于矩阵乘法问题的人工蜂群优化算法研究[J]. 计算机工程与科学, 2021, 43(12): 2131-2138.
[6]	罗磊, 陈照云, 王俪璇. 用户QoS感知的GPU集群深度学习任务动态调度[J]. 计算机工程与科学, 2021, 43(08): 1331-1340.
[7]	杨坚伟, 孟敏, 黄家乐, 武继刚. 分布式训练异构任务调度算法研究[J]. 计算机工程与科学, 2021, 43(07): 1160-1167.
[8]	黄山, 房六一, 徐浩桐, 段晓东, . 面向容器环境的Flink的任务调度优化研究[J]. 计算机工程与科学, 2021, 43(07): 1173-1184.
[9]	李波, 侯鹏, 牛力, 武浩, 丁洪伟. 基于软件定义网络的云边协同架构研究综述[J]. 计算机工程与科学, 2021, 43(02): 242-257.
[10]	邢红星, 魏叶华, 乐懿. 硬件成本缩减的异构分布式嵌入式系统调度算法[J]. 计算机工程与科学, 2021, 43(02): 258-265.
[11]	廖建锦, 孙庆骁, 杨海龙, 栾钟治, 钱德沛. 满足工作流执行时限的可抢占虚拟机实例配置和调度方法研究[J]. 计算机工程与科学, 2020, 42(11): 1956-1964.
[12]	林涛, 冯竞凯, 郝章肖, 黄少群. 基于组合预测模型的云计算资源负载预测研究[J]. 计算机工程与科学, 2020, 42(07): 1168-1173.
[13]	包敏泽, 胡秀婷, 谢玉莹, 蒋波. 基于人工蜂群算法的p-center问题求解算法[J]. 计算机工程与科学, 2020, 42(06): 1127-1133.
[14]	胡亚红1，盛夏2，毛家发1. 资源不均衡Spark环境任务调度优化算法研究[J]. 计算机工程与科学, 2020, 42(02): 203-209.
[15]	赵凤1,2，孔令润1,2，马改妮1,2. 多目标粒子群和人工蜂群混合优化的阈值图像分割算法[J]. 计算机工程与科学, 2020, 42(02): 281-290.