Near-optimal dynamic spectrum allocation in cellular networks

In this paper, we address the spectrum allocation problem in cellular networks under the coordinated dynamic spectrum access (CDSA) model. In this model, a centralized spectrum broker owns a part of the spectrum and issues dynamic spectrum leases to competing base stations in the region it controls. We consider a dynamic auction based approach where the base stations bid for channels depending on their demands. The broker allocates channels to them with an objective to maximize the overall revenue generated subject to wireless interference in the network. This problem is known to be NP-hard and has been addressed before in limited context. We address this problem in a very generic context where (i) interference in the network is modeled using pairwise and physical interference models and (ii) base stations can bid for heterogeneous channels of different width using generic bidding functions. We propose efficient approximation algorithms that give near optimal solutions with provable analytical bounds. Detailed simulation studies using randomly generated and real base station networks show that our algorithms scale very well for large network sizes.