Leader election algorithms for mobile ad hoc networks

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

Leader election algorithms for mobile ad hoc networks

Full text

Pdf (827 KB)

Source

Workshop on Discrete Algothrithms and Methods for MOBILE Computing and Communications archive
Proceedings of the 4th international workshop on Discrete algorithms and methods for mobile computing and communications table of contents

Boston, Massachusetts, United States

Pages: 96 - 103

Year of Publication: 2000

ISBN:1-58113-301-4

Authors

Navneet Malpani	Dept. of Computer Science, Texas A&M University, College Station, TX
Jennifer L. Welch	Dept. of Computer Science, Texas A&M University, College Station, TX
Nitin Vaidya	Dept. of Computer Science, Texas A&M University, College Station, TX

Sponsors

SIGMOBILE: ACM Special Interest Group on Mobility of Systems, Users, Data and Computing
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 12, Downloads (12 Months): 163, Citation Count: 26

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:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/345848.345871 What is a DOI?

ABSTRACT

We present two new leader election algorithms for mobile ad hoc networks. The algorithms ensure that eventually each connected component of the topology graph has exactly one leader. The algorithms are based on a routing algorithm called TORA [5], which in turn is based on an algorithm by Gafni and Bertsekas [3]. The algorithm require nodes to communicate with only their current neighbors, making it well suited to the ad hoc environment. The first algorithm is for a single topology change and is provided with a proof of correctness. The second algorithm tolerates multiple concurrent topology changes.

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	Jennifer L. Welch , Hagit Attiya, Distributed computing: fundamentals, simulations and advanced topics, McGraw-Hill, Inc., Hightstown, NJ, 1998
	2	Chunhsiang Cheng and Srikanta P. R. Kumar. A Loop-Free Spanning-Tree Protocol in Dynamic Topology. Proc. ~7th Annual Allerton Conference on Communication, Control and Computing, Sept. 1989, pp. 594-595.
	3	E. Gafni and D. Bertsekas. Distributed algorithms for generating loop-free routes in networks with frequently changing topology. IEEE Transactions on Communications, C-29(1):11-18, 1981.
	4	Kostas P. Hatzis , George P. Pentaris , Paul G. Spirakis , Vasilis T. Tampakas , Richard B. Tan, Fundamental control algorithms in mobile networks, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.251-260, June 27-30, 1999, Saint Malo, France [doi>10.1145/305619.305649]
	5	Vincent D. Park , M. Scott Corson, A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.1405, April 09-11, 1997
	6	Elizabeth M. Royer , Charles E. Perkins, Multicast operation of the ad-hoc on-demand distance vector routing protocol, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.207-218, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313538]
	7	Elizabeth M. Royer, Samir R. Das and Charles E. Perkins. Ad Hoc On-Demand Distance Vector (AODV) Routing (Internet-Draft). Mobile Ad Hoc Network (MANET) Working Group, 10 March, 2000 (work in progress).

