Transcript Layer 2 (LL/MAC) Performance Analysis and Improvement of

Scaling the Throughput of Wireless
Mesh Networks via Physical Carrier
Sensing and Two-Radio MultiChannel Architecture
Jing Zhu*, Sumit Roy*, Xingang Guo**, and W. Steven Conner**
*Department of Electrical Engineering
U of Washington, Seattle, WA
**Communications Technology Lab
Intel Corporation, Hillsboro, OR
Outline of Presentation
• Mesh Networks: Introduction, Architecture
• Enhancing Aggregate (Network) Throughput
1. Enhance spatial reuse via optimal physical carrier
sensing
2. Multiple Orthogonal Channels (frequency reuse)
Channel Allocation with clustering
• Multi-Radio, Multi-channel Architecture  Towards a
soft-radio architecture for high-performance MESH
Mesh Networks: Salient Features

Scalability for coverage


Heterogeneous Nodes, Hierarchy


WiFi, WiMAX, UWB, …
Challenge for MAC in Mesh
- Current MAC Protocols (e.g. 802.11) are not optimized for Mesh


Mobile Clients, APs, SoftAPs (router)
Multiple PHY technologies


Single hop  Multi-hop (mesh)
low efficiency, poor fairness, …
Key Solution Approach: Spatial Reuse + Channel Reuse
Example1: AP-MT Mesh–
Enterprise
1. As # clients (laptops) increase, more APs are needed in the
same area.
2. Available # orthogonal channels is very limited (3 or 8 in
11b/a)  increased multiple acccess interference.
Example 2: Wireless AP-AP
Mesh
Gateway
Access
Point
BSS
BSS
Mobile Terminal
Gateway
BSS
How to scale a MESH?
Our Focus
Network = Link
Throughput Capacity
PHY Optimization:
MIMO, Adaptive
Coded Modulation,
etc.
X
Spatial
Reuse
MAC
Optimization
X
Frequency
(Channel)
Reuse
Frequency Plan:
3 (11b), 7 (11a),
? (11n)
Topology
Control
Outline


CSMA/CA – the core of 802.11 MAC
Spatial Reuse and Physical Carrier Sensing


Enhance Physical Carrier Sensing Scheme



Implementation of PCS in OPNET: Simulation of Spatial
Reuse
Optimal PCS threshold through tuning: PCS adaptation
Channel Reuse: Two-Radio Multi-Channel Clustering
Architecture
Next-gen: Adaptive MAC Framework for Mesh
CSMA/CA – basic 802.11 MAC

Carrier Sensing Multiple Access / Collision
Avoidance
Physical Carrier Sensing (PCS) for Interference Avoidance
 Binary Exponential Back-off (BEB) for Collision Avoidance
 (Optional) RTS/CTS Handshaking


Advantages:


Asynchronous, Distributed, Simple
Disadvantages:
Low Spatial Reuse (due to Non-optimized PCS)
 No QoS Support (due to pure contention-based
access)

Spatial Reuse
Multiple communications using the same channel/freq happen
simultaneously at different locations w/o interfering each other



Received SINR Model:
Physical Carrier Sensing
A station samples the energy in the medium and initiates
transmission only if the reading is below a threshold 
threshold optimization
6.00E+06
1 Mbps
One-Hop Capacity (bps)

5.00E+06
2 Mbps
5.5 Mbps
11 Mbps
4.00E+06
3.00E+06
2.00E+06
1.00E+06
0.00E+00
6
7
8
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
Hidden node Problem Revisited
A1
I1
I2
Tx
R
…
Rx
B1
B2
Hidden Node: A node that
cannot hear the current
transmission but will cause
the failure of the
transmission if it transmits.
Any node outside of
transmission range of
Tx and Rx could be a
hidden node, which
cannot be prevented
by using RTS/CTS!
Hidden Nodes in a MESH

Multiple (group) of hidden nodes in a mesh
 Accumulation of interferences
 Impossible to identify due to the unknown number of
contributors.

Instead of preventing all hidden nodes, the goal of the interference
avoidance/mitigation is pro-actively avoiding the worst-case
interference

Sensed energy during PCS is a good indicator of interference level
on the coming transmission.

The lower the sensing threshold, the higher the received SNIR on
average
Effect of PCS threshold on
Network Throughput
Has a great impact on
the performance

