Birthday protocols for low energy deployment and flexible neighbor discovery in ad hoc wireless networks

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Birthday protocols for low energy deployment and flexible neighbor discovery in ad hoc wireless networks

Full text

Pdf (647 KB)

Source

International Symposium on Mobile Ad Hoc Networking & Computing archive
Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing table of contents

Long Beach, CA, USA

Session: Sensor networks and energy management table of contents

Pages: 137 - 145

Year of Publication: 2001

ISBN:1-58113-428-2

Authors

Michael J. McGlynn	Laboratory for Telecommunications Sciences, 2800 Powder Mill Road, Adelphi, MD
Steven A. Borbash	Laboratory for Telecommunications Sciences, 2800 Powder Mill Road, Adelphi, MD

Sponsor

SIGMOBILE: ACM Special Interest Group on Mobility of Systems, Users, Data and Computing

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 12, Downloads (12 Months): 72, Citation Count: 14

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	10.1145/501431.501435

ABSTRACT

In this paper, we address two problems associated with static ad hoc wireless networks; methods of saving energy during a deployment of the nodes, and efficient methods of performing adjacent neighbor discovery. To meet these goals we introduce a family of "birthday protocols"which use random independent transmissions to discover adjacent nodes. Various modes of the birthday protocol are used to solve the two problems. We provide a mathematical model and analysis of two modes of the protocol and are led to a third mode which is the probabilistic analog of the deterministic round robin scheduling algorithm. We show by analysis and simulation that the birthday protocols are a promising tool for saving energy during the deployment of an ad hoc network as well as an efficient and flexible means of having the nodes discover their neighbors

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	D.B. Johnson and D.A. Maltz. Mobile Computing, chapter 5, Dynamic Source Routing in Ad Hoc Wireless Networks, pages 153-181. Kluwer Publishing Company, 1996.
	2	Charles E. Perkins , Elizabeth M. Royer, Ad-hoc On-Demand Distance Vector Routing, Proceedings of the Second IEEE Workshop on Mobile Computer Systems and Applications, p.90, February 25-26, 1999
	3	Z.J. Haas and M.R. Pearlman. The zone routing protocol (zrp) for ad hoc networks. Internet Draft, Internet Engineering Task Force, November 1997.
	4	Terry Todd , Frazer Bennett , Alan Jones, Low power rendezvous in embedded wireless networks, Proceedings of the 1st ACM international symposium on Mobile ad hoc networking & computing, November 20, 2000, Boston, Massachusetts
	5	Dennis J. Baker and Anthony Ephremides. The architectural organization of a mobile radio network via a distributed algorithm. IEEE Transactions on Communications, COM-29 (11):1694-1701, November 19 1981.
	6	Chunhung Richard Lin and Mario Gerla. Adaptive clustering for mobile wireless networks. IEEE J. Selected Areas of Communications, 15(7):1265-1275, Sept. 1997.
	7	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]
	8	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
	9	Yu-Liang Chang , Ching-Chi Hsu, Routing in wireless/mobile ad-hoc networks via dynamic group construction, Mobile Networks and Applications, v.5 n.1, p.27-37, March 2000 [doi>10.1023/A:1019175605040]
	10	R. G. Gallager , P. A. Humblet , P. M. Spira, A Distributed Algorithm for Minimum-Weight Spanning Trees, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.1, p.66-77, Jan. 1983 [doi>10.1145/357195.357200]
	11	Bluetooth project, www.bluetooth.com, 1999.
	12	S. Ramanathan and R. Rosales-Hain. ,topology control of multihop radio networks using transmit power adjustmenC. In Proc. IEEE Infocom 2000, Tel Aviv, Mar 2000.
	13	K. Sohrabi and G. J. Pottie. Performance of a novel self-organization protocol for wireless ad-hoc sensor networks,. In IEEE Vehicular Technology Conference: 1999, volume 2, pages 1222-1226, Fall 1999.
	14	Ya Xu, John Heidemann, and Deborah Estrin. Adaptive energy-conserving routing for multihop ad hoc networks. Research Report 527, USC/Information Sciences Institute, October 2000.
	15	J. L. Bordim, J. Cui, T. Hayashi, K. Nakano, and S. Olariu. ,energy-efficient initialization protocols for ad-hoc radio networks". IEICE Trans. Fundamentals, E-83-A(9):1796-1803, Sept. 2000.
	16	A. Chandrakasan. Low power wireless sensor networks. Mobicom 2000, Presentation on energy conservation methods.
	17	Intersil Corporation. Hfa3683a data sheet. Technical report, Intersil, October 1999. File Number 4634.3.

