  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.
