CS 410/510 Sensor Networks Portland State Universityweb.cecs.pdx.edu/~nbulusu/courses/cs497-win10/lectures/Lecture8-… · Each piconet has a master and up to 7 slaves ... Extend

2/9/2009 Nirupama Bulusu 1

CS 410/510 Sensor NetworksPortland State University

Lecture 7

Energy Conservation and Harvesting


Source Acknowledgements

Wei Ye and John Heidemann USC Information Sciences Institute

Deborah Estrin

Aman Kansal

Mani Srivastava


Energy Conservation


Characteristics of a Sensor Network

A special wireless ad hoc network Large number of nodes Battery powered Topology and density change Nodes for a common task In-network data processing

Sensor-net applications Sensor-triggered bursty traffic Can often tolerate some delaySpeed of a moving object places a bound on network

reaction time

Energy efficiency

Scalability & Self-configuration

Fairness not important

Message-level Latency

Trade for energy

Adaptivity

Adaptivity


Network-level Opportunities forEnergy Conservation

Radio Transmission Power Control

Medium Access Control (MAC)

Topology-control

Routing


Radio Transmission Power Control

Why adjust transmission power?Guarantee network connectivity

Control network density/encourage spatial reuse

Minimize transmission power => reduced energy consumption (also due to reduced contention)


Example

a cb d

R

r

Let R = 3r, energy consumption inversely proportional to d2

Cost of transmitting a-d = 3 (a-b-c-d)


MAC and Its Classification

Medium Access Control (MAC)When and how nodes access the shared channel

Classification of MAC protocolsScheduled protocolsSchedule nodes onto different sub-channels

Examples: TDMA, FDMA, CDMA

Contention-based protocolsNodes compete in probabilistic coordination

Examples: ALOHA (pure & slotted), CSMA


MAC Attributes

Collision avoidanceBasic task of a MAC protocol

Energy efficiency

Scalability and adaptabilityNetwork size, node density and topology change

Channel utilization

Latency

Throughput

Fairness

Primary

Secondary


Energy Efficiency in MAC DesignEnergy is primary concern in sensor networks

What causes energy waste?Collisions

Control packet overhead

Overhearing unnecessary traffic

Long idle timebursty traffic in sensor-net apps

Idle listening consumes 50—100% of the power for receiving (Stemm97, Kasten)

Dominant factor


Scheduled Protocols

Time Division Multiple Access (TDMA)

Advantages No collisions Energy efficient — easily support low duty cycles

Disadvantages Poor scalability and adaptability

• Difficult to accommodate node changes• Difficult to handle inter-cluster communication

Requires strict time synchronization


Polling A master plus one or more slaves (star topology)

The master node decides which slave can send by polling the corresponding slave

Only direct communication between the master and a slave

A special TDMA without pre-assigned slots

ExamplesIEEE 802.11 infrastructure mode (CFP)

Bluetooth piconets

Scheduled Protocols


Self-Organization — by Sohrabiand PottieHave a pool of independent channelsFrequency band or spreading codePotential interfering links select different

channelsTalk to neighbors in different time slotsSleep in unscheduled time slotsLooks like TDMA, but actually FDMA or

CDMAAny pair of two nodes can talk at the

same timeLow bandwidth utilization

Scheduled Protocols

1 3

42


Scheduled ProtocolsBluetoothTarget for wireless personal area network

(WPAN)Short range, moderate bandwidth, low latency

IEEE 802.15.1 (MAC + PHY) is based on Bluetooth

Nodes are clustered into piconetEach piconet has a master and up to 7 slaves –

scalability problem

The master polls each slave for transmission

Frequency-hopping CDMA between clusters

Multiple connected piconets form a scatternetDifferent to handle inter-cluster communications


Scheduled Protocols

Bluetooth (Cont.)How about Bluetooth radio with sensor networks?

Scalability is a big problem

Lack of multi-hop supportNo commercial Bluetooth radio supports scatternet so far

Use two radios – expensive and energy inefficient

A node temporarily leave one piconet and joins another – high overhead and long delay

Connection maintenance is expensive even with a low-duty-cycle mode (Leopold et al.)


Scheduled Protocols

LEACH: Low-Energy Adaptive Clustering Hierarchy — by Heinzelman, et al.Similar to Bluetooth

CDMA between clusters

TDMA within each clusterStatic TDMA frame

Cluster head rotation

Node only talks to cluster head

Only cluster head talks to base station (long dist.)

The same scalability problem


Contention-based protocolsCSMA — Carrier Sense Multiple AccessListening before transmitting

