Opportunistic Random Access in CSMA/CA-Based Wireless Networks
by
Jagadeesh Balasubramani
A thesis submitted to the Graduate Faculty of
Auburn University
in partial ful llment of the
requirements for the Degree of
Master of Science
Auburn, Alabama
Dec 14, 2013
Keywords: IEEE 802.11, CSMA/CA, Contention Window, back-o time
Copyright 2013 by Jagadeesh Balasubramani
Approved by
Saad Biaz, Co-Chair, Professor of Computer Science and Software Engineering
Alvin Lim, Professor of Computer Science and Software Engineering
David Umphress, Chair, Professor of Computer Science and Software Engineering
Abstract
IEEE 802.11 MAC based CSMA/CA (Carrier Sense Multiple Access with Collision
Avoidance) is the most widely used protocol in wireless networks. In CSMA/CA, every
node listens to the shared wireless medium and transmits only when the channel is sensed
idle to avoid possible collisions. CSMA/CA allows each user of equal probability in access-
ing wireless channel, which incurs equal throughput in long term regardless of the channel
conditions. To exploit user diversity that refers to the di erence of channel condition among
users, we proposed three opportunistic random access mechanisms: overlapped contention,
segmented contention and normal distribution based contention, to favor the user of best
channel condition in channel access. In the overlapped contention, the contention windows
of all users share the same ground of zero, but have di erent upper bounds upon channel
condition. In the segmented contention, the contention window upper bound of a better
channel condition is smaller than the lower bound of a worse channel condition; namely,
their contention windows are segmented without any overlapping. In the normal distribu-
tion based contention, the back-o interval is determined using normal distribution with the
expectation of proper mean and standard deviation value within the contention window.
These algorithms are also enhanced to provide temporal fairness and avoid starving the
users with poor channel conditions. The proposed mechanisms are implemented and eval-
uated in the NS3 simulator. Extensive experiments show that the proposed opportunistic
random access schemes can signi cantly improve the network performance in throughput,
delay, and jitter over the current CSMA/CA in IEEE 802.11 networks. In particular, the
overlapped contention scheme can o er 73.3% and 37.5% throughput improvements in the
infrastructure-based and ad-hoc networks, respectively.
ii
Acknowledgments
I take this opportunity to thank all those who helped me and guided me throughput
this thesis. Most importantly, I would like to express my utmost gratitude and everlasting
thanks to my advisor, Dr.Saad Biaz for his invaluable advice, insight and critical reviews
throughout this research. Without his support and guidance, this thesis would not have
been possible. I also express my deep sense of gratitude and sincere thanks to Dr.Shaoen
Wu, Assistant Professor, School of Computing, University Of Southern Mississippi for his
advice, support and guidance right from the beginning of my thesis. I consider it as a special
privilege to convey my prodigious and sincere thanks to Dr.David Umphress and Dr.Alvin
Lim for serving on my advisory committee and all the advice, guidance and support given
to me for my thesis work. With immense pleasure and satisfaction, I express my sincere
thanks to all my friends and family members for their kind help and unstinted co-operation
and companionship during my thesis work. I also thank and praise the almighty god for
giving me strength, courage, guidance, wisdom and knowledge to complete this thesis work
successfully.
iii
Table of Contents
Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii
Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi
List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 An Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Objective of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Organization of this work . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2 Literature Review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.1 Overview of CSMA/CA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.1.1 Binary Exponential Back-o Scheme . . . . . . . . . . . . . . . . . . 4
2.2 Opportunistic Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.3 Opportunistic Transmission . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.4 Opportunistic Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3 Problem Statement and Motivation . . . . . . . . . . . . . . . . . . . . . 10
3.1 Impact of Access on Network Performance . . . . . . . . . . . . . . . . . . . 10
3.2 Equal Probability Access in CSMA/CA . . . . . . . . . . . . . . . . . . . . . 10
3.3 Opportunistic Transmission vs. Opportunistic Access . . . . . . . . . . . . . 11
4 Design of Opportunistic Random Access . . . . . . . . . . . . . . . . . 13
4.1 Contention Window Based Opportunistic Access . . . . . . . . . . . . . . . . 13
4.1.1 Overlapped Contention . . . . . . . . . . . . . . . . . . . . . . . . . . 13
4.1.2 Segmented Contention . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4.1.3 Comparison between Segmented and Overlapped Opportunistic Accesses 17
iv
4.1.4 Normal Distribution Based Back-o Selection . . . . . . . . . . . . . 18
4.2 Temporal Fairness to Avoid Starvation . . . . . . . . . . . . . . . . . . . . . 19
5 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
5.1 Evaluation with Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
5.1.1 Triple-node Infrastructure Topology . . . . . . . . . . . . . . . . . . . 22
5.1.2 Discussion on Opportunistic Access Algorithms : . . . . . . . . . . . 26
5.2 Impact of Hidden Terminal Problem . . . . . . . . . . . . . . . . . . . . . . 27
5.2.1 With RTSCTS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
5.3 Comparison with Opportunistic Transmission under Mobility and Auto Rate 30
5.3.1 High Performance of Opportunistic transmission over Opportunistic
access . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
5.3.2 Fairness Index Measurement . . . . . . . . . . . . . . . . . . . . . . . 33
5.4 Multi-hop Mesh Topology . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
5.5 Discussion on Issues with Opportunistic Access . . . . . . . . . . . . . . . . 36
5.5.1 Performance Outage in Chain Topology . . . . . . . . . . . . . . . . . 37
5.6 Random Adhoc topology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
5.6.1 Increased Collision . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
5.6.2 Opportunistic Access and Transmission . . . . . . . . . . . . . . . . . 40
6 Concluding remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
v
List of Figures
4.1 Illustration of Contention Window . . . . . . . . . . . . . . . . . . . . . . . . . 14
4.2 Normal Distribution Back-o . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
5.1 Throughput . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
5.2 Average Delay . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
5.3 Tra c Rate Vs Delay . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
5.4 Average Jitter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
5.5 Average Backo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
5.6 Hidden Terminal Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
5.7 Hidden Terminal Problem with RTSCTS . . . . . . . . . . . . . . . . . . . . . . 30
5.8 Packet Loss Ratio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
5.9 Packet Loss Ratio with RTSCTS . . . . . . . . . . . . . . . . . . . . . . . . . . 32
5.10 Illustration of Hidden Terminal topology . . . . . . . . . . . . . . . . . . . . . . 33
5.11 Mobility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
5.12 No Mobility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
5.13 Fairness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
vi
5.14 Multi-hop Mesh Topology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
5.15 Four Chain Topologies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
5.16 Throughput in Chain Topologies . . . . . . . . . . . . . . . . . . . . . . . . . . 39
5.17 Random Adhoc Topology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
vii
List of Tables
5.1 Parameters used for Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
viii
Chapter 1
Introduction
1.1 An Overview
Carrier sensing multiple access/collision avoidance (CSMA/CA) is widely used in many
wireless networks as it can reduce potential collisions and, thereby, improve the overall net-
work performance. It allows each user of equal probability in accessing wireless channel,
which incurs equal throughput in long term regardless of the channel conditions. An inter-
esting question arises: can network throughput be improved if users with temporally better
channel conditions have higher chances in accessing wireless media? If users channels oscil-
late between good and poor conditions, which is a common phenomena observed in wireless
networks, the fairness among di erent users of channel accessing is still assured. The sig-
nal transmitted on a wireless channel may reach the destination directly (line of sight) or
through multiple re ections on local scatterers (buildings, mountains, etc.). As a result,
wireless channel conditions are a ected by multiple random attenuations and delays. More-
over, the mobility of users or scattering environment may cause these random  uctuations
to vary with time. In wireless networks, the channel conditions are determined by many
factors such as fading, mobility, shadowing and location. Therefore, wireless users often
experience di erent channel conditions, which are referred as spatial diversity or user diver-
sity in wireless communication. Due to the spatial diversity, a wireless user with excellent
channel condition may be able to transmit data at the highest bit rate while others with
poor links may not be able to transmit any data even at the lowest rate. Channel condition
variations also lead to time diversity: a user may have a link of high bit rate now, but may
have to use a low rate thereafter. The user diversity of channel conditions is often considered
1
detrimental in traditional wireless communication systems because it is unpredictable and
thus each user is treated with no di erence. In recent years, opportunistic approaches have
been attempted to exploit the inherent randomness of wireless channel to improve wireless
network performance and utilization, including opportunistic rate adaptation, transmission,
scheduling and routing. Opportunistic protocols exploit user diversity by granting higher
priority to users with good channel conditions and/or time diversity by extending the use of
channel in good conditions. Unlike the above-mentioned opportunistic transmission schemes,
we propose and evaluate three opportunistic access schemes that exploit user diversity in
the CSMA/CA. These schemes enable the user with the best channel condition to have the
largest probability of accessing the shared channel, but do not starve the users with poor
links. In the long run, each user probably obtains a throughput proportional to its channel
conditions.
1.2 Objective of the Thesis
The main contributions and objectives of this work consist of:
 propose three distributed opportunistic random access variants for wireless networks,
 theoretical analysis of their opportunism and
 the implementation of the proposed algorithms in NS3- simulator.
