Cloud task scheduling strategy based on clustering and improved symbiotic organisms search algorithm

doi:10.11772/j.issn.1001-9081.2017092311

Abstract

Abstract: To solve the problems of some Quality of Service (QoS)-based scheduling algorithms in cloud computing environment, such as slow optimizing speed and imbalance between scheduling cost and user satisfaction, a cloud task scheduling strategy based on clustering and improved SOS (Symbiotic Organisms Search) algorithm was proposed. Firstly, the tasks and resources were clustered by fuzzy clustering and the resources were reordered and placed, and then the tasks were guided and assigned according to the similarity of attributes to reduce the selection range of resources. Secondly, the SOS algorithm was improved according to the cross and rotation learning mechanism to improve the algorithm search ability. Finally, the driving model was constructed by weighted summation to balance the relationship between scheduling cost and system performance. Compared with the improved global genetic algorithm, hybrid particle swarm optimization and genetic algorithm, and discrete SOS algorithm, the proposed algorithm can effectively reduce the evolution generation, reduce the scheduling cost and improve the user's satisfaction. Experimental results show that the proposed algorithm is a feasible and effective task scheduling algorithm.

Key words: cloud computing, Quality of Service (QoS), fuzzy clustering, Symbiotic Organisms Search (SOS) algorithm, task scheduling

摘要： 针对云计算环境中一些基于服务质量（QoS）调度算法存在寻优速度慢、调度成本与用户满意度不均衡的问题，提出了一种基于聚类和改进共生演算法的云任务调度策略。首先将任务和资源进行模糊聚类并对资源进行重排序放置，依据属性相似度对任务进行指导分配，减小对资源的选择范围；然后依据交叉和旋转学习机制改进共生演算法，提升算法的搜索能力；最后通过加权求和方式构造驱动模型，均衡调度代价与系统性能间关系。通过不同任务量的云任务调度仿真实验，表明该算法相比改进遗传算法、混合粒子群遗传算法和离散共生演算法，有效减少了进化代数，降低了调度成本并提升了用户满意度，是一种可行有效的任务调度算法。

关键词: 云计算, 服务质量, 模糊聚类, 共生演算法, 任务调度

CLC Number:

TP393.01

LI Kunlun, GUAN Liwei, GUO Changlong. Cloud task scheduling strategy based on clustering and improved symbiotic organisms search algorithm[J]. Journal of Computer Applications, 2018, 38(3): 707-714.

李昆仑, 关立伟, 郭昌隆. 基于聚类和改进共生演算法的云任务调度策略[J]. 计算机应用, 2018, 38(3): 707-714.

References

