TY - CONF
T1 - Algorithmic aspects of capacity in wireless networks
T2 - Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems
Y1 - 2005
A1 - Kumar,V. S. Anil
A1 - Marathe,Madhav V.
A1 - Parthasarathy,Srinivasan
A1 - Srinivasan, Aravind
KW - capacity modeling
KW - end-to-end scheduling
KW - Linear programming
KW - Wireless networks
AB - This paper considers two inter-related questions: (i) Given a wireless ad-hoc network and a collection of source-destination pairs {(si,ti)}, what is the maximum throughput capacity of the network, i.e. the rate at which data from the sources to their corresponding destinations can be transferred in the network? (ii) Can network protocols be designed that jointly route the packets and schedule transmissions at rates close to the maximum throughput capacity? Much of the earlier work focused on random instances and proved analytical lower and upper bounds on the maximum throughput capacity. Here, in contrast, we consider arbitrary wireless networks. Further, we study the algorithmic aspects of the above questions: the goal is to design provably good algorithms for arbitrary instances. We develop analytical performance evaluation models and distributed algorithms for routing and scheduling which incorporate fairness, energy and dilation (path-length) requirements and provide a unified framework for utilizing the network close to its maximum throughput capacity.Motivated by certain popular wireless protocols used in practice, we also explore "shortest-path like" path selection strategies which maximize the network throughput. The theoretical results naturally suggest an interesting class of congestion aware link metrics which can be directly plugged into several existing routing protocols such as AODV, DSR, etc. We complement the theoretical analysis with extensive simulations. The results indicate that routes obtained using our congestion aware link metrics consistently yield higher throughput than hop-count based shortest path metrics.
JA - Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems
T3 - SIGMETRICS '05
PB - ACM
CY - New York, NY, USA
SN - 1-59593-022-1
UR - http://doi.acm.org/10.1145/1064212.1064228
M3 - 10.1145/1064212.1064228
ER -