Transcript Wireless Networks: Things I Wish I Had Learned in

Wireless Networks:
Things I Wish I Had Learned in Kindergarten
Nitin Vaidya
Illinois Center for Wireless Systems (ICWS)
University of Illinois at Urbana-Champaign
www.icws.uiuc.edu
© 2007 Vaidya
1
Mesh Networks
Multi-hop wireless networks
A
C
F
B
E
D
2
Outline

A few obvious observations
3
1
outgrow
Those who cannot learn from history
are doomed to repeat it
With apologies to George Santayana
4
Pre-History of Wireless Communications:
Smoke Signals, Fires, Semaphore

Relaying : Multi-hop routes (store-and-forward)
5
Pre-History of Wireless Communications:
Homing Pigeons

Exploiting mobility
6
Pre-History of Wireless Communications:
Perimeter Guards
overcome

Aggregating knowledge
7
Reusing Ideas Reasonable,
but Need to Explore Better Alternatives
No wired-equivalent
for wireless networks
No links !
8
Wireless Channel Offers Rich Diversity
Current mesh protocols
exploit diversity
only to a limited extent
Layer 1 : 2+ gap
The vanishing link :
Diversity confuses
the notion of a link
9
2
Interference is Information
10
Interference is Information
B
A
D
C
Signal
Interference
11
Interference is Information

Discard interference
Per-flow capacity decreases with network size

Utilize information in “interference”
Per-flow capacity independent of network size
Requires network scale cooperation
[Gupta-Kumar,Ozgur et al.]
12
Interference is Information


Cooperation is already used in wireless networks
Routing, medium access, data caching, …
Need to design protocols that facilitate
fundamentally better cooperation
13
3
Bits Are Not Automobiles
14
Bits Are Not Automobiles

We treat information networks same as
physical transportation networks
• Planes, Trains and Automobiles


Bits can be combined (encoded) and
separated, unlike physical objects
Network coding:
Deliberate (reversible) injection of interference
[Ahlswede et al.]
15
Network Coding
P
A
P
B
Q
C
Q
16
Network Coding
P ++Q
Q
P
Q
A
B
C
Q
P
[Katabi,Medard]
17
4
Physics Does Not Know Layers
18
Physics Does Not Know Layers


Layering is an abstraction, not a theorem
Backpressure scheduler ( “ throughput optimal ” )
spans traditional layers 1 through 3:
arg max
r Є Rate
Region
∑ W(l) r(l)
l
[Tassiulas]
19
Physics Does Not Know Layers

Layering is useful, but need a principled approach to
identifying appropriate cross-layer exchange
Great start towards this: Network utility optimization
» Queue as price
Shortcomings:
» Not all requirements easy to capture as concave utility
» Framework does not (yet) yield enough insight on
practical “scheduling/routing”
20
[Kelley,Srikant,Shroff]
5
Opportunism Pays
21
Opportunism Pays


Channel variations make it difficult to predict
short-term optimal in advance
Late binding can work better
–
–
–
–
Opportunistic beamforming
Opportunistic routing (network layer)
MAC-Layer anycasting (MAC layer)
…
[Viswanath,Morris,RoyChoudhury]
22
6
Theory and Practice:
The Twain Must Meet
23
Theory and Practice



(Phy) Theory has had a significant impact on
cellular system design
Little impact so far on multi-hop wireless networks
Difficulty arises from capturing essential system
characteristics in a tractable abstraction
24
Net-X
Multi-Interface Multi-Channel Mesh
3 channels
8 channels 4 channels
26 MHz
100 MHz
200 MHz
150 MHz
915 MHz
2.45 GHz
5.25 GHz
5.8 GHz
250 MHz
500 MHz
1000 MHz
24.125 GHz
61.25 GHz
122.5 GHz
25
[Kyasanur-Vaidya]
Channel-Interface Scenario 1

One interface per channel used in the network
1
1
m
c=m
number of interfaces m = number of channels used c
26
Channel-Interface Scenario 2
number of interfaces m < number of channels c
1
1
m
m
c
This is the likely scenario
27
Net-X
D
Theory
to
Practice
E
Fixed
F
B
A
Switchable
C
Capacity
bounds
Net-X
testbed
Insights on
protocol design
OS improvements
Software architecture
User
Applications
Multi-channel
protocol
IP Stack
ARP
Channel Abstraction Module
Linux boxes
Interface
Interface
Device Driver
Device Driver
28
Net-X : Main Lessons

Interesting research at the intersection of
theory and protocols for real systems
» Many opportunities remain untapped


Physical layer capabilities provide the promise of
higher performance
Practical protocols needed to realize these gains
–
–
–
–
MIMO, Beamforming
Adaptive power/rate/carrier sensing
Channel diversity
Multi-user diversity
29
7
Accuracy and Repeatability:
One Without the Other
30
Repeatable (Experimental) Evaluation of
Wireless Networks


Electromagnetic isolation difficult in typical
operating environments
EM isolation feasible in an anechoic chamber
Illinois Wireless Wind Tunnel
[Bernhard et al.]
31
Illinois Wireless Wind Tunnel
Objectives

Controlled interference

Controlled mobility and environment

Accurate Scaling
32
Network Scaling

Size of the anechoic chamber often smaller than the
real network
 Need to scale the wireless network




Scale power to scale network “size”
Scale speed
Scale large scale path loss variations (shadowing)
Scale small scale fading:
Scaling of speed affects Doppler
33
Reality Strikes Back

Can’t scale speed of light (adequately)
 Hard to scale for path delay, or delay spread


Can’t evaluate accurately if PHY exploits delay
spread
Trade-off:
• EM isolation, but limited delay-spread
• Non-isolation, but true-scale otherwise
34
8
What You Don't Know Can Hurt You
35
What You Don't Know Can Hurt You


Channel variations make timely accurate
channel state dissemination impossible
Non-identical channel state observations can lead
to conflicting actions
»
»
»
»
»
»
Difficulty in distributed rate/power control
Difficulty in diagnosing attacks
Unique address assignment problem
Inaccurate topology estimates
Obfuscation of cause of packet loss
Hidden / exposed terminals
36
9
Divide and Conquer
37
Divide and Conquer


At higher rates, rate-independent overheads
become significant
Partitioning the resources can
Reduce the impact of rate-independent overheads
Improve contention resolution
38
Conclusion
39
Conclusion



Diversity in wireless networks provides many
opportunities for improving performance
Networking researchers need to understand PHY
better, and vice-versa
A truly cross-layer approach,
collaborations between EE and CS/CE researchers,
likely to be more successful
• In design and evaluation both
GENI
40
Thanks!
www.crhc.uiuc.edu / wireless
41
Incomplete List of Other Researchers
Whose Work Influenced the Observations










R. Ahlswede
Mung Chiang
Dina Katabi
Frank Kelly
P. R. Kumar
Ralph Koetter
Muriel Medard
P. Larsson
Robert Morris
A. Ozgur








Ness Shroff
R. Srikant
Sasha Stolyar
Leandros Tassiulas
David Tse
Terry Todd
Pramod Viswanath
R. W. Yeung
42