Cell planning for heterogeneous networks: An approximation algorithm
- 1 April 2014
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 0743166X,p. 1087-1095
Abstract
Low-power access points, such as pico base stations (BSs), femto BSs, and relays are introduced to the next generation cellular systems to enhance coverage and improve system capacity. Deploying low-power access points to offload the conventional macro BSs is deemed as a spectrum- and cost-efficient way to meet the sharp increase of traffic requirements of cellular networks. However, it also leads to heterogeneous network framework and raises new challenges for cell planning. In this paper, we study the minimum cost cell planning problem in such a heterogeneous network. Our optimization task is to select a subset of candidate sites to lay BSs, including macro BSs, pico BSs and relays, to minimize the total deployment cost while satisfying the rate requirements of the demand nodes (DNs) served by the cellular network. We prove that the general case of the formulated problem is APX-hard, where a DN is constrained to be associated with only one BS. However, if each DN can be served by multiple BSs, which is a reasonable case for practical cellular systems, we show it is not APX-hard and develop an approximation algorithm to work out promising solutions. Our proposed algorithm guarantees an approximation ratio of O(logR) to the global optimum, where R is the maximum achievable capacity of the BSs. Numerical results indicate that our proposal can significantly reduce the deployment cost of the cellular network with given rate requirements of DNs compared to other cell planning schemes.Keywords
This publication has 23 references indexed in Scilit:
- Efficient Resource Allocation for Cognitive Radio Networks with Cooperative RelaysIEEE Journal on Selected Areas in Communications, 2013
- Capacity and Fairness Analysis of Heterogeneous Networks with Range Expansion and Interference CoordinationIEEE Communications Letters, 2011
- Capacity and coverage enhancement in heterogeneous networksIEEE Wireless Communications, 2011
- Evolution of LTE toward IMT-advancedIEEE Communications Magazine, 2011
- Relay technologies for WiMax and LTE-advanced mobile systemsIEEE Communications Magazine, 2009
- A rolling window optimization method for large-scale WCDMA base stations planning problemEuropean Journal of Operational Research, 2007
- Convex Optimization2004
- Covering problems with hard capacities2003
- Variable-rate variable-power MQAM for fading channelsIEEE Transactions on Communications, 1997
- An approximation algorithm for the generalized assignment problemMathematical Programming, 1993