Approximation Algorithms for Cell Association and Scheduling in Femtocell Networks

Femtocells are recognized as effective for improving network coverage and capacity and for reducing power consumption due to the reduced range of wireless transmissions. Although highly appealing, a plethora of challenging problems need to be addressed for fully harvesting its potential. In this paper, we investigate the problem of cell association and service scheduling in femtocell networks. In addition to the general goal of offloading traffic from the macrobase station (BS), we also aim at minimizing the latency of service requested by the users, while considering both open and closed access strategies. We show that the cell association problem is NP-hard, and propose several near-optimal solution algorithms for assigning users to BSs, including a sequential fixing algorithm, a rounding approximation algorithm, a greedy approximation algorithm, and a randomized algorithm. For service scheduling, we develop an optimal algorithm to minimize the average waiting time for the users associated with the same BS. The proposed algorithms are analyzed with respect to performance bounds, approximation ratios, and optimality, and are evaluated with simulations.