Leader election algorithms for mobile ad hoc networks

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

1. 1.H. Attiya and J. L. Welch. Distributed Computing: Fundamentals, Simulations and Advanced Topics. London, UK: McGraw-Hill, 1998.
2. 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. 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. 4.Kostas P. Hatzis, George P. Pentaris, Paul G. Spirakis, Vasilis T. Tampakas and Richard B. Tan. Fundamental Control Algorithms in Mobile Networks. Proc. 11th Annual ACM Symposium on Parallel Algorithms and Architectures, pages 251-260, 1999.
5. 5.Vincent D. Park and M. Scott Corson. A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks. Proc. IEEE INFOCOM, April 7-11, 1997.
6. 6.Elizabeth M. Royer and Charles E. Perkins. Multicast Operations of the Ad-hoc On-Demand Distance Vector Routing Protocol. Proc. Fifth Annual A CM/IEEE International Conference on Mobile Computing and Networking (MOBICOM), pages 207-218, August 15-20, 1999.
7. 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).

Index Terms

• Computer systems organization

  • Dependable and fault-tolerant systems and networks

• General and reference

  • Cross-computing tools and techniques

    • Performance

• Networks

  • Network performance evaluation

  • Network types

    • Mobile networks

    • Wireless access networks

• Theory of computation

  • Design and analysis of algorithms

    • Approximation algorithms analysis

      • Routing and network design problems