云计算中基于博弈论的任务调度算法研究

来源 :北京工业大学 | 被引量 : 7次 | 上传用户:amysyz
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
云计算是继分布式计算、并行计算、网格计算之后出现的一种基于互联网的、具有商业特性的新兴计算模式,它的出现推动了网络发展的新浪潮。云计算通过虚拟化技术,将大量的各种闲置资源进行整合,如物理资源、网络、数据、虚拟资源等,并通过互联网向用户按需求提供这些资源,同时用户可以根据自己的使用情况支付相应的费用,即实现了“按需付费”。它的服务形式主要有以下三种:基础设施即服务(IaaS)、平台即服务(PaaS)、软件即服务(SaaS),其中,IaaS是云计算服务的基石。随着云计算的概念及云计算产品的普及范围越来越广,云计算中的核心问题——任务调度问题也成为了社会各界研究的热点。由于云计算系统具有其特有的商业特性,因此它的任务调度问题相对于传统分布式系统的任务调度问题更加复杂。本文在分析了云计算的概念、特点和相关文献介绍之后,建立了云计算任务调度系统的简化模型,在该模型中只涉及到用户、调度器和计算节点。不同于以往的云计算任务调度算法的研究,本文的研究工作是以博弈论作为数学工具的。通过将简化的任务调度系统模型与博弈论相结合,提出了基于可靠性的均衡任务调度算法和基于序贯博弈的任务调度算法。在基于可靠性的均衡任务调度算法中,基于任务调度系统模型和计算节点的可靠性分析模型,建立了任务在计算节点上稳定状态的提供能力的数学模型,并在此基础上将云计算的任务调度问题建模为合作博弈问题。在合作博弈模型中,博弈的参与者是任务调度系统中的计算节点,博弈策略为任务在计算节点上的速率分配策略,博弈的效用函数为计算节点的稳定状态的提供能力。文中在分析了讨价还价解的存在性之后,给出了讨价还价解的结构,最后给出了任务调度算法,并通过实验及其实验结果分析,表明本算法具有较好的优化效果。在基于序贯博弈的任务调度算法中,基于任务调度系统模型和序贯博弈理论将任务调度问题建模为一个多阶段序贯博弈问题。基于序贯理性假设,博弈的参与者(调度器)根据上一次的博弈结果预测下一次博弈中用到的数据,不断调整自己的任务分片策略,以使其在每一个时间点的策略达到最优。文中在给出纳什均衡解的基础上,提出了任务调度算法,并通过实验对比证明本算法具有较好的优化效果。
其他文献
本文研究了模糊智能系统的建模过程,并结合模糊逻辑、神经网络和知识工程等理论和方法,提出了一种利用模糊知识建立智能系统的可行途径,并依照此思想设计和实现了基于模糊知识的