Optimal Link Scheduling for Real-time Traffic in Wireless Mesh Networks in both Per-flow and Per-path Frameworks

In this paper we investigate link scheduling for Wireless Mesh Networks (WMNs) carrying real-time (i.e., delay-constrained) traffic. We show that the problem of computing a conflict-free link schedule with end-to-end delay constraints can be formulated as a mixed-integer non linear problem that can be optimally solved in reasonable time (i.e., minutes) for relatively large WMNs (up to 20–30 nodes). We use the above result to explore the schedulability region of a WMN with a given routing and input traffic, assessing whether and when aggregating flows which traverse the same path makes a given input flow set sched-ulable. Furthermore, we devise a heuristic solution strategy, which computes good suboptimal solutions within up to few seconds, thus being amenable for online admission control.