PHY improvement
does NOT necessarily
mean proportional
improvement at MAC

Optimal PCS threshold
varies with data rates
and topology
E2E Throughput (bps)

200k
190k
180k
170k
160k
150k
140k
130k
120k
110k
100k
90k
80k
70k
60k
50k
40k
30k
1 Mbps
2 Mbps
5.5 Mbps
11 Mbps
=2, n=90, Ptx=0dbm, PN = - 200dbm, d = 12.5 m, R =13 m
-30
-25
-20
-15
-10
-5
0
pcs_t (db)

How to set the optimal
carrier sensing
threshold dynamically?
d
0
...
1
2
n
Comparison with analytical
estimates


Analytical estimate of end2end t’put: W / k
Observations:

Near optimal results can be achieved by simply tuning
the carrier sensing threshold without using RTS/CTS
(simulation is for 90-node Chain)
[1] Xingang Guo, Sumit Roy, W. Steven Conner, "Spatial Reuse in Wireless Ad-hoc Networks," IEEE VTC
2003, Orlando, FL, October, 2003.
Optimal PCS Threshold

Assumptions:
Co-location of receiver and transmitter
 Homogenous links (same reception power)
 Ignore background noise
 Saturation traffic load


Result:
Optimal PCS Threshold ≈ 1/S0, where S0 is the SINR
threshold for sustaining the maximum link throughput
 S0 = 11dB, 14dB, 18dB, and 21dB for 802.11b 1Mbps,
2Mbps, 5.5Mbps, and 11Mbps, respectively.

4.0M
6.0M
3.5M
5.5M
Total One-Hop Throughput
Total One-Hop Throughput
10x10 Grid with Local Only Traffic and
Homogenous Links
3.0M
2.5M
=3
2.0M
=2.5
=2
1.5M
1.0M
500.0k
data rate =1Mbps, n=10x10, Random Traffic, PN=-200dbm
0.0
-29.0 -27.0 -25.0 -23.0 -21.0 -19.0 -17.0 -15.0 -13.0 -11.0 -9.0
=3
5.0M
4.5M
=2.5
4.0M
3.5M
=2
3.0M
2.5M
2.0M
1.5M
data rate =2Mbps, n=10x10, Random Traffic, PN=-200dbm
-7.0
-5.0
1.0M
-20
pcs_t (db)
-19
-18
-17
-16
-15
-14
-13
-12
-11
-10
-17
-16
-15
pcs_t (db)
10.0M
=3
12.0M
=3
Total One-Hop Throughput
Total One-Hop Throughput

8.0M
=2.5
6.0M
=2
4.0M
2.0M
10.0M
8.0M
=2.5
6.0M
=2
4.0M
2.0M
data rate =11Mbps, n=100, Random Traffic, PN=-200dbm
data rate =5.5Mbps, n=100, Random Traffic, PN=-200dbm
0.0
0.0
-20
-19
-18
-17
-16
pcs_t (db)
-15
-14
-13
-12
-25
-24
-23
-22
-21
-20
pcs_t (db)
-19
-18
Comparison of 1/S0 with the
Simulation Optimal PCS threshold
1/S0(dB)
Simulations match the theoretical estimates !
Enterprise Network: AP-MT Mesh
3 Channels
16 / 30 / 72/ 110 APs
per channel
11Mbps, So = 21dB
154 m x 154 m Office
Path Loss Exponent =3
Scale the Capacity of Enterprise AP
Network
Network Capacity (bps)
73%
Optimal PCS
Today's PCS
35.0M
30.0M
60%
25.0M
20.0M
40%
15.0M
28%
10.0M
Without Spatial Reuse
5.0M
0.0
10
20
30
40
50
60
70
80
90
100
110
120
# AP
1. Network capacity is proportional to # of APs
2. The optimal PCS achieves best per-AP capacity
Summary: Spatial-Reuse for a
single-channel MESH

Spatial-Reuse – the key to improve the aggregate
throughput of a single-channel mesh


Limitations:



links sufficiently separated can transmit simultaneously
without interfering each other
Not effective for a small scale network, i.e. the required
minimum separation distance could be high.
For example, >7 hops in a regular chain network with
802.11b 1Mbps and path loss exponent = 2.
Further Scaling the Throughput with Multiple Channels!
Scaling the Throughput with Multiple
Channels



