CS294-1 Deeply Embedded Networks Broadcast / Dissemination Sept 18, 2003BCAST: Fundamental building blockFloodingNetwork Discovery: Radio CellsNetwork DiscoveryControlled Empirical StudyExample “epidemic” tree formationFinal TreeOpen Territory => Many ChildrenSlide 10Slide 11Power Laws ?Understanding ConnectivitySensitivityBroadcast StormCollisionsSPIN version of problemsEstimating RedundancySelective Retransmission SchemesNi findings: Probabilistic SquelchAre random-placement graphs reasonable?PowerPoint PresentationSlide 23A different connectivity modelSlide 25Asymmetric LinksCounter SchemeDistance and locationFlooding vs GossipSPINSpin ExampleDelayStudyWith Loss (and contention)TrafficGeneralizing from one graph?Adaptive BCAST rateExample TreeIs this a good broadcast tree?What more to ensure reliabilityquestionsCS294-1 Deeply Embedded NetworksBroadcast / DisseminationSept 18, 2003David CullerFall 2003University of California, Berkeley01/13/19CS294-1 F032BCAST: Fundamental building block•Command•Wake-up•Form routing tree•Discover route–Source-destination discovery (DSR, AODV)–Exploration in directed diffusion•Time-synch•Constructed from underlying local broadcast (cell)01/13/19CS294-1 F033Flooding•Simple Epidemic Algorithm Schemaif (new bcast msg) thentake local actionretransmit modified request•Command, dissemination•Build spanning tree»record parent•Naturally adapts to available connectivity•Minimal state and protocol overhead=> surprising complexity in this simple mechanism01/13/19CS294-1 F034Network Discovery: Radio Cells01/13/19CS294-1 F035Network Discovery01/13/19CS294-1 F036Controlled Empirical Study•Experimental Setup–13x13 grid of nodes–separation 2ft–flat open surface–Identical length antennas, pointing vertically upwards.–Fresh batteries on all nodes–Identical orientation of all nodes–The region was clean of external noise sources.•Range of signal strength settings•Log many runs01/13/19CS294-1 F037Example “epidemic” tree formation01/13/19CS294-1 F038Final Tree01/13/19CS294-1 F039Open Territory => Many Children•Example: Level 101/13/19CS294-1 F0310Open Territory => Many Children•Example: Level 2 – variation in distance01/13/19CS294-1 F0311Open Territory => Many Children•Example: Level 3 – long links01/13/19CS294-1 F0312Power Laws ?•Most nodes have very small degree (ave = .92)•Some have degree = 15% of the population•Few large clusters account for most of the edges 11010010001 10 100Cluster Size (1 + # children)Count11010010001 10 100Cluster SizeLinks01/13/19CS294-1 F0313Understanding Connectivity•16 transmit power settings•For each transmit power setting, each node transmits 20 packets.•Receivers log successfully received packets.•Nodes transmit one after the other in a token-ring fashion •No collisions.•Define “range”: radius where 75% of enclosed nodes receive 75% of packets•Often good nodes at a distanceprobability of reception from center node vs xmit strength01/13/19CS294-1 F0314Sensitivity•Hardware platform?•MAC?01/13/19CS294-1 F0315Broadcast Storm•Redundant broadcasts–Transmission when all nbrs have the message•Contention–After a transmission, many neighbors likely to rebroadcast at nearly same time–Highly correlated behavior•Collisions–Node is likely to hear multiple conflicting transmissions–Storm paper cites lack of RTS/CTS, but is more fundamental=> everyone need not transmit•Reduce redundancy.•Will also reduce contention and collision01/13/19CS294-1 F0316Collisions•Nodes out of range may have overlapping cells–hidden terminal effect•Collisions => these nodes hear neither ‘parent’–become stragglers•As the tree propagates –folds back on itself–rebounds from the edge–picking up these stragglers.•Seen in many experiments•Mathematically complex because behavior is not independent beyond singe cell01/13/19CS294-1 F0317SPIN version of problems•Implosion–Node hears same msg from many neighbors•Overlap–Two transmitting nodes may have large intersection of neighbors•Resource blindness–Some nodes may have to do more than others–Favor energy-rich nodes when winowing redundancy•Coming from IP multicast perspective01/13/19CS294-1 F0318Estimating Redundancy•Geometric overlap–At best an additional 41% area•Decreasing yield with number of neighbors msgs•Estimation of contention–Potential contention–Delay can always take prob. Of contention to zero•Collisions–No RTS/CTS to help–Observes that MACs don’t pay enough attention one-to-many case01/13/19CS294-1 F0319Selective Retransmission Schemes•Probabilistic Retransmission–Fixed prob.–What would be the right choice?•Counter–When hear msg, start random delay–If hear C msgs during wait, don’t retransmit•Distance–If nearest node from which msg is heard is less than some threshold, don’t retransmit•Location–If portion of cell not covered by transmitting neighbors is less than some threshold, don’t retransmit•Cluster-based–Partition graph into cluster heads, gateways, and members–Members don’t transmit01/13/19CS294-1 F0320Ni findings: Probabilistic Squelch•What is the expected degree of each configuration?–100 in nxn => ~40/n (except n=1)•Is “latency” meaningful when reachability is low•How many neighbors transmit?–Savings versus nodes per cell•Reducing contention trims latency tail01/13/19CS294-1 F0321Are random-placement graphs reasonable?01/13/19CS294-1 F0322Percolation of Random Graphsλcλ210λPλ1P = Prob(exists unbounded connected component)Ed Gilbert (1961)01/13/19CS294-1 F03230.3 0.4Example0.35910…[Quintanilla, Torquato, Ziff, J. Physics A, 2000]cr201/13/19CS294-1 F0324A different connectivity model•Presence of long links dramatically change overlap estimate•Changes the percolation point too.01/13/19CS294-1 F0325251.44)(...359.022rdxxgCNPrcccCNPSquishing and squashing Shifting and squeezingfor the standard connection model (disc)MASSIMO FRANCESCHETTI01/13/19CS294-1 F0326Asymmetric Links•Asymmetric Link: –>65% successful reception in one direction –<25% successful reception in the other direction•10%-25% of links are asymmetric•Many long links are asymmetric–in large field it is likely that someone far away can hear you–what does this mean for protocol design?•OK for broadcast, not for tree build01/13/19CS294-1 F0327Counter
View Full Document
Unlocking...