Scheduling is a critical and challenging resource allocation mechanism for multi-hop wireless networks. It is well known that scheduling schemes that give a higher priority to the link with larger queue length can achieve high throughput performance. However, this queue-length-based approach could potentially suffer from large (even infinite) packet delays due to the well-known last packet problem, whereby packets may get 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 for the packet has encountered. However, the throughput performance of delay-based schemes has largely been an open problem  except in limited cases of single-hop networks. In this paper, we investigate delay-based scheduling schemes for multi-hop traffic scenarios . We view packet delays from a different perspective, and develop a scheduling scheme based on a new delay metric . Through rigorous analysis, we show that the proposed scheme achieves the optimal throughput performance. Finally , we conduct extensive 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 queuelength-based scheme.
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.
R
multi-hop
multihop
R
give a higher priority to the link
favor links
R
this
these
R
approach
schemes
R
may get
belonging to some flows may be
D
for
R
the throughput performance of
characterizing throughput-optimality of these
A
in multihop wireless networks (
R
of
where the traffic is
R
networks.
.)
R
multi-hop traffic scenarios . We view packet delays from a different perspective, and
multihop traffic scenarios with fixed routes. We
R
. Through rigorous analysis, we
, and
D
the
R
Finally
Further
D
extensive
R
queuelength-based
queue-length-based