A Two-Phase Heuristic for Base Station Placement in Long Term Evolution (LTE) Networks with Cell Heterogeneity

In cellular networks, base station placement is a critical issue because it determines the construction cost and service quality. Existing placement approaches for 2G and 3G networks usually consider homogeneous base stations, where they have similar coverage areas and hardware features. Recently, the burgeoning LTE technology allows different types of base stations to collaboratively provide service in the same network. This characteristic motivates us to address the problem of placing heterogeneous base stations to serve user devices such that the overall cost is minimized while user demands are stratified. The problem is NP-hard, and thus we develop an efficient two-phase heuristic which first employs a geometric idea to provide coverage to all user devices and then adjusts the cell range to meet the power and bandwidth constraints of each base station. Experimental results show that our two-phase heuristic can reduce the construction cost and energy consumption of base stations.