基于改进混合蛙跳算法的云工作流负载均衡调度优化

doi:10.11896/jsjkx.181001866

摘要/Abstract

摘要： 在实例密集型和开放的云环境下,工作流调度通常面临着廉价和优质资源被频繁调用的问题,导致调度效率低下,云环境稳定性遭到破坏。此外,区别于一般的任务调度,工作流任务之间通常具有关联依赖性,极大地提高了任务分配的复杂度。针对目前大多数云工作流调度中存在虚拟机间负载不均衡的现象,首先提出一种工作流分层调度模型,按任务优先级进行层级划分,将优先级相近且相互独立的任务置于同一层级,通过分层执行任务来有效缓解虚拟机的负载压力。其次,基于混合蛙跳算法进行改进,采用时间贪心算法来优化初始种群,以提高搜索效率;并增加对局部最优个体的重建策略来跳出局部最优,增强全局搜索能力。最后,将改进后的混合蛙跳算法(ISFLA)应用于云工作流调度,通过WorkflowSim仿真平台来模拟工作流调度的真实场景,并将改进后的混合蛙跳算法与传统的混合蛙跳算法及粒子群算法进行对比,从负载均衡度、工作流整体完成时间和搜索效率3个方面进行评价。实验结果表明,在迭代相同次数后,ISFLA的负载均衡度最优,并且随着任务数的增加,其值最先趋于稳定;同时,在工作流整体完成时间上,ISFLA也显著低于其他算法;在搜索效率方面,由于使用贪心算法提高了初始种群质量,ISFLA的搜索耗时大幅缩短。

关键词: 负载均衡, 混合蛙跳, 局部最优, 任务调度, 云工作流

Abstract: In instance-intensive and open cloud environments,workflow scheduling always suffers from frequent calls of the cheap and high-quality resources,resulting in poor scheduling efficiency and disruption of stability.In addition,unlike general task scheduling,workflow tasks usually have associated dependencies,which greatly increase the complexity of task assignment.Aiming at the imbalance of load between cloud virtual machines,a workflow hierarchical scheduling model was proposed,which is hierarchically divided according to task priorities so as to alleviate virtual machine load pressure.Besides,to optimize the shuffled frog leaping algorithm(ISFLA),the time greedy strategy is applied to initia-lize population,as a result,improving the search efficiency.Then,by enhancing the position of best solutions locally,a reconstruction strategy was put forward to go out of the dilemma of local optimum.Finally,the experimental results in cloud workflow scheduling show that the improved shuffled frog leaping algorithm can optimize load balance degree and is more effective in task processing as well as searching compared with the traditional shuffled frog leaping algorithm and particle swarm optimization.

Key words: Cloud workflow, Load balancing, Local optimum, SFLA, Task scheduling

中图分类号:

TP391

徐俊, 项倩红, 肖刚. 基于改进混合蛙跳算法的云工作流负载均衡调度优化[J]. 计算机科学, 2019, 46(11): 315-322. https://doi.org/10.11896/jsjkx.181001866

XU Jun, XIANG Qian-hong, XIAO Gang. Load Balancing Scheduling Optimization of Cloud Workflow Using Improved Shuffled Frog Leaping Algorithm[J]. Computer Science, 2019, 46(11): 315-322. https://doi.org/10.11896/jsjkx.181001866

参考文献

