多云环境下带截止日期约束的科学工作流调度策略

doi:10.11959/j.issn.1000-436x.2018006

通信学报 ›› 2018, Vol. 39 ›› Issue (1): 56-69.doi: 10.11959/j.issn.1000-436x.2018006

多云环境下带截止日期约束的科学工作流调度策略

林兵^1,^2,³,郭文忠^2,^3,⁴,陈国龙^2,³

¹ 福建师范大学物理与能源学院，福建福州 350117
² 福建省网络计算与智能信息处理重点实验室（福州大学），福建福州 350116
³ 空间数据挖掘与信息共享教育部重点实验室，福建福州 350003
⁴ 福州大学数学与计算机科学学院，福建福州 350116

修回日期:2018-01-01 出版日期:2018-01-01 发布日期:2018-02-07
作者简介:林兵（1986-），男，福建福清人，博士，福建师范大学讲师，主要研究方向为云计算技术、计算智能及其应用。|郭文忠（1979-），男，福建泉港人，博士，福州大学教授、博士生导师，主要研究方向为计算智能及其应用。|陈国龙（1965-），男，福建莆田人，博士，福州大学教授、博士生导师，主要研究方向为人工智能、网络安全。
基金资助:
国家重点研发计划基金资助项目(2017YFB1002000);国家自然科学基金资助项目(61672159);福建省科技创新平台计划基金资助项目(2009J1007);福建省科技创新平台计划基金资助项目(2014H2005);海峡政务大数据应用省级协同创新中心基金资助项目

Scheduling strategy for science workflow with deadline constraint on multi-cloud

Bing LIN^1,^2,³,Wenzhong GUO^2,^3,⁴,Guolong CHEN^2,³

¹ College of Physics and Energy,Fujian Normal University,Fuzhou 350117,China
² Fujian Provincial Key Laboratory of Networking Computing and Intelligent Information Processing (Fuzhou University),Fuzhou 350116,China
³ Key Laboratory of Spatial Data Mining ＆Information Sharing,Ministry of Education,Fuzhou 350003,China
⁴ College of Mathematics and Computer Science,Fuzhou University,Fuzhou 350116,China

Revised:2018-01-01 Online:2018-01-01 Published:2018-02-07
Supported by:
The National Key R＆D Program of China(2017YFB1002000);The National Natural Science Foundation of China(61672159);The Technology Innovation Platform Project of Fujian Province(2009J1007);The Technology Innovation Platform Project of Fujian Province(2014H2005);The Foundation of The Fujian Collaborative Innovation Center for Big Data Application in Governments

摘要/Abstract

摘要：

针对多云环境下带截止日期约束的科学工作流调度问题，提出一种基于遗传算法操作的自适应离散粒子群优化算法（ADPSOGA），目的是在尽可能满足工作流截止日期前提下，减少其执行代价。该方法考虑多云之间的通信代价、虚拟机的启动和关闭时间以及多云之间不同的带宽通信波动；为了避免传统粒子群优化算法（PSO,particle swarm optimization）存在的过早收敛问题，引入遗传算法的随机两点交叉操作和随机单点变异操作，有效提高种群进化过程中的多样性；在充分考虑数据通信代价和任务计算代价的情况下，设计一种基于工作流截止日期约束的代价驱动调度策略。实验结果表明，ADPSOGA在波动因素存在情况下，对工作流截止日期满足和执行代价控制方面具有良好的性能表现。

关键词: 云计算, 截止日期约束, 工作流调度, 波动性

Abstract:

In view of the deadline-constrained scientific workflow scheduling on multi-cloud,an adaptive discrete particle swarm optimization with genetic algorithm (ADPSOGA) was proposed,which aimed to minimize the execution cost of workflow while meeting its deadline constrains.Firstly,the data transfer cost,the shutdown and boot time of virtual machines,and the bandwidth fluctuations among different cloud providers were considered by this method.Secondly,in order to avoid the premature convergence of traditional particle swarm optimization (PSO),the randomly two-point crossover operator and randomly one-point mutation operator of the genetic algorithm (GA) was introduced.It could effectively improve the diversity of the population in the process of evolution.Finally,a cost-driven strategy for the deadline-constrained workflow was designed.It both considered the data transfer cost and the computing cost.Experimental results show that the ADPSOGA has better performance in terms of deadline and cost reducing in the fluctuant environment.

