Transcript Berkeley NOW - Computer Science Division

Networks of Tiny Devices embedded in
the Physical World
David Culler
Computer Science Division
U.C. Berkeley
www.cs.berkeley.edu/~culler
Intel Research
Berkeley
Technology Push
• Complete network embedded systems going
microscopic
Processing
Storage
Power
Sensing
Actuation
Communication
I SDQ SD
PLL baseband
filters
mixer
LNA
1/17/2002
TinyOS CSTB
2
Application Pull
• Complete NW embedded systems going microscopic
• Huge space of new applications
Monitoring & Managing Spaces
Disaster
Management
Habitat Monitoring
Circulatory Net
Condition-based
maintenance
Ubiquitous
computing
1/17/2002
TinyOS CSTB
3
Bridging the Technology-Application Gap
• Power-aware, communication-centric node
architecture
• Tiny Operating System for Range of HighlyConstrained Application-specific environments
• Network Architecture for vast, self-organized
collections
• Programming Environments for aggregate
applications in a noisy world
• Distributed Middleware Services (time, trigger,
routing, allocation)
• Techniques for Fine-grain distributed control
• Demonstration Applications
1/17/2002
TinyOS CSTB
4
A de facto platform for EmNets
• Developed a series of wireless sensor devices
•
•
•
•
•
TinyOS concurrency framework
Messaging Model
Networking stacks (RF and Serial)
Multihop routing
Several Key components
– sensing, logging, data filters, broadcast
• Simulation tools
• DARPA NEST OEP
1/17/2002
TinyOS CSTB
5
Many Research Groups on board
• UCB
–
–
–
–
–
–
–
•
•
•
•
•
•
NEST
SensorWeb
Blackout
Glaser structures
CBE
BFD
BRWC
UCLA
USC
Rutgers winlab
Intel
Bosch
Crossbow
1/17/2002
•
•
•
•
•
•
•
•
•
•
•
U Wash
Rutgers
UIUC
NCSA
U Virginia
Ohio State
UCSD
Dartmouth
MIT
Accenture
and soon many more
TinyOS CSTB
6
A Operating System for Tiny Devices?
• Traditional approaches
– command processing loop (wait request, act, respond)
– monolithic event processing
– bring full thread/socket posix regime to platform
• Alternative
– provide framework for concurrency and modularity
– never poll, never block
– interleaving flows, events, energy management
=> allow appropriate abstractions to emerge
1/17/2002
TinyOS CSTB
7
Tiny OS Concepts
• Scheduler + Graph of Components
init
Commands,
Event Handlers
Frame (storage)
Tasks (concurrency)
Messaging Component
– frame per component, shared stack, no
heap
• Very lean multithreading
• Efficient Layering
1/17/2002
TinyOS CSTB
internal thread
Internal
State
TX_pack
et_done
(success
RX_pack
)et_done
(buffer)
• Constrained Storage Model
init
Power(mode)
TX_packet(buf)
–
–
–
–
msg_rec(type, data)
msg_sen
d_done)
• Component:
Events
send_msg
(addr,
type, data)
Commands
power(mode)
– constrained two-level scheduling model:
threads + events
8
application
Application = Graph of Components
Route map
router
sensor appln
packet
Radio byte
bit
Radio Packet
byte
Active Messages
RFM
1/17/2002
Serial Packet
UART
Temp
photo
ADC
SW
HW
clocks
TinyOS CSTB
Example: ad hoc, multi-hop
routing of photo sensor
readings
3450 B code
226 B data
Graph of cooperating
state machines
on shared stack
9
Demonstration applications
• 29 Palms
• Cory Hall network
– ½ million packets over 3 weeks
•
•
•
•
•
•
Surge network and environment display
800 node ad hoc network
CBE
Glaser Shakes
Granlibakken retreat watcher
Robomote
=> continued application focus
• more real and long lived
• more dynamics
• extract architecture and create framework
1/17/2002
TinyOS CSTB
10
Example TinyOS study
• UAV drops 10 nodes along road,
– hot-water pipe insulation for package
•
•
•
•
•
•
•
•
Nodes self-configure into linear network
Synchronize (to 1/32 s)
Calibrate magnetometers
Each detects passing vehicle
Share filtered sensor data with 5 neighbors
Each calculates estimated direction & velocity
Share results
As plane passes by,
– joins network
– upload as much of missing dataset as possible from each node when
in range
• 7.5 KB of code!
• While servicing the radio in SW every 50 us!
1/17/2002
TinyOS CSTB
11
Structural performance due to multi-directional
ground motions (Glaser & CalTech)
.
Mote
Layout
1
3
1
54
6`
1
8
1
1
1
5
29
Mote infrastructure
Comparison of Results
Wiring for traditional
structural instrumentation
+ truckload of equipment
1/17/2002
TinyOS CSTB
12
Cory Energy Monitoring/Mgmt System
•
•
•
•
50 nodes on 4th floor
5 level ad hoc net
30 sec sampling
250K samples to database over 6 weeks
1/17/2002
TinyOS CSTB
13
Energy Monitoring Network Arch
20-ton
chiller
sensor net
GW
control net
GW
GW
802-11
PC
modbus
PC
MYSQL
telegraph
scada term
UCB power
monitor net
1/17/2002
Browser
TinyOS CSTB
14
Wealth of Research Challenges
• Large numbers of highly
constrained (energy &
capability), connected devices
• New family of issues across all
the layers
service
network
system
architecture
technology
1/17/2002
TinyOS CSTB
15
prog / data model
– operating in aggregate
application
algorithm / theory
– imperfect operation and reliability
mgmt / diag / debug
– able to be casually deployed in
infrastructure (existing or in design)
Example: Networking
• Hands-on Experience with Large
Networks of Tiny Network sensors
intense constraints, freedom of abstraction
• Re-explore entire range of networking
issues
–
–
–
–
–
–
–
–
encoding, framing, error handling
media access control, transmission rate control
discovery, multihop routing
broadcast, multicast, aggregation
active network capsule (reprogramming)
localization, time synchronization
security, network-wide protection
density independent wake-up and proximity est.
• Fundamentally new aspects in each
1/17/2002
TinyOS CSTB
16
Simple Epidemic Algorithm Schema
• One (multicast) message handler
if (new mcast) then
take local action
retransmit modified request
• Examples: Network wakeup, command
propagation
– Build spanning tree
» record parent
• Naturally adapts to available connectivity
• Minimal state and protocol overhead
=> surprising complexity in this simple mechanism
1/17/2002
TinyOS CSTB
17
Network Discovery: Radio Cells
1/17/2002
TinyOS CSTB
18
Network Discovery
1/17/2002
TinyOS CSTB
19
Controlled Empirical Study
• Experimental Setup
–
–
–
–
–
–
–
13x13 grid of nodes
separation 2ft
flat open surface
Identical length antennas, pointing vertically upwards.
Fresh batteries on all nodes
Identical orientation of all nodes
The region was clean of external noise sources.
• Range of signal strength settings
• Log many runs
1/17/2002
TinyOS CSTB
20
Example “epidemic” tree formation
1/17/2002
TinyOS CSTB
21
Final Tree
1/17/2002
TinyOS CSTB
22
Power Laws ?
1000
100
100
Links
Count
1000
10
10
1
1
1
10
100
1
10
100
Cluster Size
Cluster Size (1 + # children)
• Most nodes have very small degree (ave = .92)
• Some have degree = 15% of the population
• Few large clusters account for most of the edges
1/17/2002
TinyOS CSTB
23
Open Territory => Many Children
• Example: Level 1
1/17/2002
TinyOS CSTB
24
Open Territory => Many Children
• Example: Level 2 – variation in distance
1/17/2002
TinyOS CSTB
25
Open Territory => Many Children
• Example: Level 3 – long links
1/17/2002
TinyOS CSTB
26
Understanding Connectivity
• 16 transmit power settings
• For each transmit power setting,
each node transmits 20 packets.
• Receivers log successfully
received packets.
• Nodes transmit one after the other
in a token-ring fashion
• No collisions.
• Contour plot show probability of
reception from center node
• Define “range” a radius where 75%
of enclosed nodes receive 75% of
packets
• Often good nodes at a distance
1/17/2002
TinyOS CSTB
27
• Asymmetric Link: Greater
than 65% successful
reception in one direction
and less than 25%
successful reception in the
other direction
• Symmetric Link: Greater
than 65% successful
reception in both directions
• others are “bad” links
1/17/2002
Frequency
Link symmetry in open environment
TinyOS CSTB
28
Importance of Asymmetric Links
• 10%-25% asymmetric links.
• Many asymmetric links are long links
– || asymmetric long links|| ~ || symmetric long links ||
• Why are long links useful?
– Beacon-based Routing: Long links can be used to build low-depth routing trees
– Diffusion: short routing paths
• Protocol design
– When to confirm bidirectionality?
1/17/2002
TinyOS CSTB
29
Collisions are primary factor
• Nodes out of range may have
overlapping cells
– hidden terminal effect
• Collisions => these nodes hear
neither parent and become stragglers
• As the tree propagates
– folds back on itself
– rebounds from the edge
– picking up these stragglers.
• This effect was seen in many
experiments
1/17/2002
TinyOS CSTB
30
Stragglers
• significant fraction of links point ‘backwards’
1/17/2002
TinyOS CSTB
31
Key Experience
• Really good at building tinyOS subsystems
– non-blocking, split-phase event structures
• Internalized the “state of constant change”
paradigm
– ex: maintain routing tree by constantly rebuilding it
– soft state that is always suspect
– simple one-way protocols
• Operating in the aggregate
• Simple mechanisms to accomplish large goals
– MAC, ATC
• Out of the box on networking abstractions
– Low-power listen, wake-up, statistical sampling, weighted
aggregation
• Understanding of large scale dynamics
1/17/2002
TinyOS CSTB
32
Rich set of additional challenges
•
•
•
•
Efficient and robust security primitives
Application specific virtual machines
Time & space information in every packet
Density independent wake-up, aggregation
– sensor => can use radio in ‘analog’ mode
• Resilient aggregators
• Programming support for systems of generalized state
machines
• Programming the unstructured aggregate
– SPMD, Data Parallel, Query Processing, Tuples
• Understanding how an extreme system is behaving and
what is its envelope
– adversarial simulation
• Self-configuring, self-correcting systems
1/17/2002
TinyOS CSTB
33
The “Law of Miniaturization”
Innovation
Log R
Personal Computer
Workstation
Server
Integration
Minicomputer
Mainframe
99
Time
• Each major generation is increasingly smaller, more deeply
interactive, arrives when previous is at its strength
• Vast majority of computing will be small, embedded, devices
connected to the physical world
– actually the case today, but
– not connected to us, the web, or each other
1/17/2002
TinyOS CSTB
34