ICAASE'2014 A Highly Adaptive Leader Election Algorithm for Mobile Ad Hoc Networks A Highly Adaptive Leader Election Algorithm for Mobile Ad Hoc Networks Leila MELIT Nadjib Badache Computer Science Department, University of Bejaia, Laboratory of Computer Systems, USTHB, 06000 Bejaia, Algeria Algiers, Algeria. melitleila@yahoo.fr badache@mail.cerist.dz Abstract – Leader election has been identified as a basic building block in distributed computing. MANETs are distinct from traditional distributed systems as they are dynamic and self-organizing networks because of their dynamic wireless link formation and removal, network partitioning and disconnections, limited bandwidth and energy and highly variable message delay. These characteristics makes the design of leader election protocols even more challenging than in classical distributed networks. In this paper, we present a leader election algorithm taking into account irregular topologies and mobility of the nodes. This algorithm elects as leader the node with the highest priority among the nodes in its connected component, where priority can be defined in a variety of ways. The paper also presents proofs of correctness to exhibit the fairness of this algorithm. Keywords – leader election, mobile ad hoc networks, priority each with a priority, after a finite number of 1. INTRODUCTION topological changes, every connected component will eventually select a unique leader, The leader election problem [1] is one of the which is the node of the highest priority from fundamental problems in distributed computing. It among the nodes in that component”. has been widely studied since one reason for this The aim of this paper is to propose a higher wide interest is that many wired and wireless priority index–finding algorithm that can work in distributed protocols need an election protocol. highly dynamic and asynchronous mobile ad hoc For example, it is required in group networks. communication service [2] key distribution and management [3] [4] and routing coordination [5]. The rest of this paper is organized as follows: the next section describes our leader election In the context of mobile ad hoc networks, link algorithm for mobile ad hoc networks. The changes are common and may cause the correctness proof of the algorithm is given in network to split into multiple connected Section 3 and Section 4 concludes this paper. components. Additionally, two connected components, each with its own leader, may merge. Moreover, in many situations, it may be 2. LEADER ELECTION ALGORITHM desirable to elect a leader with some system- related characteristic as mentioned in [6]. Figure1 shows our algorithm proposed to solve Therefore, the elected leader should be the node the election problem in mobile ad hoc networks. which has the highest priority from among all Each mobile node of our system has two nodes in its connected component, where the possible states: leader or candidate. A node priority of a node is a performance–related passes in candidate state if it receives a leader characteristic such as the node’s battery life, message from a node with higher priority. But it computational capabilities, etc. Thus, the can return to leader state when it detects the requirements for a leader election algorithm departure of its leader. becomes: “Given a network of mobile nodes International Conference on Advanced Aspects of Software Engineering ICAASE, November, 2-4, 2014, Constantine, Algeria. 181 ICAASE'2014 A Highly Adaptive Leader Election Algorithm for Mobile Ad Hoc Networks 1. Leader IDi ← IDi; 2. LeaderPriorityi ← Priorityi; 3. Statei ← leader; 4. IDElecMobilei ← 0; 5. IDElecLeaderi ← IDElecMobilei; 6. Start Timeri; 7. Broadcast leader (LeaderIDi, LeaderPriorityi, IDElecLeaderi); 8. Upon expiration of timeri do 9. If (Statei = candidate) then 10. Leader IDi ← IDi; 11. LeaderPriorityi ← Priorityi; 12. Statei ← leader; 13. IDElecMobilei ← IDElecMobilei + 1; 14. IDElecLeaderi ← IDElecMobilei; 15. Broadcast leader (LeaderIDi, LeaderPriorityi, IDElecLeaderi); 16. Restart Timeri; 17. Upon reception of message Leader (LeaderIDj, LeaderPriorityj, IDElecLeaderj) do 18. If (LeaderPriorityi < LeaderPriorityj) or ((LeaderPriorityi = LeaderPriorityj) and (LeaderIDi > LeaderIDj)) then 19. LeaderIDi ← LeaderIDj; 20. LeaderPriorityi ← LeaderPriorityj; 21. IDElecLeaderi ← IDElecLeaderj; 22. If (Statei = leader) then 23. Statei ←candidate; 24. Broadcast leader (LeaderIDj, LeaderPriorityj, IDElecLeaderj); 25. Restart Timeri; 26. Else 27. If ((LeaderPriorityi=LeaderPriorityj) and (LeaderIDi=LeaderIDj) and (IDElecLeaderi < IDElecLeaderj)) then 28. IDElecLeaderi ← IDElecLeaderj; 29. Broadcast leader (LeaderIDj, LeaderPriorityj, IDElecLeaderj); 30. Restart Timeri; Figure 1: A highly adaptive leader election algorithm for mobile ad hoc networks. The competition takes place only between nodes • LeaderIDi: indicates the leader’s identifier that are in a leader state. Each node that lost becomes in the candidate state. Our algorithm • LeaderPriorityi: integer; indicates the ensures the leader of each connected priority of the leader. component to be the unique node in its • Statei: indicates the state of the mobile connected component in leader state. The other node i. It can take two possible values: nodes in its connected component must be in Leader or candidate. candidate state. • Timeri: represents the maximum delay Assumptions on system, mobile nodes and that pi expects until it receives a message networks are: from the leader of the connected • Each node has unique identifier that is component that it belongs. fixed throughout the node’s lifetime. • IDElecmobilei: indicates the identifier of • Each node has a priority associated with the latest leader message originated by i. it. The priority of a node indicates its • IDElecLeaderi: indicates the identifier of “attractiveness” as a leader of the the latest leader message originated by network, and can be any performance– the leader of i. related attribute. We say that the leader of a node i is lower Each node pi maintains the following data priority than j’s one if and only if: structures: (LeaderPriorityi < LeaderPriorityj) or • IDi: indicates the identifier of the node. ((LeaderPriorityi = LeaderPriorityj) and (LeaderIDi > LeaderIDj)). • Priorityi: indicates the priority of the node. International Conference on Advanced Aspects of Software Engineering ICAASE, November, 2-4, 2014, Constantine, Algeria. 182 ICAASE'2014 A Highly Adaptive Leader Election Algorithm for Mobile Ad Hoc Networks When a node triggers an election, it elects itself, (LeaderIDNmax, LeaderPriorityNmax, informs its neighbors and starts its timer. The IDElecLeaderNmax). expiration of the timer for a node in the leader state means that it hasn’t received a leader Proof: message from a node with higher priority. So it Lemma 1 means that after time t> T, node Nmax continues its participation in the competition by will not receive any message leader (LeaderIDj, sending a leader message containing its LeaderPriorityj, IDElecLeaderj) such as information. However, the node in the candidate (LeaderPriorityj > LeaderPriorityNmax) or state, when its timer expires, it realizes that the ([LeaderPriorityNmax = LeaderPriorityj] and leader is absent and triggers a new election. [LeaderIDj < Nmax]). Therefore, it will not Each node i upon receiving a message Leader execute the lines (17-25) of the algorithm, and (LeaderIDj, LeaderPriorityj, IDElecLeaderj) the property leaderNmax = Nmax is always compares the priority of its leader with the priority satisfied at every time t> T. To see that it is of LeaderIDj indicated by LeaderPriorityj. If its satisfied, we distinguish the following cases: leader priority is the lowest, it updates its Case 1: There was no node i in the Nmax’s information by those transported by the received component such as (LeaderPriorityi > leader message, turns its state to candidate only LeaderPriorityNmax) or ((LeaderPriorityNmax = if it was in the Leader state, restart its timer and LeaderPriorityi) and (LeaderIDi < Nmax)). In this rebroadcast the same message received. If the case, lines (17-25) of Task 1 had never been leaders of the nodes i and j have the same executed by the node Nmax. LeaderNmax = priority, but IDElecLeaderi < IDElecLeaderj, then Nmax is always satisfied and will always be the node i puts its IDElecLeaderi to satisfied at every time t> T. IDElecLeaderj, rebroadcasts the same message that had received and restarts its timer. The Case 2: There was at least one node i in the comparison between IDElecLeaderi and component such that (LeaderPriorityi > IDElecLeaderj allows the algorithm to drop old LeaderPriorityNmax) or ((LeaderPriorityNmax = messages. LeaderPriorityi) and (LeaderIDi < Nmax)) which sent periodically the message leader (LeaderIDi, Our algorithm is can tolerate node mobility, LeaderPriorityi, IDElecLeaderi) by executing line network partitioning and merging components. 15 of the algorithm. In this case, leaderIDNmax = For example, if the leader breaks down, then i has been satisfied after execution of Line 19. after a bounded time, each node detecting the Then, after a finite number of topology changes leader departure elects itself as leader and (after a time t> T), the node i (and definitely all broadcasts its identifier with its priority (lines 8- nodes that are higher priority than Nmax) left the 16). If this failure causes partitioning of the component or crashed. Therefore, Nmax component in two other components, each becomes the node that has the highest priority in component will have eventually a unique leader. its component. We distinguish two sub cases. Moreover, if a node other than the leader breaks down and causes the partitioning of the a. After time t> T, the node Nmax will not component, then nothing will change in the receive any message leader (LeaderIDi, component that contains the leader, but the other LeaderPriorityi, IDElecLeaderi) such as component elects a new leader and its identifier (LeaderPriorityi > LeaderPriorityNmax) or is propagated throughout that component. The ((LeaderPriorityNmax = LeaderPriorityi) and detection of partition from the leader is (LeaderIDi < Nmax)). So, lines 19-25 will not be guaranteed by the use of the timer. executed, the timer will not be restarted at line 25 and it will finally expired (line 8) and leaderIDNmax = Nmax will be satisfied (line 10). 3. CORRECTESS b. After time t> T, node Nmax receives a We assume that T is the moment when the message leader (LeaderIDi, LeaderPriorityi, topology becomes static. We also assume that IDElecLeaderi). It is an old message originated Nmax is the node that has the highest priority by node i and is still circulating in the component value in its component. The following theorems after the departure of i. But when the node Nmax establish the correctness of the leader election receives this message for the second time, algorithm proposed above. condition in line 27 will never be satisfied (because IDElecLeaderi is the same for the two Lemma 1. There is a time after which Nmax messages) and so lines 28-30 will not be permanently satisfies that leaderNmax = Nmax executed. Therefore, Nmax will not restart its and broadcasts periodically a message leader timer, this later will expire. Consequently, lines International Conference on Advanced Aspects of Software Engineering ICAASE, November, 2-4, 2014, Constantine, Algeria. 183 ICAASE'2014 A Highly Adaptive Leader Election Algorithm for Mobile Ad Hoc Networks 8-16 will be executed and leaderIDNmax shows that no other message will circulate into becomes Nmax. the component. So the only message that is circulating is the message leader Finally, as leaderIDNmax = Nmax, Nmax (LeaderIDNmax, LeaderPriorityNmax, broadcasts permanently and periodically the IDElecLeaderNmax) and all nodes of the message leader (LeaderIDNmax, component have Nmax as a leader. LeaderPriorityNmax, IDElecLeaderNmax). So, the algorithm ensures that: Lemma 2. There is a time after which every message leader (p, LeaderPriorityp, For each component C in ad hoc network, there IDElecLeaderp) with p ≠ Nmax disappears from is a node Nmax in C and a moment after which, the system. for every node p in C, leader p = Nmax which is the node of the highest priority in C. Proof: Note that initially, each node p begins the execution by electing itself as leader. i.e., 4. CONCLUSION leaderIDp = p (line 1). As long as it remains In this paper, we have proposed a leader election leader, it broadcasts leader (LeaderIDp, algorithm for ad hoc networks that can tolerate LeaderPriorityp, IDElecLeaderp) (line 15). Also intermittent failures, such as link failures, sudden note that each node p on receipt of each crash or recovery of mobile nodes, network message leader (LeaderIDj, LeaderPriorityj, partitions, and merging of connected network IDElecLeaderj), makes leaderp = j if j is higher components. This algorithm ensures that every priority than p (lines 17-25). connected component will eventually select a At a time t> T, Nmax is the node that has the unique leader having the highest priority. To elect highest priority value in its component and it a unique leader, the algorithm requires mobile periodically broadcasts the message leader nodes to communicate only with their immediate (LeaderIDNmax, LeaderPriorityNmax, neighbors. Our future plan is to simulate the IDElecLeaderNmax) (Lemma 1). Each node p ≠ algorithm to study self-stabilization propriety Nmax, upon receipt of this message makes witch is very important in mobile computing. leaderIDp = Nmax (line 19) and sends leader (LeaderIDNmax, LeaderPriorityNmax, IDElecLeaderNmax) to all its neighbours as 5. REFERENCES shown on line 24 of the algorithm. [1] N. Lynch, “Distributed algorithms”, Morgan Kaufmann Publishers, 1996. After time t> T, the timer of p will not expire as Nmax periodically broadcasts the message [2] G.-C. Roman, Q. Huang, and A. Hazemi, leader (LeaderIDNmax, LeaderPriorityNmax, “Consistent group membership in ad hoc networks”, Proceeding of the 23rd IDElecLeaderNmax). So p will never execute line International Conference on Software 15 of the algorithm (the message leader Engineering (ICSE ’01), 2001, pp. 381-388. (LeaderIDp, LeaderPriorityp, IDElecLeaderp) will [3] N. Asokan and P. Ginzboorg, “Key never be sent). agreement in ad hoc networks”, Computer Comm., vol. 23, no. 17, 2000, pp. 1627- Finally, every message leader (LeaderIDp, 1637. LeaderPriorityp, IDElecLeaderp) with p ≠ Nmax was disappeared from the system. [4] B. Lehane, L. Dolye, and D. O’Mahony, “Ad hoc key management infrastructure”, Theorem. There is a time after which each Proceedings of the International Conference node p in the same component have on Information Technology: Coding and Computing (ITCC ’05), vol. 2, 2005, pp. 540- leaderNmax = Nmax, where Nmax is the node 545. that has the highest priority value in that component. [5] C. Perkins and E. Royer, “Ad-hoc On- Demand Distance Vector Routing”, Proof: Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Lemma 1 shows that there is a moment after Applications, New Orleans, LA, February which the node Nmax maintains leaderNmax = 1999, pp. 90-100. Nmax (ie it is the leader of its component) and [6] S. Vasudevan, J. Kurose, and D. Towsley, periodically broadcasts the message leader “Design and analysis of a leader election (LeaderIDNmax, LeaderPriorityNmax, algorithm for mobile ad hoc networks”, IDElecLeaderNmax) to notify the other nodes in Proceedings of the 12th IEEE International Conference on Network Protocols its component that it is the leader. Lemma 2 (ICNP’04), Octobre 2004, pp. 350-360. International Conference on Advanced Aspects of Software Engineering ICAASE, November, 2-4, 2014, Constantine, Algeria. 184