HIGH PERFORMANCE RATE ADAPTATION ON IEEE 802.11 NETWORKS
Except where reference is made to the work of others, the work described in this dissertation is my
own or was done in collaboration with my advisory committee. This dissertation does not include
proprietary or classified information.
Shaoen Wu
Certificate of Approval:
Kai H. Chang
Professor
Computer Science and Software Engineering
Sa?ad Biaz, Chair
Associate Professor
Computer Science and Software Engineering
Min-Te Sun
Assistant Professor
Computer Science and Software Engineering
George T. Flowers
Interim Dean
Graduate School
HIGH PERFORMANCE RATE ADAPTATION ON IEEE 802.11 NETWORKS
Shaoen Wu
A Dissertation
Submitted to
the Graduate Faculty of
Auburn University
in Partial Fulfillment of the
Requirements for the
Degree of
Doctor of Philosophy
Auburn, Alabama
August 9, 2008
HIGH PERFORMANCE RATE ADAPTATION ON IEEE 802.11 NETWORKS
Shaoen Wu
Permission is granted to Auburn University to make copies of this dissertation at its
discretion, upon the request of individuals or institutions and at
their expense. The author reserves all publication rights.
Signature of Author
Date of Graduation
iii
VITA
Shaoen Wu, son of Daju Wu and Xiuying Tu, was born on July 18, 1976, in Sichuan, China.
He attended Qingdao University of Science and Technology in Qingdao, China, and graduated with
a Bachelor of Science degree in Automation and System Control, 1998. He immediately entered
into graduate school at University of Electronic Science and Technology of China and received a
Master of Science degree in Automation Theory and Engineering in March, 2001. He was then
hired by Bell Laboratories, Lucent Technologies Inc. (China), where he worked as a Member of
Technical Staff I. He married Lingyan Wang, daughter of Daji Wang and Fengzhen Hu, on Jan 1,
2002. In Spring of 2005, he was admitted into the Ph.D. program in Computer Science and Software
Engineering at Auburn University. In July, 2008, he and his wife Lingyan became the proud parents
of their son David (Si-Xing) Wu.
iv
DISSERTATION ABSTRACT
HIGH PERFORMANCE RATE ADAPTATION ON IEEE 802.11 NETWORKS
Shaoen Wu
Doctor of Philosophy, August 9, 2008
(M.S., University of Electronic Science and Technology of China, 2001)
(B.S., Qingdao University of Science and Technology, 1998)
112 Typed Pages
Directed by Sa?ad Biaz
IEEE 802.11 standard has evolved from the basic transmission rates in early days to multi-
ple rates today with advanced encoding and antenna techniques. The performance of IEEE 802.11
wireless networks is supposed to benefit from the support of multiple transmission rates. To take
advantage of multiple available rates, a strategy is required to choose the most appropriate rate in
transmission: rate adaptation in wireless networks is the selection of the optimal transmission rate
for data frames under current channel conditions. For this purpose, a rate adaptation scheme must
assess the channel condition and then accordingly adjust the data rate if necessary. In this disser-
tation, we extensively survey the rate adaptation schemes in literature. We progressively proposed
three strategies to address some open problems in rate adaptation. First, we exploit the periodical
mandatory beacon frames in IEEE 802.11 networks to estimate the initial rate for a stream of data
frames and yield the scheme Beacon Assisted Rate Adaptation (BARA). In IEEE 802.11 networks,
particularly with basic CSMA/CA access, the assessment of channel condition may become com-
plex because frame losses likely result from channel condition degradation or transmission collision,
and each type of frame loss requires a different response in rate adjustment. To diagnose the cause of
a frame loss, we propose the basic rate retransmission technique and a rate adaptation scheme Loss
v
Differentiated Rate Adaptation (LDRA), based on Signal-Noise-Ratio (SNR). However, SNR and
Received Signal Strength Indication (RSSI) are deemed not to be good channel condition indicators.
Then we investigate rate adaptation schemes based on frame losses with loss differentiation ability.
We discuss some anomalies observed in implementing a Linux based rate adaptation testbed. Based
on the observations, we propose Effective Rate Adaptation (ERA) to effectively adapt rates in mixed
frame lossy environments. ERA judiciously exploits the IEEE 802.11 fragmentation mechanism to
accurately diagnose the cause of a loss and responds accordingly. We analytically prove that the
fragmentation mechanism incurs less overhead and is more effective than using RTS/CTS at the
basic (lowest) rate for rate adaptation in a collision dominated environment. ERA also takes effec-
tive actions to overcome abnormalities observed in other rate adaptation schemes. For performance
evaluation, we first simulate all our three schemes on ns-2. Moreover, we implement ERA and four
selected most recent representative rate adaptation schemes on a Linux based testbed and evalu-
ate them with extensive experiments in both controlled and public field tests. Experiment results
demonstrate that our proposed schemes outperform their peers in most scenarios.
vi
ACKNOWLEDGMENTS
I thank God for bring me to USA and giving me the wisdom and the strength to accomplish
my PhD.
I sincerely thank my advisor Dr. Sa?ad Biaz for providing me with the opportunity to pursue my
Ph.D. dream. What I learned from him is not only the knowledge, but also the attitude. I am highly
grateful for his advice during my research and also for his encouragement during my frustration.
I hold great admiration for his continuous efforts to support his students and his dedication to his
work. Guidance from my committee members Dr. Chang and Dr. Sun, and outsider reader Dr. Mao
were very valuable and worth pursuing. I thank and I will miss the members of the Mobile System
Lab, faculty, staff and students of the Computer Science and Software Engineering department. This
work was supported, in part, by National Science Foundation through grants NeTS CNS#0435320
and CRCD/EI CNS#0417565, and by the Vodafone Foundation through a fellowship awarded to
me, and they are gratefully acknowledged.
I have been blessed with the most wonderful and supportive family any one can wish for.
There is little I can say to thank you all. This dissertation would not have been possible without the
support, love, and devotion of my wife Lingyan Wang. I thank God for granting me the miracle,
my beloved son, who provides sunshine and joy to my life. To you, David (Si-Xing), I dedicate this
dissertation.
vii
Style manual or journal used Journal of Approximation Theory (together with the style known
as ?aums?). Bibliograpy follows van Leunen?s A Handbook for Scholars.
Computer software used The document preparation package TEX (specifically LATEX) together
with the departmental style-file auphd.sty.
viii
TABLE OF CONTENTS
LIST OF FIGURES xi
1 INTRODUCTION 1
1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.1 Investigation on IEEE 802.11 Network Channels . . . . . . . . . . . . . . 5
1.1.2 Review of Relevant IEEE 802.11 Features . . . . . . . . . . . . . . . . . . 8
1.2 Literature Review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2.1 First Generation: Rate Adaptation without Loss Differentiation . . . . . . 10
1.2.2 Second Generation: Rate Adaptation with Loss Differentiation . . . . . . . 16
1.2.3 Rate Adaptation Schemes Classification . . . . . . . . . . . . . . . . . . . 19
1.3 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.3.1 Observations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.4 Design Principles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2 BARA: BEACON ASSISTED RATE ADAPTATION 26
2.1 Design of BARA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.1.1 Rate Adaptation with Beacon . . . . . . . . . . . . . . . . . . . . . . . . 26
2.1.2 Adaptive Rate Adaptation During Ongoing Communication . . . . . . . . 28
2.1.3 Basic Rate Retransmission . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.2 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.2.1 Simulation configuration . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.2.2 Data Rate Smoothing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.2.3 Throughput performance . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3 LDRA: LOSS DIFFERENTIATED RATE ADAPTATION 40
3.1 Design of LDRA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.1.1 Rate Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.1.2 Frame Loss Differentiation: . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.1.3 Reactions to Frame Loss: . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.2 Justification for Retransmissions at the Basic Rate . . . . . . . . . . . . . . . . . . 43
3.3 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.3.1 Simulation Configuration . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.3.2 Data Rate Adaptation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.3.3 Throughput Improvement . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.3.4 Delay Jitter Improvement . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
ix
4 ERA: EFFECTIVE RATE ADAPTATION 53
4.1 Rationale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.1.1 Fragmentation in IEEE 802.11 . . . . . . . . . . . . . . . . . . . . . . . . 54
4.1.2 Fragmentation and RTS/CTS . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.1.3 Numerical Analysis of Fragmentation . . . . . . . . . . . . . . . . . . . . 56
4.2 Design of ERA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.2.1 Channel Assessment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.2.2 Loss Diagnosis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4.2.3 Prompt Recovery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.3 Performance Evaluation on Simulation . . . . . . . . . . . . . . . . . . . . . . . . 63
4.3.1 Simulation Configuration . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4.3.2 Composite Environments: Collision and Channel Degradation . . . . . . . 67
4.3.3 Channel Degradation Dominated Environment . . . . . . . . . . . . . . . 73
4.3.4 Collisions Dominated Environment . . . . . . . . . . . . . . . . . . . . . 74
4.4 Performance Evaluation on Linux based Testbed . . . . . . . . . . . . . . . . . . . 76
4.4.1 Implementation Platform and Architecture . . . . . . . . . . . . . . . . . 77
4.4.2 Implementation of ERA in MadWifi . . . . . . . . . . . . . . . . . . . . . 78
4.4.3 Experimental Environment and Methodology . . . . . . . . . . . . . . . . 80
4.4.4 Experiment Results from Testbed . . . . . . . . . . . . . . . . . . . . . . 83
5 CONCLUSIONS AND FUTURE WORK 94
BIBLIOGRAPHY 98
x
LIST OF FIGURES
1.1 Onoe Flowchart . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.2 Continuous transmission failure anomaly . . . . . . . . . . . . . . . . . . . . . . 24
2.1 Data Rate Adaptation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.2 multi-node Rate Adaptation with only Beacon Frame . . . . . . . . . . . . . . . . 35
2.3 multi-node in BARA in WLAN . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.4 multi-node in BARA with Coefficients . . . . . . . . . . . . . . . . . . . . . . . . 36
2.5 Rate Adaptation with only Beacon Frame in Ad-Hoc network . . . . . . . . . . . . 37
2.6 multi-node in BARA with Coefficients in Ad-Hoc . . . . . . . . . . . . . . . . . . 38
2.7 Delay Jitter Improvement by SAAR/BRR . . . . . . . . . . . . . . . . . . . . . . 39
3.1 LDRA Algorithm Flow Chart . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.2 Expected Transmission . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.3 Rate Adaptation Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.4 Throughput Improvement at Different Velocity . . . . . . . . . . . . . . . . . . . 49
3.5 Improvement with Network Density . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.6 Improvement with LDRA vs Adaptive . . . . . . . . . . . . . . . . . . . . . . . . 50
3.7 Throughput Improvement in TCP . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.8 Delay Jitter Improvement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.1 NAV of fragments in IEEE 802.11 . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.2 The Probability Ratio of Successful Frame Delivery . . . . . . . . . . . . . . . . . 58
xi
4.3 Consecutive Transmission Counting . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.4 ERA flowchart . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.5 Topology of 17 static stations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
4.6 Fraction of recovered losses with ONE retransmission . . . . . . . . . . . . . . . . 69
4.7 The mean of retransmission . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.8 Throughput under both channel degradation and collision . . . . . . . . . . . . . . 70
4.9 Throughput of mobile stations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4.10 Adaptation dynamics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
4.11 Throughput under stable channel conditions . . . . . . . . . . . . . . . . . . . . . 74
4.12 Throughput under different levels of collision . . . . . . . . . . . . . . . . . . . . 75
4.13 Impact of Packet length on throughput improvement . . . . . . . . . . . . . . . . . 76
4.14 MadWifi Driver Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.15 Architecture of ERA in MadWifi . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.16 Floor plan in experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
4.17 UDP goodput in static mode in channel degradation . . . . . . . . . . . . . . . . . 84
4.18 UDP goodput in mobile mode in channel degradation . . . . . . . . . . . . . . . . 86
4.19 UDP goodput in mobile mode in combinational loss . . . . . . . . . . . . . . . . . 87
4.20 TCP goodput in static mode in combinational loss . . . . . . . . . . . . . . . . . . 87
4.21 Jitter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
4.22 Percentage of packets out-of-order . . . . . . . . . . . . . . . . . . . . . . . . . . 90
4.23 UDP goodput in heterogeneous competition . . . . . . . . . . . . . . . . . . . . . 90
4.24 UDP goodput under collision levels . . . . . . . . . . . . . . . . . . . . . . . . . 92
4.25 UDP goodput in field test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
4.26 TCP goodput in field test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
xii
CHAPTER 1
INTRODUCTION
The ?last mile? access networks are undergoing tremendous migration from wired technologies
to wireless. Among these wireless access technologies, IEEE 802.11 [1] has gained wide popular-
ity. Data transmission on wireless medium suffers frame losses from unstable channel conditions,
which fluctuate because of signal degradation (like fading, interference, fast time variation). When
a channel can support high data rates, transmission at lower rates definitely underutilizes the scarce
wireless resource. However, transmission at an overoptimistic data rate results in more frame losses.
In IEEE 802.11 networks, frame loss is exacerbated by collision because multiple stations running
with CSMA/CA protocol may transmit data simultaneously. A station can improve the probability
of successfully delivering a frame in channel degradation with a more robust modulation scheme,
which yields a lower data rate. But, it does not increase the chance in collision dominated en-
vironments. Instead, the larger transmission range of a lower data rate worsens collisions, and
consequently degrades the overall network performance. Different causes of frame loss require dif-
ferent reaction. Therefore, we need a strategy to appropriately adjust data rates based on channel
conditions. Rate adaptation is a strategy that determines the optimal rate most appropriate for the
current wireless channel conditions. Rate adaptation generally consists of two functions: channel
assessment and rate adjustment. Channel assessment estimates the channel condition or variation
trends whereas rate adjustment determines the most appropriate rate based on the assessment.
Rate adaptation on IEEE 802.11 networks has been extensively studied in the past years and
many schemes [2?13] have been proposed. These schemes can be generally categorized into two
1
generations. A first generation of these schemes consider adjusting data rate primarily due to chan-
nel degradation. They [2?7] assume that frame losses are mostly caused by channel fading because
RTS/CTS control frames are believed to minimize or eliminate collisions. Some rate adaptation
schemes [6, 7] even count on the exchange of RTS/CTS control frames running at the basic rate to
estimate the practical rate for data frames. Therefore, most first generation rate adaptation schemes
systematically respond to frame loss by decreasing the data rate. However, based on IEEE 802.11
standard and common practice, the use of RTS/CTS control frames is rare: because RTS/CTS are
overhead, they are optional and are recommended only for large data frames. Without the pres-
ence of RTS/CTS control frames, RTS/CTS based rate adaptation schemes are not effective for
deployment and also the collision is not so sparse to neglect. Even with RTS/CTS control frames,
congestion losses may still occur and mislead these rate adaptation schemes. While decreasing rate
is appropriate for channel degradation, it is not for collision for two reasons: 1) a lower rate may
exacerbate medium congestion because of longer frame transmission duration and wider effective
communication range (more interference and higher collision probability); 2) a lower rate unneces-
sarily underutilizes network resource because the channel is still able to support higher data rates.
Therefore, if granted the ability to differentiate frame loss causes, a rate adaptation can tremen-
dously benefit network performance.
Thus, recently, researchers proposed the second generation rate adaptation schemes [8, 9] to
appropriately react to each type of loss: channel degradation or collision. Some schemes explicitly
diagnose the cause of a frame loss [8,9] while others implicitly adjust the data rate to maximize the
throughput. Although they differ in methods to assess channel condition and to differentiate losses,
they all agree that the transmission rate should be decreased only in case of channel degradation and
rather remain constant for a collision.
2
Moreover, there is no effective strategy to estimate the initial data rate at the very beginning
of a transmission when a wireless station just starts up or has been staying idle for a long time.
In general, existing proposed protocols just simply suggest using the median rate in the supported
rate set, or the basic (lowest) rate, or the rate used in the last successful transmission. However,
these strategies do not depend on current channel conditions. Therefore, it is desirable to design an
effective strategy to address this challenge.
Another challenge is the loss recovery (or retransmission) strategy after a frame loss. Since no
algorithm can perfectly estimate the channel, a frame loss happens when the channel condition is
overestimated. Traditional rate adaptation algorithms unduly retransmit the lost frame at the failing
rate until the retransmission succeeds or the rate is lowered to the next level after a timer expires.
Such a strategy does not take advantage of the information exchanged in the transmission and is not
efficient.
The contributions of this dissertation are represented by three new rate adaptation schemes
proposed along the way to identify an effective and efficient strategy. The key features of these
contributions are:
? We address the estimation of the initial rate for a stream of data frames. We reach this
goal with the scheme Beacon Assisted Rate Adaptation (BARA) that exploits the periodi-
cal mandatory beacon frames available in IEEE 802.11 networks.
? We tentatively propose the basic rate retransmission technique to differentiate frame losses in
combinational loss environments and yield the scheme Loss Differentiated Rate Adaptation
(LDRA).
? We present some anomalies observed among other recent rate adaptation schemes with loss
differentiation ability. Also, we identify the inefficiency of loss differentiation in the basic
3
rate retransmission technique used in LDRA. Finally, we propose a complete strategy Effective
Rate Adaptation (ERA), to accurately diagnose the cause of losses, effectively adapt rates and
promptly recover losses by taking the advantage of the fragmentation mechanism in the IEEE
802.11 standard in channel assessment and loss differentiation. As shown later, ERA performs
effectively and efficiently in both channel degradation and collision dominated environments.
We provide a simple analytical proof that the fragmentation mechanism is more effective than
RTS/CTS control frames in diagnosing the cause of a frame loss, adapting the data rate, and
recovering losses.
? To evaluate ERA and other most recent, most representative rate adaptation schemes, we
implement them on a Linux based testbed. We conduct extensive controlled and field experi-
ments on the testbed under the same conditions for these rate adaptation schemes, in addition
to the performance evaluation with numerous simulations.
From the experiment results gathered from both simulations and the implemented testbed, our
solutions outperform their peers in most scenarios. Particularly, the outstanding performance of ERA
benefits from: 1) its accurate and prompt diagnosis of the cause of a frame loss (channel degradation
or congestion) and appropriate response; 2) its faster recovery of a frame loss. Whenever a frame
is lost for the first time, ERA splits the lost frame in two fragments in retransmission: a very short
fragment and the remainder. After the cause of a loss is analyzed, ERA maintains the rate unchanged
for collisions and judiciously adapts the rate for channel degradation based on a halving-rate strategy
described later.
The remaining sections of this chapter (Chapter 1) present the background information, the
review and our classification of rate adaptation schemes in literature, the motivation followed by
4
the design principles and the rationale of those techniques in our schemes. In the rest of this dis-
sertation, we will chronologically present each rate adaptation scheme (BARA, LDRA and ERA in
order) and the corresponding performance evaluation as an individual chapter. Next, in Chapter 2,
we present our first rate adaptation work BARA and its performance evaluation. Then, in Chapter 3
we discuss the rate adaptation scheme LDRA that can differentiate frame losses with the basic rate
retransmission technique. Afterwards, Chapter 4 presents the design of a complete rate adaptation
solution ERA, related implementation and performance evaluation. Finally, Chapter 5 concludes
this dissertation and provides hints to future work.
1.1 Background
Research in wireless network can barely be carried out without investigating the characteristics
of wireless channels. This section presents the literature investigation on IEEE 802.11 channels,
followed by the review of related IEEE 802.11 standard information.
1.1.1 Investigation on IEEE 802.11 Network Channels
Existing IEEE 802.11 link measurements [15?24] can be categorized upon different criteria.
This section groups them according to the environment in which these assessments are conducted.
Most of the measurements on IEEE 802.11 network link were completed in outdoor environments.
More extensive assessment is needed for indoor environments.
Aguayo et al. [18] performed extensive and nearly the most complete link-level measurement
in a 802.11b mesh network named Roofnet [14] with hundreds of node pairs with antenna mounted
at the top of different campus buildings. From their experiments in an urban-like network, the
interesting observations are:
5
? Most of the links experience mild loss rates regardless of the communication distance be-
tween node pairs. Namely, the frame loss rate is not closely correlated to the communication
distance.
? Although links with strong signals are likely to have low frame loss rates, signal strength is
in general not predictive of the loss rate.
? The fact that most links experience mild loss rates is probably due to multi-path fading in
outdoor environments.
? When the loss rate increases heavily due to collisions, high data rates might result in much
better performance than low data rates. This implies that rate adaptation algorithms should
not take the loss rate as the only indicator to adjust data rate.
Although Aguayo et al. carried out extensive experiments and analyzed in detail the fac-
tors impacting IEEE 802.11 networks, their results are limited to outdoor environments and IEEE
802.11b [25] only. As the physical coding is different between IEEE 802.11b and IEEE 802.11g [26],
they might have different characteristics even in the same environment, which is partially demon-
strated by Bianchi, Formisano, and Giustiniano [17].
Chebrolu, Raman, and Sen [23] monitored several links in a long distance 802.11b rural net-
work, where interference is rare. Their observation on this network setting somehow contrasts with
Aguayo?s observations [18]. They found:
? The relationship between the packet loss rate and the signal-to-noise (SNR) is close to the
theory. The loss rate varies in a very narrow band of SNR. This is confirmed by Barsochhi,
Oligeri and Potort [19].
? Transmission rate (modulation) has a significant impact on the frame loss rate.
6
? External interference can almost destroy the communication in the link.
One possible explanation for the contrast between Chebrolu [23] and Aguayo [18] is the network
environment. Although both measurements are gathered from 802.11b outdoor networks, one is
with heavy communication congestion (collision), the other is not. In [23], most frame losses are
caused by channel fading. Therefore, more robust modulation (lower data rate) incurs less frame
loss.
Rodrig et al. [15] collected real time traces from the conference SIGCOMM 2004. From the
data they gathered, almost 35% of whole transmission time is spent in retransmitting. And almost
28% of data frames had to be retransmitted. This observation implies the ineffectiveness of current
rate adaptation algorithms implemented in commercial wireless adaptor drivers. This work also
shows that the frame loss from CSMA/CA contention has a profound impact on the performance of
the rate adaptation.
Bianchi, Oligeri and Potort [17] found that the link behavior of 802.11b is totally different
from that of 802.11g due to the physical coding variance. Some signal environments favorable to
802.11b throughput are not for 802.11g?s.
Souryal et al. [27] assessed the 802.11 link in an indoor environment. They claim that the SNR
is a good indication of link robustness. But the trace is very limited and the IEEE 802.11 variant
used in experiment is not specified.
One conclusion upon these assessments of IEEE 802.11 networks is that although SNR can
be a good indicator to adapt rate in some cases particularly in outdoor wide space, frame loss from
contention (collision) is worth more attention in rate adaptation.
7
1.1.2 Review of Relevant IEEE 802.11 Features
In this section, we firstly present the support of multiple data rates on IEEE 802.11 networks.
Then we briefly introduce the basic CSMA/CA access mechanism in IEEE 802.11 Distributed Co-
ordination Function. Finally, possible frame loss scenarios are discussed.
Support of Multiple Rates in IEEE 802.11
Since 1999, IEEE 802.11 standard has evolved through several variants. The support of mul-
tiple rates becomes a mandatory requirement in the physical layer with more and more advanced
encoding and modulation techniques for all these variants. For example, IEEE 802.11g [26] offers
1, 2, 5.5, 11, 6, 9, 12, 18, 24, 36, 48, 54 Mbps; IEEE 802.11a supports 6, 9, 12, 18, 24, 36, 48,
54 Mbps; IEEE 802.11b consists of 1, 2, 5.5, and 11 Mbps. Most recently, IEEE 802.11n draft
has recommended high data rates up to 540 Mbs with MIMO [28] technology. However, the IEEE
802.11 standard group does not mandate or recommend any specific rate adaptation strategy even
though a rate adaptation strategy is critical to the performance in multiple-rate networks.
Basic CSMA/CA Access
In IEEE 802.11 standard, there are two access methods for Distributed Coordination Function.
One is CSMA/CA with optional RTS/CTS. However, the basic CSMA/CA access is mandatory.
With CSMA/CA, each station has to sense a channel before it transmits. To reduce collisions,
the station does not transmit immediately if the channel is sensed idle, but backs off a contention
window of time slots whose size is randomly picked up from a range. After the contention window
time passes and if the channel is sensed idle, the station will transmit its data immediately. If
the channel is still busy at the end of the contention window, the station picks up another random
8
contention window size from a doubled range and repeats the backoff procedure. The transmission
occurs as a stop-and-wait mechanism: an ACK frame is the proof of successful receipt of the data
frame at the receiver station. Although channel sensing and random backoff are introduced to reduce
transmission collision, two transmissions are still likely to collide with each other, especially when
a hidden terminal problem exists: a station receives two transmissions from two stations that can
not sense each other. The collision in an environment with basic CSMA/CA access is exponentially
increased with the number of transmitting stations.
Loss Scenarios
Unguided wireless medium is vulnerable to distance fading, physical characteristic change
of the air, external signal interference and collision from simultaneous transmissions. These distur-
bances cause frequent frame losses in wireless communication. IEEE 802.11 networks are generally
exposed to two kinds of loss environment: strictly channel degradation dominated or the combina-
tion of degradation and collisions. Most wireless home networks are channel degradation dominated
environments, where there is only one wireless user (laptop or other IEEE 802.11 equipped device).
In such an environment, whether the user is mobile or not, frame losses are mostly due to channel
degradation (e.g. fading due to distance or fast channel variation). Another degradation scenario is
the long distance mesh network backbone deployed in rural regions [29]. Since IEEE 802.11 sup-
ports multiple non-overlapping channels, these sparse wireless backbone nodes generally connect
to one or two neighbors, each link on a different channel, thus eliminating transmission collisions.
More frequently, IEEE 802.11 networks, such as corporate and campus networks, suffer from both
channel variation and transmission collisions. Normally, there are multiple wireless client stations
associated with an access point in these networks. It is inevitable that some transmissions collide.
9
To minimize data frame collisions, short RTS/CTS control frames are recommended to precede data
frames. However, due to the overhead caused by RTS/CTS to data frames, IEEE 802.11 standard
dissuades their use for those data frames with a length smaller than the RTS threshold. Garg and
Kappes [30] showed that, for VoIP traffic with 160-byte packets, the data frame efficiency drops to
about 12% in IEEE 802.11b networks at 11 Mbps when RTS/CTS control frames are used. Thus,
RTS/CTS frames are rarely used in practice. This low utilization of RTS/CTS was observed by Ro-
drig et al [15]: RTS/CTS control frames account for only 297 frames compared to 5540 data frames
(in Table 2 of [15]). Therefore, it is fairly reasonable to expect frequent frame losses from collision
in the real world.
1.2 Literature Review
Rate adaptation in IEEE 802.11 networks has been studied for years. This section surveys the
most typical and latest relevant schemes. We begin with the first generation rate adaptation schemes,
which do not differentiate losses due to channel degradation from those due to collision. Then the
second generation schemes with loss differentiation are reviewed.
1.2.1 First Generation: Rate Adaptation without Loss Differentiation
This section presents the rate adaptation schemes without loss differentiation. They are cate-
gorized in two groups: frame loss based and signal strength based.
Rate Adaptation Based on Frame Loss
Auto Rate Fallback (ARF) by Kamerman and Monteban [2] is the earliest rate adaptation
scheme for IEEE 802.11 based wireless networks. Kamerman and Monteban proposed it for the
10
Lucent Wave-II wireless LAN adapters. It is simple and intuitive. A sender starts transmission
at the basic (lowest available) data rate (2 Mpbs in IEEE 802.11b) and triggers a timer. If either
the timer expires or the sender succeeds for N (a constant threshold) consecutive transmissions,
the sender increases its data rate rold to a new data rate rnew, and the timer is reset. If the first
transmission at the new rate rnew fails immediately after the data rate is increased, the sender falls
back to the prior rate rold. The data rate is also decreased when the sender fails in transmission
twice consecutively. ARF considers the frame loss as the indicator of channel conditions. It adjusts
the rate based on the number of consecutive successful transmissions.
Since ARF [2] the earliest rate adaptation for WLAN, several rate adaptation schemes have
been proposed to refine it. One of them is the Adaptive Auto Rate Fallback (AARF) [3] proposed
by Lacage et al.. ARF suffers from periodical rate fluctuation between the best rate it can support
and the higher rate even in fairly stable channel condition due to its constant rate increase threshold.
To tackle with this shortcoming, AARF introduces an adaptive rate increase threshold N. Just as
ARF does, AARF records the number (M) of consecutive successfully transmitted frames. If M is
no less than the threshold N, the transmission rate is increased from rold to a new rate rnewwith the
assumption that the channel is likely stable enough to support a higher data rate. However, AARF
differs from ARF in that it adaptively adjusts this threshold N after a frame loss at a newly increased
rate. More particularly, consider that the very first transmission at this new rate rnew fails, then the
sender falls back on the prior rate rold immediately (with assumption that the channel is not actually
good enough to support rate rnew). At the same time, AARF doubles the threshold to 2N for the next
cycle to in crease rate unless the threshold reaches the upper bound (50). Otherwise, i.e. the first
transmission at the new rate succeeds, the threshold is reset to the lower bound (10). This threshold
is also reset and the rate is decreased if a transmission fails twice consecutively. The benefit of such
11
Y
N
Y
Y
Y
N
N
N
N
Initial rate = 24 Mbps (802.11a/g) or 11 Mbps (802.11b)
Credit = 0; Num=0; Retries=0;Succ=0;
Caculate:
Num: the number of frame transmitted
Retries: the average retries per frame
Succ:the number of successful tranmsissions
Succ == 0?
Transmit1 second?
Num >= 10 &&
Retries > 1Decrease rate
Retries >= 0.1
Credit++Credit--
Credit >=10Increase rate
Y
Credit=0;
Num=0;
Retries=0;
Succ=0;
Figure 1.1: Onoe Flowchart
adaptive threshold update is that the interval between two successive rate increases over a stable
channel is exponentially extended and fewer rate fluctuations are incurred than ARF.
As one the earliest implemented open source rate adaptation schemes, Onoe [10] was de-
veloped by the MadWifi organization for WiFi adapters with Atheros chips. It is a credit based
algorithm and tries to find the best data rate whose loss ratio is less than 50%. Onoe adjusts the rate
at the end of each 1000 ms cycle based on the collected transmission statistics. Therefore, Onoe
is insensitive to burst losses but irresponsive to fast changes in wireless channels. The detailed
algorithm Onoe is illustrated in the flowchart on Figure 1.1.
12
Rate adaptation scheme SampleRate [11] by Bicket is based on periodical transmission statis-
tics. The size of a transmission window is constant (10 seconds) in time. SampleRate attempts to
identify the bit-rate with the smallest average transmission time in the last transmission window.
The transmission time for a frame is defined as the time frame from sending it to the receipt of its
acknowledgement, which includes the time spent on retransmission and backoff if applicable. In the
beginning, SampleRate tries the initial transmission at the highest rate. If four consecutive transmis-
sions fails at this rate, the rate is decreased immediately. In each window, a rate is designated as the
primary rate. To probe potential better channel conditions in each window, SampleRate randomly
?samples? one of those rates whose lossless transmission time is less than the average transmission
time of the rate in use for every tenth frame. Then, SampleRate calculates the average transmission
time per frame for different rates used in transmission at the end of each transmission window. The
particular ?sample? strategy is illustrated in following example. In IEEE 802.11b, for a packet of
1500 bytes, the lossless transmission times are about 1.873, 2.976, 6.834, and 12.995 ms for the
four data rates 11, 5.5, 2 and 1 Mbps, respectively (from Figure 5-1 in [11]). Suppose the rate at
some transmission window is 11 Mpbs. After a couple of transmissions, the transmission time is
averaged as 3.276 ms (including retransmission time resulted from frame losses), which is larger
than the lossless transmission time (2.796 ms) of rate 5.5 Mbps. Then, SampleRate transmits the
tenth packet at 5.5 Mbps hoping that such a transmission might take less average transmission time
without any frame loss. Using the rates with smallest average transmission time, SampleRate seeks
to achieve the best average throughput performance in the long term.
With SampleRate, we close this section on rate adaptation schemes that are based on frame
loss to estimate channel conditions. In the following, we focus on rate adaptation schemes based on
SNR or the received signal strength indication (RSSI).
13
Rate Adaptation Based on Signal Strength/SNR
Receiver Based Auto Rate (RBAR) [6] by Holland, Vaidya, and Bahl is the first rate adaptation
that takes advantage of the control frames RTS/CTS transmitted at the basic rate. RBAR modifies
IEEE 802.11 standard in two aspects: 1) the channel reservation in the header of RTS/CTS is rep-
resented by packet size and rate, instead of the standard transmission time; 2) a proposed message
RSH precedes the data frame to finalize the tentative reservation information in CTS. In RBAR, a
source station Src selects a heuristic rate (for instance, the rate of the last successful transmission)
and includes it and the data packet size in a RTS frame. When the destination station Dst gets the
RTS, it retrieves the SNR from physical layer and translates it to a data rate that can be supported by
current channel conditions. Then Dst embeds the selected data rate and the data packet size in the
CTS frame header. All stations sensing this CTS frame can calculate the tentative channel reserva-
tion time from the packet size and the rate. Receiving the rate information in CTS, Src makes the
final decision about the rate to use. This proposal relies on the use of RTS/CTS.
Heusse et al [31] observed a performance anomaly in IEEE 802.11 multi-rate networks: all
stations achieve almost the same throughput despite different rates they can support. This is due to
the equal probability of all stations with CSMA/CA to access the shared wireless channel in spite
of their perceived channel conditions. This is the so called throughput fairness. But this fairness
hurts the performance of those stations with high rates and the overall network. Another option is
to achieve temporal fairness among stations: each station gets almost equal transmission time rather
than equal throughput. Opportunistic Auto Rate (OAR) [7] by Sadeghi et al tackles this challenge.
OAR probes the rate through the exchange of RTS/CTS exactly as RBAR does. However, it differs
from RBAR in its opportunistic transmission of data frames. After a source station Src selects the
rate, OAR transmits multiple consecutive frames depending on the selected rate: 5 for 11 Mbps, 3 for
14
5.5 Mbps and 1 for 2 Mpbs. OAR takes advantage of the fragmentation mechanism in IEEE 802.11
to transmit these multiple consecutive frames. Fragmentation allows to keep the channel until all
fragments are sent. OAR delivers time fairness and also improves the throughput performance with
less average overhead of contention time and RTS/CTS per frame.
Scheme Full Auto Rate (FAR) [12] by Li et al. attempts to achieve full data rate adaptation.
The authors contend that, as for receiver based protocols, like RBAR, if the RTS/CTS is transmitted
at a higher data rate when possible, rather than the basic rate, better performance should be achieved
because the transmission at the basic rate underutilizes the wireless channel. In FAR, an idle station
overhears frames from its neighboring stations. Based on the received signal strength, it estimates
the rate to each neighboring station. Then, when this station needs to transmit a RTS, it uses the
pre-estimated rate. If RTS is transmitted successfully, FAR follows the strategy in RBAR to estimate
the rate for the data frame with the exchange of RTS/CTS. If RTS fails, it is retransmitted at a lower
rate.
Received Signal Strength Link Adaptation (RSSLA) [5] by Pavon and Choi is a table-driven
scheme. It estimates channel conditions based on the Received Signal Strength (RSS). A station
monitors all frames it can sense and stores the adapted RSS for each neighboring station. The RSS
is adaptively updated with a constant low pass filter coefficient:
RSSn = (1??)?RSSn?1 +??r (1.1)
where RSSn is the nth adapted RSS and r is the instant RSS retrieved from the last received packet.
In transmission, the station retrieves the RSS of the destination station and maps it to the corre-
sponding rate.
15
Theoretically, the modulation scheme is closely associated with SNR [32]. Therefore, the rate
should be able to be determined from SNR measurement. However, recent studies of the signals in
realistic environments [11, 18] uncover that generally neither SNR nor RSS exhibit a strong corre-
lation with the frame delivery probability at a given rate. These observations limit the effectiveness
of SNR/RSS based schemes in practice.
1.2.2 Second Generation: Rate Adaptation with Loss Differentiation
The first generation rate adaptation schemes are effective in environments without collision
loss. But, without the ability to diagnose the cause of a loss, they also unduly decrease rates in
response to collision losses. Therefore, they can not perform effectively in collision dominated en-
vironments or in presence of losses mixed from channel fading and collision. Since most traffic
in practice does not use the optional RTS/CTS frames to clear the channel [15], losses from col-
lisions are likely to occur. To respond accurately to a frame loss, recent rate adaptation research
focuses on the loss differentiation and appropriate loss recovery. In this section, these schemes are
chronologically presented.
Pang, Leung and Liew proposed a rate adaptation scheme called loss-differentiating-ARF (LD-
ARF) [13] for IEEE 802.11 WLANs by combining ARF with a loss-differentiating MAC [33] they
developed. In LD-ARF, loss differentiation is performed at the receiver. LD-ARF assumes there is
no hidden terminal problem in a WLAN: all stations can hear each other. The authors argue that
the frame header is short and thus resilient to wireless channel fading; therefore, if a received frame
header can be decoded while the payload can not, this frame corruption is attributed to the channel
fading. Otherwise, the frame loss is inferred from a collision because two stations might transmit
in the same slot although they both are equipped with carrier sense: the collision is assumed to
16
destroy both the frame header and body. If the frame loss is diagnosed due to channel degradation,
a negative ACK (NACK) is sent back to the source station to lower down its rate: the frame source
address is assumed available in the decoded frame header. All other operations are the same as in
ARF.
To introduce the ability of differentiating frame loss between from channel degradation and
collision into ARF in environments without RTS/CTS, Kim, et al. proposed Collision-Aware Rate
Adaptation (CARA) [8]. However, CARA does rely on RTS/CTS to be ?aware? of collision in case
of a frame loss. In rate increase, CARA does the same as ARF does: by counting the consecutive
successfully transmitted data frames. However, when a data frame is lost, CARA sends a RTS before
the retransmission of the lost data frame. The motivation of CARA is that the RTS (always sent at
the basic rate) is resilient to channel fading. Therefore, if the RTS preceding retransmission of data
frames also fails, the data frame loss is likely resulted from collision. Essentially, what CARA does
is to use RTS/CTS to suppress collisions from hidden terminals with implicit assumption that the
data frame is lost due to congestion. To mitigate the overhead caused by using RTS/CTS frames,
CARA suggests that a transmitting station switches its adapter to sense the channel immediately
after a transmission is over. If its transmission gets lost and the channel is sensed busy, this loss is
attributed to collision without the probing with RTS. It should be noted that the busy channel sensed
at the source station does not necessarily result in a collision at the destination station.
Wong, et al. proposed the Robust Rate Adaptation Algorithm (RRAA) [9] and demonstrated
its outstanding performance with implementation of it and some other schemes at an access point
in a testbed. RRAA targets at environments without RTS/CTS. But, it also relies on the use of
RTS/CTS in loss differentiation after a frame loss and further to avoid collisions. RRAA consists
of two elements: rate adaptation (loss ratio estimation and rate selection) and collisions elimination
17
if collision domination is inferred. RRAA gathers the loss ratio from recent transmission statistics
over windows. Each transmission window designates the number of data frames to transmit, instead
of the time. The size of a window depends on the transmission rate to be used in this window.
Therefore, the sizes are not always equal for different rates. A station running with RRAA initializes
transmission at the maximum rate. The rate is used for all frames in a window. At the end of each
window, the frame loss ratio p is calculated to select the rate for the next window. To select a proper
rate for the next window, RRAA introduces two thresholds: PMTL and PORI. If p > PMTL, the
next lower rate is chosen for the next window transmission with the assumption that the channel is
degraded and the lower rate might produce better performance. If p < PORI, the rate is increased
with the belief that the channel condition is not fully exploited. If (PORI <= p <= PMTL), the rate
remains unchanged, but the window slides forward to continuously compute the loss ratio for the
current rate, rather initialize a new window. Once the rate is decided, it is then used to index a table to
extract the corresponding window size. Beyond the rate adaptation, RRAA presents a strategy called
Adaptive RTS (A-RTS) to reduce possible collision losses. A-RTS maintains two variables RTSwnd
and RTScounter. RTSwnd essentially ?predicates? the trend of channel condition variation. It
indicates the number of potential consecutive data frames to be transmitted with a preceding RTS.
RTSwnd is adjusted as follows: when a frame without RTS is lost, RTSwnd is incremented by one
with the assumption that this loss is probably due to collision; when a frame preceded by RTS is
lost, or a frame without RTS succeeds, RTSwnd is halved. However, it is RTScounter that controls
if a RTS should be really used before a data frame. If RTScounter is less than RTSwnd, a RTS/CTS
handshake is pursued before a data frame is transmitted. When integrating the rate adaptation and
A-RTS, RRAA does not consider the loss of RTS into the loss ratio computation. Although RRAA
uses RTS frames to mitigate collisions, it does not promptly decrease its rate even if the loss is
18
inferred from channel fading. To respond to channel variation more quickly, RRAA also suggests
an optimization: adjust the rate if necessary in the middle of a window, instead of at the end of the
window.
1.2.3 Rate Adaptation Schemes Classification
In this section, before the categorization, we first present the criteria to be used. Rate adap-
tation generally contains two essential operations: the assessment of channel condition and the
corresponding rate adjustment. The categorization criteria are identified from these two operations.
? Channel Condition Indicator: Most of the early rate adaptation schemes (e.g. RBAR [6],
OAR [7], FAR [12], and RSSLA [5]) consider Signal-to-Noise Ratio (SNR) or Received Sig-
nal Strength Indication (RSSI) as an indicator of the channel conditions. Such motivation
intuitively originates from the wireless signal propagation principle. Other early schemes
(ARF [2], AARF [3], Onoe [10]) consider frame loss as the channel conditions indicator.
Since Aguayo et al. [18] and Bicket [11] observed that neither SNR nor RSSI demonstrates
a strong correlation with delivery probability at any given data rate, all recent schemes, such
as SampleRate [11], CARA [8], and RRAA [9], use frame loss as the channel conditions in-
dicator. For those schemes using frame loss as indicator, they can be further characterized as
either winning streak or statistics based. A ?winning streak? scheme relies on a given num-
ber of consecutive successfully transmitted data frames. A ?statistics? based scheme gathers
transmission statistics over the most recent history to increase or decrease its data rate.
? Loss Differentiation: Rodrig et al. [15] discovered that most of the traffic is transmitted
without presence of RTS/CTS to reduce overhead. Therefore, frame losses in a WLAN net-
work now can be contributed by both channel degradation and collision. Consequently, the
19
Schemes
Channel Condition Indicator
Frame Loss RSSI/SNR
Winning Streak Statistics
LD CARA, LD-ARF RRAA LDRA
Non-LD ARF, AARF Onoe, SampleRate
RBAR,
FAR,
RSSLA
Table 1.1: Categorization of Rate Adaptation Schemes
ability to differentiate frame loss between these two contributors is critical because each of
them requires different response in rate adjustment. Loss differentiation consists of 1) diag-
nosing the cause of a frame loss between channel degradation or collisions, and 2) taking
appropriate actions for each cause of loss. Although rate adaptation in IEEE 802.11 networks
has been studied for years, most schemes do not explicitly diagnose a frame loss, particu-
larly those schemes based on RSSI/SNR. Recently proposed rate adaptation schemes (e.g.
CARA [8] and RRAA [9]) react to collisions by dissipating the congestion and react to channel
degradation by lowering the data rate.
According to above criteria, we classify typical rate adaptation schemes in Table 1.1, where
LD stands for Loss Differentiation, Non-LD for Non Loss Differentiation (i.e., schemes that do not
differentiate the cause of a frame loss).
1.3 Motivation
In a multi-rate wireless network, when a mobile station starts up and needs to send packets, it
generally has the following options to select a transmission rate: the basic (lowest) data rate, last
successful transmission rate, or an estimated data rate. By default, most current rate adaptation
20
schemes use the basic data rate for the first frame so that it can be captured by every station within
the transmission range. Li et al. [12] observed with simulation that transmitting RTS/CTS at an
estimated data rate, rather than the basic rate, can improve throughput. Therefore, similarly, a
well-predicted initial rate at the sender may be challenging but benefits the network performance in
environments with/without RTS/CTS. The estimation of the initial rate also benefits the transmission
after a long inactivity. Suppose station A wants to send packets to station B. But station B is
inactive and has not transmitted packets for a long time (e.g. several minutes), the sender station A
is unaware of the link status to station B.
Since RTS/CTS are overhead to data frames, they are optional in IEEE 802.11 standard and
thereof they are not used in most transmissions. Their absence in practice are shown by Rodrig
et al. [15] with collected real time traffic in a conference. Without the RTS/CTS preceding, data
frames are more likely to collide with each other. Frame losses due to collision can be addressed
with collision suppression techniques without decreasing rate. But the frame loss due to channel
degradation has to be recovered with lower rates. Therefore, a loss differentiation or diagnosis
strategy is highly desirable in rate adaptation.
Also, from the collected real time traffic, Rodrig et al. [15] observed that retransmissions oc-
cupies 46% of the whole data transmission time and that most of the transmissions occur at 1 Mbps,
the lowest rate. Such observation implies that current rate adaptation schemes implemented in com-
mercial products are inefficient and an innovative scheme is highly desirable.
In the following, we first discuss some anomalies observed while implementing, testing, and
debugging rate adaptation schemes on a Linux based testbed. Such observation also motivates and
provides insights for the design of our final scheme ERA. Then, we highlight some design principles
for an effective and efficient rate adaptation scheme.
21
1.3.1 Observations
While implementing and debugging rate adaptation schemes on a Linux based testbed, we
observed some anomalous behaviors.
? Inconsistent Performance: The schemes that requires RTS/CTS at the basic rate to differen-
tiate losses, (e.g. RRAA and CARA), do not perform as effectively in channel degradation
environments as in collision dominated environments. The root cause is that they do not have
proactive actions to promptly recover a frame loss due to channel fading. The success of
the RTS/CTS at the basic rate does not improve the probability of the data frame success-
fully retransmitted still at the old rate. Consider a frame loss occurs due to fading and the
RTS/CTS is sent (at the basic rate) to precede the retransmission. The RTS/CTS frames may
succeed at the basic rate, but the retransmitted data frame definitely fails because the rate was
not decreased to counter the fading. Therefore, although RTS/CTS control frames reduce the
congestion frame loss, they can not help with channel fading.
? Mistake in Loss Counting: So far, all frame loss based schemes (either loss ratio based or
?winning streak? based) mistakenly take the frame loss from collision into consideration in
computing their loss statistics used as an indication of channel degradation only, even if some
of them are able to diagnose the cause of a loss. The loss ratio or consecutive successful
transmissions in literature are primarily used for detecting the channel degradation, not the
collisions. Therefore, it is not reasonable to include collision losses in the measurement of
loss ratio or consecutive successful transmissions. Namely, the counting of frame losses in
existing schemes is too pessimistic in estimating channel degradation.
22
? Clumsy Response: Schemes that are based on frame loss statistic with a large cycle or window
might get numb to channel fast variation unless some rate probing strategy is adopted in the
middle of a transmission cycle. Although RRAA proposes an ?optimization technique? to
solve this problem, one failure case is still likely to occur. Such an issue is illustrated in
Figure 1.2. Consider the transmission rate is 36 Mbps. From RRAA [9], the transmission
window size for this rate is 40 frames. The loss ratio threshold PMTL to increase the rate
to 48 Mbps is 11.50% and the loss ratio threshold PORI to decrease the rate to 24 Mbps is
33.63% [9]. Suppose after a period of collision, the counter RTScounter reaches 32. Now, the
channel fades after the transmission of the 34th frame. Then the six left transmissions in this
window are all preceded by RTS/CTS, but they all will fail because the rate is not promptly
decreased to respond to the fast channel variation.
? Inefficient Transmission at Basic Rate: It is not efficient to differentiate loss with the trans-
mission at the basic rate like LDRA [34] or some schemes relying on RTS, even if the frame is
very short. Generally the channel is rarely fading abruptly. The time for a transmission at the
basic rate is long enough to allow several transmissions at the normal rate. This is particularly
wasteful in case of a collision where a transmission at basic rate does not any help.
1.4 Design Principles
Based on the above observation and successful experience from other rate adaptation schemes,
we summarize the design principles for an effective and efficient rate adaptation as follows.
? Fast Recovery: Despite that SNR is not a good indicator [11,18] of successful frame delivery,
the SNR based LDRA [34] yields a significant throughput improvement when there are no
23
Frame
Sequence
Loss
RTScounter
RTSwnd 32 16
X
8 4 2
X
1
DATA
RTSX X X
32 16 8 4 2 1
X
0
0
Figure 1.2: Continuous transmission failure anomaly
collision losses and no hidden terminal problem. The strength of LDRA stems from its re-
transmission strategy that provides prompt recovery of lost frames. Therefore, a fast recovery
strategy can improve network performance significantly.
? Accurate Loss Differentiation: Since different type of loss can not be addressed with the same
solution, an accurate differentiation of loss causes is valuable for performance improvement.
A common sense is that decreasing the rate for collisions is unnecessary and wasteful. CARA
and RRAA illustrate that a rate adaptation scheme not only should not decrease its rate in re-
sponse to collisions, but it should proactively diffuse congestion: both schemes use RTS/CTS
frames to minimize congestion.
? Consistent Performance in Different Environments: a rate adaptation should not only be ef-
fective and efficient in collision environment, it should also work outstandingly in collision
free or channel degradation environments.
24
? Fast Response to Channel Degradation: After the cause of a frame loss is diagnosed from
channel degradation, the network performance can be improved if the rate is adjusted promptly,
rather than remains till the end of the cycle or window.
? Separating Collision Loss: When we compute frame loss statistics for channel degradation,
the loss from collision in the middle of counting should not be taken into account.
So far, RTS/CTS frames are used [8, 9] to probe the channel and/or alleviate congestion to
yield an efficient rate adaptation. Since RTS/CTS control frames may be a significant overhead and
usually are not used, it is of utmost interest to find other ways than RTS/CTS to dissipate collisions.
25
CHAPTER 2
BARA: BEACON ASSISTED RATE ADAPTATION
This chapter presents our initial work on rate adaptation. This rate adaptation is named Beacon
Assisted Rate Adaptation (BARA) because beacon frames are exploited to estimate instantaneous
transmission rates In this chapter, we first discuss the design details of BARA. Then, its performance
evaluation is presented.
2.1 Design of BARA
In this section, we discuss the details of the BARA scheme. We start from the estimation of
the initial rate with beacon frame, then we illustrate the adaptive rate adaptation during an ongoing
communication. Finally, we discuss the basic rate retransmission after a frame loss to reduce the
number of retransmissions in loss recovery.
2.1.1 Rate Adaptation with Beacon
Since beacon frame is broadcast periodically, this leaves ?room? to estimate data rate without
introducing overhead. In whatever network mode, infrastructure or infrastructureless, beacon is
mandatory. These periodic beacon frames received at a mobile station allow it to determine the
statistics of the channel conditions (e.g. signal to noise ratio, signal strength, and loss rate). Based
on such wireless channel information, the mobile station can calculate the best data rate to the source
mobile station who initiates the beacon (in ad hoc networks, it is another mobile station; in WLAN
it is the access point), and then record this data rate information into a table for later use. The table
may be indexed by the destination mobile station address. Each tuple may include the modulation
26
level or data rate as content. When this mobile station needs to transmit data frames to another
mobile station, it looks up the rate table for a data rate that it can utilize to communicate with the
target mobile station. It instructs its physical layer to transmit the data frame by making use of the
associated modulation corresponding to that data rate. The main drawback of this basic strategy is
the estimated rate might not be exactly real-time because estimation is only adjusted every beacon
interval. But this mechanism is good for the initial rate estimation, because the estimated rate is still
more precise than a randomly selected data rate at the beginning of the transmission. It is also more
efficient than the basic data rate.
The following algorithm describes this strategy:
When a frame is received:
if (FrameType == Beacon)
{
Index = GetFrameMacAddress();
ChannelStatistics = GetChannelStatisticsFromPhy();
if (ChannelStatistics > ThresholdRate 11)
Rate = 11Mbps
else if (ChannelStatistics > ThresholdRate 5.5)
Rate = 5.5Mbps
else if (ChannelStatistics > ThresholdRate 2) 10
Rate = 2Mbps
else{
Rate = 0Mbps;
Log(signal is too weak. No channel
to destination mobile station);
}
27
RecordRate2Table(Rate, Index);
}
When a frame needs to transmit:
Index = GetDestinationMacAddress();
GetRateFromTable(Rate, Index);
If (Rate == 0){
Log(Transmission can not complete.
No channel to destination mobile station);
return 0;
}
TransmitDataPacket(Rate);
2.1.2 Adaptive Rate Adaptation During Ongoing Communication
This mechanism is applicable to instantaneous rate adaptation per frame for an ongoing stream
of frames. As stated in the above subsection 2.1.1, dynamic data estimation with only beacon frame
might not be real time, because beacon frame can only be sensed every beacon interval, not available
at any time. If all frames flying during communication can be used to estimate data rate, the estima-
tion would be more accurate. Thus a station in ?capture? range can dynamically estimate the data
rate of the link to those transmitting stations based on the channel condition statistics. Therefore,
after the initial rate is estimated from the most recent beacon frame, an adaptive mechanism aims to
predict data rates on both beacon frames and all other data frames that the station can receive. This
is helpful especially in two scenarios.
28
1. The first case happens within a transmission sequence of data frames. In this case, a sender
mobile station sends a stream of data frames to a mobile station with one data frame at a
time. When the receiver captures the data frames, MAC protocol mandates the receiver to
respond with an acknowledgement control frame. Therefore, the sender gets the channel
condition information from this acknowledgement packet and adapts its data rate for the next
frame transmission if necessary. Since a significant number of packets can be transmitted
within one beacon interval, even if the channel condition varies within a duration shorter than
a beacon interval, the practical data rate can still be promptly adapted by such a adaptive
strategy.
2. The other case occurs when a mobile station is just eavesdropping. In wireless communica-
tion, a mobile station can sniff all wireless signal within its capture range through its antenna
because the wireless medium is unguided in essence, not like point-to-point in wired net-
work [35]. Also, IEEE802.11 requires that each mobile station must listen to any flying frame
to determine whether this packet is addressed to itself or not, unless the station is in power
save state. Therefore, when a mobile station is filtering the received packet, even though it is
not the receiver station, it can still get the channel condition information between itself and
the packet sender. Therefore, the data rate of wireless channel can be adapted. Each station
in power save mode still needs to wake up for beacon frame periodically. Thus, even in this
Adaptive Rate Adaptation technique, periodic beacon frame is still necessary and helpful to
estimate the channel condition.
For instantaneous rate adaptation, if the rate is estimated per frame, the data rate might fre-
quently fluctuate due to fast channel condition variation, if only the latest single received frame is
29
used to the predict channel data rate for the next transmission. This happens especially when a mo-
bile station is experiencing the ping-pong effect in handoff where the data rate might iterate between
two levels of rate. It results in retransmissions. Multiple retransmissions definitely hurt the network
performance. Therefore, to solve the above rate fluctuation problem, the data rate should not only
be adjusted per frame, but also adaptively adjusted based on multiple history frames. Namely, it is
more important to predict the trend of the channel condition variation to adjust data rate before the
channel changes than just the instantaneous rate.
The rate adaptation core procedure in Adaptive Rate Adaptation is still the same as in Rate
Adaptation with Beacon strategy in Section 2.1.1. The only difference is an adaptive coefficient
introduced to smooth the data rate on wireless channel with history rate information.
One low pass filter ? is introduced in the channel statistic calculation:
ChanStatt = (1??)?ChanStatt?1 +??ChanelStatistics (2.1)
(0 < ? < 1)
It can also be expressed as:
ChanStatt = ChanStatt?1 +??(ChannelStatistics?ChanStatt?1) (2.2)
Here, the ChanStat is the cumulative prediction of potential channel status. It is used to pre-
dict the channel variation trend. ChannelStatistics is the instantaneous channel status, which is
calculated from the frame just received.
30
? is not a constant: it is dynamically updated as following:
? = ChanStat?ThresholdlowThreshold
high ?Thresholdlow
(2.3)
Here Thresholdlow and Thresholdhigh are the corresponding channel statistic thresholds for
rate estimation at each data rate level determined by physical hardware. These thresholds vary for
different data rates. For instance, ? is the low threshold for 5.5 Mbps. if the 2 Mbps and 5 Mbps
are two neighbor data rate levels in our data adaptation, ? also is the high threshold for 2 Mbps.
From the Formula 2.3, as the cumulative channel signal strength ChanStat approaches to
Thresholdhigh, ? increases, and thus instantaneous channel signal strength contributes more to
the adapted rate. This helps data rate adaptation quickly increase to higher data rate levels if more
frames are transmitted successfully under good channel conditions. This cumulative prediction can
also alleviate rate fluctuation in case of heavily fluctuating channel conditions, for example during
a handover. Therefore, the channel data rate is smoothed to a certain degree.
Adaptive Rate Adaptation operates with all sensed frames, including both broadcast control
frames like beacon and data transmission packets. Thus, the algorithm for Adaptive Rate Adaptation
evolves from algorithm for Rate Adaptation with Beacon as following.
When a frame is received:
b = constant;
Index = GetFrameMacAddress();
ChannelStatistics = GetStatFromPhy();
Threshold h = GetCurrentHighThreshold(Rate);
Threshold l = GetCurrentLowThreshold(Rate);
a = b*(ChanStat?Threshold l)/(Threshold h?Threshold l)
ChanStat = ChanStat+a*(ChannelStatistics?ChanStat);
31
if (ChanStat > ThresholdRate 11)
Rate = 11Mbps 10
else if (ChanStat > ThresholdRate 5.5)
Rate = 5.5Mbps
else if (ChanStat > ThresholdRate 2)
Rate = 2Mbps
else{
Rate = 0Mbps;
Log(signal is too weak. No channel
to destination mobile station);
}
20
RecordRateToTable(Rate, Index);
2.1.3 Basic Rate Retransmission
It is impossible for a rate adaptation scheme to accurately predict the actual data rate all the
time. Namely, there are definitely mismatches between the predicted data rate and the actual data
rate that the channel supports throughout an entire transmission. In such case, the receiver does
not successfully receive the data packet, therefore does not generate the acknowledgement. But the
sender is waiting for an acknowledgement to estimate the actual data rate for the next transmission.
A deadlock happens in this scenario. The only way to avoid such deadlock is to retry the same frame
at a lower data rate. But, minimizing the retransmissions after a transmission failure is not trivial.
Thus we propose Basic Rate Retransmission that can efficiently address the above problem. When
a sender fails to transmit a frame, the sender does not retry the transmission at the same data rate
32
used in the failing transmission, because the channel condition might have deteriorated. Instead, it
retries at the basic data rate just as for RTS/CTS frames, at which the receiver can certainly receive
the packet, if it is still in the communication range. The reason we retry directly at basic rate (and
not at the next lower level rate), is to avoid more failures. For example, if a transmission fails at
11 Mbps and the channel can only support the 2 Mbps basic rate temporally, the transmission at
5.5 Mbps, will still fail. But, the frame at 2 Mbps data rate is still able to be decoded, even in
case that the channel condition is robust enough for 5.5 Mbps. Then, when the sender catches the
acknowledgement frame for the basic rate data frame, the sender is able to adapt its instantaneous
data rate for next frame transmission based on the channel information of acknowledgement frame.
With this strategy, the transmission is immediately recovered with a retransmission at the basic
data rate. The number of retransmissions after a transmission failure can be reduced to only one.
Basic Rate Retransmission improves the network performance especially when network load is
heavy, because multiple retransmissions result in longer delay between two successful consecutive
transmissions due to the binary exponential backoff in MAC protocol. It should be stated that
although this variant can be combined with the previous two mechanisms that we propose, it also
can work individually with any other rate adaptation strategy to minimize the retransmission in case
of frame loss.
2.2 Performance Evaluation
2.2.1 Simulation configuration
The simulation is performed on ns-2 [36] version 2.29 for both WLAN and ad-hoc modes.
Only three levels of data rates are chosen in simulation: 11 Mbps, 5.5 Mbps and 2 Mbps, among
which 2 Mbps is defined as the basic rate. These simulations use two-ray ground model [32] as
33
 1.1e+07
 5.5e+06
 2e+06
 30  32  34  36  38  40
