负载敏感的云任务三支聚类评分调度研究
|
摘要
在云计算商业化的服务模式中,追求服务质量、负载均衡与经济原则的多目标优化调度。针对集群资源使用率偏低的现象,提出了三支聚类评分(three-way clustering weight,TWCW)算法,首先分析云任务的多样化需求与资源的动态特性,采用三支聚类算法对任务集合聚类划分,然后结合任务属性对类簇对象进行评分调度。基于Cloudsim实验模拟表明:相比于k-means与FCM聚类调度,三支聚类评分算法(TWCW)在任务平均响应时间与资源利用率等方面均有显著提升。
A commercialized model is established for multi-objective optimization scheduling of service quality, balanced load, and economic principles in cloud computing. A three-way clustering weight(TWCW) algorithm is proposed to solve the problem of the low utilization rate of cluster resources. First, the diversified requirements of cloud tasks and the dynamic characteristics of resources are analyzed to cluster and divide the task set by the TWCW algorithm and then score scheduling by combination with task attributes. Simulation results based on Cloudsim show that compared with k-means and FCM clustering scheduling, the TWCW algorithm has significant improvements in the average task response time and resource utilization rate.
A commercialized model is established for multi-objective optimization scheduling of service quality, balanced load, and economic principles in cloud computing. A three-way clustering weight(TWCW) algorithm is proposed to solve the problem of the low utilization rate of cluster resources. First, the diversified requirements of cloud tasks and the dynamic characteristics of resources are analyzed to cluster and divide the task set by the TWCW algorithm and then score scheduling by combination with task attributes. Simulation results based on Cloudsim show that compared with k-means and FCM clustering scheduling, the TWCW algorithm has significant improvements in the average task response time and resource utilization rate.
引文
[1] BOHRER P, ELNOZAHY E N, KELLER T,et al. The case for power management in web servers[M]//GRAYBILL R, MELHEM R. Power Aware Computing. Boston,MA, USA:Springer, 2002:261-289.
[2] BARROSO L A, HOLZLE U. The case for energy-proportional computing[J]. Computer, 2007, 40(12):33-37.
[3] REISS C, TUMANOV A, GANGER G R, et al. Heterogeneity and dynamicity of clouds at scale:Google trace analysis[C]//Proceedings of the third ACM Symposium on Cloud Computing. New York, NY, USA, 2012:1-13.
[4] LIU Zitao, CHO S. Characterizing machines and workloads on a Google cluster[C]//Proceedings of 2012 41st International Conference on Parallel Processing Workshops.Pittsburgh, PA, USA,2012:397-403.
[5]左利云.云计算中基于任务特性和资源约束的调度方法研究[D].广州:华南理工大学,2016:1-139.ZUO Liyun. The scheduling methods based on the task features and resource constraints in cloud computing[D].Guangzhou, China:South China University of Technology,2016:1-139.
[6]刘家志.模糊C-均值算法在任务调度问题上的应用[C]//第十届中国通信学会学术年会论文集.沈阳,中国,2014:310-313.LIU Jiazhi. Application of fuzzy c-means algorithm in task scheduling problem[C]//A Collection of Academic Annual Meetings of the Tenth China Communications Society.Shenyang, China, 2014:310-313.
[7]封良良,夏晓燕,贾振红,等.实验基于资源预先分类的云计算任务调度算法[J].计算机仿真,2013, 30(10):363-367, 410.FENG Liangliang, XIA Xiaoyan, JIA Zhenhong, et al.Task scheduling algorithm based on improved particle swarm optimization algorithm in cloud computing environment[J]. Computer simulation, 2013, 30(10):363-367, 410.
[8]张以利,杨万扣.云环境下基于任务分类和LPM优化模型的调度算法[J].微型电脑应用,2013, 29(10):5-8.ZHANG Yili, YANG Wankou. Scheduling algorithm based on task classifying and linear pogramming model in a cloud environment[J]. Microcomputer application, 2013,29(10):5-8.
[9]陈晶晶.云环境下基于非均匀粒度分类的任务调度算法研究[D].南京:南京邮电大学,2015:1-59.CHEN Jingjing. Research on task scheduling algorithm based on non-uniform granularity classification in cloud environment[D]. Nanjing, China:Nanjing University of Posts and Telecommunications, 2015:1-59.
[10]高正九,郑煌,辛波,等.基于任务分类的延迟调度算法[J].计算机系统应用,2014, 23(9):139-143.GAO Zhengjiu, ZHENG Quan, XIN Bo, et al. Delay scheduling algorithm based on task classification[J].Computer systemsand&applications, 2014, 23(9):139-143.
[11] YAO Yiyu. The superiority of three-way decisions in probabilistic rough set models[J]. Information sciences,2011, 181(6):1080-1096.
[12] YAO Yiyu. Three-way decisions with probabilistic rough sets[J]. Information sciences,2010, 180(3):341-353.
[13] YAO Yiyu. Three-way decision:an interpretation of rules in rough set theory[C]//Proceeding of the 4th International Conference Rough Sets and Knowledge Technology.Gold Coast, Australia, 2009:642-649.
[14] ZHOU Bing, YAO Yiyu, LUO Jigang. Cost-sensitive three-way email spam filtering[J]. Journal of intelligent information systems, 2014, 42(1):19-45.
[15] ZHANG Hengru, MIN Fan, HE Xu, et al. A hybrid recommender system based on user-recommender interaction[J]. Mathematical problems in engineering, 2015,2015:145636.
[16] YAO Jingtao, AZAM Nouman. Web-based medical decision support systems for three-way medical decision making with game-theoretic rough sets[J]. IEEE transactions on fuzzy systems, 2015, 23(1):3-15.
[17] QIAN Yuhua, ZHANG Hu, SANG Yanli, et al. Multigranulation decision-theoretic rough sets[J]. International journal of approximate reasoning, 2014, 55(1):225-237.
[18] LI Huaxiong, ZHOU Xianzhong, HUANG Bing, et al.Cost-sensitive three-way decision:a sequential strategy[M]//LINGRAS P, WOLSKI M, CORNELIS C,et al.Rough Sets and Knowledge Technology. Berlin, Germany:Springer, 2013:325-337.
[19] LIU Dun, LI Tianrui, LIANG Decui. Three-way decisions in dynamic decision-theoretic rough sets[M]//LINGRAS P, WOLSKI M, CORNELIS C, et al. Rough Sets and Knowledge Technology. Berlin, Germany:Springer,2013:291-301.
[20] SHE Yanhong. On determination of thresholds in threeway approximation of many-valued nm-logic[M]//CORNELIS C, KRYSZKIEWICZ M, SLEZAK D, et al.Rough sets and Current Trends in Computing. Cham,Germany:Springer, 2014:136-143.
[21]于洪.三支聚类分析[J].数码设计,2016, 5(1):31-35,30.YU Hong. Three-way cluster analysis[J]. Peak data science, 2016, 5(1):31-35,30.
[22]于洪,毛传凯.基于k-means的自动三支决策聚类方法[J].计算机应用,2016,36(8):2061-2065,2091.YU Hong, MAO Chuankai. Automatic three-way de-cision clustering algorithm based on k-means[J]. Journal of computer applications, 2016, 36(8):2061-2065, 2091.
[2] BARROSO L A, HOLZLE U. The case for energy-proportional computing[J]. Computer, 2007, 40(12):33-37.
[3] REISS C, TUMANOV A, GANGER G R, et al. Heterogeneity and dynamicity of clouds at scale:Google trace analysis[C]//Proceedings of the third ACM Symposium on Cloud Computing. New York, NY, USA, 2012:1-13.
[4] LIU Zitao, CHO S. Characterizing machines and workloads on a Google cluster[C]//Proceedings of 2012 41st International Conference on Parallel Processing Workshops.Pittsburgh, PA, USA,2012:397-403.
[5]左利云.云计算中基于任务特性和资源约束的调度方法研究[D].广州:华南理工大学,2016:1-139.ZUO Liyun. The scheduling methods based on the task features and resource constraints in cloud computing[D].Guangzhou, China:South China University of Technology,2016:1-139.
[6]刘家志.模糊C-均值算法在任务调度问题上的应用[C]//第十届中国通信学会学术年会论文集.沈阳,中国,2014:310-313.LIU Jiazhi. Application of fuzzy c-means algorithm in task scheduling problem[C]//A Collection of Academic Annual Meetings of the Tenth China Communications Society.Shenyang, China, 2014:310-313.
[7]封良良,夏晓燕,贾振红,等.实验基于资源预先分类的云计算任务调度算法[J].计算机仿真,2013, 30(10):363-367, 410.FENG Liangliang, XIA Xiaoyan, JIA Zhenhong, et al.Task scheduling algorithm based on improved particle swarm optimization algorithm in cloud computing environment[J]. Computer simulation, 2013, 30(10):363-367, 410.
[8]张以利,杨万扣.云环境下基于任务分类和LPM优化模型的调度算法[J].微型电脑应用,2013, 29(10):5-8.ZHANG Yili, YANG Wankou. Scheduling algorithm based on task classifying and linear pogramming model in a cloud environment[J]. Microcomputer application, 2013,29(10):5-8.
[9]陈晶晶.云环境下基于非均匀粒度分类的任务调度算法研究[D].南京:南京邮电大学,2015:1-59.CHEN Jingjing. Research on task scheduling algorithm based on non-uniform granularity classification in cloud environment[D]. Nanjing, China:Nanjing University of Posts and Telecommunications, 2015:1-59.
[10]高正九,郑煌,辛波,等.基于任务分类的延迟调度算法[J].计算机系统应用,2014, 23(9):139-143.GAO Zhengjiu, ZHENG Quan, XIN Bo, et al. Delay scheduling algorithm based on task classification[J].Computer systemsand&applications, 2014, 23(9):139-143.
[11] YAO Yiyu. The superiority of three-way decisions in probabilistic rough set models[J]. Information sciences,2011, 181(6):1080-1096.
[12] YAO Yiyu. Three-way decisions with probabilistic rough sets[J]. Information sciences,2010, 180(3):341-353.
[13] YAO Yiyu. Three-way decision:an interpretation of rules in rough set theory[C]//Proceeding of the 4th International Conference Rough Sets and Knowledge Technology.Gold Coast, Australia, 2009:642-649.
[14] ZHOU Bing, YAO Yiyu, LUO Jigang. Cost-sensitive three-way email spam filtering[J]. Journal of intelligent information systems, 2014, 42(1):19-45.
[15] ZHANG Hengru, MIN Fan, HE Xu, et al. A hybrid recommender system based on user-recommender interaction[J]. Mathematical problems in engineering, 2015,2015:145636.
[16] YAO Jingtao, AZAM Nouman. Web-based medical decision support systems for three-way medical decision making with game-theoretic rough sets[J]. IEEE transactions on fuzzy systems, 2015, 23(1):3-15.
[17] QIAN Yuhua, ZHANG Hu, SANG Yanli, et al. Multigranulation decision-theoretic rough sets[J]. International journal of approximate reasoning, 2014, 55(1):225-237.
[18] LI Huaxiong, ZHOU Xianzhong, HUANG Bing, et al.Cost-sensitive three-way decision:a sequential strategy[M]//LINGRAS P, WOLSKI M, CORNELIS C,et al.Rough Sets and Knowledge Technology. Berlin, Germany:Springer, 2013:325-337.
[19] LIU Dun, LI Tianrui, LIANG Decui. Three-way decisions in dynamic decision-theoretic rough sets[M]//LINGRAS P, WOLSKI M, CORNELIS C, et al. Rough Sets and Knowledge Technology. Berlin, Germany:Springer,2013:291-301.
[20] SHE Yanhong. On determination of thresholds in threeway approximation of many-valued nm-logic[M]//CORNELIS C, KRYSZKIEWICZ M, SLEZAK D, et al.Rough sets and Current Trends in Computing. Cham,Germany:Springer, 2014:136-143.
[21]于洪.三支聚类分析[J].数码设计,2016, 5(1):31-35,30.YU Hong. Three-way cluster analysis[J]. Peak data science, 2016, 5(1):31-35,30.
[22]于洪,毛传凯.基于k-means的自动三支决策聚类方法[J].计算机应用,2016,36(8):2061-2065,2091.YU Hong, MAO Chuankai. Automatic three-way de-cision clustering algorithm based on k-means[J]. Journal of computer applications, 2016, 36(8):2061-2065, 2091.