Budgeted Cell Planning for Cellular Networks With Small Cells

Heterogeneous networks (HetNets), where small cells are deployed within the coverage of macrocells, can increase capacity and enhance coverage of a cellular system. Compared with macrocells, small cells have superiority in terms of low installation and operation cost because of their small physical size and low transmission power. Hence, HetNets are deemed as a cost-effective way to address the everlasting radio spectrum crisis. On the other hand, HetNets also unfold a new paradigm from the viewpoint of cellular network planning. In this paper, we study the budgeted cell planning problem in HetNets, where our aim is to maximize the number of traffic demand nodes whose required rates are fully satisfied with a given budget. Our optimization task is challenging, and the formulated problem is hard to solve because of constraints in practical cellular systems, including power limitation, available bandwidth, and traffic requirements. We develop an approximation algorithm that yields an (e - 1)/2e fraction of the optimum, which not only provides quality-guaranteed solutions to the budgeted cel planning problem but sheds useful lights on how to plan a HetNet with limited capital expenditure as well. Preliminary numerical results show that small cells can improve the capacity of a cellular system significantly if they are properly planned.