Transcript PowerPoint Slides - Nitin Vaidya - University of Illinois at Urbana

Multi-Channel Wireless Networks:
Theory to Practice
Nitin Vaidya
Electrical and Computer Engineering
University of Illinois at Urbana-Champaign
Sept. 8. 2008
1
Multi-Channel Wireless Networks
Acknowledgements
Ph.D
M.S.

Jungmin So (2006)

Priya Ravichandran (2003)

Pradeep Kyasanur (2006)

Chandrakanth Chereddi (2006)

Vartika Bhandari (2008)

Rishi Bhardwaj (2007)

Thomas Shen (2008)

Vijay Raman
Post-docs

Wonyong Yoon

Cheolgi Kim
Funded in part by:
NSF, ARO, Motorola, Boeing
2
Preliminaries …
3
Wireless Networks

Wireless paradigms:
Single hop versus Multi-hop

Multi-hop networks:
Mesh networks, ad hoc networks, sensor networks
4
What Makes Wireless Networks
Interesting?
Significant path loss
- Signal deteriorates over space
+ Spatial re-use feasible
B
A
power

S
distance
5
5
What Makes Wireless Networks
Interesting?
Interference management non-trivial
B
A
power

I
C
D
S
distance
6
What Makes Wireless Networks
Interesting?
Many forms of diversity
• Time
• Route
• Antenna
• Path
• Channel
7
What Makes Wireless Networks
Interesting?
Time diversity
C
D
gain
Time
8
What Makes Wireless Networks
Interesting?
Route diversity
infrastructure
AP1
Access
point
AP2
B
F
A
X
C
D
E
Z
9
What Makes Wireless Networks
Interesting?
Antenna diversity
D
C
A
B
10
Sidelobes not shown
What Makes Wireless Networks
Interesting?
Path diversity
11
What Makes Wireless Networks
Interesting?
Channel diversity
High interference
Low gain
B
A
B
A
High gain
B
A
B
A
D
C
D
C
Low interference
12
Wireless Capacity

Wireless capacity limited

In dense environments, performance suffers

How to improve performance ?
13
Improving Wireless Performance

Exploit physical resources, diversity

Exploiting diversity requires appropriate protocols
14
This Talk
Utilizing multiple channels
in multi-hop wireless
15
Multi-Channel Environments
Available spectrum
Spectrum divided into channels
1
2
3
4
…
c
16
Multiple Channels
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
IEEE 802.11 in ISM Band
17
Shared Access : Time & Spectrum
D
B
C
A
One Channel
Spectrum
A
B
Time
A
Two Channels
C
A
B
C
Time
C
18
Why Divide Spectrum into Channels ?

Manageability:
• Different networks on different channels
avoids interference between networks

Contention mitigation:
• Fewer nodes on a channel reduces channel contention
19
Why Divide Spectrum into Channels ?


Lower transmission rate per channel
• Slower hardware (simpler, cheaper)
Reducing impact of bandwidth-independent
overhead
fixed time
data size/rate
20
Outline
capacity
D
Theory
to
Practice
Net-X
testbed
E
Fixed
F
B
A
Switchable
C
Capacity
bounds
channels
Insights on
protocol design
OS improvements
Software architecture
User
Applications
Multi-channel
protocol
IP Stack
ARP
Channel Abstraction Module
Linux box
CSL
Interface
Interface
Device Driver
Device Driver
21
Interfaces & Channels

An interface can only use one channel at a time
Channel 1
W
cW
Channel c

Switching between channels may incur delay
22
Channel Switching

Unconstrained :
An interface can tune to any available channel

Constrained :
Restricted channel switching
23
This Talk

Assume unconstrained switching

Constrained switching results elsewhere
24
Multiple Interfaces


Reducing hardware
cost allows for
multiple interfaces
m interfaces per node
1
m
25
Practical Scenario

m<c
A host can only be on
subset of channels
1
1
m
m
m+1
c
c–m unused channels
at each node
26
Multi-Channel Mesh

How to best utilize multiple channels
in a mesh network
with limited hardware ?
?
27
Need for New Protocols
m<c
c = 4 channels
m = 2 interfaces
1,2
1,2
A
B
D 1,2
Some channels not used
1,2
C
1,3
1,2
3,4
A
B
C
D
2,4
Network poorly connected
28
Multi-Channel Networks
Many Inter-Dependent Issues

How to choose a channel
for a transmission?
B
A


How to schedule
transmissions?
How to measure
“channel quality”
C
- gain, load