Data Rate (bps)
Time (s)
Data Rate in Sender Adaptive Auto Rate
Figure 2.1: Data Rate Adaptation
channel fading. All motion scenarios are generated by CMU mobile scenario program ?setdest? in
ns-2 package. And all traffic flows for ad-hoc network simulation are generated by CMU scripts
?cbrgen.tcl? in ns-2. In the following result figures, we mainly compared our mechanism with ARF
proposal unless there is special explanation.
2.2.2 Data Rate Smoothing
Compared to the rate fluctuation in ARF, the data rate does not vibrate widely with our pro-
posed strategy. The result can be observed from Figure 2.1.
2.2.3 Throughput performance
We separately evaluate the performance of rate adaptation with beacon only technique and
adaptive rate adaptation technique. The improvement for WLAN network is really dramatic, as
illustrated in Figure 2.2 and in Figure 2.4. Figure 2.2 represents the improvement for multiple
34
160%
140%
120%
100%
80%
60%
40%
20%
 5  7  9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39
Throughput Improvement(%)
Nodes
Figure 2.2: multi-node Rate Adaptation with only Beacon Frame
nodes operating in rate adaptation with only beacon frame. Figure 2.4 shows the improvement on a
network with multiple nodes with different fixed adaptive coefficients. In both figures, the X-axis
represents the number of nodes (including one access point) in an area of 100x100. The Y -axis
is the throughput improvement by percentage(%). As network density increases, more than 100%
improvement can be achieved. However, the Figure 2.3 shows that BARA with adaptive coefficient
in formula 2.3 does not perform so well as with constant coefficients as illustrated in Figure 2.4.
Figure 2.5 shows the improvement from data rate adaptation with only beacon frame in Ad-
Hoc network mode. The X-axis represents the number of nodes in the networks and the Y -axis
represents the throughput improvement by percentage. There are 3 scenarios for different network
sizes in this figure: 100x100, 150x150 and 200x200. As can be observed in Figure 2.5, the improve-
ment increases as the network density increases. It is because BARA adapts its data rate with the
proper signal strength (or communication distance) regardless of frame losses from collision. But
35
40%
30%
20%
10%
 0
 7  9  11  13  15  17  19
Throughput Improvement(%)
Nodes
Figure 2.3: multi-node in BARA in WLAN
50%
40%
30%
20%
 7  9  11  13  15  17  19  21  23  25  27
Throughput Improvement(%)
Nodes
coef=0.2
coef=0.4
coef=0.6
coef=0.8
Figure 2.4: multi-node in BARA with Coefficients
36
60%
50%
40%
30%
20%
10%
 0
 12  16  20  24  28
Throughput Improvement(%)
Nodes
100x100
150x150
200x200
Figure 2.5: Rate Adaptation with only Beacon Frame in Ad-Hoc network
ARF strategy is impacted extensively by frame losses. When the network density increases, so does
frame collision. Thus, BARA can achieve more improvement.
The simulation result for BARA with different constant coefficients in Ad Hoc network is il-
lustrated in Figure 2.6. The X-axis denotes the number of nodes in the network area of 100x100
and the Y -axis represents the throughput improvement. The different results lines in Figure 2.6
show the result for different coefficients used in BARA adaptive rate adaptation mechanism. From
Figure 2.6, we can observe that, unlike in WLAN mode, BARA with constant coefficient is outper-
formed by BARA with adaptive coefficient of formula 2.3. Also, we can observe that the different
fixed coefficients do impact on the improvement, the result of coefficient of 0.3 is better than other
four counterparts.
37
80%
60%
40%
20%
 4  8  12  16  20  24  28
