Distributed algorithms for mobile ad hoc networks

Abstract

We first 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 (Park and Corson, 1997), which in turn is based on an algorithm by Gafni and Bertsekas (1981). The algorithms require nodes to communicate only with their current neighbors, making them 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. Next we present several distributed algorithms that cause a token to continually circulate through all the nodes of a mobile ad hoc network. An important application of such algorithms is to ensure total order (Birman and Van Renesse, 1994) of message delivery in a group communication service. Some of the proposed algorithms are aware of, and adapt to, changes in the ad hoc network topology. When using a token circulation algorithm, a round is said to complete when every node has been visited at least once. Criteria for comparing the algorithms include the average time required to complete a round, number of bytes sent per round, and number of nodes visited per round. Comparison between the proposed algorithms is performed using simulation results obtained from a detailed simulation model (with ns-2 simulator).