[1] FOSTER I, ZHAO Y,RAICU I, et al. Cloud computing and grid computing 360-degree compared[C]//GCE'08:Proceedings of the 2008 Grid Computing Environments. Washington,DC:IEEE Computer Society, 2008:1-10.
[2] BOCHENINA K. A comparative study of scheduling algorithms for the multiple deadline-constrained workflows in heterogeneous computing systems with time windows[EB/OL].[2017-04-12]. http://pdfs.semanticscholar.org/c88f/93f927d69432276665f53a5203c6987e8594.pdf.
[3] DURAO F,FONSEKA A,GARCIA V C, et al. A systematic review on cloud computing[J]. Journal of Supercomputing, 2014, 68(3):1321-1346.
[4] AVRAM M G. Advantages and challenges of adopting cloud computing from an enterprise perspective[EB/OL].[2017-04-12].https://core.ac.uk/download/pdf/82662807.pdf.
[5] AHMAD S G, LIEW C S, MUNIR E U, et al. A hybrid genetic algorithm for optimization of scheduling workflow applications in heterogeneous computing systems[J]. Journal of Parallel and Distributed Computing, 2016, 87(C):80-90.
[6] KOŁODZIEJ J, XHAFA F, BOGDANSKI M. Secure and task abortion aware GA-based hybrid metaheuristics for grid scheduling[M]//Proceedings of the 2011 International Conference on Parallel Problem Solving from Nature, LNCS 6238. Berlin:Springer, 2011:526-535.
[7] BRATTON D, KENNEDY J. Defining a standard for particle swarm optimization[C]//Proceedings of the 2007 IEEE Swarm Intelligence Symposium. Washington, DC:IEEE Computer Society, 2007:120-127.
[8] XUE S-J, WU W. Scheduling workflow in cloud computing based on hybrid partial swarm algorithm[J]. TELKOMNIKA:Indonesian Journal of Electrical Engineering, 2012,10(7):1560-1566.
[9] BANSAL N, MAURYA A, KUMAR T, et al. Cost performance of QoS driven task scheduling in cloud computing[EB/OL].[2017-04-15]. http://core.ac.uk/download/pdf/82232227.pdf.
[10] ARABNEJAD H, BARBOSA J G. Multi-QoS constrained and profit-aware scheduling approach for concurrent workflows on heterogeneous systems[J]. Future Generation Computer Systems, 2017,68:211-221.
[11] 王娟,李飞,张路桥.PSO应用于QoS偏好感知的云存储任务调度[J].通信学报,2014,35(3):231-238.(WANG J, LI F, ZHANG L Q. Apply PSO into cloud task scheduling with QoS preference awareness[J]. Journal on Communications, 2014, 35(3):231-238.)
[12] GAMAL EL DIN HASSAN ALI H, SAROIT I A, KOTB A M. Grouped tasks scheduling algorithm based on QoS in cloud computing network[J]. Egyptian Informatics Journal, 2017, 18(1):11-19.
[13] 杜晓丽,蒋昌俊,徐国荣,等.一种基于模糊聚类的DAG任务图调度算法[J].软件学报,2006,17(11):2277-2288.(DU X L, JIANG C J, XU G R, et al. A grid DAG scheduling algorithm based on fuzzy clustering[J]. Journal of Software, 2006, 17(11):2277-2288.)
[14] 陈志刚,杨博.网络服务资源多维性能聚类任务调度[J].软件学报,2009,20(10):2766-2774.(CHEN Z G,YANG B. Task scheduling based on multidimensional performance clustering of grid service resources[J]. Journal of Software,2009, 20(10):2766-2774.)
[15] 李文娟,张启飞,平玲娣,等.基于模糊聚类的云任务调度算法[J].通信学报,2012,33(3):146-153.(LI W J, ZHANG Q F, PING L D, et al. Cloud scheduling algorithm based on fuzzy clustering[J]. Journal on Communications, 2012, 33(3):146-153.)
[16] 郭凤羽,禹龙,田生伟,等.云计算环境下对资源聚类的工作流任务调度算法[J].计算机应用,2013,33(8):2154-2157.(GUO F Y, YU L, TIAN S W, et al. Workflow task scheduling algorithm based on resource clustering in cloud computing environment[J]. Journal of Computer Applications, 2013, 33(8):2154-2157.)
[17] DEAN J, GHEMAWAT S. MapReduce:simplified data processing on large clusters[C]//OSDI'04:Proceedings of the 6th Conference on Symposium on Operating Systems Design and Implementation. Berkeley, CA:USENIX Association, 2004:10.
[18] CHENG M Y, PRAYOGO D. Symbiotic organisms search:a new metaheuristic optimization algorithm[J]. Computer and Structures, 2014,139:98-112.
[19] EZUGWU E S, ADEWUMI A O, FRINCU M E. Simulated annealing based symbiotic organisms search optimization algorithm for traveling salesman problem[J]. Expert Systems with Applications, 2017,77:189-210.
[20] YU V F, REDI A A N P, YANG C L, et al. Symbiotic organisms search and two solution representations for solving the capacitated vehicle routing problem[J]. Applied Soft Computing, 2017, 52(C):657-672.
[21] TEJANI G G, SAVSANI V J, PATEL V K. Adaptive Symbiotic Organisms Search (SOS) algorithm for structural design optimization[J]. Journal of Computational Design and Engineering, 2016, 3(3):226-249.
[22] GUHA D, ROY P, BANERJEE S. Quasi-oppositional symbiotic organism search algorithm applied to load frequency control[J]. Swarm and Evolutionary Computation, 2016,33:46-67.
[23] ABDULLAHI M, NGADI M A, ABDULHAMID S M. Symbiotic organism search optimization based task scheduling in cloud computing environment[J]. Future Generation Computer Systems, 2016,56:640-650.
[24] BEZDEK J C. Pattern Recognition with Fuzzy Objective Function Algorithms[M]. Norwell, MA:Kluwer Academic Publishers, 1981:10-18.
[25] 王娟,李飞,刘兵,等.融合层次分析法的PSO云存储任务调度算法[J].计算机应用研究,2014,31(7):2013-2016.(WANG J, LI F, LIU B, et al. AHP integrated PSO task scheduling algorithm in cloud storage system[J]. Application Research of Computers, 2014, 31(7):2013-2016.)
[26] LI K. Scheduling parallel tasks with energy and time constraints on multiple manycore processors in a cloud computing environment[EB/OL].[2017-03-01]. http://www.cs.newpaltz.edu/~lik/publications/Keqin-Li-FGCS-2017.pdf.
[27] 李昆仑,王珺,宋健,等.基于改进GEP和资源改变量的局部云任务调度算法[J].软件学报,2015,26(S2):78-89.(LI K L, WANG J, SONG J, et al. Local cloud task scheduling algorithm based on improved GEP and change of resources[J]. Journal of Software, 2015, 26(S2):78-89.)