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

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

136 Scopus citations

Abstract

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)
Title of host publicationProceedings of the Annual International Conference on Mobile Computing and Networking, MOBICOM
PublisherAssociation for Computing Machinery (ACM)
Pages200-209
Number of pages10
ISBN (Print)9781581134223
DOIs
StatePublished - 2001
Event7th Annual International Conference on Mobile Computing and Networking - Rome, Italy
Duration: Jul 16 2001Jul 21 2001

Publication series

NameProceedings of the Annual International Conference on Mobile Computing and Networking, MOBICOM

Conference

Conference7th Annual International Conference on Mobile Computing and Networking
Country/TerritoryItaly
CityRome
Period7/16/017/21/01

ASJC Scopus subject areas

  • Computer Science(all)

Fingerprint

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