Takes advantage of multiple channels (even multiple bands)
 8 orthogonal channels in 802.11 a
 3 orthogonal channels in 802.11 b
 UWB, 802.11, and 802.16
Channel Bonding (wider channel BW) is another alternative
 Increases peak link rate but does not translate to proportional
MAC throughput increase
 Lack of backward compatibility: proprietary solution
Multi-channel Approaches – Our Choice
 No change on channel BW
 Use all available channels through the network
 Key issues: channel allocation
Feasible Multi-Channel Architectures

One-Radio Multi-Channel Approaches*




Multi Radio: One Channel per NIC(Network Interface Card) **




Efficient, but will require new MAC (hence not backwards compatible)
Still cannot do full-duplex transmission (e.g.difficult to conduct channel sensing consistently
due to channel switching)
Control overhead – per-packet channel swtiching
Simple to implement
 Each NIC channel is fixed (i.e. comes hard-coded from manufacturer)
 no negotiation required for channel selection
Fully compatible with legacy
But costly, will not scale (number of NICs = number of channels)
Our Approach: Two Radio Multi-Channel



Scale, i.e. number of NICs fixed at 2
Backwards compatible
Assumptions: ad-hoc scenario, irregular but not random topology, homogenous traffic  No
need to frequently update the channel allocation!
*:Jiandong LI, Zygmunt J. Haas, and Min Sheng; ``Capacity Evaluation of Multi-Channel Multi-Hop Ad Hoc Networks ''; IEEE International
Conference on Personal Wireless Communications, ICPWC 2002.
**: A. Adya, P. Bahl, J. Padhye, A. Wolman, and L. Zhu, A Multi-Radio Unification Protocol for IEEE 802.11 Wireless
Networks, Microsoft Research, Technical Report MSR-TR-2003-44, July, 2003.
Two-Radio Based Network Cluster
IP
MAC Extension
Channel 1
Channel 2
Channel 3
•
•
•
Default
MAC/PHY
Secondary
MAC/PHY
Channel Allocation with Clustering
• Each cluster is identified a common channel – i.e. all inter-cluster
communications using the default (primary) radio
• Intra-cluster communications on different channels using the secondary
radio
Interference Mitigation
• Interference among co-channel clusters is minimized through an efficient
channel selection algorithm – MIX (min. interference channel select).
• Interference within the cluster is prevented by Physical Carrier Sensing.
Legacy compatible: legacy APs connect to mesh via default radio.
Framework


Clustering
(HCC)
Reset the 2nd
PHY/MAC
Re
I am
Cluster Head.
ce
i ve
fro Cha
m nn
Clu el
ste Info
r H rm
ea atio
d
n
Cluster Head
is down.
Channel Selection
(MIX)
Find
Channel

Semi-distributed clustering channel
assignment + distributed MAC
mechanisms (802.11 DCF)
 Semi-distributed: channel on
secondary radio is assigned by the
local cluster-head within the cluster
 Distributed: CSMA/CA MAC
protocols
Default vs. Secondary Radio
 Both radios are for data transmission
 The secondary radio has no
administrative functionality, such as
association, authentication, etc.
 The common channel on the default
radio is determined a-priori.
Layer 3 (IP) routing between the
nodes
Configure the 2nd
PHY/MAC
Receive Channel
Update Information
From Cluster Head
Channel
Information
Expired
Reset the 2nd
PHY/MAC
Distributed Highest Connection
Clustering (HCC) Algorithm*



A node is elected as a clusterhead if it is the most
highly connected (has the highest number of
neighbor nodes) node of all its ``uncovered"
neighbor nodes (in case of a tie, lowest ID (e.g.
MAC address) prevails).
A node which has not elected its clusterhead is an
“uncovered” node, otherwise it is a “covered” node.
A node which has already elected another node as
its clusterhead gives up its role as a clusterhead.
* M. Gerla and J.T.-C. Tsai, "Multicluster, mobile, multimedia radio network", ACM/Baltzer Journal of Wireless Networks. vol. 1, (no. 3), 1995, p. 255-265.
Clustering Procedure



Step 1: All nodes have their neighbor list
ready (every node should know its neighbors,
how many)
Step 2: All nodes broadcast their own
neighboring information, i.e., the number of
neighbors, to its neighborhood.
Step 3: A node that has got such information
from all its neighbors can decide its status
(clusterhead or slave)
MIX – Minimum Interference
Channel Selection