Not enough for multi-hop networks (collision at receiver)

CSMA/CA (CA stands for Collision Avoidance)RTS/CTS handshake before send data

Other nodes (e.g. node c) backoff

Contention-Based Protocols

a b c

Hidden terminal: a is hidden from c’s carrier sense



Contention-based protocols (contd.)MACA — Multiple Access w/ Collision

AvoidanceAdd duration field in RTS/CTS informing other node

about their backoff time

MACAW — improved over MACARTS/CTS/DATA/ACK

Fast error recovery at link layer

IEEE 802.11 Distributed Coordination Function (DCF)Largely based on MACAW


Contention-Based Protocols IEEE 802.11 DCF: ad hoc modeVirtual and physical carrier sense (CS)Network allocation vector (NAV), duration field

Binary exponential backoff

RTS/CTS/DATA/ACK for unicast packets

Broadcast packets are directly sent after CS

Fragmentation supportRTS/CTS reserve time for first (fragment + ACK)

First (fragment + ACK) reserve time for second…

Give up transmission when error happens



Tx rate control — by Woo and CullerBased on a special network setupA base station tries to collect data equally from all

sensors in the network

CSMA + adaptive rate control

Promote fair bandwidth allocation to all sensorsNodes close to the base station forward more traffic,

and have less chances to send their own data

Helps in congestion avoidance


Scheduled vs. Contention Protocols

Loose or not required

StrictTime synchronization

EasyDifficultMulti-hop communication

GoodBadScalability and adaptation

BadGoodEnergy efficiency

YesNoCollisions

Contention Protocols

Scheduled Protocols


Energy Efficiency in Contention-Based Protocols

Contention-based protocols need to work hard in all directions for energy savingsReduce idle listening – support low duty cycleBetter collision avoidanceReduce control overheadAvoid unnecessary overhearing


Energy-Efficient MAC Design

PAMAS: Power Aware Multi-Access with Signalling — by Singh and RaghavendraImprove energy efficiency from MACA

Avoid overhearing by putting node into sleep

Use separate control and data channelsRTS, CTS, busy tone to avoid collision

Probe packets to find neighbors transmission time

Increased hardware complexityTwo channels need to work simultaneously, meaning

two radio systems.



Piconet — by Bennett, Clarke, et al.Not the same piconet in BluetoothLow duty-cycle operation — energy efficientSleep for 30s, beacon, and listen for a whileSending node needs to listen for receiver’s beacon

first, thenCSMA before sending data

May wait for long time before sending



Asynchronous sleeping – by Tseng, et al.Extend 802.11 PS mode to Multi-hops

Nodes do not synchronize with each other

Designed 3 sleep patterns — ensure nodes listen intervals overlap, example:Periodically fully-awake interval: similar to S-MAC

Problem on broadcast — wake up each neighbor



ZigBee Industry standard

through application profiles running over IEEE 802.15.4 radios

Target applications are sensors networks, interactive toys, smart badges, remote controls, and home automation



ZigBee (Cont.)Three devices specifiedNetwork Coordinator

Full Function Device (FFD)• Can talk to any device, more computing power

Reduced Function Device (RFD)• Can only talk to a FFD, simple for energy conservation

CSMA/CA with optional ACKs on data packets

Optional beacons with superframes

Optional guaranteed time slots (GTS), which supports contention-free access



ZigBee (Cont.)Low power, low rate (250kbps) at physical layer

MAC layer supports low duty cycle operationTarget node life time > 1 year


Case Study: S-MAC

S-MAC — by Ye, Heidemann and Estrin

Tradeoffs

Major components in S-MACPeriodic listen and sleep

Collision avoidance

Overhearing avoidance

Message passing

LatencyFairness

Energy


Coordinated Sleeping

Problem: Idle listening consumes significant energy!

Solution: Periodic listen and sleep

• Turn off radio when sleeping• Reduce duty cycle to ~ 10% (120ms on/1.2s off)

sleeplisten listen sleep

Latency Energy



Schedules can differ

• Prefer neighboring nodes have same schedule— easy broadcast & low control overhead

Border nodes:two schedules orbroadcast twice

Node 1

Node 2



Schedule 2

Schedule 1



Schedule Synchronization New node tries to follow an existing schedule

Remember neighbors’ schedules — to know when to send to them

Each node broadcasts its schedule every few periods of sleeping and listening

Re-sync when receiving a schedule update

Periodic neighbor discoveryKeep awake in a full sync interval over long

periods



