Please wait a minute...
浙江大学学报(工学版)
服务计算     
基于二次聚类的多目标混合云任务调度算法
李建丽, 丁丁, 李涛
北京交通大学 交通数据分析与挖掘北京市重点实验室,北京 100044
Multi-objective hybrid cloud task scheduling using twice clustering
LI Jian-li, DING Ding, LI Tao
Beijing Key Lab of Traffic Data Analysis and Mining, Beijing Jiaotong University, Beijing 100044, China
 全文: PDF(1153 KB)   HTML
摘要:

针对混合云环境包含大量异构云计算节点的情况,提出二次聚类方法,依据资源的综合特性,将异构资源进行分簇,将任务分发到合适的资源聚类,缩小任务搜索空间.在此基础上,结合私有云的安全可靠性、公有云的可扩展性以及用户需求的多样性,提出混合云环境下多目标优化的任务调度算法.该算法首先在私有云优先调度截止时间短的任务,对于每个聚类,将任务分配给完成时间最接近于其结束时间的资源,以完成更多的任务;将溢出的高负载任务转移到公有云聚类执行,结合任务的计算成本、通信开销和截止时间的约束,选择费用最低的资源.实验结果表明,与传统无聚类的算法相比,该算法降低了执行费用,同时提高了资源利用率和用户满意度.

Abstract: A twice clustering method was introduced aiming at the case that hybrid cloud environment contains a large number of heterogeneous computing nodes. This method reduced task search space through clustering the heterogeneous resources based on the synthetic characteristics of resources and splitting tasks to the appropriate cluster resources. On this basis, multi-objective task scheduling algorithm in hybrid cloud was proposed, combined with the security and reliability of the private cloud, the scalability of the public cloud and the diversity of user requirements. Firstly, the earliest deadline first algorithm was used in private cloud. To accomplish more tasks, the task was assigned to resource whose completing time was closest to the deadline for each cluster. Then, the public cloud handled the overloading tasks, which would choose the lowest-cost resource under the constraint of computing budget, communication cost and the deadline. Simulation results confirm that the proposed algorithm performs better in lower cost, better resource utilization and greater user satisfaction, compared to the traditional algorithm without clustering.
出版日期: 2017-06-11
CLC:  TP 393  
基金资助:

国家自然科学基金资助项目(61300176);中央高校基本科研基金资助项目(2016JBM019).

通讯作者: 丁丁,女,副教授. ORCID: 0000-0002-4108-3418.     E-mail: dding@bjtu.edu.cn
作者简介: 李建丽(1990—),女,硕士生,从事云计算、计算机并行处理研究. ORCID: 0000-0003-3760-7853. E-mail:14120399@bjtu.edu.cn
服务  
把本文推荐给朋友
加入引用管理器
E-mail Alert
作者相关文章  

引用本文:

李建丽, 丁丁, 李涛. 基于二次聚类的多目标混合云任务调度算法[J]. 浙江大学学报(工学版), 10.3785/j.issn.1008-973X.2017.06.022.

LI Jian-li, DING Ding, LI Tao. Multi-objective hybrid cloud task scheduling using twice clustering. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 10.3785/j.issn.1008-973X.2017.06.022.

