CS294-1 Deeply Embedded Networks “Woo” MACWhy a new MAC protocol?Design GoalsDesign NotesAdaptive Rate Control (ARC)ARC DetailsSingle Cell Analysis (1)Single Cell Analysis (2)Multi Hop AnalysisMulti-Hop Anaysis ResultsConclusionsCS294-1 Deeply Embedded Networks“Woo” MACMichael DemmerFall 2003University of California, Berkeley9/4/03cs294-1 f032Why a new MAC protocol?•Sensor network traffic is different–Bursty due to a single event noted at multiple nodes–Data packets relatively small (tens of bytes)•Nodes operate as a collective–Multi-Hop routing vs. point to point flows•Meager hardware support–No carrier sensing, collision detection, framing, encoding9/4/03cs294-1 f033Design Goals•Three conflicting metrics:•Claim: In a sensor network, fairness and power consumption more important than throughput.FairnessPowerThroughput9/4/03cs294-1 f034Design Notes•Listening:–Can’t rely on hardware for collision avoidance, need to add random delay to unsynchronize conflicting nodes•Backoff:–Need randomness to unsynchronize periodic data streams•Contention:–802.11 style RTS/CTS/DATA/ACK can be 40% of overall traffic–ACK maybe implicit when parent propagates packet•Hidden Node Problem:–Can expect grandparent to transmit after time x, thus wait for x + PACKETTIME after parent transmits to avoid conflict9/4/03cs294-1 f035Adaptive Rate Control (ARC)•Analogy with freeway traffic – congestion increases up the tree–Goal is fair throughput, regardless of which “on-ramp” the data takes–Ideal would be an equivalent packet rate from each node•Apply backpressure in response to congestion–Similar to TCP congestion control–Nodes monitor transmission success/failure and modify rate accordingly•Nodes further up the tree give more bandwidth to route-through traffic9/4/03cs294-1 f036ARC Details•Each node modifies application’s desired send rate S probabilistically by a factor of p (0 < p < 1)–Increase p linearly by α on each transmission success–Decrease p multiplicatively by β (0 < β < 1) on failure•Adaptation preference to route-thru traffic: βroute = 1.5 * βoriginate αoriginate = α route / (n + 1)–‘n’ is the number of descendants, can be approximated by monitoring flow-through traffic9/4/03cs294-1 f037Single Cell Analysis (1)•Before getting to ARC, examine various ways of doing CSMA to share channel without RTS/CTS•Simple One-CellTopology:•CSMA schemes tested:–Varied delay, listening time and backoff mechanisms:9/4/03cs294-1 f038Single Cell Analysis (2)•Both simulation and empirical results generally consistent–802.11 much more power hungry, less fair, less utilization? –Without random pre-transmission delay, schemes fail when sends are synchronized–Random listening period consumes more power than fixed since average listen time goes up•Added application phase shift to avoid capturing effect in 802.11–Brought throughput and fairness up to par, energy consumption still much worse•Conclusion–Random delay, constant listen period, backoff with fixed or binary exponential decrease9/4/03cs294-1 f039Multi Hop Analysis•Topology:•Challenges:–Nodes near the base station can drown out distant nodes–Collectively, if nodes exceed channel capacity, energy wasted in trying to route them•Four Protocols Examined:–802.11 RTS/CTS/ACK–Simple RTS/CTS–CSMA D_CONST_FIX–CSMA with ARC9/4/03cs294-1 f0310Multi-Hop Anaysis Results•ARC improves end-to-end fairness, maintaining reasonable throughput and power consumption9/4/03cs294-1 f0311ConclusionsMetrics Matter•For each metric, a different protocol may be optimal:–802.11 gets best overall throughput, though unfair and power-hungry–Simple CSMA better at power savings, close to optimal throughput, still unfair–ARC improves end-to-end fairness at the expense of throughput and power
View Full Document
Unlocking...