Macro-Scheduling of Base Stations for Video-on-Demand Flows in WiMAX Networks

Wireless broadband access network technologies, such as IEEE 802.16e WiMAX, by enabling high bandwidth applications for mobile users, necessitate mechanisms for efficiently utilizing the limited wireless resources and meeting growing user expectations. In this context, in a WiMAX network, we consider efficient utilization of base station (BS) radio resources and lifetime quality-of-experience (QoE) management of video-on-demand (VoD) users. For efficient resource utilization, we propose dynamic load balancing through coordinated scheduling among multiple BSs. To ensure that all flows of a single user are assigned to the same BS, our approach to coordinated scheduling is hierarchical. In this approach, allocations to users are determined initially (first level), followed by a distribution of users’ allocations among their flows (second level). During both stages of hierarchical scheduling, a utility-maximization based approach is used. To achieve long-term proportional fairness (PF) and manage lifetime QoE, user and flow utilities are modeled as functions of past service rates, in addition to their current channel conditions and bandwidth needs.

PF scheduling of users or flows across multiple BSs is known to be NP-hard. In this paper, we show that the problem is in fact NP-hard in the strong sense. We hence consider approximation algorithms proposed in prior work and design efficient heuristics for first-level scheduling. For the second level, we consider the single-BS allocation problem, and show that, despite integrality constraints, it can be solved optimally in quadratic time. Finally, we show that the hierarchical approach that we propose is optimal. The efficacy of our approaches in improving QoE and the number of satisfied users in WiMAX networks is evaluated through simulations.