Delay-Based Back-Pressure Scheduling in Multihop Wireless Networks

Abstract

Scheduling is a critical and challenging resource allocation mechanism for multihop wireless networks. It is well known that scheduling schemes that favor links with larger queue length can achieve high throughput performance. However, these queue-length-based schemes could potentially suffer from large (even infinite) packet delays due to the well-known last packet problem, whereby packets belonging to some flows may be excessively delayed due to lack of subsequent packet arrivals. Delay-based schemes have the potential to resolve this last packet problem by scheduling the link based on the delay the packet has encountered. However, characterizing throughput-optimality of these delay-based schemes has largely been an open problem in multihop wireless networks (except in limited cases where the traffic is single-hop.) In this paper, we investigate delay-based scheduling schemes for multihop traffic scenarios with fixed routes. We develop a scheduling scheme based on a new delay metric, and show that the proposed scheme achieves optimal throughput performance. Further, we conduct simulations to support our analytical results, and show that the delay-based scheduler successfully removes excessive packet delays, while it achieves the same throughput region as the queue-length-based scheme.

Accepted for publication in IEEE/ACM Transactions on Networking. A preliminary version of this work was presented at the IEEE INFOCOM 2011

References in corpus (2)

• Simple Distributed Weighted Matchings
• Delay-Based Back-Pressure Scheduling in Multihop Wireless Networks

Cited by in corpus (10)

• Delay-Based Back-Pressure Scheduling in Multihop Wireless Networks
• Backpressure with Adaptive Redundancy (BWAR)
• A Novel Max Pressure Algorithm Based on Traffic Delay
• Backpressure Control with Estimated Queue Lengths for Urban Network Traffic
• SERENADE: A Parallel Randomized Algorithm Suite for Crossbar Scheduling in Input-Queued Switches
• Low-Complexity Scheduling Policies for Achieving Throughput and Asymptotic Delay Optimality in Multi-Channel Wireless Networks
• Fair Scheduling for Data Collection in Mobile Sensor Networks with Energy Harvesting
• Achieving Optimal Throughput and Near-Optimal Asymptotic Delay Performance in Multi-Channel Wireless Networks with Low Complexity: A Practical Greedy Scheduling Policy
• Traffic Allocation for Low-Latency Multi-Hop Networks with Buffers
• Achieving Delay Rate-function Optimality in OFDM Downlink with Time-correlated Channels