1.3 Organization of this work
The rest of this thesis is organized as follows.
 Chapter 2 (Literature Review) provides details about the CSMA/CA mechanisms and
related opportunistic access schemes are brie y reviewed.
 Chapter 3 (Problem Statement and Motivation) presents the problems that motivates
this work.
2
 Chapter 4 (Design of Opportunistic Random Access) discusses about the design of three
proposed opportunistic random access variants and also analyzes the opportunism of
the proposed schemes.
 Chapter 5 (Performance Evaluation) presents the experiment settings, implementation
details and the performance evaluation of the proposed schemes in the NS-3 simulator.
 Chapter 6  nally concludes this thesis.
3
Chapter 2
Literature Review
2.1 Overview of CSMA/CA
Many wireless networks such as IEEE 802.11 adopt CSMA/CA [4] as the core media
access mechanism. The opportunistic algorithms proposed in this work are therefore based
on this mechanism. CSMA/CA is a contention-based MAC protocol. In a typical CSMA/CA
network, regardless of ad-hoc or infrastructure mode, all nodes that have data to transmit
on the shared wireless link must undergo a contention procedure  rst. Only the node that
wins the contention can transmit while all others freeze the contention procedure until the
winner completes its transmission.
2.1.1 Binary Exponential Back-o Scheme
The contention is regulated by a binary exponential back-o process in which each node
maintains a contention window that has a lower bound of 0 and an upper bound that starts
with an initial value and may exponentially increase when network becomes congested. Then,
a node that is ready to transmit randomly selects a back-o value Tb from the contention
window using a uniform distribution. The node will keep sensing the channel.
If the channel is busy, the back-o value is frozen until the channel becomes idle. Oth-
erwise, it is decremented by one at every (idle) time slot. When the back-o value reaches
0, the node starts its transmission. If the transmission fails, the current contention window
upper-bound is doubled unless it has reached the maximum. Then another back-o proce-
dure is repeated with the updated contention window. Although this back-o was created
4
to avoid possible collisions from simultaneous transmissions from multiple nodes, it actually
also regulates the likelihood of channel access using the size of the back-o interval.
Normally the value of back-o interval is selected within the default contention window
and the contention window size varies depending upon the IEEE 802.11 MAC protocols.
Without opportunism on random access protocols, all nodes have equal initial contention
window regardless of their channel conditions. Therefore, they have an equal probability
of selecting a back-o interval and win the channel in contention. For example, in IEEE
802.11g, the initial contention window size is 15 and each node selects a value from 0-15 as
its back-o interval in uniform distribution. If a node consecutively losses the contention,
its contention window size exponentially or linearly increases to avoid further collisions.
Although CSMA/CA has been used widely in wireless networks, it also has hidden
terminal problem if multiple stations cannot hear each other. This is due to di erences in
transmitting power, receiver sensitivity, as well as distance and location with respect to each
other. This issue can be avoided considerable by sending RTS (Request to Send) and CTS
(Clear to Send) frames but still the network performance is not achieved similar to the one
enjoyed in normal wireless networks in which nodes can hear each other. This is because
RTS-CTS frame tend to use the channel resource and it is an extra overhead to the wireless
channel utilization.
Many attempts has been made to improve the resource utilization and performance of
wireless networks. Some of the works related to our opportunistic access scheme are discussed
below:
2.2 Opportunistic Scheduling
An opportunistic CSMA/CA was proposed by Hwang and Cio [24], which targets the
user diversity in WLAN. Their algorithm schedules a node to transmit at a speci c time
slot according to the signal-to-noise-ratio (SNR) of its channel. To avoid the nodes with the
same SNR to collide with each other on the same time slot, a random number is introduced
5
when the time slot is determined. These algorithms prioritize the users having high signal
to noise ratio to gain earlier channel access.
Zhai et al. [21], [11] proposed an opportunistic media access control protocol that
focused on the opportunistic scheduling of tra c at a node to its neighbors based on their
channel conditions. The tra c to the neighbor with the best channel conditions is scheduled
 rst for transmission. This protocol takes advantage of both multi-user diversity and rate
