End-to-end packet-scheduling in wireless ad-hoc networks

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'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.

REFERENCES

• 1: Noga Alon , F. R. K. Chung , R. L. Graham, Routing Permutations on Graphs Via Matchings, SIAM Journal on Discrete Mathematics, v.7 n.3, p.513-530, Aug. 1994 [doi>10.1137/S0895480192236628]
• 2: Micah Adler , Christian Scheideler, Efficient communication strategies for ad-hoc wireless networks (extended abstract), Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.259-268, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277651.277692]
• 3: M. Andrew , A. Goel , A. Fernández, Source Routing and Scheduling in Packet Networks, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.168, October 14-17, 2001
• 4: B. Awerbuch, B. Berger, L. Cowen, and D. Peleg. Low-diameter graph decomposition is in N. C. Random Structures & Algorithms, 5:441--452, 1994.
• 5: B. Awerbuch, A. V. Goldberg, M. Luby, and S. A. Plotkin. Network decomposition and locality in distributed computation. In Proc. IEEE Symposium on Foundations of Computer Science, pages 364--369, 1989.
• 6: Baruch Awerbuch , David Peleg, Routing with polynomial communication-space trade-off, SIAM Journal on Discrete Mathematics, v.5 n.2, p.151-162, May 1992 [doi>10.1137/0405013]
• 7: H. Balakrishnan, C. Barrett, V.S. Anil Kumar, M. Marathe, S. Thite. Induced Matchings and its Relationship to Maximum Instantaneous Capacity of Media Access Layer, Manuscript.
• 8: Chris Barrett , Achla Marathe , Madhav V. Marathe , Martin Drozda, Characterizing the interaction between routing and MAC protocols in ad-hoc networks, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513812]
• 9: C. Barrett, G. Istrate, V. S. Anil Kumar, M. Marathe and S. Thite. Algorithms for link scheduling in wireless radio networks. Manuscript.
• 10: Devdatt Dubhashi , Alessandro Mei , Alessandro Panconesi , Jaikumar Radhakrishnan , Arvind Srinivasan, Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 11: Irene Finocchi , Alessandro Panconesi , Riccardo Silvestri, Experimental analysis of simple, distributed vertex coloring algorithms, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.606-615, January 06-08, 2002, San Francisco, California
• 12: David A. Grable , Alessandro Panconesi, Fast distributed algorithms for Brooks-Vizing colorings, Journal of Algorithms, v.37 n.1, p.85-120, Oct. 2000 [doi>10.1006/jagm.2000.1097]
• 13: Sven O. Krumke , Madhav V. Marathe , S. S. Ravi, Models and approximation algorithms for channel assignment in radio networks, Wireless Networks, v.7 n.6, p.575-584, November 2001 [doi>10.1023/A:1012311216333]
• 14: T. Leighton, B. Maggs and S. Rao. Packet Routing and Job Shop Scheduling in O(Congestion+Dilation) Steps. Combinatorica, v14, 2, pp. 167--180, 1994.
• 15: T. Leighton, B. Maggs and A. Richa. Fast algorithms for finding O(Congestion+Dilation) packet routing schedules. Combinatorica, pp. 1--27, 1999.
• 16: F. T. Leighton , Bruce M. Maggs , Abhiram G. Ranade , Satish B. Rao, Randomized routing and sorting on fixed-connection networks, Journal of Algorithms, v.17 n.1, p.157-205, July 1994 [doi>10.1006/jagm.1994.1030]
• 17: N. Linial and M. Saks. Low Diameter Graph Decompositions. Combinatorica, 13:441--454, 1993.
• 18: Michael Luby, Removing randomness in parallel computation without a processor penalty, Journal of Computer and System Sciences, v.47 n.2, p.250-286, Oct. 1993 [doi>10.1016/0022-0000(93)90033-S]
• 19: F. Meyer auf der Heide and B. Vöcking. A packet routing protocols for arbitrary networks. LNCS, Vol. 439, 291--302, 1995.
• 20: Rafail Ostrovsky , Yuval Rabani, Universal O(congestion + dilation + log1+&egr;N) local control packet switching algorithms, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.644-653, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258659]
• 21: Alessandro Panconesi , Aravind Srinivasan, On the complexity of distributed network decomposition, Journal of Algorithms, v.20 n.2, p.356-374, March 1996 [doi>10.1006/jagm.1996.0017]
• 22: Larry L. Peterson , Bruce S. Davie, Computer networks: a systems approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 23: Subramanian Ramanathan, Scheduling algorithms for multi-hop radio networks, University of Delaware, Newark, DE, 1992
• 24: S. Ramanathan, A Unified Framework and Algorithm for (T/F/C)DMA Channel Assignment in Wireless Networks, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.900, April 09-11, 1997
• 25: Subramanian Ramanathan , Errol L. Lloyd, Scheduling algorithms for multihop radio networks, IEEE/ACM Transactions on Networking (TON), v.1 n.2, p.166-177, April 1993 [doi>10.1109/90.222924]
• 26: Yuval Rabani , Éva Tardos, Distributed packet switching in arbitrary networks, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.366-375, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237983]
• 27: Prabhakar Raghavan , Clark D. Tompson, Randomized rounding: a technique for provably good algorithms and algorithmic proofs, Combinatorica, v.7 n.4, p.365-374, Dec, 1987 [doi>10.1007/BF02579324]
• 28: Christian Scheideler , J. Van Leeuwen , J. Hartmanis , G. Goos, Universal Routing Strategies for Interconnection Networks, Springer-Verlag New York, Inc., Secaucus, NJ, 1998
• 29: Aravind Srinivasan , Chung-Piaw Teo, A constant-factor approximation algorithm for packet routing, and balancing local vs. global criteria, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.636-643, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258658]