[1]CHAI X Z,CAO J.Cloud Computing Oriented Workflow Technology[J].Journal of Chinese Computer Systems,2012,33(1):90-95.(in Chinese)
柴学智,曹健.面向云计算的工作流技术[J].小型微型计算机系统,2012,33(1):90-95.
[2]ZHU Z,ZHANG G,LI M,et al.Evolutionary Multi-Objective Workflow Scheduling in Cloud[J].IEEE Transactions on Parallel & Distributed Systems,2016,27(5):1344-1357.
[3]CHEN H K,ZHU J H,ZHU X M,et al.Resource-Delay-Aware Scheduling for Real-Time Tasks in Clouds[J].Journal of Software,2017,54(2):446-456.(in Chinese)
陈黄科,祝江汉,朱晓敏,等.云计算中资源延迟感知的实时任务调度方法[J].软件学报,2017,54(2):446-456.
[4]ZHENG H S,YU D J,ZHANG L.Multi-QoS Cloud Workflow Scheduling Based on Firefly Algorithm and Dynamic Priorities[J].Computer Integrated Manufacturing Systems,2017,23(5):963-971.(in Chinese)
郑宏升,俞东进,张蕾.基于萤火虫算法和动态优先级的多QoS云工作流调度[J].计算机集成制造系统,2017,23(5):963-971.
[5]ULLMAN J D.NP-complete scheduling problems[M].AcademicPress,Inc.1975.
[6]RAHMAN M,VENUGOPAL S,BUYYA R.A Dynamic Critical Path Algorithm for Scheduling Scientific Workflow Applications on Global Grids[C]∥IEEE International Conference on E- Science and Grid Computing.IEEE Computer Society,2007:35-42.
[7]ZHU Y,LI W,LUO J Z.Multi-User Oriented Load-Aware Dynamic Service Selection Model[J].Journal of Software,2014,25(6):1196-1211.(in Chinese)
朱勇,李伟,罗军舟.一种面向多用户的负载感知动态服务选择模型[J].软件学报,2014,25(6):1196-1211.
[8]CHEN W,DA S R F,DEELMAN E,et al.Using imbalance metrics to optimize task clustering in scientific workflow executions[J].Future Generation Computer Systems,2014,46(1):69-84.
[9]DHINESH B L D,KRISHNA P V.Honey bee behavior inspired load balancing of tasks in cloud computing environments[J].Applied Soft Computing Journal,2013,13(5):2292-2303.
[10]TAWFEEK M A,EL-SISI A,KESHK A E,et al.Cloud taskscheduling based on ant colony optimization[C]∥International Conference on Computer Engineering & Systems.IEEE,2014:64-69.
[11]SUN L Y,LING M,ZHU P,et al.Load balancing Task Scheduling Algorithm Based on Tabu Search in Cloud Computing[J].Journal of Chinese Computer Systems,2015,36(9):1948-1952.(in Chinese)
孙凌宇,冷明,朱平,等.云计算环境下基于禁忌搜索的负载均衡任务调度优化算法[J].小型微型计算机系统,2015,36(9):1948-1952.
[12]EUSUFF M,LANSEY K,PASHA F.Shuffled frog-leaping algorithm:a memetic meta-heuristic for discrete optimization[J].Engineering Optimization,2006,38(2):129-154.
[13]LUO X H,YANG Y,LI X.Modified shuffled frog-leaping algorithm to solve traveling salesman problem[J].Journal on Communications,2009,30(7):130-135.(in Chinese)
罗雪晖,杨烨,李霞.改进混合蛙跳算法求解旅行商问题[J].通信学报,2009,30(7):130-135.
[14]WANG L,FANG C.An effective shuffled frog-leaping algorithm for multi-mode resource-constrained project scheduling problem[J].Information Sciences,2011,181(20):4804-4822.
[15]KAUR P,MEHTA S.Resource provisioning and workflowscheduling in clouds using augmented Shuffled Frog Leaping Algorithm[M].Academic Press,2017.
[16]JUVE G,CHERVENAK A,DEELMAN E,et al.Characterizing and profiling scientific workflows[J].Future Generation Computer Systems,2013,29(3):682-692.
[17]THANT P T,POWELL C,SCHLUETER M,et al.A Level-Wise Load Balanced Scientific Workflow Execution Optimization Using NSGA-II[C]∥IEEE/ACM International Symposium on Cluster,Cloud and Grid Computing.ACM,2017:882-889.
[18]EUSUFF M M,LANSEY K E.Optimization of Water Distribution Network Design Using the Shuffled Frog Leaping Algorithm[J].Journal of Water Resources Planning & Management,2003,129(3):210-225.
[19]CHEN H,WANG F,NA H,et al.User-priority guided Min-Min scheduling algorithm for load balancing in cloud computing[C]∥Parallel Computing Technologies.IEEE,2013:1-8.
[20]CHEN W,DEELMAN E.WorkflowSim:A toolkit for simulating scientific workflows in distributed environments[C]∥IEEE,International Conference on E-Science.IEEE,2013:1-8.
[21]ACCORSI R,STOCKER T.Discovering Workflow Changeswith Time-Based Trace Clustering[M]∥Data-Driven Process Discovery and Analysis.Berlin:Springer,2017:154-168.
[22]ALAM M,SHAKIL K A,SETHI S.Analysis and clustering of workload in google cluster trace based on resource usage[C]∥Computational Science and Engineering (CSE) and IEEE Intl Conference on Embedded and Ubiquitous Computing (EUC) and 15th Intl Symposium on Distributed Computing and Applications for Business Engineering (DCABES).IEEE,2016:740-747.
[23]DENG Y,CHENG X H.A heterogeneous multiprocessor taskscheduling algorithm based on SFLA[C]∥World Automation Congress.IEEE,2016:1-5.
[24]CHEN W N,ZHANG J.A set-based discrete PSO for cloudworkflow scheduling with user-defined QoS constraints[C]∥IEEE International Conference on Systems,Man,and Cyberne-tics.IEEE,2012:773-778.
[25]TAO X L,WEI Y,WANG Y.A Load Balancing Method Based on Hierarchy and Multi-agent for Cloud Computing Platform.Acta Electronica Sinica,2016,44(9):1068-1077.(in Chinese)
陶晓铃,韦毅,王勇.一种基于分层多代理的云计算负载均衡方法.电子学报,2016,44(9):1068-1077.
[26]WANG L.Research and implementation of task scheduling algorithm in cloud environment.Chengdu:University of Electronic Science and Technology of China,2016.(in Chinese)
王玲.云计算下任务调度算法的研究与实现.成都:成都电子科技大学,2016.
[27]WANG Y W,GUO Y F,LIU W Y,et al.A Task Scheduling Method for Cloud Workflow Security.Joural Computer Research and Development,2018,55(6):66-75. (in Chinese)
王亚文,郭云飞,刘文彦,等.面向云工作流安全的任务调度方法.计算机研究与发展,2018,55(6):66-75.

