Transcript Smart Dust and TinyOS: Hardware and Software for Network

Wireless Embedded Inter-Networking
Foundations Ubiquitous Sensor Networks
Low-Power Reliable Wireless Link Layer
David E. Culler
University of California, Berkeley
June 2008
WEI Short Course L7-link
1
Building A Low-Power Link
• Media Management Control – not MAC
Net
Link
Adaptation
Tran
Media Management Control
Remote Media
Data
Ack
Link Stats
Local Media
Neighbor Table
Sample Period
Addr
Period
Phase
Pending
RSSI
PRR
Sample Phase
Phy
June 2008
WEI Short Course L7-link
2
IEEE 802.15.4 Frame Format
June 2008
WEI Short Course L7-link
3
Elements of Robust Communication
• Application: feasible workload
– Packet rates, pattern, timing
• Network: finding and using good paths
– Topology discovery and route selection
– Route cost determination, selection
– Forwarding
• Link: Framing, Media Management Protocol
–
–
–
–
On to receive during transmission
Frame structure, error detection, acknowledgement
Avoiding contention (MAC, CCA, Hidden Terminal)
Link quality estimation
• Physical: Signal to Noise Ratio
–
–
–
–
June 2008
Device Transmission Power / Receive Sensitivity
Antenna design and orientation, obstructions, attenuation
Receive signal vs interference, noise, multipath
Modulation, channel coding
WEI Short Course L7-link
4
In a nutshell
TX
June 2008
WEI Short Course L7-link
5
Why Multihop Routing?
• Power!
– Power to transmit distance D grows as D3 or worse
– Power to route distance D grows linearly
• Bandwidth (spatial multiplexing)
– With n nodes in a single cell, each gets at most 1/n bandwidth
– Many small cells => many simultaneous transmissions.
• Reliability
– Individual links experience interference, obstacles, and
multipath effects
– Even short-range “wireless wires” require human nurturing
» IRDA, Bluetooth, WiFi, Cell Phone
– Provides spatial diversity and receiver diversity
» rather than antenna diversity
– Protocol level reliability
June 2008
WEI Short Course L7-link
6
Properties of a good Link layer
•
•
•
•
•
•
•
•
June 2008
It works!
It supports the network layer above it.
It allows low-power operation
It allows highly reliable communication
It allows for low latency
It allows bursts
It avoids contention
It is simple, robust and flexible
WEI Short Course L7-link
7
The “Idle Listening” Problem
• The power consumption of “short range” (i.e., lowpower) wireless communications devices is roughly
the same whether the radio is transmitting, receiving,
or simply ON, “listening” for potential reception
– includes IEEE 802.15.4, Zwave, Bluetooth, and the many variants
– WiFi too!
– Circuit power dominated by core, rather than large amplifiers
• Radio must be ON (listening) in order receive anything.
– Transmission is infrequent. Reception α Transmit x Density
– Listening (potentially) happens all the time
Total energy consumption dominated by idle listening
June 2008
WEI Short Course L7-link
8
MAC Caution
• The idle listen problem is often associated with Media
Access Control (MAC) protocols,
– TDMA, CSMA, …
• but MACs provide arbitration among multiple
transmitters attempting to utilize a shared medium
simultaneously.
– Reduce Contention and associated loss.
– May involve scheduling (TDMA) or transmission detection (CSMA)
• The problem here is the opposite.
– Most of the time, nothing is transmitting.
– Avoid listening when there is nothing to hear.
– Scheduling and detection are involved, but to determine when to turn
on receiver, rather than when to turn off transmission.
• You need Media Access Control, but that is not
enough
June 2008
WEI Short Course L7-link
9
What we mean by “Low Power”
• 2 AA => 1.5 amp hours (~4 watt hours)
• Cell => 1 amp hour
(3.5 watt hours)
Cell: 500 -1000 mW
WiFi: 300 - 500 mW
GPS: 50 – 100 mW
=> few hours active
=> several hours
=> couple days
WSN: 50 mW active, 20 uW passive
450 uW => one year
45 uW => ~10 years
* System design
* Leakage (~RAM)
* Nobody fools
mother nature
Ave Power = fact * Pact + fsleep * Psleep + fwaking * Pwaking
June 2008
WEI Short Course L7-link
10
Where the energy goes
• Sleep
– 7 uA for TI MSP
•
•
•
•
Sensing
Transmitting results
Management Traffic
Routing Structure Maintenance
– only parent tracking for leaf
• Listening
• Forwarding
– non-leaf
• Overhearing packets destined for others
June 2008
WEI Short Course L7-link
11
Communication Power Consumption
Sleep
~10 uA
Transmit
~20 mA x 1-5 ms
[20 - 100 uAs]
I
Time
I
Time
Listen Receive
~20 mA ~20 mA x 2-6 ms
June 2008
WEI Short Course L7-link
12
Radio
• Trade-offs:
– resilience | performance => slow wake up
– Wakeup vs interface level
– Ability to optimize vs dedicated support
* Polastre, Culler, BMAC, Sensys 2005
June 2008
WEI Short Course L7-link
13
Brief Comparison
Vendor
Model
Type
TI
CC2430
System-on-Chip
Link
http://www.ember.com/pdf/EM
http://www.ti.com/lit/gpn/cc243 http://www.xbow.com/Products http://www.meshnetics.com/zig 250/120-0082http://www.dustnetworks.com/d
0
/productdetails.aspx?sid=264 bee-products/
000H_EM250_Datasheet.pdf ocs/M2030.pdf
Micro Controller
Program Memory (KB)
SRAM (KB)
Nominal Voltage (V)
MCU Active current (mA)
MCU Active RX current (mA)
MCU Active TX current (mA)
Numer of power saving modes
8051 core integrated in
CC2430
32/64/128
8
3
9.5
26.7
26.9 (at 0 dBm)
3
Power mode 1 (uA)
Power mode 2 (uA)
Power mode 3 (uA)
Number of timers
190
0.5
0.3
4
Granularity of timers
one general 16-bit timer four general 16-bit timers four general 16-bit timers two 16-bit general timer
two general 8-bit timers two general 8-bit timers two general 8-bit timers one 16-bit sleep timer
one MAC timer
ADC
precision (bits)
# channels
DMA
Radio
Data rate (kbps)
Receiver Sensitivity (dBm)
Current at RX (mA)
Current at TX at 0dBm (mA)
Current at minimum TX (mA)
Current at maximum TX (mA)
Any link or signal indicator
Non standard mode
How high in the stack
June 2008
Crossbow
IRIS M2110CA
OEM module
MeshNetics
ZigBit ZDM-A1281
OEM module
Ember
EM250
System-on-Chip
Atmega 1281
128
8
3
8
24
25 (at 3 dBm)
1
Atmega1281
128
8
3
14
19
18 (at 0 dBm)
1
Integrated 16-bt XAP2b
MCU
128
5
1.8
8.5
35.5
35.5 (at 0 dBm)
1
8 (sleep mode)
6 (power save mode)
1 (deep sleep)
6
6
3
DustNetworks
SmartMesh-XT M2030
OEM module
Integrated
3
22
20 (at -2 dBm)
2
51 (low power
networking)
10 (sleep)
12
8
Yes
10
8
10
4
12
4
Yes
CC2430
250
-92
17.2
17.4 (at 0 dBm)
18.3 (at -25.2 dBm)
32.4 (at 0.6 dBm)
RSSI, LQI
AT86RF230
250
-101
16
AT86RF230
250
-101
16
Integrated
250
-90
10 (at -17 dBm)
17 (at 3 dBm)
RSSI, LQI
10 (at -17 dBm)
17 (at 3 dBm)
RSSI, LQI
EM250
250
-97
27
24.3 (at 0 dBm)
19.5 (at -32 dBm)
27 (at 3 dBm)
RSSI, LQI
802.15.4/XMesh
802.15.4/ZigBee
802.15.4/ZigBee
802.15.4/TSMP
802.15.4/ZigBee
WEI Short Course L7-link
14
Power States at Node Level
Active
Active
Sleep
WakeUP
Work
Sleep
WakeUP
Work
Telos: Enabling Ultra-Low Power Wireless Research, Polastre, Szewczyk, Culler, IPSN/SPOTS 2005
June 2008
WEI Short Course L7-link
15
3 Basic Solution Techniques
• Listen during scheduled time slots
–
–
–
–
Arrange a schedule of communication opportunities
Maintain coordinated clocks and schedule
Listen during specific “slots”
Many variants:
» Aloha, Token-Ring, TDMA, Beacons, Bluetooth piconets, …
» S-MAC, T-MAC, PEDAMACS, TSMP, FPS, …
• Sampled Listening
–
–
–
–
Listen for very short intervals to detect eminent transmissions
On detection, listen actively to receive
DARPA packet radio, LPL, BMAC, XMAC, …
Maintain “always on” illusion, Robust
• Listen after send (with powered infrastructure)
– Generally, device is not listening and will not receive.
– After it transmits to a receptive device, it listens for a time window
– Many variants: 802.11 AMAT, Key fobs, remote modems, …
• Many hybrid optimizations possible
June 2008
WEI Short Course L7-link
16
Communication Power – Passive Vigilance
Sleep Transmit
~10 uA ~20 mA x 1-5 ms
[20 - 100 uAs]
I
Time
I
Time
Listen Receive
~20 mA ~20 mA x 2-6 ms
• Listen just when there is something to hear …
June 2008
WEI Short Course L7-link
17
Approaches
•
•
•
•
•
•
June 2008
Powered Router / Duty cycle Leaf
Coordinator / Beacon
Network schedule
Preamble Sampling
Slotted Preamble Sampling
Quasi-scheduled
WEI Short Course L7-link
18
Powered Router + Leaf
• Algorithm
– Leaf nodes never forward, turn off when ever they like
» Typically a minimum frequency
– Forwarding nodes never turn off
– Special case transmit to leaf
» Buffer and wait till hear
• Usage
– Ember, Sensicast, Millennial, Figure 8
» All started with fancier schemes and gave up
June 2008
WEI Short Course L7-link
19
Scheduled Listen
Transmit during
Listen interval
P
Tschedule
Time
P
Tperiod
Time
Listen intervals
no transmit
Synchronization
skew
• Pave  Psleep + Plisten Tlisten / Tschedule + Pxmit  Txmit / Txmit+ Pclock-sync-ave + Pdiscover-ave
interval
• Communication to maintain synch. sets lower bound.
• Full power listen to discover and join schedule.
June 2008
WEI Short Course L7-link
20
Schedule Mechanisms
• Compute schedule off-line and distribute it to the nodes
– Requires some unscheduled communication mechanism to perform survey
of who-communicates-with-whom and who-interferes-with-whom, collect
results, and distributed schedule.
– Easy for star and clique.
– Changing conditions, additions and deletions are problematic
• Define set of slots, advertise, resolve
– Relatively easy for star, clique, or ring.
– Complicated for general mesh. Essentially constraint resolution.
– Typically, coordinator schedules for one-hop neighbors and coordinators
(cluster heads) stay powered.
» As network grows, leaf-fanout trends to 1
– Embedded a “scheduling tree”
• Essentially the traffic-light coordination problem, but the roads
and flows are changing.
June 2008
WEI Short Course L7-link
21
Communication Scheduling: TDMA
• Time Division Media Access
– Each node has a schedule of awake times
– Typically used in star around coordinator
» Bluetooth, ZIGBEE
» Coordinator hands out slots
– Far more difficult with multihop (mesh) networks
– Further complicated by network dynamics
» Noise, overhearing, interference
June 2008
WEI Short Course L7-link
22
Node 2
listen
sleep
listen
sleep
sync
• T-MAC
sleep
listen
sync
– Hard to maintain set of schedules
Node 1
sync
• Carrier Sense Media Access
• Synchronized protocol with
periodic listen periods
• Integrates higher layer
functionality into link protocol
sync
S-MAC
listen
sleep
[van Dam and Langendoen, Sensys 2003]
– Reduces power consumption by
returning to sleep if no traffic is
detected at the beginning of a
listen period
Schedule 1
Schedule 2
Wei Ye, USC/ISI
Ye, Heidemann, and Estrin, INFOCOM 2002
June 2008
WEI Short Course L7-link
23
Flexible Power Scheduling
•
TDMA-like scheduling of listening slots
– Distributed allocation
– CSMA with LPL within a slot
•
Node allocates
– listen slots for each child
– Transmission slots to parent
– Hailing slot to hear joins
•
To join listen for full cycle
– Pick parent and announce self
– Get transmission slot
•
CSMA to manage media
– Allows slot sharing
– Little contention
•
•
Reduces loss & overhearing
Connectivity changes cause mgmt traffic
Holte, PhD 2004, IPSN 2004
June 2008
WEI Short Course L7-link
24
IEEE 802.15.4 SuperFrame
June 2008
WEI Short Course L7-link
25
Coordinator / Beacon
•
Algorithm
– Coordinator broadcasts periodic beacon assigning speaking/receiving slot for each node
– Node listens for full beacon period to learn slot
– Listens / Recv / Transmit in each slot to maintain synch and communicate
•
Usage
– 802.15.4 provision, baked deeply into Zigbee
» No Zigbee provider uses it, just powered routers + leaf
•
Strengths
– Localized timesynch, not whole network
•
Weaknesses
– Fragile: can’t comm till find coordinator and bind. What happens if none around. Lose
coordinator temporarily.
– Adaptation
» Scan when joining network.
» When to reclaim slots
– Utilization
» Only fraction of channel available, even when only one node needs to burst
– Efficiency
» Need to participate in beacon coordination even if nothing to send or receive
– Routing
» Within cell easy, need to coordinate across multiple coordinators
•
Power bounds
– Beacons + time synch
June 2008
WEI Short Course L7-link
26
TSMP
• Connectivity Survey of
entire network on every
channel.
• Offline computation of a
communication
opportunity schedule.
June 2008
WEI Short Course L7-link
27
Scheduled Listen Tradeoffs
+ Transmission scheduling that reduces contention,
reduces loss, reduces retransmission, saves energy.
– regardless of whether reception is scheduled.
+ Transmission and Reception costs predictable in
steady state (synched and stable)
-- Listening Cost: Plisten Tlisten / Tperiod
– Pay the cost even when nothing is received.
– Tlisten must be greater than the maximum synchronization variation.
• Delay
– In the worst case, delay is Tcycle per hop. Expected Tcycle/2. Aligning
slots for one direction of flow increases delay for others.
– Jitter in latency is small,
» except that loss requires retransmission and whenever fanin
exceeds reserved slots for next hop
- Bandwidth
- Limited as 1/Tschedule even if rest is unused
June 2008
WEI Short Course L7-link
28
Scheduled Listen (Cont)
-- Time synchronization required
– Frequency of time-synch protocol communication increases
with required accuracy and with variations in clocks.
– If you lose synch, it is hard to regain it because you don’t
know when the node is listening. You must transmit
continuously or wait for it to go into a watchdog full listen.
– Reducing listening cost (Tlisten) requires tightening synch
accuracy.
– Having paid the cost, timestamping data is easy, but generally
overkill.
– Nodes cannot “go silent” as they will lose synch.
-- Discovery/Join cost
– generally requires long period of full listen or long period of
announce transmission.
– The less the nodes are listening, the more costly the
discovery.
• Fragile (with scale)
• Rigid (with scale and with variation)
June 2008
WEI Short Course L7-link
29
Sampled Listen
P
Time
Tperiod
P
Time
•
•
•
•
•
•
Relatively frequent, Very short “Listen Samples”
Transmit (infrequent) increased to cover Tperiod
Pave  Psleep+ PlistenTsample / Tperiod + PxmitTperiod / Txmit-interval
No time synchronization required.
Rapid join and at low power.
Scheduled sleep, wake times, time synch, etc. built on top for
further reductions in power
June 2008
Versatile Low Power Media Access for Wireless Sensor Networks, Polastre and Culler, Sensys04
WEI Short Course L7-link
30
Sampling Mechanisms
Typical Frame Structure
Preamble Start Header
Data Payload
Trailer
Goal: Shift continuous listen burden to infrequent transmit
• Preamble Sampling (DARPA 1984) and Low-power Listen (UCB, 99)
– TX: extend preamble to listen period.
– RX: samples, hears preamble, Receives till START as usual.
– Requires low level link access (e.g., RFM1000)
• Repeated Transmit
– Transmit packet multiple times to fill listen period.
– RX: CCA to sample, ON to receive packet
• Wake-up Packets
– Transmit (small) wake up packets to cover sample, then packet
June 2008
WEI Short Course L7-link
31
Low Power Listening
• Extremely short CCA (500 us)
• Use short ‘chirp’ messages as preamble
– Addressing  minimizes overhearing cost
– Data time  receive cost independent of sample period
• Communicate with anyone anytime
– Always-on illusion  manageability, IP friendly
June 2008
WEI Short Course L7-link
32
Optimal Listen Sampling
0.14
0.12
Comm. Cost
0.1
TX cost
0.08
RX cost
Listen cost
Total
0.06
L opt
0.04
0.02
0
0
20
40
60
80
100
120
140
160
180
Listen Interval (packet times)
June 2008
WEI Short Course L7-link
33
Sampled Listen Trade-offs
+ Responsive
– Unscheduled communication at Tperiod per hop, not Tschedule
+ Adaptive
– Joins, leaves, changes in connectivity don’t require rescheduling
– Rapid discovery
+ No synchronization cost
– Can run time synch on top to further reduce costs
– Don’t depend on it for correctness
+ Resilient
– When forced to listen, do so at low power
+ Flexible
– Tperiod configurable to workload, even on per-node basis
– Permits a wide array of further optimizations to eliminate reduce wakeup costs and
listening samples
• Bandwidth
+ Node can burst at full link bandwidth, not 1/Tschedule
- unoptimized bandwidth limited by 1/ Tperiod
- Transmit cost increases Tperiod
– So does receive cost if you do it naively
June 2008
WEI Short Course L7-link
34
Link Layer – Optimizations
• Scheduling
– Remove preamble cost for a subset of neighbors
– Reduce overhearing
• Packet pending
– Efficiently transmit packet trains
• Use 802.15.4 data frame as acknowledgement
– Addressing, secure, synchronization information
Basic LPL
June 2008
Phase-Synchronized LPL
WEI Short Course L7-link
Packet Train
35
Link Layer – Abstraction
• Media Management Control
– Local Media: Sample Period + Phase
– Remote Media: Sample Period + Phase + Pending
• Neighbor Connectivity Statistics
– Signal Quality (RSSI)
– Success Rates (windowed average)
Data
Ack
Media Management Control
Link Stats
Sample Period
Neighbor Table
Addr
Period
Phase
Pending
Local Media
RSSI
Success
Sample Phase
Link
Remote Media
Phy
June 2008
WEI Short Course L7-link
36
Communication Power Model
•
•
•
•
•
Sleep Current
= Is uA
RX packet (n)
= R0 + n* Rbyte uAs
RX wake and receive = Rw + RXpacket(n)
RX overhear and reject: Rrjt
TX packet (n,c) = T0 + n* Tbyte + W* Iw uAs
– Radio Wakeup, Clear Channel Assessment, Transmit
• Listen
June 2008
= Lw / W uA
WEI Short Course L7-link
37
TX ack
SPI transfer
Receive 17 - Header
RX bytes
Warm Up - AGC
25.000
Start Oscillator
Bottom Up Power Modeling
Receive 127
25.000
20.000
15.000
15.000
mA
mA
20.000
10.000
10.000
5.000
5.000
0.000
3.00E-02
3.20E-02
3.40E-02
3.60E-02
3.80E-02
4.00E-02
4.20E-02
4.40E-02
Receive packet with 15.4 header (17B)
- one EUID64, one Short16
TelosB configuration:
TI MSP430-F1611 + TI CC2420
June 2008
0.000
2.00E-02
2.20E-02
2.40E-02
2.60E-02
2.80E-02
3.00E-02
3.20E-02
3.40E-02
Receive max 15.4 packet (127B)
Linear model:
WEI Short Course L7-link
38
Energy Cost of the Primitives
Channel Sample
Overhear
Receive
Receive
(26 bytes)
(127 bytes)
Transmit
Transmit
Preamble + Transmit
Preamble + Transmit
(26 bytes)
(127 bytes)
(64 ms)
(128 ms)
June 2008
WEI Short Course L7-link
39
Link-Level Power Model
June 2008
WEI Short Course L7-link
40
Empirical Power Model
June 2008
WEI Short Course L7-link
41
MAC => Media Management
• Sampled Listening
– Darpa Packet Radio, LPL, BMAC, XMAC, …
– Maintain Always-On Illusion, robust
• Scheduled Communication
– S-MAC, T-MAC, PEDAMACS, TSMP, FPS, …
– Low power when in sync, but fragile
• Hybrid Optimization
– WiseMAC, SCP-MAC, …
– Streaming – one wake up, many packets
– Optimistic scheduling
• Learn when likely to listen
• Use ack feedback to detect and repair
=> 802.15.4e ???
June 2008
WEI Short Course L7-link
42
Open Issues for Research and Industry
• Sampled vs Synchronized
– Is time synchronization required for the network to work at all?
– Or is it an optimization
• Multi-channel usage
– Frequency agility
– Increased diversity
– Impact on prediction, link assessment
• Distributed vs. Centralized
– How much is determined locally vs network wide
• Fundamental lower bounds
– energy is required to maintain structure
– Where is the optimal point
• Visibility
– How does network level inform link of relevance
– How does link level inform network of status
June 2008
WEI Short Course L7-link
43
Robustness and Reliability
June 2008
WEI Short Course L7-link
44
Connectivity
• Much of the CS work on network protocols
– Routing, cluster head formation, topology formation, …
assumes a unit disk model
– If Distance < R, Connectivity = 1, otherwise 0
• EM models based on fading, signal-to-noise ratio
(SNR), modulation, and coding.
– PRR (packet receive rate) for SNR (g), frame size (f)…
For Mica2 with FSK CC1000
– Nakagami and Rayleigh Fading
June 2008
WEI Short Course L7-link
45
Real World Example – open surface
• 2003 study of 100-200
first generation motes
placed in regular grid
in open tennis court.
• RFM 916 MHz ASK RF
transceivers with
simple whip antenna.
• Variation in Packet
Receive Rate (PRR)
from each transmitter.
Taming the Challenges of Reliable Multihop Routing
in Sensor Networks, Alec Woo and David Culler, ACM
SenSys Nov. 2003.
D. Ganesan, B. Krishnamachari, A. Woo, D. Culler, D. Estrin, and S.
Wicker, "An Empirical Study of Epidemic Algorithms in Large Scale
Multihop ," Intel Research, IRB-TR-02-003, Mar. 14, 2002
June 2008
WEI Short Course L7-link
46
Analytical Models with Mulipath
Path loss with distance d
Bit error rate
a
19.2 kbps
30 kHz
PRR
Marco Zuniga, Bhaskar Krishnamachari, "Analyzing the Transitional Region in Low
Power Wireless Links", IEEE SECON 2004.
June 2008
WEI Short Course L7-link
47
PRR vs Distance in practice
June 2008
WEI Short Course L7-link
48
Example: TI CC2420
• IEEE 802.15.4 compliant
• 2400 – 2483.5 MHz RF tranceiver
• O-QPSK Direct Sequence Spread Spectrum (DSSS)
– 250 kpbs data rate, 2 Mchips/s
•
0 dBm (1 mW) transmit power
• -95 dBm receive sensitivity
• 30/45 dB adjacent channel rejection
• 53/54 dB alternate channel rejection
• PIFA PCB antenna
http://focus.ti.com/lit/ds/symlink/cc2420.pdf
http://focus.ti.com/lit/ug/swru043/swru043.pdf
June 2008
WEI Short Course L7-link
49
Channel Modulation
FSK
• ASK - Amplitude Shift Keying
– Rene, Mica1 – RFM1000
• FSK - Frequency Shift Keying
– Mica2 – CC1000
• O-PSK - Orthogonal
Quadrature phase-shift keying
– Telos, TelosB, MicaZ - 802.15.4
June 2008
WEI Short Course L7-link
50
O-QPSK, RSSI, CCI/LQI
• Chip Correlation Indicator
June 2008
WEI Short Course L7-link
51
Real World Example
•
•
•
•
•
June 2008
Heavy metal environment
Operating machinery
Changing environment
Electronic Equipment
…
WEI Short Course L7-link
52
RSSI - Stationary
June 2008
WEI Short Course L7-link
53
RSSI - Driving
June 2008
WEI Short Course L7-link
54
Industrial Setting (Sexton)
6
1
5
2
4
3
IEEE 802.5.4 Channels
June 2008
WEI Short Course L7-link
55
Channel Fading
• Multipath effects
– Varies by position
– Varies by frequency
– Varies over time
• Overcome with diversity
– Time diversity
» Retransmission
– Spatial Diversity
» Multiple antennas
– Path diversity
» Alternative receivers
– Frequency diversity
» Spreading, Multiple channels
Radio Channel Quality in Industrustrial Wireless
Environments, Dan Sexton, et. al SICON'05
June 2008
WEI Short Course L7-link
56
WIFI Relationship
June 2008
WEI Short Course L7-link
57
Variations over time
•Understanding the causes of packet delivery success and failure in dense wireless sensor
networks, Kannan Srinivasan, Prabal Dutta, Arsalan Tavakoli, and Philip Levis
June 2008
WEI Short Course L7-link
58
Received Signal Strength ?
June 2008
WEI Short Course L7-link
59
Noise
• Periodic WiFi beacon
June 2008
WEI Short Course L7-link
60
802.11 / 802.15.4 Interference
June 2008
WEI Short Course L7-link
61
Classic Media Access Control
• CSMA wireless MAC
–
–
–
–
–
–
–
MACA, MACAW, IEEE 802.11
Listen (CCA - clear channel assessment)
If channel busy, back off (exponentially) and retry
Send RTS – request to send
Wait for destination to respond with CTS (clear to send)
On CTS, send data packet
and on overhearing CTS to another backoff
• TDMA
– Divide time into periodic slots
– Assign slots for individual nodes to transmit
A
B
C
Hidden Terminal
June 2008
B
A
C
D
Exposed Terminal
WEI Short Course L7-link
62
Lesson 1: Listen
• MACs deal with mitigating high contention
– In low duty cycle networks, contention is low regardless
– Can occur due to highly correlated behavior
» Example: all node sample periodically
» Separate sample from report, shift phase
• WSN packets are not the only thing on the air
• CCA essential for determining noise also
– Don’t transmit over a noisy (or busy) channel
– Required even with TDMA techniques
• Low-Power Wireless Packets are small
– IEEE 802.15.4 limit 127 bytes
– PRR drops rapidly with frame size!
– Handshake is extremely energy expensive
• In a mesh, hidden terminals and exposed
terminals are EVERYWHERE
June 2008
WEI Short Course L7-link
63
Lesson 2: Link Level Retransmission
• There will be packet loss, even on good links
• PRR(h hops) = PRRh
• Link-level acknowledgements are essential.
– Provides ability to estimate the quality of the link!
Receive Ack
CCA
25
20
mA
15
10
5
0
-15
-10
-5
0
5
10
15
ms
June 2008
WEI Short Course L7-link
64
Lesson 3 – Asymmetric Links
• Asymmetric Links are common
– Non-isotropic antenna, propagation, multipath
– Variations in transmit power or receive sensitivity among
nodes
– Variations in noise level at receiver and transmitter
• Cannot assume the reverse link is good
– Verify it!
– Continuously
June 2008
WEI Short Course L7-link
65
Lesson 4 – Variation in Time
•
•
•
•
Link quality varies in time due to many factors
Changing physical environment.
Changing RF noise
Changing traffic from other nodes
– Essentially additional noise, but right in the channel
• Cannot expect to determine connectivity in
advance and just use it.
– Zigbee route determination?
– TSMP connectivity “survey”?
June 2008
WEI Short Course L7-link
66
Lesson 5: Reception => Link
• Reception of a packet from a node does not imply
the link is good.
• Will infrequently receive good packets even on a
bad link.
• Many nodes far away => will frequently receive a
packet from one of them.
• Neighbor table cannot contain an entry for
everyone that a node has heard from!
• Must track only a small important subset?
June 2008
WEI Short Course L7-link
67
Lesson 6: No Reception => No Link
• Capture Effect
• A node will receive packets with low signal
strength (at least if the noise is low)
• If a strong packet appears at the receiver while it is
in the middle of processing a weak packet
– Both will be lost
• And collision => loss
– If a weak packet arrives while receiving a strong packet, the
strong packet will be received if the weak does not exceed the
SNR threshold.
Exploiting the Capture Effect for Collision Detection and Recovery
Whitehouse, K.; Woo, A.; Jiang, F.; Polastre, J.; Culler, D.
Embedded Networked Sensors, 2005. EmNetS-II. The Second IEEE Workshop on
Volume , Issue , 30-31 May 2005 Page(s): 45 - 52
June 2008
WEI Short Course L7-link
68
Lesson 7: Determining Link Quality
• RSSI, LQI, and Packet Sequence numbers tell
receiver about the inbound link.
• Need to reply to the sender for it to know if that
is a good link.
• The 2-way exchange provides way to filter out
asymmetric links.
• Link ACKs inform sender about outbound link.
• The more channels you track the less you know
about each
• Need a simple metric for network layer to use
June 2008
WEI Short Course L7-link
69
Summary
• Many of the best protocols are opportunistic
– Use whatever connectivity occurs
• Topology determination and route selection is a
constant and gentle process
– Passive monitoring wherever possible
– Use every piece of information available to track quality
• Concentrate link estimation on the few important
candidates.
• Additional network density helps reliability
– If the media management is done right
June 2008
WEI Short Course L7-link
70
June 2008
WEI Short Course L7-link
71
Power-aware Routing
• Cost-based Routing
– Minimize number of hops
– Minimize loss rate along the path
– Perform local retransmissions, minimize number along path
• Energy balance
– Cost-function prefers nodes with larger energy resources
• Utilize redundancy
– Nodes near the sink route more traffic, hence use more energy
– Give them bigger batteries or provide more of them and spread the load
– Randomize routes
• Utilize heterogeneity
– Route through nodes with abundant power sources
June 2008
WEI Short Course L7-link
72
Example Mesh Routing Implementations
•
TinyOS
– MintRoute (2003) – cost based collection routing over Low Power Listening on CC1000
– MultiHop LQI (2005) – LQI cost-based collection on 15.4
– Drain / Drip – (2006)
•
ZIGBEE
–
–
–
–
–
•
Star, Tree, and Mesh defined
Tree generally rejects
Only mesh profiles appear to be utilized
AODV (build tree from any node with full bcast)
No power management defined
Ember
– Proprietary extensions / simplifications of zigbee
•
Millennial
– Powered backbone
•
Crossbow xmesh / TrueMesh
– extends TinyOS mint-route with local slots
– Preamble Chirps on slot edge, listens only on edges
•
Dust SmartMesh
–
–
–
–
•
Survey all pairs connectivity
Compute off-line schedule of Source->Dest opportunities
Maintain global time slots with single pair per slot
Periodic collection to single root at 1 packet per minute
Arch Rock
– 15.4 packet-based Sampled Listening
– IP routing over 6LoWPAN, triply-redundant mesh
June 2008
WEI Short Course L7-link
73
In-network Processing
• Best way to reduce communication cost is to not
communicate
• Compute at the sensor
– Only communicate important events
• Compute over localized regions of the network
– Distributed detection
– Validation
June 2008
WEI Short Course L7-link
74
Previous Work on Duty-Cycling
– Dual-channel MAC: PAMAS [SR98]
• Synchronization of PAMAS:
– Each node sends and receives RTS/CTS messages over
control channel, which is always turned on.
• Power Saving of PAMAS:
– Data channel is turned on when activity is expected.
• Pros: Easy to implement.
• Cons: Requires dual-channel, control channel still
consumes power
active
Node 1
Data Channel
Control Channel
(always on)
Node 2
Data Channel
sleep
RTS
Node 3
Data Channel
Control Channel
sleep
CTS
listen
Control Channel
(always on)
June 2008
active
WEI Short
L7-link
(always Course
on)
sleep
RTS
CTS
listen
sleep
sleep
75
Previous Work on Duty-Cycling
– Virtual Clustering (S-MAC, T-MAC)
• Power Saving of S-MAC:
– Each node is turned on only for its time slot.
• Synchronization of S-MAC:
–
–
–
–
Each node sets up its own schedule by
(1) Sending its SYNC packet when it hasn’t found neighbor.
(2) Following schedule of a neighbor whose schedule is earlier.
Channel contention is addressed by RTS/CTS.
• Pros: Algorithm can be applied to any platform.
• Cons: Overhead of RTS/CTS, Atmel specific implementation.
Synchronization of S-MAC
Td1
Td1
active
active
sleep
Node 1
sleep
Follow the schedule of Node 1
SYNC
packet
Td1
active
active
sleep
sleep
Node 2
Td2
June 2008
WEI
Rebroadcast the schedule of
Node 2 after
a randomL7-link
delay
Short
Course
Td2
76
Previous Work on Duty-Cycling
– Low-power listening (B-MAC)
• Power Saving for B-MAC:
– Each node sleeps after listen with no channel activity.
• Synchronization for B-MAC:
– Preamble from sender node is long enough to span Tperiod.
• Pros: No separate synchronization step is needed.
• Cons: Long preamble is not supported on Trio node.
Tperiod
time
125 ms
Sender
Receiver
Receiver
125 ms
preamble
125 ms
125 ms
data
data
data
Source: XMesh Routing Layer, Martin Turon et al. TinyOS Tech Exchange 2005.
June 2008
WEI Short Course L7-link
77