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

《云计算环境下基于网络博弈的任务调度算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、山东师范大学硕士学位论文攻读硕士学位期间发表的论文及参与的科研项目.........................59致谢...............................................................60III万方数据山东师范大学硕士学位论文摘要云计算是一种新的计算模式，它通过服务的形式为用户提供各种资源。云计算的正常运行离不开虚拟化技术。云计算中，利用虚拟化技术，将物理服务器的资源映射到虚拟机层，在一个服务器上部署多个虚拟机，利用虚拟机来执行用户任务，这样

2、不但提高了服务器的资源利用率，同时保证了不同用户的应用程序的独立性。近年来，越来越多的企业架构了自己的云服务器，云计算系统需要有满足自身用户需要的资源分配和任务调度策略，目前还没有相关的任务调度标准。因此，对云计算环境下的任务调度算法研究具有重要的理论和现实意义。本文分析了云计算环境下的任务调度法算的研究现状，总结了云计算这一新兴商业模式的独有的特点，对现有调度算法存在的问题进行了深入分析，然后分别针对独立型和依赖型两类任务，提出了两种任务调度算法。此外，考虑了用户对云计算中心虚拟机资源的不同偏好性，针对多

3、用户类，设计了多准则的任务调度算法。总体来说，本文主要完成了以下工作：⑴针对云计算环境下的独立型任务，现有的调度方法一般包括遗传算法、蚁群算法、模拟退火算法等智能算法，这些算法收敛的速度较快，但是容易陷入局部最优，并且算法过度依靠适应度函数的设计，算法复杂度较高。考虑到这类随机算法的劣势，我们从博弈论的角度分析云计算环境下的任务调度问题，设计了一个任务调度博弈模型，将所有用户任务作为博弈的参与者，所选择的虚拟机作为博弈策略，以任务处理时延作为博弈参与者的效用函数。找到了博弈的势函数，证明了博弈是一个势博弈，

4、并且博弈存在Nash均衡，利用数学分析，证明了该博弈的稳定点就是势函数的最小值点。此外，提出了一种基于势博弈的任务调度算法，算法能够求解博弈到达稳定点时各个虚拟机上的任务量分布状态。仿真实验表明，该调度算法能降低任务的整体处理时延，并且能使系统的负载均衡程度自适应于用户任务量的变化，当任务量较少时，开启较少的虚拟机资源，减少系统的开销，当任务量较多时，开启较多的虚拟机资源，保证任务的QoS。此外，考虑了虚拟机的阈值限制，对所提算法进行了扩展，将虚拟机阈值限制这一参数I万方数据山东师范大学硕士学位论文加入到算

5、法中，使得算法更具有一般性。⑵针对依赖型任务，分析了任务的DAG图，主要研究了Fork-Join型任务图，针对该类任务，基于网络博弈论中的Wardrop均衡原理，给出了以全体用户任务处理时延作为代价函数的博弈分析，考虑网络中全体用户任务，将求解全体用户的系统最优问题转化为求解单个用户的用户最优问题，设计了一个针对该任务的调度算法，该算法能够求解Wardrop均衡理论中的系统最优状态。最后，对此算法进行了仿真实验，实验表明，相比于单个用户最优的求解算法，该算法能够较快的完成用户任务，并且使整个云计算用户任务达

6、到系统最优。⑶针对云计算用户任务对虚拟机资源具有不同的偏向性，对多用户类多准则的任务调度进行了研究。在云计算环境下，有些用户偏向于选择处理时延小的虚拟机资源，有些用户偏向于选择费用低的虚拟机资源，有些用户偏向于选择更加安全的虚拟机资源。根据用户的偏好性不同，将网络中的用户分为多类用户，只考虑费用和时间这两种指标，为这多类用户同时竞争虚拟机资源时设计了博弈模型，找到了博弈的势函数，证明了该博弈为一个势博弈，同时证明了博弈存在Nash均衡，并且Nash均衡与势函数的最大值等价。最后，提出了一种基于多用户类多准则

7、的任务调度算法，求解博弈达到均衡时的各个虚拟机上任务量的状态分布。算法的仿真实验表明，所提算法具有收敛性，算法的求解结果与所有自私用户经过自由博弈后所得到的稳定状态是相同的，进一步说明了该算法的有效性及可行性。关键词：云计算；任务调度算法；网络博弈；任务依赖；势博弈分类号：TP393II万方数据山东师范大学硕士学位论文TaskSchedulingAlgorithmsBasedonNetworkGameinCloudComputingEnvironmentAbstractCloudcomputingisane

8、wcomputingmodel,whichprovidesavarietyofresourcesforusersthroughthemodeofservice.Cloudcomputing’snormaloperationisinseparablefromvirtualizationtechnology.Cloudcomputingmapstheresourcesofthephysicalservertoavir