LEADER ELECTION IN MOBILE AD HOC NETWORKS
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
nit_cal
Active In SP
**

Posts: 237
Joined: Oct 2009
#1
30-10-2009, 04:19 PM



.pdf   Superthreading.pdf (Size: 196.38 KB / Downloads: 112)
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 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 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 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 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 link failure or a 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 link disappears at time t, causing node i to lose its last outgoing link but not disconnecting the component.
• Case 2: A link appears at time t, joining two formerly separate components.
• Case 3: A link disappears at time t, causing node i to lose its last outgoing 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 link disappears at time t, causing node i to lose its last outgoing 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 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 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.
Use Search at http://topicideas.net/search.php wisely To Get Information About Project Topic and Seminar ideas with report/source code along pdf and ppt presenaion
Reply
aswinanandpa
Active In SP
**

Posts: 1
Joined: Jul 2010
#2
17-07-2010, 10:00 PM

file is not related to super threading
Reply

Important Note..!

If you are not satisfied with above reply ,..Please

ASK HERE

So that we will collect data for you and will made reply to the request....OR try below "QUICK REPLY" box to add a reply to this page

Quick Reply
Message
Type your reply to this message here.


Image Verification
Please enter the text contained within the image into the text box below it. This process is used to prevent automated spam bots.
Image Verification
(case insensitive)

Possibly Related Threads...
Thread Author Replies Views Last Post
  Switching and Traffic Grooming in WDM Networks at java project topics 3 951 09-09-2016, 02:27 PM
Last Post: Dhanabhagya
  intel centrino mobile technology ppt jaseelati 0 272 05-01-2015, 04:49 PM
Last Post: jaseelati
  The Three-Tier Security Scheme in Wireless Sensor Networks with Mobile Sinks seminar flower 3 2,748 09-12-2014, 09:25 PM
Last Post: Guest
  Detection and Localization of Multiple Spoofing Attackers in Wireless Networks seminar flower 4 1,808 02-06-2014, 09:51 AM
Last Post: seminar project topic
  ON THE EFFECTIVENESS OF MONITORING FOR INTRUSION DETECTION IN MOBILE AD HOC abstract seminar tips 2 802 09-05-2014, 09:43 AM
Last Post: seminar project topic
  Hop-by-Hop Routing in Wireless Mesh Networks with Bandwidth Guarantees Abstract seminar projects maker 2 760 08-03-2014, 12:43 PM
Last Post: seminar project topic
  Online Mobile Phone Shop seminar class 15 12,068 22-10-2013, 07:51 PM
Last Post: vishalonne
  Identifying Evolving Groups in Dynamic Multimode Networks Projects9 2 1,141 30-09-2013, 10:54 AM
Last Post: Guest
  Routing Security in Ad Hoc Wireless Networks seminar projects maker 0 555 26-09-2013, 02:20 PM
Last Post: seminar projects maker
  Adaptation in Reputation Management Systems for Ad hoc Networks seminar projects maker 0 383 26-09-2013, 02:09 PM
Last Post: seminar projects maker