Fast Algorithms for Resource Allocation in Cellular Networks

Submitted to IEEE Transactions on Networking, October 2007.

• fast_tdma.pdf

We consider a wireless cellular network where the channels from the base station to the n mobile users undergo flat fading. Spectral resources are to be divided among the users using time division multiple access (TDMA) in order to maximize total user utility. We show that this problem can be cast as a nonlinear convex optimization problem, and describe an O(n) algorithm to solve it. Computational experiments show that the algorithm typically converges in around 25 iterations, where each iteration has a cost that is O(n), with a modest constant. When the algorithm starts from an initial resource allocation that is close to optimal, convergence typically takes even fewer iterations. Thus, the algorithm can efficiently track the optimal resource allocation as the channel conditions change due to fading. While we focus on TDMA systems, our approach extends to frequency selective channels, and to frequency division multiple access (FDMA), and code division multiple access (CDMA) systems.