An Energy-Efficient MAC Protocol for Wireless Sensor NetworksIntroductionMedium Access Control in Sensor NetsEnergy Efficiency in MACReminder: IEEE 802.11 MACBig problem with existing wireless MACsIdle listening in 802.11Slide 8Sensor-MAC (S-MAC) DesignPeriodic Listen and SleepSlide 11Periodic Listen and Sleep - Choosing and Maintaining SchedulesSlide 13Periodic Listen and Sleep - Schedule SynchronizationSlide 15Collision AvoidanceOverhearing AvoidanceMessage PassingEnergy Savings vs. Increased LatencySleep delay and Relative energy savingsImplementation on Testbed NodesExperimentsConclusionsQuestions?An Energy-Efficient MAC Protocol for Wireless Sensor NetworksWei Ye, John Heidemann, Deborah Estrin-- Adapted the authors’ Infocom 2002 talkIntroductionWireless sensor network•Special ad hoc wireless network•Large number of nodes w/ sensors & actuators•Battery-powered nodes  energy efficiency•Unplanned deployment  self-organization•Node density & topology change  robustnessSensor-net applications•Nodes cooperate for a common task•In-network data processingMedium Access Control in Sensor NetsImportant attributes of MAC protocols1. Collision avoidance2. Energy efficiency3. Scalability in node density4. Latency5. Fairness6. Throughput7. Bandwidth utilizationPrimarySecondaryMajor sources of energy waste•Idle listeningEnergy consumption of typical 802.11 WLAN cardsidle:receive:send — 1:1.05:1.4, 1:2:2.5 (Stemm 1997)Example: directed diffusion (Intanagonwiwat 2000)Energy Efficiency in MAC00.020.040.060.080.10.120.140 50 100 150 200 250 300Average Dissipated Energy (Joules/Node/Received Event)Network SizeDiffusionOmniscient MulticastFlooding00.0020.0040.0060.0080.010.0120.0140.0160.018050 100 150 200 250 300Average Dissipated Energy (Joules/Node/Received Event)Network SizeDiffusionOmniscient MulticastFloodingOver always-listening MACOver energy-aware MACReminder: IEEE 802.11 MACVery popular wireless MAC protocolTwo modes: DCF (distributed coordination function) & PCF (point coordination function)DCF is based on CSMA/CA ≈ CSMA + MACA•RTS-CTS-DATA-ACK•Physical carrier sensing + NAV (network allocation vector) containing time value that indicates the duration up to which the medium is expected to be busy due to transmissions by other nodes•Every packet contains the duration info for the remainder of the message•Every node overhearing a packet continuously updates its own NAV for virtual carrier sensingIFS (inter frame spacing)•Short IFS (SIFS), PCF IFS (PIFS), DCF IFS (DIFS), Extended IFS (EIFS)Big problem with existing wireless MACsIdle listening•Does anybody send me a RTS?•Does anyone send CTS to my neighbor which I want to communicate with?•Huge energy consumption!PAMAS (Power Aware Medium Access with Signaling)•Separate radio channel for RTS/CTS•Sleep for the duration of the transmission indicated in the control packets  S-MAC aims to achieve this without requiring a separate channel for RTS & CTSIdle listening in 802.11RTS & CTS only reserves the medium for the first data fragment & the first ACKThe 1st fragment & ACk reserves the medium for the 2nd fragment and so onAfter overhearing a fragment or an ACK, a neighboring node knows that there is one more fragment to be sent •It has to keep listening until all the fragments are sent •Promote fairness; If the sender fails to get ACK after sending a fragment, it must give up the transmission and recondtend for the medium•For in-network processing, an entire message is needed in sensor networks  802.11 may cause a largee delayMajor sources of energy waste (cont.)•Idle listeningLong idle time when no sensing event happens•Collisions•Control overhead•OverhearingReduce energy consumption from all above sourcesCombine benefits of TDMA + contention protocolsEnergy Efficiency in MACCommon to all wireless networksDominant in sensor netsSensor-MAC (S-MAC) DesignTradeoffsMajor components in S-MAC•Periodic listen and sleep•Collision avoidance•Overhearing avoidance•Massage passingLatencyFairnessEnergyPeriodic Listen and SleepProblem: Idle listening consumes significant energySolution: Periodic listen and sleep•Turn off radio when sleeping•Reduce duty cycle to ~ 10% (200ms on/2s off)sleeplistenlistensleepLatencyEnergyPeriodic Listen and SleepSchedules can differ•Prefer neighboring nodes have same schedule— easy broadcast & low control overheadBorder nodes: two schedules broadcast twiceNode 1Node 2sleeplisten listensleepsleeplisten listensleepSchedule 2Schedule 1Each nodes has a schedule table- Stores the schedules of all its known neighbors1. Listens for a certain amount of time - If it doesn’t hear a schedule, it becomes a synchronizer - It randomly chooses a schedule and broadcast it in SYNC message- SYNC message indicates that it will go to sleep after t secondsPeriodic Listen and Sleep - Choosing and Maintaining Schedules2. If the node receives a schedule before choosing its own schedule, it follows that schedule- follower- waits for a random delay td and re-broardcasts this schedule, indicating that it will sleep in t – td 3. If a node receives a different schedule after it selects and broadcast (border node)- adopts both schedules - less time to sleep - consume more energyPeriodic Listen and Sleep - Choosing and Maintaining SchedulesPeriodic Listen and Sleep - Schedule Synchronization Remember neighbors’ schedules — to know when to send to themEach node broadcasts its schedule for multiple periods of sleeping and listening•Update period can be long, e.g., tens of secondsRe-sync when receiving a schedule updateSync packets also serve as beacons for new nodes to join a neighborhoodListenFor SYNCFor RTS SleepReceiverSender 1Sender 2Sender 3Sleep SYNCCSCSCSCS SYNC RTS RTS Send data if CTS received Send data if CTS received Figure 2. Timing relationship between a receiver and different sendersPeriodic Listen and SleepCollision AvoidanceProblem: Multiple senders want to talkOptions: Contention vs. TDMASolution: Similar to IEEE 802.11 ad hoc mode (DCF)•Physical and virtual carrier sense•Randomized backoff time•RTS/CTS for hidden terminal problem•RTS/CTS/DATA/ACK sequenceOverhearing AvoidanceProblem: Receive packets destined to others•In 802.11, each node keeps listening to all transmissions from its neighbors for