adaptation techniques.
Qin and Berry [27] proposed an media access protocol to enable the user to transmit
opportunistically when stations have favorable channel conditions without the use of a cen-
tralized scheduler. Each user measures the current channel conditions using the pilot signal
broadcasted by the base station. This distributed approach to identify channel conditions
adaptively scales up as the number of users increases and considerably reduces the overall
round trip time of the frames.
2.3 Opportunistic Transmission
Opportunistic transmission based on multiple rates was demonstrated to yield a signif-
icant improvement of the network performance in IEEE 802.11 networks [1], [2], [3] where a
node opportunistically transmits multiple frames if its bit rate is high, instead of tradition-
ally one frame. These algorithms rely on rate adaptations such as RBAR [5] to estimate the
channel conditions in terms of bit rate and then a sender calculates the number of frames
that should be transmitted based on the adapted bit rate to maintain temporal fairness
among nodes.
For example, opportunistic auto rate (OAR) protocol exploits time diversity to op-
portunistically send multiple back-to-back data packets whenever they have better channel
quality. This is achieved by using the fragmentation mechanism of IEEE 802.11. If the
channel conditions of a particular user are measured at a data rate above the base rate, the
more fragments  ag in the frame control  eld of MAC header is enabled by the sender until
6
transmission rate divided by base rate number of packets are transmitted. The sender also
needs to set the fragment number to zero in the sequence control  eld of MAC header to
make sure that the transmitted frames are a data packet.
On the other hand, a multi-channel opportunistic auto rate media access protocol
(MOAR) exploits frequency diversity (in the form of multiple frequency channels) to op-
portunistically select a better quality frequency channel to transmit data at high bit rates if
the signal to noise ratio on the existing channel is not good.
These opportunistic transmission protocols occur after the contention of channel access
that is still conducted with traditional non opportunistic approach: equal probability access.
It exploits the time diversity and frequency diversity of a node, not the user diversity of a
network.
Xin, Edwin and Ness [28] proposed an opportunistic transmission scheduling protocol
exploiting time diversity of scarce wireless channel conditions to improve the network per-
formance under a certain stochastic resource allocation constraint. This protocol assigns
each user a number between 0 and 1 to represent the long-term fraction of time assignments
to the user. With the resource allocation constraint and fairness constraint, a scheduling
scheme that maximizes the channel utilization is proposed to determine which user should
be scheduled to transmit at every time slot such that the network performance is optimized.
IEEE 802.11e [7] categorizes network tra c into various types and speci es di erent
contention window size for each tra c type such that the highest priority tra c type such
as real time video/audio is assigned in smallest size. In this way, the higher priority tra c
has a chance to be delivered before lowest priority tra c types.
Vaidya [22], [23] proposed to dynamically vary the contention window to achieve the
distributed proportional scheduling in IEEE 802.11 WLANs. Based on the weight assigned
to each tra c  ow, the contention window is calculated such that a more weighted  ow
has a smaller contention window. Then, the  ow has more chances to use the channel for
delivering more data than less weighted  ows. Unlike opportunistic transmission taking
7
advantage of time diversity due to the temporal dynamic characteristics of the wireless
channel, opportunistic access exploits user diversity in wireless networks. In opportunistic
transmission, after a node wins the contention, it tries to transmit aggressively while its
channel remains good because the condition may degrade later.
In CSMA/CA, a node only transmits one frame when it wins the channel while in op-
portunistic transmission schemes such as OAR [1] and MOAR [3], more than one frame may
be transmitted when a node wins access. The number of frames to be transmitted is deter-
mined by the channel conditions. In OAR and MOAR, the number of frames transmitted
after a node wins the contention is calculated as the ratio of current bit rate over the basic
rate.
2.4 Opportunistic Routing
Opportunistic Adaptive Routing protocol [25] focuses on multiple simultaneous  ows
in wireless mesh networks by 1) Exploiting path diversity to select the forwarding path
opportunistically; 2) prioritize time-based forwarding to favor the user with best forwarding
path and 3) adaptively determine the sending rate based on the current channel conditions.
kai and Zhenyu [26] proposed an opportunistic routing protocol for multi-channel multi-
radio multi-hop wireless networks. This protocol focuses on the co-channel interference and
the tradeo between multiplexing and spatial diversity. The forwarding candidate selection
is achieved opportunistically using linear programming approach to improve the network
performance.
Petar and Hiroyuki [29] proposed an opportunistic scheduling for wireless network cod-
ing which takes advantage of multiple fading due to time diversity between the relay and the
destination nodes. A relay node can combine many packets into a single packet and broad-
casted to di erent receivers. Each receiver extracts the desired packet from the network codes
packet thus reducing the number of transmissions. The relay is scheduled opportunistically
to transmit network-coded packets based on the instantaneous channel conditions intended
8
for di erent receivers. It takes advantage of both network coding and opportunistic schedul-
ing in a wireless multi-hop network to improve the network performance. Therefore, various
mechanisms have been proposed to opportunistically transmits frames depending upon the
current channel conditions.
These observations motivates me to work on providing opportunism on the contention
window mechanisms of binary exponential back-o schemes which are discussed in the fol-
lowing sections.
9
Chapter 3
Problem Statement and Motivation
The motivation of this work is to exploit user diversity in random access wireless net-
works. This motivation stems from a few observations as described below.
3.1 Impact of Access on Network Performance
The access mechanism in a wireless network with user diversity has signi cant impact
on the network performance and channel utilization. Let us examine a network with a base
station and two client nodes: A and B. Suppose A has poor channel conditions supporting a
bit rate of Rl and B has good channel conditions supporting a bit rate of Rh. In one extreme
case where only A has the access to the channel, the network throughput is A?s bit rate Rl
assuming no packet failure. In the other extreme case where only B uses the channel, the
network throughput is B?s bit rate Rh. Otherwise, if A and B share the channel, the network
throughput will be some value between Rl and Rh. Namely, Rh and Rl are respectively the
upper and lower bounds of the network throughput. Therefore, to improve the network
throughput and channel utilization, B should be favored for accessing the channel, which is
referred as opportunistic access.
3.2 Equal Probability Access in CSMA/CA
From the brief review of CSMA/CA in Section 2.1, regardless of the channel conditions,
all nodes probabilistically have equal opportunities to access the channel because they uni-
formly select the back-o value from the same initial contention windows. In a two-node
network with CSMA/CA, a node A with poor channel condition may beat the node B with
10
good channel condition because both nodes have equal probability in channel access. How-
ever, intuitively and from the discussion in the last section (Section 3.1), it is more bene cial
to allow B to transmit under these conditions for two reasons. First, B would use the wire-
less channel more e ciently because it takes less time in transmitting the same amount of
data at a higher bit rate than A. This opportunism can lead to higher utilization, e ciency,
and throughput of the overall network. Second, because of the inherent temporal variations
of the wireless channel, B with presently good channel conditions may not keep as good
when it wins the channel later.
3.3 Opportunistic Transmission vs. Opportunistic Access
Unlike opportunistic access that exploits user diversity in wireless networks, opportunis-
tic transmission takes advantage of time diversity due to the temporal dynamic characteris-
tics of the wireless channel. In opportunistic transmission, after a node wins the contention,
it tries to transmit aggressively while its channel remains good because the condition may
degrade later. In CSMA/CA, a node only transmits one frame when it wins the channel
while in opportunistic transmission schemes such as OAR [1] and MOAR [3], more than one
frame may be transmitted when a node wins access. The number of frames to be transmit-
ted is determined by the channel conditions. In OAR and MOAR, the number of frames
transmitted after a node wins the contention is calculated as the ratio of current bit rate
over the basic rate. For example, if the current bit rate of a node is 11 Mbps and the basic
rate is 2 Mbps, then the ratio should be b11/2c = 5, so the node will transmits  ve pack-
ets before the channel is released for contention. Each communication cycle in the random
access wireless networks can actually be considered as two phases: access (contention) fol-
lowed by transmission. From the above discussion, opportunistic transmission focuses on the
transmission phase but not the access phase. Although opportunistic transmission improves
the network performance by exploiting time diversity, it does not guarantee the node with
the best channel condition has the best chance to win the channel. However, the node with
11
the best channel conditions deserves the chance to use the channel because its channel may
degrade later. To improve the utilization of scarce wireless resources, we are motivated to
design opportunistic access algorithms that grant the channel in probability to the node that
has the best channel condition, namely that is most likely to generate the largest instan-
taneous network throughput. With the observations discussed above, to improve network
e ciency and channel utilization, we are motivated to design distributed opportunistic ac-
cess algorithms that probabilistically favor the users with best channel conditions in winning
the channel contention.
12
Chapter 4
Design of Opportunistic Random Access
To achieve opportunistic random access, we propose three algorithms based on the con-
tention mechanism in the CSMA/CA. Two of these algorithms target at calculating the
contention window for each node based on its instantaneous channel conditions. The third
algorithm proposes to select a back-o value from the contention window with a normal
distribution, rather than a uniform distribution as in the CSMA/CA. In addition, oppor-
tunistic access inherently tends to starve nodes with poor channel conditions. This section
elaborates on these algorithms and how to address the starvation problem with temporal
fairness.
4.1 Contention Window Based Opportunistic Access
The following two algorithms achieve opportunistic random access by determining con-
tention windows based on channel conditions and are discussed as follows.
4.1.1 Overlapped Contention
In the  rst approach, the contention windows of all nodes share the same lower bound
of \0" as CSMA/CA does, but have di erent initial upper bounds that are determined by
the channel conditions in terms of achievable bit rates. Therefore, the contention windows
of all nodes overlap in ranges as plotted on the left plot in Figure 4.1. The initial upper
bound CW is inversely proportional to the ratio of current achievable bit rate over the basic
bit rate and computed as in Formula 4.1 below whenever a node is ready to contend on the
13
channel for a new transmission.
CW =d  RbR
i
 CWbasee (4.1)
