logging in or signing up mobile ad hoc networks SIRVAN Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINT lite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: Embed: Flash iPad Copy Does not support media & animations WordPress Embed Customize Embed URL: Copy Thumbnail: Copy The presentation is successfully added In Your Favorites. Views: 15379 Category: Education License: All Rights Reserved Like it (13) Dislike it (0) Added: June 04, 2008 This Presentation is Public Favorites: 9 Presentation Description No description available. Comments Posting comment... By: galisowjanya (5 month(s) ago) thank u Saving..... Post Reply Close Saving..... Edit Comment Close By: sushila.maims (12 month(s) ago) I want this ppt because it is good. my mail-id is sushila.maims@gmail.com Saving..... Post Reply Close Saving..... Edit Comment Close By: anand2468 (20 month(s) ago) thank u Saving..... Post Reply Close Saving..... Edit Comment Close By: ammulusri (21 month(s) ago) I want mobile ad hoc networks ppt. Saving..... Post Reply Close Saving..... Edit Comment Close By: amrelmasry (24 month(s) ago) i want 2 download it Saving..... Post Reply Close Saving..... Edit Comment Close loading.... See all Premium member Presentation Transcript Algorithms for Ad Hoc Networks : Algorithms for Ad Hoc Networks Roger Wattenhofer MedHocNet 2005 Distributed Algorithms vs. Ad Hoc Networking : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 2 Distributed Algorithms vs. Ad Hoc Networking Small community O(…), (…), (…) Everybody knows best paper New algorithm: Compare it with the best previous Sometimes study the wrong problem; propose protocols that are way too complicated Big community Milliseconds Everybody knows first* paper New protocol: Compare it with the first that was proposed Reinvent the wheel; many papers do not offer any progress Algorithmic Research in Ad Hoc and Sensor Networking : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 3 Algorithmic Research in Ad Hoc and Sensor Networking Link Layer Network Layer Services Theory/Models Clustering (Dominating Sets, etc.) MAC Layer and Coloring Topology and Power Control Interference and Signal-to-Noise-Ratio Deployment (Unstructured Radio Networks) New Routing Paradigms (e.g. Link Reversal) Geo-Routing Broadcast and Multicast Data Gathering Location Services and Positioning Time Synchronization Modeling and Mobility Lower Bounds for Message Passing Selfish Agents, Economic Aspects, Security Overview : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 4 Overview Introduction Ad Hoc and Sensor Networks Routing / Broadcasting Clustering Conclusions Routing in Ad Hoc Networks : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 5 Routing in Ad Hoc Networks Multi-Hop Routing Moving information through a network from a source to a destination if source and destination are not within mutual transmission range Reliability Nodes in an ad-hoc network are not 100% reliable Algorithms need to find alternate routes when nodes are failing Mobile Ad-Hoc Network (MANET) It is often assumed that the nodes are mobile Simple Classification of Ad hoc Routing Algorithms : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 6 Simple Classification of Ad hoc Routing Algorithms Proactive Routing Small topology changes trigger a lot of updates, even when there is no communication does not scale Flooding: when node received message the first time, forward it to all neighbors Distance Vector Routing: as in a fixnet nodes maintain routing tables using update messages Reactive Routing Flooding the whole network does not scale no mobility mobility very high critical mobility Source Routing (DSR, AODV): flooding, but re-use old routes Discussion : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 7 Discussion Lecture “Mobile Computing”: 10 Tricks 210 routing algorithms In reality there are almost that many! Q: How good are these routing algorithms?!? Any hard results? A: Almost none! Method-of-choice is simulation… Perkins: “if you simulate three times, you get three different results” Flooding is key component of (many) proposed algorithms At least flooding should be efficient Overview : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 8 Overview Introduction Clustering Flooding vs. Dominating Sets Algorithm Overview Phase A Phase B Lower Bounds Conclusions Finding a Destination by Flooding : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 9 Finding a Destination by Flooding Finding a Destination Efficiently : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 10 Finding a Destination Efficiently (Connected) Dominating Set : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 11 (Connected) Dominating Set A Dominating Set DS is a subset of nodes such that each node is either in DS or has a neighbor in DS. A Connected Dominating Set CDS is a connected DS, that is, there is a path between any two nodes in CDS that does not use nodes that are not in CDS. It might be favorable tohave few nodes in the (C)DS. This is known as theMinimum (C)DS problem. Formal Problem Definition: M(C)DS : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 12 Formal Problem Definition: M(C)DS Input: We are given an (arbitrary) undirected graph. Output: Find a Minimum (Connected) Dominating Set,that is, a (C)DS with a minimum number of nodes. Problems M(C)DS is NP-hard Find a (C)DS that is “close” to minimum (approximation) The solution must be local (global solutions are impractical for mobile ad-hoc network) – topology of graph “far away” should not influence decision who belongs to (C)DS Overview : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 13 Overview Introduction Clustering Flooding vs. Dominating Sets Algorithm Overview Phase A Phase B Lower Bounds Topology Control Conclusions Algorithm Overview : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 14 Algorithm Overview 0.2 0.5 0.2 0.8 0 0.2 0.3 0.1 0.3 0 Input: Local Graph Fractional Dominating Set Dominating Set Connected Dominating Set 0.5 Phase C: Connect DS by “tree” of “bridges” Phase B: Probabilistic algorithm Phase A: Distributed linear program rel. high degree gives high value Overview : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 15 Overview Introduction Clustering Flooding vs. Dominating Sets Algorithm Overview Phase A Phase B Lower Bounds Topology Control Conclusions Phase A is a Distributed Linear Program : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 16 Phase A is a Distributed Linear Program Nodes 1, …, n: Each node u has variable xu with xu ¸ 0 Sum of x-values in each neighborhood at least 1 (local) Minimize sum of all x-values (global) 0.5+0.3+0.3+0.2+0.2+0 = 1.5 ¸ 1 Linear Programs can be solved optimally in polynomial time But not in a distributed fashion! That’s what we do here… 0.2 0.5 0.2 0.8 0 0.2 0.3 0.1 0.3 0 0.5 Linear Program Adjacency matrix with 1’s in diagonal Phase A Algorithm : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 17 Phase A Algorithm Result after Phase A : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 18 Result after Phase A Distributed Approximation for Linear Program Instead of the optimal values xi* at nodes, nodes have xi(), with The value of depends on the number of rounds k (the locality) Overview : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 19 Overview Introduction Clustering Flooding vs. Dominating Sets Algorithm Overview Phase A Phase B Lower Bounds Topology Control Conclusions Dominating Set as Integer Program : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 20 Dominating Set as Integer Program What we have after phase A What we want after phase B Phase B Algorithm : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 21 Phase B Algorithm Each node applies the following algorithm: Calculate (= maximum degree of neighbors in distance 2) Become a dominator (i.e. go to the dominating set) with probability Send status (dominator or not) to all neighbors If no neighbor is a dominator, become a dominator yourself From phase A Highest degree in distance 2 Result after Phase B : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 22 Result after Phase B Randomized rounding technique Expected number of nodes joining the dominating set in step 2 is bounded by log(+1) ¢ |DSOPT|. Expected number of nodes joining the dominating set in step 4 is bounded by |DSOPT|. Theorem: E[|DS|] · O( ln ¢ |DSOPT|) Related Work on (Connected) Dominating Sets : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 23 Related Work on (Connected) Dominating Sets Global algorithms Johnson (1974), Lovasz (1975), Slavik (1996): Greedy is optimal Guha, Kuller (1996): An optimal algorithm for CDS Feige (1998): ln lower bound unless NP 2 nO(log log n) Local (distributed) algorithms “Handbook of Wireless Networks and Mobile Computing”: All algorithms presented have no guarantees Gao, Guibas, Hershberger, Zhang, Zhu (2001): “Discrete Mobile Centers” O(loglog n) time, but nodes know coordinates MIS-based algorithms (e.g. Alzoubi, Wan, Frieder, 2002) that only work on unit disk graphs. Kuhn, Wattenhofer (2003): Tradeoff time vs. approximation Recent Improvements : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 24 Recent Improvements Improved algorithms (in submission): O(log2 / 4) time for a (1+)-approximation of phase A with logarithmic sized messages. If messages can be of unbounded size there is a constant approximation of phase A in O(log n) time, using the graph decomposition by Linial and Saks. An improved and generalized distributed randomized rounding technique for phase B. Works for quite general linear programs. Is it any good…? Overview : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 25 Overview Introduction Clustering Flooding vs. Dominating Sets Algorithm Overview Phase A Phase B Lower Bounds Topology Control Conclusions Lower Bound for Dominating Sets: Intuition… : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 26 Lower Bound for Dominating Sets: Intuition… m n-1 complete n m m … n n n Two graphs (m << n). Optimal dominating sets are marked red. |DSOPT| = 2. |DSOPT| = m+1. Lower Bound for Dominating Sets: Intuition… : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 27 Lower Bound for Dominating Sets: Intuition… In local algorithms, nodes must decide only using local knowledge. In the example green nodes see exactly the same neighborhood. So these green nodes must decide the same way! m n-1 n m … Lower Bound for Dominating Sets: Intuition… : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 28 Lower Bound for Dominating Sets: Intuition… m n-1 complete n m m … n n n But however they decide, one way will be devastating (with n = m2)! |DSOPT| = 2. |DSOPT without green| ¸ m. |DSOPT| = m+1. |DSOPT with green| > n The Lower Bound : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 29 The Lower Bound Lower bounds (Kuhn, Moscibroda, Wattenhofer @ PODC 2004): Model: In a network/graph G (nodes = processors), each node can exchange a message with all its neighbors for k rounds. After k rounds, node needs to decide. We construct the graph such that there are nodes that see the same neighborhood up to distance k. We show that node ID’s do not help, and using Yao’s principle also randomization does not. Results: Many problems (vertex cover, dominating set, matching, etc.) can only be approximated (nc/k2 / k) and/or (1/k / k). It follows that a polylogarithmic dominating set approximation (or maximal independent set, etc.) needs at least (log / loglog ) and/or ((log n / loglog n)1/2) time. Graph Used in Dominating Set Lower Bound : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 30 Graph Used in Dominating Set Lower Bound The example is for k = 3. All edges are in fact special bipartite graphswith large enough girth. A Theory of “Locality”? : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 31 A Theory of “Locality”? Ad hoc and sensor networks The largest network in the world?!? Managing organizations? Society?!? Matrix multiplication, etc. A better and faster algorithm : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 32 A better and faster algorithm Assume that nodes know their position (GPS) Assume that nodes are in the plane; two nodes are within their transmission radius if and only if their Euclidean distance is at most 1 (UDG, unit disk graph) Then… : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 33 Then… half of tx radius Algorithm : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 34 Algorithm Beacon your position If, in your virtual grid cell, you are the node closest to the center of the cell, then join the CDS, else do not join. That’s it. 1 transmission per node, O(1) approximation, even for CDS If you have mobility, then simply “loop” through algorithm, as fast as your application/mobility wants you to. Comparison : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 35 Comparison First algorithm (distributed linear program) Algorithm computes CDS k2+O(1) transmissions/node O(O(1)/k log ) approximation General graph No position information Second algorithm (virtual grid) Algorithm computes CDS 1 transmission/node O(1) approximation Unit disk graph (UDG) Position information (GPS) Let’s talk about models… : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 36 Let’s talk about models… General Graph Captures obstacles Captures directional radios Often too pessimistic UDG & GPS UDG is not realistic GPS not always available Indoors 2D 3D? Often too optimistic too pessimistic too optimistic Are there any models in between these extremes? Models : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 37 Models too pessimistic too optimistic General Graph UDG GPS UDG No GPS Quasi UDG d 1 Bounded Growth Unit Ball Graph In a doubling metric: Number of independent neighbors is bounded (UDG: 5) Another Algorithm 1: MIS : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 38 Another Algorithm 1: MIS Build maximal independent set (MIS), then connect MIS for CDS Proposed by many, patented(!) by Alzoubi et al. A MIS is by definition also a DS Connecting with independent 1- and 2-hop bridges Slow! Works well only on UDGs; robust for general graphs Another Algorithm 2: Election : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 39 Another Algorithm 2: Election Every node elects a leader; every elected node goes into DS First analyzed by Jie Gao et al. 1 round of communication for DS only; lots of practical appeal In the worst case very bad, even for UDGs only a √n approximation 5 6 1 9 4 7 2 3 8 Another Algorithm 3: Non-neighboring neighbors : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 40 Another Algorithm 3: Non-neighboring neighbors If a node has neighbors who are not neighbors, join CDS Proposed by Jie Wu et al. Renders a CDS directly Almost as bad as choosing all nodes, even for random UDGs Only DS algorithm reviewed in several books Lots of improvements, also proposed by Jie Wu et al. ? Another Algorithm 4: Covering connected neighbors : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 41 Another Algorithm 4: Covering connected neighbors If higher priority neighbors are connected and cover all other neighbors, then don’t join CDS, else join CDS This talk, inspired by an improvement of Jie Wu 2 rounds of communication for CDS only; lots of practical appeal In the worst case very bad, even for UDGs only a √n approximation However, on random UDGs, this gives a O(1) approximation 5 6 1 9 4 7 2 3 8 Result Overview : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 42 Result Overview tx / node quality O(1) log √n 1 2 O(log*) O(log) General Graph2 UDG67 UDG4 UDG5 UDG/GPS1 GBG8 UDG = Unit Disk Graph UBG = Unit Ball Graph GBG = Growth Bounded G. /GPS = With Position Info /D = With Distance Info Lower Bound for General Graphs9 better better UBG/D3 loglog ? References : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 43 References Folk theorem, e.g. Kuhn, Wattenhofer, Zhang, Zollinger, PODC 2003 Kuhn, Wattenhofer, PODC 2003; improvement submitted CDS improvement by Dubhashi et al, SODA 2003 Kuhn, Moscibroda, Wattenhofer, PODC 2005 Alzoubi, Wan, Frieder, MobiHoc 2002 Wu and Li, DIALM 1999 Gao, Guibas, Hershberger, Zhang, Zhu, SCG 2001 This Talk, improving on Wu and Li Kuhn, Moscibroda,Nieberg, Wattenhofer, submitted Kuhn, Moscibroda, Wattenhofer, PODC 2004 More Models : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 44 More Models Random Distribution for all geometric models “Infocom vs. PODC” Related Problems e.g. (Connected) Domatic Partition Moscibroda et al., WMAN 2005 Facility Location Moscibroda et al., PODC 2005 Weighted Graph Models Signal-to-Interference-and-Noise-Ratio (SINR) Communication Models Message Size Unstructured Radio Network (no established MAC layer) Clustering for Unstructured Radio Networks : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 45 Clustering for Unstructured Radio Networks “Big Bang” (deployment) of a sensor and/or ad-hoc network: Nodes wake up asynchronously (very late, maybe) Neighbors unknown Hidden terminal problem No global clock No established MAC protocol No reliable collision detection Limited knowledge of the number of nodes or degree of network. We have randomized algorithms that compute DS (or MIS) in polylog(n) time even under these harsh circumstances, where n is an upper bound on the number of nodes in the system. [Kuhn, Moscibroda, Wattenhofer @ MobiCom 2004] [Moscibroda, Wattenhofer @ PODC 2005] Overview : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 46 Overview Introduction Clustering Conclusions Big Research Opportunities : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 47 Big Research Opportunities Link Layer Network Layer Services Theory/Models Clustering (Dominating Sets, etc.) MAC Layer and Coloring Topology and Power Control Interference and Signal-to-Noise-Ratio Deployment (Unstructured Radio Networks) New Routing Paradigms (e.g. Link Reversal) Geo-Routing Broadcast and Multicast Data Gathering Location Services and Positioning Time Synchronization Modeling and Mobility Lower Bounds for Message Passing Selfish Agents, Economic Aspects, Security Check yourself: www.dcg.ethz.ch Reading List : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 48 Check yourself: www.dcg.ethz.ch Reading List … Conclusions & Open Problems : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 49 Conclusions & Open Problems You don’t have to do algorithms and proofs… … but it would be good to be aware of them. Open Problems and Research Directions Fast good algorithm (for standard UDG) or new lower bound Study problems for models in-between UDG and general graph Mobility and dynamics Study new models: e.g. SINR Real implementations Questions?Comments? : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 Questions?Comments? Thank you for your attention You do not have the permission to view this presentation. In order to view it, please contact the author of the presentation.
mobile ad hoc networks SIRVAN Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINT lite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: Embed: Flash iPad Copy Does not support media & animations WordPress Embed Customize Embed URL: Copy Thumbnail: Copy The presentation is successfully added In Your Favorites. Views: 15379 Category: Education License: All Rights Reserved Like it (13) Dislike it (0) Added: June 04, 2008 This Presentation is Public Favorites: 9 Presentation Description No description available. Comments Posting comment... By: galisowjanya (5 month(s) ago) thank u Saving..... Post Reply Close Saving..... Edit Comment Close By: sushila.maims (12 month(s) ago) I want this ppt because it is good. my mail-id is sushila.maims@gmail.com Saving..... Post Reply Close Saving..... Edit Comment Close By: anand2468 (20 month(s) ago) thank u Saving..... Post Reply Close Saving..... Edit Comment Close By: ammulusri (21 month(s) ago) I want mobile ad hoc networks ppt. Saving..... Post Reply Close Saving..... Edit Comment Close By: amrelmasry (24 month(s) ago) i want 2 download it Saving..... Post Reply Close Saving..... Edit Comment Close loading.... See all Premium member Presentation Transcript Algorithms for Ad Hoc Networks : Algorithms for Ad Hoc Networks Roger Wattenhofer MedHocNet 2005 Distributed Algorithms vs. Ad Hoc Networking : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 2 Distributed Algorithms vs. Ad Hoc Networking Small community O(…), (…), (…) Everybody knows best paper New algorithm: Compare it with the best previous Sometimes study the wrong problem; propose protocols that are way too complicated Big community Milliseconds Everybody knows first* paper New protocol: Compare it with the first that was proposed Reinvent the wheel; many papers do not offer any progress Algorithmic Research in Ad Hoc and Sensor Networking : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 3 Algorithmic Research in Ad Hoc and Sensor Networking Link Layer Network Layer Services Theory/Models Clustering (Dominating Sets, etc.) MAC Layer and Coloring Topology and Power Control Interference and Signal-to-Noise-Ratio Deployment (Unstructured Radio Networks) New Routing Paradigms (e.g. Link Reversal) Geo-Routing Broadcast and Multicast Data Gathering Location Services and Positioning Time Synchronization Modeling and Mobility Lower Bounds for Message Passing Selfish Agents, Economic Aspects, Security Overview : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 4 Overview Introduction Ad Hoc and Sensor Networks Routing / Broadcasting Clustering Conclusions Routing in Ad Hoc Networks : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 5 Routing in Ad Hoc Networks Multi-Hop Routing Moving information through a network from a source to a destination if source and destination are not within mutual transmission range Reliability Nodes in an ad-hoc network are not 100% reliable Algorithms need to find alternate routes when nodes are failing Mobile Ad-Hoc Network (MANET) It is often assumed that the nodes are mobile Simple Classification of Ad hoc Routing Algorithms : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 6 Simple Classification of Ad hoc Routing Algorithms Proactive Routing Small topology changes trigger a lot of updates, even when there is no communication does not scale Flooding: when node received message the first time, forward it to all neighbors Distance Vector Routing: as in a fixnet nodes maintain routing tables using update messages Reactive Routing Flooding the whole network does not scale no mobility mobility very high critical mobility Source Routing (DSR, AODV): flooding, but re-use old routes Discussion : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 7 Discussion Lecture “Mobile Computing”: 10 Tricks 210 routing algorithms In reality there are almost that many! Q: How good are these routing algorithms?!? Any hard results? A: Almost none! Method-of-choice is simulation… Perkins: “if you simulate three times, you get three different results” Flooding is key component of (many) proposed algorithms At least flooding should be efficient Overview : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 8 Overview Introduction Clustering Flooding vs. Dominating Sets Algorithm Overview Phase A Phase B Lower Bounds Conclusions Finding a Destination by Flooding : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 9 Finding a Destination by Flooding Finding a Destination Efficiently : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 10 Finding a Destination Efficiently (Connected) Dominating Set : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 11 (Connected) Dominating Set A Dominating Set DS is a subset of nodes such that each node is either in DS or has a neighbor in DS. A Connected Dominating Set CDS is a connected DS, that is, there is a path between any two nodes in CDS that does not use nodes that are not in CDS. It might be favorable tohave few nodes in the (C)DS. This is known as theMinimum (C)DS problem. Formal Problem Definition: M(C)DS : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 12 Formal Problem Definition: M(C)DS Input: We are given an (arbitrary) undirected graph. Output: Find a Minimum (Connected) Dominating Set,that is, a (C)DS with a minimum number of nodes. Problems M(C)DS is NP-hard Find a (C)DS that is “close” to minimum (approximation) The solution must be local (global solutions are impractical for mobile ad-hoc network) – topology of graph “far away” should not influence decision who belongs to (C)DS Overview : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 13 Overview Introduction Clustering Flooding vs. Dominating Sets Algorithm Overview Phase A Phase B Lower Bounds Topology Control Conclusions Algorithm Overview : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 14 Algorithm Overview 0.2 0.5 0.2 0.8 0 0.2 0.3 0.1 0.3 0 Input: Local Graph Fractional Dominating Set Dominating Set Connected Dominating Set 0.5 Phase C: Connect DS by “tree” of “bridges” Phase B: Probabilistic algorithm Phase A: Distributed linear program rel. high degree gives high value Overview : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 15 Overview Introduction Clustering Flooding vs. Dominating Sets Algorithm Overview Phase A Phase B Lower Bounds Topology Control Conclusions Phase A is a Distributed Linear Program : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 16 Phase A is a Distributed Linear Program Nodes 1, …, n: Each node u has variable xu with xu ¸ 0 Sum of x-values in each neighborhood at least 1 (local) Minimize sum of all x-values (global) 0.5+0.3+0.3+0.2+0.2+0 = 1.5 ¸ 1 Linear Programs can be solved optimally in polynomial time But not in a distributed fashion! That’s what we do here… 0.2 0.5 0.2 0.8 0 0.2 0.3 0.1 0.3 0 0.5 Linear Program Adjacency matrix with 1’s in diagonal Phase A Algorithm : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 17 Phase A Algorithm Result after Phase A : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 18 Result after Phase A Distributed Approximation for Linear Program Instead of the optimal values xi* at nodes, nodes have xi(), with The value of depends on the number of rounds k (the locality) Overview : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 19 Overview Introduction Clustering Flooding vs. Dominating Sets Algorithm Overview Phase A Phase B Lower Bounds Topology Control Conclusions Dominating Set as Integer Program : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 20 Dominating Set as Integer Program What we have after phase A What we want after phase B Phase B Algorithm : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 21 Phase B Algorithm Each node applies the following algorithm: Calculate (= maximum degree of neighbors in distance 2) Become a dominator (i.e. go to the dominating set) with probability Send status (dominator or not) to all neighbors If no neighbor is a dominator, become a dominator yourself From phase A Highest degree in distance 2 Result after Phase B : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 22 Result after Phase B Randomized rounding technique Expected number of nodes joining the dominating set in step 2 is bounded by log(+1) ¢ |DSOPT|. Expected number of nodes joining the dominating set in step 4 is bounded by |DSOPT|. Theorem: E[|DS|] · O( ln ¢ |DSOPT|) Related Work on (Connected) Dominating Sets : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 23 Related Work on (Connected) Dominating Sets Global algorithms Johnson (1974), Lovasz (1975), Slavik (1996): Greedy is optimal Guha, Kuller (1996): An optimal algorithm for CDS Feige (1998): ln lower bound unless NP 2 nO(log log n) Local (distributed) algorithms “Handbook of Wireless Networks and Mobile Computing”: All algorithms presented have no guarantees Gao, Guibas, Hershberger, Zhang, Zhu (2001): “Discrete Mobile Centers” O(loglog n) time, but nodes know coordinates MIS-based algorithms (e.g. Alzoubi, Wan, Frieder, 2002) that only work on unit disk graphs. Kuhn, Wattenhofer (2003): Tradeoff time vs. approximation Recent Improvements : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 24 Recent Improvements Improved algorithms (in submission): O(log2 / 4) time for a (1+)-approximation of phase A with logarithmic sized messages. If messages can be of unbounded size there is a constant approximation of phase A in O(log n) time, using the graph decomposition by Linial and Saks. An improved and generalized distributed randomized rounding technique for phase B. Works for quite general linear programs. Is it any good…? Overview : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 25 Overview Introduction Clustering Flooding vs. Dominating Sets Algorithm Overview Phase A Phase B Lower Bounds Topology Control Conclusions Lower Bound for Dominating Sets: Intuition… : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 26 Lower Bound for Dominating Sets: Intuition… m n-1 complete n m m … n n n Two graphs (m << n). Optimal dominating sets are marked red. |DSOPT| = 2. |DSOPT| = m+1. Lower Bound for Dominating Sets: Intuition… : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 27 Lower Bound for Dominating Sets: Intuition… In local algorithms, nodes must decide only using local knowledge. In the example green nodes see exactly the same neighborhood. So these green nodes must decide the same way! m n-1 n m … Lower Bound for Dominating Sets: Intuition… : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 28 Lower Bound for Dominating Sets: Intuition… m n-1 complete n m m … n n n But however they decide, one way will be devastating (with n = m2)! |DSOPT| = 2. |DSOPT without green| ¸ m. |DSOPT| = m+1. |DSOPT with green| > n The Lower Bound : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 29 The Lower Bound Lower bounds (Kuhn, Moscibroda, Wattenhofer @ PODC 2004): Model: In a network/graph G (nodes = processors), each node can exchange a message with all its neighbors for k rounds. After k rounds, node needs to decide. We construct the graph such that there are nodes that see the same neighborhood up to distance k. We show that node ID’s do not help, and using Yao’s principle also randomization does not. Results: Many problems (vertex cover, dominating set, matching, etc.) can only be approximated (nc/k2 / k) and/or (1/k / k). It follows that a polylogarithmic dominating set approximation (or maximal independent set, etc.) needs at least (log / loglog ) and/or ((log n / loglog n)1/2) time. Graph Used in Dominating Set Lower Bound : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 30 Graph Used in Dominating Set Lower Bound The example is for k = 3. All edges are in fact special bipartite graphswith large enough girth. A Theory of “Locality”? : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 31 A Theory of “Locality”? Ad hoc and sensor networks The largest network in the world?!? Managing organizations? Society?!? Matrix multiplication, etc. A better and faster algorithm : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 32 A better and faster algorithm Assume that nodes know their position (GPS) Assume that nodes are in the plane; two nodes are within their transmission radius if and only if their Euclidean distance is at most 1 (UDG, unit disk graph) Then… : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 33 Then… half of tx radius Algorithm : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 34 Algorithm Beacon your position If, in your virtual grid cell, you are the node closest to the center of the cell, then join the CDS, else do not join. That’s it. 1 transmission per node, O(1) approximation, even for CDS If you have mobility, then simply “loop” through algorithm, as fast as your application/mobility wants you to. Comparison : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 35 Comparison First algorithm (distributed linear program) Algorithm computes CDS k2+O(1) transmissions/node O(O(1)/k log ) approximation General graph No position information Second algorithm (virtual grid) Algorithm computes CDS 1 transmission/node O(1) approximation Unit disk graph (UDG) Position information (GPS) Let’s talk about models… : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 36 Let’s talk about models… General Graph Captures obstacles Captures directional radios Often too pessimistic UDG & GPS UDG is not realistic GPS not always available Indoors 2D 3D? Often too optimistic too pessimistic too optimistic Are there any models in between these extremes? Models : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 37 Models too pessimistic too optimistic General Graph UDG GPS UDG No GPS Quasi UDG d 1 Bounded Growth Unit Ball Graph In a doubling metric: Number of independent neighbors is bounded (UDG: 5) Another Algorithm 1: MIS : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 38 Another Algorithm 1: MIS Build maximal independent set (MIS), then connect MIS for CDS Proposed by many, patented(!) by Alzoubi et al. A MIS is by definition also a DS Connecting with independent 1- and 2-hop bridges Slow! Works well only on UDGs; robust for general graphs Another Algorithm 2: Election : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 39 Another Algorithm 2: Election Every node elects a leader; every elected node goes into DS First analyzed by Jie Gao et al. 1 round of communication for DS only; lots of practical appeal In the worst case very bad, even for UDGs only a √n approximation 5 6 1 9 4 7 2 3 8 Another Algorithm 3: Non-neighboring neighbors : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 40 Another Algorithm 3: Non-neighboring neighbors If a node has neighbors who are not neighbors, join CDS Proposed by Jie Wu et al. Renders a CDS directly Almost as bad as choosing all nodes, even for random UDGs Only DS algorithm reviewed in several books Lots of improvements, also proposed by Jie Wu et al. ? Another Algorithm 4: Covering connected neighbors : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 41 Another Algorithm 4: Covering connected neighbors If higher priority neighbors are connected and cover all other neighbors, then don’t join CDS, else join CDS This talk, inspired by an improvement of Jie Wu 2 rounds of communication for CDS only; lots of practical appeal In the worst case very bad, even for UDGs only a √n approximation However, on random UDGs, this gives a O(1) approximation 5 6 1 9 4 7 2 3 8 Result Overview : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 42 Result Overview tx / node quality O(1) log √n 1 2 O(log*) O(log) General Graph2 UDG67 UDG4 UDG5 UDG/GPS1 GBG8 UDG = Unit Disk Graph UBG = Unit Ball Graph GBG = Growth Bounded G. /GPS = With Position Info /D = With Distance Info Lower Bound for General Graphs9 better better UBG/D3 loglog ? References : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 43 References Folk theorem, e.g. Kuhn, Wattenhofer, Zhang, Zollinger, PODC 2003 Kuhn, Wattenhofer, PODC 2003; improvement submitted CDS improvement by Dubhashi et al, SODA 2003 Kuhn, Moscibroda, Wattenhofer, PODC 2005 Alzoubi, Wan, Frieder, MobiHoc 2002 Wu and Li, DIALM 1999 Gao, Guibas, Hershberger, Zhang, Zhu, SCG 2001 This Talk, improving on Wu and Li Kuhn, Moscibroda,Nieberg, Wattenhofer, submitted Kuhn, Moscibroda, Wattenhofer, PODC 2004 More Models : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 44 More Models Random Distribution for all geometric models “Infocom vs. PODC” Related Problems e.g. (Connected) Domatic Partition Moscibroda et al., WMAN 2005 Facility Location Moscibroda et al., PODC 2005 Weighted Graph Models Signal-to-Interference-and-Noise-Ratio (SINR) Communication Models Message Size Unstructured Radio Network (no established MAC layer) Clustering for Unstructured Radio Networks : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 45 Clustering for Unstructured Radio Networks “Big Bang” (deployment) of a sensor and/or ad-hoc network: Nodes wake up asynchronously (very late, maybe) Neighbors unknown Hidden terminal problem No global clock No established MAC protocol No reliable collision detection Limited knowledge of the number of nodes or degree of network. We have randomized algorithms that compute DS (or MIS) in polylog(n) time even under these harsh circumstances, where n is an upper bound on the number of nodes in the system. [Kuhn, Moscibroda, Wattenhofer @ MobiCom 2004] [Moscibroda, Wattenhofer @ PODC 2005] Overview : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 46 Overview Introduction Clustering Conclusions Big Research Opportunities : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 47 Big Research Opportunities Link Layer Network Layer Services Theory/Models Clustering (Dominating Sets, etc.) MAC Layer and Coloring Topology and Power Control Interference and Signal-to-Noise-Ratio Deployment (Unstructured Radio Networks) New Routing Paradigms (e.g. Link Reversal) Geo-Routing Broadcast and Multicast Data Gathering Location Services and Positioning Time Synchronization Modeling and Mobility Lower Bounds for Message Passing Selfish Agents, Economic Aspects, Security Check yourself: www.dcg.ethz.ch Reading List : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 48 Check yourself: www.dcg.ethz.ch Reading List … Conclusions & Open Problems : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 49 Conclusions & Open Problems You don’t have to do algorithms and proofs… … but it would be good to be aware of them. Open Problems and Research Directions Fast good algorithm (for standard UDG) or new lower bound Study problems for models in-between UDG and general graph Mobility and dynamics Study new models: e.g. SINR Real implementations Questions?Comments? : Roger Wattenhofer, ETH Zurich @ MedHocNet 2005 Questions?Comments? Thank you for your attention