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

发布时间：2018-04-05 00:27

本文选题：云计算　切入点：任务调度算法　出处：《山东师范大学》2014年硕士论文

【摘要】：云计算是一种新的计算模式，它通过服务的形式为用户提供各种资源。云计算的正常运行离不开虚拟化技术。云计算中，利用虚拟化技术，将物理服务器的资源映射到虚拟机层，在一个服务器上部署多个虚拟机，利用虚拟机来执行用户任务，这样不但提高了服务器的资源利用率，同时保证了不同用户的应用程序的独立性。近年来，越来越多的企业架构了自己的云服务器，云计算系统需要有满足自身用户需要的资源分配和任务调度策略，目前还没有相关的任务调度标准。因此，对云计算环境下的任务调度算法研究具有重要的理论和现实意义。本文分析了云计算环境下的任务调度法算的研究现状，总结了云计算这一新兴商业模式的独有的特点，对现有调度算法存在的问题进行了深入分析，然后分别针对独立型和依赖型两类任务，提出了两种任务调度算法。此外，考虑了用户对云计算中心虚拟机资源的不同偏好性，针对多用户类，设计了多准则的任务调度算法。总体来说，本文主要完成了以下工作： ⑴针对云计算环境下的独立型任务，现有的调度方法一般包括遗传算法、蚁群算法、模拟退火算法等智能算法，，这些算法收敛的速度较快，但是容易陷入局部最优，并且算法过度依靠适应度函数的设计，算法复杂度较高。考虑到这类随机算法的劣势，我们从博弈论的角度分析云计算环境下的任务调度问题，设计了一个任务调度博弈模型，将所有用户任务作为博弈的参与者，所选择的虚拟机作为博弈策略，以任务处理时延作为博弈参与者的效用函数。找到了博弈的势函数，证明了博弈是一个势博弈，并且博弈存在Nash均衡，利用数学分析，证明了该博弈的稳定点就是势函数的最小值点。此外，提出了一种基于势博弈的任务调度算法，算法能够求解博弈到达稳定点时各个虚拟机上的任务量分布状态。仿真实验表明，该调度算法能降低任务的整体处理时延，并且能使系统的负载均衡程度自适应于用户任务量的变化，当任务量较少时，开启较少的虚拟机资源，减少系统的开销，当任务量较多时，开启较多的虚拟机资源，保证任务的QoS。此外，考虑了虚拟机的阈值限制，对所提算法进行了扩展，将虚拟机阈值限制这一参数加入到算法中，使得算法更具有一般性。 ⑵针对依赖型任务，分析了任务的DAG图，主要研究了Fork-Join型任务图，针对该类任务，基于网络博弈论中的Wardrop均衡原理，给出了以全体用户任务处理时延作为代价函数的博弈分析，考虑网络中全体用户任务，将求解全体用户的系统最优问题转化为求解单个用户的用户最优问题，设计了一个针对该任务的调度算法，该算法能够求解Wardrop均衡理论中的系统最优状态。最后，对此算法进行了仿真实验，实验表明，相比于单个用户最优的求解算法，该算法能够较快的完成用户任务，并且使整个云计算用户任务达到系统最优。 ⑶针对云计算用户任务对虚拟机资源具有不同的偏向性，对多用户类多准则的任务调度进行了研究。在云计算环境下，有些用户偏向于选择处理时延小的虚拟机资源，有些用户偏向于选择费用低的虚拟机资源，有些用户偏向于选择更加安全的虚拟机资源。根据用户的偏好性不同，将网络中的用户分为多类用户，只考虑费用和时间这两种指标，为这多类用户同时竞争虚拟机资源时设计了博弈模型，找到了博弈的势函数，证明了该博弈为一个势博弈，同时证明了博弈存在Nash均衡，并且Nash均衡与势函数的最大值等价。最后，提出了一种基于多用户类多准则的任务调度算法，求解博弈达到均衡时的各个虚拟机上任务量的状态分布。算法的仿真实验表明，所提算法具有收敛性，算法的求解结果与所有自私用户经过自由博弈后所得到的稳定状态是相同的，进一步说明了该算法的有效性及可行性。
[Abstract]:Cloud computing is a new computing mode, it is in the form of services to provide users with a variety of resources. The normal operation of cloud computing cannot do without virtualization. Cloud computing, the use of virtualization technology, the resource mapping of physical servers to virtual machine layer on a server to deploy multiple virtual machines. To perform user tasks using the virtual machine, it will not only improve the utilization of server resources, while ensuring the independence of the application of different users.
In recent years, more and more enterprise architecture its own cloud server, cloud computing system has to meet the need of resource allocation and task scheduling strategy to meet the needs of users, there is no task scheduling standards. Therefore, it has important theoretical and practical significance to the research of cloud computing task scheduling algorithm under the environment. This paper analyzes the research the status of task scheduling method in cloud computing environment is summarized, which is an emerging business model of the unique characteristics of cloud computing, on the existing scheduling problems in-depth analysis, and then according to the independent type and the dependent two kinds of task, put forward two kinds of task scheduling algorithms. In addition, taking into account the different the user preference of virtual machine resources on Cloud Computing Center, for many users, the task scheduling algorithm design standards. In general, this paper mainly completed the following work:
The independent task for cloud computing environment, the existing scheduling method generally includes genetic algorithm, ant colony algorithm, simulated annealing algorithm and other intelligent algorithms, the algorithm converges faster, but easy to fall into local optimum, and the algorithm is too dependent on the design of fitness function, the complexity of the algorithm is higher. Considering the stochastic algorithm the disadvantage, we analyze the problem of cloud computing task scheduling environment, designed a task scheduling game model, all user tasks as the player of the game, the selected virtual machine as the game strategy, the task of processing delay as a utility function of game participants. Find the potential function of the game that proves that the game is a potential game, and the game of the Nash equilibrium, using mathematical analysis, proved that the stable point of the game is the potential function of the minimum point in addition, Presents a task scheduling algorithm based on potential game, each virtual machine algorithm can solve the game task distribution reaches the stable point. Simulation results show that the overall processing delay of the scheduling algorithm can reduce task, and make changes in the load balance of the system is adaptive to the degree of user task amount, when the quantity of task less, less open virtual machine resources, reduce the cost of the system, when the task quantity is more and more open virtual machine resources, ensure the task of QoS. in addition, considering the threshold limit of the virtual machine, the proposed algorithm is extended to the virtual machine threshold limits the parameter added to the algorithm. The algorithm is more general.
For dependent tasks, task analysis DAG, mainly studies the Fork-Join task graph for this kind of task, Wardrop equilibrium principle of network game theory based on the given by the user task processing time delay as the game analysis of the cost function, considering all the users in the network, the optimal solution of all the user into a single user user optimal problem solving, a task scheduling algorithm for the system design, the algorithm can solve the Wardrop equilibrium theory in optimal state. Finally, this algorithm in the simulation experiment, experimental results show that the algorithm compared to the single user optimum, this algorithm can quickly complete the task of the user, and the users of cloud computing task to achieve optimal system.
According to the users of cloud computing tasks with different bias of virtual machine resources, task scheduling for multi user multi criterion is studied. In the cloud computing environment, some users tend to choose the processing resources of virtual machine small delay, some users tend to choose low cost virtual machine resources, some users tend to virtual machine resources to choose more safe. According to different user preferences, the network users are divided into many types of users, only consider the two indicators of cost and time, for the multi class user and virtual machine resources design competition game model, find the potential function of the game, the game is proved a potential game, and prove the existence of Nash equilibrium game, and the maximum value of the equivalent Nash equilibrium and potential function. Finally, put forward a task scheduling algorithm for multi user multi criterion based on solving the game reached The amount of task distribution on each virtual machine scale. Simulation results show that the algorithm, the proposed algorithm has convergence algorithm for solving steady state results and are all selfish users through free after the game is the same, and further illustrates the effectiveness and feasibility of the algorithm.

【学位授予单位】：山东师范大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP393.01

【引证文献】