How to select routes ?
29
Outline
capacity
D
Theory
to
Practice
Net-X
testbed
E
Fixed
F
B
A
Switchable
C
Capacity
bounds
channels
Insights on
protocol design
OS improvements
Software architecture
User
Applications
Multi-channel
protocol
IP Stack
ARP
Channel Abstraction Module
Linux box
CSL
Interface
Interface
Device Driver
Device Driver
30
Capacity Analysis


How does capacity improve with more channels ?
How many interfaces necessary to
efficiently utilize c channels ?
31
Network Model
32
Network Model
[Gupta-Kumar]

Random source-destination pairs among
randomly positioned n node in unit area,
with n  ∞
33
Capacity = ?


l = minimum flow throughput
Capacity = n l
34
Capacity Constraints


Capacity constrained by available
spectrum bandwidth
Other factors further constrain
wireless network capacity …
35
Connectivity Constraint
[Gupta-Kumar]

Need routes between source-destination pairs
Places a lower bound on transmit power
A
D
Not connected
A
D
Connected
36
Interference Constraint
[Gupta-Kumar]


Interference among simultaneous transmissions
Limits spatial reuse
>r
A
r
C
D
B
37
Capacity
[Gupta-Kumar]

c=m
capacity
a
1
1
m=c
c=m
Capacity scales linearly with channels
38
Capacity

What if fewer interfaces ?
1
1
m
m
m+1
c
39
Interface Constraint

Throughput is limited by number of interfaces in a
neighborhood
N nodes in the “neighborhood”
 total throughput ≤ N * m * W
Interfaces as a resource
in addition to spectrum, time and space
40
Mutlti-Channel Capacity
Order of
Channels (c/m)
41
Capacity with n  ∞
Are these results relevant ?

Yield insights on design of
good routing and scheduling protocols

Insights relevant in smaller networks too
42
Outline
capacity
D
Theory
to
Practice
Net-X
testbed
E
Fixed
F
B
A
Switchable
C
Capacity
bounds
channels
Insights on
protocol design
OS improvements
Software architecture
User
Applications
Multi-channel
protocol
IP Stack
ARP
Channel Abstraction Module
Linux box
CSL
Interface
Interface
Device Driver
Device Driver
43
Insights from Analysis (1)
Channel Assignment

Need to balance load on channels

Local coordination in channel assignment helpful
44
Insights from Analysis (2)


Static channel allocation
not optimal performance
in general
Must dynamically switch channels
Channel 1
B
A
2
C
D
45
Insights from Analysis (3)

Optimal transmission range function of
number of channels
Intuition:
# of interfering nodes ≈ # of channels
46
Insights from Analysis (4)

Routes must be distributed within a neighborhood
D
D
F
A
B
E
F
B
A
E
C
C
m=1
interface
c=1,2
channels
47
Insights from Analysis (5)

Channel switching delay potentially detrimental,
but may be hidden with
careful scheduling – create idle time on
interfaces between
channel switches
additional interfaces
48
Protocol Design: Timescale Separation
Upper layers

Routing: Longer timescales
(Optional) Multi-channel aware
route selection

Interface management:
Shorter timescales
Dynamic channel assignment
Interface switching
Transport
Network
802.11 Link
Physical
Layer
49
Channel Management


Two interfaces much better than one
Hybrid channel assignment: Static + Dynamic
Fixed (ch 1)
Fixed (ch 2)
Fixed (ch 3)
A
B
C
Switchable
2
1
Switchable
3
2
Channel assignment locally balanced
Switchable
50
Selecting Channel Diverse Routes
1
A
D
3
4
2
3
B
4
4
C
4
E
F
4
2
A needs route to C
Route A-B-C better  More channel diverse
51
Impact of Switching Cost
on Route Selection
1
3
4
A
B
C
3
D needs route to F
D
2
Route A-B-C in use
2
E
4
4
F
2
Route D-E-F better
2
Prefer routes that do not require frequent switching
52
CBR – Random topology
(50 nodes, 50 flows, 500m x 500m area)
CBR flows
Normalized throughput
16
(m,c)
(2,2)
(2,5)
(5,5)
(2,12)
(12,12)
14
12
10
8
6
4
2
0
1
2
3
4
5
6
7
Topology number
8
9
10
53
Outline
capacity
D
Theory
to
Practice
Net-X
testbed
E
Fixed
F
B
A
Switchable
C
Capacity
bounds
channels
Insights on
protocol design
OS improvements
Software architecture
User
Applications
Multi-channel
protocol
IP Stack
ARP
Channel Abstraction Module
Linux box
CSL
Interface
Interface
Device Driver
Device Driver
54
Net-X Testbed


