Research On Grid Resource Allocation And Pricing Based On The Combinatorial Double Auction Model

Under the trend of intensified informatization, the research of the grid resource management becomes a top priority, as the utilization of the grid technology can create strong resource convergence. In recent years, the grid resource management based on economy/market mechanism becomes a hot topic for researches. As an importance branch of Economics theories, auction model is widely used for solving different kinds of resource allocation problem. As a new type of auction method, the combinatorial double auction possess the dual advantage of both combinatorial auction and double auction, its character of being "combinatorial" allows bidder to bid for different resource combination by volume and by type, its character of being "double" allows multiple seller and buyer to bid simultaneously, it breaks the monopoly enjoyed by sole seller/buyer for single auction, furthermore it can significantly reduce the amount of transaction. The combinatorial double auction is very applicable in resource allocation under grid environment, due to its nature of equality for transaction, variety for auction combination and high efficiency for resource allocation.Based on an in-depth analysis of the traditional combinatorial double auction, this paper presents several methods for winner determination for multiple combinatorial double auction, and algorithm for resource allocation and pricing seting. Focusing on four important parameters: social surplus, transaction ratio, time efficiency and specific environment adaptability, this paper improves and perfects the traditional mode, the below are the key findings of this paper:This paper introduces a multi-round combinatorial double auction with virtual seller. After the completion of traditional double auction, the winning selling market may have surplus from untraded resources. The value and the allocation of the surplus resources has not caught much attention from previous studies, nevertheless, our experiments prove that the number of surplus resources can not be ignored, thus the surplus resources have to be re-allocated and utilized. Our model introduces a mechanism for multi-round combinatorial double auction with virtual seller, utilizes surplus resources and improves the deficiency of single bid in tradition model. Our model assigns surplus resources from current bid to a virtual seller as a zero offer, however requires the assigned surplus resources be carried into next round bid. Due to the participation of the virtual seller, surplus resource will be re-allocated and converted into value(Money), and contributing the incremental on social surplus. The multi-round combinatorial double auction creates the conditions and can effectively improve the bid transaction ratio. As a pricing setting adjustment tactic in multi-round combinatorial double auction, this model designs a method for bidders to automatically adjust the bid once a reference price is identified. This method can ensure the bid price for every round will not exceed the reserved price set by the bidders. Simulation experiments results shows that the transactional mechanism under the model of multi-round can significantly boost the social surplus and transaction ratio, consequently, the virtual sells can convert the surplus resources into value, further enlarge the social surplus.This paper presents a proposal to win multi-round combinatorial double auction based on the transactional tactics. In the field of combinatorial auction, winner determination is the core problem which deserves lots of research attention because:this problem can determine the final bid winner; the speed of determination can directly affect the practicality of this auction model. Currently bid winner are mainly being determined by optimization model, there are two categories of algorithm under this model:Accurate mathematical algorithm and approximate algorithm. For large scale auction, accurate mathematical algorithm can not finish the calculation in polynomial time frame; approximate algorithm can complete the calculation, but can not guarantee the optimized result, thus a dilemma emerges. Considering the dilemma when applying optimization model to determine bid winner, this paper integrates WDP into the transaction tactics; presents proposals to determine the bid winner by the process of resource allocation and pricing setting, and gives detailed transaction algorithm. In terms of transaction path, this algorithm is similar to Marshallian Path of traditional double auction to utilize the social surplus. In terms of transaction method, it integrates the character of grid resource allocation. The algorithm allows sellers partially trade their bundles and the transaction path approximates to Marshallian Path. Comparing to current combinational double auction and pricing setting algorithm, this algorithm unifies the three steps of an auction:resource allocation, resource pricing setting and winner determination, it removes the negative utility during the pricing setting process. Results from simulation experiments show that because the adjustment on seller’s transaction model, this algorithm can generate much larger social surplus winner determination set than most optimized model. In large scale auction, this algorithm can complete the entire process of the combinational double auction with high efficiency, avoiding the difficulty of Non-Deterministic Polynomial for using the optimization model to determine winner.This paper presents the combination double auction model with time restraint, offers algorithm for resource allocation and pricing setting. This model is tailor made to the equipment grid regarding time restraint, descriptive information of bid, resource transaction method. To the contrary to computational grid where CPU, memory, bandwidth are shared, equipment grid involves resource which are mainly expensive and large equipment geographically scattered. Its resource allocation has two characters:first the sellers need to provide a stable supply in the time frame requested by the buyer, thus they can not continuously provide service by using its scattered and idle timing of its own. Second, partial resource of the buyer need to be provided by collective sellers at one spot; can not let numerous sellers to supply from scattered locations. Our model can fulfill very well for the above requirements, and it guarantees sells’scientific experiment to be accomplished in a few locations systematically in required time frame. For instance, simulation analyzed a micro-result from an auction; it straightforwardly presents the philosophy of this resource allocation and pricing setting algorithm, as well as sustains the character of the combination double auction:price competitiveness is no longer decisive in determining the result of bid. Price competitiveness is no long the only decisive factor in determine the winner of the bid and the effectiveness of transaction of the winner. The volume and type of resources, time attribute, the suitability of resources between buyers and sellers are all important factors in determining the bid result.