TY - CONF
T1 - Approximation algorithms for throughput maximization in wireless networks with delay constraints
T2 - 2011 Proceedings IEEE INFOCOM
Y1 - 2011
A1 - Guanhong Pei
A1 - Anil Kumar,V. S
A1 - Parthasarathy,S.
A1 - Srinivasan, Aravind
KW - Approximation algorithms
KW - Approximation methods
KW - approximation theory
KW - Delay
KW - delay constraints
KW - delays
KW - general interference model
KW - Interference
KW - multihop wireless networks
KW - optimisation
KW - Optimized production technology
KW - radio networks
KW - radiofrequency interference
KW - target delay bound
KW - Throughput
KW - throughput maximization
KW - Wireless networks
AB - We study the problem of throughput maximization in multi-hop wireless networks with end-to-end delay constraints for each session. This problem has received much attention starting with the work of Grossglauser and Tse (2002), and it has been shown that there is a significant tradeoff between the end-to-end delays and the total achievable rate. We develop algorithms to compute such tradeoffs with provable performance guarantees for arbitrary instances, with general interference models. Given a target delay-bound Δ(c) for each session c, our algorithm gives a stable flow vector with a total throughput within a factor of O (logΔm/log log Δm) of the maximum, so that the per-session (end-to-end) delay is O ((logΔm/log log Δm Δ(c))2), where Δm = maxc{Δ(c)}; note that these bounds depend only on the delays, and not on the network size, and this is the first such result, to our knowledge.
JA - 2011 Proceedings IEEE INFOCOM
PB - IEEE
SN - 978-1-4244-9919-9
M3 - 10.1109/INFCOM.2011.5934887
ER -