Distributed multi-hop scheduling and medium access with delay and throughput constraints

V. Kanodia, C. Li, A. Sabharwal, B. Sadeghi, E. Knightly

Research output: Contribution to conferencePaperpeer-review

136 Scopus citations


Providing quality of service in random access multi-hop wireless networks requires support from both medium access and packet scheduling algorithms. However, due to the distributed nature of ad hoc networks, nodes may not be able to determine the next packet that would be transmitted in a (hypothetical) centralized and ideal dynamic priority scheduler. In this paper, we develop two mechanisms for QoS communication in multi-hop wireless networks. First, we devise distributed priority scheduling, a technique that piggybacks the priority tag of a node's head-of-line packet onto handshake and data packets; e.g., RTS/DATA packets in IEEE 802.11. By monitoring transmitted packets, each node maintains a scheduling table which is used to assess the node's priority level relative to other nodes. We then incorporate this scheduling table into existing IEEE 802.11 priority back-off schemes to approximate the idealized schedule. Second, we observe that congestion, link errors, and the random nature of medium access prohibit an exact realization of the ideal schedule. Consequently, we devise a scheduling scheme termed multi-hop coordination so that down-stream nodes can increase a packet's relative priority to make up for excessive delays incurred upstream. We next develop a simple analytical model to quantitatively explore these two mechanisms. In the former case, we study the impact of the probability of over-hearing another packet's priority index on the scheme's ability to achieve the ideal schedule. In the latter case, we explore the role of multi-hop coordination in increasing the probability that a packet satisfies its end-to-end QoS target. Finally, we perform a set of ns-2 simulations to study the scheme's performance under more realistic conditions.

Original languageEnglish (US)
Number of pages10
StatePublished - 2001
Event7th Annual International Conference on Mobile Computing and Networking - Rome, Italy
Duration: Jul 16 2001Jul 21 2001


Conference7th Annual International Conference on Mobile Computing and Networking

ASJC Scopus subject areas

  • Computer Science(all)


Dive into the research topics of 'Distributed multi-hop scheduling and medium access with delay and throughput constraints'. Together they form a unique fingerprint.

Cite this