30-10-2009, 04:19 PM
[attachment=379]
Presented by:George Mathew
Preejesh B
Rajesh M K
Sreelesh V
LEADER ELECTION IN MOBILE AD HOC NETWORKS
Abstract
We implement a leader election algorithms for mobile ad hoc networks. The algorithms ensure that eventually each connected component of the topology graph has exactly one leader. The algorithms are based on a routing algorithm called TORA. The algorithms require nodes to communicate with only their current neighbors. The algorithm is for a single topology change.
Problem defenition
To implement a leader election algorithm for mobile ad hoc networks assuming that there is only a single topology change in the network at a time.
2 Introduction
An ad hoc network is often defined as an "infrastructureless" network, meaning a network without the usual routing infrastructure like fixed routers and routing backbones. Typically, the ad hoc nodes are mobile and the underlying communication medium is wireless. Each ad hoc node may be capable of acting as a router. Such ad hoc networks may arise in personal area networking, meeting rooms and conferences, disaster relief and rescue operations, battlefield operations, etc.
3 Motivation
Leader election is a useful building block in distributed systems, whether wired or wireless, especially when failures can occur. Leader election can also be used in group communica¬tion protocols, to choose a new coordinator when the group membership changes. Developing distributed algorithms for ad hoc networks is a very challenging task since the topology may change very frequently and unpredictably.
4 Literature Survey
4.1 Algorithm
• A.
When node i has no outgoing links due to a page link failure:
1. If node i has no incoming links as well then
2. lidi = i
3. (n , oidj, Ti) = ( - 1 , - 1 , - 1 )
4. Si := 0
5. else
6. (TJ, oidj , tj) = (t,i,0) // t is the current time
7. Si = 0
• B.
When node i has no outgoing links due to a page link reversal following reception of an Update message and the reference levels (TJ , oidj, r^) are not equal for all j eNf.
1. (n, oidj ,Ti) = m a x (TJ , oidj , Tj ) | jeNi
2. Si = minrj — j eNi and (r^oidj,^) = (r^oidj,^) - 1
• C.
When node i has no outgoing links due to a page link reversal following reception of an Update message and the reference levels (TJ , oidj, r^) are equal with tj = 0 for all j eNf
1. (Ti,oidi,rj) = (Tj,oid,-,l) for any j eNi
2. Si =0
• D.
When node i has no outgoing links due to a page link reversal following reception of an Update message and the reference levels ( tj , oidj , tj ) are equal with tj = 1 for all j eNi and oidj = i
1. lidi := i
2. (rj,oidi,ri) = (-1,-1,-1)
3. Si = 0
• E.
When node i receives an Update message from neighboring node j such that lidj ^ lidf
1. if lidj > lidj or (oid, = lidj and r, = 1) then
2. lidi = lid,-
3. (Ti ,oidi,ri) = (0,0,0)
4. Si = Sj + 1
In part E, if the new id is smaller than yours, then adopt it. If the new id is larger than yours, then adopt it, but only if it is the case that the originator of a new reference level has detected a partition and elected itself.
4.2 Correctness
We assume that each connected component is a leader-oriented DAG originally and that only one change (either a page link failure or a page link formation) can occur at a time. The next change occurs only after the entire network has recovered from the previous change. We also assume that the system is synchronous, i.e., the execution occurs in lock step rounds. Messages are sent at the beginning of each round and are received by the nodes to which they were sent before the end of each round.
4.2.1 Theorm 1
The algorithm ensures that each component eventually has exactly one unique leader. PROOF:
We consider the following three cases (the remaining cases cause no changes).
• Case 1: A page link disappears at time t, causing node i to lose its last outgoing page link but not disconnecting the component.
• Case 2: A page link appears at time t, joining two formerly separate components.
• Case 3: A page link disappears at time t, causing node i to lose its last outgoing page link and disconnecting the component. In each case we show that eventually each component in the resulting graph is a leader-oriented DAG.
In each case we show that eventually each component in the resulting graph is a leader-oriented DAG.
Let G be the directed graph representing the resulting topology (of the component). Let T be the leader of the component. Then the component was an 1-oriented DAG before the link
• Case 1: A page link disappears at time t, causing node i to lose its last outgoing page link but not disconnecting the component.
was lost. Let V; be the set of nodes that still have a path to I. At time t, the remaining nodes have a path to i; let this set be V;. Let G; be the graph induced by G*.
• DEFINITION 1.
The frontier nodes of V, are nodes that are adjacent to nodes in V; ; the edges between Vj and V; are the frontier edges. Let k be any node in V,.
• DEFINITION 2.
Level(k) is the length of the longest path in G, from k to i. Note that level is defined with respect to the fixed G*. Even though the direction of edges changes as the algorithm executes, the levels do not change.
LEMMA 1.
If k is on a path in G, from a frontier node to i, then k's final height is (l,t,i,0,-level ( k ) , k ) . Otherwise, k's final height is (1, t, i, 1, -diff (k), k), where diff ( k) =max level(h)/h ? Vj and k is reachable from h in G, -level(k).
PROOF.
We will show by induction on the number of rounds r after t that at the end of round r:
(a) If r j level(k), then k's height is the same as it was at time t.
(b) If k is on a path from a frontier node to i and r level(k), then k's height is (1, t, i, O, -level(k), k).
The following condition will arise which is different from the conditions in case 1. Let r 1 be equal to maxlevel(k)+2, dill(k) for all k adjacent to i. At round rl , the heights of all the adjacent nodes k will be (l,t,i,l,-diff(k),k) and node i will detect that a partition has occurred and will elect itself as the leader.
LEMMA 3.
At round rl a DAG with node i as the sink has already been formed. PROOF.
We know from the proof of case 1 that, when r i level(k) + 2. diff(k) for any node k other than i, node k has changed its height to (l,t,i,l, - diff(k),k) and has no outgoing page link towards node i. This height of k will not change when r i level(k) + 2. diff(k) and r j rl. Also when r = r 1 - 1, one of the nodes k which is adjacent to i will change its height to (1, t, i, l,-diff(k), k) and have on outgoing page link to node i. This node k will also be the last adjacent node of i to do so.
Thus at rl , when node i detects the partition, it changes its height to (1,-1,-1,-1,0,1) and sends an Update message to its neighbors. This message is propagated throughout the new component. The resulting graph is an i-oriented DAG. The proof for this is the same as the proof for Lemma 2.
Thus we see from all the three cases that our algorithm will eventually ensure that each component has exactly one unique leader.