Key words: cloud computing, deadline constraint, workflow scheduling, fluctuation

中图分类号:

TP338

林兵,郭文忠,陈国龙. 多云环境下带截止日期约束的科学工作流调度策略[J]. 通信学报, 2018, 39(1): 56-69.

Bing LIN,Wenzhong GUO,Guolong CHEN. Scheduling strategy for science workflow with deadline constraint on multi-cloud[J]. Journal on Communications, 2018, 39(1): 56-69.

图/表 12

图1

表1

图2

图3

图4

图5

表2

表3

表4

表5

图6

图7

参考文献 20

[21]	WOO S S , MIRKOVIC J . Optimal application allocation on multiple public clouds[J]. Computer Networks, 2014,68(11): 138-148.
[22]	KENNEDY J , EBERHART R . Particle swarm optimization[C]// IEEE International Conference on Neural Networks. 2002: 1942-1948.
[23]	SU J S , GUO W Z , YU C L ,et al. Fault-tolerance clustering algorithm with load-balance aware in wireless sensor network[J]. Chinese Journal of Computers, 2014,37(2): 445-456.
[24]	SHI Y , EBERHART R . A modified particle swarm optimizer[C]// IEEE World Congress on Computational Intelligence. 1998: 69-73.
[25]	BHARATHI S , CHERVENAK A , DEELMAN E ,et al. Characterization of scientific workflows[C]// Workflows in Support of Large-Scale Science. 2008: 1-10.
[1]	RODRIGUEZ M A , BUYYA R . Deadline based resource provisioning and scheduling algorithm for scientific workflows on clouds[J]. IEEE Transactions on Cloud Computing, 2014,2(2): 222-235.
[2]	FARD H M , PRODAN R , FAHRINGER T . A truthful dynamic workflow scheduling mechanism for commercial multicloud environments[J]. IEEE Transactions on Parallel ＆ Distributed Systems, 2013,24(6): 1203-1212.
[3]	MALAWSKI M , JUVE G , DEELMAN E ,et al. Cost-and deadline-constrained provisioning for scientific workflow ensembles in IaaS clouds[C]// International Conference for High Performance Computing,Networking,Storage and Analysis. 2012: 1-11.
[4]	MASDARI M , SALEHI F , JALALI M ,et al. A survey of PSO-based scheduling algorithms in cloud computing[J]. Journal of Network ＆Systems Management, 2017,25(1): 1-37.
[5]	WU Z , NI Z , GU L ,et al. A revised discrete particle swarm optimization for cloud workflow scheduling[C]// International Conference on Computational Intelligence and Security, 2010: 184-188.
[6]	ABRISHAMI S , NAGHIBZADEH M , EPEMA D H J . Deadline-constrained workflow scheduling algorithms for infrastructure as a service clouds[J]. Future Generation Computer Systems, 2013,29(1): 158-169.
[7]	MATTOSO M , DIAS J,OCA?A K A C S ,et al. Dynamic steering of HPC scientific workflows:a survey[J]. Future Generation Computer Systems, 2015,46(C): 100-113.
[8]	ZENG L , VEERAVALLI B , ZOMAYA A Y . An integrated task computation and data management scheduling strategy for workflow applications in cloud environments[J]. Journal of Network ＆ Computer Applications, 2015,50(C): 39-48.
[9]	CHEN W N , ZHANG J . An ant colony optimization approach to a Grid workflow scheduling problem with various QoS requirements[J]. IEEE Transactions on Systems Man ＆ Cybernetics Part C, 2008,39(1): 29-43.
[10]	CAO H , JIN H , WU X ,et al. DAGMap:efficient and dependable scheduling of DAG workflow job in grid[J]. The Journal of Supercomputing, 2010,51(2): 201-223.
[11]	HIGASHINO W A , CAPRETZ M A M , TOLEDO M B F D ,et al. A hybrid particle swarm optimization-genetic algorithm applied to grid scheduling[J]. International Journal of Grid ＆ Utility Computing, 2016,7(2): 113-129.
[12]	苑迎春, 李小平, 王茜 ,等. 基于逆向分层的网格工作流调度算法[J]. 计算机学报, 2008,31(2): 282-290.
	YUAN Y C , LI X P , WANG Q ,et al. Bottom level based heuristic for workflow scheduling in grids[J]. Chinese Journal of Computers, 2008,31(2): 282-290.