Throughput Improvement(%)
Nodes
coef=0.1
coef=0.3
coef=0.5
coef=0.7
coef=0.9
Adaptive Coef
Figure 2.6: multi-node in BARA with Coefficients in Ad-Hoc
Delay Jitter Improvement:
The delay jitter improvement is shown in Figure 2.7, in which only one access point (AP)
and one mobile station communicate with each other with continuous CBR traffic. In this figure,
the X-axis represents the two mechanisms that are compared and the Y -axis is the percentage of
improvement. It can be observed that: although the jitter improvement by BARA with only adaptive
coefficient mechanism (SAAR in figure)is not noticeable, only a little more than 10%, there is still
marginal improvement by Basic Rate Retransmission (BRR in figure). It can improve the delay
jitter as much as 25% for station. This supports our statement on Basic Rate Retransmission for
improvement on delay and jitter because it minimizes the delay to just once retransmission.
38
SAAR
BRR
0
5
10
15
20
25
30
Station
Improvement
Domain
Delay Jitter Improvement
Figure 2.7: Delay Jitter Improvement by SAAR/BRR
2.3 Discussion
Two key strengths of BARA are: 1) the exploit of periodical and mandatory beacon frames in
rate adaptation without introducing any extra control frames overhead and 2) the basic rate technique
to reduce the number of retransmissions in loss recovery. However, BARA is based on the SNR that
is studied not to be a good channel indicator in practice. Therefore, although the simulation shows
its benefits, its implementation and application in the real world is limited. Also, BARA does not
have any functionality to diagnose the frame loss cause in composite lossy environments.
39
CHAPTER 3
LDRA: LOSS DIFFERENTIATED RATE ADAPTATION
Although BARA estimates the transmission rate without introducing overhead, like its many
peer schemes, it does not have any loss differentiation capability. To integrate such a loss diagnosis
ability, we propose a rate adaptation scheme Loss Differentiated Rate Adaptation (LDRA). It differ-
entiates the frame loss cause by retransmitting the lost frame at the basic rate directly. Note that
LDRA works for IEEE 802.11 in infrastructure mode as well as in infrastructureless (ad hoc) mode.
In this chapter, we first discuss the details of the scheme LDRA. Then we justify the use of the
basic rate retransmission technique used by LDRA. Finally, its performance evaluation is presented.
3.1 Design of LDRA
LDRA mainly consists of three components: (1) data rate estimation using Signal-to-Noise
Ratio (SNR) from the beacon, (2) data rate selection for retransmissions after a frame loss, and
(3) frame loss differentiation with appropriate actions for each type of frame loss. The following
presents each in order.
3.1.1 Rate Estimation
The rate estimation in LDRA is similar to the mechanism we adopt in BARA in Chapter 2.
In an IEEE 802.11 infrastructure network, a station that is associated and synchronized with its
access point knows the beacon interval. Each station periodically listens for a beacon frame that
can be used to measure the channel conditions through the signal-to-noise ratio (SNR), the received
signal strength (RSS), the frame loss rate, or the error bit rate. Based on such collected information,
40
the station estimates the most appropriate data rate to communicate with the source of the beacon.
The smaller is the beacon interval, the more accurate is the estimation as channel conditions would
less drastically change. This is particularly true for mobile nodes at low speed or stationary nodes
like mesh networks. Even if the beacon interval is comparably large, this estimated rate is still
more appropriate than a randomly selected or ?guessed? initial data rate at the beginning of the
transmission.
A supplement to the beacon estimation is to take all communication frames into consideration
for adaptive data rate adaptation after two stations start their communication. Such a strategy can
provide more accurate estimation if there are multiple transmissions within a beacon interval.
When SNR is collected from the physical layer, LDRA adjusts the data rate Rn such that
Rn = ? ?Rn?1 + (1 ? ?) ? r where r is the instantaneous rate estimated from the SNR. When
? is a constant, this equation is similar to Pavon and Choi [5]. We use an adaptive ? such that
? = ?? Rn?RlowRhigh?Rlow and ? is a constant from 0 to 1. Rlow is the SNR low threshold for a given data
rate (e.g. 5.5 Mbps); and Rhigh is the SNR high threshold for the same data rate.
3.1.2 Frame Loss Differentiation:
Since no data rate adaptation scheme is perfect, the sender may transmit at an overoptimistic
data rate, leading to frame losses. In practice, due to the sparse of RTS/CTS, a data frame can also
be lost from transmission collision. A frame loss may hint to decrease the data rate. In ARF [2]
and other frame loss based rate adaptation schemes, the number of lost frames or the frame loss
rate determine the data rate. ARF decreases the data rate whenever two consecutive frames get lost,
no matter what caused the frame loss. However, a lower rate would unduly hurt performance if the
41
frame loss was due to a collision. Thus, it is critical to determine the cause of a frame loss and take
appropriate actions in a data rate adaptation scheme.
LDRA exploits the retransmission (after a loss) at the lowest rate technique to accurately diag-
nose the cause of a frame loss (collision or channel degradation). When a frame loss occurs for the
very first time, the sender retransmits the lost frame at the lowest data rate, instead of the same rate.
Such retransmission allows the discrimination based on the following cases:
? If the receiver is still within the radio range, then the receiver would most likely receive this
retransmitted data frame in case of channel degradation because of the lowest data rate. Thus
the sender can receive the acknowledgement and correctly infer that the loss is due to channel
degradation.
? If the retransmitted frame is lost, and no beacon is received during the latest N beacon periods,
the sender can correctly infer that the receiver is out of range (for the current channel quality).
? If the retransmission at the lowest data rate is lost, but a beacon frame has been received in
the latest N beacon periods, then the sender can infer that the loss is rather due to collisions.
After diagnosing the loss, LDRA will take the appropriate actions for each type of loss as
explained in the next section.
3.1.3 Reactions to Frame Loss:
After a frame is lost, three reactions are proposed to improve network performance upon dif-
ferent diagnosed frame loss causes.
Frame loss due to channel degradation: Since the loss is not due to a collision, then the
sender should not double its contention window as stipulated in IEEE 802.11 [1]. Moreover, based
42
on the frame exchange retransmitted at the lowest rate, the sender is able to estimate the new appro-
priate data rate.
Frame loss due to out of range of the receiver: The sender will immediately pause its trans-
missions until it detects a new beacon frame. This results in two benefits: 1) it eliminates unneces-
sary network traffic and therefore reduces collisions (or hidden/exposed terminal problems), and 2)
it saves power.
For the frame loss identified from a collision: As usual, the sender will invoke, for good
reason, the binary exponential backoff mechanism, but will not decrease the data rate: a lower data
rate does not remedy or alleviate collisions. On the contrary, a lower data rate increases signal
coverage and thus may worsen interference and collision. Therefore, the sender should maintain the
current data rate after a collision. This is a critical difference from traditional data rate adaptation
algorithms without loss differentiation.
The core algorithm of LDRA is illustrated in the flow chart in Figure 3.1.
3.2 Justification for Retransmissions at the Basic Rate
In IEEE 802.11b [25], there are four modulation schemes: BPSK (1Mbps), QPSK (2Mbps),
CCK5.5 (5.5Mbps), CCK11 (11Mbps). We analyze the expected time required to successfully
transmit a frame for each modulation (each rate) in different signal-to-noise ratio (SNR) environ-
ments. In IEEE 802.11, the Frame Error Rate (FER) is associated with a frame length of 1024
bytes. If the bit error rate (BER) p is very small and losses are independent, then the corresponding
FER can be approximated as p ? 1024 ? 8. The expected number of transmissions for a frame to
be successfully delivered is 11?FER. The expected transmission time at the rate bw is 1(1?FER)?bw.
Based on the bit error rate data reported by Wu [37], Figure 3.2 illustrates the relationship between
43
N
Y
N
Y
Frame
Received
Estimate Rate from RSSI
Frame 
Lost
Retransmitted before?
Save current date rat DR
Use lowest data rate to 
retransmit
No exponential backoff
Beacon received?
Restore data rate DR
Exponential backoff
Retransmit
frame
Pause transmission 
and monitor beacon
Figure 3.1: LDRA Algorithm Flow Chart
44
expected transmission time and SNR for different modulations. The x-axis represents the SNR, and
the y-axis is the expected transmission time. Bianchi et al. [38] observed that the SNR in outdoor
environment is usually less than 6 db for 802.11b/g. From Figure 3.2, it can be observed that, if
a frame is transmitted at 5.5 Mbps or 11 Mbps in an environment with SNR less than 6 db, it has
to be retransmitted so many times that transmissions are unlikely to succeed. But for the lowest
rate of 1 Mpbs or 2 Mbps, a frame will successfully be transmitted almost every time in low SNR
environment. Thus, in traditional retransmission schemes, even if a frame is lost due to channel
fading with a very low SNR, CSMA/CA always assumes the loss to be due to collision. It backs off
and retransmits the frame at the same high data rate again for several times. As illustrated by Fig-
ure 3.2, this retransmission strategy is wasteful and doomed for frame losses resulting from channel
degradation. Thus, it is important to retransmit at the lowest data rate and differentiate the cause of
a frame loss.
3.3 Performance Evaluation
In this section, we mainly evaluate the network performance improvement by LDRA over other
existing algorithms with composite frame losses from wireless transmission collision and channel
degradation.
3.3.1 Simulation Configuration
LDRA is simulated in IEEE 802.11b WLAN and ad hoc modes with ns-2 [36] (version 2.29).
Three data rates are used: 11 Mbps, 5.5 Mbps and 2 Mbps. The proposed scheme is compared
with ARF [2] and Adaptive Auto Rate [5] through simulations of a single flow and then multiple
45
 0
 1
 2
 3
 4
 1  2  3  4  5  6  7  8  9  10 11 12 13 14
