@conference {17593,
title = {End-to-end packet-scheduling in wireless ad-hoc networks},
booktitle = {Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms},
series = {SODA {\textquoteright}04},
year = {2004},
month = {2004///},
pages = {1021 - 1030},
publisher = {Society for Industrial and Applied Mathematics},
organization = {Society for Industrial and Applied Mathematics},
address = {Philadelphia, PA, USA},
abstract = {Packet-scheduling is a particular challenge in wireless networks due to interference from nearby transmissions. A distance-2 interference model serves as a useful abstraction here, and we study packet routing and scheduling under this model. The main focus of our work is the development of fully-distributed (decentralized) protocols. We present polylogarithmic/constant factor approximation algorithms for various families of disk graphs (which capture the geometric nature of wireless-signal propagation), as well as near-optimal approximation algorithms for general graphs. The packet-scheduling work by L eighton, Maggs and Rao (Combinatorica, 1994) and a basic distributed coloring procedure, originally due to Luby (J. Computer and System Sciences, 1993), underlie many of our algorithms. Experimental work of Finocchi, Panconesi, and Silvestri (SODA 2002) showed that a natural modification of Luby{\textquoteright}s algorithm leads to improved performance, and a rigorous explanation of this was left as an open question; we prove that the modified algorithm is provably better in the worst-case. Finally, using simulations, we study the impact of the routing strategy and the choice of parameters on the performance of our distributed algorithm for unit disk graphs.},
isbn = {0-89871-558-X},
url = {http://dl.acm.org/citation.cfm?id=982792.982945},
author = {Kumar,V. S. Anil and Marathe,Madhav V. and Parthasarathy,Srinivasan and Srinivasan, Aravind}
}