Adaptive listening Reduce multi-hop latency due to periodic sleep

Wake up for a short period of time at end of each transmission

41 2 3

CTS

RTS

CTS

Reduce latency by at least half

listen listenlistent1 t2


Collision Avoidance

S-MAC is based on contention

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 sequence


Overhearing AvoidanceProblem: Receive packets destined for

othersSolution: Sleep when neighbors talkBasic idea from PAMAS (Singh, Raghavendra 1998)

But we only use in-channel signaling

Who should sleep?All immediate neighbors of sender and receiver

How long to sleep?The duration field in each packet informs other

nodes the sleep interval


Message Passing

Problem: Sensor net in-network processing requires entire message

Solution: Don’t interleave different messagesLong message is fragmented & sent in burst

RTS/CTS reserve medium for entire message

Fragment-level error recovery — ACK

— extend Tx time and re-transmit immediately

Other nodes sleep for whole message time

Fairness EnergyMsg-level latency


ImplementationPlatformMica Motes (UC Berkeley) 8-bit CPU at 4MHz,

128KB flash, 4KB RAM

20Kbps radio at 433MHz

TinyOS: event-driven

Configurable S-MAC optionsLow duty cycle with adaptive listen

Low duty cycle without adaptive listen

Fully active mode (no periodic sleeping)


Experiments: Two-hop network Topology, measured energy consumption on source

nodes

Source 1

Source 2

Sink 1

Sink 2

• S-MAC consumes much less energy than 802.11-like protocol w/o sleeping

• At heavy load, overhearing avoidance is the major factor in energy savings

• At light load, periodic sleeping plays the key role

0 2 4 6 8 10

200

400

600

800

1000

1200

1400

1600

1800Average energy consumption in the source nodes

Message inter-arrival period (second)

En

erg

y c

on

sum

pti

on

(m

J)

802.11-like protocolwithout sleep

Overhearingavoidance

S-MAC w/o adaptive listen


0 2 4 6 8 100

5

10

15

20

25

30

Message inter-arrival period (S)

En

erg

y co

nsu

mp

tion

(J)

10% duty cycle without adaptive listen

No sleep cycles

10% duty cycle with adaptive listen

Energy consumption at different traffic load

Energy Consumption over Multi-Hops Ten-hop linear network at different traffic load

3 S-MAC

configurations

At light traffic load, periodic sleeping has significant energy savings over fully active mode

Adaptive listen saves more at heavy load by reducing latency


Latency as Hops Increase

Adaptive listen significantly reduces latency causes by periodic sleeping

0 2 4 6 8 100

2

4

6

8

10

12Latency under highest traffic load

Number of hops

Ave

rage

mes

sage

late

ncy

(S)

10% duty cycle withoutadaptive listen


No sleep cycles

0 2 4 6 8 100

2

4

6

8

10

12Latency under lowest traffic load

Number of hops

Ave

rage

mes

sage

late

ncy

(S)


10% duty cycle withadaptive listen

No sleep cycles


Throughput as Hops Increase

Adaptive listen significantly increases throughput

0 2 4 6 8 100

20

40

60

80

100

120

140

160

180

200

220Effective data throughput under highest traffic load

Number of hops

Effe

ctiv

e da

ta th

roug

hput

(B

yte/

S)

No sleep cycles


10% duty cycle without adaptive listen

Using less time to pass the same amount of data


Combined Energy and Throughput

Periodic sleeping provides excellent performance at light traffic load

With adaptive listening, S-MAC achieves about the same performance as no-sleep mode at heavy load 0 2 4 6 8 10

0

0.5

1

1.5

2

2.5

3

Message inter-arrival period (S)

Ene

rgy-

time

prod

uct p

er b

yte

(J*S

/byt

e)

Energy-time cost on passing 1-byte data from source to sink

No sleep cycles




#3: Topology Control

Between MAC and routing

Turn off as many nodes as possibleLeave only enough on to keep a connected topologyEnsures data can transit through network

Topology control vs. MACOperate at much coarser timescales

Cycle radios on the order of minutes rather than seconds


Examples

Geography-based Use physical location to infer network coverage.

Divide physical area into grids, select one node per grid.

Topology-basedDirectly measure network connectivity

Select node in topology if two of its neighbors cannot talk to each other

Energy savings depend on network density

Node mobility


#4: Energy-efficient Routing

Minimize energy cost per packet

Balance energy consumption in the network.

More in next lecture


Conclusion

Energy conservation active area of research

Current workTransmission power control

MAC protocol design

Topology control

Routing


Energy Harvesting


