Transcript Document
Multi-Channel Wireless Networks:
Capacity and Protocols
Pradeep Kyasanur and Nitin H. Vaidya
University of Illinois at Urbana-Champaign
Wireless networks
Access Point
D
C
Wireless
channel
A
B
Infrastructure-based Network
Multi-hop Network
We consider multi-hop networks
Ad hoc networks, mesh networks, sensor networks
2
Key limitation
Wireless channel is a shared resource
Simultaneous transmissions limited by interference
Higher density reduces per-node throughput
Throughput reduces with multiple hops
Throughput reduces as number of flows increase
New applications require higher throughput
Streaming video, games
Improving network capacity is important
3
Multiple channels
Typically, available frequency spectrum is split
into multiple channels
Large number of channels may be available
Using all the available channels is beneficial
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
4
Current state of art
Typical multi-hop networks use one channel only
A
Key challenge: Connectivity vs using multiple channels
1
1
B
1
1
C
1
D
Multiple channels not used
A
1
B
C
2
D
Network is poorly connected
5
Multiple interfaces
Nodes may be equipped with multiple interfaces
Common case may be small number of interfaces
Wireless radio interfaces typically support one
channel at a time
We assume a half-duplex transreceiver
Interface can switch to any channel
Number of interfaces per node expected to be
smaller than number of channels
6
Example configuration
IEEE 802.11 has multiple
channels
Devices can be equipped
with multiple interfaces
12 in IEEE 802.11a
E.g., one interface per
PCMCIA/ mini-PCI slot
Typically, fewer interfaces
than channels
2 interfaces, 12 channels
7
Focus of research
Establish capacity of multi-channel networks
How does capacity vary with channels?
What are the insights from theoretical study?
Design, implement and evaluate protocols
Can we use existing protocols?
Develop suitable protocols optimized for multi-channel
networks
How to implement protocols in real systems?
8
Organization
Capacity analysis
Theory to protocols: Overview of challenges
Protocols
Interface Management Protocol
Routing Protocol
Implementation Issues
Summary and Future Work
9
Capacity problem
Per-node capacity decreases as network density
increases
Use more channels when network density increases
Challenge: Harder to scale interfaces at the
same rate as channels
How does the network capacity scale with large
number of channels, and fewer interfaces than
channels?
10
Related work
[Gupta&Kumar] have studied the capacity of
single channel networks
[Gamal et al.] have studied the throughput-delay
tradeoff
Result applicable for multi-channel networks when
number of channels = number of interfaces per node
Some of our constructions are based on their work
Lot of work on studying capacity in other contexts
Mobility, infrastructure-support, delay constraints, etc.
11
Model
n nodes in the network, all located on a unit torus
c channels are available
m interfaces per node
Interface operates on one channel at a time
Channel model 1: Total bandwidth W, each
channel has bandwidth W/c
Channel model 2: Total bandwidth Wc, each
channel has bandwidth W
12
Network scenarios [Gupta&Kumar]
Arbitrary network
Nodes can be located anywhere on the torus
Traffic patterns can be arbitrarily chosen
Measure of capacity – aggregate network transport
capacity (bit-meters/sec)
Random network
Nodes are randomly placed on the torus
Each node sets up a flow to a random destination
Measure of capacity – minimum of flow throughputs
(bits/sec)
13
Results
Established tight bounds
Upper bounds and constructive lower bounds have
same order
Capacity depends on ratio of c to m
Derived insights from constructions
Capacity-optimal routing and scheduling strategies
14
Arbitrary network – Region 1
Capacity constrained by interference
15
Arbitrary network – Region 2
Capacity constrained by interfaces
16
Random network – Region 1
Capacity constrained by connectivity + interference
17
Random network – Region 2
Capacity constrained by interference (arbitrary n/w)
18
Random network – Region 3
Capacity constrained by bottleneck destination
19
Practical implications
When m < c, it is better to use c channels
Single interface per node often suffices
If only m channels are used, larger capacity loss
Up to log(n) channels, 1 interface is sufficient
Switching delay may not affect capacity
Extra hardware has to be provided
20
Insights for protocol development
Multiple interfaces can simplify protocol design
Routing protocol has to distribute routes
Use one interface for receiving data on a fixed channel
Use second interface for sending data
Important for multi-channel networks
Optimal transmission range depends on density
of nodes as well as number of channels
Optimum: # of interfering nodes = # of channels
21
Open issues
Impact of switching delay has to be better
studied
Is switching required at all?
Capacity under other switching constraints – switch
among only a subset of channels
Analyze capacity of deterministic networks
Given a topology, what is the capacity?
What protocols should be used to achieve this
capacity?
22
Organization
Capacity analysis
Theory to protocols: Overview of challenges
Protocols
Interface Management Protocol
Routing Protocol
Implementation Issues
Summary and Future Work
23
Assumptions
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
Homogeneous channels: Channels with similar
ranges and rates
Possibly channels in same frequency band
Alternatively, use appropriate power control
24
Design choice: Multiple interfaces
Theory indicates single interface may suffice
Multiple interfaces simplify protocols
But, multiple interfaces can hide switching delay
Our proposal, described later, is simple to implement
Multiple interfaces can allow full-duplex transfer
Useful when multiple channels are available
A
1
B
2
C
25
Design choice: Protocol separation
Separate protocol design into two components
Interface management – shorter timescales
Interface management
Routing
Map interfaces to channels
Schedule and control interface switching
Routing – longer timescales
Select “channel diverse” routes
26
Protocol separation overview
Routing and
Interface assignment
User Space
Kernel Space
IP Stack
Interface Switching
and Buffering
Interface
Interface
27
Link layer requirements
Utilize all the available channels
Even if number of interfaces < number of channels
E.g.: Interfaces can be switched to different channels
A
1,2
B
2
D
3,4
C
Ensure connectivity is not affected
B should be able to communicate with A and D
Need to be cognizant of switching delay
28
Link layer requirements
Solution should be simple to implement
Avoid the need for complicated co-ordination, tight
time synchronization
Allow implementation with existing hardware
Avoid requiring hardware changes
Avoid assuming specific hardware capabilities
29
Routing requirements
Improve single flow throughput by using multiple
channels
Both interfaces can be utilized at the relay nodes
A
1
B
2
D
3
C
Improve network throughput by distributing flows
A
1
B
3
D
2
C
4
E
F
30
Organization
Capacity analysis
Theory to protocols: Overview of challenges
Protocols
Interface Management Protocol
Routing Protocol
Implementation Issues
Summary and Future Work
31
Key components
Interface assignment strategy
How to map interfaces to channels?
How to ensure neighboring nodes can communicate
with each other?
Interface management protocol
Control when interfaces are switched, based on
assignment strategy
Buffer packets if interface is busy
32
Interface assignment strategies
Static Interface Assignment
Dynamic Interface Assignment
Interface to channel assignment is fixed
Interface assignment changes with time
Hybrid Interface Assignment
Some interfaces use static assignment, others use
dynamic assignment
33
Static interface assignment
Each interface is fixed to one channel
A
Does not require frequent co-ordination
1,2
B
1,2
D
1,2
C
Not all channels
used
Common channel approach (e.g., [Draves2004Mobicom])
A
1,2
B
2
D
3
3
Not possible
E
3,4
C
May lead to longer
routes
Varying channel approach (e.g., [Raniwala2005Infocom])
34
Dynamic interface assignment
Interfaces can switch channels as needed
E.g., [So2004Mobihoc, Bahl2004Mobicom]
A
1-4
1-4
B
D
1-4
C
Transmissions can dynamically occur on any channel
A
1
B
2
D
Co-ordination may be needed
for each transmission
D is unaware of B’s communication
35
Hybrid strategies
One common channel used as “control” channel
One interface always fixed to this channel
Remaining channels used as “data” channels
Second interface switches among data channels
1
A
1
B
[Nasipuri1999Wcnc]
1
D
C
[Jain2001Ic3n]
2-4
2-4
2-4
Channel for data transmission negotiated on control channel
Common control channel becomes a bottleneck
36
Proposed hybrid assignment
One interface “fixed” on a channel
Other interfaces “switch” as needed
Dynamic assignment
Fixed interface receives data on well-known channel
Different nodes use different fixed channels
Avoids co-ordination issues, deafness problems
Switchable interfaces send on recipient's fixed channel
Retain flexibility of dynamic assignment
37
Hybrid assignment example
Fixed (ch 1)
Fixed (ch 2)
Fixed (ch 3)
A
B
C
Switchable
2
1
Switchable
3
2
Switchable
Switchable interface of B switches to channel 3 when sending to node
C, and to channel 1 when sending to node A
Any node pairs within transmission range can communicate
38
Identifying fixed channel
Static Approach: Fixed channel as a function of
node-identifier
Simple to build, but may not balance assignment
Dynamic approach: Choose fixed channel based
on neighborhood information
A node chooses least used channel for fixed channel
Can balance load, and still inexpensive
39
Interface management
Each channel is associated with a queue
Broadcast packets are inserted in to every queue
Fixed interface services fixed channel queue
Switchable interface services other channels
Channels serviced in round-robin fashion
Each channel is serviced for at most MaxSwitchTime
40
UDP throughput – chain topology
35
DSR - 1
MCR - 2
MCR - 5
MCR - 12
30
25
20
15
10
5
0
1
2
3
4
5
6
7
Chain length (in hops)
8
9
10
41
FTP throughput – chain topology
30
DSR - 1
MCR - 2
MCR - 5
MCR - 12
25
20
15
10
5
0
1
2
3
4
5
6
7
Chain length (in hops)
8
9
10
42
Open issues
Broadcast cost increases linearly with channels
Consider partial broadcasts
Use a separate broadcast channel, with third interface
Fixed channel selection is topology-based
Consider load, channel quality information
Integrate with a routing solution
43
Organization
Capacity analysis
Theory to protocols: Overview of challenges
Protocols
Interface Management Protocol
Routing Protocol
Heterogeneous channels
Summary and Future Work
44
Routing approach
Existing routing protocols can be operated over
interface management protocol
May not select channel diverse routes
Does not consider cost of switching interfaces
Our solution
Develop a new channel-aware metric
Incorporate metric in an on-demand source-routed
protocol
45
Selecting channel diverse routes
Most routing protocols use shortest-hop metric
Not sufficient with multi-channel networks
Need to exploit channel diversity
1
B
1
A
Route A-C-D is better
D
2
C
1
When possible, select routes where
different hops are on different channels
46
Impact of switching cost
Interface switching cost has to be considered
Switching interfaces incurs a delay
A node may be on different routes, requiring switching
2
B
1
Route A-B-D is better
D
A
2
1
C
3
When possible, select routes that do
not require frequent switching
E
47
Designing a routing metric
Measure switching cost for a channel
Measure total link cost of a hop
Combine individual link costs into path cost
2
B
1
D
A
2
1
C
3
E
48
Measuring switching cost
Switching cost depends on the likelihood a
switch is necessary before transmission
Fixed channel has cost 0
“Active” channel has low switching cost
Switching cost (SC) directly proportional to time
spent on other channels
3
E
1
C
0.9
D
0.1
49
Routing protocol
Incorporate metric in on-demand source-routed
protocol (similar to DSR)
Source initiates RREQ
Intermediate nodes forward RREQ if,
RREQ messages modified to include link costs
New RREQ
Cost of RREQ smaller than previously seen RREQ
Destination can compute best path
Using link cost information in sent RREQ
50
Throughput in random networks
DSR - 1
MCR - 2
MCR - 5
MCR - 12
14
12
10
8
6
4
2
0
1
2
3
4
5
6
7
Topology Number
8
9
10
51
Throughput with varying load
20
DSR - 1
MCR - 2
MCR - 5
MCR - 12
15
10
5
0
2
4
6
8
10
Number of Flows
12
14
52
Open issues
Incorporate load information into MCR metric
Support for route caching
Metric does not allow route combination
Design alternate metrics?
Integrated routing and fixed channel selection
Can improve performance at cost of increased
complexity
53
Organization
Capacity analysis
Theory to protocols: Overview of challenges
Protocols
Interface Management Protocol
Routing Protocol
Implementation Issues
Summary and Future Work
54
Lack of multi-channel support
Existing assumptions break with multiple channels
Assume # of channels = # of interfaces
Routing table has interface information only
Not easy to use multiple interfaces
Switching channels requires explicit invocation
Interfaces and channels not hidden from applications
Frequent switching not permitted
55
Requirements
Hide interface management from “data path”
Break node-channel mapping
Allow existing applications to work unmodified
Allow channel to be selected based on destination
Support multi-channel / single channel broadcast
Broadcast primitive required for many applications
56
Proposed architecture
Channel Policy
Manager
User Applications
ARP
Abstraction layer exports
single virtual interface
IP Stack
Channel switching
details are hidden
Interface and Channel
Abstraction Layer
Interface
Interface
Joint work with Chandrakanth Chereddi
Fixed channel selection,
and routing protocol is
implemented as part of
channel policy manager
57
Organization
Capacity analysis
Theory to protocols: Overview of challenges
Protocols
Interface Management Protocol
Routing Protocol
Heterogeneous channels
Implementation Issues
Summary and Future Work
58
Summary
Goal of the project is to utilize multiple channels
Research issues considered are
Analysis of capacity of multi-channel networks
Design of protocols for multi-channel networks
Implementing protocol suite in testbed
59
Future work
Capacity analysis with switching delay
Flow-aware protocol design
What if there is no switching allowed at all?
Assign channels based on channel quality and load
Select routes based on existing routes
Implementation and measurement
Fully implement all protocols
Measure characteristics of multiple channels
60
Questions?
More details at:
http://www.crhc.uiuc.edu/wireless
61
Backup Slides
62
Arbitrary Network: Upper bound
Interference constraints [Gupta&Kumar]: Each
pair of simultaneous receivers must have
minimum separation
Separation depends on transmission radius
Bounds the number of simultaneous transmissions
Interface constraint: Only m interfaces available
Each node can send/receive at most m bits/sec
63
Arbitrary Network: Lower bound
Divide torus in to
square cells
Each cell has
nodes
c sender nodes
c receiver nodes
64
Random Networks: Upper bound
Arbitrary network constraints: Random network is
a special case of an arbitrary network
Connectivity constraint: A minimum transmission
range is needed to ensure network is connected
Destination bottleneck constraint: The maximum
number of incoming flows at any node will limit
per-flow throughput
65
Lower bound: Routing
Divide torus in to square cells of area a(n)
a(n) depends on the number of channels
Route through cells on the straight line joining
source and destination
Balance route
assignment
within each cell
66
Lower bound: Step 1 schedule
Divide every second in to “hop-color” slots
Flow scheduling: For each hop of a flow,
schedule its transmission in some hop-color slot
Procedure:
Build a routing graph
Edge color the graph
Vertices are nodes in the network
One edge for every hop
Number of colors used = number of hop-color slots
Map each color to a “hop-color” slot
Every hop is scheduled in slot associated with its color
67
Lower bound: Step 2 schedule
Divide each “hop-color” slot in to “node” slots
Node scheduling: Each node can only transmit in
its node slot
Procedure:
Build an interference graph
Vertex color the graph
Vertices are nodes in the network
One edge for every pair of nodes that may interfere
# of colors = # of node slots per hop-color slot
Map each color to a slot
Each node transmits only in slot associated with its color
68
Switching Delay
Initial analysis ignores interface switching delay
Upper bounds do not mandate switching
Open question: Is interface switching required at all
Possible that switching delay does not affect capacity
Lower bound constructions affected by delay
Capacity affected only if there are latency constraints
Even with latency constraints, multiple interfaces can
hide delay
69
Benefits of Proposed Strategy
Frequent co-ordination not required
Maintains full-connectivity
Fixed channel information infrequently exchanged
Any node pairs within transmission range can
communicate
No changes required to MAC protocol
Can be built with existing IEEE 802.11 hardware
70
Arbitrary networks
Two capacity regions
When
capacity is
When
capacity is
71
Random networks
Three capacity regions
1)
capacity is
2)
capacity is
3)
capacity is
72
One approach
Based on ETT measurement [Draves2004Mobicom]
ETT(j) = Expected Transmission Time of packet
LinkLossRate measurement modified
LinkRate measured from probing driver
73
One path metric (MCR)
Based on WCETT [Draves2004Mobicom]
Path cost limited by bottleneck channel cost ( Xj )
Network throughput depends on aggregate cost
74
CBR throughput
75
CBR throughput
76