基于纳什议价解的多目标合作博弈云任务调度
|
摘要
针对云任务调度优化问题,提出一种基于纳什议价解的多目标合作博弈调度算法NBS-EATS。基于纳什议价解NBS,将多约束条件下云任务调度形式化为合作博弈模型,模型以任务截止时间和任务结构需求为约束,将主机能耗与任务执行跨度Makespan同步最小化定义为多目标函数,通过求解模型NBS得到最优任务映射方案。数学分析结果表明,合作博弈是有解的,在求解产生Pareto最优解的NBS时,时间复杂度为O(nmlog(m))(n为任务数量,m为主机数量);仿真结果表明,与同类算法Greedy和LR相比,NBS-EATS算法在总体能耗和平均执行跨度上分别低24.4%、50.7%和22.8%、29.6%,验证了该算法的可行性。
Aiming at the optimization problem of cloud tasks shceduling,a multi-objective cooperative game scheduling algorithm NBS-EATS based on Nash bargaining solution was proposed.Cloud tasks scheduling problem with multi-constraint conditions was formalized as a cooperative game model based on Nash bargaining solution(NBS).This model defined task's deadline time and task's configuration requirement as constraints and defined the synchronization minimum of the energy consumption of host and task's execution makespan as the multi-objective function.An optimal task mapping strategy was got through solving NBS of the model.Mathematical analysis shows that cooperative game algorithm can produce Pareto optimal solution in the form of NBS with the time complexity of O(nmlog(m))(n is the number of tasks and m is the number of hosts).Results of simulation show that,compared with the same kind of greedy algorithm and linear relaxation(LR)algorithm,NBS-EATS is 24.4%,50.7% and 22.8%,29.6% lower in terms of reducing the overall energy consumption and the average execution makespan,which verifies the feasibility of the proposed algorithm.
Aiming at the optimization problem of cloud tasks shceduling,a multi-objective cooperative game scheduling algorithm NBS-EATS based on Nash bargaining solution was proposed.Cloud tasks scheduling problem with multi-constraint conditions was formalized as a cooperative game model based on Nash bargaining solution(NBS).This model defined task's deadline time and task's configuration requirement as constraints and defined the synchronization minimum of the energy consumption of host and task's execution makespan as the multi-objective function.An optimal task mapping strategy was got through solving NBS of the model.Mathematical analysis shows that cooperative game algorithm can produce Pareto optimal solution in the form of NBS with the time complexity of O(nmlog(m))(n is the number of tasks and m is the number of hosts).Results of simulation show that,compared with the same kind of greedy algorithm and linear relaxation(LR)algorithm,NBS-EATS is 24.4%,50.7% and 22.8%,29.6% lower in terms of reducing the overall energy consumption and the average execution makespan,which verifies the feasibility of the proposed algorithm.
引文
[1]TIAN Wenhong,ZHAO Yong.Cloud computing resource scheduling and management[M].Beijing:National Defense Industry Press,2011:35-45(in Chinese).[田文洪,赵勇.云计算资源调度管理[M].北京:国防工业出版社,2011:35-45.]
[2]XU Bo,ZHAO Chao,ZHU Yanjun,et al.Multi-objective scheduling optimization of virtual machine resource in cloud computing[J].Journal of System Simulation,2014,26(3):592-595(in Chinese).[许波,赵超,祝衍军,等.云计算中虚拟机资源调度多目标优化[J].系统仿真学报,2014,26(3):592-595.]
[3]GUO Lizheng,GENG Yongjun,JIANG Changyuan,et al.Multi-objective optimization based on particle swarm optimization algorithm in cloud computing[J].Computer Engineering and Design,2013,34(7):2358-2362(in Chinese).[郭力争,耿永军,姜长源,等.云计算环境下基于粒子群算法的多目标优化[J].计算机工程与设计,2013,34(7):2358-2362.]
[4]TIAN Suzhen,ZHAI Yumei,LIU Chuanling.Improvement research on multi-object service scheduling algorithm based on cloud computing[J].Journal of Shanxi University of Technology(National Science Edition),2012,28(1):24-29(in Chinese).[田素贞,翟玉梅,刘传领.基于云计算的多目标服务调度算法的改进研究[J].陕西理工学院学报(自然科学版),2012,28(1):24-29.]
[5]AI Haojun,GONG Suwen,YUAN Yuanming.Esearch of cloud computing virtual machine allocated strategy on multi-objective evoluationary algorithm[J].Computer Science,2014,41(6):48-53(in Chinese).[艾浩军,龚素文,袁远明.基于多目标演化算法的云计算虚拟机分配策略研究[J].计算机科学,2014,41(6):48-53.]
[6]XU Bo,CHEN Ke,ZHU Xingtong,et al.Virtual machine multi-objective placement algorithm based on optimization of energy consumption in the cloud computing[J].Journal of Chinese Computer Systems,2014,35(6):1304-1308(in Chinese).[许波,陈珂,朱兴统,等.云计算中基于能耗优化的虚拟机多目标放置算法[J].小型微型计算机系统,2014,35(6):1304-1308.]
[7]LIAO Daqiang.Multi-objective planning research of resource scheduling algorithm for cloud computing[J].Computer System Application,2016,25(2):180-189(in Chinese).[廖大强.面向多目标的云计算资源调度算法[J].计算机系统应用,2016,25(2):180-189.]
[8]XU Zhongsheng,SHEN Subin.A multi-objective optimization scheduling method in cloud computing[J].Microcomputer Its Application,2015,34(13):17-20(in Chinese).[徐忠胜,沈苏彬.一种云计算资源的多目标优化的调度方法[J].微型机与应用,2015,34(13):17-20.]
[9]GAO Yan,CHEN Xiaohui,REN Yongjun.MOJSP optimization algorithm based on approximateε-constraint in cloud computing platform[J].Application Research of Computers,2016,33(3):711-715(in Chinese).[高燕,陈小辉,任勇军.云计算平台下基于近似ε-约束的多目标作业调度优化算法[J].计算机应用研究,2016,33(3):711-715.]
[10]Guo L,Zhao S,Shen S,et al.Task scheduling optimization in cloud computing based on heuristic algorithm[J].Journal of Networks,2012,7(3):547-553.
[11]Ergu D,Kou G,Peng Y,et al.The analytic hierarchy process:Task scheduling and resource allocation in cloud computing environment[J].The Journal of Supercomputing,2013,64(3):835-848.
[12]Varia J.Best practices in architecting cloud applications in the AWS cloud[M].Cloud Computing:Principles and Paradigms,Eds.Wiley Press,2011:459-490.
[13]Genez T,Bittencourt L,Madeira E.On the performancecost tradeoff for workflow scheduling in hybrid clouds[C]//Proc of the 6th IEEE/ACM International Conference on Utility and Cloud Computing.Washington:IEEE Computer Socity,2013:411-416.
[14]Rusu C,Ferreira A,Scordino C.Energy-efficient real-time heterogeneours server clusters[C]//Proc Real-Time and Embedded Technology and Applications Symp.Washington:IEEE Computer Socity,2012:418-428.
[2]XU Bo,ZHAO Chao,ZHU Yanjun,et al.Multi-objective scheduling optimization of virtual machine resource in cloud computing[J].Journal of System Simulation,2014,26(3):592-595(in Chinese).[许波,赵超,祝衍军,等.云计算中虚拟机资源调度多目标优化[J].系统仿真学报,2014,26(3):592-595.]
[3]GUO Lizheng,GENG Yongjun,JIANG Changyuan,et al.Multi-objective optimization based on particle swarm optimization algorithm in cloud computing[J].Computer Engineering and Design,2013,34(7):2358-2362(in Chinese).[郭力争,耿永军,姜长源,等.云计算环境下基于粒子群算法的多目标优化[J].计算机工程与设计,2013,34(7):2358-2362.]
[4]TIAN Suzhen,ZHAI Yumei,LIU Chuanling.Improvement research on multi-object service scheduling algorithm based on cloud computing[J].Journal of Shanxi University of Technology(National Science Edition),2012,28(1):24-29(in Chinese).[田素贞,翟玉梅,刘传领.基于云计算的多目标服务调度算法的改进研究[J].陕西理工学院学报(自然科学版),2012,28(1):24-29.]
[5]AI Haojun,GONG Suwen,YUAN Yuanming.Esearch of cloud computing virtual machine allocated strategy on multi-objective evoluationary algorithm[J].Computer Science,2014,41(6):48-53(in Chinese).[艾浩军,龚素文,袁远明.基于多目标演化算法的云计算虚拟机分配策略研究[J].计算机科学,2014,41(6):48-53.]
[6]XU Bo,CHEN Ke,ZHU Xingtong,et al.Virtual machine multi-objective placement algorithm based on optimization of energy consumption in the cloud computing[J].Journal of Chinese Computer Systems,2014,35(6):1304-1308(in Chinese).[许波,陈珂,朱兴统,等.云计算中基于能耗优化的虚拟机多目标放置算法[J].小型微型计算机系统,2014,35(6):1304-1308.]
[7]LIAO Daqiang.Multi-objective planning research of resource scheduling algorithm for cloud computing[J].Computer System Application,2016,25(2):180-189(in Chinese).[廖大强.面向多目标的云计算资源调度算法[J].计算机系统应用,2016,25(2):180-189.]
[8]XU Zhongsheng,SHEN Subin.A multi-objective optimization scheduling method in cloud computing[J].Microcomputer Its Application,2015,34(13):17-20(in Chinese).[徐忠胜,沈苏彬.一种云计算资源的多目标优化的调度方法[J].微型机与应用,2015,34(13):17-20.]
[9]GAO Yan,CHEN Xiaohui,REN Yongjun.MOJSP optimization algorithm based on approximateε-constraint in cloud computing platform[J].Application Research of Computers,2016,33(3):711-715(in Chinese).[高燕,陈小辉,任勇军.云计算平台下基于近似ε-约束的多目标作业调度优化算法[J].计算机应用研究,2016,33(3):711-715.]
[10]Guo L,Zhao S,Shen S,et al.Task scheduling optimization in cloud computing based on heuristic algorithm[J].Journal of Networks,2012,7(3):547-553.
[11]Ergu D,Kou G,Peng Y,et al.The analytic hierarchy process:Task scheduling and resource allocation in cloud computing environment[J].The Journal of Supercomputing,2013,64(3):835-848.
[12]Varia J.Best practices in architecting cloud applications in the AWS cloud[M].Cloud Computing:Principles and Paradigms,Eds.Wiley Press,2011:459-490.
[13]Genez T,Bittencourt L,Madeira E.On the performancecost tradeoff for workflow scheduling in hybrid clouds[C]//Proc of the 6th IEEE/ACM International Conference on Utility and Cloud Computing.Washington:IEEE Computer Socity,2013:411-416.
[14]Rusu C,Ferreira A,Scordino C.Energy-efficient real-time heterogeneours server clusters[C]//Proc Real-Time and Embedded Technology and Applications Symp.Washington:IEEE Computer Socity,2012:418-428.