This paper proposes an efficient method to compute minimum delay schedules over multi-hop wireless networks that use time-division multiple access (TDMA)-based media access control protocols. Simulation results are also presented.

Section 1 introduces the work, and Section 2 explains the transmission model used. The model assumes a standard TDMA model that corresponds to 802.16 mesh networks, and time slots are grouped in frames. Formulas related to stop-and-go queueing systems, involving link rates, are derived. Five different types of conflicts are explained, as well as the creation of conflict graphs. Section 3 presents the TDMA scheduling algorithms. The authors develop conditions for link rates with a conflict-free schedule over frames of a given number of slots, and describe a polynomial complexity algorithm for fixed transmission order. This algorithm is modified for multiple transmissions. Section 4 gives an algorithm that computes the minimum number of slots required to schedule all links, which scales down links if necessary. Section 5 discusses delay-aware scheduling. End-to-end delays that depend only on scheduling delays are discussed for round-trip paths. Min-max TDMA delay scheduling, single frames on tree overlays, and modulo operation on both of them are also discussed. Section 6 presents the performance of the algorithms, using tables and graphs. In order to measure performance, schedules are run over a small topology, a chain topology, and a mesh topology. Section 7 contains the conclusions of the paper.