The Research On Game Theoretical Methods For Profit Optimization Of Cloud Users

With the popularity of cloud computing and its many advantages,such as,cost-effectiveness,flexibility,and scalability,more and more user applications are moved from local to cloud data center.To satisfy the various of demands from cloud users,cloud providers are equipped with more and more servers,which results in a tremendous amounts of energy consumption.There-fore,how to optimize user utilities on limited computing resources is an important research problem.Actually,user utilities are closely related to the utility of a cloud provider.Specifi-cally,if users are dissatisfied with there obtained utility,they will refuse cloud service and just prefer to complete their tasks locally.This will lead to the reduce of number of cloud users and thus impacts the utility of a cloud provider.On the contrary,if users are satisfied with their utilities.They will pleased to frequently use cloud services.Furthermore,this will attract more cloud users in the market to use cloud service.In this thesis,we consider the utility optimiza-tion problems from cloud users view.We focus on the optimization from three aspects,which are request submitting strategy,resource bidding strategy,and performance guaranteed schedul-ing scheme.Under the different characteristics and objectives,we consider the problems from non-cooperative or cooperative game theoretic perspectives,and propose the corresponding op-timizing frameworks and algorithms,which realize simultaneous utility optimizations for all cloud users.In this thesis,we first focus on the strategy configurations of multiple users to make cloud service reservation.We consider the problem from a game theoretic perspective and formulate it into a non-cooperative game among the multiple cloud users,in which each user is informed with incomplete information of other users.For each user,we design a utility function which combines the net profit with time efficiency and try to maximize its value.We solve the problem by employing variational inequality(VI)theory and prove that there exists a Nash equilibrium solution set for the formulated game.Then,we propose an iterative proximal algorithm(IPA),which is designed to compute a Nash equilibrium solution.The convergence of the IPA algo-rithm is also analyzed and we find that it converges to a Nash equilibrium if several conditions are satisfied.Finally,we conduct some numerical calculations to verify our theoretical analysis.The experimental results show that our proposed IPA algorithm converges to a stable state very quickly and improves the utilities of all users to certain extent by configuring a proper request strategy.Next,we consider the scheduling of simple linear deteriorating jobs on parallel machines from a new perspective based on game theory.In scheduling,jobs are often controlled by independent and selfish agents,in which each agent tries to select a machine for processing that optimizes its own payoff while ignoring the others.We formalize this situation as a game in which the players are job owners,the strategies are machines,and a player~?s utility is inversely proportional to the total completion time of the machine selected by the agent.The price of anarchy is the ratio between the worst-case equilibrium makespan and the optimal makespan.In this paper,we design a game theoretic approximation algorithm A and prove that it converges to a pure-strategy Nash equilibrium in a linear number of rounds.We also derive the upper bound on the price of anarchy of A and further show that the ratio obtained by A is tight.Finally,we analyze the time complexity of the proposed algorithm.Then,we focus on price bidding strategies of multiple users competition for resource usage in cloud computing.We consider the problem from a game theoretic perspective and formulate it into a non-cooperative game among the multiple cloud users,in which each cloud user is informed with incomplete information of other users.For each user,we design a utility function which combines the net profit with time efficiency and try to maximize its value.We design a mechanism for the multiple users to evaluate their utilities and decide whether to use the cloud service.Furthermore,we propose a framework for each cloud user to compute an appropriate bidding price.At the beginning,by relaxing the condition that the allocated number of servers can be fractional,we prove the existence of Nash equilibrium solution set for the formulated game.Then,we propose a sequenced iterative algorithm(SIA),which is designed to compute a Nash equilibrium solution.The convergency of the proposed algorithm is also analyzed and we find that it converges to a Nash equilibrium if several conditions are satisfied.Finally,we revise the obtained solution and propose a near-equilibrium price bidding algorithm(NPBA)to characterize the whole process of our proposed framework.The experimental results show that the obtained near-equilibrium solution is close to the equilibrium one.Finally,we focus on request scheduling scheme with performance guarantees in cloud computing.We consider the problem from a game theoretic perspective and formulate it into a cooperative game among multiple cloud users.Each cloud user submits requests with per-formance requirement.The cloud provider tries to find a scheduling scheme,i.e.,allocating requests to multiple servers,such that the performance requirements of all cloud users are guar-anteed.We prove the existence of Nash bargaining solution for the formulated game and then analyze the computation for a Nash bargaining solution.For the situation when the allocating substream is strictly positive,we propose a computational algorithm(CA),which is very effi-cient.For more general case,we propose an iterative algorithm(IA),which is based on duality theory.The convergence of our proposed IA algorithm is also analyzed.Finally,we conduct some numerical calculations.The experimental results show that our proposed IA algorithm can find an appropriate scheduling strategy with performance guarantees and converges to a stable state very quickly.