logging in or signing up 3 MANET Cuthbert Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINTLite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 3939 Category: Entertainment License: All Rights Reserved Like it (2) Dislike it (0) Added: January 01, 2008 This Presentation is Public Favorites: 0 Presentation Description No description available. Comments Posting comment... By: yuvrajtr19 (15 month(s) ago) hey please send me red tacton ppt please.. please send it on yuvrajtr19@gmail.com Saving..... Post Reply Close Saving..... Edit Comment Close By: vissu552 (16 month(s) ago) hi plz semd me the ppts of manet Saving..... Post Reply Close Saving..... Edit Comment Close By: b.veerun (16 month(s) ago) plz send this manet in ppt Saving..... Post Reply Close Saving..... Edit Comment Close By: ravi003 (20 month(s) ago) please send this manets in ppt Saving..... Post Reply Close Saving..... Edit Comment Close By: ravi003 (20 month(s) ago) hi plz semd me the ppts of manet Saving..... Post Reply Close Saving..... Edit Comment Close loading.... See all Premium member Presentation Transcript Time Synchronization in 802.11-based MANETs: Time Synchronization in 802.11-based MANETs Ten H. Lai Ohio State UniversityOut-of-sync problem in MANETs: Out-of-sync problem in MANETs More sever than in IBSS because of hidden terminals. Recall: causes of out-of-sync Unidirectional clocks Equal beacon opportunity Single beacon per interval Beacon contention (collision)Basic Ideas: Basic Ideas Select a subset of nodes to generate beacons more frequently than the rest. What subset? fastest node + (connected) dominating set Dominating Sets: Dominating Sets A set of nodes that covers the entire graph. connected dominating set Constructing CDS’s: Constructing CDS’s Many existing algorithms. Layer 3 algorithms – useful for routing, useless for our purpose.A New CDS Algorithm: A New CDS Algorithm Embedded in TSF (time sync function) Nodes exchanging info via beacons Overhead: 3 bits per beacon (550 bits) window beacon intervalDS, Bridges, Covered, Uncovered Nodes: DS, Bridges, Covered, Uncovered Nodes DS Constructing a CDS: basic idea: Constructing a CDS: basic idea Initially, DS contains a single node. The fastest node enters DS. Bridges keep entering DS until no more bridges. DS Design Issue #1: Design Issue #1 How to recognize the fastest node, bridges, DS nodes, covered nodes, uncovered nodes thru beacons? SA Timestamp Beacon Design Issue #2: Design Issue #2 How to minimize the number of bridges entering DS? Design Issue #3: Design Issue #3 Cope with topology change and node mobility. B A A B Design Issue #4: Design Issue #4 How to merge two subnets? Easy & hard. ? Design Issue #5: MANET Formation: Design Issue #5: MANET Formation How to form a MANET from scratch? ? Another way of MANET formation: Another way of MANET formation ? Assumptions: Assumptions Formation: MANET initiated by a single node. Connectivity: MANET remains connected. Summary of Design Issues: Summary of Design Issues How to recognize the fastest node and bridges? How to control the number of bridges entering DS? How to cope with topology change and node mobility? How to merge subnets? Initialization: Initialization Rule 1: Let the starting node enter the DS. Slide18: Rule 2: A node x recognizes itself as the fastest if T(beacons) < T(x) for the last k received beacons. The fastest enters DS Am I the Fastest? 1:00 12:01 3:45 8.16 1.00 1.01 7:59 1.01 0:59 1:33 1:32 1:31 1:31 1:30 1.00 10:01 1:35 Solution for Design Issue #1 : Solution for Design Issue #1 How to recognize fastest node and bridges, DS nodes, covered nodes, uncovered nodes thru beacons? SA Timestamp Beacon Adding Bridges to DS: Adding Bridges to DS Rule 3: In each beacon interval, let bridge i enter DS with probability P(i). Desired properties of P(i)? DS Does it construct a CDS?: Does it construct a CDS? R1. The starting node enters DS. R2. The fastest node enters DS. R3. Each bridge enters DS with a probability. DS, yes. CDS, not necessarily. How to make it connected?: How to make it connected? Gateway: a covered node receiving a beacon from a DS node with a far smaller timing. Rule 4: Let gateways enter DS. 12:05 12:04 12:03 12:32 12:30 12:20How fast can gateways be recognized?: How fast can gateways be recognized? Depends on the drift rate between fastest node and A. The higher the drift rate, the easier and faster to recognize gateways. A Is the resulting DS always connected?: Is the resulting DS always connected? Not necessarily Not a problem as far as clock sync is concerned. What if we do need a connected DS?: What if we do need a connected DS? Is it possible to always construct a CDS using only beacons? Yes Complicated A problem: entrance only, no exit.: A problem: entrance only, no exit. R1. The starting node enters DS. R2. The fastest node enters DS. R3. Each bridge enters DS with a probability. R4. Each gateway enters DS. Exit Rules: Exit Rules R1. The starting node enters DS. R2. The fastest node enters DS. R3. Each bridge enters DS with a probability. R4. Each gateway enters DS. R2’. If no longer the fastest, leaves the DS. Exit Rules: Exit Rules R1. The starting node enters DS. R2. The fastest node enters DS. R3. Each bridge enters DS with a probability. R4. Each gateway enters DS. R3’ & R4’. Leaves DS after a random amount of time. 802.11 TSF max time drift: 802.11 TSF max time driftDS-Based TSF: DS-Based TSFProblem, Problem, Problem!: Problem, Problem, Problem! ???A different approach (ASP): A different approach (ASP) A Clock Synchronization Algorithm for Multihop Wireless Ad Hoc networks J.P. Sheu, C.M. Chao, C.W. Sun, NCU ICDCS’04Basic Idea 1: Basic Idea 1 Adjust C(x) according to x’s rank in speed in its neighborhood. N(x) = number of neighbors Slower(x) = number of slower neighbors C(x) = {max(1, N(x)) / max(1, Slower(x))}^α x Basic Idea 2: Basic Idea 2 Automatic self-time-correcting Suppose t2-t1 > t2’-t1’ (T > T’) B falls behind A by T-T’ per T’ μs, or 1 μs per k = T’ / T-T’ μs B moves its clock 1 μs ahead per each k μs Clock A Clock B t1 t2 t1’ t2’ T T’A subtle detail: A subtle detail In measuring T, A should not be synchronized between t1 and t2. Same for B? Variable SyncNum Carries SyncNum in beacon Clock A Clock B t1 t2 t1’ t2’ T T’Automatic Self-Time-Correcting: Automatic Self-Time-CorrectingMATSF (to be presented at MASS’05): MATSF (to be presented at MASS’05)ASP (ICDCS’04): ASP (ICDCS’04)Summary: Summary Proposed: a DS-based clock sync protocol By-product: an algorithm for constructing DS. DS: mostly connected, occasionally not. A different approach What’s next? You do not have the permission to view this presentation. In order to view it, please contact the author of the presentation.
3 MANET Cuthbert Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINTLite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 3939 Category: Entertainment License: All Rights Reserved Like it (2) Dislike it (0) Added: January 01, 2008 This Presentation is Public Favorites: 0 Presentation Description No description available. Comments Posting comment... By: yuvrajtr19 (15 month(s) ago) hey please send me red tacton ppt please.. please send it on yuvrajtr19@gmail.com Saving..... Post Reply Close Saving..... Edit Comment Close By: vissu552 (16 month(s) ago) hi plz semd me the ppts of manet Saving..... Post Reply Close Saving..... Edit Comment Close By: b.veerun (16 month(s) ago) plz send this manet in ppt Saving..... Post Reply Close Saving..... Edit Comment Close By: ravi003 (20 month(s) ago) please send this manets in ppt Saving..... Post Reply Close Saving..... Edit Comment Close By: ravi003 (20 month(s) ago) hi plz semd me the ppts of manet Saving..... Post Reply Close Saving..... Edit Comment Close loading.... See all Premium member Presentation Transcript Time Synchronization in 802.11-based MANETs: Time Synchronization in 802.11-based MANETs Ten H. Lai Ohio State UniversityOut-of-sync problem in MANETs: Out-of-sync problem in MANETs More sever than in IBSS because of hidden terminals. Recall: causes of out-of-sync Unidirectional clocks Equal beacon opportunity Single beacon per interval Beacon contention (collision)Basic Ideas: Basic Ideas Select a subset of nodes to generate beacons more frequently than the rest. What subset? fastest node + (connected) dominating set Dominating Sets: Dominating Sets A set of nodes that covers the entire graph. connected dominating set Constructing CDS’s: Constructing CDS’s Many existing algorithms. Layer 3 algorithms – useful for routing, useless for our purpose.A New CDS Algorithm: A New CDS Algorithm Embedded in TSF (time sync function) Nodes exchanging info via beacons Overhead: 3 bits per beacon (550 bits) window beacon intervalDS, Bridges, Covered, Uncovered Nodes: DS, Bridges, Covered, Uncovered Nodes DS Constructing a CDS: basic idea: Constructing a CDS: basic idea Initially, DS contains a single node. The fastest node enters DS. Bridges keep entering DS until no more bridges. DS Design Issue #1: Design Issue #1 How to recognize the fastest node, bridges, DS nodes, covered nodes, uncovered nodes thru beacons? SA Timestamp Beacon Design Issue #2: Design Issue #2 How to minimize the number of bridges entering DS? Design Issue #3: Design Issue #3 Cope with topology change and node mobility. B A A B Design Issue #4: Design Issue #4 How to merge two subnets? Easy & hard. ? Design Issue #5: MANET Formation: Design Issue #5: MANET Formation How to form a MANET from scratch? ? Another way of MANET formation: Another way of MANET formation ? Assumptions: Assumptions Formation: MANET initiated by a single node. Connectivity: MANET remains connected. Summary of Design Issues: Summary of Design Issues How to recognize the fastest node and bridges? How to control the number of bridges entering DS? How to cope with topology change and node mobility? How to merge subnets? Initialization: Initialization Rule 1: Let the starting node enter the DS. Slide18: Rule 2: A node x recognizes itself as the fastest if T(beacons) < T(x) for the last k received beacons. The fastest enters DS Am I the Fastest? 1:00 12:01 3:45 8.16 1.00 1.01 7:59 1.01 0:59 1:33 1:32 1:31 1:31 1:30 1.00 10:01 1:35 Solution for Design Issue #1 : Solution for Design Issue #1 How to recognize fastest node and bridges, DS nodes, covered nodes, uncovered nodes thru beacons? SA Timestamp Beacon Adding Bridges to DS: Adding Bridges to DS Rule 3: In each beacon interval, let bridge i enter DS with probability P(i). Desired properties of P(i)? DS Does it construct a CDS?: Does it construct a CDS? R1. The starting node enters DS. R2. The fastest node enters DS. R3. Each bridge enters DS with a probability. DS, yes. CDS, not necessarily. How to make it connected?: How to make it connected? Gateway: a covered node receiving a beacon from a DS node with a far smaller timing. Rule 4: Let gateways enter DS. 12:05 12:04 12:03 12:32 12:30 12:20How fast can gateways be recognized?: How fast can gateways be recognized? Depends on the drift rate between fastest node and A. The higher the drift rate, the easier and faster to recognize gateways. A Is the resulting DS always connected?: Is the resulting DS always connected? Not necessarily Not a problem as far as clock sync is concerned. What if we do need a connected DS?: What if we do need a connected DS? Is it possible to always construct a CDS using only beacons? Yes Complicated A problem: entrance only, no exit.: A problem: entrance only, no exit. R1. The starting node enters DS. R2. The fastest node enters DS. R3. Each bridge enters DS with a probability. R4. Each gateway enters DS. Exit Rules: Exit Rules R1. The starting node enters DS. R2. The fastest node enters DS. R3. Each bridge enters DS with a probability. R4. Each gateway enters DS. R2’. If no longer the fastest, leaves the DS. Exit Rules: Exit Rules R1. The starting node enters DS. R2. The fastest node enters DS. R3. Each bridge enters DS with a probability. R4. Each gateway enters DS. R3’ & R4’. Leaves DS after a random amount of time. 802.11 TSF max time drift: 802.11 TSF max time driftDS-Based TSF: DS-Based TSFProblem, Problem, Problem!: Problem, Problem, Problem! ???A different approach (ASP): A different approach (ASP) A Clock Synchronization Algorithm for Multihop Wireless Ad Hoc networks J.P. Sheu, C.M. Chao, C.W. Sun, NCU ICDCS’04Basic Idea 1: Basic Idea 1 Adjust C(x) according to x’s rank in speed in its neighborhood. N(x) = number of neighbors Slower(x) = number of slower neighbors C(x) = {max(1, N(x)) / max(1, Slower(x))}^α x Basic Idea 2: Basic Idea 2 Automatic self-time-correcting Suppose t2-t1 > t2’-t1’ (T > T’) B falls behind A by T-T’ per T’ μs, or 1 μs per k = T’ / T-T’ μs B moves its clock 1 μs ahead per each k μs Clock A Clock B t1 t2 t1’ t2’ T T’A subtle detail: A subtle detail In measuring T, A should not be synchronized between t1 and t2. Same for B? Variable SyncNum Carries SyncNum in beacon Clock A Clock B t1 t2 t1’ t2’ T T’Automatic Self-Time-Correcting: Automatic Self-Time-CorrectingMATSF (to be presented at MASS’05): MATSF (to be presented at MASS’05)ASP (ICDCS’04): ASP (ICDCS’04)Summary: Summary Proposed: a DS-based clock sync protocol By-product: an algorithm for constructing DS. DS: mostly connected, occasionally not. A different approach What’s next?