Transcript ee380-w07 - Stanford Information Networks Group (SING)

T2: What the Second Generation Holds
Philip Levis
Stanford University
17.i.2007
Moore’s Law
17.i.2007
EE380
2
Bell’s Law
log(users/device)
QuickTime™ and a
TIFF (Uncompressed) decompressor
are needed to see this picture.
1950
17.i.2007
1960
1970
1980
EE380
1990
2000
2010
3
Applications
33m: 111
32m: 110
30m: 109,108,107
QuickTime™ and a
TIFF (Uncompressed) decompressor
are needed to see this picture.
20m: 106,105,104
10m: 103, 102, 101
Sustainable architecture: monitoring
and conserving water/energy use.
Biology: redwood microclimates and trends
QuickTime™ and a
TIFF (Uncompressed) decompressor
are needed to see this picture.
Law enforcement and military:
17.i.2007pinpointing snipers in cities.
EE380
Medicine: monitoring patients
outside the office.
4
Many Tiny Low-Cost Devices
• Weighing the costs
– Cost of device
– Cost of deployment
– Cost of maintenance
• Unseen and in uncontrolled environments
– A tree, a body, a faucet, a river, a vineyard
• Wireless is inherent to embedded sensor networks
– Reduces cost of deployment and maintenance
– Wires not feasible in many environments
17.i.2007
EE380
5
Sensornets Today
Patch
(tiny nodes)
17.i.2007
Transit
Gateway
Backend
(PC, cellphone,
stargate)
(PC)
EE380
6
The Hardware
• Two platform classes: gateway and embedded wireless.
Linux: MB of RAM
Active power: W
Sleep power: mW
TinyOS: KB of RAM
Active power: mW
Sleep power: µW
3 orders of
magnitude
- Energy is defining metric: lifetime, form factor, resources
AA Battery for a year: ~2.7 Ah / (365 days * 24 hours) = 300µA avg. draw
17.i.2007
EE380
7
Moore’s Law
17.i.2007
EE380
8
Moore’s Law with Energy
17.i.2007
EE380
9
Microcontrollers
17.i.2007
EE380
10
A Brand New World
• Cost, scale, lifetime and environment require wireless
– Wireless makes energy the limiting factor
– Moore’s Law has not followed an energy curve
– Need for long-lived deployments means that ultra low-power
nodes must still spend 99% of their time asleep.
• These extreme energy limitations, coupled with long
lifetimes, large numbers, and embedment, completely
change hardware design, software design, OS structure,
network protocols, and application semantics.
17.i.2007
EE380
11
Outline
• A Brave New World
• Platforms and hardware considerations
• Operating systems and software
• Networking and network protocols
• An open alliance
17.i.2007
EE380
12
Sample Platforms
4-10kB RAM
40-250 kbps
17.i.2007
EE380
13
Why So Little?
Power
17.i.2007
EE380
14
Where the mica2 Energy Goes
Active
20-25mA
Idle
13-18mA
Idle, radio off 3mA
110µA
2002
Active Power Draw (mA)
Active Power Draw (mA)
Power-down
20
15
10
5
0
MCU
17.i.2007
radio rx
radio tx
storage
read
storage
write
EE380
25
20
15
MCU
Radio
10
5
0
mica2
15
Where the Telos Energy Goes
Active
18-21mA
Idle
17-20mA
Idle, radio off 50µA
10µA
2004
Active Power Draw (mA)
Active Power Draw (mA)
Power-down
20
15
10
5
0
MCU
17.i.2007
radio rx
radio tx
storage
read
storage
write
EE380
25
20
15
MCU
Radio
10
5
0
Telos revB
16
Lifetime
• 2 AA batteries is ~2700mAh
• To last a year, average draw must be 2-300µA
• Radio is principal cost
Platform
Draw
Lifetime
Mica2 active
20 mA
5.5 days
Mica2 idle
13 mA
8 days
Mica2 power-down
110 µA
~3 years
Telos active
18 mA
6 days
Telos idle
17 mA
6 days
Telos power-down
10 µA
~30 years
17.i.2007
EE380
17
CPU Utilization
(mica2)
Application uses 0.01% 0.4% of the CPU
From “Simulating the Power Consumption of Large-Scale Sensor
Network Applications,” Shnayder et al., SenSys 2004.
17.i.2007
EE380
18
Platform and Hardware Considerations
• Three axes for optimization: sleep power, wakeup times,
and active power
• Radio increasingly dominates power profile
– Low-power reception is critical to long-term deployments
• Need fine-grained control of component power states
– MCU power state depends on external components
• Lowest power states depend on timers
• Platforms are evolving quickly, and there is much variety
– BTnode3, tinynode, etc.
17.i.2007
EE380
19
Outline
• A Brave New World
• Platforms and hardware considerations
• Operating systems and software
• Networking and network protocols
• An open alliance
17.i.2007
EE380
20
In the Beginning
(1999)
• Wireless sensor networks are on the horizon…
• … but what are they going to do?
– What problems will be important?
– What will communication look like?
– What will hardware platforms look like?
• An operating system would provide a common execution
environment for building and researching systems…
• … but how do you design one with these uncertainties?
17.i.2007
EE380
21
TinyOS Goals
(2000)
• Allow fine-grained concurrency
• Require very few resources
• Adapt to hardware evolution
• Support a wide range of applications
• Be robust
• Support a diverse set of platforms
17.i.2007
EE380
22
TinyOS Basics
(2000)
• A program is a set of components
– Components can be easily developed and reused
– Components can be easily replaced
– Components can be hardware or software
• Allow hardware/software boundary to easily change
• Hardware has internal concurrency
– Software must have it as well
• Hardware is non-blocking
– Software must be so as well
17.i.2007
EE380
23
TinyOS Basics, Continued
(2002)
Component
Data Link
Protocol
Data Link
Protocol
Hardware
Crypto
Software
Crypto
Interface
Component
17.i.2007
EE380
Task
24
TinyOS Composition
Application
Tree Routing
Collection
Single-hop packet
Timer
Routing
Packet
17.i.2007
Logging Storage
Timers
Logging
EE380
25
TinyOS Composition
Application
Tree Routing
Collection
Single-hop packet
Timer
Routing
Packet
17.i.2007
Logging Storage
Timers
Logging
EE380
26
TinyOS Goals, Revisited
• Allow fine-grained concurrency: tasks
• Require very few resources: no threads, components
• Adapt to hardware evolution: components
• Support a wide range of applications: flexible boundaries
• Be robust: component encapsulation
• Support a diverse set of platforms: replacing components
17.i.2007
EE380
27
TinyOS Timeline
• 1999: First platform (30 nodes)
• 2000: rene platform, 4-5 groups
• 2002: mica platform, 35+ groups, TinyOS 1.0 released
• 2003: mica2 platform, 100+ groups, TinyOS 1.1 released
• 2004: Telos/micaZ, 200 downloads/day, 100K+ nodes
• 2006: 500K+ nodes, TinyOS 2.0
17.i.2007
EE380
28
TinyOS 2.x
(2005-6)
• Evolution of TinyOS to address recent developments
–
–
–
–
Need for better standardization
Growing community interest and contribution
Increasing platform diversity
Transition from research to commercially viable platform
• Four basic developments
–
–
–
–
17.i.2007
Scheduler: improve robustness and flexibility
Network types: platform interoperability
Platform definition: simplify porting
Power management: OS support for long-term deployments
EE380
29
The Power of Counting
• A TinyOS program is a complete component graph
• Counting across a program is a very powerful primitive
– How many packet senders are there?
– How many timers are used?
– How many tasks are there?
• Only components used by an application are included
• Assigning each element a unique counter
– 3 senders: sender 0, sender 1, sender 2
– 6 timers: timer 0, timer 1, … timer 5
– 8 tasks: task 0, task 1, … task 7
17.i.2007
EE380
30
Tasks and the Scheduler
• Tasks represent internal software concurrency
• A component posts a task, which the OS runs later
• Counting provides compile-time guarantees, leads to simpler
code, and can enforce fairness policies
• 80 cycles (10µs) to post and run a task
17.i.2007
EE380
31
Network Types
• Depending on the processor, there are different data
alignment and layout restrictions
– ARM vs. x86 vs. AVR vs. MSP430
• Network protocols often use “network ordering”
– Big endian, byte aligned, OSes have conversion functions
• TinyOS supports network types at the language level
– Automatically pack/unpack as needed
struct data_packet_t {
nx_am_addr_t source;
nx_am_addr_t dest;
nx_uint8_t; opt;
nx_uint16_t sNo;
nx_uint8_t index;
};
17.i.2007
MSP430
source
opt
index
dest
sNo
x86
source
opt
index
dest
sNo
network type
EE380
source
opt
sNo
dest
32
index
MCU Power States
ATMega128
External
Interrupts
State
External
Clock
Main
Clock
Timer0
EEPROM
ADC,
I/O
Idle
Ext. Standby
Standby
Power-save
Power-down
While waiting for packet reception
or transmission to complete, the
MCU can drop into power-save.
17.i.2007
EE380
While reading/writing packets to
the radio, the MCU cannot drop
below the idle state.
33
Computing a Power State
CC2420
Application
SPI Bus
Scheduler
McuSleep
Hardware State
17.i.2007
EE380
34
Computing a Power State
• Application turns on radio
CC2420
Application
SPI Bus
Scheduler
McuSleep
Hardware State
17.i.2007
EE380
35
Computing a Power State
• Application turns on radio
– Radio sets sleep state dirty
CC2420
Application
SPI Bus
Scheduler
McuSleep
Hardware State
17.i.2007
EE380
36
Computing a Power State
• Application turns on radio
– Radio sets sleep state dirty
CC2420
• Scheduler completes
Application
SPI Bus
Scheduler
– Sees sleep state is dirty,
recalculates sleep state
McuSleep
Hardware State
17.i.2007
EE380
37
Computing a Power State
• Application turns on radio
– Radio sets sleep state dirty
CC2420
• Scheduler completes
Application
SPI Bus
Scheduler
– Sees sleep state is dirty,
recalculates sleep state
– Goes to power-down
McuSleep
Hardware State
17.i.2007
EE380
38
Computing a Power State
• Application turns on radio
– Radio sets sleep state dirty
CC2420
• Scheduler completes
Application
– Sees sleep state is dirty,
recalculates sleep state
– Goes to power-down
SPI Bus
• Packet wakes up TinyOS
Scheduler
McuSleep
Hardware State
17.i.2007
EE380
39
Computing a Power State
• Application turns on radio
– Radio sets sleep state dirty
CC2420
• Scheduler completes
Application
– Sees sleep state is dirty,
recalculates sleep state
– Goes to power-down
SPI Bus
• Packet wakes up TinyOS
Scheduler
– Stack starts reading in
packet from bus
– Bus sets sleep state dirty
McuSleep
Hardware State
17.i.2007
EE380
40
Computing a Power State
• Application turns on radio
– Radio sets sleep state dirty
CC2420
• Scheduler completes
Application
– Sees sleep state is dirty,
recalculates sleep state
– Goes to power-down
SPI Bus
• Packet wakes up TinyOS
Scheduler
– Stack starts reading in
packet from bus
– Bus sets sleep state dirty
McuSleep
• Scheduler completes
Hardware State
17.i.2007
EE380
– Sees sleep state is dirty,
recalculates sleep state
41
Computing a Power State
• Application turns on radio
– Radio sets sleep state dirty
CC2420
• Scheduler completes
Application
– Sees sleep state is dirty,
recalculates sleep state
– Goes to power-down
SPI Bus
• Packet wakes up TinyOS
Scheduler
– Stack starts reading in
packet from bus
– Bus sets sleep state dirty
McuSleep
• Scheduler completes
Hardware State
17.i.2007
EE380
– Sees sleep state is dirty,
recalculates sleep state
– Goes to idle
42
Putting It Together
• Components are lightweight state machines
– Encapsulated state
– Respond to external events
• TinyOS remains reactive with low-overhead tasks
– 80 cycles to post and run
– Allows components to interleave execution cooperatively
• Language techniques to optimize call paths and provide
some compile-time promises of system behavior
• Fine-grained component control enables fine-grained
power management
17.i.2007
EE380
43
The Big Picture
• Clean-slate OS design
– Not an RTOS, significant departures from prior embedded
• Make as much of a program static as possible
– Compile-time, not run-time promises
– Component isolation through careful design
• Language/OS co-design
– Brand-new domain enables breaking out of the law of C
• Hide complexity when possible, expose it when needed
– As we better understand sensornets and their requirements,
versions of TinyOS can provide more policy
17.i.2007
EE380
44
Outline
• A Brave New World
• Platforms and hardware considerations
• Operating systems and software
• Network protocols and a network architecture
• An open alliance
17.i.2007
EE380
45
Networking and Network Protocols
• United States National Research Council thesis:
“embedded sensor networks are different.”
– Embedment, energy limitations, data-centric operation
– They’re not just a new set of IP devices
• If not IP, what are they?
– What are the critical services and mechanisms?
– What does a sensornet protocol stack look like?
– Maybe it is just IP…
17.i.2007
EE380
46
Testing the Hypothesis
• We don’t know what these networks will look like, so we’ll
build a framework so everyone can figure it out
• TinyOS: component-based OS
– Can easily switch components
– Designed for and supports major requirements: low power,
hardware diversity, robustness, etc.
• A lot of people start using TinyOS, and 6 years later…
17.i.2007
EE380
47
Sensor Network Protocols Today
Application
Regions EnviroTrack
Hood
FTSP
Transport
Diffusion
SPIN
TTDD
Deluge
MMRP
Network
TORA
CGSR
AODVDSR
ARA
GSR
DBF
DSDV
TBRPF
Resynch
SMAC
PAMAS
Link/MAC
GPSR
Drain
SPAN
17.i.2007
RadioMetrix
RFM
GRAD
WooMac
BMAC
ZMAC
eyes
TOSSIM
EE380
FPS
Yao
Pico
CC1000
MintRoute
GAF
Bluetooth
Phy
Drip
Arrive
Ascent
TMAC
WiseMAC
STRAW
Trickle
ReORg
PC
Topology
TinyDB
802.15.4
nordic
48
Defining an Architecture
• Protocol research, applications, and real deployments
show sensornets to have a diverse set of requirements
– Traditional layer boundaries do not fit well
• Commonalities emerge from these diverse efforts
• From these commonalities we can begin to understand
and define a sensor network architecture
– Provide a structure for protocols and
applications, separating concerns and
promoting interoperability
17.i.2007
EE380
49
Why a New Architecture?
• Short answer: we haven’t seen IP take over
• Long answer: the Internet assumes a usage model
– Independent end-to-end flows
– Host-centric communication
– Edge networks with a shared infrastructure
• Sensor networks do not follow this model
– Collaborative protocols
– Data-centric communication
– Sensing removes distinction between edge and core
17.i.2007
EE380
50
The Two Major Protocols
• Most simple sensornets start with two
protocols
• Protocol 0: Dissemination
– Reliably deliver data to every node in a
network
– Reconfiguration, programs, queries
– Basic mechanism for network control
• Protocol 1: Collection
– Deliver data from every node to one or
more sinks
– Basic mechanism for gathering data
17.i.2007
EE380
51
Dissemination
• Use local broadcasts and packet suppression
– Scale to a wide range of densities
– Control transmissions over space
• 100% eventual reliability
– Disconnection, repopulation, etc.
– Continuous process
• Maintenance: exchange metadata (e.g., version numbers,
hashes) at a low rate to ensure network is up to date
• Propagation: when a node detects an inconsistency, the
network quickly broadcasts the new data
17.i.2007
EE380
52
Trickle
• Polite gossip: “Every once in a while, broadcast what data
you have, unless you’ve heard some other nodes
broadcast the same thing recently.”
• Energy efficient, fast, and scalable
– Maintenance: a few sends per hour
– Propagation: across large multihop networks in seconds
– Scalability: thousand-fold changes in density
17.i.2007
EE380
53
Trickle Algorithm
• Time interval of length t
• Redundancy constant k (e.g., 1, 2)
• Maintain a counter c
• Pick a time t from [0, t]
• At time t, transmit metadata if c < k
• Increment c when you hear identical metadata to your own
• Transmit updates when you hear older metadata
• At end of t, pick a new t
17.i.2007
EE380
54
Example Trickle Execution
k=1
c
A
0
B
0
C
0
t
time
transmission
17.i.2007
suppressed transmission
EE380
reception
55
Example Trickle Execution
k=1
c
A
0
B
1
C
0
tA1
t
time
transmission
17.i.2007
suppressed transmission
EE380
reception
56
Example Trickle Execution
k=1
c
A
0
B
2
C
0
tA1
t
tC1
time
transmission
17.i.2007
suppressed transmission
EE380
reception
57
Example Trickle Execution
k=1
c
A
0
B
2
C
0
tA1
tB1
t
tC1
time
transmission
17.i.2007
suppressed transmission
EE380
reception
58
Example Trickle Execution
k=1
c
A
0
B
0
C
0
tA1
tB1
t
tC1
time
transmission
17.i.2007
suppressed transmission
EE380
reception
59
Example Trickle Execution
k=1
c
A
1
B
0
C
1
tA1
tB1
t
tB2
tC1
time
transmission
17.i.2007
suppressed transmission
EE380
reception
60
Example Trickle Execution
k=1
c
A
1
B
0
C
1
tA1
tB1
t
tB2
tC1
tC2
time
transmission
17.i.2007
suppressed transmission
EE380
reception
61
Example Trickle Execution
k=1
c
A
1
B
0
C
1
tA1
tA2
tB1
t
tB2
tC1
tC2
time
transmission
17.i.2007
suppressed transmission
EE380
reception
62
Example Trickle Execution
k=1
c
A
0
B
0
C
0
tA1
tA2
tB1
t
tB2
tC1
tC2
time
transmission
17.i.2007
suppressed transmission
EE380
reception
63
Propagation
• Simulated 400 node 16 hop
network
• Time to reception in seconds
Time To Reprogram, Tau, 10 Foot Spacing
(seconds)
18-20
16-18
14-16
12-14
10-12
• Set tl = 1 sec, th = 1 min
• 20s for 16 hops
• Wave of activity
8-10
6-8
4-6
2-4
0-2
Time
• Real 71 node 8 hop network
• Time to reception in seconds
• Set tl = 1 sec, th = 1 min
• Time to “catch,” long tail
17.i.2007
EE380
64
Trickle Overview
• Trickle scales logarithmically with density
• Can obtain rapid propagation with low maintenance
– In example deployment, maintenance of a few sends/hour,
propagation of 30 seconds
• Controls a transmission rate over space
– Coupling between network and the physical world
• Trickle is a nameless protocol
– Uses wireless connectivity as an implicit naming scheme
– No name management, neighbor lists…
– Stateless operation (well, eleven bytes)
17.i.2007
EE380
65
The Internet Narrow Waist
• The Internet narrow waist is at
the network layer: IP
• Separate many transport and
application protocols from
underlying data-link technologies
• But sensornets have many
different network protocols
(collection, dissemination, etc.)
• Local coordination and
communication pushes the
narrow waist downwards…
17.i.2007
EE380
66
Sensor Network Narrow Waist
• Hypothesis: in sensor networks, the narrow waist of is at
layer 2 (single hop)
• But there are many L2 packet formats and protocols
– International spectrum allocation
– Media access
• Work at the network layer and above can provide
guidance on what the narrow waist needs to provide
17.i.2007
EE380
67
Narrow Waist Proposal: FWP
• Fair Waiting Protocol
– A multihop protocol receives a fair share of local bandwidth
– Also provides protocol isolation
• Basic mechanism: grant-to-send
– Every transmission has an optimal time value t
– Only the recipient may transmit during this time t
• Current area of active work
A
B
C
SINK
X
X
17.i.2007
EE380
68
Sensor Network Architecture
• Edge devices within the larger Internet cloud
– Not transit networks
• Data-centric within
–
–
–
–
Collaborative operation
Snooping, address-free
Complex single-hop requirements
Traditional layers do not apply
• Addressable from without
– Management, configuration, etc.
17.i.2007
EE380
69
IETF 6lowpan WG
• Question: how do you connect a low-power embedded
wireless network to the larger Internet with IPv6?
• Wide range of issues:
–
–
–
–
–
–
–
–
IP adaptation/Packet Formats and interoperability
Addressing schemes and address management
Network management
Routing in dynamically adaptive topologies
Security, including set-up and maintenance
Application programming interface
Discovery (of devices, of services, etc)
Implementation considerations
• Definition without evaluation is dangerous…
– Per-hop vs. end-to-end fragmentation and assembly
– Cost: prr-(f+h) vs. fh x prr-1
17.i.2007
EE380
70
Outline
• A Brave New World
• Platforms and hardware considerations
• Operating systems and software
• Network protocols and a network architecture
• An open alliance
17.i.2007
EE380
71
Changing the World
33m: 111
32m: 110
QuickTime™ and a
TIFF (Uncompressed) decompressor
are needed to see this picture.
30m: 109,108,107
20m: 106,105,104
10m: 103, 102, 101
17.i.2007
QuickTime™ and a
TIFF (Uncompressed) decompressor
are needed to see this picture.
EE380
72
TinyOS Alliance
• Low-power wireless embedded networks need a close
collaboration between academia and industry
– Many unsolved problems
– Revisiting old assumptions
– Remaining grounded in practical concerns
• The TinyOS Alliance mission
– “Provide a forum to facilitate… the development and
maintenance of a stable,technically-sound base of TinyOS
technology and surrounding tools through the creation of
standard interfaces and protocols, vetted extensions, open
reference implementations, technical documents,testing and
verification suites, and educational materials…”
17.i.2007
EE380
73
TinyOS Alliance Structure
(tentative)
• Grassroots: it’s about the
contributors and their
work
Steering
Committee
– Follow an IETF model
• Members, corporate
members, contributing
members
WG
WG
WG
Members
• Working groups
• Steering committee
17.i.2007
EE380
74
Learn, Participate, and Use
http://www.tinyos.net/
17.i.2007
EE380
75
Questions
17.i.2007
EE380
76