Distributed resource allocation using multi-linked bargaining markets.

摘要

The primary focus of this dissertation is the development of a distributed resource allocation method for large-scale systems. This dissertation consists of three parts. First, it develops a resource allocation model based on multi-linked bargaining markets. This model explicitly considers resource interactions through the use of non-separable utilities. The market consists of randomly matched buyers and sellers engaged in exclusive pairwise bargaining episodes. Sets of bargaining strategies are constructed and a distributed fixed point method is developed that allows efficient computation of the solution. This research proves that the proposed fixed point method converges to a unique solution and the underlying bargaining game is subgame perfect, resulting in an efficient allocation of resources when the market equilibrium is reached.; Second, a distributed scientific computational infrastructure is developed for large-scale numerical experimentation and simulation. This environment is designed to simultaneously support the numerical computation of the distributed resource allocation model and the simulation of large resource allocation problems. This system is designed to work with grid and computational cluster resources using existing middleware. Scaling and performance properties of the infrastructure are studied for a variety of problem sizes.; Finally, the resource allocation model is implemented on the distributed computational environment to study a large-scale sensor network problem, which is motivated by a real world application. The sensor network problem is used to highlight the need to provide a provably "good" solution within the "real-time" constraints.