云计算环境下对资源聚类的工作流任务调度算法

计算机应用 ›› 2013, Vol. 33 ›› Issue (08): 2154-2157.

云计算环境下对资源聚类的工作流任务调度算法

郭凤羽¹,禹龙²,田生伟³,于炯³,孙华³

1. 新疆大学信息科学与工程学院，乌鲁木齐 830046;
2. 新疆大学网络中心，乌鲁木齐 830046
3. 新疆大学软件学院，乌鲁木齐 830008

收稿日期:2013-02-04 修回日期:2013-03-19 发布日期:2013-09-11 出版日期:2013-08-01
通讯作者: 禹龙
作者简介:郭凤羽(1990-)，女，河南邓州人，硕士研究生，主要研究方向：云计算、分布式计算;
禹龙(1974-)，女，新疆乌鲁木齐人，副教授，硕士，主要研究方向：计算机网络、计算机智能;
田生伟(1973-)，男，新疆乌鲁木齐人，教授，博士，主要研究方向：云计算、分布式计算、计算机智能;
于炯(1964-)，男，北京人，教授，博士，主要研究方向：云计算、网格与分布式计算、网络安全;
孙华(1977-)，女，新疆喀什人，讲师，博士，主要研究方向：信息安全、信誉管理。
基金资助:
新疆维吾尔自治区自然科学基金资助项目

Workflow task scheduling algorithm based on resource clustering in cloud computing environment

GUO Fenguu¹,YU Long²,TIAN Shengwei³,YU Jiong³,SUN Hua³

1. School of Information Science and Engineering, Xinjiang University, Urumqi Xinjiang 830046, China
2. Network Center, Xinjiang University, Urumqi Xinjiang 830046, China
3. School of Software, Xinjiang University, Urumqi Xinjiang 830008, China

Received:2013-02-04 Revised:2013-03-19 Online:2013-09-11 Published:2013-08-01
Contact: YU Long

摘要/Abstract

摘要： 针对云计算环境中资源具有规模庞大、异构性、多样性等特点，提出了一种对资源进行模糊聚类的工作流任务调度算法。经过对网络资源属性进行量化、规范化，以预先构建的任务模型和资源模型为基础，结合模糊数学理论划分资源，使得在任务调度时能够较准确地优先选择综合性能较好的资源类簇，缩短了任务资源相匹配的时间，提高了调度性能。通过仿真实验将此算法与HEFT、DLS进行比较，实验结果表明，当任务在[0,100]范围增加时，该算法平均SLR比HEFT小34%，比DLS小99%，其平均Speedup比HEFT大59%，比DLS大102%；当资源在[0,100]范围增加时，该算法平均SLR比HEFT小36%,比DLS小97%，其平均Speedup比HEFT大45%，比DLS大108%。所提算法实现了对资源的合理划分，且在执行跨度方面具有优越性。

关键词: 云计算, 工作流任务调度, 资源属性, 模糊聚类, 资源划分

Abstract: Focusing on the characteristics of resource under large-scale, heterogeneous and dynamic environment in cloud computing, a workflow task scheduling algorithm based on resource fuzzy clustering was proposed. After quantizing and normalizing the resource characteristics, this algorithm integrated the theory of clustering to divide the resources based on the workflow task model and the resource model constructed in advance. The cluster with better synthetic performance was chosen firstly in scheduling stage. Therefore, it shortened the matching time between the task and the resource, and improved the scheduling performance. By comparing this algorithm with HEFT (Heterogeneous Earliest Finish Time) and DLS (Dynamic Level Scheduling), the experimental results show that the average SLR (Schedule Length Ratio) of this algorithm was smaller than that of HEFT by 3.4%, the DLS by 9.9%, and the average speedup of this algorithm was faster than that of HEFT by 59%, the DLS by 10.2% with the increase of tasks in a certain range of [0,100]; when the resources were increased in a certain range of [0,100], the average SLR of this algorithm was smaller than that of HEFT by 3.6%, the DLS by 9.7%, and the average speedup of this algorithm was faster than that of HEFT by 4.5%, the DLS by 10.8%. The results indicate that the proposed algorithm realizes the reasonable division of resources, and it surpasses HEFT and DLS algorithms in makespan.

Key words: cloud computing, workflow task scheduling, resource characteristics, fuzzy clustering, resource division

中图分类号:

TP393.027

郭凤羽禹龙田生伟于炯孙华. 云计算环境下对资源聚类的工作流任务调度算法[J]. 计算机应用, 2013, 33(08): 2154-2157.

GUO Fenguu YU Long TIAN Shengwei YU Jiong SUN Hua. Workflow task scheduling algorithm based on resource clustering in cloud computing environment[J]. Journal of Computer Applications, 2013, 33(08): 2154-2157.

参考文献

［1］陈全，邓倩妮．云计算及其关键技术［J］．计算机应用，2009，29(9)：282-290．

［2］ARMBRUST M，FOX A，GRIFFITH R，et al. A view of cloud computing ［J］. Communications of the ACM，2010，53(4)： 50-58.

