Approximation Algorithms for Cellular Networks Planning with Relay Nodes

Relay nodes are introduced to the next generation cellular networks to enhance coverage and improve system capacity, leading to a new radio network planning paradigm. In this paper, we study two planning problems for cellular networks with relay nodes: Minimum cost cell planning and budgeted cell planning. The former is to minimize the total installation cost for opening base stations (BSs), including macro BSs and relay nodes, while satisfying all users' traffic demands. The latter is to maximize the number of users with predefined traffic demands under a given budget. Both of the problems are NP-hard. We present approximation algorithms to work out promising solutions to these problems. For the minimum cost cell planning, we develop an O(log W)-approximation algorithm, where W is the maximum capacity of macro BSs. For the budgeted cell planning, we prove that the problem is NP-hard to approximate and give an e-1/3e-1-approximation algorithm for a special case of the problem, which is general enough to meet practical requirements.