Transcript wsn-networking-classic - Network and Systems Laboratory

Network and Systems Laboratory
nslab.ee.ntu.edu.tw
Wireless Sensor Networks:
Classic Protocols
Polly Huang
Department of Electrical Engineering
National Taiwan University
http://cc.ee.ntu.edu.tw/~phuang
[email protected]
Polly@NTU
Copyright © 2008
1
Network and Systems Laboratory
nslab.ee.ntu.edu.tw
Classic Protocols
 Designed for outdoor sensor networks
 Directed diffusion
 S-MAC
Polly@NTU
Copyright © 2008
2
Network and Systems Laboratory
nslab.ee.ntu.edu.tw
Directed Diffusion
Largely based on slides from
Chalermek Intanagonwiwat & Deborah
Estrin
Polly@NTU
Copyright © 2008
3
Network and Systems Laboratory
nslab.ee.ntu.edu.tw
In Short
 A data dissemination mechanism fitting into the
data-centric communication paradigm for sensor
networks
Polly@NTU
Copyright © 2008
4
Network and Systems Laboratory
nslab.ee.ntu.edu.tw
Sensor Networks
One way
Or another
Polly@NTU
Copyright © 2008
5
Network and Systems Laboratory
nslab.ee.ntu.edu.tw
Applications
Scientific: eco-physiology,
biocomplexity mapping
Infrastructure: contaminant
flow monitoring (and modeling)
www.jamesreserve.edu
Engineering: monitoring
(and modeling) structures
Polly@NTU
Copyright © 2008
6
Network and Systems Laboratory
nslab.ee.ntu.edu.tw
The Real Need
 Specialized communication in a wild wide space
 Specialized: application dependent
 Wild: little or no infrastructure
 Wide: expensive to build/use communication
infrastructure
Polly@NTU
Copyright © 2008
7
Network and Systems Laboratory
nslab.ee.ntu.edu.tw
Applications: A Longer List
 Science: monitoring temperature change on a
volcanic island
 Engineering: monitoring power use of industrial
district
 Infrastructure: monitoring passenger traffic at
MRT stations
 Military: tracking enemy migration in a dessert
 Disaster: emergency relief after Gozzila taking a
short tour of Tokyo
Polly@NTU
Copyright © 2008
8
Network and Systems Laboratory
nslab.ee.ntu.edu.tw
Common Vision
 Embed numerous distributed devices to
monitor and interact with physical world
 Exploit spatially and temporally dense, in
situation, sensing and actuation
 Network these devices so that they can
coordinate to perform higher-level tasks
 Requires robust distributed systems of
hundreds or thousands of devices
Polly@NTU
Copyright © 2008
9
Network and Systems Laboratory
nslab.ee.ntu.edu.tw
Challenges
 Tight coupling to the physical world and embedded
in unattended systems
 Different from traditional Internet, PDA, Mobility applications that
interface primarily and directly with human users
 But solutions might be applicable to the Internet, PDA, Mobility
applications as well
 Untethered, small form-factor, nodes present
stringent energy constraints
 Living with small, finite, energy source is different from traditional
fixed but reusable resources such as BW, CPU, Storage
 Communications is primary consumer of energy
in this environment
 R4 drop off dictates exploiting localized communication and inPolly@NTU
network processing whenever possible
10
Network and Systems Laboratory
nslab.ee.ntu.edu.tw
Energy the Bottleneck Resource
 Communication VS Computation Cost [Pottie
2000]
 E α R4
 10 m: 5000 ops/transmitted bit
 100 m: 50,000,000 ops/transmitted bit
 Avoid communication over long distances
 Cannot assume global knowledge, cannot preconfigure networks
 Achieve desired global behavior through localized
interactions
 Empirically adapt to observed environment
 Can leverage data processing/aggregation inside
Polly@NTU
the network
Copyright © 2008
11
Network and Systems Laboratory
nslab.ee.ntu.edu.tw
In-Network Processing
 Sensor technology is advancing steadily
 Situations detected by the sensors can be
surprisingly rich
 For example, all these at once
 Detecting a speech
 Inferring the location and identity of the speaker
 These information can be used to facilitate
efficient dissemination of the recorded speech
 Suppressing speech coming from the same speaker
 Forwarding towards the likely listeners
Polly@NTU
Copyright © 2008
12
Network and Systems Laboratory
nslab.ee.ntu.edu.tw
New Design Themes
 Long-lived systems that can be untethered and
unattended
 Energy efficient communication
 Self configuring systems that can be deployed ad
hoc
Polly@NTU
Copyright © 2008
13
Network and Systems Laboratory
nslab.ee.ntu.edu.tw
Approach
 Leverage data processing inside the network
 Exploit computation near data to reduce
communication
 Achieve desired global behavior with adaptive
localized algorithms (i.e., do not rely on global
interaction or information)
 Dynamic, messy (hard to model), environments
preclude pre-configured behavior
 Can’t afford to extract dynamic state information
needed for centralized control or even Internet-style
distributed control
Polly@NTU
Copyright © 2008
14
Network and Systems Laboratory
nslab.ee.ntu.edu.tw
Why can’t we simply adapt Internet
protocols and “end to end” architecture?
 Internet routes data using IP Addresses in Packets
and Lookup tables in routers
 Humans get data by “naming data” to a search engine
 Many levels of indirection between name and IP address
 Works well for the Internet, and for support of Person-
to-Person communication
 Embedded, energy-constrained (un-tethered,
small-form-factor), unattended systems can’t
tolerate communication overhead of indirection
Polly@NTU
Copyright © 2008
15
Network and Systems Laboratory
nslab.ee.ntu.edu.tw
Therefore, Directed Diffusion
Features
Operations
Evaluations
Polly@NTU
Copyright © 2008
16
Network and Systems Laboratory
nslab.ee.ntu.edu.tw
Directed Diffusion Paradigm
 Data-centric communication
 Supported with distributed algorithms using
localized interactions
 Application-specific in-network processing
Polly@NTU
Copyright © 2008
17
Network and Systems Laboratory
nslab.ee.ntu.edu.tw
IP Communication
 Organize system based on named nodes
 Per-node forwarding state
 Senders need to push data to the node address of sink
To Bob
To Bob
To Bob
My name is Alice.
My name is Alice.
My name is Alice.
I am a 19-yr old
I am a 19-yr old
I am a 19-yr old
I
am
Bob
I
am
Bob
I
am
Bob
I am Bob
girl…
girl…
girl…
Alice
Bob there
Polly@NTU
Chris
Bob
Bob there
Copyright © 2008
18
Network and Systems Laboratory
nslab.ee.ntu.edu.tw
Data-Centric Communication
 Organize system based on named data
 Per-data diffusion state
 Sinks need to be specific about what data they’d pull
Here’s a 19-yr old Tell me Here’s a 19-yr old
Here’s a 19-yr old Tell meTell me
Tell me
girl…
about girls
about girls
about girls girl…
girl…
about girls
Girl info goes there
Polly@NTU
Girl info goes there
Copyright © 2008
19
Network and Systems Laboratory
nslab.ee.ntu.edu.tw
Directed Diffusion Paradigm
 Data-centric communication
 Supported with distributed algorithms
using localized interactions
 Application-specific in-network processing
Polly@NTU
Copyright © 2008
20
Network and Systems Laboratory
nslab.ee.ntu.edu.tw
Localized Interaction
 Diffuse requests/interest across network
 Set up gradients to guide responses/data
 Diffuse responses/data based on the gradients
 (Pretty much the same as in the IP routing)
a 19-yr old Tell me Here’s a 19-yr old
me
Here’s a 19-yr old Tell meTell Here’s
Tell me
about girls
aboutgirl…
girls
about girls girl…
girl…
about girls
Girl info goes there
Polly@NTU
Girl info goes there
Copyright © 2008
21
Network and Systems Laboratory
nslab.ee.ntu.edu.tw
Directed Diffusion Paradigm
 Data-centric communication
 Supported with distributed algorithms using
localized interactions
 Application-specific in-network processing
Polly@NTU
Copyright © 2008
22
Network and Systems Laboratory
nslab.ee.ntu.edu.tw
Without In-Network Processing
 Data are simply passed on
Here’s a 19-yr old
Tell me
girl…
about girls
Girl info goes there
Here’s a 20-yr old
girl…
Here’s a 20-yr old
girl…
Here’s a 19-yr old Tell me Here’s a 19-yr old
Tell meTell me
girl…
about girls
about girls
about girls girl…
Here’s a 20-yr old
Tell me
girl…
about girls
Girl info goes there
Girl info goes there
Polly@NTU
Copyright © 2008
23
Network and Systems Laboratory
nslab.ee.ntu.edu.tw
With In-Network Processing
 Data are aggregated and then passed on
Here’s a 19-yr old
girl…
Girl info goes there
Here’s a 20-yr old
girl…
Here’re two 19+
yr old girls…
Girl info goes there
Application-specific
Aggregation Here!
Girl info goes there
Polly@NTU
Here’re two 19+
yr old girls…
Copyright © 2008
24
Network and Systems Laboratory
nslab.ee.ntu.edu.tw
Directed Diffusion Paradigm
 Data-centric communication
 Supported with distributed algorithms using
localized interactions
 Application-specific in-network processing
Polly@NTU
Copyright © 2008
25
Network and Systems Laboratory
nslab.ee.ntu.edu.tw
Example: Remote Surveillance
 Interrogation:
 e.g., “Give me periodic reports about animal location in region A
every t seconds”
 Interrogation is propagated to sensor nodes in region A
 Sensor nodes in region A are tasked to collect data
 Data are sent back to the users every t seconds
Polly@NTU
Copyright © 2008
26
Network and Systems Laboratory
nslab.ee.ntu.edu.tw
Basic Directed Diffusion
Setting up gradients
Source
Sink
Interest = Interrogation
Gradient = Who is interested
Polly@NTU
Copyright © 2008
27
Network and Systems Laboratory
nslab.ee.ntu.edu.tw
Basic Directed Diffusion
Sending data and Reinforcing the best path
Source
Sink
Low rate event
Polly@NTU
Reinforcement = Increased interest
Copyright © 2008
28
Network and Systems Laboratory
nslab.ee.ntu.edu.tw
Directed Diffusion and Dynamics
Source
Sink
Recovering
from node failure
Low rate event
High rate event
Polly@NTU
Copyright © 2008
Reinforcement
29
Network and Systems Laboratory
nslab.ee.ntu.edu.tw
Directed Diffusion and Dynamics
Source
Sink
Stable path
Low rate event
High rate event
Polly@NTU
Copyright © 2008
30
Network and Systems Laboratory
nslab.ee.ntu.edu.tw
Local Behavior Choices
 For propagating interests
 For data transmission
 In this example, flood
 Multi-path delivery with
 More sophisticated
selective quality along
different paths
 probabilistic forwarding
 single-path delivery, etc.
behaviors possible: e.g.
based on cached
information, GPS
•
For setting up gradients
•
•
Polly@NTU
data-rate gradients are set
up towards neighbors who
send an interest.
Others possible:
probabilistic gradients,
energy gradients, etc.
Copyright © 2008
•
For reinforcement
•
•
reinforce paths, or parts
thereof, based on observed
delays, losses, variances
etc.
other variants: inhibit
certain paths because
resource levels are low
31
Network and Systems Laboratory
nslab.ee.ntu.edu.tw
Simulation Study
 Key metric
 Average Dissipated Energy per event delivered
 indicates energy efficiency and network lifetime
 Compare diffusion to
 flooding
 centrally computed tree (omniscient multicast)
Polly@NTU
Copyright © 2008
32
Network and Systems Laboratory
nslab.ee.ntu.edu.tw
Diffusion Simulation Details






Simulator: ns-2
Network Size: 50-250 Nodes
Transmission Range: 40m
Constant Density: 1.95x10-3 nodes/m2 (9.8 nodes in radius)
MAC: Modified Contention-based MAC
Energy Model: Mimic a realistic sensor radio [Pottie 2000]
 660 mW in transmission, 395 mW in reception, and 35 mw in idle
Polly@NTU
Copyright © 2008
33
Network and Systems Laboratory
nslab.ee.ntu.edu.tw
Diffusion Simulation
 Surveillance application
 5 sources are randomly selected within a 70m x 70m






