Resource Allocation in Green Dense Cellular Networks: Complexity and Algorithms

This paper studies the problem of user association, deadline scheduling and channel allocation in dense cellular networks with energy harvesting base stations. The objective is to maximize the number of associated and scheduled users while allocating the available channels to the users and respecting the energy and deadline constraints. First, the computational complexity of this problem is characterized by studying its NP-hardness in different cases. Next, efficient algorithms are proposed in each case. The case of single channel and single base station is solved by proposing polynomial-time optimal algorithms. The case of single channel and multiple base stations is solved by proposing an efficient constant-factor approximation algorithm. The case of multiple channels is solved by proposing efficient heuristic algorithms. Our theoretical analysis are supplemented by simulation results to illustrate the performance of the proposed algorithms.