Game-based Computing Resource Allocation And Optimization Algorithms And The Applications In Cloud/Edge Environment

With the advancement of social economy and science and technology,high computing demands and complex applications are driving the development of high-performance supercomputing systems.Due to the super-large scale,high reliability,versatility,and high scalability of cloud computing resources,cloud computing has been used as a business computing model to meet market needs and promote social technological progress.With the large-scale increase of mobile terminal electronic equipments and their high-quality demands,the concept of edge computing is proposed.Based on the nature of network function virtualization(NFV)and software-defined networking(SDN),edge computing sinks cloud computing capabilities and cloud storage capabilities to network edge nodes,reducing network operations and service delivery delays,thereby improving user service quality experience.In the cloud/edge environment,both users and providers hope to obtain maximum benefits.However,with the rapid increase in user scale and the diversity of user needs,the goal of maximizing benefits is even more difficult to achieve.The service characteristics of computing resources require that they continue to meet the increasingly diverse needs of users.A reasonable service mechanism can not only meet the needs of users for various tasks,but also maximize resource utilization and avoid resource waste and idleness.Game theory is the study of the mathematical model of conflict and cooperation between intelligent and rational decision-makers.It plays an increasingly important role in computer science,such as non-cooperative games and cooperative games.This paper focuses on the research of resource allocation problems based on game theory in the cloud/edge environment,and separately studies the problem of reasonable resource pricing by cloud providers in cloud computing resources,the problem of coalition resource procurement by multi-cloud users with Deadline-constrained in cloud computing,the problem that MEC with limited computing power allocates resources for users.The main work and innovations of this paper are as follows:(1)A Game-Based Price Bidding Algorithm for Multi-attribute Cloud Resource Provision.Aiming at the problem of multi-attribute resource purchase in cloud computing,a price bidding algorithm based on non-cooperative game about the profit maximization of cloud users and providers is proposed.Using the analytic hierarchy process to analyze the multi-attribute preferences of each user to finally determine providers' service quality,we propose a novel incentive resource purchase model about service quality and bidding.Then,combined with the user's resource purchase model,providers' price bidding problem is transformed into a game model to find an appropriate price for each cloud provider.In order to find the Nash equilibrium solution,we propose an equilibrium solution iteration(ESI)algorithm,which is proven to converge to the Nash equilibrium.Finally,we propose a near-equilibrium price bidding algorithm(NPB)to modify the obtained Nash equilibrium solution.(2)Coalition Formation for Deadline-constrained Resource Procurement in Cloud Computing.Aiming at the problem that a large number of cloud users cooperate to purchase cloud resources according to preferential policies of cloud providers to reduce their purchase costs,a heuristic deadline-constrained resource coalition allocation(DRCA)algorithm is proposed.A cooperative purchasing platform(CPP)is designed to receive user resource requests,then classify users that request the same resource type,calculate the users' cooperation plan,and finally feedback the cooperation result to users.A coalition game based on multi-customer resource procurement is established,which proves that there is a unique and optimal solution to satisfy individual stability and group stability.In addition,the best solution is a solution in which the selected service program of each coalition can optimize the cost of each customer and maximize resource utilization.A backtracking algorithm is proposed to calculate the pseudo-maximum resource utilization of the provided program by improving the matrix packing problem.Then,a heuristic deadline-constrained resource coalition allocation algorithm is proposed to calculate a near-optimal solution.(3)Game-based Task Offloading of Multiple Mobile Devices with Qo S in Mobile Edge Computing Systems.We study the problem of how to allocate limited computing resources to multiple devices to maximize the number of devices served by edge computing.We propose a computational task offloading(GCO)algorithm based on non-cooperative game.Greedy pruning algorithm is designed to determine the maximum number of devices that can offload tasks to the MEC with limited computing.At the same time,each device can compete for computing resources of mobile edge computing through its transmission power control strategy.The problem of task offloading of multiple devices is modeled as a non-cooperative game,and each player wants to maximize his own benefit.The existence of the Nash equilibrium solution of the proposed game model is proved,and the transmission power sequence solution obtained from the GCO algorithm converges to the equilibrium solution.(4)Applications of cloud/edge computing resource allocation algorithms in the field of intelligent transportation.On the basis of the cloud/edge computing resource allocation algorithm proposed in Chapters 3 to 5,we first discuss the demand and preference of cloud computing resources for different traffic video surveillance applications in the field of traffic big data,and use multi-attribute cloud computing resource bidding algorithm to allocates the optimal resource procurement plan for each application.Next,we discuss the time constraints and cost constraints of the traffic data analysis business of timeliness awareness,and use the cloud computing resource coalition procurement algorithm to purchase the lowest cost cloud computing resources that meet the constraints for each application.Finally,we discuss computing requirements of traffic data analysis services,and use edge computing task offloading algorithms to dynamically offload the computing load of mobile devices to the nearest edge node to improve business processing efficiency.