Research On Cloud Resource Allocation Mechanism Based On Auction Theory And Heuristic Algorithm

Following distributed computing,grid computing,and peer-to-peer computing,cloud computing is a new computing model that provides services over the Internet.Its main features are on-demand use,expansion at any time,and pay-per-use.A cloud provider configures the underlying computing resources(CPU,memory,storage,etc.)into different types of Virtual Machine(VM)instances and provides computing resources to cloud users in the form of VM instances.However,the massiveness,heterogeneity,and dynamic nature of cloud computing resources make cloud computing resource allocation more complex.How to allocate cloud computing resources to cloud users reasonably and effectively to maximize social welfare has become a hotspot and difficulty in the cloud computing research.Many cloud providers use fixed-price based mechanisms to allocate cloud resources,but these mechanisms belong to static pricing mechanisms,thus they are economically ineffective.On the contrary,auction-based cloud resource allocation mechanisms are economically effi-cient and belong to dynamic pricing mechanisms.It can dynamically create equilibrium market prices based on resource supply and demand,cope with diverse and conflicting interests of participants and enable participants to make independent decisions.In addition,in the auction-based cloud resource allocation mechanisms,the Winner Determination Problem(WDP)is usu-ally a NP-hard problem with high computational complexity.Heuristic algorithms have the characteristics of being intuitive,simple,and fast,and it can obtain satisfactory solutions within a reasonable time range when dealing with large-scale problem instances.Therefore,heuristic algorithms are used to solve the WDP in the cloud resource allocation process.For IaaS(Infrastructure as a Service)type services,this dissertation focuses on the appli-cation of auction theory in the field of cloud resource allocation,introduces reverse auctions,combinatorial auctions,combinatorial double auctions,and group-buying auctions into cloud resource allocation according to different application scenarios,and designs three heuristic al-gorithms(greedy heuristic algorithm,multi-objective particle swarm optimization algorithm,and adaptive differential evolution algorithm)to solve WDP in cloud resource allocation pro-cess,in order to achieve better effect of resource allocation.The main research content of this dissertation is as follows:Multi-attribute reverse Vickrey auction based cloud resource allocation mechanism.In the cloud market,when cloud users purchase cloud computing resources to complete tasks,they cannot fully understand the reliability of cloud providers.In order to solve this problem,the reliability of various attributes of cloud providers(the reliability of the amount of cloud re-sources provided and the reliability of the Quality of Service(QoS)values provided)is consid-ered,and a novel reputation scheme to calculate the comprehensive reputation of cloud provid-ers is designed.In order to help cloud providers fully realize their respective competitive ad-vantages and fully satisfy the diverse personalized needs of cloud users,a Multi-Attribute Re-verse Vickrey Auction based Cloud Resource Allocation(MARVA-CRA)mechanism is de-signed.When determining the winning cloud provider,the mechanism considers not only the price attribute,but also non-price attributes,such as the amount of cloud resources provided,QoS indicators(e.g.,response time,availability)and cloud provider's comprehensive reputa-tion.Thus,cloud users comprehensively evaluate the cloud providers' multiple attributes to determine the winning cloud providers.At the same time,it is also considered that the actual amount of computing resources and QoS indicators provided by cloud providers may not be consistent with the promised.In order to compensate for the cloud user's loss caused by the cloud provider's default,a penalty mechanism is proposed to reduce the amount paid to the cloud provider so as to ensure that the utility of the cloud user is not lost.Experimental results show that the proposed reputation scheme can effectively determine the reliability of cloud providers.MARVA-CRA mechanism not only ensures that the cloud provider provides a truth-ful bid,but also effectively prevents the cloud user's utility from being lost due to the cloud provider's default.Combinatorial auction-based cloud resource allocation mechanism.There exists the fol-lowing deficiencies in the existing combinatorial auction-based cloud resource allocation mech-anism.(1)The cloud provider does not consider the actual needs of cloud users,and predefines the types of VM instances provided and the number of corresponding types of VM instances,resulting in the cloud provider's resource utilization is low.(2)The existing greedy heuristic algorithm based allocation mechanism does not reasonably deal with the huge differences in resource composition and price of heterogeneous VM instances when calculating the bid den-sity,resulting in poor performance of the resource allocation mechanism.(3)In the process of resource allocation and pricing,the reservation prices of VM instances are ignored,which may cause the utility of cloud providers to decline.To solve the aforementioned problems are pro-posed,two cloud resource allocation mechanisms based on combinatorial auctions,which are Vickrey-Clarke-Groves based cloud resource allocation mechanism(VCG-CRA)and greedy heuristic algorithm based cloud resource allocation(GHA-CRA)mechanism.Experimental re-sults show that the VCG-CRA mechanism can achieve the maximum social welfare,but its time complexity is high and it is not suitable for practical application scenarios.GHA-CRA not only ensures that the social welfare obtained are very close to the social welfare obtained by the VCG-CRA mechanism,but also has a very short execution time.Combinatorial double auction-based and reputation-aware cloud resource allocation mechanism.In order to create a healthy cloud market environment,not only to maximize the social welfare,but also to encourage the integrity of participants,a combinatorial doable auc-tion-based and reputation-aware cloud resource allocation(CDARA-CRA)mechanism is pro-posed.In order to solve the problem of dishonest transaction behavior due to information asym-metry between participants,a reputation scheme is first designed to calculate the credibility of the participants in this mechanism.Then,a price predicting algorithm based on random forest is designed to obtain a reasonable cloud user's bidding price and cloud provider's asking price.On this basis,the cloud resource allocation problem is formulated as a multi-objective optimi-zation problem that not only considers two conflicting objectives(maximizing social benefits and maximizing total expected reputation),but also allows a cloud user's request can be satis-fied by one cloud provider alone or multiple cloud providers.Finally,in order to solve the WDP in the mechanism,a winner determination mechanism based on modified multi-objective par-ticle swarm optimization algorithm is designed to obtain the optimal Pareto solution set of the problem.And then,the mechanism uses the TOPSIS(Technique for Order Performance by Similarity to Ideal Solution)method to choose the best compromise solution.The experimental results show that the mechanism is feasible and effective,improving not only the social welfare,but also the total expectation reputation.Group-buying auction-based dynamic cloud resource provisioning and allocation.In order to enable cloud providers to aggregate more cloud user needs and benefit from it,and enable cloud users to purchase the required cloud computing resources at a lower price than when they purchased them separately,a group-buying auction-based dynamic cloud resource provisioning and allocation(GBA-DCRPA)mechanism is proposed.The mechanism does not require cloud providers to pre-configure various types of VM instances,and allows cloud providers to dy-namically configure various types of VM instances based on the actual needs of cloud users.In order to make the mechanism more suitable for the actual cloud environment,the mechanism considers that there are multiple cloud providers in the cloud market that support the group-buying strategy,and allows the cloud user's demand to be satisfied by one cloud provider alone or multiple cloud providers together.In addition,in order to solve the WDP in this mechanism,a winner determination mechanism based on an adaptive differential evolution algorithm is proposed to obtain an approximate optimal solution to the problem.The experimental results show that this mechanism can promote social welfare,improve the cloud provider's resource utilization,and improve the number of completed tasks.