Sources

Chapter 9: Energy Harvesting Aman Kansal and Mani Srivastava

Sensor-coordinated actuation for energy harvestingMohammed Rahimi et al


Energy harvesting

Batteries are too big

Batteries do not last forever

Methods exist to extract energy from the environmentThermoelectric (DARPA, JPL, Caltech)

Micro-hydraulic transducer (DARPA, MIT)

Solar cells

Bio-fuel (University of Bristol)


Managing Harvested Energy

It is different from battery energySupply varies with timeNeed to adapt performance

Supply varies with spaceDifferent nodes get different energy

Need load sharing

Supply is repetitive (does not die out)Opportunity to last forever

Efficiency ConcernsMatch load to maximize transfer

Supply direct when possible, instead of through battery


Example

Which route to choose?

source

destination


Managing Harvested Energy

Key issuesUse available energy most efficiently

Estimate achievable performance level

Harvesting Technology

Harvesting Circuit

Scheduler

DeploymentSpecificChoice

•Buffering (batteryor ultra-capacitor)•Consumption

Arbitration•Tracking availability

Performance ScalingNetwork-wide task scheduling


Harvesting Circuit

System Block Diagram

Harvestingdevice

Energy Tracker

Energy storageDevice

Rechargingcircuit

ConsumptionArbiter Sub-module

Power switching

HarvestingAwarePower management

SensorNode

E

data


Scheduler Design

Scale performance; match availability; last forever

Track environmental availability

Kansal’s

Approach

Battery makes up for discrepancy, node dies when out of battery

Recharge battery and let the load use energy as desired

Existing

Approach

Supply is independent of demand

Environmental

energy supply is variable

Problem


Source Characterization

What is available from the variable environmental source?

Leaky bucket like model for bursty energy supply

E(t) is a (ρ,σ1,α2) source if for all T:

E(t) integral over 0 to T is

>= (ρT – σ1)

<= (ρT + σ2)


Interesting Questions

Given the source parameters:What is the achievable application throughput

or latency?

Can the system last eternally at required performance level?What additional resources are required, if not?

Considering efficiencies of batteries and other power modes, how should the tasks be scheduled?


Harvesting Theory

Theorem: If a system is powered by a (ρ,σ1,σ2) source

has energy capacity >= (σ1+ σ2)

Operates at a constant power level ρ

Then1. It utilizes the energy source fully

2. Can survive forever


Performance control

Sleep and active modes

Dynamic voltage scaling

Radio range control

Sub-module power switching

Learn energyenvironment parameters

Predict SustainablePerformance

level

AdaptPerformance

ρ = xPmax + (1 –x)Psleep


Multi-server Harvesting

How can a distributed system manage the harvested energy to maximize performance of the system as a whole?Energy resources vary across nodes

Task-load differs at different nodes

Some workload is shareable while some is not

Consider one energy intensive task: routing dataDetermine environmental energy aware communication

strategy


Routing Options

Optimal routing is impractical

Nodes share state information and coordinate performance adaptation actions

Nodes adapt performance locally and routing protocol operates over sleepy nodes


Practical Networking Method

Routing for an event monitoring sensor networkSingle sink (base station), multiple sources (node

monitoring events)

Must report event when it occurs; otherwise no data

Measure energy and calculate duty-cycle locallyDuty cycle determines latency of data relaying

Sensor

Sleep Timer

Sensor Node

Event detected

Timerexpired

Snooze:ProcessorAnd radiosleeping


Communication with Sleep Mode

Node can wake up if it has data to send

How does a sleeping node receive data?


Routing Tree

Protocol Base station sends INIT Receiver sends ACK and forwards INIT

Reverse path set up to base station Possibly shortest; but not necessarily lowest latency

Base stationINIT

ACK


Network-wide Performance

Estimate network-wide latency constraint with observed environmental resource

Central control over network latency is impracticalSending all latencies to base station reduces scalability

Use in-network processing to compute path latencyReceive path latencies from children

Forward highest plus own latency


Conclusions

Harvesting technologies can enable long system lifetimeProof-of-concept system and algorithms to exploit

environmental energy demonstrated

Methods are needed to measure and characterize energy sourcesBattery characterization is not sufficient

Distributed methods are required to optimally adapt global performanceSchedule tasks appropriately in space and time to

enhance performance

Documents

CS 410/510 Sensor Networks Portland State Universityweb.cecs.pdx.edu/~nbulusu/courses/cs497-win10/lectures/Lecture8-… · Each piconet has a master and up to 7 slaves ... Extend