Expectation of Transmission
SNR
1 Mbps
2 Mbps
5.5 Mbps
11 Mbps
Figure 3.2: Expected Transmission
46
competing flows. All wireless stations are within a 500mx500m area that is covered by the signal
of one access point located at the center.
We simulate the channel degradation with the two-ray ground fading model. The two-ray
ground fading model [32] is a large scale fading model. According to this model, the signal received
is composed of two components: the line-of-sight through the direct path and the wave reflected by
ground. In general, the power of the received signal at a location is proportional to the exponent of
the transmission distance, which follows:
Pr = Pt? 1d4 (3.1)
where Pt is the power of the signal at the transmitter; ? represents the antenna factors, such as the
heights, the antenna gains; and d is the transmission distance. With the two-ray ground fading, SNR
is constant at the receiver if both the receiver and the transmitter are static at some locations.
3.3.2 Data Rate Adaptation
At first, LDRA is compared with ARF to show LDRA?s ability to converge to a steady data rate.
The first experiment consists of one mobile client node with one access point. The client node moves
around an area such that 5.5 Mbps is the most appropriate data rate. Figure 3.3 plots the results:
the x-axis represents the time and the y-axis is the data rate. Figure 3.3 shows, as expected, that
ARF frequently changes the data rate because it blindly makes adjustments regardless of wireless
channel conditions. Under the same conditions, the proposed scheme, LDRA, remains steady at the
appropriate data rate of 5.5 Mbps.
47
11
5.5
 0
 4  4.01  4.02  4.03  4.04  4.05
Data Rate (Mbps)
Time (s)
ARF
LDRA
Figure 3.3: Rate Adaptation Comparison
3.3.3 Throughput Improvement
We define throughput improvement of LDRA over some scheme X as ThroughputLDRA?ThroughputXThroughputX .
UDP CBR is used as the traffic in most experiments, except the last case testing TCP flows.
Figure 3.4 plots the throughput improvement over ARF in an experiment with varying the
density of mobile nodes at different velocities in a WLAN network. The x-axis is for velocity
and the y-axis represents the network throughput improvement with different node densities. As
shown on the figure, although the velocity impacts throughput, it does not significantly impact the
improvement. The improvement sharply increases with nodes density. This is due to LDRA?s ability
to correctly distinguish a frame loss due to collision from that due to wireless channel fading. As
collision increases in denser networks, LDRA exploits its ability to correctly diagnose collision
losses and to maintain the original data rate. With ARF, the node unduly decreases the data rate. As
collision increases, LDRA performs better than ARF, leading to a better throughput improvement.
48
360%
320%
280%
240%
200%
160%
120%
80%
40%
 0
 2  4  6  8  10  12  14
Improvement
Velocity (m/s)
12-node
20-node
28-node
36-node
40-node
Figure 3.4: Throughput Improvement at Different Velocity
The relationship between throughput improvement and network density is even stronger from
the simulation results depicted in Figure 3.5. In this scenario, the mobile nodes move at random
velocity in an ad hoc network. The x-axis and y-axis respectively represent the number of mobile
nodes in network and the throughput improvement.
We also compare the throughput from LDRA with that from work AAR by Pavon and Choi [5]
in ad hoc network. Figure 3.6 illustrates the results. Note that the benefits from LDRA are more
remarkable as the network density increases. In low network density, AAR scheme [5] performs
better than LDRA, because LDRA spends time on the loss differentiation that is not so necessary
with little composite loss. But in a high node density environment, LDRA outperforms it, due to the
ability to differentiate losses.
Another set of experiments were carried with TCP flows. Different numbers of TCP flows are
tested for LDRA and ARF. The total network throughput for all TCP flows is used to measure the
improvement. The simulation results are plotted in Figure 3.7. The x-axis represents the number of
49
200%
160%
120%
80%
40%
 0
 4  8  12  16  20 24  28  32  36  40
Improvement
The Number of Nodes
Figure 3.5: Improvement with Network Density
110%
90%
70%
50%
30%
10% 0
-10%
-30%
-50%
 12  16  20  24  28  32  36  40
Improvement
The Number of Nodes
Figure 3.6: Improvement with LDRA vs Adaptive
50
110%
100%
90%
80%
70%
 2  4  6  8  10
Improvement
The Number of Nodes
Figure 3.7: Throughput Improvement in TCP
TCP flows. The y-axis represents the overall network throughput improvement of LDRA over ARF.
This figure shows a dramatic improvement up to almost 100% for different scenarios.
3.3.4 Delay Jitter Improvement
Figure 3.8 shows a significant improvement of delay jitter in WLAN by LDRA over ARF. Delay
jitter is defined as the time difference in delay between two successive frames. We collect the maxi-
mum delay jitter for each scheme to compute the delay jitter improvement as DelayJitterARF?DelayJitterLDRADelayJitterLDRA .
The experiment involves one mobile client node and one access point with a UDP flow. The x-axis
and y-axis respectively represent the velocity and the delay jitter improvement. Basic Rate Retrans-
mission technique substantially contributes to this improvement because the number of retransmis-
sions is minimized by LDRA. LDRA induces less variability of delay after a frame loss and therefore
yields a lower delay jitter than ARF.
51
110%
100%
90%
80%
 2  4  6  8  10  12  14
Improvement
Motion Speed (m/s)
Figure 3.8: Delay Jitter Improvement
3.4 Discussion
LDRA benefits from its loss diagnosis ability. It also recovers lost frames promptly with the
basic rate retransmission technique. As BARA does, LDRA also relies on SNR for rate adaptation,
which restricts its implementation to evaluate in practice. Therefore, an effective rate adaptation
scheme based on frame loss is challenging but highly desirable to implement and evaluate in the
real world for more sense in research.
52
CHAPTER 4
ERA: EFFECTIVE RATE ADAPTATION
To identify a reasonable, implementable, effective, and practical rate adaptation scheme with
loss diagnosis, we investigate most recent rate adaptation schemes. As presented in Section 1.3.1,
we identify their anomalies in the implementation. Based on these observations and design princi-
ples in Section 1.4, we design the scheme Effective Rate Adaptation (ERA).
In order to address the challenge of not using RTS/CTS frames in most scenarios, we take
advantage of the fragmentation mechanism to assess the channel after a frame loss, to diagnose
the cause of the loss, and to develop an efficient retransmission strategy for loss recovery. Also,
to efficiently adapt rates in collision free environments, we introduce the binary backoff concept
similar to that in AARF, but different in counting the number of successfully delivered data frames.
In this chapter, we first discuss the rationale to exploit fragmentation mechanism in ERA. Then
we detail the design of this scheme. Afterwards, we partition the performance evaluation into two
sections: the first section presents the results from simulation; the second section discusses the
experiments on a Linux based tested including the implantation platform, the experimental envi-
ronments and methodology, and the results from extensive experiments conducted on the testbed
implemented with ERA and selected most recent rate adaptation schemes.
4.1 Rationale
This section details the rationale of using fragmentation technique to serve loss differentiation,
fast recovery purpose in our proposal.
53
Frag2Frag1
ACK1 ACK2
NAV in Frag1
NAV in ACK1SIFS
Figure 4.1: NAV of fragments in IEEE 802.11
4.1.1 Fragmentation in IEEE 802.11
Fragmentation is standardized in IEEE 802.11 that is usually used for packets too large to load
in an MAC data frame or unfit for current channel conditions. In a collision dominated environment,
a long data frame may yield poor performance, but fragmenting it into fragments of optimal size
may dramatically improve performance, although the per-bit overhead is increased. Figure 4.1
illustrates the transmission of fragments stipulated in IEEE 802.11. Consider a sender station splits
a frame F into two fragments Frag1 and Frag2. Fragment Frag1 bears a network allocation vector
(NAV) NAV1 that reflects the time duration that the sender requires to complete the transmission
of the second fragment Frag2 (till the reception of ACK2), therefore the full frame F . Due to the
virtual carrier sense mechanism, all stations other than the receiver that hear the fragment Frag1
will remain silent for duration NAV1. The receiver acknowledges with ACK1 that bears a new
NAV also reserving the complete transmission of the second fragment. Such reservation completes
till the completion of all fragments of the full frame F. Therefore, in an environment with collision,
if the first fragment is successfully transmitted, the channel is cleared for all remaining fragments of
that frame. Namely, the strength of fragmentation is that the probability of collision for the whole
frame is reduced to the probability of collision of its first fragment.
54
4.1.2 Fragmentation and RTS/CTS
When a frame is fragmented into several pieces, each of them is needed to assemble with a
MAC header. Therefore, fragmentation yields more per-bit overhead to data payload. At first glance,
fragmentation appears to incur more overhead than RTS/CTS control frames because RTS/CTS are
shorter than the MAC header. However, with detail investigation, this impression is not correct
for following reasons. First, the lead fragment is transmitted at the same rate as a data frame,
instead of the basic rate at which RTS/CTS are transmitted. The following example gives a more
clear view. In IEEE 802.11g, RTS is sent at the basic rate 6 Mbps while the median rate is 24
Mbps. Therefore, the time to transmit a RTS (20 bytes) is equal to the time to transmit an 80-byte
(= 20?24?6) data frame at 24 Mbps. Deducting 34-byte of the MAC header and CRC, the time
is still enough for a fragment carrying 56 bytes data payload. Another benefit of transmitting the
short (lead) fragment at the data frame rate after a frame loss is discussed later in Section 4.2.2.
Second, the transmission in IEEE 802.11 operates in time slots: namely, every transmission uses
up a whole slot time even the transmission is over at the beginning of this time slot. Thus, when
we calculate the transmission time, we should computer the number of time slots occupied, rather
than the continuous nano-seconds (or even smaller time units). In 802.11g, a time slot lasts for 20
?s. A RTS plus PLCP header requires about 50 ?s to be transmitted at the basic rate 6 Mbps in
OFDM coding. The transmission time of a RTS is rounded up and equal to 3 slots, which is enough
to transmit about 77 bytes MAC data payload plus the MAC layer header at the intermediate rate 24
Mbps. In conclusion, a short fragment transmitted at a normal rate often incurs less overhead than
RTS/CTS.
55
4.1.3 Numerical Analysis of Fragmentation
To analytically demonstrate the strengths of fragmentation in a collision dominated environ-
ment, first we compute the probability for a frame to collide as a function of its length. Then, we
will compute the ratio of the probability to collide for a whole frame over the probability for a
fragmented frame. Consider an IEEE 802.11 network with M stations under saturated traffic: each
station has a frame available to transmit all the time. Suppose all data frames are of equal length and
the transmission of a frame occupies N time slots. Let p be the stationary probability that a station
transmits a frame in a randomly chosen slot. p can be obtained using Bianchi?s analysis [39]. Now,
suppose a station is transmitting.
Let q denote the probability that no other station transmits in any generic slot (K) occupied by
the frame being transmitted. q can be deducted as following:
q = (1?p)M?1 (4.1)
For the frame in transmission not to collide, all N slots occupied by the frame should not
overlap with any transmission from other stations. Therefore, the probability that this frame is not
in collision should be:
r = qN = (1?p)N(M?1) (4.2)
Then, the probability that this frame is collided can be calculated as:
P = 1?r = 1?(1?p)N(M?1) (4.3)
56
When a frame is fragmented into two parts: one is very short, the other is the remainder. If the
short fragment occupies S slots, the probability of this fragment to collide is 1?(1?p)S(M?1). As
noted above, with fragmentation in IEEE 802.11, the probability of collision for the whole frame is
reduced to the probability of collision of its first fragment. Therefore, the collision probability ratio
for a whole frame over the same frame but fragmented is:
1?(1?p)N(M?1)
1?(1?p)S(M?1) (4.4)
With above analysis, it is convenient to computer the numerical benefit of the fragmentation.
Consider a WLAN of five contending stations (M = 5) and the data payload of a frame is one Kbyte.
After fragmentation, the first (lead) short fragment carries 20 bytes. In IEEE 802.11g, a time slot is
20 ?s. Taking into consideration the headers of PLCP, MAC, IP, and UDP, the data frame occupies
10, 20, and 74 slots respectively at transmission rates 54 Mbps, 24 Mbps, and 6 Mbps. Following
the same calculation, the short fragment occupies 2, 3, and 7 slots, respectively. Based on these
data and Equation 4.4, the collision probability ratio as a function of the transmission probability
p is plotted in Figure 4.2. The y-axis represents the collision probability ratio and the x-axis is for
the stationary probability p that a station transmits in a generic time slot. Bianchi [39] shows that
the optimal throughput performance for a small M occurs at very small p. The binary exponential
backoff mechanism in IEEE 802.11 does keep p small. As we can observe from Figure 4.2, when
p is small (less than 0.15, shown in the inner magnified figure), the probability for a long frame to
collide is several times that of a fragmented frame. We can conclude that the probability for a frame
to collide in contention dominated environments is dramatically reduced by using fragmentation.
57
 2
 4
 6
 8
 10
 12
 0  0.1  0.2  0.3  0.4  0.5  0.6  0.7  0.8  0.9  1
Probability Ratio
Transmission Probability
54 Mbps
24 Mbps
6 Mbps
 2
 4
 6
 8
 10
 12
 0  0.03  0.06  0.09  0.12  0.15
