Site placement and site selection algorithms for UMTS radio planning with quality constraints

In this paper, we address the problem of finding the optimal deployment of UMTS base stations (BSs) in a certain geographic area with a given user distribution to minimize the total BS transmit power while maintaining a satisfactory level of downlink signal-to-interference ratio (SIR) for all users and satisfying the base station maximum power constraint. We define a continuous component of the problem, referred to as the site placement problem, and an integer component, referred to as the site selection problem. The continuous component involves finding the optimal BS locations given a fixed number of BSs in the area of interest. We model the continuous problem as a constrained optimization problem with the BS locations as decision variables and the powers allocated to their assigned users as state variables, and we propose and implement an algorithm using pattern search techniques. On the other hand, the integer component is a combinatorial optimization problem which involves finding the minimum number of BSs given fixed candidate BS locations to satisfy the SIR constraints. We devise an efficient algorithm based on successive elimination of BSs in order to obtain a minimal BS set. Finally, experimental results are presented for different scenarios and different user distributions.