Revisiting Scheduling in Heterogeneous Networks When the Backhaul is Limited
Heterogeneous networking paradigm addresses the ever growing need for throughput and connectivity in wireless cellular networks. Heterogeneous networks bring capacity improvement by deploying numerous low power base stations overlaying the existing macro cellular coverage. Dense deployment of small cells with low average number of users per base station means that the cost of backhauling becomes a significant part of the total capital expenditure. It is thus desirable that the capacity of the installed backhaul links is kept low.
We present a study on the impact of the limited capacity of backhaul links on user scheduling in a heterogeneous network comprising macro base stations and small cells. Assuming a tree topology of the backhaul network, we formulate a global proportional fair (PF) scheduling problem and show that the backhaul capacity limitations have a fundamental impact on user scheduling. If the limitations are on the backhaul links between the macro base station and the small cells, the global PF user scheduling problem can be decomposed into a set of independent local PF user scheduling problems. Unlike the case with unlimited backhaul where the local PF scheduler would allocate equal time to each user, a local scheduler in this case can be of one of three types. We completely characterize these three types and also propose a simple heuristic for optimal local PF scheduling.
When the link between the macro base station and the core network is also of limited capacity, we show how each base station can still perform a local scheduling as in the previous case as long as there is a master problem that allocates feasible virtual backhaul capacities to each base station. However, computing the optimal virtual capacities is complex and expensive in terms of the amount and frequency of information exchanges. For this scenario, we propose several heuristics that strike different trade-offs between the throughput performance and the complexity/overhead.