你好,游客 登录 注册 发布搜索
背景:
阅读新闻

[硕士论文]云计算环境下基于网络博弈的任务调度算法

[日期:2014-08-08] 来源:山东师范大学  作者:李晓 [字体: ]

云计算环境下基于网络博弈的任务调度算法

山东师范大学 李晓

本文主要完成了以下工作:⑴针对云计算环境下的独立型任务,现有的调度方法一般包括遗传算法、蚁群算法、模拟退火算法等智能算法,这些算法收敛的速度较快,但是容易陷入局部最优,并且算法过度依靠适应度函数的设计,算法复杂度较高。考虑到这类随机算法的劣势,我们从博弈论的角度分析云计算环境下的任务调度问题,设计了一个任务调度博弈模型,将所有用户任务作为博弈的参与者,所选择的虚拟机作为博弈策略,以任务处理时延作为博弈参与者的效用函数。找到了博弈的势函数,证明了博弈是一个势博弈,并且博弈存在Nash均衡,利用数学分析,证明了该博弈的稳定点就是势函数的最小值点。此外,提出了一种基于势博弈的任务调度算法,算法能够求解博弈到达稳定点时各个虚拟机上的任务量分布状态。仿真实验表明,该调度算法能降低任务的整体处理时延,并且能使系统的负载均衡程度自适应于用户任务量的变化,当任务量较少时,开启较少的虚拟机资源,减少系统的开销,当任务量较多时,开启较多的虚拟机资源,保证任务的QoS。此外,考虑了虚拟机的阈值限制,对所提算法进行了扩展,将虚拟机阈值限制这一参数加入到算法中,使得算法更具有一般性。⑵针对依赖型任务,分析了任务的DAG图,主要研究了Fork-Join型任务图,针对该类任务,基于网络博弈论中的Wardrop均衡原理,给出了以全体用户任务处理时延作为代价函数的博弈分析,考虑网络中全体用户任务,将求解全体用户的系统最优问题转化为求解单个用户的用户最优问题,设计了一个针对该任务的调度算法,该算法能够求解Wardrop均衡理论中的系统最优状态。最后,对此算法进行了仿真实验,实验表明,相比于单个用户最优的求解算法,该算法能够较快的完成用户任务,并且使整个云计算用户任务达到系统最优。⑶针对云计算用户任务对虚拟机资源具有不同的偏向性,对多用户类多准则的任务调度进行了研究。在云计算环境下,有些用户偏向于选择处理时延小的虚拟机资源,有些用户偏向于选择费用低的虚拟机资源,有些用户偏向于选择更加安全的虚拟机资源。根据用户的偏好性不同,将网络中的用户分为多类用户,只考虑费用和时间这两种指标,为这多类用户同时竞争虚拟机资源时设计了博弈模型,找到了博弈的势函数,证明了该博弈为一个势博弈,同时证明了博弈存在Nash均衡,并且Nash均衡与势函数的最大值等价。最后,提出了一种基于多用户类多准则的任务调度算法,求解博弈达到均衡时的各个虚拟机上任务量的状态分布。


云计算环境下基于网络博弈的任务调度算法

收藏 推荐 打印 | 录入:574107552 | 阅读:
相关新闻       云计算 网络博弈 任务调度 
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数
点评:
       
评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款