CITED BY 26

	Emmanuelle Anceaume , Ajoy K. Datta , Maria Gradinariu , Gwendal Simon, Publish/subscribe scheme for mobile networks, Proceedings of the second ACM international workshop on Principles of mobile computing, October 30-31, 2002, Toulouse, France
	Ioannis Chatzigiannakis , Sotiris Nikoletseas , Paul Spirakis, Distributed communication algorithms for ad hoc mobile networks, Journal of Parallel and Distributed Computing, v.63 n.1, p.58-74, January 2003
	Lali Barrière , Paola Flocchin , Pierre Fraigniau , Nicola Santor, Can we elect if we cannot compare?, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA
	Costas Busch , Srikanth Surapaneni , Srikanta Tirthapura, Analysis of link reversal routing algorithms for mobile ad hoc networks, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA
	Saurabh Ganeriwal , Ram Kumar , Mani B. Srivastava, Timing-sync protocol for sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA
	Ioannis Chatzigiannakis , Sotiris Nikoletseas, Design and analysis of an efficient communication strategy for hierarchical and highly changing ad-hoc mobile networks, Mobile Networks and Applications, v.9 n.4, p.319-332, August 2004
	Djibo Karimou , Jean Frédéric Myoupo, An Application of an Initialization Protocol to Permutation Routing in a Single-Hop Mobile Ad Hoc Networks, The Journal of Supercomputing, v.31 n.3, p.215-226, March 2005
	K. Shashi Prabh , Tarek F. Abdelzaher, Energy-conserving data cache placement in sensor networks, ACM Transactions on Sensor Networks (TOSN), v.1 n.2, p.178-203, November 2005
	Vlady Ravelomanana, Extremal Properties of Three-Dimensional Sensor Networks with Applications, IEEE Transactions on Mobile Computing, v.3 n.3, p.246-257, July 2004
	Chun-Ta Li , Min-Shiang Hwang , Chi-Yu Liu, An electronic voting protocol with deniable authentication for mobile ad hoc networks, Computer Communications, v.31 n.10, p.2534-2540, June, 2008
	Maria Halkidi , Dimitris Papadopoulos , Vana Kalogeraki , Dimitrios Gunopulos, Resilient and energy efficient tracking in sensor networks, International Journal of Wireless and Mobile Computing, v.1 n.2, p.87-100, February 2006
	Yu Chen , Jennifer L. Welch, Self-stabilizing dynamic mutual exclusion for mobile ad hoc networks, Journal of Parallel and Distributed Computing, v.65 n.9, p.1072-1089, September 2005
	S. Subramaniam , T. Palpanas , D. Papadopoulos , V. Kalogeraki , D. Gunopulos, Online outlier detection in sensor data using non-parametric models, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
	Azzedine Boukerche , Kaouther Abrougui, An efficient leader election protocol for mobile networks, Proceeding of the 2006 international conference on Communications and mobile computing, July 03-06, 2006, Vancouver, British Columbia, Canada
	Fabrice Theoleyre , Fabrice Valois, A self-organization structure for hybrid networks, Ad Hoc Networks, v.6 n.3, p.393-407, May, 2008
	Christian Seitz , Michael Berger , Bernhard Bauer, Towards a general approach to mobile profile based distributed grouping, Personal and Ubiquitous Computing, v.9 n.2, p.90-99, March 2005
	Gruia-Catalin Roman , Jamie Payton, A Termination Detection Protocol for Use in Mobile Ad Hoc Networks, Automated Software Engineering, v.12 n.1, p.81-99, January 2005
	Abdelouahid Derhab , Nadjib Badache, Self-stabilizing algorithm for high service availability in spite of concurrent topology changes in ad hoc mobile networks, Journal of Parallel and Distributed Computing, v.68 n.6, p.752-768, June, 2008
	Daniel Augot , Raghav Bhaskar , Valérie Issarny , Daniele Sacchetti, A three round authenticated group key agreement protocol for ad hoc networks, Pervasive and Mobile Computing, v.3 n.1, p.36-52, January, 2007
	Zvi Lotker , Alfredo Navarra, Grid emulation for managing random sensor networks, Ad Hoc Networks, v.6 n.6, p.900-908, August, 2008
	Tanya L. Crenshaw , Spencer Hoke , Ajay Tirumala , Marco Caccamo, Robust implicit EDF: A wireless MAC protocol for collaborative real-time systems, ACM Transactions on Embedded Computing Systems (TECS), v.6 n.4, p.28-es, September 2007
	Nikolaos Liveris , Hai Zhou , Robert P. Dick , Prithviraj Banerjee, State space abstraction for parameterized self-stabilizing embedded systems, Proceedings of the 7th ACM international conference on Embedded software, October 19-24, 2008, Atlanta, GA, USA
	Chien-Fu Cheng , Shu-Ching Wang , Tyne Liang, Byzantine Agreement & Fault Diagnosis Agreement in Dynamic Ad-Hoc Environment, Fundamenta Informaticae, v.89 n.2-3, p.161-187, January 2009
	Shancang Li , Xinheng Wang , Deyun Zhang, An adaptive distributed localisation in wireless sensor network, Enterprise Information Systems, v.3 n.2, p.117-132, May 2009
	Mikel Larrea , Cristian Martin , Jose Javier Astrain, Fault-tolerant aggregator election and data aggregation in wireless sensor networks, International Journal of Communication Networks and Distributed Systems, v.3 n.2, p.93-115, June 2009
	Bernadette Charron-Bost , Antoine Gaillard , Jennifer Welch , Josef Widder, Routing without ordering, Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures, August 11-13, 2009, Calgary, AB, Canada