参考文献(References):
[1] BUYYA R, YEO C S, VENUGOPAL S, et al. Cloud computing and emerging IT platforms: vision, hype, and reality for delivering computing as the 5th utility [J]. Future Generation Computer Systems, 2009, 25(6): 599-616.
[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] 刘鹏.云计算:第3版[M].北京:电子工业出版社,2015: 1-8.
[4] DILLON T, WU C, CHANG E. Cloud computing: issues and challenges [C]∥ IEEE International Conference on Advanced Information Networking and Applications. Perth: IEEE, 2010: 27-33.
[5] SINGH S, CHANA I. A survey on resource scheduling in cloud computing: issues and challenges [J]. Journal of Grid Computing, 2016, 14(2): 217-264.
[6] BITTENCOURT L F, MADEIRA E R M, DA FONSECA N L S. Scheduling in hybrid clouds [J].IEEE Communications Magazine, 2012, 50(9): 42-47.
[7] CHOPRA N, SINGH S. Deadline and cost based workflow scheduling in hybrid cloud [C]∥ 2013 International Conference on Advances in Computing, Communications and Informatics (ICACCI). Mysore: IEEE, 2013: 840-846.
[8] 云计算趋势:DevOps、 Docker、混合云将有大的进步.(2016-04-13)[2016-04-13].http:∥www.chinacloud.cn/show.aspx?id=23234&cid=14.
[9] VASILE M A, POP F, TUTUEANU R I, et al. Resource-aware hybrid scheduling algorithm in heterogeneous distributed computing [J]. Future Generation Computer Systems, 2015, 51(C): 61-71.
[10] JENNINGS B, STADLER R. Resource management in clouds: survey and research challenges [J]. Journal of Network and Systems Management, 2015, 23(3):567-619.
[11] SHIFRIN M, ATAR R, CIDON I. Optimal scheduling in the hybrid-cloud [C] ∥IFIP/IEEE International Symposium on Integrated Network Management. Ghent: IEEE, 2013: 51-59.
[12] VAN DEN BOSSCHE R, VANMECHELEN K, BROECKHOVE J. Cost-optimal scheduling in hybrid iaas clouds for deadline constrained workloads [C] ∥ 2010 IEEE 3rd International Conference on Cloud Computing (CLOUD). Miami: IEEE, 2010: 228-235.
[13] WANG W J, CHANG Y S, LO W T, et al. Adaptive scheduling for parallel tasks with QoS satisfaction for hybrid cloud environments [J]. The Journal of Supercomputing, 2013, 66 (2): 783-811.
[14] SINGH S, CHANA I. QRSF: QoS-aware resource scheduling framework in cloud computing [J]. The Journal of Supercomputing, 2015, 71(1): 241-292.
[15] 张敏,于剑.基于划分的模糊聚类算法[J].软件学报,2004,15(6): 858-868.
ZHANG Min, YU Jian. Fuzzy partitional clustering algorithms [J]. Journal of Software, 2004, 15(6): 858-868.
[16] 杜晓丽,蒋昌俊,徐国荣,等.一种基于模糊聚类的网格DAG任务图调度算法[J].软件学报,2006,17(11): 2277-2288.
DU Xiao-li, JIANG Chang-jian, XU Guo-rong, et al. A Grid DAG scheduling algorithm based on fuzzy clustering [J]. Journal of Software, 2006, 17(11): 2277-2288.
[17] 陈志刚,杨博.网格服务资源多维性能聚类任务调度[J].软件学报,2009,20(10): 2766-2775.
CHEN Zhi-Gang,YANG Bo. Task scheduling based on multidimensional performance clustering of grid service resources [J]. Journal of Software, 2009, 20(10): 2766-2775.
[18] 李文娟,张启飞,平玲娣,等.基于模糊聚类的云任务调度算法[J].通信学报,2012,33(3): 146-154.
LI Wen-juan,ZHANG Qi-fei, PING Ling-di,et al. Cloud scheduling algorithm based on fuzzy clustering [J]. Journal of China Institute of Communications, 2012, 33(3): 146-154.
[19] LI W J,WU J Y,ZHANG Q F,et al. Trust-driven and QoS demand clustering analysis based cloud workflow scheduling strategies [J]. Cluster computing, 2014,17(3): 1013-1030.
[20] 江务学,魏文国,丁度坤,等.异构云环境下基于分簇的云资源感知任务调度方案[J].计算机应用研究,2016,33(11): 3422-3425.
JIANG Wu-xue,WEI Wen-guo,DING Du-kun,et al. Task scheduling scheme based on clustering in heterogeneous cloud computing platform [J]. Application Research of Computers,2016,33(11): 3422-3425.
[21] LIU Z, QU W, LIU W, et al. Resource preprocessing and optimal task scheduling in cloud computing environments [J]. Concurrency and Computation: Practice and Experience, 2015, 27(13): 3461-3482.
[1] 张伊璇,龚俭. 基于DNS流量的多层多域名检测与测量[J]. 浙江大学学报(工学版), 2020, 54(12): 2423-2429.
[2] 成海秀,李冠霖,张凌. 基于时间槽的可降带宽核心网视频业务动态资源预约算法[J]. 浙江大学学报(工学版), 2020, 54(9): 1746-1752.
[3] 李冬,鲁喻,于俊清. 软件定义网络中源地址验证绑定表安全[J]. 浙江大学学报(工学版), 2020, 54(8): 1543-1549.
[4] 武秋韵,丁伟. 基于动态暗网的互联网扫描行为分析[J]. 浙江大学学报(工学版), 2020, 54(8): 1550-1556.
[5] 齐平,束红. 智慧医疗场景下考虑终端移动性的任务卸载策略[J]. 浙江大学学报(工学版), 2020, 54(6): 1126-1137.
[6] 罗逸涵,程杰仁,唐湘滟,欧明望,王天. 基于自适应阈值的DDoS攻击态势预警模型[J]. 浙江大学学报(工学版), 2020, 54(4): 704-711.
[7] 陈蔚,刘雪娇,夏莹杰. 基于层次分析法的车联网多因素信誉评价模型[J]. 浙江大学学报(工学版), 2020, 54(4): 722-731.
[8] 游录金, 卢兴见, 何高奇. 云环境亚健康研究[J]. 浙江大学学报(工学版), 2017, 51(6): 1181-1189.
[9] 张欣欣, 徐恪, 钟宜峰, 苏辉. 网络服务提供商合作行为的演化博弈分析[J]. 浙江大学学报(工学版), 2017, 51(6): 1214-1224.
[10] 王钰翔, 李晟洁, 王皓, 马钧轶, 王亚沙, 张大庆. 基于Wi-Fi的非接触式行为识别研究综述[J]. 浙江大学学报(工学版), 2017, 51(4): 648-654.
[11] 钱良芳, 张森林, 刘妹琴. 基于预约的数据队列水下无线传感器网络MAC协议[J]. 浙江大学学报(工学版), 2017, 51(4): 691-696.
[12] 李晓东, 祝跃飞, 刘胜利, 肖睿卿. 基于权限的Android应用程序安全审计方法[J]. 浙江大学学报(工学版), 2017, 51(3): 590-597.
[13] 黄焱, 王鹏, 谢高辉, 安俊秀. 智能电网下数据中心能耗费用优化综述[J]. 浙江大学学报(工学版), 2016, 50(12): 2386-2399.
[14] 余洋,夏春和,原志超,李忠. 计算机网络协同防御系统信任启动模型[J]. 浙江大学学报(工学版), 2016, 50(9): 1684-1694.
[15] 齐平, 李龙澍, 李学俊. 具有失效恢复机制的云资源调度算法[J]. 浙江大学学报(工学版), 2015, 49(12): 2305-2315.