where Ri refers to the current achievable bit rate of a particular node i, Rb denotes the basic
rate in a bit rate set and CWbase is a constant base value, e.g. 15 in IEEE 802.11n. Note
that RbRi may be very small, for example, in IEEE 802.11n, 6:5Mbps600Mbps is almost 0.01. Therefore,
a coe cient,  , is introduced to make sure that the computed window for the highest bit
rate is no less than a certain small value to maintain a random access. From this formula,
intuitively, a high bit rate, namely good channel conditions, leads to a small CW and thereby
a larger probability to win the channel contention with the uniform selection of a back-o 
value from the contention window. Then, the computed CW can be used by the Binary
Exponential Back-o procedure in the CSMA/CA to ful ll the opportunistic access. Note
Figure 4.1: Illustration of Contention Window
14
that, in the Overlapped Contention, a node with low bit rate still has the probability to beat
another node with a high bit rate: the lower rate node still has chance to select a smaller
back-o value because their contention windows have the same lower bound of "0".
Opportunism of Overlapped contention
As discussed above, the overlapped contention is an opportunistic access that assigns
larger probability of wining the channel to the node with higher rate. Denote Pie as the
probability that a node i attempts to transmit a frame. According to [8], with di erent
contention window size, the Pie is calculated as:
Pie = 2CWi
max + 1
(4.2)
where CWmaxi is the contention window size of node i. De ne Pit the successful transmission
probability of node i. Then
Pit = Pie 
Y
j6=i
(1 Pje ) (4.3)
De ne PitPj
t
as the opportunism metric that node i will compete node j in accessing the channel.
Based on Eq. (1), Eq. (2) and Eq. (3), we have
Pit
Pjt =
 (  Rj)
   Rj = 1 +
(  1) 
  Rj (4.4)
where  = RiRj and  =  :CWb:Rb. According to Eq. (1)
 = CWjmaxXRj (4.5)
Because the contention window CWmaxi is always larger than 1, we have  >Rj. Assume
that node i has the largest bit rate Ri in the networks, then we have  > 1 and also PitPj
t
> 1.
15
This clearly shows that the overlapped contention opportunistic access helps those nodes at
higher rates to win the contention.
4.1.2 Segmented Contention
To strictly grant a higher priority of accessing channel to the users with better chan-
nel conditions, another algorithm separates the contention windows for nodes at di erent bit
rates as illustrated on the right of Figure 4.1. In this approach, the initial contention window
is still computed as in Formula 4.1. However, unlike the Overlapped Contention that main-
tains the same lower bound of \0" for all contention windows, this algorithm di erentiates
the lower bounds of the contention window for di erent channel conditions. A higher bit rate
results in an upper bound of the contention window smaller than the lower bound of a node
at a lower bit rate. For example, on the right of Figure 4.1, Wi max and Wi+1 max respectively
denote the computed initial upper bounds of the contention window of bit rate Ri and Ri+1
according to Formula 4.1. Then, the lower bound of the contention window CWi of bit rate
Ri is assigned the value that is larger by one than Wi+1 max, the upper bound of CWi+1, i.e.
the window is [Wi+1 max + 1, Wi max]. This segments the contention of nodes with di erent
channel conditions in that a node at bit rate Ri can never get a back-o value smaller than
a node at bit rate Ri+1. This approach can be considered semi-probabilistic in that (1) the
access of the nodes at the same bit rate is random since they have the same initial window
size to randomly generate a back-o value, but (2) the access of nodes at di erent rates is
deterministically prioritized because the lower rate nodes can never get a smaller back-o 
value than the higher rate nodes. This approach provides a tight opportunism by grouping
nodes with similar channel conditions into the same random access team at the cost of ran-
domness across teams. Note that this approach leads to a signi cant problem: starvation of
nodes with poor conditions. This problem will be addressed in Section 4.2.
16
4.1.3 Comparison between Segmented and Overlapped Opportunistic Accesses
The segmented contention deterministically guarantees that nodes at higher rates will
win the lower rate nodes because the latter can never have chance to obtain a smaller back-
o window than the former. Therefore, the opportunism is deterministically maintained. In
this section, we compare the system performance of segmented and overlapped contentions
while both provide opportunism in access. For comparison, we de ne a system performance
metric  = RE(T
b)
, where R refers to the bit rate of a node that wins the access and E(Tb) is
the expected back-o time slots before transmission. Clearly, larger the value of  , the better
the network performance.  serves as an network e ciency metric to evaluate the system
performance of contention based opportunistic variants. In the segmented contention, nodes
at di erent bit rates do not share the same lower or higher bounds. Refer to the right plot of
Fig. 1. The expectation of back-o for node i becomes E(Tb) = (CWimin +CWimax)=2 where
CWimin is the lower bound of node is contention window, which is also the higher bound of
node i+1. So if node i run the segmented contention algorithm, we have its e ciency metric
as:
 is = 2RiCWi
max +CWi+1max
= 2 (Ri)
2
 (4.6)
where  = "1+" and " = RiRi+1. In the overlapped contention, a node at higher bit rate does not
deterministically beat a lower bit rate node because of the overlapped contention windows.
Consider two nodes i and j having bit rates (Ri >Rj). Denote Pi the probability that node
i wins over j in channel access. Similarly, Pj refers to the probability that node j wins over
i in channel access. Then, Pj and Pi can be calculated as follows:
Pj =
CWiX
x=1
1
CWj:
CWi x
CWi  
CWi
2CWj (4.7)
Pi = CWj CWiCW
j
+ CWiCW
j
CWiX
x=1
1
CWi:
x 1
CWi  1 Pj (4.8)
17
where CWj = CWjmax and CWi = CWimax. Therefore, the e ciency metric of node i with
overlapped contention scheme can be derived as:
 io = Pi: 2RiCW
