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