相关文章 15

[1]	田真真, 蒋维, 郑炳旭, 孟利民. 基于服务器集群的负载均衡优化调度算法 Load Balancing Optimization Scheduling Algorithm Based on Server Cluster 计算机科学, 2022, 49(6A): 639-644. https://doi.org/10.11896/jsjkx.210800071
[2]	高捷, 刘沙, 黄则强, 郑天宇, 刘鑫, 漆锋滨. 基于国产众核处理器的深度神经网络算子加速库优化 Deep Neural Network Operator Acceleration Library Optimization Based on Domestic Many-core Processor 计算机科学, 2022, 49(5): 355-362. https://doi.org/10.11896/jsjkx.210500226
[3]	田冰川, 田臣, 周宇航, 陈贵海, 窦万春. 减少Hadoop集群中网络队头阻塞的调度算法 Reducing Head-of-Line Blocking on Network in Hadoop Clusters 计算机科学, 2022, 49(3): 11-22. https://doi.org/10.11896/jsjkx.210900117
[4]	谭双杰, 林宝军, 刘迎春, 赵帅. 基于机器学习的分布式星载RTs系统负载调度算法 Load Scheduling Algorithm for Distributed On-board RTs System Based on Machine Learning 计算机科学, 2022, 49(2): 336-341. https://doi.org/10.11896/jsjkx.201200126
[5]	沈彪, 沈立炜, 李弋. 空间众包任务的路径动态调度方法 Dynamic Task Scheduling Method for Space Crowdsourcing 计算机科学, 2022, 49(2): 231-240. https://doi.org/10.11896/jsjkx.210400249
[6]	夏中, 向敏, 黄春梅. 基于CHBL的P2P视频监控网络分层管理机制 Hierarchical Management Mechanism of P2P Video Surveillance Network Based on CHBL 计算机科学, 2021, 48(9): 278-285. https://doi.org/10.11896/jsjkx.201200056
[7]	宋海宁, 焦健, 刘永. 高速公路中的移动边缘计算研究 Research on Mobile Edge Computing in Expressway 计算机科学, 2021, 48(6A): 383-386. https://doi.org/10.11896/jsjkx.200900212
[8]	王政, 姜春茂. 一种基于三支决策的云任务调度优化算法 Cloud Task Scheduling Algorithm Based on Three-way Decisions 计算机科学, 2021, 48(6A): 420-426. https://doi.org/10.11896/jsjkx.201000023
[9]	郑增乾, 王锟, 赵涛, 蒋维, 孟利民. 带宽和时延受限的流媒体服务器集群负载均衡机制 Load Balancing Mechanism for Bandwidth and Time-delay Constrained Streaming Media Server Cluster 计算机科学, 2021, 48(6): 261-267. https://doi.org/10.11896/jsjkx.200400131
[10]	姚泽玮, 林嘉雯, 胡俊钦, 陈星. 基于PSO-GA的多边缘负载均衡方法 PSO-GA Based Approach to Multi-edge Load Balancing 计算机科学, 2021, 48(11A): 456-463. https://doi.org/10.11896/jsjkx.210100191
[11]	蔡凌峰, 魏祥麟, 邢长友, 邹霞, 张国敏. 故障场景下的边缘计算DAG任务重调度方法 Failure-resilient DAG Task Rescheduling in Edge Computing 计算机科学, 2021, 48(10): 334-342. https://doi.org/10.11896/jsjkx.210300304
[12]	杨紫淇, 蔡英, 张皓晨, 范艳芳. 基于负载均衡的VEC服务器联合计算任务卸载方案 Computational Task Offloading Scheme Based on Load Balance for Cooperative VEC Servers 计算机科学, 2021, 48(1): 81-88. https://doi.org/10.11896/jsjkx.200800220
[13]	郭飞雁, 唐兵. 基于用户延迟感知的移动边缘服务器放置方法 Mobile Edge Server Placement Method Based on User Latency-aware 计算机科学, 2021, 48(1): 103-110. https://doi.org/10.11896/jsjkx.200900146
[14]	王国澎, 杨剑新, 尹飞, 蒋生健. 负载均衡的处理器运算资源分配方法 Computing Resources Allocation with Load Balance in Modern Processor 计算机科学, 2020, 47(8): 41-48. https://doi.org/10.11896/jsjkx.191000148
[15]	金琪, 王俊昌, 付雄. 基于智能放置策略的Cuckoo哈希表 Cuckoo Hash Table Based on Smart Placement Strategy 计算机科学, 2020, 47(8): 80-86. https://doi.org/10.11896/jsjkx.191200109

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed