Transcript Geographic Routing Architecture for Sensor Networks

Embedded Systems
and Sensor Networks
Pete Broadwell
<[email protected]>
Joe Polastre
<[email protected]>
Introduction
Network-enabled embedded
systems currently are
approaching widespread use.
We make a case for the
“access network” approach to
converging such networks with
larger networks, and present
wireless sensor networks as a
case study.
Talk Outline
• Introduction to embedded systems
– Design considerations
– Networking options
• Strategies for network convergence
– Access networks
– Service discovery
• Sensor networks: a case study
– Operating environment
– Networking implementation
– Supported applications
Embedded Systems
Pete Broadwell
<[email protected]>
What is an embedded system?
• Hardware and software components
• Part of a larger system
• Operates without human intervention
Tiny Webserver
• Example:
– Single-board microcomputer
– Software stored in ROM
– Runs special-purpose app until turned off
Types of embedded systems
• Sensors*
– Collect data
– Passive interaction with environment
• Actuators*
– Control machines
– May introduce changes into environment
• Beacons*
– No sensing or actuation
– Can alert other sensors to changes in environment
* All can benefit from being networked!
Why the interest in embedded
systems?
• Embedded systems are becoming ubiquitous
– Moore’s Law: more computing power in smaller devices
• Example: laboratory temperature alarm
Embedded devices:
Traditional electronics:
temperature
sensor
+5V
controlling
ROM
comparator
thermistor
comm. bus
interface
+5V
speaker
comm. bus
environment
monitor
Why network them?
• Some embedded systems have no use for
network connectivity
– Example: my car’s ABS (or do they?)
• Others benefit from network access
– Example: refrigerator orders milk when it’s low
• It’s easy: ubiquitous large network access
– Infrared
– Wireless
– Cable, telephone, power lines…
Motivations for networked
embedded systems
“Smart spaces”
Stanford iRoom
Remote actuation
Remote surgery
Access to sensor network data (more later)
Embedded systems design
issues
• Power consumption
• OS/programming API
– Real-time? Event-driven?
• Communication
– Medium? Protocol?
• Localization
• Monitoring
• Security
Communications decisions
• Medium choices:
– Infrared
– Wireless
– Fiber
• Protocol choices:
– IrDA
– Bluetooth
– Ultra Wideband
(eventually)
– PicoNet
• Messaging format
choices:
– Active messages
(asynchronous
– RPC (synchronous)
– Proprietary
• Network setup
choices:
– Ad-hoc or static
– TCP/IP compatibility
– Internet connectivity
OS/Programming model
• Example: Windows XP Embedded
– Componentized version of consumer OS
– Device-specific “enabling features”
XP Embedded
configuration screen
• Embedded Linux is similar
Computation in the network
• Embedded systems push functionality
into the network
– Leaving data processing/decision making
to supervisor is slow and wasteful
• One solution: Active Messages
– Facilitate asynchronous intra-network
computation
– May support distributed queries of sensors
(treating sensor networks as a DB)
Relation to network convergence
• Embedded systems employ an
extremely diverse range of
programming models and
communication methods.
• Common thread: connectivity exists
among hosts, as well as between hosts
and a central supervisor entity with
greater computing resources.
A case for the Access Network
approach to convergence
Treat networks of embedded systems as
“access networks”
Internet
Unresolved issue: service
discovery
• How do hosts on a large network discover
services offered by networked embedded
systems?
• Service discovery protocols
–
–
–
–
–
–
Sun’s Jini
Microsoft’s UPnP
Salutation
Bluetooth*
PicoNet*
IrDA*
* Per-connection only
Service Discovery Protocols:
Electronic eavesdropping example
Nosy Dan’s
eavesdropping
device
Base
Station
1. “Register service:
Mote 1
Mote 1 listening in Room 1”
Nosy Dan’s
competitor
Base
Station
6.3.
“Establish
“Requestconnection
service:
With
Mote 1”
Listening
in Room 1”
Nosy Dan
Room 1
Room 2
4. “Lookup service:
5. “Reply: Mote 1
Listening in Room
1” in Room 1”
Listening
2. “Register service:
Mote 1 listening in Room 1”
LAN
Lookup
server
• An Internet-scale solution to this problem has yet to be developed.
Sensor Networks
Joe Polastre
<[email protected]>
Emerging Extremes and
Convergence
• Planetary Services
• Open Internet Services
• Internet Services
• Servers
• Workstations
• Personal Computers
• PDAs / HPCs/ smartphones
• Microscopic sensor/embedded
networks
From David Culler’s Invited Lecture at USC, February 28, 2001
Network Convergence
Sensor Networks
• Concurrency intensive
–
•
•
•
•
Self-organized and reactive control
provides real time services via
different network mechanisms
•
Different elements of the converged
network have varied loads
•
•
May or may not have UI
Network is adaptive
population usage & physical stimuli
robustness
Hands-off (no UI)
Dynamic configuration, discovery
–
–
data streams and real-time events,
not command-response
Huge variation in load
–
–
Converged Network
• Concurrency intensive
–
service discovery major part of
huge, all-encompassing network
Complimentary roles
– tiny semi-autonomous devices empowered by
infrastructure
– infrastructure services connected to the real world
Sensor Networks
• Existing Research Platforms
TinyOS/Mica
SmartDust
WINS
NG 2.0
– Berkeley
Platform
– Sensoria
–
(Pister)
Berkeley
2001 (Culler)
330µm
TX Drivers
Power input
ambient light
sensor
Photodiode
ADC
Power
Oscillator
13 state
Sensor input
0-100kbps
CCR or diode
FSM
controller
1mm
Optical Receiver
Sensor Integration
The TinyOS Platform Application Model
Environment
monitoring
IP
DB
SerialForwarder
Traditional
network
RF
Remote
control
console for
motes
IP
SerialForwarder
SerialForwarder
IP
Inventory
tracking
Services… What about Sensors?
• Variety of sensors & actuators
available
– All-in-one sensor board includes light,
temperature, microphone, sounder,
accelerometer, and magnetometer
– Environmental monitoring sensor
board includes light, calibrated
temperature, thermopile, humidity,
barometric pressure
– Remote control sensor board
includes external pin connections to
control physical devices including RC
vehicles
Multi-Network Data Acquisition
--- Demo ---
• Two motes are sensing light and
reporting the results back to a base
station
• Base station allows IP clients to connect
and read sensor data or control motes
from anywhere on Internet
Robust Communication
Geographic Routing: QoS multi-hop data acquisition
• GeoCast (Navas and Imielinski 1996)
– Architecture for addressing and routing in wide are
networks
• GeoMote (Pete, Joe, Rachel 2001)
– Sensor network implementation of GeoCast: lower
power, adhoc
– Primary Services:
• Geographic Multicast
• Nearest Neighbor Service Discovery
• Geographic Network Reprogramming and
Reconfiguration
• Low Power Pursuer/Evader Games
Geographic Routing Architecture
Client
Process
Event
Router
Gateway
Host
Event
Client
Process
Direct
Message
Low-Power Pursuer Evader
Geographic vs. Internet Architecture
• Geographic (sensor)
– Routers may never
talk to Hosts and
vice versa
– Gateways are
entry/exit points but
have no routing info
– Broadcast medium
dependant on
distance from source
• Internet
– Functions of the
gateway and router
are typically merged
– Gateways perform
routing functions and
are entry/exit points
– Broadcast medium
dependant on
physical network
Directed Diffusion
• Data-Centric
• Register “interests” in the network
– < Attribute, Value > pairs
• Nodes diffuse the interest towards producers
via a sequence of local interactions
• Gradients determine path of data
• Achieve efficient distribution of data through
reinforcement and negative reinforcement
Illustrating Directed Diffusion
Setting up gradients
Sending data
Source
Source
Sink
Sink
Reinforcing
stable path
Source
Source
Sink
Sink
Recovering
from node failure
Illustration courtesy of Deborah Estrin, UCLA
Distributed Algorithms
• Completely new area to investigate
robust distributed algorithms on sensor
networks
– Example: New Distributed Algorithm for
Connected Dominating Sets in Wireless
Ad-Hoc Networks ---Alzoubi et. al.
– Connected Dominating Set Typically Used
as a backbone for wireless networks—
useful to compose the backbone
dynamically
Connected Dominating Set
1) Set the rank of each node
0
2) Lowest Rank Among Neighbors
DOMINATOR
Start Dominator
INVITE
JOIN
3) If all lower ranking
1
neighbors dominee
DOMINEE
INVITE
JOIN
then you are dominator
2
2
4) Invite black nodes
DOMINATOR
to participate in
3
dominating tree
1
DOMINEE
JOIN
INVITE
2
2
DOMINATOR
3
3
DOMINEE
4
4
This is all occurring over RF broadcasts!
3
Sensor Network as a Database
Two Projects:
• Intel Research w/ UC Berkeley: TAG
– Tiny Aggregate Queries in Ad-hoc Sensor
Networks
– Sam Madden, Wei Hong, Joe Hellerstein, Mike
Franklin, David Culler
• Cornell University: Cougar
– Towards Sensor Database Systems
– Querying the Physical World
– Philippe Bonnet, Johannes Gehrke, Praveen
Seshdri
Databases vs. Sensor Networks
• Database
–
–
–
–
–
–
Single Physical Device
Static data
Centralized
Failure is not an option
Plentiful resources
Administrated
• Sensor Network
–
–
–
–
–
–
–
–
–
Numerous Devices
Streaming data
Large number of nodes
Multi-hop network
No global knowledge
about the network
Frequent node failure
Energy is the scarce
Resource, limited
memory
Autonomous
Want “to combine and aggregate data streaming from
sensors.” Sounds like a database…
Fjords
Use Fjords to handle lack of reliabilty and
streaming push data
• Allows arbitrary combinations of push/pull amongst
devices
– Operators assume non-blocking queue interface between
each other.
– Queues implement push vs. pull
• Pull from A to B : Suspend A, schedule B until it produces data.
A cannot go forward until B produces data.
• Push from B to A : A polls, scheduler thread invokes B until it
produces data. A can process other inputs while waiting for B.
– Supports parallelism between operators
Fjording the Stream
Querying Streaming Sensor Data

P
u
s
h

Pull
Social Networks / Active Badges
• Sensor networks can record social
interactions by detecting proximity
• Not just a convergence of sensors and
Internet, but other “networks” too!
• First attempt to monitor social network at
UCB NEST Retreat, January 2002
• UCLA: iBadge Prototype
– Investigate behavior of children in a
Kindergarten
Social Network Visualization
Wagner
Culler
Social Network Results
Conclusions
and
Future Directions
Future Directions
• Everyone disagrees over whether sensors should
directly communicate via IP
–
–
–
–
Sensors: Routing is data-centric and energy-aware
Internet: Routing is bandwidth and latency-centric
If so, we need IPv6 NOW!
Do sensors need TCP/IP overhead since the transport
medium is unreliable?
• Networked Sensors may choose to elect some nodes
to participate in networking and others to acquire
data
– Partitions the network into two sets, end-hosts and
infrastructure, like current Internet
Conclusions
• Research opportunities in sensor networks is infinite
(or nearly infinite)
–
–
–
–
Algorithms
Network Architecture / Routing
Data Acquisition / Aggregation
Network Convergence of Devices
• Computing will continue to move within the network
• Sensors and Embedded Systems will enabled
ubiquitous computing efforts
• Connecting Embedded Devices to Traditional
Networks can be very powerful:
– Environmental Monitoring
– Autonomous Actuation (eg: “Smart” home)
References
• See
www.cs.berkeley.edu/~polastre/cs294-2002sp
• Links to relevant papers and more
information on Embedded and Sensor
Networks
Embedded Systems
and
Sensor Networks