Soekris 4521


Linux 2.4
Two 802.11a radios
per mesh node (m = 2)
Legacy clients with
1 radio
c = 5 channels
Net-X source
available
55
Phy-Aware Support

Additional mechanisms needed
to choose channels based on
destination
Ch. 2
B
A
Ch. 1
C
Next hop not equivalent to a wireless interface id


Phy-aware forwarding not supported traditionally
In general, need a “constraint” specification
for desired channel(s), antenna beamform,
power/rate, … to be used for the next hop
56
Phy-Aware Support

Multi-channel (phy-aware)
broadcast
Ch. 2
D

Channel switching from user space
has high latency: frequent switching
from user space undesirable
Ch. 3 A
B
Ch. 1
C
57
New Kernel Support

Interface management needs to be hidden from
“data path”
– Buffering packets for different channels
– Scheduling interface switching
Ch. 2
Ch. 1
Packet to B
buffer packet
Interface switches
to channel 1
Packet to C
Packet to C arrives
58
Net-X Architecture
User
Applications
Multi-Channel Routing,
Channel Assignment

IP Stack
ARP
Interface and Channel
Abstraction Layer
Interface
Device Driver
Interface
Device Driver
Abstraction layer
simplifies use of
multiple interfaces
Implemented by
extending Linux
“bonding driver”
59
capacity
D
E
Fixed
F
B
A
Switchable
C
Capacity
bounds
channels
Insights on
protocol design
Wrap-up
Net-X
testbed
OS improvements
Software architecture
User
Applications
Multi-channel
protocol
IP Stack
ARP
Channel Abstraction Module
Linux box
CSL
Interface
Interface
Device Driver
Device Driver
60
Current Status

~ 25 node network operational

Protocol improvements … ongoing process

Further results for
• Scheduling in multi-channel networks
• Constrained channel assignment
• Cross-channel interference
61
Summary



Significant performance benefits using
many channels despite limited hardware
Insights from analysis useful in protocol design
Conversely, implementation experience helps
formulate new theoretical problems
Important to complete the
loop from theory to practice
62
Research Opportunities


Significant effort in protocol design needed to
exploit available physical resources
Other opportunities:
• MIMO (multi-antenna)
• Cooperative relaying
• Dense wireless infrastructure
63
Thanks!
www.crhc.uiuc.edu/wireless
64
Thanks!
www.crhc.uiuc.edu/wireless
65
Thanks!
www.crhc.uiuc.edu/wireless
66
Thanks!
www.crhc.uiuc.edu/wireless
67
Scenario 1

1
m=c
One interface per channel
1
1
m=c
c=m
1
Common case
With sufficient hardware
68
Constrained Switchability


An interface may be constrained to use only a
subset of channels
Motivation:
Hardware limitations (“untuned radio” [petrovic] )
Hardware heterogeneity
(802.11b/g versus 802.11a/b/g)
Policy issues (cognitive radios)
69
Impact of Constrained Switching
(4, 5)
(4, 6)
(5, 6)
(1, 2)
(1, 7)
(4, 5)
A
(6, 7)
E
B
D
(3, 4)
C (2, 4)
(7, 8)
(1, 3)
Reduced
Connectivity
Detour Routing
(6, 7)
(2, 5)
70
Impact of Constrained Switching
1 relay on channel b
Z
3 relays on channel a
X,Y,Z
a, b
S
a
X
a
Y
Z
a, b
a, b
D
Coupling between channel selection & relay choice
71
Impact of Constrained Switching
a, c
G
a
c
c, f
P
c
a, b
X
c, d
Y
b
b, d
H
d
d
d, f
Q
6 channels: a, b, c, d, e, f
Bottleneck formed at Y
72
Destination Bottleneck Constraint

A node may be destination of multiple flows

Node throughput shared by all the incident flows
f incoming
flows
D
Node throughput
T ≤ mW
Per-flow throughput T / f
73
Multi-Channel Network Capacity
Interference and
interface bottleneck
Interface and
destination bottlenecks
Connectivity and
interference
Ratio c/m
74
Routing Approach

Legacy routing protocols can be operated over our
interface management layer
Does yield significant benefits from multiple channel
Does not consider cost of channel switching

An alternative
Develop a channel-aware metric
(aware of channel diversity and switching costs)
75