Chapter 5
Centrality-Based Eventual Leader Election in Dynamic Networks

This chapter proposes a new eventual leader election algorithm for dynamic systems, which implements a cross-layer neighbor detection, and a neighbor-aware mechanism that improves the sharing of topological knowledge, electing a central leader faster. Furthermore, in order to improve the performance of information propagation, the algorithm uses a topological knowledge based on a self-pruning mechanism combined with probabilistic gossip. Evaluations were conducted on the OMNeT++ [Var10] environment, simulating realistic MANET including interference, collision, and messages loss.

Nodes are mobile and communicate by sending messages over wireless links. The system membership is not known in advance. The communication graph can evolve over time, therefore, the network is not always fully connected but composed of one or more connected components. The algorithm chooses the leader according to a topological criterion: for every component, the leader is eventually the node having the best closeness centrality in the component. Each node progressively builds and maintains a local knowledge of the component communication graph. This knowledge is then used to locally determine a central leader, well located to be reached by a majority of processes.

The current chapter brings three main contributions:

1.

A new Centrality-based Eventual Leader election algorithm for dynamic systems, called CEL, where the leader eventually has the best centrality. CEL has a cross-layer neighbors detection which exploits the broadcast features of the underlying wireless network. The neighbor-aware mechanism improves the sharing of the topological knowledge and elects a central leader faster.

2.

CEL uses the topological knowledge through a self-pruning mechanism, combined with probabilistic gossip, to reduce global information propagation costs.

3.

An extensive evaluation on the OMNeT++ environment [Var10] using two mobility patterns to simulate Mobile Ad Hoc Network (MANET) with interference, collision, and messages loss. Comparison with the closest algorithm [Góm⁺13] shows that CEL has a good trade-off considering the number of messages exchanged, stability of the leader (i.e. the percentage of the average time that nodes adopt the expected leader), and the closeness of the leader to the other nodes.

Compared to the algorithm in the previous chapter, the system model of CEL assumes unreliable communication channels, which are suitable for realistic environments with interference and message collisions. Message loss is taken into account by the CSMA/CA protocol included in IEEE 802.11 [Com99]. Rather than assuming an underlying probe system, CEL uses a cross-layer mechanism to leverage already existing data link layer messages, and to access the MAC addresses of the nodes, which are used to construct the topological knowledge of the connected component. In addition, the topological knowledge is used to improve communication performance, and the sharing of this knowledge between nodes is optimized by taking advantage of the bidirectional links assumption (neighbor-aware mechanism), whereas in the previous chapter, the algorithm does not provide such mechanisms. Evaluation compare CEL with the Ω eventual leader election algorithm of Gómez-Calzado et al. [Góm⁺13], which also assumes eventually reliable communication channels and is more recent than Vasudevan et al. algorithm [VKT04]. Experiments use two more realistic mobility models: the Random Walk and the Truncated Lévy Walk.

The rest of the chapter is organized as follows: Section 5.1 presents the system model and assumptions, Section 5.2 describes the algorithm, Section 5.4 discusses performance results, and finally, a conclusion is given in Section 5.5.

Table of Contents