Since the choice of the leader has an impact on the performance of algorithms using the leader election service, a Ω algorithm must take into account the average number of hops to reach the leader. Hence, the ideal would be to elect a non-faulty node with the best network centrality. To this end, each node could maintain a knowledge of the network topology.
This thesis thus proposes two eventual leader election algorithms, denoted Topology Aware and Centrality-based Eventual Leader (CEL), for MANETs considering partial synchronous system and network partitions. Nodes can move, fail by crash, join and leave the system. Initially, nodes only know their respective identity, and, by exchanging messages with neighbor nodes in their transmission range, they acquire knowledge of the network topology. The algorithms exploit this knowledge to eventually elect one leader per connected component of the network with the best closeness centrality. The Topology Aware algorithm considers reliable channels, while the CEL algorithm tolerates message loss, interference and collisions. Furthermore, CEL implements a cross-layer mechanism and a probabilistic gossip to reduce the number of sent messages and increase the stability of the algorithm.
To the best of my knowledge, no other Ω algorithm for dynamic networks in the literature uses the closeness centrality as a criterion to choose the eventual leader.
The first proposed algorithm, denoted Topology Aware, assumes reliable communication links with an underlying probe system to detect connection and disconnection of nodes. An incremental update mechanism is used to improve propagation cost of messages over the network.
Experiments were conducted on the PeerSim simulator [MJ09], comparing our algorithm to a flooding leader algorithm [VKT04] with Random Waypoint and a periodic single point of interest mobility models. Performance results show that the Topology Aware algorithm outperforms the flooding one considering leader choice stability, number of messages, and average distance to the leader metrics.
The first contribution assumes reliable communication channels, which are not suitable for communication environments prone to interference and message collisions. The second proposed eventual leader election algorithm for dynamic networks is the Centrality-based Eventual Leader (CEL), that, similarly to Topology Aware, exploits topological information to improve the choice of a central leader and reduce message exchanges. However, rather than assuming an underlying probe system, CEL has a cross-layer neighbors detection, with a neighbor-aware mechanism, to improve the dissemination of topological knowledge and elect a central leader faster. It uses a self-pruning mechanism based on the topological knowledge, combined with probabilistic gossip, to improve the performance of information propagation.
Evaluations were conducted on the OMNeT++/INET environment [VH08; MVK19], simulating realistic MANET following the IEEE 802.11n specifications with interference, collision, and messages loss. CEL was compared to Gómez-Calzado et al. algorithm [Góm+13], with Random Walk and Truncated Lévy Walk mobility models. Results show that CEL presents better performance than the latter, including fewer message exchanges, shortest paths to the leader, and better stability.