An O(log n) dominating set protocol for wireless ad-hoc networks under the physical interference model

ABSTRACT

Dealing with interference is one of the primary challenges to solve in the design of protocols for wireless ad-hoc networks. Most of the work in the literature assumes localized or hop-based interference models in which the effect of interference is neglected beyond a certain range from the transmitter. However, interference is a more complex phenomenon that cannot, in general, be captured by localized models, implying that protocols based on such models are not guaranteed to work in practice. This paper is the first to present and rigorously analyze a distributed dominating set protocol for wireless ad-hoc networks with O(1) approximation bound based on the physical interference model, which accounts for interference generated by all nodes in the network. The proposed protocol is fully distributed, randomized, and extensively uses physical carrier sensing to reduce message overhead. It does not need node identifiers or any kind of prior information about the system, and all messages are of constant size (in bits). We prove that, by appropriately choosing the threshold for physical carrier sensing, the protocol stabilizes within a logarithmic number of communication rounds, w.h.p., which is faster than the runtime of any known distributed protocol without prior knowledge about the system under any wireless model that does not abstract away collisions.

REFERENCES

• 1: http://standards.ieee.org/getieee802/download/802.11a-1999.pdf
• 2: Mansoor Alicherry , Randeep Bhatia , Li (Erran) Li, Joint channel assignment and routing for throughput optimization in multi-radio wireless mesh networks, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080836]
• 3: K. Alzoubi , P.-J. Wan , O. Frieder, New Distributed Algorithm for Connected Dominating Set in Wireless Ad Hoc Networks, Proceedings of the 35th Annual Hawaii International Conference on System Sciences (HICSS'02)-Volume 9, p.297, January 07-10, 2002
• 4: Gurashish Brar , Douglas M. Blough , Paolo Santi, Computationally efficient scheduling with the physical interference model for throughput improvement in wireless mesh networks, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161092]
• 5: X. Cheng, D. Huang, W. Li, W. Wu, D. Z. Du, "A Polynomial-Time Approximation Scheme for the Minimum-Connected Dominating Set in Ad Hoc Wireless Networks", : Networks: an International Journal, vol.42, 2003.
• 6: S. Choi, "IEEE 802.11e MAC-level FEC Performance Evaluation and Enhancement", Proc. IEEE Globecom, 2002.
• 7: Brent N. Clark , Charles J. Colbourn , David S. Johnson, Unit disk graphs, Discrete Mathematics, v.86 n.1-3, p.165-177, Dec. 14, 1990 [doi>10.1016/0012-365X(90)90358-O]
• 8: 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
• 9: Olga Goussevskaia , Yvonne Anne Oswald , Roger Wattenhofer, Complexity in geometric SINR, Proceedings of the 8th ACM international symposium on Mobile ad hoc networking and computing, September 09-14, 2007, Montreal, Quebec, Canada [doi>10.1145/1288107.1288122]
• 10: Jimmi Grönkvist , Anders Hansson, Comparison between graph-based and interference-based STDMA scheduling, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501449.501453]
• 11: J. Gronkvist, "Traffic Controlled Spatial Reuse TDMA in Multi-hop Radio Networks," Proceedings of International Symposium on Personal, Indoor, and Mobile Radio Communications, pp. 1203--1207, 1998.
• 12: P. Gupta, P. R. Kumar, "The Capacity of Wireless Networks," IEEE Transactions on Information Theory, Vol. 46, No. 2, pp. 388--404, 2000.
• 13: Hai Huang , Andréa W. Richa , Michael Segal, Approximation algorithms for the mobile piercing set problem with applications to clustering in ad-hoc networks, Mobile Networks and Applications, v.9 n.2, p.151-161, April 2004 [doi>10.1023/B:MONE.0000013626.53247.1c]
• 14: Kamal Jain , Jitendra Padhye , Venkata N. Padmanabhan , Lili Qiu, Impact of interference on multi-hop wireless network performance, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938993]
• 15: Tomasz Jurdzinski , Grzegorz Stachowiak, Probabilistic Algorithms for the Wakeup Problem in Single-Hop Radio Networks, Proceedings of the 13th International Symposium on Algorithms and Computation, p.535-549, November 21-23, 2002
• 16: Kishore Kothapalli , Christian Scheideler , Melih Onus , Andrea Richa, Constant density spanners for wireless ad-hoc networks, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA [doi>10.1145/1073970.1073987]
• 17: Fabian Kuhn , Aaron Zollinger, Ad-hoc networks beyond unit disk graphs, Proceedings of the 2003 joint workshop on Foundations of mobile computing, p.69-78, September 19, 2003, San Diego, CA, USA [doi>10.1145/941079.941089]
• 18: Fabian Kuhn , Roger Wattenhofer , Yan Zhang , Aaron Zollinger, Geometric ad-hoc routing: of theory and practice, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.63-72, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872044]
• 19: F. Kuhn, T. Moscibroda, R. Wattenhofer, "Radio Network Clustering from Scratch", Proc. of ESA, 2004.
• 20: Fabian Kuhn , Roger Wattenhofer, Constant-time distributed dominating set approximation, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.25-32, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872040]
• 21: P. Kyasanur and N. Vaidya, "Routing and Interface Assignment in Multi-Channel Multi-Interface Wireless Networks", Proceedings of IEEE Wireless Communications and Networking Conference (WCNC), 2005.
• 22: M Luby, A simple parallel algorithm for the maximal independent set problem, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.1-10, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22146]
• 23: Thomas Moscibroda , Roger Wattenhofer , Aaron Zollinger, Topology control meets SINR: the scheduling complexity of arbitrary topologies, Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing, May 22-25, 2006, Florence, Italy [doi>10.1145/1132905.1132939]
• 24: S. Parthasarathy, R. Gandhi, "Distributed Algorithms for Coloring and Domination in Wireless Ad Hoc Networks", Proc. FSTTCS, 2004.
• 25: B. Raman, "Channel Allocation in 802.11-based Mesh Networks," Proc. IEEE Infocom 2006.
• 26: A. Raniwala and T. Chiueh, "Architecture and Algorithms for an IEEE 802.11-Based Multi-Channel Wireless Mesh Networks", Proceedings of IEEE International Conference on Computer Communications (Infocom), pp. 2223--2234, 2005.
• 27: Theodore S. Rappaport, Wireless Communications: Principles and Practice, Prentice-Hall, Inc., Upper Saddle River, NJ, 1995
• 28: C. Scheideler. Probabilistic Methods for Coordination Problems. HNI-Verlagsschriftenreihe 78, University of Paderborn, 2000. See also www14.in.tum.de/personen/scheideler.
• 29: Gaurav Sharma , Ravi R. Mazumdar , Ness B. Shroff, On the complexity of scheduling in wireless networks, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161116]
• 30: X. Yang, N. H. Vaidya, "Spatial Backoff Contention Resolution for Wireless Networks", Proc. IEEE WiMesh, 2006.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

General Terms:
Algorithms, Theory

Keywords:
ad hoc networks, dominating set, physical interference model, self-stabilization