i
+Pj: 2RjCW
j
(4.9)
By substituting Eq. (1) into Eq. (4) and (5), we can obtain:
 io
 is =
 2 + 2(  1=2
2  3 (4.10)
In this equation, " takes values from [1.1, 2] in 802.11n, then  will be constants falling into
[0.5,0.7]. Therefore, Eq. (6) is a monotonic decreasing function of  . It decreases to 1 when
  1:5 and approaches to 0 hereafter. This means that segmented contention outperforms
overlapped contention when  > 1;5 that happens at the probability of 85% in IEEE 802.11
with rates (13, 26, 39, 52, 78, 104, 117 and 130 Mbps) for 20MHz bandwidth if two nodes
have di erent bit rates.
4.1.4 Normal Distribution Based Back-o Selection
In the Overlapped Contention, although nodes with di erent channel conditions obtain
di erent initial contention windows, each node still uses a uniform distribution to select
the back-o value from its contention window. The third proposed opportunistic access
approach consists of using a normal rather than a uniform distribution, in selecting the
back-o value once the contention window is determined as in the Overlapped Contention.
With the expectation of the normal distribution set to a proper value within the contention
window and a proper standard deviation, a node with higher bit rate has signi cantly greater
probability to obtain a smaller back-o value than a lower bit rate node. Systematically, the
expectation of the normal distribution of a node at rate R is computed as below:
E =dCW2 e (4.11)
18
where CW is computed as in Formula 4.1. Let us examine an example where a network has
Figure 4.2: Normal Distribution Back-o 
two nodes A at rate R and B at rate R2 . Then, the expectations of the normal distribution
at A and B are respectively set as N4 and N2 to select their back-o values as shown in
Figure 4.2. As a result, in the long run, A will select a smaller back-o value than B because
most likely the selected values are near to the expectation in the normal distribution.
4.2 Temporal Fairness to Avoid Starvation
The equal probability access regardless of channel conditions in the CSMA/CA leads to
an anomaly that all nodes will have identical throughputs in the long run [8], which is called
throughput fairness. It is obvious that the nodes at lower bit rate hurt the throughputs of the
nodes at higher bit rates as well as the overall throughput of the network. This fairness is not
19
\fair" in temporal use of the channel among nodes. With the identical throughput, a node at
the lowest bit rate in a network will use the channel for the longest time. On the other hand,
as discussed in Section 3, although opportunistic access can improve the network throughput
by always favoring the users with the best channel conditions, it may starve the users with
poor channel conditions. A solution both problems of identical throughputs and starvation is
to achieve temporal fairness among nodes [19] that is de ned as each node has approximately
the identical amount of time in using channel. To achieve temporal fairness, we propose to
use a bit rate normalized average throughput as a metric in computing the initial contention
window. Each node tracks the average throughput T updated in an exponentially weighted
window tw. Suppose Node K is the transmitter at a certain moment, T is updated at each
node k that has packets ready for transmission in each time slot with a low-pass  lter as:
Tk[m+ 1] =
8
><
>:
(1 1tw ) Tk[m] + 1tw  Rk[m] if k = K
(1 1tw ) Tk[m] if k6= K
The bit rate normalized average throughput for node k having bit rate Rk in the m-th window
is de ned as:
Tnormalized[k;m] = Tk[m]=Rk (4.12)
This is used to compute the initial contention window. As a result, Formula 4.1 is accordingly
updated as:
CW =   Tnormolizd[k;m] CWbase (4.13)
The contention with Formula 4.12 maintains two important features: temporal fairness and
opportunism. The temporal fairness is achieved because the bit rate normalized average
throughput can actually be explained as the temporal quota of a node in transmission period.
This is clear if we rewrite the de nition of Tnormalized[k;m] as (tc Tk[m]=Rk)=tc in a period
of length tc: tc Tk[m] is the average transmitted data in bits and thereby tc Tk[m]=Rk is
the transmission time. Thus, (tc Tk[m]=Rk)=tc is the the percentage of the time that node
20
k gains for transmission in a period of tc. The opportunism in Formula 4.12 is driven by
the bit rate. If a node has a high bit rate, its Tnormalized[k;m] tends to be small. According
to Formula 4.13, a small Tnormalized[k;m] leads to a small contention window CW to win
the channel. If a node uses the channel for too long, it will end up with a large average
throughput Tk[m], thereby a large Tnormalized[k;m] that enlarges its contention window and
decreases its chance to win the channel. Note that the size of the weighted window, tw, is
associated with the latency requirement of applications. If tw is large, it allows the node
with the optimal channel condition to use the channel for a long duration, but may hurt
other nodes having applications requiring low latency. If it is small, the channel is frequently
switched among nodes of di erent bit rates and the overall performance degrades. Another
concern is the support of QoS. If multiple classes of applications are involved, each class
has di erent requirements, especially regarding latency. Then, a weight parameter  c for
each class of application is necessary in updating the average throughput as: Tk[m + 1] =
(1 1tw ) Tk[m] + 1tw    Rk[m]. Then, the basic contention window size CWb for each
packet will be updated according to its priority.
21
Chapter 5
Performance Evaluation
We extensively evaluated the performance of the proposed opportunistic access algo-
rithms with simulation in NS-3.
5.1 Evaluation with Simulation
We developed all three proposed algorithms into the simulator NS3 [30] and comprehen-
sively evaluated the performance with extensive simulations. Our algorithms were compared
with the default CSMA/CA without opportunism for each case. The evaluation began with
a simple infrastructure topology having one access point and two clients, then studied the
impact of hidden terminal on opportunistic access, compared with opportunistic transmis-
sion in the case of mobility, and  nally evaluated the performance on a multiple-hop mesh
network. All experiments were performed with constant bit rate (CBR) UDP tra c at a
rate of 10 Mbps for 5 minutes with packet size of 1K bytes. The results are averaged over 50
runs for each case. In simulations,  in Formula 4.1 was set to 1.7 and the weighted window
tw was set to 50 ms. In the following performance  gures, \Original" represents the default
algorithm in the CSMA/CA, \Overlapped" for the Overlapped Contention, \Segmented" for
the Segmented Contention and \Normal" for the Normal Distribution Based Back-o Selec-
tion. The following table represents the experiment settings for the simulation performed in
NS-3.
5.1.1 Triple-node Infrastructure Topology
We  rst evaluated the throughput and jitter performance of opportunistic access over
the original algorithm in a simple topology: one access point and two client nodes. All nodes
22
Table 5.1: Parameters used for Evaluation
Parameters Values
MAC Protocol IEEE 802.11g
Slot time 20 s
SIFS 10 s
DIFS 50 s
Data rate (6,9,12,18,24,36,48,54) Mbps
CWmin 15
CWmax 1023
were in radio range of each other. These client nodes transmitted packets to the access point
at di erent bit rates. One client node was set to a 54 Mbps, but the other node changed its
bit rate from the IEEE 802.11 rate set consisting of 6, 12, 24, 36, and 48 Mbps.
Throughput Performance :
Figure 5.1 plots the throughput performance when one client changes its bit rate each
time to imitate the changes of channel conditions. The X-axis represents the di erent bit
rates and the Y-axis represents the throughputs of opportunistic access algorithms and the
original one in the CSMA/CA. From the  gure, opportunistic access improves the through-
put by approximately 30 - 100% based on channel conditions as compared to the original
algorithm.
Delay Performance:
Figure 5.2 plots the measured average delay at di erent bit rates The opportunistic
access shows a signi cant improvement in delay as compared to the original access. This is
because the high bit rate nodes in opportunistic access has very less contention time and
transmits packets rapidly. The lower bit rate nodes experiences a much larger delay compar-
atively because of collision due to back-o terminate at the same time and the contention
window size gets doubled every time when it encounters a collision. Yet the overall network
performance in delay is improved signi cantly over the default CSMA/CA method. To show
23
 6
 8
 10
 12
 14
 16
 18
 20
 6  12  24  36  48
Throughput (Mbps)
Bit Rate (Mbps)
Original
Overlapped
Segmented
Normal
Figure 5.1: Throughput
more clearly, we further studied the delay performance with increase in tra c rate Figure 5.3.
As expected, the delay gets increased as CBR tra c rate increases because more packets are
transmitted frequently. Although the variation in individual packet delay between high bit
rate nodes and low bit rate nodes is high, the overall network performance of opportunistic
access is improved.
Jitter Performance :
Figure 5.4 shows the measured jitters at di erent bit rates. Jitter is the delay variation
between two consecutive successful packet receptions and the result plotted is the average of
delay variation of total received packets. Surprisingly, the opportunistic access outperforms
the original one in jitter as well. This is because, with opportunistic access, the high bit rate
nodes obtain much smaller initial contention windows than those in the default CSMA/CA
24
 0.1
 0.2
 0.3
 0.4
 0.5
 0.6
 0.7
 0.8
 0.9
 1
 1.1
 6  12  24  36  48
Average Packet Delay (ms)
Bit Rate (Mbps)
Original
Overlapped
Segmented
Normal
Figure 5.2: Average Delay
and the selected back-o in the contention is thereby signi cantly reduced. As a result,
although lower bit rate nodes experience larger jitters than higher bit rate nodes, the overall
jitter across the network is improved because of the shortened time spent on the contention
with opportunistic access.
Average Back-o Time:
To further investigate how the opportunistic access improves the throughput and jitter,
we collected the back-o time in terms of time slots of each transmission. Figure 5.5 shows the
average back-o time per successful transmission for each access algorithm. Average back-o 
slot time per packet is calculated as the sum of individual packet back-o time slots over the
total number of packets transmitted successfully. From the  gure, the opportunistic access
algorithms consume much less time in back-o than the original access, up to 400% less at 48
25
 0
 200
 400
 600
 800
 1000
 1200
 1400
 1  2  3  5  10  15  20
Average Packet Delay (ms)
CBR Traffic Rate (Mbps)
Original
Overlapped
Segmented
Normal
Figure 5.3: Tra c Rate Vs Delay
Mbps. The overall network performance improves because 1) the equal probability access in
the original algorithm results in almost constant average back-o , and 2) the opportunistic
access algorithms spend less time on back-o , namely contention.
5.1.2 Discussion on Opportunistic Access Algorithms :
Among the proposed three opportunistic access schemes, the Segmented Contention
yields in general the best performance from Figure 5.1 to 5.5. This is because the channel
access of nodes at di erent bit rates is deterministically prioritized when their contention
windows are segmented. Nodes with lower rates never get a smaller back-o value than the
ones with higher bit rates. The Overlapped Contention and the Normal Distribution Based
Back-o result in almost identical performance. This is because both of them have a similar
expectation in selecting back-o values for the nodes at the same bit rate. Because they both
26
 0.2
 0.4
 0.6
 0.8
 1
 1.2
 1.4
 1.6
 1.8
 2
 2.2
 6  12  24  36  48
