Distributed algorithms for end-to-end packet scheduling in wireless ad hoc networks

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 of interference. 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. A basic distributed coloring procedure, originally due to Luby [1993] (Journal of Computer and System Sciences, 47:250-286, 1993), underlies many of our algorithms. The work of Finocchi et al. [2002] (Proc. ACM-SIAM Symposium on Discrete Algorithms, 2002) showed that a natural modification of this algorithm leads to improved performance. A rigorous explanation of this was left as an open question, and we prove that the modified algorithm is indeed provably better in the worst case.