TY - GEN
T1 - Distributed multi-hop scheduling and medium access with delay and throughput constraints
AU - Kanodia, V.
AU - Li, C.
AU - Sabharwal, A.
AU - Sadeghi, B.
AU - Knightly, E.
PY - 2001
Y1 - 2001
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0034782707&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0034782707&partnerID=8YFLogxK
U2 - 10.1145/381677.381697
DO - 10.1145/381677.381697
M3 - Conference contribution
AN - SCOPUS:0034782707
SN - 9781581134223
T3 - Proceedings of the Annual International Conference on Mobile Computing and Networking, MOBICOM
SP - 200
EP - 209
BT - Proceedings of the Annual International Conference on Mobile Computing and Networking, MOBICOM
PB - Association for Computing Machinery (ACM)
T2 - 7th Annual International Conference on Mobile Computing and Networking
Y2 - 16 July 2001 through 21 July 2001
ER -