Practical Lazy Scheduling in Wireless Sensor Networks Ramana Rao Kompella and Alex C Snoeren Proceedings of ACM SenSys 2003 Distributed Rate Adaptation Problem In wireless networks e g sensor nets 802 11 radios consume significant power Opportunity Where radios have multiple transmit rates reducing rate may reduce energy consumption Challenge Find a distributed online transmit scheduling algorithm CSE 291 Topics in Wireless Networking Radio Power Consumption Transmit Electronics Transmit Amplifier 50nJ bit d 100pJ bit m2 HeinzelmanISLPED2000 Receive Electronics 50nJ bit Transmit Amplifier most dominant energy consumer except for short distances 5 10m Electronic power dictated by Moore s Law is decreasing with improvements in technology Transmit RF power more or less remains the same CSE 291 Topics in Wireless Networking Many radios have multiple transmit power rate levels Shannon s laws suggest that energy in joules bit is convex in rate of transmission So why not transmit all packets at the lowest speed Energy required Key Idea Exploit Power rate Tradeoff Rate of transmission Problem Delay increases if packets sent too slowly CSE 291 Topics in Wireless Networking Transmit Scheduling Algorithm Power level for a given rate Different radios have different energy delay curves Henceforth only rate selection Application layers Scheduling Algorithm MAC Layer Wireless medium Radio with multiple Tx rate and power levels CSE 291 Topics in Wireless Networking Prior Work In Reducing Tx RF power Mechanism Shurgers et al show how to adjust rate discretely for QAM radios Show energy gains for a single sender Study energy delay tradeoff Single Sender algorithm Uysal et al analyze theoretical scheduling algorithm Limitations Single sender with knowledge of arrivals Offline algorithm Continuous Radios CSE 291 Topics in Wireless Networking Paper contributions Discretization Offline algorithm for radios with discrete set of Tx rates Single Sender Online algorithm for power conservation Multiple Senders Distributed self tuning algorithm for multi node case Implementation over CSMA CA CSE 291 Topics in Wireless Networking Optimal Offline Algorithm uysal01 Assumptions All arrivals known in advance No time deadlines for individual packets Radios are continuous All packets need to be transmitted within the interval with no additional delay CSE 291 Topics in Wireless Networking Optimal Offline Algorithm Transforms a known set of arrivals into a schedule of transmission durations Schedule takes advantage of packet inter arrival times Schedules packets such that output rate approximates input rate of packets CSE 291 Topics in Wireless Networking Optimal Offline Algorithm Inter arrival Time 100 80 60 40 20 0 0 10 20 30 40 Packet Number CSE 291 Topics in Wireless Networking 50 Optimal Offline Algorithm Transmission Duration 100 80 60 Distributes the packets as uniformly as possible 40 20 0 0 10 20 30 40 Packet Number CSE 291 Topics in Wireless Networking 50 Online Algorithm Approach Estimate the amount of traffic Choose transmission rate based on this estimate Two phases in pipelined fashion Look ahead Buffer packets Scheduling Schedule packets with optimal bit rate CSE 291 Topics in Wireless Networking Simple example From applications Wireless medium buffer scheduler CSE 291 Topics in Wireless Networking Simulation Description Poisson Variable bit rates from 100Kbps to 1Mbps Results for different bit rates in paper qualitatively similar Fixed packet size of 10Kbits Two Key Metrics Bursty traffic arrival patterns in paper qualitatively similar Average Power total Energy total Time Average Delay total Delay total packets Energy function used Uysal et al t 106 0 06 t 2 0 12 t 1 CSE 291 Topics in Wireless Networking Results Power savings single node Average Power in nW 3 5e 08 3e 08 Offline Online Lookahead 500ms Online Lookahead 1000ms Online Lookahead 2000ms 15 higher at 0 8 2 5e 08 2e 08 1 5e 08 1e 08 8 higher at 0 5 Increasing lookahead 5e 07 5 higher at 0 1 0 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 Offered Load Maximum Capacity CSE 291 Topics in Wireless Networking 0 9 Results Average Delay single node 3000 Average Delay ms 2500 Offline Online Lookahead 500ms Online Lookahead 1000ms Online Lookahead 2000ms 2000 Delay 1 2 lookahead 1500 Increasing lookahead 1000 500 0 0 1 0 2 0 3 0 4 0 5 0 6 Offered Load 0 7 0 8 CSE 291 Topics in Wireless Networking 0 9 Performance summary single node case Online algorithm achieves power savings competitively within 5 8 for light loads with offline algorithm Average delay suffered by packets bounded and predictable Increasing the look ahead achieves better power savings but also introduces higher average delay CSE 291 Topics in Wireless Networking Multi node Scenario Shared broadcast channel One owner manages every node no malicious nodes global power savings CSMA CA based MAC protocol Time synchronization uSec Non negligible packets to send Transmit Range of Yellow Node CSE 291 Topics in Wireless Networking CSMA CA example Load 4 Node A Node A senses the medium and if idle transmits packet Again Node A senses the medium finds idle If collision due to no ack backoff random time Shared Wireless channel Load 3 Node B Node B senses the medium and if idle transmits packet CSE 291 Topics in Wireless Networking Goals Power Saving Achieve power conservation using transmit rate adaptation Self tuning No prior information about arrival patterns number of nodes etc Easy Deployment Apply no changes to any of the existing layers Global properties Global fairness and throughput delay are important CSE 291 Topics in Wireless Networking Simple extension to multiple node case Quantize time into intervals All nodes follow two phase pipelined protocol Each node transmits packets in scheduling phase based on look ahead Throughput total packets total time decreases CSE 291 Topics in Wireless Networking Total Load Estimation Need a distributed way to communicate the overall load in the scheduling phase Na ve way would be to indicate before the start of every interval the load on the network Do not know apriori how many nodes have packets to send Allocating a fixed amount of time to perform load discovery in every interval is wasteful CSE 291 Topics in Wireless Networking Distributed Online Algorithm First node that gets access sends its packets slowly Nodes with packets snoop to determine the Tx rate and the sender If node is sending the first time each node increases its estimate Nodes account for
View Full Document
Unlocking...