OPTIMAL CELLULAR NETWORK DEPLOYMENT REUSING EXISTING BASE STATIONS

Cellular communications has experienced an explosive growth recently. In order to increase the capacity of a cellular network without new frequency spectrum allocation, it is a common practice to use base stations with a lower power transmitter. Cell splitting is one of such techniques, which increases the network capacity four-fold by dividing a cell into four smaller cells. Although the cell splitting technique can reuse the existing base stations, it requires that those existing base stations be uniformly distributed. In addition, the radius of each new cell is always half that of the original cell. In this paper, it is assumed that the radius of new cells can be of any smaller size, and that the existing base stations are not necessarily uniformly distributed. While new base stations can be placed at the cell centers based on the design of the new cellular network, existing base stations should be put as close to a cell center as possible in the new cellular network. The problem to be solved, referred to as the optimal cellular network deployment, can be formulated as follows: given a set of existing base stations and a planned cellular network that has a fixed cell size and network orientation but is movable, find a position to fix the movable cellular network such that the maximum distance between existing base stations and their corresponding cell centers is minimized. This paper shows that the optimal cellular network deployment problem can be solved in O(n3) time if n existing base stations will be reused.