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.

By: Shubhadip Mitra, UmaMaheswari Devi,Parul Gupta, Partha Dutta, Malolan Chetlur, Shivkumar Kalyanaraman

Published in: RI09011 in 2009


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.


Questions about this service can be mailed to .