Average Jitter (ms)
Bit Rate (Mbps)
Original
Overlapped
Segmented
Normal
Figure 5.4: Average Jitter
have contention windows starting at \0", the higher bit rate nodes may still be occasionally
beaten by nodes at lower bit rates.
5.2 Impact of Hidden Terminal Problem
In this case, the network was con gured to still have one access point and two client
nodes with one at 54 Mbps and the other varying its bit rate, but the clients do not hear each
other. RTS and CTS are disabled to fully stimulate the hidden terminal problem. Figure
5.10 illustrates the hidden terminal scenario in wireless networks. Node A and H are the
client nodes and node B is the access point. Node A and H cannot hear each other because
they are not in radio range but they can hear node B. If node A and H transmit frames, it will
sense the channel  rst but cannot hear the frames from nodes hidden to each other. So both
nodes attempt to transmit simultaneously and results in collisions which reduces the network
27
 2
 3
 4
 5
 6
 7
 8
 9
 10
 11
 6  12  24  36  48
Average Back-off (Ts)
Bit Rate (Mbps)
Original
Overlapped
Segmented
Normal
Figure 5.5: Average Backo 
performance drastically. Our opportunistic access schemes also have this hidden terminal
e ect but it has the probability of transmitting more frames over the traditional 802.11
MAC protocols and hence improve the network performance considerably. The performance
results are discussed as follows: Figure 5.6 plots the measured throughputs at di erent rates.
The hidden terminal problem does hurt the performance of all algorithms. The  gure tells
that the overall network throughput is still improved by the opportunistic access, although
the improvement is reduced to some degree by the hidden terminal problem. To show more
clearly the e ect of hidden terminal, we further studied the percentage of packet loss ratio of
the network. Packet loss ratio percentage is the di erence between total transmitted packets
and total received packets over the total number of transmitted packets. Figure 5.8 shows
that packet loss ratio is considerably reduced in opportunistic access which explains the
performance improvement of opportunistic access as compared to the original access.
28
 6
 7
 8
 9
 10
 11
 12
 13
 6  12  24  36  48
Throughput (Mbps)
Bit Rate (Mbps)
Original
Overlapped
Segmented
Normal
Figure 5.6: Hidden Terminal Problem
5.2.1 With RTSCTS
Although opportunistic access performs better than original one, the measured through-
put performance is mainly due to high bit rate nodes in the presence of hidden terminal. This
is because the high bit rate nodes win the channel more frequently due to its initial smaller
contention window size, suppressing the channel access to lower bit rate nodes. Hence the
channel should be reserved by nodes before its access to provide the fairness among the nodes.
We have enabled the RTS/CTS reservation technique for this purpose. As expected, the op-
portunistic access outperforms the original one in throughput as shown in Figure 5.7 and
gives the throughput proportional to its bit rates because of channel reservation technique
and long term temporal fairness provided by our scheme. The packet loss ratio of our scheme
is also considerably reduced in the presence of RTS/CTS channel reservation technique as
29
 5
 6
 7
 8
 9
 10
 11
 12
 13
 14
 15
 6  12  24  36  48
Throughput (Mbps)
Bit Rate (Mbps)
Original
Overlapped
Segmented
Normal
Figure 5.7: Hidden Terminal Problem with RTSCTS
shown in Figure 5.9 which increases the overall network performance of opportunistic access.
5.3 Comparison with Opportunistic Transmission under Mobility and Auto
Rate
We also evaluated the performance in an infrastructure topology of multiple  ows with
mobility. We tested topologies with a di erent number of nodes varying from 2 to 6 nodes
with one  ow between each node and the access point. The maximum transmission range
of a node was set to 30m and mobility was enabled such that each node would be moving
randomly within the bounded area of 50m 50m at a speed of 5 m/s. The nodes sometimes
move out of range and packet losses occur more frequently. Because of mobility, the sup-
ported bit rate has to be dynamically adapted. RRAA [20] rate adaptation algorithm was
30
 30
 35
 40
 45
 50
 55
 60
 65
 70
 75
 6  12  24  36  48
Packet Loss Ratio (%)
Bit Rate (Mbps)
Original
Overlapped
Segmented
Normal
Figure 5.8: Packet Loss Ratio
enabled for this purpose. In addition, we also implemented Opportunistic Auto Rate (OAR)
protocol as a representative of opportunistic transmission algorithms to compare with the
opportunistic access in this experiment setting. Figure 5.11 shows the throughput perfor-
mance of the opportunistic access algorithms, the original access and OAR with mobility
and RRAA in the case of multiple  ows. The X-axis represents the number of  ows and the
Y-axis represents the throughput for the entire network. From the  gure, the opportunistic
access (our algorithms) and the opportunistic transmission (OAR) have close performance
when the network only has a couple of nodes, but the opportunistic access gradually out-
performs the opportunistic transmission as the number of mobile nodes increases. This is
because of the di erence in the opportunism between access and transmission. With the
growing number of mobile users, the user diversity increases as well. OAR does not exploit
user diversity and it uniformly selects a user to transmit. As a result, it does not favor the
31
 30
 35
 40
 45
 50
 55
 60
 65
 70
 75
 6  12  24  36  48
