Research On Task Scheduling Algorithm Based On Game Theory In Cloud Computing

Cloud computing with commercial properties is a new computing model based onInternet after distributed computing, parallel computing and grid computing. Itsemergence promotes the development of the network. Cloud computing integrates alarge variety of idle resources, such as physical resources, network, data, virtualresources and so on, through virtualization technology. Users can use these resourceson demands through the Internet. The main service form of cloud computing includesInfrastructure as a Service (IaaS), Platform as a Service (PaaS) and Software as aService (SaaS). IaaS is the cornerstone of cloud computing.With the concept and products of cloud computing ranging more widely, the coreissue of cloud computing-task scheduling has become a hot research in all sectors ofsociety. As cloud computing has its unique business characteristics, its task schedulingis more complex than the problem of traditional distributed systems. In this paper,after analyzing the concept, characteristics and related literatures of cloud computing,we proposed a simplified model of task scheduling system in cloud computing. Thismodel only contains users, schedulers and computing nodes. Unlike previous studiesof task scheduling algorithm in cloud computing, this paper used game theory as amathematical tool. By combining simplified task scheduling system and game theory,we proposed a balancing task scheduling algorithm based on reliability and a taskscheduling algorithm based on sequential game.In the balancing task scheduling algorithm based on reliability, we built the model ofcomputing nodes’ ability under steady state on the basis of task scheduling systemmodel and computing nodes’ reliability model. And on this basis, we built thecooperative game model in task scheduling. In this cooperative game model,participants are computing nodes, game strategy is the allocation strategy of task rateon computing nodes, utility function is the ability that computing nodes can provideunder steady state. After analyzing the existence of bargaining solution, we gave thestructure of bargaining solution and task scheduling algorithm. At last, we proved the algorithm had better optimization results through experiments.About the task scheduling algorithm based on sequential game, we modeled theproblem as a multi-stage sequential game on the basis of task scheduling systemmodel and sequential game theory. Based on sequential rational assumption, gameplayers chose their data that to use next stage and adjusted their strategies accordingto the previous results. Their strategies were optimal at each time point. We proposedthe task scheduling algorithm after giving the Nash equilibrium. At last we proved thealgorithm had a better optimization results through experiments.