Back to Search
Start Over
Design of Scheduling Algorithms for End-to-End Backlog Minimization in Wireless Multi-Hop Networks Under K-Hop Interference Models.
- Source :
- IEEE/ACM Transactions on Networking; Apr2016, Vol. 24 Issue 2, p1265-1278, 14p
- Publication Year :
- 2016
-
Abstract
- In this paper, we study the problem of link scheduling for multi-hop wireless networks with per-flow delay constraints under the K-hop interference model. Specifically, we are interested in algorithms that maximize the asymptotic decay-rate of the probability with which the maximum end-to-end backlog among all flows exceeds a threshold, as the threshold becomes large. We provide both positive and negative results in this direction. By minimizing the drift of the maximum end-to-end backlog in the converge-cast on a tree, we design an algorithm, Largest-Weight-First (LWF), that achieves the optimal asymptotic decay-rate for the overflow probability of the maximum end-to-end backlog as the threshold becomes large. However, such a drift minimization algorithm may not exist for general networks. We provide an example in which no algorithm can minimize the drift of the maximum end-to-end backlog. Finally, we simulate the LWF algorithm together with a well known algorithm (the back-pressure algorithm) and a large-deviations optimal algorithm in terms of the sum-queue (the P-TREE algorithm) in converge-cast networks. Our simulation shows that our algorithm performs significantly better not only in terms of asymptotic decay-rate, but also in terms of the actual overflow probability. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 10636692
- Volume :
- 24
- Issue :
- 2
- Database :
- Complementary Index
- Journal :
- IEEE/ACM Transactions on Networking
- Publication Type :
- Academic Journal
- Accession number :
- 114705895
- Full Text :
- https://doi.org/10.1109/TNET.2015.2414660