Packet Loss Ratio (%)
Bit Rate (Mbps)
Original
Overlapped
Segmented
Normal
Figure 5.9: Packet Loss Ratio with RTSCTS
user with the best channel condition to use the channel each time. On the contrary, oppor-
tunistic access exploits user diversity. With more users, it is more likely that someone is at a
very high bit rate. Because the opportunistic access always favors the user with the highest
bit rate to use the channel, the overall network performance is improved. In addition, in
this environment, the mobility and rate adaptation introduce fast channel variations. This
may result in transmission failure when OAR opportunistically transmits a burst of frames
if the channel degrades before the opportunistic transmission  nishes. However, because the
opportunistic access only transmits one frame per contention, its short transmission time is
resilient to the fast variations. Moreover, the variations generate new user diversity in the
network that facilities the opportunistic access to exploit for high network performance. The
performance  gure also shows that the overall throughput increases slowly when the number
of  ows grows because of the increasing contention among the  ows.
32
Figure 5.10: Illustration of Hidden Terminal topology
5.3.1 High Performance of Opportunistic transmission over Opportunistic ac-
cess
In this case, the network is still con gured with infra-structure topology of multiple
 ows but without mobility and auto rate algorithms. The number of  ows is increased
from 2 to 6 by gradually adding one node each time. All nodes transmit packets to the
access point. Because of stable channel conditions and less network overhead, opportunistic
transmission OAR protocol transmits multiple frames when it gains access to the channel
whereas opportunistic access relies on one frame transmission per contention and network
overhead is more comparatively. Although OAR protocol shows a high performance over
opportunistic access scheme as shown in Figure 5.12, opportunistic access shows a better
performance than default CSMA/CA method.
5.3.2 Fairness Index Measurement
Jain Fairness Index is the most commonly used metric to measure the fairness variation
using the individual  ow throughput over wireless networks. Basically Jain Fairness rates the
individual throughput variation with respect to number of  ows. If resources are allocated
equally, then Jain fairness index will have the maximum value 1 and vice-versa. Jain Fairness
33
 7
 7.5
 8
 8.5
 9
 9.5
 10
 10.5
 11
 11.5
 12
 12.5
 2  3  4  5  6
Throughput (Mbps)
Number Of Flows
Original
Overlapped
Segmented
Normal
OAR
Figure 5.11: Mobility
Index is given by
IJ = (
Pn
i=1ri)
2
nPni=1r2i (5.1)
Where ri and n are the allocated resources to user i and the total number of users respectively.
Figure 5.13 shows that the fairness of opportunistic access scheme gets increased as the
number of  ows increases. This is because the opportunistic access actually reduces the
contention time of high bit rate nodes, thereby giving opportunism to send more packets but
the lower bit rate node remain in its regular channel access time. The fairness of opportunistic
transmission is also compared with opportunistic access which shows that the resources are
allocated equally over the long term.
34
 0
 2
 4
 6
 8
 10
 12
 14
 16
 18
 2  3  4  5  6
Throughput (Mbps)
Number of Flows
Original
Overlapped
Segmented
Normal
OAR
Figure 5.12: No Mobility
5.4 Multi-hop Mesh Topology
In this scenario, 30 nodes were randomly and statically distributed in a 150m 150m area
and bit rates (12, 24, 36, 48, 54 Mbps) were assigned to the hops in a uniform distribution.
Since the radio range was 30 m, these nodes form a multi-hop mesh network. Source and
destination pairs of  ows were preselected among the nodes and the number of  ows was
increased from 1 to 9. OLSR [32] protocol was used to route the packets over the network.
The network throughput performance is plotted in Figure 5.14. The opportunistic access
shows an average throughput improvement of up to 40% over the original access. This is
because the original access takes the same initial contention window upper bound regardless
of bit rates, but the opportunistic access obtains a smaller initial contention window upper
bound than that in the original access if the bit rate is larger than the basic rate. As a
result, the opportunistic access spends less overhead time on contention than the original
35
 0.2
 0.4
 0.6
 0.8
 1
 1.2
 2  3  4  5  6
Fairness Index
Number of Flows
Original
Overlapped
Segmented
Normal
OAR
Figure 5.13: Fairness
access if the channel condition for the single  ow is good. As the number of  ows grows,
the throughputs decrease because of the increased collisions among  ows. The Overlapped
Contention and the original access boost their throughputs in the case of 9  ows because
their uniform selection of back-o from overlapping contention windows helps dilute the
collision.
5.5 Discussion on Issues with Opportunistic Access
This section presents some issues with opportunistic access as observed during the per-
formance evaluation. We also brie y discuss the tradeo between the opportunistic trans-
mission and access.
36
 1
 1.5
 2
 2.5
 3
 3.5
 4
 4.5
 5
 1  3  5  7  9
Throughput (Mbps)
Number Of Flows
Original
Overlapped
Segmented
Normal
Figure 5.14: Multi-hop Mesh Topology
5.5.1 Performance Outage in Chain Topology
During the performance evaluation with simulation, we tested a 5-hop chain network
where the sender and receiver were placed at the extremities of the chain with 4 nodes
between. Each node had a bu er of 130 frames. The bit rates of these 5 hops were set in four
di erent patterns as shown in Figure 5.15. Pattern A has ascending bit rates (12, 24, 36, 48,
54 Mbps) along the transmission path, B has descending bit rates (54, 48, 36, 24, 12 Mbps),
C has hybrid ordering with lower rates  rst (12, 24, 54, 36, 48 Mbps), and D has hybrid
ordering with high bit rates  rst (36, 48, 54, 12, 24 Mbps). Figure 5.16 plots the throughput
performance of all algorithms in the four bit rate distribution patterns. From the  gure, the
opportunistic access is signi cantly outperformed by the original access in the decreasing
order case (B) and slightly outperformed in the hybrid order that has high bit rates  rst
(D). This performance outage problem occurs because the opportunistic access transmits
37
Figure 5.15: Four Chain Topologies
more packets in the early hops than what the low bit rate nodes in the downstream hops can
drain out of the network. Therefore, many packets have to be dropped on the intermediate
hops. This problem should exist to some degree whenever the bit rate bottleneck is in the
downstream of a path, but opportunistic access or transmission exacerbates it.
5.6 Random Adhoc topology
In this experiment, we have evaluated the performance of random topology of 50 nodes
placed initially in a random position bounded by 150m 150m area. The bit rates (12, 24,
36, 48, 54 Mbps) were assigned to the nodes in a uniform distribution and the radio range
was 30m. Mobility is enabled such that the nodes are moving at a speed of 5m/sec in a
random direction. Because of mobility, the auto rate algorithm (RRAA) is enabled to adapt
dynamically the channel conditions and reduce loss due to hidden terminal problem. Pre-
selected source and destination are con gured such that the number of  ows are increased
from 1 to 10. OLSR protocol was used to route the packets. The opportunistic access
performance is degraded considerably due to mobility and auto rate as shown in Figure 5.17.
This is because opportunistic access doesn?t give the OLSR protocol enough time to compute
its MPR (Multi-point Relay) and routing table. Opportunistic access injects packets into the
network more frequently due to its less contention time. The position of nodes also changes
randomly over a wider area due to mobility which may sometimes lead to multi-hop routing
38
 0
 0.5
 1
 1.5
 2
 2.5
 3
A B C D
Throughput (Mbps)
Original
Overlapped
Segmented
Normal
Figure 5.16: Throughput in Chain Topologies
of packets to reach the destination. Because of this two reasons, OLSR protocol not able to
build its routing table in less time. So network congestion and packet losses occurs which
leads to degradation in performance.
5.6.1 Increased Collision
In the proposed opportunistic access, high bit rate nodes tend to have small contention
windows. Although the back-o values of these nodes are selected randomly, the initial con-
tention window size for very high bit rate nodes is too small, which increases the probability
for these nodes to select the same back-o value, especially when a network has many such
nodes. Then, this exacerbates the collision because the back-o values at the nodes termi-
nate at the same time. Although the binary exponential back-o mechanism can address this
problem, the network e ciency is degraded with the channel resource wasted by frequent
39
 1.8
 2
 2.2
 2.4
 2.6
 2.8
 3
 3.2
 3.4
 3.6
 1  2  3  4  5  6  7  8  9  10