Figure 4.2: The Probability Ratio of Successful Frame Delivery
58
4.2 Design of ERA
ERA is purposely designed upon frame loss, since SNR and RSSI do not show strong correla-
tion with channel conditions in complex environments. It is a ?winning streak? scheme that counts
the number of consecutive data frames transmitted successfully for rate increase to exploit potential
better channel conditions. ERA accurately differentiates frame losses with fragmentation mecha-
nism and promptly adjusts rate if a loss is diagnosed from channel degradation. In the following,
we discuss each of these features.
4.2.1 Channel Assessment
One consideration deserving special effort for rate adaptation is the method to exploit poten-
tially better channel conditions. Channel exploit for frame loss based schemes can only be achieved
through rate increase. It is double-edged: 1) if the rate is increased more frequently than the channel
condition upgrades, frame loss also increases as if it is from channel degradation; 2) if the rate is
adjusted less frequently, the better channel condition is not fully exploited. It is impossible for a
rate adjustment to keep the same pace as the channel condition varies. However, to achieve optimal
network utilization, a rate adaptation should identify a delicate balance between these two ?edges?.
ERA exploits the potential better channel condition by using the ?winning streak? mechanism with
an adaptive threshold. Before the detail of the rate increase in ERA is presented, a notion of trans-
mission counter is introduced first for convenience in explanation.
The transmission counter Tr is used to assess the signal stability of the channel in communica-
tion. Tr used by the sender records the number of consecutive successfully transmitted data frames
at some rate. Tr increments upon a successful transmission. It is reset to 0 for another rate under
two scenarios: 1) a transmission failure is diagnosed due to channel fading; 2) the transmission
59
Frame
Sequence
Loss
Loss Cause
Ts Counter 1 2
X
Col Fad
2 3 0
X
1
At Rate A
At Rate B
Col --- Collision
Fad --- Fading
0
Figure 4.3: Consecutive Transmission Counting
succeeds after a rate increase with consideration that channel condition is good enough for higher
rates. But Tr is not impacted by any diagnosed collision loss. The detail counting process of Tr
is plotted in Figure 4.3. Let Tr = 2 after two consecutive successful transmissions at data rate R.
Suppose that the third frame fails and the frame loss is diagnosed as a collision, then Tr remains
2. Furthermore, Tr is incremented after the third frame is recovered (as the forth) at rate R: the
channel is still good enough at rate R! However, the fifth frame fails and the cause is diagnosed as
from channel degradation, Tr is reset for the lower rate in a new counting cycle.
To balance the ?double-edge? of rate increase, ERA introduces an adaptive rate increase thresh-
old Ts, which is similar to that in AARF. In channel exploit, ERA increases the rate when the trans-
mission counter Tr reaches the adaptive threshold Ts. Such an increase is based on the inference
that, since there are Tr consecutive data frames transmitted successfully (excluding the collision)
at current channel condition, the channel condition might be good enough to support higher rates.
To achieve the balance, Ts should not be too high so that a sender can quickly reach the highest
available rate and should not be too small to avoid rate oscillations and frequent losses due to overly
optimistic increases. The initial value of Tr is set to 8 in our testbed. To reduce the frame loss in
stable signal environment, the value of Tr is adaptively updated: if a transmission fails immediately
after a rate increase, Ts is doubled, up to 32 maximum. At the same time, the rate falls back to the
60
prior rate with the assumption that the prior rate is already the highest that current channel condition
can support.
4.2.2 Loss Diagnosis
In IEEE 802.11 wireless environments containing fast channel variation plus transmission col-
lision, the frame loss is inevitable. But different type of frame loss can not be treated with the same
solution. Therefor ERA achieves the loss diagnosis/differentiation with fragmentation mechanism.
Suppose a frame loss occurs at rate rfail. Let rprevious be the rate of the last successful trans-
mission before the current transmission failure. Two possible cases deserve consideration in loss
differentiation.
1. rfail > rprevious: This occurs only when the rate is increased from rprevious to rfail after
Tr consecutive successful transmissions. The immediate transmission failure might indicate
that the current channel condition can not support the new higher rate rfail. Therefore, it is
reasonable to conclude that the frame loss is likely due to overoptimistic rate increase to rfail:
the wireless channel condition can only support rate rprevious, but not rate rfail.
2. rfail = rprevious: In this case, previous transmissions succeeded at the same rate rfail, but
the current frame is lost. Therefore, the loss may be due to channel degradation as well
as collision. Loss diagnosis requires more delicate strategy. We assume that the channel
condition is fairly stable during the short loss differentiation and recovery process. This is
reasonable because that time is shorter than channel variation.
In order to further diagnose the loss, ERA splits the lost frame into two fragments by fol-
lowing the fragmentation technique in standard: a very short fragment and the other of the
remainder. First, the short/lead frame is retransmitted at the same rate rfail. The transmission
61
consequence directs the diagnosis. If the transmission is successful for this short fragment,
then the loss was most likely due to a collision. This inference is reasonable for two reasons:
1) the probability of successful delivery is much higher for a smaller frame in a collision prone
environment, 2) the probability of successful delivery is not significantly higher for a smaller
frame in a degraded channel environment. Otherwise, if the transmission of the short frag-
ment fails also, then the loss is likely due to channel degradation, but not certainly. Therefore,
further differentiation is required. Then ERA halves the rate to retransmit the short fragment.
For example, the rate is halved to 24 Mbps if rfail was 48 Mbps. Such a retransmission with
rate halving is repeated till the transmission succeeds, or the rate is decreased to the lowest
rate. If a retransmission at any halved rate other than the lowest rate is successful, the loss is
diagnosed from channel degradation. Otherwise, the loss is assumed due to severe collision.
The complete diagnosis procedure is illustrated in Figure 4.4.
A key feature of ERA in diagnosing the cause of a loss consists of using the current rate rfail
to retransmit the short (lead) fragment rather than using the basic (lowest) rate immediately
after the original failure 1. This feature improves the accuracy and speed in the loss diagnosis
in contrast with other schemes. Other schemes use short frames (e.g. RTS) sent at the basic
rate immediately after the original failure. If the transmission at the basic rate is successful,
it is equivocal if the transmission success is the result of the use of a lower (basic) rate (in
channel degradation) or the use of a short frame (in collisions).
1It refers to the first failure of a specific data frame, instead of the failure of any retransmission of this lost frame or
its fragments.
62
4.2.3 Prompt Recovery
The prompt and efficient recovery of a frame loss in ERA benefits from is accurate frame loss
diagnosis. The recovery has to consider three cases that result from loss differentiation.
? If the loss is diagnosed due to overoptimistic rate increase, namely the frame is lost immedi-
ately after rate increase, the rate falls back to the prior rate immediately and the rate increase
threshold Ts is doubled at the same time.
? If the loss is diagnosed due to collision, the rate remains. But the short (lead) fragment from
fragmentation combined with the binary backoff in the 802.11 standard should efficiently
address the problem.
? If the loss is diagnosed due to channel degradation, the halving-rate technique can identify
the appropriate new rate quickly for the degraded channel condition and recover the loss.
Unlike other rate adaptation schemes, ERA diagnoses the cause per loss: it differentiates the
loss upon each frame loss. Once it diagnoses the loss is due to channel degradation, it adjusts the
rate immediately, rather than waiting till some time later. This per loss diagnosis speeds up the
response to frame loss, recovers lost frames quickly and therefore improves the network utilization.
The complete and precise scheme of ERA is described in the flowchart in Figure 4.4.
4.3 Performance Evaluation on Simulation
We evaluate EAR on both network simulator ns-2 and a implemented Linux testbed. This
section only presents the result gathered from simulations.
63
N
Y
N
YN
NY
Update Number of Consecutive
Successful transmissions
(Tr++)
Tr >=
Threshold
(Ts)?
Increase rate
Threshold Ts =  8
Transmit
Initial rate = intermediate rate (24 Mbps in 802.11g)
Tr = 0
success?
Rate falls back
Was rate just
increased?
Fragment lost frame Was the
retranmission at
halved rate?
Rate for fragment is restored
Differentiated as from collision
Double Threshold
(Ts *= 2)
Halve rate for
fragments
Tr = 0
Tr = 0
YN
Frame was
fragmented?
YN
YIs the rate the
lowest?
Y
N
Frame was lost
& fragmented?
Y
N Rate was
halved?
Decrease rate
Differentiated as
from fading
Differentiated as
from collision
Figure 4.4: ERA flowchart
64
4.3.1 Simulation Configuration
All experiments are restricted to WLAN infrastructure networks. Experiments were carried
out with IEEE 802.11g MAC on simulator ns-2 [36]. We refer the physical layer parameters to
the Cisco Aironet 802.11a/b/g cardBus wireless LAN adapter [40]. Schemes ARF, CARA and our
ERA were chosen and implemented in ns-2 for comparison: ARF from the category without loss
differentiation; CARA from the category with loss differentiation but requiring RTS/CTS; and ERA
from the category with loss differentiation but without requiring RTS/CTS. The performance of
these schemes is evaluated in two cases: a static mesh network environment and a mobile network.
A set of experiments evaluated the impact of congestion level while another set evaluated the per-
formance in a collision free environment. Most simulations were conducted with multiple wireless
nodes. The static network topology of 16 client stations and one access point is shown in Figure 4.5.
These stations are within the radio coverage of the access point, but they do not necessarily hear
each other. Therefore the existence of hidden terminal depends on the network area size. To simu-
late a realistic environment, wireless channel fading is simulated with Ricean fading model [32] that
takes into account both distance fading and time varying channel fluctuations. Consequently, such
a simulation environment contains mixed losses from both channel fading and collisions. Another
simulation scenario was carried out with one client and two-ray channel fading model.
The performances of ARF, CARA, and ERA are respectively evaluated and compared under
different scenarios: strictly congested network (no losses due to channel degradation), strict channel
degradation (collision free), and the more usual case where mixed losses may occur due to channel
degradation as well as collisions.
Performance evaluation is conducted through extensive simulations using ns-2 network sim-
ulator. IEEE 802.11g [26] is used as the MAC layer because it has more predefined rates. For
65
Figure 4.5: Topology of 17 static stations
Simulator ns-2 v.30
MAC CSMA/CA DCF basic access
MAC data rates 6, 9, 12, 18, 24, 36, 48, 54 Mbps
Channel fading Two-ray ground or Ricean
Ricean fading factor (K) 4
Traffic UDP Constant Bit Rates (CBR)
Frame length 100, 500, 1000, 1500 Bytes
The short fragment length Same as RTS
Table 4.1: Simulation parameters
66
Topology Number of Stations Motion Model
?1 2 static
?2 2 random movement
?3 17 static
?4 17 random movement
Table 4.2: Simulation topologies
the physical layer, we use the parameters of Cisco Aironet 802.11a/b/g cardBus wireless LAN
adapter [40] and assume symmetric links. Table 4.1 summarizes the network configurations and
parameters used in these simulations; and Table 4.2 describes the main four network topologies
and the number of stations (including the access point) in each one. The traffic is always from the
stations to the access point.
Each result figure plots the data averaged from multiple runs with random staring time in
different evaluation environments. Each run of simulation is of 2-minute saturated UDP traffic.
We evaluate ERA in three environments: channel degradation dominated, collision dominated, and
composite (frame losses due to collisions as well as channel degradation). First, we present the
experiments made in a composite environment.
4.3.2 Composite Environments: Collision and Channel Degradation
First, we evaluate the presumed strength of ERA, i.e., its effectiveness to promptly recover from
losses. Then we measure the throughput (by Kframes/s) for the static network on Figure 4.5 and for
a network of mobile stations.
ERA Retransmission/Recovery Effectiveness
We measure the effectiveness by collecting the fraction of frames losses recovered after only
ONE retransmission. For example, if there are 100 losses and forty of them were recovered after
67
only one retransmission, then the fraction is 0.40. The experiments are conducted over a static
network with 16 stations and one access point located at the center as shown on Figure 4.5. We
use topology #3 (See Table 4.2). We adopt the Ricean fading model to induce dynamic channel
conditions. By varying the size of the network layout area, we get a variable of loss ratio due to
collision: the collision ratio is the number of frame losses due to collision over the total number
of frame losses. If the collision ratio is null, this means that the environment is collision free
(channel degradation dominated), which is emulated with only one client station. A strictly collision
dominated environment has a collision ratio of one, which happens when all the stations are so
close to the access point that there is no transmission failure due to channel fading even with Ricean
model. Figure 4.6 plots the fraction of recovered losses after only one retransmission on the y-axis
with the collision ratio on the x-axis. Under most conditions, ERA succeeds in recovering 80%
of the losses with only one retransmission of the whole lost frame and outperforms CARA under
all circumstances. In a channel degradation dominated environment (close to null collision ratio),
CARA does not recover quickly because it often addresses the loss as a collision.
For the same experiment, we also compute the mean of the number of retransmissions plotted
on the y-axis of Figure 4.7. The strength of ERA stems from its refined mechanism to diagnose the
cause of a frame loss and adopt the best strategy to recover. But for CARA, the success of RTS/CTS
at the basic rate can not indicate channel fading or collision.
Throughput for Static Networks
To evaluate ARF, CARA, and ERA under realistic channel conditions with both channel degra-
dation and collision, we use the Ricean fading model on a static network of 16 stations (see Fig-
ure 4.5) and vary the area size to adjust the congestion level. We use topology #3 (See Table 4.2).
68
 0
 0.2
 0.4
 0.6
 0.8
 1
 0  0.2  0.4  0.6  0.8  1
Fraction of retransmission at once
Collision ratio
ERA
CARA
Figure 4.6: Fraction of recovered losses with ONE retransmission
 1
 1.2
 1.4
 1.6
 1.8
 2
 2.2
 2.4
 0  0.2  0.4  0.6  0.8  1
Mean of retransmission
Collision ratio
ERA
CARA
Figure 4.7: The mean of retransmission
69
 0
 0.05
 0.1
 0.15
 0.2
 0.25
 30  60  90  120  150  180  210
Throughput (KFrames/s)
Length of the rectangular (m)
ERA
CARA
ARF
Figure 4.8: Throughput under both channel degradation and collision
CBR traffic with 1000 bytes packets is sent from the 16 stations to the access point. Figure 4.8 plots
on the y-axis the throughput achieved by ARF, CARA, and ERA, respectively. As we observe, ERA
performs better in heavily congested environments (in smaller areas). This is because ERA implic-
itly assumes the loss is due to collision at first (by transmitting the short fragment at the current
rate). Consequently, it favors the loss differentiation in collision dominated environments.
Throughput for Mobile Nodes
The throughputs of ARF, CARA, and ERA are respectively evaluated on a mobile network of
17 stations: all 16 client stations are mobile at random velocities to random destinations with short
pause between two consecutive movements in a 350mX350m area. The access point, located at the
center of the network , is static. We use topology #4 (See Table 4.2). The Ricean fading model is
used to simulate channel degradation. Table 4.3 shows the parameters used in these simulations.
All stations keep transmitting to the access point UDP CBR traffic.
70
parameter value
Network Area 350mX350m
Location of Access Point (175m, 175m)
Fading Ricean
Velocity 2 m/s to 30 m/s
Pause Time 1 second
Client Stations 16
Table 4.3: Network parameters for mobile network simulations
 0
 0.5
 1
 1.5
 2
 2.5
 500  1000  1500
Throughput (KFrames/s)
Frame Length (Bytes)
ERA
CARA
ARF
Figure 4.9: Throughput of mobile stations
The first experiment evaluates the throughput for all schemes with a CBR traffic with different
packet lengths: 500 bytes, 1000 bytes and 1500 bytes. Figure 4.9 plots the throughput of ARF,
CARA, and ERA for different packet lengths. The horizontal axis represents the packet length used.
With longer frames, there are more collisions, therefore ERA has more opportunities to deploy its
strength.
We also collect the adaptation transient dynamics for ARF, CARA, and ERA for the mobile
stations. Figure 4.10 displays three plots for ARF, CARA, and ERA. Each plot corresponds to a
71
 54
 48
 36
 24
 18
 12 9
 6
 0
 8  8.5  9  9.5  10
Data Rate (Mbps)
Time (s)
ARF
Channel Rate
 54
 48
 36
 24
 18
 12 9
 6
 0
 8  8.5  9  9.5  10
Data Rate (Mbps)
Time (s)
CARA
Channel Rate
 54
 48
 36
 24
 18
 12 9
 6
 0
 8  8.5  9  9.5  10
Data Rate (Mbps)
Time (s)
ERA
Channel Rate
Figure 4.10: Adaptation dynamics
two-second period of dynamics for a randomly chosen mobile client station. The x-axis is the time.
The y-axis shows the data rate in Mbps. Each plot presents two curves: the first curve labeled
?Channel Rate? (symbol ?) is the rate that the channel can support at that instant (assuming perfect
knowledge) and the second curve (symbol +) is the rate selected by ARF, CARA, or ERA. We
observe that in such conditions (mixed environment with both collision and channel degradation),
1) the volatile nature of the channel makes it difficult for any rate adaptation scheme to select the
optimal supported rate 2) the plot for ERA has more points (which means more frame transmissions)
than the two others (ARF and CARA) because ERA results in less congestion loss, and 3) ERA selects
a rate that is closer to the optimal achievable rate. CARA outperforms ARF mainly due to its ability
to reduce collision with RTS frames.
With above extensive simulations on different network topologies and configurations, ERA
robustly exhibits dramatic performance improvement. These simulation results illustrate ERA?s ef-
fectiveness in composite environments (channel degradation and collisions). In order to understand
better ERA, we evaluated it separately in a strictly channel degradation dominated environment and
then in a strictly collisions dominated environment.
72
4.3.3 Channel Degradation Dominated Environment
For these experiments, we use topology #1 (See Table 4.2) with one static station at a con-
stant distance from an access point. First, we evaluate the throughput performance throughout the
experiments of ARF, CARA, and ERA in stable channel environments. Second, we measure the
throughput for these three schemes in an environment with dynamic channel conditions simulated
with the more general Ricean fading model. Finally, we measure the impact of packet length on
the throughput of those three schemes for a station at 300m from an access point. Due to the space
limitation, we only present the result gathered in the stable environment and leave the result of the
other two scenarios in our technical report [41].
Stable Channel Conditions
In general, a user sits at a desk and has a long work session where a given constant rate will
be most often supported. We somewhat create such environment with only one fixed station and
one access point. The two-ray ground fading model is used to ensure that a given constant rate
is supported: the supported rate under a two-ray ground fading model depends only on the com-
munication distance. Figure 4.11 plots on the y-axis the throughput achieved by ARF, CARA, and
ERA respectively when the client is at a constant distance (x-axis) from the access point. ERA
outperforms the other schemes due to 1) the effectiveness of its recovery strategy and 2) the mecha-
nism inherited from AARF: adaptively adjusting the threshold number (Threshold) of consecutive
successful transmissions required to increase the rate.
73
 0
 0.125
 0.25
 0.375
 0.5
 120  180  240  300  360  420  480
Throughput (KFrames/s)
Transmission distance (m)
ERA
ARF
CARA
Figure 4.11: Throughput under stable channel conditions
4.3.4 Collisions Dominated Environment
For this environment, all simulations are carried out in a network with 17 static stations corre-
sponding to topology #3 (See Table 4.2): one access point and 16 client stations. The objective is
to evaluate the performance of ERA and compare it to ARF and CARA performances in a collision
dominated environment. We use the two-ray ground fading model such that the best supported rate
is constant (stable channel conditions): with the two-ray ground fading model, the quality of the
channel is determined only by the distance. All 16 client stations are uniformly placed in a rectan-
gular area as shown in Figure 4.5. The congestion level in the network is varied by adjusting the
size of the network layout rectangle. All stations keep sending 10 Mbps CBR traffic to the access
point at the center of the rectangular area. We measure the throughput and evaluate the impact of
the packet length on the performance.
74
 0
 0.05
 0.1
 0.15
 0.2
 0.25
 80  160  240  320  400  480  560