[13]	ABRISHAMI S , NAGHIBZADEH M , EPEMA D H J . Cost-driven scheduling of grid workflows using partial critical paths[J]. IEEE Transactions on Parallel ＆ Distributed Systems, 2012,23(8): 1400-1414.
[14]	KHAJEMOHAMMADI H , FANIAN A , GULLIVER T A . Fast workflow scheduling for grid computing based on a multi-objective genetic algorithm[C]// Communications,Computers and Signal Processing. 2013: 96-101.
[15]	沈虹, 李小平 . 带准备时间和截止期约束的云服务工作流调度算法[J]. 通信学报, 2015,36(6): 183-192.
	SHEN H , LI X P . Algorithm for the cloud service workflow scheduling with setup time and deadline constraints[J]. Journal on Communica-tions, 2015,36(6): 183-192.
[16]	肖鹏, 胡志刚, 屈喜龙 . 面向数据密集型工作流的能耗感知调度策略[J]. 通信学报, 2015,36(1): 149-158.
	XIAO P , HU Z G , QU X L . Energy-aware scheduling policy for da-ta-intensive workflow[J]. Journal on Communications, 2015,36(1): 149-158.
[17]	MAO M , HUMPHREY M . Auto-scaling to minimize cost and meet application deadlines in cloud workflows[C]// High Performance Computing,Networking,Storage and Analysis. 2011: 1-12.
[18]	PANDEY S , WU L , GURU S M ,et al. A particle swarm optimization-based heuristic for scheduling workflow applications in cloud computing environments[C]// IEEE International Conference on Advanced Information Networking and Applications. 2010: 400-407.
[19]	KEAHEY K , TSUGAWA M , MATSUNAGA A ,et al. Sky computing[J]. IEEE Internet Computing, 2009,13(5): 43-51.
[26]	TOPCUOGLU H , HARIRI S , WU M Y . Performance-effective and low-complexity task scheduling for heterogeneous computing[J]. IEEE Transactions on Parallel ＆ Distributed Systems, 2002,13(3): 260-274.
[20]	LIN B , GUO W , XIONG N ,et al. A pretreatment workflow scheduling approach for big data applications in multicloud environments[J]. IEEE Transactions on Network ＆ Service Management, 2016,13(3): 581-594.

相关文献	设施环境		应用类型			环境波动性		目标		限制条件		方法
相关文献	单云	多云	作业	单工作流	工作流组	静态	动态	代价	时间	截止日期	预算	数据规划	启发式	元启发式
文献[1]	+	?	?	+	?	?	+	+	?	+	?	?	?	+
文献[2]	?	+	?	+	?	?	+	+	+	?	?	?	+	?
文献[3]	+	?	?	?	+	+	?	?	?	+	+	+	+	?
文献[5]	+	?	?	+	?	+	?	+	+	+	+	?	?	+
文献[15]	+	?	?	+	?	+	?	+	?	+	?	?	+	?
文献[17]	+	?	?	?	+	?	+	+	?	+	?	?	+	?
文献[18]	+	?	?	+	?	+	?	+	+	?	?	?	?	+
文献[20]	?	+	?	+	?	+	?	+	?	+	?	?	+	?

通信代价	C1→C2	C1→C3	C2→C3
均值/(Mbit·s^?1)	1.33	3.25	5.43
时间/(s·Gbit^?1)	770	315	189
均方差	29.50%	18.23%	33.26%