Throughput (Mbps)
Number Of Flows
Original
Overlapped
Normal
Figure 5.17: Random Adhoc Topology
collisions. The network throughput and delay will be hurt as well. Further e ort is required
to mitigate this problem.
5.6.2 Opportunistic Access and Transmission
Although the performance evaluation showed a case that the opportunistic access out-
performed the opportunistic transmission OAR under fast channel variations due to mobility,
the opportunistic transmission may perform better in some cases. One case is when the user
diversity is light, then the opportunistic access does not make much di erence from the origi-
nal access. Since the opportunistic transmission sends multiple frames per contention period,
it results in average smaller overhead per frame than the opportunistic access. Another pos-
sible case is when the channel is stable enough to sustain the completion of transmitting
multiple frames in the opportunistic transmission.
40
Chapter 6
Concluding remarks
This thesis work proposes three opportunistic random access algorithms to exploit user
diversity in wireless networks. These algorithms probabilistically or semi-deterministically
enable the users to access the shared wireless channel based on their channel conditions such
that the user at the highest achievable bit rate is favored. To avoid starving users with poor
channel conditions, a slow  ltering scheme are proposed to maintain temporal fairness among
nodes. The proposed three opportunistic schemes are also derived and compared analytically
between overlapped contention and segmented contention to prove that our opportunistic
scheme performs better than original CSMA/CA scheme. With extensive experiments on
the NS3 network simulator, it shows that the proposed opportunistic access signi cantly
improves the network performance in throughput, delay, and jitter.
41
Bibliography
[1] B Sadeghi, V Kanodia, A Sabharwal, E Knightly, Opportunistic media access for multi-
rate ad hoc networks, IEEE MobiCom 2002
[2] B. Sadeghi, V. Kanodia, A. Sabharwal, and E. Knightly. OAR: An opportunistic auto-
rate media access protocol for ad hoc networks. Wireless Networks, 11:39-53, 2005
[3] V. Kanodia, A. Sabharwal, and E. Knightly, MOAR: a multi-channel opportunistic auto-
rate media access protocol for ad hoc networks. In proceedings. First International Con-
ference on Broadband Networks 2004
[4] Vaduvur Bharghavan, Alan Demers, Scott Shenker, Lixia Zhang. MACAW: a media
access protocol for wireless LAN?s. SIGCOMM 1994
[5] G. Holland, N. Vaidya, P. Bahl. A rate-adaptive MAC protocol for multi-Hop wireless
networks. MobiCom 2001
[6] IEEE LAN MAN Standards, part 11: Wireless LAN medium access control (mac) and
physical layer (phy) speci cations, March 1999.
[7] IEEE LAN MAN Standards, part 11: Amendment 8: Medium Access Control (MAC)
Quality of Service Enhancements, 2005
[8] Martin Heusse, Franck Rousseau, Gilles Berger-Sabbatel, Andrzej Duda, Performance
Anomaly of 802.11b, Infocom 2003
[9] Vipin M, Srikanth S, Analysis of Open Source Drivers for IEEE 802.11 WLANs, ICWCSC
2010
[10] http://linuxwireless.org/en/users/Drivers/ath9k
42
[11] H. Zhai, Y. Fang, M.C. Yuang, Opportunistic Media Access Control and Rate Adapta-
tion for Wireless Ad Hoc Networks, ICC, 2004
[12] Hiroyuki Yomo, Petar Popovski, Opportunistic Scheduling for Wireless Network Coding,
ICC, 2007
[13] Xiaojun Liu, Edwin K. P. Chong, Ness B. Shro , Opportunistic transmission Scheduling
with resources-sharing constraints in wireless networks, JSAC, vol. 19, no. 10, pp. 2053-
2064, 2001
[14] Yonghe Liu, Edward W. Knightly, Opportunistic Fair Scheduling over Multiple Wireless
Channels, Infocom 2003
[15] Sanjit Biswas, Robert Morris, Opportunistic routing in multi-hop wireless networks,
CCR, vol. 34, no. 1, pp. 69-74, 2004
[16] Sanjit Biswas, Robert Morris, ExOR: Opportunistic multi-hop routing for wireless net-
works, SIGCOMM, 2005
[17] Szymon Chachulski, Michael Jennings, Sachin Katti, Dina Katabi, Trading structure
for randomness in wireless Opportunistic routing, SIGCOMM 2007
[18] Luciana Pelusi, Andrea Passarella, Marco Conti, Opportunistic networking: data for-
warding in disconnected mobile ad hoc networks, IEEE Communications Magazine, vol.
44, no.11, pp. 134-141. 2006
[19] Godfrey Tan, John V. Guttag. Time-based Fairness Improves Performance in Multi-
Rate WLANs. USENIX 2004
[20] Starsky H. Y. Wong, Hao Yang, Songwu Lu, and Vaduvur Bharghavan. \Robust rate
adaptation for 802.11 wireless networks." In Proceedings of the 12th annual international
conference on Mobile computing and networking (MobiCom ?06). ACM, New York, NY,
USA, 2006
43
[21] J. Wang, H. Zhai, Y. Fang and M.C. Yuang. Opportunistic media access control and
rate adaptation for wireless ad hoc networks. IEEE International Conference on Com-
munications, 2004
[22] Vaidya, N.; Dugar, A.; Gupta, S.; Bahl, P.; \Distributed fair scheduling in a wireless
LAN," IEEE Transactions on Mobile Computing, vol.4, no.6, pp. 616- 629, Nov.-Dec.
2005
[23] N. Vaidya, P. Bahl, and S. Gupta. Distributed fair scheduling in a wireless LAN. In Pro-
ceedings of the 6th annual international conference on Mobile computing and networking
(MobiCom ?00), New York, NY, USA, 2000
[24] Chan-soo Hwang; Cio , J.M.; , \Opportunistic CSMA/CA for achieving multi-user
diversity in wireless LAN," IEEE Transactions on Wireless Communications, vol.8, no.6,
pp.2972-2982, June 2009
[25] Eric Rozner, Jayesh Seshadri, Yogita Ashok Mehta, Lili Qiu; "SOAR: Simple Oppor-
tunistic Adaptive Routing Protocol for wireless Mesh Networks", IEEE transactions on
Mobile computing, 2009
[26] Kai Zeng, Zhenyu Yang, Wenjing Lou; "OR:Opportunistic Routing in Multi-Radio
Multi-Channel Multi-Hop Wireless Networks", IEEE transactions on Wireless Commu-
nications, vol.9, Nov 2010
[27] Xiangping Qin, Randall Berry, "Opportunistic Splitting Algorithms for Wireless Net-
works", Twenty-third Annual Joint conference of IEEE computer and communications
societies, Infocom 2004
[28] Xin Liu, Edwin K.P.Chong, Ness.B.Shro "Opportunistic Transmission Scheduling with
Resource-Sharing Constraints in Wireless Networks" IEEE journal on selected areas in
communications, Oct 2001
44
[29] Hiroyuki Yomo, Petar Popovski, "Opportunistic Scheduling for Wireless Network Cod-
ing" IEEE International Conference on Communications, June 2007
[30] NS3{Network Simulator 3, http://www.nsnam.org
[31] Iperf, http://sourceforge.net/projects/iperf/
[32] IETC, RFC3626: Optimized Link State Routing Protocol (OLSR)
45