CITED BY 14

	Curt Schurgers , Vlasios Tsiatsis , Saurabh Ganeriwal , Mani Srivastava, Topology management for sensor networks: exploiting latency and density, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland
	Curt Schurgers , Vlasios Tsiatsis , Saurabh Ganeriwal , Mani Srivastava, Optimizing Sensor Networks in the Energy-Latency-Density Design Space, IEEE Transactions on Mobile Computing, v.1 n.1, p.70-80, January 2002
	Katayoun Sohrabi , William Merrill , Jeremy Elson , Lewis Girod , Fredric Newberg , William Kaiser, Methods for Scalable Self-Assembly of Ad Hoc Wireless Sensor Networks, IEEE Transactions on Mobile Computing, v.3 n.4, p.317-331, October 2004
	Curt Schurgers , Gautam Kulkarni , Mani B. Srivastava, Distributed On-Demand Address Assignment in Wireless Sensor Networks, IEEE Transactions on Parallel and Distributed Systems, v.13 n.10, p.1056-1065, October 2002
	Thomas Moscibroda , Roger Wattenhofer, Coloring unstructured radio networks, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA
	Shih-Lin Wu , Pao-Chu Tseng , Zi-Tsan Chou, Distributed power management protocols for multi-hop mobile ad hoc networks, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.47 n.1, p.63-85, 14 January 2005
	Elyes Ben Hamida , Guillaume Chelius , Eric Fleury, Revisiting neighbor discovery with interferences consideration, Proceedings of the 3rd ACM international workshop on Performance evaluation of wireless ad hoc, sensor and ubiquitous networks, October 06-06, 2006, Terromolinos, Spain
	Steven A. Borbash , Anthony Ephremides , Michael J. McGlynn, An asynchronous neighbor discovery algorithm for wireless sensor networks, Ad Hoc Networks, v.5 n.7, p.998-1016, September, 2007
	Matthew J. Miller , Nitin H. Vaidya, Ad hoc routing for multilevel power save protocols, Ad Hoc Networks, v.6 n.2, p.210-225, April, 2008
	Andreas Meier , Mischa Weise , Jan Beutel , Lothar Thiele, NoSE: efficient initialization of wireless sensor networks, Proceedings of the 6th ACM conference on Embedded network sensor systems, November 05-07, 2008, Raleigh, NC, USA
	Prabal Dutta , David Culler, Practical asynchronous neighbor discovery and rendezvous for mobile sensing applications, Proceedings of the 6th ACM conference on Embedded network sensor systems, November 05-07, 2008, Raleigh, NC, USA
	Luke Ritchie , Sapna Deval , Martin Reisslein , Andrea W. Richa, Evaluation of physical carrier sense based spanner construction and maintenance as well as broadcast and convergecast in ad hoc networks, Ad Hoc Networks, v.7 n.7, p.1347-1369, September, 2009
	Neeraj Mittal , Srinivasan Krishnamurthy , R. Chandrasekaran , S. Venkatesan , Yanyan Zeng, On neighbor discovery in cognitive radio networks, Journal of Parallel and Distributed Computing, v.69 n.7, p.623-637, July, 2009
	Shudong Fang , Stevan Mirko Berber , Akshya Kumar Swain, Characterization of hello message exchange for estimating distribution of network residual energy, Proceedings of the 2009 International Conference on Wireless Communications and Mobile Computing: Connecting the World Wirelessly, June 21-24, 2009, Leipzig, Germany