Report ID
2009-10
Report Authors
Lili Cao, Lei Yang, Heather Zheng
Report Date
Abstract

Spectrum frequency allocation problems are fundamental problems in wireless spectrum auctions and wireless LAN management. Due to their complexity, most existing proposals simplify the allocation problems by reducing physical interference to a graph-based interference model. In this paper, we propose LIGHTHOUSE, a new line of efficient approximation algorithms that operate directly on physical interference models and perform within a constant bound from the optimum under geometric signal propagation. Our design is motivated by the fact that conventional greedy methods become brittle under physical interference models although they perform well under graph interference models. We overcome such brittleness by building a new globalized optimization path, first reducing the optimization constraints into linear constraints to produce a starting solution and then applying iterative improvements to approach the global optimum. To our best knowledge, our solution is the first to achieve a constant approximation bound. It also has low complexity and supports a wide-range of optimization goals. Experiments show that our solution outperforms existing solutions by 50+% in utilization, and is within 10% gap from the optimal solution.

Document
2009-10.pdf345.44 KB