Efficient Link Scheduling for Online Admission Control of Real-time Traffic in Wireless Mesh Networks

We investigate the problem of joint routing and link scheduling in Time-Division Multiple Access (TDMA) Wireless Mesh Networks (WMNs) carrying real-time traffic. We propose a framework that always computes a feasible solution (i.e. a set of paths and link activations) if there exists one, by optimally solving a mixed integer-non linear problem. Such solution can be computed in minutes or tens thereof for e.g. grids of up to 4×4 nodes. We also propose heuristics based on Lagrangian decomposition to compute suboptimal solutions considerably faster and/or for larger WMNs, up to 8×8 nodes. We show that the heuristic solutions are near-optimal, and we exploit them to investigate the optimal placement of one or more gateways from a delay bound perspective.