Transcript Document

On Accurate Measurement of Link
Quality in Multi-hop Wireless
Mesh Networks
Kyu-Han Kim and Kang G. Shin
Real-Time Computing Laboratory
Department of EECS, The University of Michigan
September 25, 2006
ACM MobiCom
Accurate Measurement of Link Quality
Routing protocols
Quality-of-Service
Fault diagnosis
Channel assignment
Internet
Gateway 1
Gateway 2
Accuracy
Efficiency
Asymmetry
Feasibility
Focus of this work
 Present a novel link-quality measurement framework
 Show potential benefits of the framework
`
2
Outline




Limitations
Approach
Evaluation
Conclusion
3
Limitations
 Broadcast-based Active Probing (BAP)
▪ Based on inexpensive broadcast
▪ Easy to implement at all layers
LAB  S AB  S BA
A
B
Different PHY settings [Aguayo04]
 Bidirectional measurements

BAP
A
Data
B
SBA=0.6
LAB = LBA = 0.54
A
SAB=0.9
B
ACK
LAB= 0.9
4
Limitations
 Unicast-based Active Probing
▪ Same PHY settings as data transmissions
▪ Unidirectional measurement (LAB≠ LBA)
A
B
Capacity overhead (i.e., O(n) vs. O(1) )
 Blind to underlying retransmission at MAC

 Self-monitoring data frame transmission
▪ Reduce probing overheads
▪ Use unicast and unidirectional results
Require active probing for probing idle links
 Blind to underlying retransmission at MAC

5
Outline




Limitations
Approach
Evaluation
Conclusion
6
EAR: Efficient and Accurate link-quality monitoR
 EAR
▪ exploits existing traffic by adaptive selection of passive,
active or cooperative measurement scheme
uses unicast packets and derives unidirectional results
▪
▪ is easily deployable and places itself at a network layer and
a device driver for cross-layer interactions
Mesh Router
Inner EAR or iEAR
IP
EAR
Device driver
Outer EAR or oEAR
MAC / PHY
7
EAR Design and Operations
Tegg ≥ Pthresh
MeasureMeasureTcrss ≥ Cthresh Cooperative
period (i)
Cycle (i)
Tcrss < Pthresh Tcrss ≥ Cthresh
UpdateActiveperiod (i)
Time
Tcrss ≤ Cthresh
Techniques
Passive
Cooperative
Active
Routing-table
Manager
Link State
Table

Passive
Tegg < Pthresh
Task
Processor


Outgoing traffic
Incoming traffic
oEAR MAC
Tegg ≥ Pthresh
Task
Timers

iEAR
 Distributed measurement
 Hybrid techniques
 Unicast-based results
 Cross-layer interaction
Management Information Base at MAC
 Data frame transmission results
Link quality of interest
 Link capacity: Data transmission rate
 Delivery ratio: d = NS/NT
8
Measurement Techniques (1)
Passive scheme
A
B
C
 Monitoring at a device driver
 Interaction with MAC’s MIB
 Obtaining transmission results
Link-state table at B
Time
Links Scheme Ratio Data rate
BA Passive 0.9 11 Mbps
9
Measurement Techniques (2)
Cooperative scheme
A
B
C
 Selective overhearing
 Overhearing cross traffic
 Reporting overhearing results
Time
Link-state table at B
Links Scheme Ratio Data rate
BA Passive 0.9 11 Mbps
BC
Coop
0.9 11 Mbps
10
Measurement Techniques (3)
Active scheme
A
B
C
 Minimizing probe overheads
 Adaptive active probing timer (ET)
 Using a cooperation technique
Link-state table at B
Time
Links Scheme Ratio Data rate
BA
Active
0.9 11 Mbps
BC Active-Co 0.9 11 Mbps
ET=rand[0,W]
P
W=2
W=4
W=1
P
P
P
P
Cycle
11
Outline




Limitations
Approach
Evaluation
Conclusion
12
Performance Evaluation
 Implementation
▪ Linux kernel-2.4.20 (Netfilter and Orinoco device driver)
▪ ETX and ETT routing metrics
N
W
E
▪ BAP for comparison
N4 N8
S
 Testbed
▪
▪
▪
▪
Corridor
2nd floor of EECS Building
N10
10 mesh nodes
IEEE 802.11b PCMCIA
N5
N2
Other public networks (802.11b/g)
N9
N7
N1
Offices
N6
N3
 Evaluation Metrics
▪ Accuracy, asymmetry-awareness, and efficiency
13
Characteristics of Link Asymmetry
 Link asymmetry is common
diff =| SF– SB |
duration
Wireless link-quality has different degrees of quality
asymmetry with different amounts of asymmetry duration
14
Accuracy
 Comparison between BAP and EAR
▪ BAP: 10.2% error
▪ EAR: 1.6% error
SN1N2
N1
N2
LN1N2
EAR reduces measurement error from 4 to 20 times,
compared to BAP, and provides unidirectional results
15
Asymmetry Awareness
 EAR improves end-to-end throughput
N
W
E
N4
S
N8
Corridor
BAP
N5
N10
N9
EAR
N7
N1
N2
Offices
N6
N3
 Benefits
▪ Goodput improvement
▪ 12.9~35.2% (1-hop), 114% (3-hop)
▪ Thanks mainly to unidirectional measurements of EAR
EAR helps routing protocols identify/use asymmetric links
16
Efficiency
 Probing overheads
▪ Large number of neighboring
▪
▪
nodes in 200m x 200m
No egress/cross traffic
Thanks to cooperation and
exponential back-off timers
 Use of data traffic for measurements
13 times more
measurement
traffic than BAP
owing to hybrid
approach
17
Outline




Limitations
Approach
Evaluation
Conclusion
18
Conclusion
 EAR solves problems of varying and asymmetric wireless
link-quality in wireless mesh networks
 EAR is a hybrid measurement framework that efficiently
and accurately measures wireless link quality
 EAR’s link-asymmetry-awareness improves end-to-end
throughput by up to two times
 EAR is useful for wireless network protocols, such as
routing, QoS support and network diagnosis
 Remaining Issues
▪ Measurement of other QoS parameters (e.g., latency)
▪ Extension for MANETs
19
Any questions?
Thank You !
Contact:
Kyu-Han Kim ([email protected])
Real-Time Computing Laboratory
(http://kabru.eecs.umich.edu)
20