Wireless spectrum allocation by simulated annealing

Dynamic spectrum allocation shows great promise in increasing efficient spectrum usage in the face of growing wireless bandwidth demands, but satisfactory solutions to the practical problem of implementation have not yet been found. High utilization solutions have been proposed utilizing a central authority and hierarchical schemes but with high communications overhead and slow response to changing network demands. Heuristic solutions using only local information have also been proposed, but with much lower performance. This paper introduces a formulation of the problem using an annealed Metropolis Hastings algorithm that uses only local information and provably converges to the global optimum, albeit in exponential time. Despite the exponential time required for complete convergence, we show experimentally that it provides superior performance to the state of the art local heuristic solution in approximately the same number of iterations, with identical communication overhead.