数据量	C1→(C2,C3)	C2→(C1,C3)	C3→(C2,C3)
0～1 GB	0.00	0.12	0.00
1 GB～1 TB	0.19	0.12	0.12
1～10 TB	0.19	0.12	0.11
10～50 TB	0.15	0.10	0.10

算法	小型		偏小型		中型
算法	ADPSOGA	WPSO	ADPSOGA	WPSO	ADPSOGA	WPSO
CyberShake	369	103	688	159	998	214
Epigenomics	392	273	934	348	997	391
LIGO	689	239	605	212	998	331
Montage	612	174	916	210	998	296
SIPHT	590	169	511	213	877	269

算法	小型		偏小型		中型
算法	ADPSOGA	WPSO	ADPSOGA	WPSO	ADPSOGA	WPSO
CyberShake	426	252	612	161	940	319
Epigenomics	457	260	585	322	861	308
LIGO	332	184	542	249	896	376
Montage	475	267	762	257	710	222
SIPHT	695	134	600	320	936	368

多云环境下带截止日期约束的科学工作流调度策略

Scheduling strategy for science workflow with deadline constraint on multi-cloud

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 12

参考文献 20

相关文章 15

Metrics

推荐阅读 0

[1]	马玲, 樊漆亮, 许婷, 郭冠琛, 张圣林, 孙永谦, 张玉志. 基于强化学习的在线离线混部云环境下的调度框架[J]. 通信学报, 2023, 44(6): 90-102.
[2]	王化群, 刘哲, 何德彪, 李继国. 公有云中身份基多源IoT终端数据PDP方案[J]. 通信学报, 2021, 42(7): 52-60.
[3]	张键红, 武梦龙, 王晶, 刘沛, 姜正涛, 彭长根. 云环境下安全的可验证多关键词搜索加密方案[J]. 通信学报, 2021, 42(4): 139-149.
[4]	李瑞琪, 贾春福, 王雅飞. 基于NTRU的多密钥同态代理重加密方案及其应用[J]. 通信学报, 2021, 42(3): 11-22.
[5]	张嘉伟, 马建峰, 马卓, 李腾. 云计算中基于时间和隐私保护的可撤销可追踪的数据共享方案[J]. 通信学报, 2021, 42(10): 81-94.
[6]	王文娟, 杜学绘, 单棣斌. 基于动态概率攻击图的云环境攻击场景构建方法[J]. 通信学报, 2021, 42(1): 1-17.
[7]	田有亮,骆琴. 基于改进Merkle-Tree认证方法的可验证多关键词搜索方案[J]. 通信学报, 2020, 41(9): 118-129.
[8]	王娜,郑坤,付俊松,李剑. 基于分块的移动边缘计算密文检索方法[J]. 通信学报, 2020, 41(7): 95-102.
[9]	赵临东,庄文芹,陈建新,周亮. 异构蜂窝网络中分层任务卸载：建模与优化[J]. 通信学报, 2020, 41(4): 34-44.
[10]	梁冰,纪雯. 基于次模优化的边云协同多用户计算任务迁移方法[J]. 通信学报, 2020, 41(10): 25-36.
[11]	苏命峰,王国军,李仁发. 基于利益相关视角的多维QoS云资源调度方法[J]. 通信学报, 2019, 40(6): 102-115.
[12]	陈兴蜀,滑强,王毅桐,葛龙,朱毅. 云环境下SDN网络低速率DDoS攻击的研究[J]. 通信学报, 2019, 40(6): 210-222.
[13]	王万良, 臧泽林, 陈国棋, 屠杭垚, 王宇乐, 陆琳彦. 大规模云计算服务器优化调度问题的最优二元交换算法研究[J]. 通信学报, 2019, 40(5): 180-191.
[14]	王田,沈雪微,罗皓,陈柏生,王国军,贾维嘉. 基于雾计算的可信传感云研究进展[J]. 通信学报, 2019, 40(3): 170-181.
[15]	何欣枫,田俊峰,刘凡鸣. 可信云平台技术综述[J]. 通信学报, 2019, 40(2): 154-163.