Efficient link scheduling for online admission control of real-time traffic in wireless mesh networks

Link scheduling is used in wireless mesh networks (WMNs) to guarantee interference-free transmission on the shared wireless medium in a time division multiple access approach. Several papers in the literature address the problem of link scheduling guaranteeing a minimum throughput to the flows traversing the WMN. However, none of the existing works address the problem of computing a schedule that guarantees that pre-specified end-to-end delay constraints are met. In this paper, we make a first step forward in this direction by defining a link scheduling algorithm that works in sink-tree WMNs, i.e. those whose traffic is routed towards a common sink (i.e. the Internet gateway). Our iterative algorithm exploits a delay-based admission control procedure, devised through Network Calculus, which solves an optimization problem and tests the feasibility of a schedule from the point of view of delay guarantees. Thanks to a clever solution approach for the optimization problem, the iterative algorithm computes feasible solutions in affordable times for networks of several tens of nodes, and is thus amenable to online admission control of real-time traffic. (C) 2011 Elsevier B.V. All rights reserved.