Initializing newly deployed ad hoc and sensor networks

ABSTRACT

A newly deployed multi-hop radio network is unstructured and lacks a reliable and efficient communication scheme. In this paper, we take a step towards analyzing the problems existing during the initialization phase of ad hoc and sensor networks. Particularly, we model the network as a multi-hop quasi unit disk graph and allow nodes to wake up asynchronously at any time. Further, nodes do not feature a reliable collision detection mechanism, and they have only limited knowledge about the network topology. We show that even for this restricted model, a good clustering can be computed efficiently. Our algorithm efficiently computes an asymptotically optimal clustering. Based on this algorithm, we describe a protocol for quickly establishing synchronized sleep and listen schedule between nodes within a cluster. Additionally, we provide simulation results in a variety of settings.

REFERENCES

• 1: I. F. Akyildiz , W. Su , Y. Sankarasubramaniam , E. Cayirci, Wireless sensor networks: a survey, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.38 n.4, p.393-422, 15 March 2002 [doi>10.1016/S1389-1286(01)00302-4]
• 2: Khaled M. Alzoubi , Peng-Jun Wan , Ophir Frieder, Message-optimal connected dominating sets in mobile 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.513820]
• 3: D. J. Baker and A. Ephremides. The Architectural Organization of a Mobile Radio Network via a Distributed Algorithm. IEEE Transactions on Communications, COM-29(11):1694--1701, 1981.
• 4: Reuven Bar-Yehuda , Oded Goldreich , Alon Itai, On the time-complexity of broadcast in radio networks: an exponential gap between determinism randomization, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.98-108, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41849]
• 5: Lali Barriére , Pierre Fraigniaud , Lata Narayanan, Robust position-based routing in wireless Ad Hoc networks with unstable transmission ranges, Proceedings of the 5th international workshop on Discrete algorithms and methods for mobile computing and communications, p.19-27, July 2001, Rome, Italy [doi>10.1145/381448.381451]
• 6: Stefano Basagni, Distributed Clustering for Ad Hoc Networks, Proceedings of the 1999 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '99), p.310, June 23-25, 1999
• 7: M. Chatterjee, S. K. Das, and D. Turgut. An On-Demand Weighted Clustering Algorithm (WCA) for Ad-Hoc Networks. In Proceedings of IEEE GLOBECOM 2000, pages 1697--1701. ACM Press, 2000.
• 8: J. Deng and Z. Haas. Dual Busy Tone Multiple Access (DBTMA): A New Medium Access Control for Packet Radio Networks. In Proceedings of IEEE ICUPC, volume 1, pages 973--977, 1998.
• 9: Eyal Kushilevitz , Yishay Mansour, An $\Omega(D\log (N/D))$ Lower Bound for Broadcast in Radio Networks, SIAM Journal on Computing, v.27 n.3, p.702-712, June 1998 [doi>10.1137/S0097539794279109]
• 10: Uriel Feige, A threshold of ln n for approximating set cover, Journal of the ACM (JACM), v.45 n.4, p.634-652, July 1998 [doi>10.1145/285055.285059]
• 11: Jie Gao , Leonidas Guibas , John Hershberger , Li Zhang , An Zhu, Discrete mobile centers, Proceedings of the seventeenth annual symposium on Computational geometry, p.188-196, June 2001, Medford, Massachusetts, United States [doi>10.1145/378583.378666]
• 12: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 13: Leszek Gąsieniec , Andrzej Pelc , David Peleg, The wakeup problem in synchronous broadcast systems (extended abstract), Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.113-121, July 16-19, 2000, Portland, Oregon, United States [doi>10.1145/343477.343529]
• 14: Mario Gerla , Jack Tzu-Chieh Tsai, Multicluster, mobile, multimedia radio network, Wireless Networks, v.1 n.3, p.255-265, 1995 [doi>10.1007/BF01200845]
• 15: Wendi Rabiner Heinzelman , Anantha Chandrakasan , Hari Balakrishnan, Energy-Efficient Communication Protocol for Wireless Microsensor Networks, Proceedings of the 33rd Hawaii International Conference on System Sciences-Volume 8, p.8020, January 04-07, 2000
• 16: Harry B. Hunt, III , Madhav V. Marathe , Venkatesh Radhakrishnan , S. S. Ravi , Daniel J. Rosenkrantz , Richard E. Stearns, NC-approximation schemes for NP- and PSPACE-hard problems for geometric graphs, Journal of Algorithms, v.26 n.2, p.238-274, feb. 1998 [doi>10.1006/jagm.1997.0903]
• 17: L. Jia, R. Rajaraman, and R. Suel. An Efficient Distributed Algorithm for Constructing Small Dominating Sets. In Proc. of the 20th ACM Symposium on Principles of Distributed Computing (PODC), pages 33--42, 2001.
• 18: 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
• 19: R. M. Karp. Reducibility Among Combinatorial Problems. In Proc. of a Symposium on the Complexity of Computer Computations, pages 85--103, 1972.
• 20: R. Kershner. The number of circles covering a set. American Journal of Mathematics, 62, 1939.
• 21: F. Kuhn, T. Moscibroda, and R. Wattenhofer. Radio Network Clustering from Scratch. In Proceedings of the 12th Annual European Symposium on Algorithms (ESA), 2004.
• 22: Fabian Kuhn , Thomas Moscibroda , Roger Wattenhofer, What cannot be computed locally!, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011811]
• 23: 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]
• 24: 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]
• 25: Shay Kutten , David Peleg, Fast distributed construction of small k-dominating sets and applications, Journal of Algorithms, v.28 n.1, p.40-66, July 1, 1998 [doi>10.1006/jagm.1998.0929]
• 26: Koji Nakano , Stephen Olariu, Energy-Efficient Initialization Protocols for Single-Hop Radio Networks with No Collision Detection, IEEE Transactions on Parallel and Distributed Systems, v.11 n.8, p.851-863, August 2000 [doi>10.1109/71.877942]
• 27: Venkatesh Rajendran , Katia Obraczka , J. J. Garcia-Luna-Aceves, Energy-efficient collision-free medium access control for wireless sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958513]
• 28: Lawrence G. Roberts, ALOHA packet system with and without slots and capture, ACM SIGCOMM Computer Communication Review, v.5 n.2, p.28-42, April 1975 [doi>10.1145/1024916.1024920]
• 29: Jacob Sharony, An architecture for mobile radio networks with dynamically changing topology using virtual subnets, Mobile Networks and Applications, v.1 n.1, p.75-86, Aug. 1996 [doi>10.1007/BF01342734]
• 30: P. Sinha, R. Sivakumar, and V. Bharghavan. Enhancing Ad Hoc Routing with Dynamic Virtual Infrastructures. In IEEE Conference on Computer Communications (INFOCOM), pages 1763--1772, 2001.
• 31: F. A. Tobagi and L. Kleinrock. Packet Switching in Radio Channels: Part II - The Hidden Terminal Problem in Carrier Sense Multiple Access and the Busy Tone Solution. COM-23(12):1417--1433, 1975.
• 32: P. Wan, K. Alzoubi, and O. Frieder. Distributed construction of connected dominating set in wireless ad hoc networks. In Proceedings of INFOCOM, 2002.
• 33: Yu Wang , Xiang-Yang Li, Geometric Spanners for Wireless Ad Hoc Networks, Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS'02), p.171, July 02-05, 2002
• 34: Alec Woo , David E. Culler, A transmission control scheme for media access in sensor networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.221-235, July 2001, Rome, Italy [doi>10.1145/381677.381699]
• 35: Jie Wu , Hailan Li, On calculating connected dominating set for efficient routing in ad hoc wireless networks, Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications, p.7-14, August 20-20, 1999, Seattle, Washington, United States [doi>10.1145/313239.313261]
• 36: W. Ye, J. Heidemann, and D. Estrin. An Energy-Efficient MAC protocol for Wireless Sensor Networks. In Proceedings of IEEE INFOCOM, pages 1567--1576, New York, NY, USA, June 2002.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Theory

Keywords:
ad-hoc networks, asynchronous wake-up, clustering, distributed algorithms, dominating set algorithms, initialization, sensor networks