The Research Of Game Theoretic Grid Resources Scheduling Algorithms

Allocation and scheduling of grid resources is one of the essential technologies in grid computing. In resource-limited environment, grid users start game to contend limited resources, every user wants to win in the game of competing grid resources. How to guarantee users' rates of wins is the primary target for a grid resources scheduling system, because a higher users'rate of win makes the system more attractive and superb, maximizing both users'and resources'benefits and optimizing resources allocation and usage.In order to solve the scheduling problem, we present a model called Extended Second Price Sealed Auction (ESPSA) based on the conventional Second Price Sealed Auction. In the presented model, vast number of grid resources are auctioned in Second Price Sealed Auction, each user that is allowed to take part in the auction sends the bidding information to the resource broker, the information contains the total bidding price and the amount of demand for resources, at last the resource broker chooses the winner whose unit bidding is the highest and announces all the resource demand information. For the purpose of guaranteeing users' expected victory rates, we introduce the analysis entity, it can predict the users'next bidding price according to the information sent by users based on Hidden Makov Model (HMM).We do the experience based on the simulation toolkit-GridSim, the results show that the ESPSA we proposed has certain superiority in guaranteeing users'victory rates compared with some other traditional models, such as random bidding model, mean value bidding model. Finally, to illustrate the practicability of the ESPSA model, we not only analyze the existence of Nash Equilibrium according to the experiment results, but also prove the existence of Nash Equilibrium theoretically.