Throughput (KFrames/s)
Length of the rectangular (m)
ERA
CARA
ARF
Figure 4.12: Throughput under different levels of collision
Impact of the Congestion Level
Figure 4.12 plots on the y-axis the throughputs of ARF, CARA, and ERA, respectively. The
x-axis represents the length of the rectangle. The packet size is set to 1000 bytes.
ERA performs best again, followed by CARA, and then ARF. Especially, as the collision in-
creases (smaller rectangular area), more improvement is achieved by ERA due to a more accurate
loss differentiation and to the judicious recovery strategy.
Impact of Packet Length on ERA
In each simulation, each station sends CBR traffic with packets of 100 bytes, 500 bytes, 1000
bytes, or 1500 bytes. All stations send packets of the same size in each run. Figure 4.13 plots the
percentage throughput improvement of ERA over CARA (100? ERA?CARACARA ). When the frame size
increases, the improvement increases because collisions are more likely with longer frames. The
75
 0
20%
40%
60%
80%
100%
120%
140%
 80  160  240  320  400  480  560
Throughput Improvement
Length of the rectanglular (m)
100 Bytes
500 Bytes
1000 Bytes
1500 Bytes
Figure 4.13: Impact of Packet length on throughput improvement
improvement is more significant for smaller rectangles because there are more collisions and ERA
has more opportunity to take advantage of its superiority.
4.4 Performance Evaluation on Linux based Testbed
In addition to above simulation experiments, we also implement and evaluate ERA and selected
presentative schemes on a Linux based testbed. Because SNR and RSSI have been studied to be
poor channel conditions indicators, SNR/RSSI based rate adaptation scheme are not considered for
implementation in our testbed. Moreover, some of these schemes are not IEEE 802.11 compli-
ant and just cannot be implemented on off-the-shelf IEEE 802.11 network interfaces. Therefore,
we only implement for performance evaluation the representative schemes that use frame loss as
channel condition indicator. After investigation, AARF, CARA, RRAA and SampleRate are selected
to respectively represent Non Loss Differentiation-Winning Streak, Loss Differentiation-Winning
Streak, Loss Differentiation-Statistics, Non Loss Differentiation-Statistics, which are highlighted in
76
Table 1.1. These representative schemes together with our proposed scheme ERA are implemented
in the Linux based testbed.
This section presents the implementation details of the Linux based testbed. Then experimental
environments and methodology are discussed. Finally the results from this testbed are presented.
4.4.1 Implementation Platform and Architecture
Our testbed consists of one wireless router and six laptop clients. Considering the open ar-
chitecture, we implement rate adaptation schemes in clients. Each laptop client is equipped with
a mini-PCI 802.11 adaptor with Atheros R5212 chipset. This adaptor is chosen for some of its
attractive features. First, Atheros R5212 chipset supports 802.11 a/b/g modes. It is convenient for
us to tune to any 802.11 mode in our experiments without extra hardware support. Second, also
most important, there is an open source driver comprehensively supporting adaptors with Atheros
chipset in Linux, which is downloadable from MadWifi [42]. This driver is delicately designed
and layered in architecture to take in new development. Third, the MadWifi driver is dissected
into different modules: rate adaptation control is developed as an individual module. This archi-
tecture speeds up the implementation of a new rate adaptation scheme. In addition, the MadWifi
driver provides an excellent mechanism to access the communication statistics through a delicate
interface to the firmware on the chipset. The communication statistics (e.g. SNR, RTS/CTS rate,
transmission result and retries) are accessible and controllable with minimum delay. The transmis-
sion queues in driver can also be manipulated for per-frame operation. The rough architecture of
this open source driver is depicted in Figure 4.14. As shown in the figure, the MadWifi driver con-
sists of four components. Among them, net802.11 provides generic IEEE 802.11 services such as
frame assembly/disassembly, user authentication and data encryption. HAL (Hardware Abstraction
77
HAL
ath
Rate
control
Net802.11
Madwifi
Figure 4.14: MadWifi Driver Architecture
Layer) provides access for the other components to the hardware firmware. HAL acts as an abstract
application interface because it is a closed source package with binary only format maintained by
Atheros Inc. The third component, ath, consists of specific callbacks for net80211 and rate control
through the interfaces supported by by HAL. Therefore, ath behaves more like an encapsulation
of HAL to provide firmware access. The component Rate control is responsible for executing rate
adaptation algorithm to select the transmission rate for each data frame. We implemented rate adap-
tation schemes in Rate control as individual modules. Our implementation is carried out on Linux
kernel version 2.6.18 and MadWifi driver version 0.9.3. AARF, CARA, RRAA, and ERA are imple-
mented as separate rate control modules. SampleRate [11] already exists in the MadWifi driver, but
by default it deliveries the control of retransmission to firmware, it has a clear advantage over the
other schemes. Therefore, for fairness in comparison, we turned off this capability for SampleRate:
SampleRate is modified to control the retransmissions in the driver as the other schemes do.
4.4.2 Implementation of ERA in MadWifi
In our testbed, to be compatible with the architecture of MadWifi, ERA is implemented as an
individual rate control module. ERA module consists of three primary components: rate adjustment,
78
HAL
ath
Net802.11
Madwifi
Rate Adjustment
Loss
Differentiation
Retransmisison
RAILD
Figure 4.15: Architecture of ERA in MadWifi
retransmission and loss differentiation. The dependency and interaction of these components are
illustrated in Figure 4.15. For each transmission, ERA detects the consequence (failure or success) of
the transmission from the callbacks in module ath. If the transmission succeeds, the rate adjustment
component updates the transmission counter Ts and increases the rate if the condition is satisfied. In
case of failure, the loss differentiation component takes over the control. It is charge of fragmenting
the lost frame, handing over the fragments to retransmit and diagnosing the cause of a loss. The
result of loss differentiation is output to the rate adjustment component to decrease the rate in case
of channel degradation. The retransmission component is responsible for queueing corresponding
fragments of the failed frame into the transmission queue and assigning the short fragment a rate
by consulting the rate adjustment. Since we do not have control over the transmission buffer in the
firmware, we turn off the retransmission functionality for each data frame in firmware provided by
ath. Instead, we retransmit in the driver through the transmission queue.
79
4.4.3 Experimental Environment and Methodology
We conduct experiments in both controlled tests and field public site tests. The controlled
experiments are carried out in a building called Shop Building whose floor plan is depicted in Fig-
ure 4.16. The experimental building consists of classrooms, offices and labs. But all office furniture
and lab equipment have been moved out as the department relocated. To minimize the external sur-
rounding interference, we conduct all experiments in the evening after all classes dismissed when
nobody was walking around during the experiments.
Our testbed consists of one access point and six laptops. The access point is a Belkin wireless G
router with compatibility to 802.11b. All client laptops are IBM Thinkpad T60 whose configuration
is CPU Intel Core Duo 1.8Ghz, RAM 1G, HD 80G and mini-PCI WIFI adaptor with Atheros R5212
chipset. All rate adaptation schemes are implemented in the laptops so that any scheme can be
selected at any time for performance evaluation. The access point is closed to hack and runs ?AS IS?
with its factory settings. All data traffic is generated from the laptops to the access point. The access
point marked with AP in Figure 4.16 is located in the upper rightmost classroom. Those laptops
generating traffic for trace collection are placed at locations (L-1, L-2, L-3 and L-4). Interfering
laptops are placed at locations (I-1, I-2, I-3 and I-4).
Both laptops and the access point run in IEEE 802.11b/g compatible mode. Therefore, the
available rates are 1, 2, 5.5, 11, 6, 9, 12, 18, 24, 36, 48, and 54 Mbps in experiments.The access
point supports 11 channels (US standard). There are three non-overlapping channels (1, 6, 11)
available in IEEE 802.11 networks. To reduce co-channel interference, these channels are normally
deployed to neighboring access points in campus networks. In the experimental building, before the
experiments, we sniffed the channels that are in use by other surrounding networks. Channel 6 and
11 are heavily used by more than ten surrounding access points. The signal from these networks is
80
AP
I-4I-3
I-2
I-1
L-1
L-2
L-3
L-4
Figure 4.16: Floor plan in experiments
strong and has a large impact on the result if we tune our testbed to these channels. Comparably,
channel 1 is lightly used by only two networks. Therefore, to minimize the interference from other
networks, we tuned the testbed to channel 3 because it is not used by any other close-by network.
Note however that Channel 3 is slightly impacted by networks running on channel 1 and channel 6.
Besides the controlled experiments in Shop Building, we also carried out field tests in public
areas. Laptops with implemented schemes AARF, CARA, RRAA, SampleRate and ERA are con-
nected to some public access point of the campus network. The traffic generated by client laptops
are transmitted to a wired receiver. These transmissions contend for channel access against other
anonymous wireless stations connected to the same access point.
Each experiment lasts for 2 minutes for two considerations. First, the time is long enough to
cover time variations of 802.11 wireless signal. Second, it is short so that the channel background
environment does not change wildly for interleaved measurement for each scheme in each run.
For each experiment scenario, five runs are repeated. And for each run, tests for all schemes are
interleaved such that they are evaluated under the same conditions (as much as we can). Then, in
gathered trace, the maximum and the minimum values of the five runs are ignored to avoid wild
variation. The remaining three values are averaged as the final result. In all our experiments, the
81
RTS threshold is set to the maximum to turn off RTS completely for all sizes of frame. UDP and
TCP traffic are used as data load. Two types of UDP traffic are generated with Mgen [43] at 16
Mbps (1000 packets of 2 KBytes per second) or 48 Mbps (2000 packets of 3 KBytes per second).
TCP traffic is generated with Iperf [44]. The receiving TCP window size is set to the default value
(16 Kbytes) (which is not allowed to change in the Linux we used).
To comprehensively compare ERA and other selected rate adaptation schemes, we mainly mea-
sure their performance in the following scenarios:
? Channel degradation dominated. In this scenario, only one client runs in an 802.11 cell.
This scenario emulates a wireless home network. Experiments are conducted for both station-
ary and mobile scenarios. For the static case, the performance is evaluated at each location
L-i. Even static transmissions suffer from frame loss due to time-variant channel fluctua-
tions [32]. For the mobile case, one client laptop with traffic to the access point is carried
by a person walking at an almost constant speed from L-1 to L-4 through all four locations.
Mobility introduces more complexity to channel degradation [32].
? Composite lossy environment. For this scenario, the communication experiences frame loss
from both channel fading and collision. We place two contending clients at interfering loca-
tions I-1 and I-2. These clients continuously generate data traffic to the access point. Such
a configuration attempts to reproduce an office or campus network. Again, both static and
mobile experiments are conducted as we did for the channel degradation dominated environ-
ment.
? Heterogenous rate adaptation schemes. In this scenario, each of four laptops runs one of
the rate adaptation schemes CARA, ERA, RRAA and SampleRate, respectively. The objective
82
is to observe how these schemes contend with each other. AARF is not taken into evaluation
in this scenario because it performs poorly in congestion dominated environments.
? Increasing contention level. The contention level is gradually increased by running one
more laptop each time (incrementally) at interfering locations I-1, I-2, I-3 and I-4. The rate
adaptation schemes experience different levels of collision generated by two, three, or four
laptops.
4.4.4 Experiment Results from Testbed
With the testbed of implemented rate adaptation schemes: AARF, CARA, RRAA, SampleRate
and our ERA, extensive experiments are carried out to evaluate their performance. Our experimental
setting is as presented in Section 4.4.3. Performance is evaluated under a combination of scenarios
described in Section 4.4.3. Both static and mobile scenarios are considered. We conduct both
controlled experiments and public field tests in the real world where all conditions are out of our
control. The testbed in controlled testes is set as only one WLAN: all stations are within the radio
coverage of the same access point. But note that these client stations are not necessarily within the
radio coverage of each other, leading to possible hidden terminal collisions. The traffic is always
from the clients to the access point. Unless particularly specified, the y-axis in all the following
figures represents the goodput: data successfully collected at the receiver station per second. As
we may observe from the following experiment results, in most cases, ERA outperforms the other
schemes. The results are presented in groups of experimental scenario.
83
 0
 5
 10
 15
 20
 25
 30
 35
 40
L-1 L-2 L-3 L-4
Goodput (Mbps)
AARF
CARA
RRAA
SampleRate
ERA
Figure 4.17: UDP goodput in static mode in channel degradation
Channel Degradation Dominated
We first evaluate the performance of these rate adaptation schemes in channel degradation dom-
inated environments. Such environments are widely visible in residential wireless home networks
where only one wireless client at a time is accessing the Internet through the access point. The client
may move around, but more often be stationary. Therefore, in channel degradation environments,
we conduct experiments for both static and mobile modes.
In the static mode, a client laptop is successively placed at each evaluation location (L-1, L-2,
L-3, L-4 in Figure 4.16). Experimental trace is collected at one location at a time. UDP traffic
generated by the client is transmitted towards a wired receiver through the access point. Figure 4.17
depicts the goodput of each scheme in the static mode. The x-axis represents locations (L-1 through
L-4). We observe that the performance of each scheme may vary widely at each location. ERA per-
forms best at L-1 and L-4. Particularly at L-4, ERA improves goodput by about 70% over the runner
84
up SampleRate. At these two spots, the signal strength is either best or worst, therefore supporting
very stable rates. L-1 can support highest rate all the time and L-1 can only support the lowest
rate. Without collision, in locations with stable rates, ERA outstands with benefits from its adaptive
threshold for rate increase. It incurs fewer frame losses, thereby less overhead from fragmentation
and less resource consumption in retransmission. But, ERA does not perform best at L-2, L-3.
Since all losses are due to channel variation in this environment, after a frame loss, the first trans-
mission of the lead (short) fragment in ERA at the normal rate most likely fails, therefore causing an
overhead to each retransmission. SampleRate samples other rates at every tenth transmission, con-
stantly wasting the resource roughly 10%. Observe that RRAA and CARA perform poorly at most
locations because they do not explicitly take prompt actions for degradation even they detects it.
CARA almost achieves a null goodput at L-4 (weakest signal strength). It is also not surprising that
traditional schemes SampleRate and AARF have better performance because they primarily target
channel degradation environments without explicit consideration of collision.
In mobile experiment mode, a client laptop is carried by a person moving at an almost constant
pace through over the path L-1 ? L-2 ? L-3 ? L-4 shown in Figure 4.16. The traffic pattern is the
same as in above static mode. The experimental results are plotted in Figure 4.18. We can observe
that ERA achieves the best goodput in this scenario. Again, RRAA and CARA are outperformed
because they do not address well the channel variation explicitly.
Composite Lossy Environments
Then we evaluate the performance in environments with mixed frame losses due to channel
variations and collisions. Such mixed environments are similar to campus or corporate environ-
ments where each access point is associated with multiple clients and more than one wireless client
85
 0
 5
 10
 15
 20
 25
AARF CARA RRAA SampleRate ERA
Goodput (Mbps)
Figure 4.18: UDP goodput in mobile mode in channel degradation
may well transmit to the access point in a generic time slot, especially when they are hidden termi-
nals to each other. To introduce the collision into the environment, we place two interfering wireless
stations statically at location I-1 and I-2 in Figure 4.16. These two stations continually transmit traf-
fic at a constant pattern also to the wired receiving node through access point over all the experiment
time. Both static and mobile scenarios are evaluated.
The mobile scenario still adopts the route L-1 ? L-2 ? L-3 ? L-4. Only UDP traffic is
evaluated in this case. But, the traffic has to contend with the interfering traffic from those stations
located at I-i. The results are presented in Figure 4.19. Although without using RTS/CTS, ERA
improve the goodput about 25% over RRAA, the second best scheme in this scenario. The strength
of ERA is that it not only diffuses collisions, but also it can react to channel degradation. Its per
frame loss diagnose also prompts the loss recovery. Because of their ability to suppress collisions
with RTS/CTS after loss, RRAA and CARA outperform traditional schemes in the combinational
loss environments.
86
 0
 0.5
 1
 1.5
 2
 2.5
 3
AARF CARA RRAA SampleRate ERA
Goodput (Mbps)
Figure 4.19: UDP goodput in mobile mode in combinational loss
 0
 1
 2
 3
 4
 5
