Load balancing in cellular wireless networks

We present a linear-programming approach for dynamic load balancing in CDMA networks. The linear program characterizes the minimum achievable base station load for a given configuration of mobiles at each time interval, and gives a useful benchmark for the potential gains from optimizing the power assignment. The solution of the linear program also offers valuable insight to the qualitative properties of the optimal power allocation. In particular, the structure of the optimal assignment reflects the critical notion that power allocation should not just be based on signal strength values but also on shadow prices which arise from load considerations. We develop a dual-ascent scheme for solving the linear program in a (mostly) distributed fashion with low communication overhead. Extensive numerical experiments demonstrate that there is scope for significant gains from balancing base station loads in typical scenarios. Keywords: CDMA networks, cellular networks, uplink power control, Yates-Huang-Hanly fixed point, load balancing, min-max optimization, dual linear program, shadow pricing, distributed algorithm, stochastic approximation