Date Added: Oct 2009
Time Division Multiple Access (TDMA) based Medium Access Control (MAC) protocols can provide QoS with guaranteed access to the wireless channel. However, in multi-hop wireless networks, these protocols may introduce scheduling delay if, on the same path, an outbound link on a router is scheduled to transmit before an inbound link on that router. The total scheduling delay can be quite large since it accumulates at every hop on a path. This paper presents a method that finds conflict-free TDMA schedules with minimum scheduling delay. The authors show that the scheduling delay can be interpreted as a cost, in terms of transmission order of the links, collected over a cycle in the conflict graph.