L-1 L-2 L-3 L-4
Goodput (Mbps)
AARF
CARA
RRAA
SampleRate
ERA
Figure 4.20: TCP goodput in static mode in combinational loss
87
In the static test, a client laptop running with implemented schemes is successively placed at
each location (L-1, L-2, L-3, L-4 in Figure 4.16. Measurements are made at one location at a time.
We measure the TCP traffic in this scenario. The collected goodput results are plotted in Figure 4.20.
The x-axis represents locations L-1 through L-4. From the figure, the performance for each scheme
fluctuates wildly at different locations in such mixed loss setting. But, one surprising observation
is that SampleRate does not perform poorly as reported in the literature. After investigation, we
find that the SampleRate implemented in the MadWifi driver probes (samples) all rates except the
current one. This behavior is different from the behavior described in the paper [11] that only probes
the rate ?that may do better than the current one?. SampleRate implemented in the code probes also
all the rates lower than the current one at every tenth transmission. In collision environments, the
probing at lower rates likely increase the transmission failure due to more collision with bigger
effective transmission range. Therefore, SampleRate is aware that lower rates can not have better
performance than the current rate in use in the transmission window. It remains its current rate or
even increases rate for better throughput depending on the sampling result. Such operation is most
appropriate in a collision environment. Implicitly, it somehow has the ability not to decrease rate in
collision prone case while it does not have any explicit differentiation measure.
Multimedia Parameters
As multimedia services become popular in mobile applications, the capability of a WLAN
network supporting the multimedia payload transportation is critical. We conduct experiments to
evaluate metrics of interest to multimedia applications: jitter and the percentage of out-of-order
packets. The experimental setting is as in a static loss environment. In these experiments, we
use Iperf [44] to generate VoIP UDP traffic and gather the jitter and the number of out-of-order
88
 0
 50
 100
 150
 200
 250
 300
AARF CARA RRAA SampleRate ERA
Jitter (ms)
Figure 4.21: Jitter
packets. The report is generated at intervals of 500 ms. Then the largest jitter is recorded as the
final result. Figure 4.21 plots the largest jitter for each rate adaptation scheme where the y-axis
is the jitter in ms. ERA performs best (with smallest jitter) in this scenario. This is because ERA
deploys a prompt loss recovery strategy upon each loss in both collision and channel fading cases.
Except for ERA and RRAA, all other schemes deliver jitters larger than 100 ms, the time constraint
required by real-time multimedia applications such as VoIP. The percentage of out-of-order packets
is shown in Figure 4.22. The y-axis depicts the percentage of out-of-order packets. With ERA, the
percentage is reduced to about 10%. A larger number of out-of-order packets requires more buffer
at the application client to play back multimedia.
Heterogeneous Clients Contention
To evaluate the contention among these rate adaptation schemes, four laptops clients transmit
together, each of which runs one of schemes CRA, RRAA, SampleRate and ERA. AARF is not taken
89
 0
5%
10%
15%
20%
25%
30%
AARF CARA RRAA SampleRate ERA
Percentage
Figure 4.22: Percentage of packets out-of-order
 0
 2
 4
 6
 8
 10
CARA RRAA SampleRate ERA
Goodput (Mbps)
Figure 4.23: UDP goodput in heterogeneous competition
90
into experiments because it performs poorly in collision or mixed environments. For fairness to
each scheme, the four laptops are evenly distributed on a circle centering at the access point. We
checked that they all nearly receive the same signal strength. The measurement is illustrated in
Figure 4.23. The y-axis represents the goodput of each scheme. From the result, ERA wins the con-
tention. It achives almost 35% improvement over CARA. Its outstanding performance benefits from
its accuracy in loss diagnosis and prompt recovery strategy in the heavy contention environment.
Increasing contention level
We also measured the performance of each rate adaptation scheme undergoing different colli-
sion levels. In this scenario, one client running one rate adaptation scheme each time is statically
placed at location L-2. The collision level is gradually increased by adding one more interfering
stations at locations I-1, I-2, I-3, and I-4. The experiments start with two interfering stations and
end up with four. All interfering stations generate the same UDP traffic to the receiver through the
access point. Figure 4.24 plots the results. To keep consistent, we start the interference from 2
stations (we take 2 interfering stations as minimum interference in all our experiments). Although
ERA does not perform best with 2 interfering stations, it outperforms all others as the collision level
increases and its gain is higher in heavier collision: 40% more than the runner up. When collision is
light, the overhead introduced by fragmenting in ERA is not offset by its benefits. But, as the colli-
sion becomes severe, the benefits of fragmenting in collision environments result in the outstanding
performance of ERA.
Field Tests
To evaluate the performance of these schemes in practice, we also conduct two field tests by
connecting client(s) running with rate adaptation schemes to an access point in the campus network.
91
 0
 2
 4
 6
 8
 10
2 3 4
Goodput (Mbps)
Number of interfering stations
AARF
CARA
RRAA
SampleRate
ERA
Figure 4.24: UDP goodput under collision levels
One scenario is measured with UDP traffic while the other with TCP. All clients are stationarily
placed. For the scenario with UDP traffic, the four laptops are distributed with almost the same
signal strength to the campus access point. The clients are competing with other anonymous clients
transmitting to the same access point. Also, they contend with each other. Consistent to the results
obtained in Figure 4.23, ERA performs best, as shown on Figure 4.25.
In the TCP experiment, we run one client only. One scheme is measured each time. The
experiment results are plotted in Figure 4.26. As we observe, ERA marginally outperforms RRAA.
But it can outperform CARA and AARF by more than 30%.
92
 2
 2.5
 3
 3.5
 4
CARA RRAA SampleRate ERA
Goodput (Mbps)
Figure 4.25: UDP goodput in field test
 3
 3.5
 4
 4.5
 5
 5.5
 6
 6.5
 7
AARF CARA RRAA SampleRate ERA
Goodput (Mbps)
Figure 4.26: TCP goodput in field test
93
CHAPTER 5
CONCLUSIONS AND FUTURE WORK
Multi-rate support in IEEE 802.11 networks requires efficient and effective rate adaptation
solutions to fully exploit scarce wireless resource. In this dissertation, we review rate adaptation
schemes in literature for IEEE 802.11 networks. Although rate adaptation on IEEE 802.11 networks
has been deemed for years, most of these schemes are based on SNR/RSSI that are studied not
closely correlated to the successful frame delivery. Different approaches are also proposed to adapt
rates based on frame loss. However, most of them do not consider the causes of different losses,
assuming that the collision in IEEE 802.11 networks are avoided by the use of RTS/CTS. The real
time trace from practice shows the presence of RTS/CTS frames is rare in the traffic in IEEE 802.11
networks because they are optional due to the overhead. Such overhead is particularly severe in
multimedia communication that is surging in daily life. The absence of RTS/CTS frames results in
complexity to rate adaptation because the frame losses might be caused by channel degradation and
also by transmission collision. Different frame loss can not be addressed by the same strategy.
In our effort to identify an effective rate adaptation scheme, we successively propose three rate
adaptation strategies. With our investigation of proposed rate adaptation schemes in the literature,
we found that there is no solution taking into account the estimation of initial data rate to start the
transmission of a stream of data frames. But a proper initial rate can improve the utilization of
network resource or reduce frame losses in the beginning. Therefore, we propose a scheme called
Beacon Assisted Rate Adaptation BARA for the initial rate and ongoing rates with the periodically
broadcast beacon frames which are mandatory in IEEE 802.11 standard. This technique benefits the
94
network performance without introducing any extra transmission overhead to data frames in net-
works with or without RTS/CTS control frames. To differentiate frame losses, we propose a second
scheme Loss Differentiation Rate Adaptation LDRA that diagnoses the cause of losses and quickly
recovers lost frames with the basic rate retransmission technique. Also, in this dissertation, we ex-
tensively investigate the rate adaptation schemes proposed in recent years with explicit consideration
of different types of frame loss. Implementing these schemes on a Linux based testbed, we observe
some anomalies in their adaptation dynamics in running time. Based on these observations, we
design an effective rate adaptation scheme Effective Rate Adaptation ERA. It is a ?winning streak?
scheme increasing rate upon the number of consecutive successfully transmitted data frames. But,
unlike other frame loss based schemes, ERA does not reset the count of this number in confronting
any loss from collision. Namely, the collision does not interrupt the counting of frame losses to indi-
cate channel degradation. To dissipate frame losses in stable channel environments, ERA adaptively
extends the rate increase cycle to exploit potential better channel conditions. Upon a data frame
loss, ERA judiciously exploits the IEEE 802.11 fragmentation mechanism in full compliance with
the standard to diagnose the cause. In this work, we analytically and numerically show the bene-
fits of fragmentation: 1) ERA diagnoses loss accurately; 2) the loss can be recovered quickly; 3) it
even incurs less overhead at the intermediate rate than RTS/CTS control frames. For a diagnosed
collision, ERA diffuses the congestion with a short (lead) fragment and retains the rate. Moreover,
it halves the rate for a diagnosed channel degradation to quickly recover loss.
We evaluate the benefits of these three schemes with extensive simulation on a network simula-
tor. Furthermore, to evaluate the performance of rate adaptation schemes in practice, we implement
on a Linux based testbed ERA and four other representative adaptation schemes: AARF, CARA,
95
RRAA, and SampleRate. Extensive both controlled and public field experiments on the testbed sug-
gest that ERA often performs best in the most channel fading or collision dominated environments.
Also, we observe that each of these schemes has undeniable strengths and some weaknesses.
Part of our future work is to understand the IEEE 802.11 channel dynamics. As reviewed
in Section 1.3, there are limited measurements of IEEE 802.11 channels under realistic scenarios,
though some work has been conducted in literature. Most current measurements are limited in
the following aspects: 1) the measurement experimental settings are limited to specific testbeds or
controlled tests. These environments are not generic or representatives of public hot spots. 2) most
of the experiments were conducted on IEEE 802.11b channels. However, most of current networks
operate on 802.11g or even the 802.11n draft recently. It is shown that the different encoding
schemes lead to a considerable difference in performance among these IEEE 802.11 variants. 3) the
observations are primarily from overall network performance. Investigation of detailed per frame
channel dynamics is scarce. Therefore, the next step is to analyze IEEE 802.11 channel dynamics
with extensive experiments in both controlled tests and public sites. This analysis is needed to better
understand traffic and channel models.
Our future agenda also includes the design of a hybrid rate adaptation scheme. As we ob-
serve with the extensive experiments in practice on our implemented testbed, although ERA out-
performs its peers in most scenarios, every implemented rate adaptation scheme demonstrates its
own strength. It is challenging but beneficial to design a rate adaptation scheme that synergies the
strengths and mitigates the weaknesses of the above five schemes on the testbed. This design will
be based on the above understanding of channel dynamics, and on strategies considering both short-
term and long-term network performance. As multimedia applications surge in daily life, a new rate
96
adaptation scheme should not only perform efficiently for traditional TCP based services, e.g. FTP,
HTTP, but also for these new multimedia services, e.g. online video, radio, VoIP.
Another future work is to integrate rate adaptation into routing metrics. Recent years, research
on routing protocols in multiple hops wireless networks, e.g. mesh networks, ad-hoc networks,
has gained extensive attention. However, most of these innovative protocols are based on very flat
routing metrics. Since different links along a routing path operate on rates adapted frequently by
rate adaptation, introduction of rate adaptation into routing metrics should significantly impact route
selection and improve network performance.
97
BIBLIOGRAPHY
[1] IEEE802.11, ?http://standards.ieee.org/getieee802/download/ 802.11-1999.pdf,? 1999.
[2] A. Kamerman and L. Monteban, ?WaveLAN II: A high-performance wireless LAN for the
unlicensed band,? Bell Labs Technical Journal, pp. 118?133, 1997.
[3] M. Lacage, M. Manshaei, and T. Turletti, ?IEEE 802.11 Rate Adaptation: A Practical Ap-
proach,? in MSWiM04, 2004, pp. 126 ? 134.
[4] D. Qiao, S. Choi, and K. Shin, ?Goodput Analysis and Link Adaptation for IEEE 802.11a
Wireless LANs,? IEEE TRANSACTIONS ON MOBILE COMPUTING, vol. 1, pp. 278?292,
2002.
[5] J. Pavon and S. Choi, ?Link Adaptation Strategy for IEEE 802.11 WLAN via Received Signal
Strength Measurement,? in ICC, 2003, pp. 1108?1123.
[6] G. Holland, N. Vaidya, and P. Bahl, ?A rate-adaptive MAC protocol for multi-hop wireless
networks,? in ACM MOBICOM?01, 2001.
[7] B. Sadeghi, V. Kanodia, A. Sabharwal, and E. Knightly, ?Opportunistic Media Access for
Multirate Ad Hoc Networks,? in MOBICOM02, 2002, pp. 24 ? 35.
[8] J. Kim, S. Kim, S. Choi and D. Qiao, ?CARA: Collision-Aware Rate Adaptation for IEEE
802.11 WLANs,? in IEEE INFOCOM?06, Barcelona, Spain, April 2006.
[9] S. Wong, H. Yang, S. Lu and V. Bharghavan, ?Robust Rate Adaptation for 802.11 Wireless
Networks,? in MobiCom?06, Angeles, California, USA., September 2006, pp. 146 ? 157.
[10] Madwifi., ?http://sourceforge.net/projects/madwifi.?
[11] J. C. Bicket, ?Bit-rate Selection in Wireless Networks,? Master?s thesis, Massachusetts Insti-
tute of Technology, 2005.
[12] Z. Li, A. Das, A.K. Gupta, and S. Nandi, ?Full auto rate MAC protocol for wireless ad hoc
networks,? IEEE Procedings on Communication, vol. 3, pp. 311?319, 2005.
[13] Q. Pang, V. Leung, and S. C. Liew, ?A Rate Adaptation Algorithm for IEEE 802.11 WLANs
Based on MAC-Layer Loss Differentiation,? in IEEE BROADNETS 2005 - Broadband Wire-
less Networking Symposium, Boston, USA, 2005, pp. 709?717.
[14] MIT Roofnet., ?http://pdos.csail.mit.edu/roofnet.?
98
[15] M. Rodrig, C. Reis, R. Mahajan, D. Wetherall, and J. Zahorjan, ?Measurement-based Charac-
terization of 802.11 in a Hotspot Setting,? in SIGCOMM?05 Workshops, 2005.
[16] A. Kashyap, S. Ganguly, and S. R. Das, ?A Measurement-Based Approach to Modeling Link
Capacity in 802.11-Based Wireless Networks,? in Mobicom?07, 2007.
[17] G. Bianchi, F. Formisano, and D. Giustiniano, ?802.11b/g Link Level Measurements for an
Outdoor Wireless Campus Network,? in WoWMoM?06, 2006.
[18] D. Aguayo, J. Bicket, S. Biswas, G. Judd, and R. Morris, ?Link-Level Measurements from an
802.11b Mesh Networks,? in ACM SIGCOMM, 2004.
[19] P. Barsocchi, G. Oligeri, and F. Potort, ?Validation for 802.11b Wireless Channel Measure-
ments,? Consiglio Nazionale delle Ricerche, Tech. Rep. 2006-TR-29, 2006.
[20] V. Lenders, J. Wagner, and M. May, ?Measurements from an 802.11b mobile ad hoc network,?
in WoWMoM?06, 2006.
[21] Y. Cheng, J. Bellardo, P. Benkoy, A. C. Snoeren, G. M. Voelker, and S. Savage, ?Jigsaw:
Solving the Puzzle of Enterprise 802.11 Analysis,? in SIGCOMM?06, 2006.
[22] V. Bychkovsky, B. Hull, A. Miu, H. Balakrishnan, and S. Madden, ?A Measurement Study of
Vehicular Internet Access Using In Situ WiFi Networks,? in Mobicom?06, 2006.
[23] K. Chebrolu, B. Raman, and S. Sen, ?Long-Distance 802.11b Links: Performance Measure-
ments and Experience,? in Mobicom?06, 2006.
[24] C. Cheng, P. Hsiao, H. T. Kung, and D. Vlah, ?Performance Measurement of 802.11aWireless
Links from UAV to Ground Nodes with Various Antenna Orientations,? in ICCCN?06, 2006.
[25] IEEE802.11b, ?http://standards.ieee.org/getieee802/ download/802.11b-1999.pdf,? 1999.
[26] IEEE802.11, ?http://standards.ieee.org/getieee802/download/802.11g-2003.pdf.?
[27] M. R. Souryal, L. Klein-Berndt, L. E. Miller, and N. Moayeri, ?Link Assessment in an Indoor
802.11 Network,? in WCNC?06, 2006.
[28] D. Gesbert, M. Shafi, D. Shiu, P. J. Smith, and A. Naguib, ?From Theory to Practice: An
Overview of MIMO SpaceTime Coded Wireless Systems,? IEEE JOURNAL ON SELECTED
AREAS IN COMMUNICATIONS, vol. 21, pp. 281?302, 2003.
[29] D. Johnson, ?Evaluation of a single radio rural mesh network in South Africa.?
[30] S. Garg and M. Kappes, ?An Experimental Study of Throughput for UDP and VoIP Traffic in
IEEE 802.11b Networks,? in WCNC2003, vol. 3, March 2003, pp. 1748? 1753.
[31] M. Heusse, F. Rousseau, G. Berger-Sabbatel, and A. Duda, ?Performance anomaly of
802.11b,? in INFOCOM 2003, vol. 2, 30 March-3 April 2003, pp. 836?843vol.2.
99
[32] Z. Rong and T. S. Rappaport, Wireless Communications: Principles and Practice, 2nd Edition.
Prentice Hall, 2002.
[33] Q. Pang, S. C. Liew, and V. Leung, ?Design of an Effective Loss-Distinguishable MAC Proto-
col for 802.11 WLAN,? IEEE Communications Letters, vol. 9, pp. 781?783, 2005.
[34] S. Wu and S. Biaz, ?Loss Differentiated Rate Adaptation in Wireless Networks,? Auburn Uni-
versity, Tech. Rep. CSSE07-02, March 2007.
[35] W. Stallings, Wireless Communications and Networks. Prentice Hall, 2004.
[36] ISI, 2006. [Online]. Available: ?http://www.isi.edu/nsnam/ns/?
[37] X. Wu, ?Simulate 802.11b Channel within NS2,? National University of Singapore, Tech. Rep.
[38] G. Bianchi, F. Formisano, and D. Giustiniano, ?802.11b/g Link Level Measurements for an
Outdoor Wireless Campus Network,? in Proceedings of the 2006 International Symposium on
a World of Wireless, Mobile and Multimedia Networks (WoWMoM?06), 2006.
[39] G. Bianchi, ?Performance analysis of the ieee 802.11 distributed coordination function,? Se-
lected Areas in Communications, IEEE Journal on, vol. 18, no. 3, pp. 535?547, 2000.
[40] Cisco Systems. [Online]. Available: ?http://www.cisco.com/en/US/products/hw/wireless/
ps4555/products data sheet09186a00801ebc29.html.?
[41] S. Wu and S. Biaz, ?ERA: Efficient Rate Adaption Algorithm with Fragmentation,? Auburn
University, Tech. Rep. CSSE07-04, June 2007.
[42] Madwifi. [Online]. Available: ?http://madwifi.org/?
[43] Naval Research Laboratory. [Online]. Available: ?http://cs.itd.nrl.navy.mil/work/mgen/index.php?
[44] A. Tirumala, F. Qin, J. Dugan, J. Ferguson, and K. Gibbs. [Online]. Available:
?http://dast.nlanr.net/Projects/Iperf/?
100