A Consensus-Based Leader Election Algorithm for Wireless Ad Hoc Networks

In a distribution computing system or mobile network, leader election is a very important issue. A leader is responsible of making sure the synchronization between different devices. In addition, a leader would assure the responsibility of dispatching IP, updating routing information and service list. The Bully election algorithm is one of the well-known leader election algorithms. Its drawbacks are message passing cost and complexity. Many modified Bully algorithms have been proposed to reduce the redundancy of the election process and the number of message passing. However, their modifications did not take group consensus into consideration. Thus, they can't handle the problem of having more than one node declare to be the leader. In this paper, we propose a consensus-based leader election algorithm. By analyzing the mathematic analysis and algorithm simulation results, we notice that, when a new leader is elected, the proposed algorithm guarantees a consensus be reached while at the same time reducing the number of message passing.