On-Air energy estimation per channel
Ei






t 0 T
t0
Ei (t )dt
T
t0: estimation starting time
T: estimation period
Ei(t): on-air energy at time t on channel i
k: Selected Channel
k | E
k

 min( E i | i  {1,2,..., n})
Forwarding Table (MAC Extension)
Neighbor
MAC/PHY
192.168.0.2
Secondary
Neighbor
MAC/PHY
192.168.0.2
Default
192.168.0.4
Secondary
192.168.0.3
192.168.0.1
192.168.0.4
Cluster 1
Cluster 2
Neighbor
MAC/PHY
192.168.0.3
Secondary
192.168.0.2
Neighbor
MAC/PHY
192.168.0.1
Secondary
192.168.0.3
Default
IP
MAC Extension
Default
MAC/PHY

An IP packet will be forwarded to default or
Secondary MAC/PHY according to the forwarding
table in the MAC Extension layer.
Secondary
MAC/PHY
Example – 10 x 10 Grid
Cluster-Slave
Cluster-Head


Bits
Transmission
range = 2 d
d: neighboring
distance
2
6
8
Status Channel
Number of Uncovered
Neighboring Nodes
00
Uncovered
01
Cluster Head
10
Cluster Member
Simulation Topology








Random, Local, and
Saturate Traffic
10 x 10 Grid
802.11 b 1Mbps
3 orthogonal channels
Path Loss Exponent = 3
Packet Size =1024 Bytes
Dash Circle: Cluster
Dark node: Cluster-Head
B1
0
10
B3
20
B4
30
B5
40
B6
50
B7
60
B8
70
B9
80
B10
90
1
11
21
31
41
51
61
71
81
91
2
12
22
32
42
52
62
72
82
92
3
13
23
33
43
53
63
73
83
93
4
14
24
34
44
54
64
74
84
94
A1 5
C1
B2
A2
15
A3
25
A4
35
A5
45
A6
55
A7
65
A8
75
A9
85
A10
95
6
16
26
36
46
56
66
76
86
96
7
17
27
37
47
57
67
77
87
97
8
18
28
38
48
58
68
78
88
99
9
C2
19
C3
29
C4
39
Channel 1
C5
49
C6
59
C7
69
C8
Channel 2
79
C9
89
C10
99
Tracing One-Hop Aggregate
Throughput
9M
Data Rate = 1Mbps
Packet Size = 1024 Bytes
Path Loss Exponent = 3
8M
Throughput (bps)
7M
6M
Clustering Multi-Channel and Two-Radio Architecture
5M
4M
3M
2M
Traditional Single-Channel and Single-Radio Mesh
1M
0
0
100
200
300
400
500
Time (sec.)

The new multi-channel and two radio architecture
achieves 3X performance, compared to a traditional
single-channel and single-radio mesh.
Throughput Distribution
One-Hop Throughput (bps)
100000
C1
B1 B2
C2
B3
C3
B4
C4
B5
C5
B6
C9 C10
B10
C8
B9
C6
B7
C7
B8
10000
A10
A1
A9
A2
1000
A8
A7
A4
A3
A5
A6
Clustering Multi-Channel and Two-Radio Mesh
Traditional Single-Channel and Single-Radio Mesh
100
0
100
200
300
400
500
600
700
Link


Location-dependent fairness problem : Links Ai experience worse
interference environment than links Bi and Ci, leading to the oscillation
of the throughput distribution.
Future Work: How Physical Carrier Sensing could mitigate the location
dependent fairness problem?
200m x 200m 100 nodes
Random Topology
Performance Comparison in
Random Topology
10M
9M
One-Hop Throughput (bps)
100000
Throughput (bps)
8M
Clustering Multi-Channel and Two-Radio Architecture
7M
6M
Traditional Single-Channel and Single-Radio Mesh
5M
4M
3M
Data Rate = 1Mbps
Packet Size = 1024 Bytes
Path Loss Exponent = 3
2M
1M
10000
1000
100
Clustering Multi-Channel and Two-Radio Mesh
Traditional Single-Channel and Single-Radio Mesh
0
0
100
200
300
400
500
100
Time (sec.)
a) Tracing Aggregate Throughput

Performance gain of aggregate throughput is almost 3x (10Mbps vs. 3.5Mbps)
200
300
Link
b) Throughput Distribution
400