corner in the field
5 sinks are randomly selected across the field
High data rate is 2 events/sec
Low data rate is 0.02 events/sec
Event size: 64 bytes
Interest size: 36 bytes
All sources send the same location estimate for base
experiments
Polly@NTU
Copyright © 2008
34
Network and Systems Laboratory
nslab.ee.ntu.edu.tw
Average Dissipated Energy
Average Dissipated Energy
(Joules/Node/Received Event)
0.018
0.016
Flooding
0.014
0.012
0.01
0.008
Omniscient Multicast
0.006
0.004
Diffusion
0.002
0
0
50
100
150
200
250
300
Network Size
Diffusion can outperform flooding and even omniscient multicast.
WHY ?
Polly@NTU
Copyright © 2008
35
Network and Systems Laboratory
nslab.ee.ntu.edu.tw
Average Dissipated Energy
(Joules/Node/Received Event)
In-network Processing
0.025
Diffusion Without
Suppression
0.02
0.015
0.01
Diffusion With
Suppression
0.005
0
0
50
100
150
200
250
300
Network Size
Application-level suppression allows diffusion to reduce traffic
and to surpass omniscient multicast.
Polly@NTU
Copyright © 2008
36
Network and Systems Laboratory
nslab.ee.ntu.edu.tw
Average Dissipated Energy
(Joules/Node/Received Event)
Negative Reinforcement
0.012
0.01
Diffusion Without
Negative Reinforcement
0.008
0.006
0.004
Diffusion With Negative
Reinforcement
0.002
0
0
50
100
150
200
250
300
Network Size
Reducing high-rate paths in steady state is critical
Polly@NTU
Copyright © 2008
37
Network and Systems Laboratory
nslab.ee.ntu.edu.tw
Summary of Diffusion Results
 Under the investigated scenarios, diffusion
outperformed omniscient multicast and flooding
 Application-level data dissemination has the
potential to improve energy efficiency
significantly
 Duplicate suppression is only one simple example out
of many possible ways.
 Aggregation (next)
 All layers have to be carefully designed
 Not only network layer but also MAC and application
level
Polly@NTU
Copyright © 2008
38
Network and Systems Laboratory
nslab.ee.ntu.edu.tw
Standard 802.11 energy
model)
Average Dissipated Energy
(Joules/Node/Received Event)
0.14
Diffusion
0.12
Flooding
Omniscient Multicast
0.1
0.08
0.06
0.04
0.02
0
0
50
100
150
200
250
300
Network Size
Standard 802.11 is dominated by idle energy
Polly@NTU
Copyright © 2008
39
Network and Systems Laboratory
nslab.ee.ntu.edu.tw
802.11
 Contention-based protocol
 RTS-CTS-DATA-ACK
Sender
DATA
RTS
Receiver
CTS
ACK
[Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY)
Specification, IEEE Std. 802.11-1999 edition]
Polly@NTU
Copyright © 2008
40
Network and Systems Laboratory
nslab.ee.ntu.edu.tw
S-MAC
listen
sleep
listen
sleep
 Contention-based protocol
 RTS-CTS-DATA-ACK
 Listen interval
 Send packets
 Receive packets
[W. Ye et al., “An energy-efficient MAC protocol for wireless sensor
networks”, in INFOCOM 2002]
Polly@NTU
Copyright © 2008
41
Network and Systems Laboratory
nslab.ee.ntu.edu.tw
Schedule synchronization
Node 1
Node 2
listen
sleep
listen
listen
sleep
sleep
listen
sleep
 Schedules can differ
 Neighboring nodes have same schedule
Border nodes:
two schedules
Schedule 2
broadcast twice
Schedule 1
Polly@NTU
Copyright © 2008
(Borrowed from S-MAC)
42
Network and Systems Laboratory
nslab.ee.ntu.edu.tw
Scheduling in S-MAC
 Unknown neighbors
 the same schedule
1
3
Collision
Unicast
Schedule 1
Schedule 2
2
4
Broadcast
Polly@NTU
Copyright © 2008
43
Network and Systems Laboratory
nslab.ee.ntu.edu.tw
Questions?
Polly@NTU
Copyright © 2008
44
Network and Systems Laboratory
nslab.ee.ntu.edu.tw
Questions?
Polly@NTU
Copyright © 2008
45