［3］LUIS M. V，LUIS R-M，JUAN C，et al. A break in the clouds: towards a cloud definition ［J］. ACM SIGCOMM Computer Communications Review，2009，39(1)： 50-55.

［4］罗海滨，范玉顺，吴澄．工作流技术综述［J］. 软件学报，2000，11(7)： 899-907.

［5］柴学智，曹健. 面向云计算的工作流技术［J］. 小型微型计算机系统，2012，33(1)：90-95.

［6］TOPCUOGLU H，HARIRI S， WU M-Y. Performance-effective and low-complexity task scheduling for heterogeneous computing ［J］. IEEE Transaction on Parallel and Distributed Systems，2002，13(3)： 260-274.

［7］LAN Z，SUN S X. Scheduling algorithm based on critical tasks in heterogeneous environments ［J］. Journal of Systems Engineering and Electronics，2008，19(2)： 398-404.

［8］OMARA F A，ARAFA M M. Genetic algorithms for task scheduling problem ［J］. Journal of Parallel and Distributed Computing，2010，70(1)： 13-22.

［9］宋娇，葛临东. 一种遗传模糊聚类算法及其应用［J］. 计算机应用，2008，28(5)： 1197-1199.

［10］DORIGO M，GAMBARDELLA L M. Ant colony system: a cooperative learning approach to the traveling salesman problem ［J］. IEEE Transactions on Evolutionary Computation，1997，1(1)： 53-66.

［11］张敏，于剑.基于划分的模糊聚类算法［J］. 软件学报，2004，15(6)：858-869.

［12］陈志刚，杨博. 网格服务资源多维性能聚类任务调度［J］. 软件学报，2009，20(10)： 2766-2775.

［13］ZADEH L A. Is there a need for fuzzy logic ［J］. Information Sciences，2008，178(13)： 2751-2779.

［14］姚婧，何聚厚. 基于模糊聚类分析的云计算负载平衡策略［J］. 计算机应用，2012，32(1)：213-217.

[1]	陆佳行, 戴华, 刘源龙, 周倩, 杨庚. 面向云环境密文排序检索的字典划分向量空间模型[J]. 《计算机应用》唯一官方网站, 2023, 43(7): 1994-2000.
[2]	唐海涛, 王红军, 李天瑞. 判别多维标度特征学习[J]. 《计算机应用》唯一官方网站, 2023, 43(5): 1323-1329.
[3]	游坤, 王钦辉, 李鑫. 通用的多元抵制假名的云计算拍卖机制[J]. 《计算机应用》唯一官方网站, 2023, 43(11): 3351-3357.
[4]	孙京宇, 朱家玉, 田自强, 史国振, 关川江. 基于椭圆曲线加密且支持撤销的属性基加密方案[J]. 《计算机应用》唯一官方网站, 2022, 42(7): 2094-2103.
[5]	张金泉, 徐寿伟, 李信诚, 王重洋, 徐景芝. 基于正交自适应鲸鱼优化的云计算任务调度[J]. 《计算机应用》唯一官方网站, 2022, 42(5): 1516-1523.
[6]	陈家豪, 殷新春. 基于云雾计算的可追踪可撤销密文策略属性基加密方案[J]. 计算机应用, 2021, 41(6): 1611-1620.
[7]	葛丽娜, 胡雨谷, 张桂芬, 陈园园. 云计算环境基于客体属性匹配的逆向混合访问控制方案[J]. 计算机应用, 2021, 41(6): 1604-1610.
[8]	杨翎, 姜春茂. 基于三支决策的虚拟机节能迁移策略[J]. 计算机应用, 2021, 41(4): 990-998.
[9]	孙晓玲, 杨光, 沈焱萍, 杨秋格, 陈涛. 基于可拆分倒排索引的可搜索加密方案[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3288-3294.
[10]	吕佳玉, 竺智荣, 姚志强. 云计算环境下的双通道数据动态加密策略[J]. 计算机应用, 2020, 40(8): 2268-2273.
[11]	郭曙杰, 李志华, 蔺凯青. 云环境下基于模糊隶属度的虚拟机放置算法[J]. 计算机应用, 2020, 40(5): 1374-1381.
[12]	陈程军, 毛莺池, 王绎超. 基于激活-熵的分层迭代剪枝策略的CNN模型压缩[J]. 计算机应用, 2020, 40(5): 1260-1265.
[13]	许英鑫, 孙磊, 赵建成, 郭松辉. 基于蚁群优化算法的虚拟现场可编程门阵列部署策略[J]. 计算机应用, 2020, 40(3): 747-752.
[14]	刘福鑫, 李劲巍, 王熠弘, 李琳. 基于Kubernetes的云原生海量数据存储系统设计与实现[J]. 《计算机应用》唯一官方网站, 2020, 40(2): 547-552.
[15]	王庆永, 毛莺池, 王绎超, 王龙宝. 基于多微云协作的计算任务卸载[J]. 《计算机应用》唯一官方网站, 2020, 40(2): 328-334.