Algorithmic Aspects of Access Networks Design in B3G/4G Cellular Networks

The forthcoming 4G cellular systems will provide broadband wireless access to a variety of advanced data and voice services. In order to do that, these networks will have a significantly larger number of base stations and a much higher bandwidth demand from their radio access networks. This will motivate operators to replace the commonly used star based architecture, in which an RNC is connected to a set of base stations via direct links, with a more complex tree structure, in which a base station can be connected to an RNC via other base stations. In this paper we address algorithmic aspects of this challenging design problem, in which tree-topology is used to connect base stations and RNCs. We formulate the problem as an optimization problem and prove that it is NP-hard to approximate it in the general case. For the metric case, however, we develop an O(log n)-approximation algorithm. We then study the performance of this algorithm and several other heuristics in practical scenarios. Our results indicate that a combination of a certain greedy heuristic and the proven approximation algorithm, generates a solution that produces close to optimal results in practical scenarios and can be efficiently computed for sufficiently large network sizes.