This chapter presents the first contribution of this thesis: an eventual leader election for Mobile Ad Hoc Networks (MANET), which exploits the knowledge that nodes maintain of the network in the decision of the leader choice. The mobile nodes communicate by transmitting messages over wireless links. Only nodes within the transmission range of each other can communicate directly with one another. Then, they can retransmit the message to other nodes. Thus, one or more intermediate nodes may act as relays. In such a network, the communication graph evolves: nodes can move, join and leave the system, fail, and recover at runtime. Due to these dynamics, the network may be partitioned, i.e. composed of two or more connected components. Initially, nodes have no knowledge of the system membership, learning about it during execution time.
As seen in Chapter 3, many works have proposed leader election algorithms in both static and dynamic distributed systems. However, among the latter, only a few of them take into account the above highly dynamic characteristics and membership lack of knowledge of MANET [Mos+05; MA+06; MB12]. Furthermore, in the majority of these algorithms, the choice of the leader is based on a beforehand criterion such as the lowest or the highest nonfaulty process identity. However, it is important that the criterion should take into account the impact that the choice of the leader may have on the performance of algorithms that use the leader election service. Performance-related criteria are, for instance, nodes remaining battery life, nodes computation capabilities, nodes topological position (e.g. the minimum average distance from a node to all other nodes), etc. Similarly to [VKT04], the most valued node denotes the one that best meets the performance-related criterion in question and, therefore, should be chosen as the leader. Hence:
The proposed algorithm is an eventual leader election algorithm called Topology Aware, which is based on the most valued node criterion and whose nodes have a global knowledge of the communication graph and its dynamic evolution, denoted topological knowledge. The algorithm progressively builds and maintains a local knowledge of the connected graph. It relies only on broadcasts within node transmission ranges and does not require any election communication phase: with both its current topological knowledge and choosing the most valued node, each node can directly deduce at any moment which node is the current leader. In particular, the topological knowledge makes the computation of the closeness centrality possible, as well as the election of per component central located leaders, which, thus, efficiently spread information across nodes of the component. Even if the problem of discovering network topology has been studied in various contexts [NT09; BO99], this approach has never been used to elect an eventual leader.
It is worth pointing out that even if the presented work target MANET, the Topology Aware algorithm has been designed for generic mobile dynamic systems.
The rest of the chapter is organized as follows: Section 4.1 explains the chosen model and assumptions, while Section 4.2 describes the algorithm. Section 4.4 discusses performance results and, finally, a conclusion is given in Section 4.5.