Synergy MAC: A Cooperative MAC Protocol
Except where reference is made to the work of others, the work described in this thesis is
my own or was done in collaboration with my advisory committee. This thesis does not
include proprietary or classified information.
Santosh B. Kulkarni
Certificate of Approval:
David Umphress, Co-Chair
Associate Professor
Computer Science and Software Engi-
neering
Prathima Agrawal, Co-Chair
Samuel Ginn Distinguished Professor
Electrical and Computer Engineering
Alvin Lim
Associate Professor
Computer Science and Software Engi-
neering
George T. Flowers
Dean
Graduate School
Synergy MAC: A Cooperative MAC Protocol
Santosh B. Kulkarni
A Thesis
Submitted to
the Graduate Faculty of
Auburn University
in Partial Fulfillment of the
Requirements for the
Degree of
Master of Science
Auburn, Alabama
May 9, 2009
Synergy MAC: A Cooperative MAC Protocol
Santosh B. Kulkarni
Permission is granted to Auburn University to make copies of this thesis 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
Santosh Kulkarni was born on the 1st of January, 1980 in Bijapur, India. He received
his Bachelors degree in Computer Science Engineering from Visvesvaraya Technological
University, India, in 2002. Following graduation he was employed by MindTree Limited,
Bangalore, India, where he was involved with the development and maintenance of various
communication products for the organization?s R&D division. In the fall of 2006, he moved
to Auburn, Alabama, to pursue his graduate studies at the department of Computer Science
and Software Engineering, Auburn University.
During his sojourn in Auburn, Santosh was granted teaching as well as research assis-
tantships. He was also awarded the Vodafone wireless research fellowship in January, 2008.
He is presently a member of Dr. Prathima Agrawal?s Wireless Research Group, pursuing his
research interests in wireless networking, medium access control, routing protocols, quality
of service and cooperative communications.
iv
Thesis Abstract
Synergy MAC: A Cooperative MAC Protocol
Santosh B. Kulkarni
Master of Science, May 9, 2009
(B.E., Visvesvaraya Technological University, India 2002)
75 Typed Pages
Directed by Prathima Agrawal
Since the advent of IEEE?s 802.11 standard, Wireless Local Area Networks (WLAN)
have gained widespread acceptance in providing broadband wireless access to portable de-
vices. The performance of any WLAN depends largely on the nature of the wireless envi-
ronment available to its participating nodes. This is because radio waves experiencing in-
terference and fading effects severely affect the overall throughput achieved by the wireless
network. Although spatial diversity is known to minimize the ill effects of channel fading,
realizing this form of diversity generally requires incorporation of newer technologies such
as Multiple Input Multiple Output (MIMO) systems. But it is impractical to equip every
node in a WLAN with multiple antennas, primarily due to their size and energy constraints.
Recent research on cooperative communication demonstrates that spatial diversity can
also be achieved by exploiting some unique properties of the underlying wireless medium.
The inherent broadcast nature of the wireless channel suggests that any signal transmitted
on the medium can be overheard by all nodes within the receiving range. If such nodes
were to retransmit the overheard signal towards the destination rather than discarding it
completely, they would effectively provide the destination with extra observations of the
source signal. These observations at the destination are all dispersed in space and are akin
to the observations resulting from MIMO systems. In short, one can think of a cooperative
system as a virtual antenna array, where each antenna in the array corresponds to one of
v
the assisting neighbors. However, to exploit the spatial diversity realized at the physical
layer, the idea of node cooperation needs to be extended to other layers of the protocol
stack, especially the MAC sub-layer. Further, if such cooperation aware MAC sub-layer is
designed to be backward compatible with 802.11b, then even devices with legacy hardware
could potentially derive its benefits.
In addition to interference and fading effects, nodes in WLANs can also suffer from
fairness problems resulting from multi-rate modulation scheme employed by IEEE?s 802.11b
standard. Studies have shown that when all nodes in a WLAN have uniform traffic to/from
the access point (AP), the lower data rate nodes will use much more channel time than the
higher data rate nodes resulting in two negatives: not only do the lower data rate nodes get
poor service, they also reduce the bandwidth of the higher data rate nodes. This in turn
reduces the effective throughput of the entire network. Researchers have proposed a multi-
hop extension to IEEE?s 802.11b infrastructure mode to mitigate such fairness problems.
In this work, we focus on the design of a new IEEE 802.11b compatible cooperative
MAC protocol that also incorporates multi-hop techniques to counter fairness problems
discussed above. With the studied protocol, labeled Synergy MAC, low data rate nodes
transmit their packet first to an intermediate node which in turn forwards the packet to
the destination at rates higher than otherwise possible. By ensuring that the destination
receives two copies of the original transmission, Synergy MAC is able to realize spatial
diversity. Performance of Synergy MAC is validated by means of extensive simulations
using ns-2 network simulator. Results show that the proposed protocol is able to deliver a
superior performance in comparison to IEEE?s 802.11b.
vi
Acknowledgments
This work would not have been possible without the help and support of many key
individuals. First and foremost, I would like to thank my advisor, Dr. Prathima Agrawal,
for a list that is perhaps too long to enumerate. Her insightful and open approach to
research, her unwavering commitment towards her research team along with her willingness
to let students tackle problems in their own style, were all instrumental in bringing this
work to fruition.
I would also like to thank Dr. David Umphress for not only lending me an ear every time
I stopped by unannounced, but also for agreeing to serve as a Co-Chair on my advisory
committee. I am equally grateful to Dr. Alvin Lim, with whom I had the pleasure of
publishing my first paper, for readily accepting to join the rest of my thesis panel.
I also owe much gratitude to Dr. Daniela Marghitu for her warm and supportive nature
as well as her concern for my professional and personal well-being. Furthermore, I would
like to thank Dr. Biaz, Dr. Hamilton, Dr. Chapman as well as Dr. Narayanan for their
several after-class, occasionally in-corridor brainstorming discussions. My thanks also go
out to Mrs. Shelia Collis and Mrs. Barbara McCormack for always helping me get by my
school paper work. I also extend my special thanks to the Vodafone?s Fellowship Program
and U.S. Air Force Office of Scientific Research (Grant No. FA 9550-06-1-0103) for partly
supporting my graduate studies.
Finally, I end my acknowledgement where my happiness begins: with my family and
friends. I thank Pratap and Ananth for being such wonderful room-mates, the Sree family
for giving me a home away from home and all my friends, both local and remote, who stood
by me even as my body clock frequently changed time zones. Most of all, I want to thank
my family for tirelessly supporting, enduring and guiding me in their own magical way.
Together they define my existence and it is to them that I lovingly dedicate this work.
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 aums.sty.
viii
Table of Contents
List of Figures xi
1 Introduction 1
1.1 Evolution of Mobile Radio Communications . . . . . . . . . . . . . . . . . . 1
1.1.1 IEEE 802.11 Standards . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Propagation Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2 Fading in Wireless Environment 6
2.1 Multipath Propagation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 Effects of Multipath Propagation . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3 Types of Fading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.4 Fading Channel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.5 Diversity for Error Compensation . . . . . . . . . . . . . . . . . . . . . . . . 12
2.5.1 Cooperative Diversity . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3 Cooperative Communication 16
3.1 Underlying Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.2 Benefits of Cooperative Networking . . . . . . . . . . . . . . . . . . . . . . . 20
3.2.1 Higher Spatial Diversity . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.2.2 Higher Throughput-Lower Delay . . . . . . . . . . . . . . . . . . . . 22
3.2.3 Lower Power Consumption and Lower Interference . . . . . . . . . . 22
3.2.4 Adaptability to Network Conditions . . . . . . . . . . . . . . . . . . 23
4 Overview of IEEE 802.11b 25
4.1 802.11b PHY Layer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.2 802.11b MAC Layer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.2.1 Carrier Sensing and Network Allocation Vector . . . . . . . . . . . . 28
4.2.2 Interframe Spacing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4.2.3 Contention Based Access . . . . . . . . . . . . . . . . . . . . . . . . 31
4.3 802.11b Fairness Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
5 Synergy MAC 35
5.1 The Synergy Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
5.2 The RTS frame . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
5.3 Relay Identification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
5.4 The CTS Frame . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
5.5 Cooperative Communication . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
5.6 NAV Update Mechanism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
ix
5.7 Comparing Cooperative MACs . . . . . . . . . . . . . . . . . . . . . . . . . 43
5.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
6 Simulations and Results 48
7 Conclusion 57
8 Future Work 59
Bibliography 61
x
List of Figures
2.1 Propagation mechanisms ? Reflection (R), Scattering (S), Diffraction (D) . . . . 7
2.2 Two pulses in time-variant multipath . . . . . . . . . . . . . . . . . . . . . . . 8
2.3 Typical slow and fast fading in an urban mobile environment . . . . . . . . . . . 9
2.4 Theoretical Bit Error Rate for Various Fading Conditions . . . . . . . . . . . . . 11
2.5 Interleaving in TDM Stream . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.6 Interleaving without TDM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.1 Cooperative system for an isolated link . . . . . . . . . . . . . . . . . . . . . . 18
3.2 Time division in cooperative coding . . . . . . . . . . . . . . . . . . . . . . . . 18
3.3 Two user cooperative coding performance for d1 = 1, d2 = 0.5 and d3 = 0.5, (13,
15, 15, 17) convolutional code, 100-byte frame size . . . . . . . . . . . . . . . . . 19
3.4 Cooperation in a network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.5 Illustration of the delay and throughput improvement achieved by cooperation in
the time domain . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4.1 The IEEE 802 family and its relation to the OSI model . . . . . . . . . . . . . . 25
4.2 BER vs. SNR for different 802.11b modulation schemes . . . . . . . . . . . . . . 27
4.3 A sample 802.11b network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.4 NAV propagation mechanism in 802.11b . . . . . . . . . . . . . . . . . . . . . . 29
4.5 Interframe spacing in 802.11b . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4.6 Effect of slow nodes in WLAN . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
5.1 IEEE 802.11b RTS frame format . . . . . . . . . . . . . . . . . . . . . . . . . . 37
5.2 Synergy MAC Control Frame exchange . . . . . . . . . . . . . . . . . . . . . . 38
xi
5.3 IEEE 802.11b CTS frame format . . . . . . . . . . . . . . . . . . . . . . . . . . 39
5.4 NAV update mechanism in Synergy MAC . . . . . . . . . . . . . . . . . . . . . 43
5.5 Flow chart at source node Ns . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
5.6 Flow chart at relay node Nr . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
5.7 Flow chart at destination node Nd . . . . . . . . . . . . . . . . . . . . . . . . . 46
6.1 Transmission ranges for different data rates of IEEE 802.11b . . . . . . . . . . . 48
6.2 Basic setup consisting a source, a relay and a destination . . . . . . . . . . . . . 49
6.3 Synergy MAC vs. IEEE 802.11b with zero traffic at relay . . . . . . . . . . . . . 51
6.4 Synergy MAC vs. IEEE 802.11b with traffic at relay . . . . . . . . . . . . . . . . 52
6.5 Throughput vs. Number of nodes in the network . . . . . . . . . . . . . . . . . 53
6.6 Throughput Gain(%) vs. Number of nodes in the network . . . . . . . . . . . . . 54
6.7 Throughput vs. Number of mobile nodes in the network . . . . . . . . . . . . . . 56
6.8 Throughput Gain(%) vs. Number of mobile nodes in the network . . . . . . . . . 56
8.1 Spatial reuse in Synergy MAC . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
xii
Chapter 1
Introduction
The ability to communicate with people on the move has evolved remarkably since
Guglielmo Marconi first demonstrated radio?s ability to provide continuous contact with
ships sailing the English Channel in 18971. Since then, wireless communication methods
and services have been enthusiastically adopted by people throughout the world. Partic-
ularly during the past ten years, the mobile radio communications industry has grown by
orders of magnitude fueled by digital and radio frequency (RF) circuit fabrication improve-
ments, newlarge-scalecircuitintegration and other miniaturizationtechnologies which make
portable radio equipment smaller, cheaper, and more reliable. Digital switching techniques
have facilitated the large scale deployment of affordable easy-to-use radio communication
networks. Scientists envision that these trends will continue at an even grater pace during
the next decade [1].
1.1 Evolution of Mobile Radio Communications
The foundations of wireless communication were laid by Michael Faraday?s work on
electromagnetism, which established that electric and magnetic effects result from ?lines of
force? that surround conductors and magnets. Based on Faraday?s work, James Maxwell
derived mathematical equations that represented the ?lines of force? that Faraday had ex-
plained. Maxwell published his work in a paper in 1855. Later, in 1861, Maxwell further
developed his work showing that if an electric charge was applied to a (hypothetical) elastic
fluid, it would result in the generation of waves that would travel through the medium. In
effect, Maxwell predicted the existence of electromagnetic waves. Friedrich Kohlrausch and
1The actual invention of radio communications more properly should be attributed to Nikola Tesla, who
gave a public demonstration in 1893. Marconi?s patents were overturned in favor of Tesla in 1943 [2].
1
Wilhem Weber furthered Maxwell?s work by calculating that these waves would travel at
the speed of light. Up until 1888, the field of electromagnetism was that of pure theory. In
that year, Heinrich Hertz discovered radio waves which are an example of electromagnetic
radiation. Hertz did this by devising a transmitting oscillator and a ?receiver?. The ?re-
ceiver? was basically a metal loop with a gap on one side. When this loop was placed within
the transmitter?s electromagnetic field, sparks were produced across the gap in the loop.
This proved that electromagnetic waves could be sent out into space and remotely detected.
In effect, Hertz showed that the elastic fluid that Maxwell had hypothesized could be the
ether. The discovery of radio waves confirmed the ideas of Maxwell and other scientists
who had worked on electromagnetism and sparked a greater interest in the field.
WhenGuglielmoMarconilearnedaboutHertz?swork, herealizedthatiftheradiowaves
could be transmitted over large distances, wireless telegraphy could be developed. Marconi
started experimenting with this idea, and by 1894, managed to receive radio signals at a
distance of over a mile. Marconi tried to develop his work further by taking the help of
the Italian government. However, the Italian government was not interested. So, Marconi
approached the British government. He was granted a patent for wireless telegraphy in 1897
and the world?s first radio factory was setup at Chelmsford in 1898. Soon, radios started to
be used commercially. The world of wireless telegraphy got another big boost in 1901 when
Marconi and his associates were able to successfully receive a signal across the Atlantic.
Recognizing his contribution to the field of wireless communication, Marconi was awarded
the Nobel Prize in 1909 [3].
Radio technology has since advanced rapidly to enable transmissions over larger dis-
tances with better quality, less power and smaller, cheaper devices, thereby enabling public
and private radio communications, television and wireless networking. While early radio
systems transmitted analog signals, today most radio systems transmit digital signals com-
posed of binary bits obtained either by digitizing an analog signal or by directly reading a
digital stream. A digital radio can transmit a continuous bit stream or it can group the bits
into packets. The latter type of radio is called a packet radio and is often characterized by
2
bursty transmissions: the radio is idle except when it transmits a packet, although it may
transmit packets continuously. The first network based on packet radio, ALOHANET, was
developed at the University of Hawaii in 1971. This network enabled computer sites at seven
campuses spread out over four islands to communicate with a central computer on Oahu
island via radio transmissions. The ALOHANET network architecture used a star topology
with the central computer at its hub. Any two computers could establish a bi-directional
communications link with each other by going through the central hub. ALOHANET in-
corporated the first set of protocols for channel access and routing in packet radio systems
and many of the underlying principles in those protocols are still in use today [4].
In 1985, the Federal Communications Commission (FCC) enabled the commercial de-
velopment of wireless LANs by authorizing the public use of the Industrial, Scientific and
Medical (ISM) frequency bands for wireless LAN products. The ISM band was attractive to
wireless LAN vendors because they did not need to obtain an FCC license to operate in this
band. By late 1990, vendors began introducing products based on wireless LAN technolo-
gies which operated in the 900 megahertz (MHz) frequency band. These solutions, which
used non-standard, proprietary designs, provided data transfer rates of approximately 1
megabit per second (Mbps). This was significantly slower than the 10 Mbps speed provided
by most wired local area networks (LAN) at that time. In 1992, vendors began selling
wireless LAN (WLAN) products that used the 2.4 gigahertz (GHz) band. Although these
products provided higher data transfer rates than 900 MHz band products, they also used
proprietary designs. The need for interoperability among different brands of WLAN prod-
ucts led to several organizations developing wireless networking standards [5]. Subsection
1.1.1 briefly describes the IEEE 802.11 family of standards.
1.1.1 IEEE 802.11 Standards
In 1997, IEEE ratified the 802.11 standard [6] for wireless LANs. The IEEE 802.11
standard supports three transmission methods, including radio transmission within the
2.4 GHz band. In 1999, IEEE ratified two amendments to the 802.11 standard?802.11a
3
Table 1.1: Summary of IEEE 802.11 WLAN Technologies
IEEE Standard
of amendment
Maximum
Data
Rate
Typical
Range
Frequency
Band
Comments
802.11 2 Mbps 50-100
meters
2.4 GHz -
802.11a 54 Mbps 50-100
meters
5 GHz Not compatible with 802.11b
802.11b 11 Mbps 50-100
meters
2.4 GHz Most dominant WLAN technology
802.11g 54 Mbps 50-100
meters
2.4 GHz Backward compatible with 802.11b
and 802.11b?that define radio transmission methods. Wireless LAN equipment based
on IEEE 802.11b [7] quickly became the dominant wireless technology. IEEE 802.11b
equipment transmits in the 2.4 GHz band, offering data rates of up to 11 Mbps. IEEE
802.11b was intended to provide performance, throughput, and security features comparable
to wired LANs. In 2003, IEEE released the 802.11g amendment, which specifies a radio
transmission method that uses the 2.4 GHz band and can support data rates of up to 54
Mbps. Additionally, IEEE 802.11g-compliant products are backward compatible with IEEE
802.11b-compliant products. Table 1.1 compares the basic characteristics of IEEE 802.11,
802.11a, 802.11b, and 802.11g. IEEE 802.11 wireless networking is also known as Wi-Fi.
Table 1.1 does not include all current and pending 802.11 amendments. For example, in
November2005, IEEEratifiedIEEE802.11e, whichprovidesqualityofserviceenhancements
to IEEE 802.11 that improves the delivery of multimedia content. The IEEE 802.11n project
is specifying IEEE 802.11 enhancements that will enable data throughput of at least 100
Mbps [5]. The publication of the final IEEE 802.11n spec is expected in April 2009. However
products based on the draft 802.11n are already available in market.
4
1.2 Propagation Limitations
Since the advent of IEEE 802.11 standard, wireless local area networks have gained
widespread acceptance in providing broadband wireless access to portable devices. How-
ever, like with any radio transmission, impairments in the propagation channel of wireless
LANs can disturb the information carried by the transmitted signal. The resulting channel
disturbance can be a combination of additive noise, multiplicative fading and distortion due
to time dispersion. Among all these impairments that cause bit errors in wireless trans-
missions, fading is perhaps the most challenging one. We take a closer look at fading, its
effects and available countermeasures in Chapter 2.
5
Chapter 2
Fading in Wireless Environment
Perhaps the most challenging technical problem facing communications system engi-
neers is fading in the wireless environment. The term fading refers to the time variation of
received signal power caused by changes in the transmission medium or path(s). In a fixed
environment, fading is affected by changes in atmospheric conditions such as rainfall. But
in a mobile environment, where one of the two antennas is moving relative to the other,
the relative location of various obstacles changes over time, creating complex transmission
effects.
2.1 Multipath Propagation
All three propagation mechanisms, illustrated in Figure 2.1 obtained from [8], con-
tribute towards multi-path propagation. Reflection occurs when an electromagnetic signal
encounters a surface that is large relative to the wavelength of the signal. For example, sup-
pose a ground-reflected wave near the mobile unit is received. Because the ground-reflected
wave has a 180 degree phase shift after reflection, the ground wave and the line-of-sight wave
may tend to cancel, resulting in high signal loss1. Further, because the mobile antenna is
lower than most human-made structures in the area, multi-path interference occurs. These
reflected waves may interfere constructively or destructively at the receiver.
Diffraction occurs at the edge of an impenetrable body that is large compared to the
wavelength of the radio wave. When a radio wave encounters such an edge, waves propagate
in different directions with the edge as the source. Thus signals can be received even when
there is no unobstructed line of sight (LOS) from the transmitter.
1On the other hand, the reflected signal has a longer path, which creates a phase shift due to delay
relative to the un-reflected signal. When this delay is equivalent to half a wavelength, the two signals are
back in phase
6
Figure 2.1: Propagation mechanisms ? Reflection (R), Scattering (S), Diffraction (D)
If the size of an obstacle is on the order of the wavelength of the signal or less, Scat-
tering occurs. An incoming signal is scattered into several weaker outgoing signals. At
typical cellular microwave frequencies, there are numerous objects, such as lamp posts and
traffic signs that can cause scattering. Thus scattering effects are difficult to predict.
These three propagation effects influence system performance in various ways depend-
ing on local conditions and as the mobile unit moves within a cell. If a mobile unit has
a clear LOS to the transmitter, then diffraction and scattering are generally minor effects,
although reflection may have a significant impact. If there is no clear LOS, such as in
urban area at street level, then diffraction and scattering are the primary means of signal
reception.
2.2 Effects of Multipath Propagation
As just noted, one unwanted effect of multi-path propagation is that multiple copies
of a signal may arrive at different phases. If these phases add destructively, the signal level
relative to noise declines, making signal detection at the receiver more difficult.
7
A second phenomenon, of particular importance for digital transmission, is inter-symbol
interference (ISI). Consider that we are sending a narrow pulse at a given frequency across
a link between a fixed antenna and a mobile unit. Figure 2.2 obtained from [8], shows what
the channel may deliver to the receiver if the impulse is sent at two different times. The
upper line shows two pulses at the time of transmission. The lower line shows the resulting
pulses at the receiver. In each case the first received pulse is the desired LOS signal.
The magnitude of that pulse may change because of changes in atmospheric attenuation.
Further, as the mobile unit moves farther away from the fixed antenna, the amount of
LOS attenuation increases. But in addition to this primary pulse, there may be multiple
secondary pulses due to reflection, diffraction, and scattering. Now suppose that this pulse
encodes one or more bits of data. In that case, one or more delayed copies of a pulse may
arrive at the same time as the primary pulse for a subsequent bit. These delayed pulses act
as a form of noise to the subsequent primary pulse, making recovery of the bit information
at the receiver more difficult.
Figure 2.2: Two pulses in time-variant multipath
As the mobile antenna moves, the location of various obstacles changes; hence the
number, magnitude and timing of the secondary pulses change. This makes it difficult to
8
design signal processing techniques that will filter out multi-path effects so that the intended
signal is recovered with fidelity.
2.3 Types of Fading
Fading effects in a wireless environment can be classified as either fast or slow. Refer-
ring to Figure 2.1 obtained from [8], as the mobile unit moves down a street in an urban
environment, rapid variations in signal strength occur over distances of about one-half a
wavelength. At a frequency of 900 MHz, which is typical for mobile cellular applications, a
wavelength is 0.33m. The rapidly changing waveform in Figure 2.3 obtained from [8] shows
an example of spatial variation of received signal amplitude at 900 MHz in an urban setting.
Note that changes of amplitude can be as much as 20 or 30 db over a short distance. This
type of rapidly changing fading phenomenon, known as fast fading, affects not only mobile
phones in automobiles, but even a mobile phone user walking down an urban street.
Figure 2.3: Typical slow and fast fading in an urban mobile environment
As the mobile user covers distances well in excess of a wavelength, the urban environ-
ment changes, as the user passes buildings of different heights, vacant lots, intersections
and so forth. Over these longer distances, there is a change in the average received power
level about which the rapid fluctuations occur. This is indicated by the slowly changing
waveform in Figure 2.3 and is referred to as slow fading.
9
Fading effects can also be classified as flat or selective. Flat fading, or nonselective
fading, is that type of fading in which all frequency components of the received signal
fluctuate in the same proportions simultaneously. Selective fading affects unequally the
different spectral components of a radio signal. The term selective fading is usually signif-
icant only relative to the bandwidth of the overall communications channel. If attenuation
occurs over a portion of the bandwidth of the signal, the fading is considered to be selec-
tive; non-selective fading implies that the signal bandwidth of interest is narrower than and
completely covered by the spectrum affected by the fading.
2.4 Fading Channel
In designing a communications system, the communications engineer needs to estimate
the effects of multi-path fading and noise on the mobile channel. The simplest channel
model, from the point of view of analysis is theadditive white Gaussian noise (AWGN)
channel. In this channel, the desired signal is degraded by the thermal noise associated with
the physical channel itself as well as electronics at the transmitter and receiver (and any
intermediate amplifiers or repeaters). This model is fairly accurate in some cases, such as
space communications and some wire transmissions, such as coaxial cable. For terrestrial
wireless transmission, particularly in the mobile station, AWGN is not a good guide for the
designer.
Rayleighfading occurs when there are multiple indirect paths between transmitter and
receiver and no distinct dominant path, such as an LOS path. This represents a worst case
scenario. Fortunately Rayleigh fading can be dealt with analytically, providing insights into
performance characteristics that can be used in difficult environments, such as downtown
urban settings.
Rician fading best characterizes a situation where there is a direct LOS path in addi-
tion to a number of indirect multi-path signals. The Rician model is often applicable in an
indoor environment whereas the Rayleigh model characterizes outdoor settings. The Rician
10
Figure 2.4: Theoretical Bit Error Rate for Various Fading Conditions
model also becomes more applicable in smaller cells or in more open outdoor environments.
The channels can be characterized by a parameter K, as defined in the equation 2.1.
K = power in the dominant pathpower in the scattered path (2.1)
When K = 0 the channel is Rayleigh (i.e., numerator is zero) and when K = ?, the
channel is AWGN (i.e., denominator is zero). Figure 2.4 obtained from [8], shows system
performance in the presence of noise. Here bit error rate is plotted as a function of the
ratio Eb/N0?. Of course, as the ratio increases, the bit error rate drops. The figure shows
?Eb/N0 is the ratio of signal energy per bit to noise power density per Hertz. It is related to signal-to-noise
ratio (SNR) and is more convenient for determining digital data rates and error rates.
11
that with a reasonably strong signal, relative to noise, an AWGN exhibit provides fairly
good performance, as do Rician channels with larger values of K, roughly corresponding
to micro cells or an open country environment. The performance would be adequate for
digitized voice application, but for digital data transfer, efforts to compensate would be
needed. The Rayleigh channel provides relatively poor performance; this is likely to be seen
for flat fading and for slow fading; in these cases, error compensation mechanisms become
more desirable. Finally, some environments produce fading effects worse than the so-called
worst case Rayleigh. Examples are fast fading in an urban environment and the fading
within the affected band of a selective fading channel. In these cases, no level of Eb/N0 will
help achieve the desired performance, and compensation mechanisms are mandatory.
2.5 Diversity for Error Compensation
Diversity is based on the fact that individual channels experience independent fading
events. We can therefore compensate for error effects by providing multiple logical channels
in some sense between transmitter and receiver and sending part of the signal over each
channel. This technique does not eliminate errors but it does reduce the error rate, since
we have spread the transmission out to avoid being subjected to the highest error rate that
might occur. Other techniques like equalization and forward error correction can then cope
with the reduced error rate.
Some diversity techniques involve the physical transmission path and are referred to as
space diversity. For example, multiple nearby antennas may be used to receive the mes-
sage, with the signals combined in some fashion to reconstruct the most likely transmitted
signal. Another example is the use of collocated multiple directional antennas, each oriented
to a different reception angle with the incoming signal again combined to reconstitute the
transmitted signal.
More commonly, the term diversity refers to frequency diversity or time diversity
techniques. With frequency diversity, the signal is spread out over a large frequency band-
width or carried on multiple frequency carriers.
12
Figure 2.5: Interleaving in TDM Stream
Time diversity techniques aim to spread the data out over time so that a noise burst
affects fewer bits. Time diversity can be quite effective in a region of slow fading. If a mobile
unit is moving slowly, it may remain in a region of a high level of fading for a relatively
long interval. The result will be a long burst of errors even though the local mean signal
level is much higher than the interference. Even powerful error correction codes may be
unable to cope with an extended error burst. If digital data is transmitted in a time division
multiplex (TDM) structure, in which multiple users share the same physical channel by the
use of time slots, then block interleaving can be used to provide time diversity. Figure
2.5 obtained from [8] illustrates the concept. Note that the same number of bits are still
affected by the noise surge, but they are spread out over a number of logical channels. If
each channel is protected by forward error correction, the error-correcting code may be able
to cope with the fewer number of bits that are in error in a particular logical channel. If
TDM is not used, time diversity can still be applied by viewing the stream of bits from the
source as a sequence of blocks and then shu?ing the blocks. In Figure 2.6 obtained from
[8], blocks are shu?ed in groups of four. Again, the same number of bits is in error, but
the error correcting code is applied to sets of bits that are spread out in time. Even greater
diversity is achieved by combining TDM interleaving with block shu?ing.
13
Figure 2.6: Interleaving without TDM
The tradeoff with time diversity is delay. The greater the degree of interleaving and
shu?ing used, the longer the delay in reconstructing the original sequence at the receiver
[8].
2.5.1 Cooperative Diversity
When one examines all forms of diversity discussed in previous sections, spatial diver-
sity emerges as the type that is most attractive. Spatial diversity relies on the principle
that signals transmitted from geographically separated transmitters, and/or to geograph-
ically separated receivers, experience fading that is independent. Therefore, independent
of whether other forms of diversity are being employed, having multiple transmit antennas
is desirable due to the spatial diversity they provide [9]. However, this is impractical, if
not infeasible, mostly due to the size and energy constraints of commonly found wireless
devices.
Recent research on cooperative communication [9] [10] [11] [12] [13] [14] demonstrates
that spatial diversity can also be achieved by exploiting some unique features of the under-
lying wireless medium. The inherent broadcast nature of the wireless channel suggests that
any signal transmitted on the medium can be overheard by all nodes within the receiving
14
range. If such nodes were to retransmit the overheard signal towards the destination rather
than discarding it completely, they would effectively provide the destination with extra ob-
servations of the source signal. These observations at the destination are all dispersed in
space and are akin to observations resulting from MIMO systems. In short, one can think
of a cooperative system as a virtual antenna array, where each antenna in the array cor-
responds to one of the assisting neighbors [14]. Such spatial diversity resulting from nodal
cooperation is called cooperative diversity. Chapter 3 describes the notion of physical layer
cooperation and cooperative diversity in greater detail.
15
Chapter 3
Cooperative Communication
The burgeoning demand for mobile data networks has highlighted some constraints
on its future growth. Wireless links have always had orders of magnitude less bandwidth
than their wired counterparts. Mobile users have always chafed at this limitation, which
essentially forces them to use applications in a manner reminiscent of wired networks of
decades past, albeit freeing them from a desktop. Newer technologies such as multiple-input
multiple-output (MIMO) systems are starting to increase the number of bits per second per
hertz of bandwidth through spatial multiplexing, and to improve the robustness/range of the
wireless link for a given data rate through space-time coding and beamforming. However,
all these improvements come at the cost of multiple RF front ends at both the transmitter
and the receiver. Furthermore, the size of the mobile devices may limit the number of
antennas that can be deployed. Even when MIMO technology is feasible, wireless engineers
are running into another roadblock: the inefficient way the electromagnetic spectrum has
been allocated to different classes of users, mainly for historical or regulatory reasons. Thus,
while large portions of the spectrum are grossly underused, the popular unlicensed bands
are very crowded. Given this limitation, for unlicensed bands, the issue of interference from
having too many users has become as important as how much bandwidth can be squeezed
from it.
One way to address these problems is by using the notion of cooperation between
wireless nodes. Consider the following analogy from everyday life that vividly portrays
cooperative wireless communications.
?Denise and her husband Mitch are at opposite ends of a living room at a
crowded party. Denise tries to attract Mitch?s attention and shouts something
16
at him. All Mitch can hear is the word ?Let?s.? Celine, in the middle of the
room, who overhears Denise and notices their predicament, repeats to Mitch
the part she hears: ?Go home.? This time, all Mitch hears is the word ?home.?
Mitch finally figures out that his wife wants to go home.?
The above analogy portrays the essential element of cooperative wireless communi-
cations, namely, utilizing information overheard by neighboring nodes to provide robust
communication between a source and its destination. In cooperative communications, such
neighboring nodes in a wireless network work together to form a virtual antenna array.
Using cooperation, it is possible to exploit the spatial diversity of the traditional MIMO
techniques without each node necessarily having multiple antennas. Multihop networks
use some form of cooperation by enabling intermediate nodes to forward the message from
source to destination. However, cooperative communication techniques described in this
work are fundamentally different in that the relaying nodes can forward the information
fully or in part. Also the destination receives multiple versions of the message from the
source, and one or more relays and combines these to obtain a more reliable estimate of the
transmitted signal as well as higher data rates.
3.1 Underlying Concepts
This section introduces some basic concepts that underlie cooperative communications.
Cooperative techniques utilize the broadcast nature of wireless signals by observing that
a source signal intended for a particular destination can be ?overheard? at neighboring
nodes. These nodes, called relays, partners, or helpers, process the signals they overhear
and transmit towards the destination. The relay operations can consist of repetition of the
overheard signal (obtained, for example, by decoding and then re-encoding the information
or by simply amplifying the received signal and then forwarding), or can involve more
sophisticated strategies such as forwarding only part of the information, compressing the
overheard signal, and then forwarding. The destination combines the signals coming from
17
the source and the relays, enabling higher transmission rates and robustness against channel
variations due to fading. Such spatial diversity arising from cooperation is not exploited
in current cellular, wireless LAN, or ad hoc systems; only one copy of the signal, whether
it comes from the mobile directly or from a relay, is processed at the destination. Hence,
cooperative relaying is substantially different than traditional multihop or infrastructure
based methods.
Figure 3.1: Cooperative system for an isolated link
Figure 3.2: Time division in cooperative coding
This notion of cooperation dates back to the relay channel model in information the-
ory extensively studied in the 1970s by Cover and El Gamal [15], but we owe the recent
popularity to [9] [10] [11] [12] [13] [14], which showed the benefits of cooperative relaying
in a wireless environment. In order to illustrate the idea of cooperation and cooperative
diversity at the physical layer, let us consider the cooperative coding scheme used in [16]
and [17]. Let us consider an isolated source S who wants to communicate with a destination
18
D with the help of a cooperative relay R, as illustrated in Figure 3.1 obtained from [19].
Here, di denotes the distances between the nodes.
Figure 3.3: Two user cooperative coding performance for d1 = 1, d2 = 0.5 and d3 = 0.5, (13, 15,
15, 17) convolutional code, 100-byte frame size
For direct transmission (i.e., if the relay R is not utilized), each channel block, or
packet, contains B data bits and r parity bits for forward error correction (FEC), leading
to a total of N = B+r coded bits, as shown at the top of Figure 3.2 obtained from [19]. For
ease of exposition, let us have r >= B. Let us assume that cyclic redundancy check (CRC)
is employed for error detection. In order to cooperate, S divides its channel block into two
and only transmits in the first half, as shown at the bottom of Figure 3.2. Hence, in the
cooperative mode S ends up sending only half of its coded bits. These bits are received
both by the destination D and by the relay R. The relay observes a higher coding rate and
thus a weaker FEC. Nevertheless, it attempts to decode the underlying B data bits. If R
has the correct information (which can be checked using the CRC), it re-encodes and sends
19
the remaining N/2 parity bits in the second half of S?s time slot. Otherwise, R informs
S that there was a failure in decoding, and S continues transmission. Therefore, when R
decodes correctly, the destination will receive half the coded bits from S and the remaining
ones from R, thus creating spatial diversity. The question is how often this happens and
how it affects the overall error performance.
Figure 3.3 obtained from [19], illustrates simulation results for frame error rate (FER)
versus the total transmit signal-to-noise ratio (SNR) for the scenario where the relay is
located halfway between the source and destination (i.e., d1= 1.0, d2 = 0.5, and d3 =
0.5). Note that direct transmission and cooperative coding use the same total power and
bandwidth (considering a low-mobility environment). Hence, along with path loss, the
assumption is that all links experience independent slow Rayleigh fading that stays constant
for the duration of each packet. The nodes use convolutional coding and each node has the
same average power constraint. We observe from the figure that for an error rate of 10?3 we
obtain about 18 dB improvement in SNR with cooperation. Also, the FER for cooperative
coding decreases at a much faster rate than direct transmission; in fact, cooperation is able
to achieve two full levels of diversity similar to a MIMO system with two transmit antennas
and one receive antenna.
The above example considers one particular cooperative scheme to obtain diversity, yet
it shows the potential of cooperation at the physical layer. Indeed, there is a rich literature
on physical-layer cooperation that investigates many aspects, such as cooperative protocols
for two or more users, performance bounds for cooperative systems, resource allocation for
cooperation, and partner-choice strategies.
3.2 Benefits of Cooperative Networking
From the perspective of the network, cooperation can benefit not only the nodes in-
volved, but the whole network in many different aspects. For illustration purposes, only a
few potential benefits are explained below.
20
3.2.1 Higher Spatial Diversity
As a simple example, Figure 3.4 obtained from [19], shows a small network of four
mobile nodes. If the channel quality between mobile nodes S and D degrades severely (e.g.,
due to shadow or small-scale fading), a direct transmission between these two nodes may
experience an intolerable error rate, which in turn leads to retransmissions. Alternatively,
S can exploit spatial diversity by having a relay R1 overhear the transmissions and then
forward the packet to D as discussed above. The source S may resort to yet another terminal
R2 for help in forwarding the information, or use R1 and R2 simultaneously [18]. Similar
ideas apply to larger networks as well. Therefore, compared with direct transmission, the
cooperative approach enjoys a higher successful transmission probability. We note here that
cooperative communications has the ability to adapt and to mitigate the effects of shadow
fading better than MIMO since, unlike MIMO, antenna elements of a cooperative virtual
antenna array are separated in space and experience different shadow fading.
Figure 3.4: Cooperation in a network
21
Figure 3.5: Illustration of the delay and throughput improvement achieved by cooperation in the
time domain
3.2.2 Higher Throughput-Lower Delay
At the physical layer, rate adaptation is achieved through adaptive modulation and
adaptive channel coding. Many MAC protocols have introduced rate adaptation to combat
adverse channel conditions. For instance, when a high channel error rate is encountered
due to a low average SNR, the wireless LAN standard IEEE 802.11 switches to a lower
transmission rate so as to guarantee a certain error rate. The power of cooperation is
evident when it is applied in conjunction with any rate adaptation algorithm. In Figure 3.4,
specifically, if Rate2 and Rate3 are higher than Rate1 such that the total transmission time
for the two-hop case through R2 is smaller than that of the direct transmission, cooperation
readily outperforms the legacy direct transmission, in terms of both throughput and delay
perceived by the source S. Furthermore, for relays such as R1 and R2, it turns out that their
own individual self-interest can be best served by helping others. As further illustrated in
Figure 3.5 obtained from [19], the intermediate node R1 that cooperates enjoys the benefit
of lower channel-access delay, which in turn can be translated into higher throughput.
3.2.3 Lower Power Consumption and Lower Interference
The diversity, error rate, and throughput gains obtained through cooperation can be
traded in for power savings at the terminals. Alternatively, cooperation leads to an extended
coverage area when the performance metric (error rate, throughput, etc.) is fixed.
22
The advantage of cooperation also leads to reduced interference when the network is
deployed in a cellular fashion to reuse a limited bandwidth. With the improvement of
throughput, we can reduce the average channel time used by each station to transfer a
certain amount of traffic over the network. Therefore, the signal-to-interference ratio (SIR)
between proximal cells using the same channel can be reduced, and a more uniform coverage
can be achieved. As wireless network deployments become denser, a reduction of SIR will
directly lead to a boost in network capacity. Indeed, the problem of dense deployment has
already been reported for IEEE 802.11 b/g networks, which have only three non-overlapping
channels.
3.2.4 Adaptability to Network Conditions
The cooperative communication paradigm allows wireless terminals to seamlessly adapt
to changing channel and interference conditions. The choice of relays, cooperation strategy,
and the amount of resources available for cooperation can be opportunistically decided.
For example, in Figure 3.4, if the source S has some information about the current channel
gains, packet-loss rates, traffic conditions, interference, or remaining battery energy of nodes
in the network, it may choose to transmit its information directly to its destination D, using
R1 or R2 or both in a cooperative fashion, depending on which transmission mode results
in better performance (in terms of error rates, throughput, or power). This way, a surplus
of resources such as battery energy or bandwidth at a particular node can be utilized by
other nodes in the network in a manner that will benefit everyone, including the relay node
itself.
Although originating from physical-layer cooperation, all the aforementioned benefits
cannot be fully realized until proper mechanisms have been incorporated at higher protocol
layers (e.g., MAC, network) and the necessary information is made available from the lower
layer (e.g., PHY) [19]. Therefore it is imperative that the idea of node cooperation be
extended to other layers of the protocol stack especially the medium access control (MAC)
sub-layer. Further, if such re-designed, cooperation aware MAC sub-layer is compatible
23
with IEEE 802.11b standard, a large number of devices despite their legacy hardware,
could potentially derive the benefits of cooperation. Subsequent chapters shall discuss in
detail the design and analysis of one such IEEE 802.11b compatible, cooperative MAC
protocol, called the Synergy MAC.
24
Chapter 4
Overview of IEEE 802.11b
802.11 is a member of the IEEE 802 family, which is a series of specifications for local
area network (LAN) technologies. Figure 4.1 obtained from [20], shows the relationship
between the various components of the 802 family and their place in the OSI model. IEEE
802 specifications are focused on the two lowest layers of the OSI model because they
incorporate both physical and data link components. Medium access control (MAC) in the
link component, is a set of rules to determine how to access the medium and send data. The
details of transmission and reception however, are left to the physical (PHY) component.
Figure 4.1: The IEEE 802 family and its relation to the OSI model
Individual specifications in the 802 series are identified by a second number. For ex-
ample, 802.3 is the specification for a Carrier Sense Multiple Access network with Collision
Detection (CSMA/CD). Similarly other specifications describe other parts of the 802 pro-
tocol stack. 802.2 specifies a common link layer, the Logical Link Control (LLC), which can
be used by any lower-layer LAN technology. 802.11 on the other hand specifies a link layer
for mobile networks that relies on 802.2/LLC encapsulation. The base 802.11 specification
includes the 802.11 MAC and two physical layers: a frequency hopping spread-spectrum
(FHSS) physical layer and a direct-sequence spread-spectrum (DSSS) link layer. Later
25
revisions to 802.11 added additional physical layers. 802.11b specifies a high-rate direct-
sequence layer (HR/DSSS) while 802.11a describes a physical layer based on orthogonal
frequency division multiplexing (OFDM) [20].
4.1 802.11b PHY Layer
802.11b provides three variations for PHY layer. These include Direct Sequence Spread
Spectrum (DSSS), Frequency Hopping Spread Spectrum (FHSS), and Infrared. In practice,
only DSSS has any significant presence in the market.
802.11b DSSS operates in the 2.4 GHz ISM band which is allocated from 2400 to
2483 MHz. The channel assignments in North America are channels 1 to 11, starting
at 2412 MHz and spaced at 5 MHz intervals to 2462 MHz. Each channel is about 22
MHz wide so there is substantial overlap. Therefore, channels 1, 6, and 11 can be used
as non-overlapping channels. The DSSS system has different modulation modes for every
transmission rate. These are: Differential Binary Phase Shift Keying (DBPSK) for 1Mbps,
Differential Quaternary Phase Shift Keying (DQPSK) for 2Mbps and Complementary Code
Keying (CCK) for 5.5Mbps and 11Mbps. The spreading is performed by multiplying binary
data by a pseudo random (PN) binary waveform. At 1 and 2Mbps, the PN code is an 11-
chip long Barker sequence. For the CCK modulation, 8-chip long Walsh codes are used.
The transmitter divides the data into 4-bits or 8-bits. At 5.5Mbps, 2 of the 4 bits are
used to select one of 4 complex spread sequences from a table of CCK sequences and then
DQPSK modulates this sequence with the other two bits. At 11Mbps, 6 bits are used to
select one of 64 sequences and the remaining 2 bits are used for modulation. For 5.5Mbps
data rate, 4 bits are encoded into the 8-chip long codeword. So the processing gain is only
2. For the 11Mbps data rate, there?s no processing gain because 8 bits are encoded into
8-chips.
Figure 4.2, obtained from [21], shows the Bit Error Rate (BER) vs. Signal to Noise
Ratio (SNR) for different modulation schemes of 802.11b. While these curves can be derived
theoretically as well, for the purpose of this paper and to achieve a solution closer to
26
Figure 4.2: BER vs. SNR for different 802.11b modulation schemes
reality, we use these empirical curves provided by Intersil for its HFA3861B chip. From the
figure we can derive that given a BER one can find the most suitable 802.11b modulation
scheme to use based on the received SNR. Because path loss determines SNR, we can
also derive that higher transmission rates are possible only when communicating nodes are
sufficiently close by. This leads to the hypothesis that when the communicating nodes are
far apart, it might be advantageous to utilize an intermediate relay for data transmission.
This is because the source-relay and relay-destination transmissions can both employ better
modulation schemes when compared to source-destination transmissions on account of high
SNR resulting from physical proximity.
4.2 802.11b MAC Layer
In all IEEE 802.11 standards, access to the wireless medium is controlled by the MAC
sub-layer?s coordination functions. 802.11b?s MAC sub-layer supports two such functions -
distributed coordination function (DCF) for an Ethernet-like contention based CSMA/CA
27
access and point coordination function (PCF) for contention free frame transfers. The two
are explained below:
? The DCF is the basis of the standard CSMA/CA access mechanism. Like Ethernet, it
first checks to see that the radio link is clear before transmitting. To avoid collisions,
stations use a random backoff after each frame, with the first transmitter seizing the
channel. In some circumstances, the DCF may use the CTS/RTS clearing technique
to further reduce the possibility of collisions.
? Point coordination provides contention-free services. Special stations called point
coordinators are used to ensure that the medium is provided without contention.
Point coordinators reside in access points, so the PCF is restricted to infrastructure
networks. To gain priority over standard contention-based services, the PCF allows
stations to transmit frames after a shorter interval. The PCF is not widely imple-
mented in 802.11b based products. Hence in this work, our focus will remain on
DCF.
4.2.1 Carrier Sensing and Network Allocation Vector
Carrier sensing is used to determine if the medium is available. Two types of carrier
sensing functions in 802.11b manage this process: the physical carrier-sensing and virtual
carrier-sensing functions. If either carrier-sensing function indicates that the medium is
busy, the MAC reports this to higher layers.
Physical carrier-sensing functions are provided by the physical layer in question and
depend on the medium and modulation used. It is difficult (or, more to the point, expen-
sive) to build physical carrier-sensing hardware for RF-based media, because transceivers
can transmit and receive simultaneously only if they incorporate expensive electronics. Fur-
thermore, with hidden nodes potentially lurking everywhere, physical carrier-sensing cannot
provide all the necessary information.
28
Virtual carrier-sensing is provided by the Network Allocation Vector (NAV). Most
802.11b frames carry a duration field, which can be used to reserve the medium for a fixed
time period. The NAV is a timer that indicates the amount of time the medium will be
reserved. Stations set the NAV to the time for which they expect to use the medium,
including any frames necessary to complete the current operation. Other stations count
down from the NAV to 0. When the NAV is nonzero, the virtual carrier-sensing function
indicates that the medium is busy; when the NAV reaches 0, the virtual carrier-sensing
function indicates that the medium is idle.
Figure 4.3: A sample 802.11b network
Figure 4.4: NAV propagation mechanism in 802.11b
By using the NAV, stations can ensure that atomic operations are not interrupted.
For example, consider the wireless network depicted in Figure 4.3. To ensure that the
sequence is not interrupted, node Ns sets the NAV in its RTS to block access to the medium
while the RTS is being transmitted. All stations that hear the RTS defer access to the
29
medium until the NAV elapses. RTS frames are not necessarily heard by every station in
the network. Therefore, the recipient of the intended transmission, Nd responds with a CTS
that includes a shorter NAV. This NAV prevents other stations from accessing the medium
until the transmission completes. After the sequence completes, the medium can be used by
any station after distributed interframe space (DIFS), which is depicted by the contention
window in Figure 4.4.
4.2.2 Interframe Spacing
As with traditional Ethernet, the interframe spacing plays a large role in coordinating
access to the transmission medium. Three of them are used to determine medium access;
the relationship between them is shown in Figure 4.5 obtained from [21].
Figure 4.5: Interframe spacing in 802.11b
Varying interframe spacings create different priority levels for different types of traffic.
The logic behind this is simple: high-priority traffic doesn?t have to wait as long after the
medium has become idle. To assist with interoperability between different data rates, the
interframe space is a fixed amount of time, independent of the transmission speed.
The SIFS is used for the highest-priority transmissions, such as RTS/CTS frames and
positive acknowledgments. High-priority transmissions can begin once the SIFS has elapsed.
The PIFS is used by the PCF during contention-free operation. Stations with data to
transmit in the contention-free period can transmit after the PIFS has elapsed and preempt
30
any contention-based traffic. The DIFS is the minimum medium idle time for contention-
based services. Stations may have immediate access to the medium if it has been free for a
period longer than the DIFS.
Atomic operations start like regular transmissions: they must wait for the DIFS before
they can begin. However, the second and any subsequent steps in an atomic operation
take place using the SIFS, rather than during the DIFS. This means that the second (and
subsequent) parts of an atomic operation will grab the medium before another type of frame
can be transmitted. By using the SIFS and the NAV, stations can seize the medium for as
long as necessary.
4.2.3 Contention Based Access
The DCF allows multiple independent stations to interact without central control,
and thus may be used in either ad hoc networks or in infrastructure networks. Before
attempting to transmit, each station checks whether the medium is idle. If the medium is
not idle, stations defer to each other and employ an orderly exponential backoff algorithm
to avoid collisions. In distilling the 802.11b MAC rules, there is a basic set of rules that are
always used, and additional rules may be applied depending on the circumstances. Two
basic rules apply to all transmissions using the DCF:
? If the medium has been idle for longer than the DIFS, transmission can begin immedi-
ately. Carrier sensing is performed using both a physical medium dependent method
and the virtual (NAV) method.
? If the previous frame was received without errors, the medium must be free for
at least the DIFS.
? If the previous transmission contained errors, the medium must be free for the
amount of the EIFS.
? If the medium is busy, the station must wait for the channel to become idle. 802.11b
refers to the wait as access deferral. If access is deferred, the station waits for
31
the medium to become idle for the DIFS and prepares for the exponential backoff
procedure.
Additional rules may apply in certain situations. Many of these rules depend on the
particular situation ?on the wire? and are specific to the results of previous transmissions.
? Error recovery is the responsibility of the station sending a frame. Senders expect
acknowledgments for each transmitted frame and are responsible for retrying the
transmission until it is successful.
? Positive acknowledgments are the only indication of success. Atomic exchanges
must complete in their entirety to be successful. If an acknowledgment is ex-
pected and does not arrive, the sender considers the transmission lost and must
retry.
? All unicast data must be acknowledged.
? Any failure increments a retry counter, and the transmission is retried. A failure
can be due to a failure to gain access to the medium or a lack of an acknowl-
edgment. However, there is a longer congestion window when transmissions are
retried
? Multiframe sequences may update the NAV with each step in the transmission pro-
cedure. When a station receives a medium reservation that is longer than the current
NAV, it updates the NAV. Setting the NAV is done on a frame-by-frame basis.
? The following types of frames can be transmitted after the SIFS and thus receive
maximum priority: acknowledgments, the CTS in an RTS/CTS exchange sequence,
and fragments in fragment sequences.
? Once a station has transmitted the first frame in a sequence, it has gained control
of the channel. Any additional frames and their acknowledgments can be sent
using the short interframe space, which locks out any other stations.
32
? Additional frames in the sequence update the NAV for the expected additional
time the medium will be used.
? Extended frame sequences are required for higher-level packets that are larger than
configured thresholds.
? Packets larger than the RTS threshold must have RTS/CTS exchange.
? Packets larger than the fragmentation threshold must be fragmented.
4.3 802.11b Fairness Issues
The multi-rate modulation scheme employed by the 802.11b protocol is known to cause
fairness problems within the wireless network as shown in [22]. If all the stations have
uniform traffic to/from the access point (AP), then the low data rate stations will use much
more channel time than the high data rate stations. This has two negative effects: not only
do the low data rate stations get poor service, they also reduce the bandwidth of high data
rate stations. This reduces the effective throughput of the network [23]. Other works like
[24] too have demonstrated that the presence of a few low data rate stations will have an
adverse effect on the overall throughput of the network.
Figure 4.6: Effect of slow nodes in WLAN
33
The negative effect of stations operating at a lower data rate on the average throughput
per node for an 802.11b system is shown in Figure 4.6 obtained from [25]. As can be seen
from the figure, the presence of stations at 1 Mbps reduces the average throughput of all
the stations in the network. This is because a 1 Mbps station takes roughly 11 times more
transmission time than a 11 Mbps station to transmit the same number of bits [25].
In [26], the authors discuss the potential benefit of enabling a bridge like multi-hop
transmission to mitigate the effects of slow stations. One of the goals of the proposed
Synergy MAC protocol is to allow the high rate stations help those stations that can only
sustain a low data rate to mitigate the unfairness effect. The design of Synergy MAC is
described in great detail in Chapter 5
34
Chapter 5
Synergy MAC
The Medium Access Control (MAC) protocol described in this chapter is based on
IEEE 802.11b?s DCF mechanism. Synergy MAC can be described as a cooperative MAC
protocol for infrastructure wireless LANs whose main aim is to combat the ill effects of
channel fading by achieving spatial diversity through cooperation. The protocol also aims
to mitigate 802.11b?s unfairness issue arising from its multi-rate modulation scheme. The
following are some of Synergy MAC?s assumptions:
1. Transmission power for all nodes in the network is fixed.
2. Communication channel between any two nodes in the network is symmetrical.
3. Threshold SNR for each modulation scheme is predefined and stored in a physical
mode table on every node in the network.
4. Transmitting nodes choose their data modulation scheme based on the received signal
to noise ratio (SNR).
5. Control frames like RTS, CTS and ACK are overheard by other nodes besides the
transmitter and the receiver.
The following sections shall now present the underlying details of Synergy MAC protocol.
5.1 The Synergy Table
After associating itself with an access point (AP), a node starts listening for control and
data frames sent out by other nodes on the shared channel. This is required by 802.11b?s
35
DCF mechanism as all nodes in the network need to correctly update their network allo-
cation vector (NAV). In addition to this, Synergy MAC requires each node to maintain a
Synergy Table as shown in Table 5.1 to help determine its ability to volunteer as relay dur-
ing cooperation. Each row in this table has five fields and is similar to the one maintained
by [23]. The first field of this table stores the ID (MAC address) of the source followed by
the Time that the last packet from that node was heard. The third field is used to record
the data rate that can be used to send data packets from the source to the current node and
is denoted by Rsr. The fourth field stores the ID (MAC address) of the destination followed
by Rsd which represents the data rate used between the source and the destination.
Source ID Time Src-Rly Rate Destination ID Src-Dst Rate
Ns Time Rsr Nd Rsd
Table 5.1: Synergy Table
Synergy Table on any node Nr gets updated in the following manner:
When any transmission between other nodes is overheard by the node (Nr), it will
check if the transmitting node (Ns) is already in its Synergy Table. If not, a new row is
added for the sender and is identified by the sender?s ID. Then Nr computes the relative
channel condition between the sender of that packet and itself by measuring the received
power level (in dB). Path loss can be calculated by subtracting the transmission power (in
dB), which is fixed for all nodes and the received power. By checking its physical mode
table, Nr can find the data rate between Ns and itself and use this value to update the rate
Rsr for Ns. If any data packet between source Ns and destination Nd is overheard by Nr,
it will be able to detect the transmission rate used, by looking into the PHY header of the
data frame, which is always transmitted at the base rate of 1 Mbps. This value along with
the destination?s ID is used to update the Rsd field for Ns. The Time field is updated every
time a packet from Ns is overheard by Nr.
36
5.2 The RTS frame
When a source node Ns wants to send L octets of data to destination Nd, it consults
its Synergy Table and calculates the time needed to transmit all the octets using direct
transmission. Following this, node Ns begins to sense the shared channel for any wireless
activity. If the channel is found to be idle for distributed inter-frame space (DIFS) time and
Ns has completed the required backoff procedure, an RTS frame is sent to the destination
Nd, reserving the channel for the time needed for direct transmission. If the channel was
sensed busy, node Ns waits until the channel is idle plus a DIFS interval and then sends its
RTS frame to destination Nd.
Figure 5.1: IEEE 802.11b RTS frame format
Figure 5.1 obtained from [20] shows the IEEE 802.11b RTS control frame format.
According to [7], the More Fragments bit field in 802.11b frame header is set to 0 on
all frames other than those data or management frames that have another fragment of
their current MAC Service Data Unit (MSDU) or MAC Management Protocol Data Unit
(MMPDU) to follow. This means that control frames in 802.11b never get fragmented and
consequently always have their More Fragments bit set to 0.
It is therefore feasible for Synergy MAC to use this bit to distinguish its control frames
from those of standard 802.11b?s. Apart from setting its More Fragments bit to 1, Synergy
MAC requires no other change to the legacy RTS frame format. An alternative strategy for
Synergy MAC would have been to use a different protocol version in the Protocol field of the
RTS control frame header, but doing so could have rendered it incompatible with existing
37
versions of 802.11b implementations. Figure 5.2 shows the exchange of control frames in
Synergy MAC protocol.
Figure 5.2: Synergy MAC Control Frame exchange
5.3 Relay Identification
When an intermediate node Nr, overhears an RTS transmission between source Ns
and destination Nd, it estimates the length of the subsequent data frame based on the
transmission duration obtained from the Duration field of the overheard frame and the
rate of data transmission Rsd, between nodes Ns and Nd obtained from its Synergy Table.
Next, Nr computes the time required to transmit the same data frame over two hops with
itself acting as the relay. If the data frame is L octets long, the transmission time via Nr
ignoring overhead and the contention time is 8L/Rsr + 8L/Rrd where, Rsr is the rate of
data transmission between Ns and Nr and Rrd is the rate of data transmission between Nr
and Nd. Nr obtains both Rsr and Rrd from its Synergy Table. Such two hop transmission
via Nr is efficient only if 8L/Rsr+8L/Rrd < 8L/Rsd. If this is indeed the case, node Nr will
indicate its availability for cooperation by transmitting a self addressed CTS frame with
Duration set to 8L/Rsr +8L/Rrd after short inter-frame space (SIFS) time. Like with the
overheard RTS, node Nr sets the More Fragments bit to 1 in its CTS-to-self frame header.
To resolve potential collisions between many candidate relay nodes, the CTS-to-self frame
38
from all eligible intermediate nodes are governed by a contention window. The contention
window size used by candidate relays for transmitting their self addressed CTS frame is
small when compared to that used by source nodes for transmitting their data frames.
Moreover, candidate relays shall always choose their random slot time within [1, CWr] for
transmitting their self addressed CTS frames. The candidate that picks the lowest slot
in the window wins while the remaining candidate relays update their NAV based on the
Duration contained in the winning CTS-to-self frame. In an infrastructure basic service set
(BSS), the value of CWr can be announced by the AP in its beacon while in an ad hoc
network, the nodes choose CWr = CWmin.
Though the candidate nodes could have used any new frame format to announce their
availability, using a self addressed CTS frame to accomplish this task has its benefits. Not
only is the CTS-to-self frame compatible with 802.11b standard as mentioned in [?], it also
serves the purpose of reserving the medium for the duration of cooperation. In addition
to this, a CTS-to-self frame lets the source and the destination nodes know the identity of
the assisting relay Nr. Figure 5.3 obtained from [20], shows the IEEE 802.11b CTS control
frame format used for CTS-to-self frames.
Figure 5.3: IEEE 802.11b CTS frame format
5.4 The CTS Frame
After receiving the initial RTS frame from source, the destination waits to overhear the
CTS-to-self frame (CTSr) transmitted by the winning relay. If the CTSr from the relay
Nr is overheard by the destination Nd, it sends out a CTS frame (CTSd) to source Ns after
39
SIFS time, reserving the channel for the time needed to complete a two hop transmission
via Nr. If a CTSr is not overheard within a period of CTSRelayTimeout, Nd still sends out a
CTSd frame to source, but this time reserving the channel for the time needed to complete
a direct transmission. In case of the former, Synergy MAC sets the More Fragments bit in
the CTSd frame header to 1, requesting the source to use relay assisted transmission for
its subsequent data frame. As the latter case is similar to that of legacy 802.11b, the More
Fragments bit in the response header remains set to 0.
In situations where the destination is a legacy 802.11 device, a CTS response to a
Synergy MAC RTS, is sent immediately after SIFS time. This is exactly the reason why
the contention window for candidate relays is always in the interval [1, CWr] and not in
[0, CWr]. Any random slot in [1, CWr] ensures that all contending relays overhear the
legacy device?s response and update their NAV, behaving as if the destination had picked
the lowest slot in the relay contention window. This results in 802.11b mode of operation
for Synergy MAC. Thus Synergy MAC ensures that it is interoperable with legacy 802.11b
devices without incurring any penalty.
5.5 Cooperative Communication
Once node Ns receives a CTSd frame from destination Nd, it starts transmitting its
data frame after SIFS time with the Duration field set to CTSd?s estimate duration. If
CTSd?s More Fragments bit was set to 1, Ns sends the data frame to Nr using rate Rsr.
Node Nr then checks the CRC field of the received data frame and if correct, forwards the
frame to Nd, using rate Rrd after SIFS time. If CTSd?s More Fragments bit was set to 0,
Ns sends the data frame directly to Nd using rate Rsd.
It is possible that node Ns does not overhear a CTSr from the winning relay before
receiving a CTSd from Nd with its More Fragments bit set to 1. This might occur due
to drastic change in channel condition between Ns and Nr during CTSr frame exchange.
But because Nd had overheard a CTSr from relay, its Duration estimate in CTSd would
be far less than the Duration contained in the initial RTS frame. If this is the case, source
40
Ns resorts to fragmenting its data frame, based on CTSd?s Duration and its direct data
transmission rate Rsd in order to maintain consistency of the NAV.
After receiving the data frame, destination Nd responds back to Ns with an ACK
frame indicating a successful reception. Otherwise Nd stays idle in which case Ns notices
the failure of transmission after a timeout period and starts backing off exponentially, which
is the same as in the standard IEEE 802.11b MAC.
5.6 NAV Update Mechanism
According to [7], all nodes receiving a valid frame except the one whose MAC address is
equal to the RA (Receiver Address) mentioned in the frame header, are required to update
their NAV with the information received in the frame?s Duration field. When compared to
[7], Synergy MAC differs slightly in the way its NAV is calculated. The Duration carried in a
Synergy MAC RTS header is the time in microseconds required to transmit the pending data
frame using direct transmission from source Ns to destination Nd, plus a relay timeout1,
plus one CTS frame, one ACK frame, and three interleaving SIFS intervals as given in
equation 5.1.
DurationRTS = 3TSIFS +CTSRelayTimeout +TCTS +8L/Rsd +TACK (5.1)
This ensures that even if there is no intermediate node to volunteer, the data frame
can be sent to the destination by direct transmission using rate Rsd. The Duration field in
subsequent CTSr will be set according to equation 5.2 given below. As depicted in Figure
5.4, this duration reflects the time in microseconds required to transmit the pending data
frame using node Nr as relay, plus one CTS frame, one ACK frame and four interleaving
SIFS intervals.
DurationCTSr = 4TSIFS +TCTS +8L/Rsr +8L/Rrd +TACK (5.2)
1Synergy MAC needs to consider a relay timeout for its RTS Duration in order to account for situations
where a suitable relay was either not found or not identified.
41
The Duration in the CTSd frame header is calculated based on whether or not the
destination overheard a CTSr from the winning relay. If the destination overheard a CTSr,
the value of the Duration via Nr is computed as shown in equation 5.3. This value represents
the time in microseconds required to transmit the pending data frame using node Nr as
relay, plus an ACK frame and three interleaving SIFS intervals as depicted in Figure 5.4.
DurationCTSd = 3TSIFS +8L/Rsr +8L/Rrd +TACK (5.3)
In cases where the destination does not overhear a CTSr, the Duration in the CTSd
frame header is given by equation 5.4 which represents the time required to directly transmit
the pending data frame from source Ns to destination Nd using transmission rate Rsd, plus
an ACK frame and two interleaving SIFS intervals as shown in Figure 4.4.
DurationCTSd = 2TSIFS +8L/Rsd +TACK (5.4)
Finally, the value of CTSRelayTimeout can be computed according to equation 5.5. This
value reflects the length of contention window in microseconds plus the time required to
transmit a CTSr from the winning relay.
CTSRelayTimeout = CWr ?SlotTime802.11b +TCTS (5.5)
Figure 5.4 illustrates the NAV update mechanism in Synergy MAC. Nodes that can
overhear both RTS and CTSd frames (e.g. N1) need to set their NAV duration according
to the RTS frame first. Once the CTSr or CTSd frame is overheard, they need to reset the
NAV according to the duration contained in the new frame. Hidden terminals that can only
overhear Nd?s transmissions (e.g. N2) need to update their NAV on overhearing a CTSd.
Terminals that can only overhear Ns?s transmissions set their NAV according to the initial
RTS frame and update it when the subsequent Data frame is overheard.
42
Figure 5.4: NAV update mechanism in Synergy MAC
The flow charts for nodes Ns (source), Nr (relay) and Nd (destination) are depicted in
Figure 5.5, 5.6 and 5.7 respectively.
5.7 Comparing Cooperative MACs
Cooperation among nodes is a relatively new area of research in improving the perfor-
mance of wireless networks. However, we are aware of other 802.11b based cooperative MAC
protocols that have been proposed earlier. This section contrasts Synergy MAC against such
protocols. In UTD MAC [27], the data frame transmitted by source is simultaneously made
available at both the relay and the destination. It is only when the destination fails in
its reception attempt that the relay intervenes to re-send the data frame after RIFS dura-
tion. Because the Duration in RTS and CTS remains unaltered, the protocol can lead to
inconsistency in NAV propagation resulting in collisions. For example, nodes that can only
overhear source node?s transmissions would have a NAV value which does not account for
the subsequent transmission by the relay.
Though Coop MAC I [23] employs similar techniques as Synergy MAC, it requires
considerable changes in the frame formats of 802.11 rendering it incompatible with legacy
implementations. For example, Coop MAC I requires addition of at least three new fields
43
Figure 5.5: Flow chart at source node Ns
44
Figure 5.6: Flow chart at relay node Nr
45
Figure 5.7: Flow chart at destination node Nd
46
Characteristic Coop
MAC I
Coop
MAC II
UTD
MAC
Synergy
MAC
IEEE 802.11b based check check check check
Backward compatible with legacy 802.11 X check check check
Employs three-way handshake check X X check
Relay node identified on the fly X X X check
Avoids collisions during cooperation check X X check
Handles multi-rate fairness check check X check
Table 5.2: Comparison of Different Cooperative MAC Protocols
to the legacy 802.11b RTS frame header. The protocol also requires the relay node to
transmit a new frame called ?HTS? to indicate its willingness to assist the source node
during cooperation. Coop MAC II [23] on the other hand does not require any such changes
to the 802.11b frame formats but because it employs only a 2-way handshake, it can lead
to collisions at the relay node. Also both Coop MAC I and II identify their relay nodes
beforehand at source and are vulnerable to change in its availability caused due to node
mobility. The complete list of differences between these cooperative MAC schemes is given
in Table 5.2.
5.8 Summary
In summary, Synergy MAC implements multi-hop extension proposed in [26] by allow-
ing nodes with low SNR to their destination make use of intermediate relays, to transmit
data at rates higher than otherwise possible. The protocol is also able to achieve spatial
diversity by ensuring that the destination overhears multiple copies of the original frame
(initial source-relay and later relay-destination transmissions).
47
Chapter 6
Simulations and Results
In this chapter, we describe our efforts to validate the performance of the proposed
cooperative MAC protocol. Our verification strategy mainly relies on a detailed simula-
tion study of the proposed protocol using ns-2 network simulator. Towards this end, ns-2?s
existing IEEE 802.11b source code was modified to implement Synergy MAC. This im-
plementation was validated against the expected behavior of Synergy MAC by manually
inspecting the log messages generated by ns-2. Other details regarding the experiments
involved in this study are as explained below.
Figure 6.1: Transmission ranges for different data rates of IEEE 802.11b
All nodes in the experiments choose their modulation scheme based on the received
SNR such that BER ? 10?5. From Figure 4.2, this translates to data rates of 11 Mbps if
48
the node?s distance from AP < 48m, 5.5 Mbps if the distance from AP ? 48m but < 67m,
2 Mbps if the distance from AP ? 67m but < 74m and 1 Mbps if the distance from AP ?
74m but < 100m. Nodes located farther than 100m from the AP are considered to be out
of communication range. 802.11b?s data rates and the corresponding transmission ranges
are depicted in Figure 6.1.
We begin our first experiment with a basic setup of three nodes ? one source, one
destination and one relay as shown in Figure 6.2. The idea behind using such a basic setup
is to accurately gauge the improvement in performance achieved by Synergy MAC protocol.
The experiment has two parts to it. In the first part, the relay node is idle, i.e., it does
not contribute to the traffic on the medium. We call this case the idle relay scenario. This
scenario ensures that the source node does not have to contend with any other node to
access the wireless medium. In the second part of the experiment, the relay node has some
data that needs to be transferred to the destination. We call this case the active relay
scenario. Here both, the source and the relay nodes contend with each other to gain access
to medium.
Figure 6.2: Basic setup consisting a source, a relay and a destination
In both the experiments, the source and the relay nodes are positioned in various data
rate zones, as depicted in Figure 6.1, to achieve all possible data rate combinations (Rsr
and Rrd) during cooperation. The same is then repeated with 802.11b to get a measure of
the baseline performance. In all the trials, the source node transfers data to the destination
via cbr traffic. At source, the data packets are all 1000 octets in length and arrive at a rate
49
of 500 packets per second to keep the network heavily loaded. When active, the relay too
has the same incoming traffic pattern.
The results for idle and active scenarios shown in Figure 6.3 and 6.4 respectively. In
these figures the x-axis lists the coordinates for all the nodes involved in the trials. Distance
from the destination is then used to compute the node?s data rate. The y-axis in the graphs
indicates the end-to-end throughput achieved by averaging all trials. Throughput was
calculated by dividing the amount of data transferred in each frame by its corresponding
transfer time. From the graphs it is clear that Synergy MAC is able to achieve better
performance when compared to 802.11b. This is mainly because with the help of the relay
node, a source with low SNR to destination is able to achieve much better transmission
rates than otherwise possible. With improved data rates, more data is transferred to the
destination which effectively improves the throughput achieved.
The next experimental scenario consists of a single access point (AP) servicing multiple
end nodes in an infrastructure BSS. The end nodes are all randomly distributed in a circular
area of radius 100 meters with the AP located right at the center of the circle. At each
node, data packets of length 1000 octets arrive at a rate of 500 packets per second to keep
the network heavily loaded. The experiment sets the minimum contention window size
(CWmin) to 31 slots and uses a maximum of 6 backoff stages during retransmission.
Figure 6.5 shows the saturated throughput achieved by both 802.11b and Synergy MAC
protocols. Each data point in the graph represents an average of 20 simulation runs. From
the graph it is clear that the aggregate throughput achieved by both protocols is much
less than 11 Mbps. This is because not all randomly distributed nodes are located within
48m of the AP to be able to use transmission rates of 11 Mbps. Collisions and protocol
overheads further reduce the achievable throughput. When compared to 802.11b however,
Synergy MAC is able to achieve much higher throughput. This is because Synergy MAC
allows nodes with low data rates to the AP utilize intermediate nodes as relays to achieve
higher transmission rates. By doing so, the protocol also minimizes the effects of fading
through spatial diversity.
50
Figure 6.3: Synergy MAC vs. IEEE 802.11b with zero traffic at relay
51
Figure 6.4: Synergy MAC vs. IEEE 802.11b with traffic at relay
52
Figure 6.5: Throughput vs. Number of nodes in the network
Figure 6.5 also reveals that the throughput for 802.11b decreases with increase in the
number of nodes on the network. This is mainly due to excessive collisions occurring on the
shared channel. In case of Synergy MAC however, with more nodes in the network, there
is a higher possibility for a node with low data rate to find an intermediate relay. This
increased availability of relays not only offsets the degradation in performance caused by
packet collisions but also leads to an increase in the overall throughput achieved by Synergy
MAC. The relative gain in the throughput of Synergy MAC expressed as percentage versus
number of nodes in the network is shown in Figure 6.6.
Our last experimental scenario tests the robustness of Synergy MAC in face of node
mobility. Node mobility in network simulators are typically realized in two ways; by either
using network traces or by using mathematical mobility models. To analyze the performance
of Synergy MAC protocol in mobile environments, we employ the latter in our simulation
study. Random Mobility Models [28] are widely used to model mobile networks in which
some of the parameters responsible for mobility are indeterministic. Some of these param-
eters may be node attributes such as speed, direction, etc [29]. In our simulation study, we
53
use two such random mobility models namely the Random Waypoint Model and the Ran-
dom Walk model (Brownian motion). These are by far, the most commonly used mobility
models in simulations involving non-static participants.
Random Waypoint mobility model [29] is the most frequently used mobility model
in wireless network simulations. According to this model, nodes move independently to
a randomly chosen destination with a randomly selected velocity. The destination, speed
and direction are all chosen randomly and independently of other nodes. The simplicity of
Random Waypoint model is the main reason for its widespread use in simulations [30].
Figure 6.6: Throughput Gain(%) vs. Number of nodes in the network
However, Random Waypoint has been shown to have some inherent deficiencies such
as speed decay and non-stationarity [31]. Stationarity means that the model?s statistical
properties remain constant at all times during simulation. The most important among them
is the average speed of the nodes which has been shown to decrease consistently. In fact,
over a large interval of time, speed decay will cause node velocity to become zero. With
increasing simulation time, the speed of the nodes will have an exponential distribution [32]
[33]. Hence what started off as a uniform distribution is changing with time and hence does
not satisfy the condition of stationarity. Also, it suffers from border effect which means that
nodes pass through the center of the simulation area with a greater probability than any
54
other area. However, it is widely used since the decaying effects are only observed during
long simulations.
The Random Walk model [34] has similarities with the Random Waypoint model be-
cause the node movement has strong randomness in both models. However, in the Random
Walk model, the nodes change their speed and direction at each time interval. For every
new simulation interval, t, each node randomly and uniformly chooses its new direction ?.
Similarly, the new speed follows a uniform distribution or a Gaussian distribution. If the
node moves according to the above rules and reaches the boundary of the simulation area,
the exiting node is bounced back to the simulation field with the angle of pi?? respectively.
This effect is called border effect. However, in our simulations, we have used Random Walk
model with a wrap around effect which causes boundary exiting nodes to wrap around i.e.,
re-appear at the opposite boundary.
The experimental setup consists of a single access point (AP) servicing variable number
of end nodes in an infrastructure BSS. The AP is located right at the center of a rectangular
area of dimensions 250m X 250m. All client nodes are mobile and are randomly uniformly
distributed in this area. Nodes in the network move according to Random Waypoint or
Random Walk mobility models in the grid. Random Walk mobility model was simulated
using [35]. All nodes travel at speeds of 5 meters/second with a pause time of 1 second.
At each node, data packets of length 1000 octets arrive at a rate of 500 packets per second
to keep the network heavily loaded. The experiment sets the minimum contention window
size (CWmin) to 31 slots and uses a maximum of 6 back off stages during retransmission.
Nodes select their data rates based on the received SNR as described above.
Figure 6.7 shows the the saturated throughput achieved by both 802.11b and Synergy
MAC protocols for different mobility models. Data points in the graph represents the aver-
age throughput derived from 20 simulation runs for varying number of nodes in the network.
From the graph it is clear that Synergy MAC is able to achieve much higher throughput
than 802.11b despite node mobility. Part of the reason behind such impressive performance
lies in the design of Synergy MAC, which enables the relay to be identified dynamically.
55
Figure 6.7: Throughput vs. Number of mobile nodes in the network
This design feature, allows the source node to solicit help from its ever changing neighbor
set with little or no overhead costs. And because the source is able to solicit such help from
its neighbors for every frame it transmits, it is able to reap the benefits of cooperation even
when nodes in the network are mobile [36]. The relative gain in the throughput of Synergy
MAC expressed as percentage versus number of mobile nodes in the network is shown in
Figure 6.8.
Figure 6.8: Throughput Gain(%) vs. Number of mobile nodes in the network
56
Chapter 7
Conclusion
In this work, we first looked at fading and its ill effects on radio communication.
We then saw how diversity can help reduce the errors induced by fading via effectively
transmitting or processing multiple (semi)independently fading copies of the original signal.
We also discussed the concept of cooperative diversity, where nodes within the transmission
range of source act as virtual antennas and retransmit the overheard signal to destination
to achieve spatial diversity.
We then explored cooperation at the medium access control (MAC) layer and pro-
posed a new 802.11b compatible, cooperative MAC protocol called Synergy MAC. With
the proposed protocol, low data rate nodes transmit their packet first to an intermediate
node which in turn forwards the packet to the destination at rates higher than otherwise
possible. By ensuring that the destination overhears multiple copies of the original frame
(initial source-relay and later relay-destination transmissions) the protocol is able to achieve
spatial diversity. Also, by implementing the multi-hop transmission scheme suggested in
[26], the protocol is able to minimize 802.11b?s unfairness issue resulting from its multi-rate
modulation scheme. As verified by extensive simulations, Synergy MAC is able to achieve
substantial throughput improvements in comparison to 802.11b, without incurring signif-
icant overhead in system design. In fact the protocol?s decreased sensitivity to channel
variation is an advantage that warrants nodal cooperation even if there are no benefits
of increased data rates. This is because some minimum data rate requiring real-time ap-
plications such as voice or video are better served by an improved QoS resulting from
cooperation. Moreover for a given network throughput, Synergy MAC can reduce the inter-
ference experienced in proximal cells and thus can provide a more uniform coverage under
57
dense deployment. Simulations also demonstrate that the proposed protocol?s performance
is resilient to node mobility.
Since the relay node simply forwards the source?s data frame without looking into the
contents of the MSDU, the confidentiality of the MSDU can be maintained by encrypting
the content. Access fairness is not compromised in the new MAC, since the relaying node
is allowed to access the network without utilizing its own transmission opportunities.
Also, Synergy MAC can be readily extended to other higher data rate extensions of
802.11, even though the current implementation is evaluated against IEEE?s 802.11b only.
58
Chapter 8
Future Work
Following up on the results presented in this work, a number of additional research
problems can be suggested. For example, in our study, we only consider infrastructure
basic service sets. Although one can conjecture a similar result for single flows in ad hoc
networks, the outcome needs to be demonstrated. Another interesting point that needs
to be investigated in an environment of dense ad-hoc nodes is, whether spatial reuse via
cooperation is beneficial or harmful. The issue is not straightforward as explained in the
following example.
Figure 8.1: Spatial reuse in Synergy MAC
Consider an ad-hoc network deployment as depicted in Figure 8.1. When 802.11b is
used for medium access control, the nodes that remain silent during an ongoing communi-
cation between Ns and Nd are N3, Nr and N4. On the other hand when Synergy MAC is
59
used, the CTSr frame also forces nodes N1 and N2 to defer their transmissions so as to not
collide with the ongoing communication. The impact of silencing communication beyond
immediate neighbors at the relay remains to be investigated.
Similarly other issues like identifying the right relay, rewarding an idle relay, estimating
energy overhead at a relay, handling too many candidate relays as well as achieving com-
munication integrity and confidentiality during cooperation are still wide open and remain
to be addressed.
60
Bibliography
[1] Theodore S. Rappaport, ?Wireless Communications: Principles and Practice,? IEEE
Press, Piscataway, NJ, 1996.
[2] Richard Engelmann, ?The Origins of Radio,? IEEE Potentials, November 2000.
[3] Praphul Chandra, ?Bulletproof Wireless Security: GSM, UMTS, 802.11, and Ad Hoc
Security (Communications Engineering),? Newnes, 2005.
[4] Andrea Goldsmith, ?Wireless Communications,? Cambridge University Press, 2005.
[5] Sheila Frankel, Bernard Eydt, Les Owens, and Karen Scarfone, ?Establishing wireless
robust security networks: a guide to IEEE 802.11i,? National Institute of Standards
and Technology, 2007.
[6] IEEE Computer Society, ?IEEE Std. 802.11-1999 Part 11: Wireless LAN Medium
Access Control (MAC) and Physical Layer (PHY) Specifications,? IEEE Press, Piscat-
away, NJ, 1999.
[7] IEEE Computer Society, ?IEEE Std. 802.11b-1999 Supplement to Part 11: Wireless
LANMedium AccessControl (MAC) and PhysicalLayer (PHY)Specifications: Higher-
speed Physical Layer Extension in the 2.4 GHz Band,? IEEE Press, Piscataway, NJ,
1999.
[8] William Stallings, ?Wireless Communication and Networks,? Pearson Prentice Hall,
NJ, 2005.
[9] Andrew Sendonaris, Elza Erkip and Behnaam Aazhang, ?User cooperation diversity-
Part I: System Description,? IEEE Trans. Commun., vol. 51, no. 11, pp. 1927-1938,
Nov. 2003.
[10] Andrew Sendonaris, Elza Erkip and Behnaam Aazhang, ?User cooperation diversity-
Part II: Implementation aspects and performance analysis,? IEEE Trans. Commun.,
vol. 51, no. 11, pp. 1939-1948, Nov. 2003.
[11] J. Nicholas Laneman, David N. C. Tse, and Gregory W. Wornell, ?Cooperative Di-
versity in Wireless Networks: Efficient Protocols and Outage Behavior,? IEEE Trans.
Inform. Theory, vol. 50, no. 12, pp. 3062-3080, Dec. 2004.
[12] Matthew C. Valenti and Neiyer Correal, ?Exploiting Macrodiversity in Dense Multihop
NetworksandRelaychannels,? inProc.IEEEWirelessCommun. andNetworkingConf.
(WCNC), vol. 3, Mar. 2003, pp. 1877-1882.
61
[13] Ingmar Hammerstroem, Marc Kuhn, Boris Rankov, and Armin Wittneben, ?Space-
Time Processing for Cooperative Relay Networks,? in Proc. of IEEE Vehicular Tech-
nology Conf. (VTC), Oct. 2003.
[14] Elza Erkip, Andrew Sendonaris, Andrej Stefanov and Behnaam Aazhang, ?Cooperative
Communication in Wireless Systems,? Advances in Network Information Theory, AMS
DIMACS Series, 2004.
[15] Thomas M. Cover and Abbas El Gamal, ?Capacity Theorems for the Relay Channel,?
IEEE Trans. Info. Theory, vol. IT-25, Sept. 1979, pp. 57284.
[16] Andrej Stefanov and Elza Erkip, ?Cooperative Coding for Wireless Networks,? IEEE
Trans. Commun., vol. 52, Sept. 2004, pp. 147076.
[17] Todd E. Hunter and Aria Nosratinia, ?Diversity through Coded Cooperation,? IEEE
Trans. Wireless Commun., vol. 5, Feb. 2006, pp. 28389.
[18] J. Nicholas Laneman and Gregory W. Wornell, ?Distributed Space-Time Coded Pro-
tocols for Exploiting Cooperative Diversity in Wireless Networks,? IEEE Trans. Info.
Theory, vol. 49, Oct. 2003, pp. 2415-25.
[19] Pei Liu, Zhifeng Tao, Zinan Lin, Elza Erkip and Shivendra Panwar, ?Cooperative Wire-
less Communications: A Cross-Layer Approach,? in IEEE Wireless Communications,
vol. 13, Aug. 2006, pp. 84-92.
[20] Matthew Gast, ?802.11 Wireless Networks: The Definitive Guide,? O?Reilly Media,
2005.
[21] Javier Delprado and Sunghyun Choi, ?Link Adaptation Strategy for IEEE 802.11
WLAN via Received Signal Strength Measurement,? In Proc. IEEE ICC?03, Vol.2,
pp.1108-1113, May 2003.
[22] Martin Heusse, Franck Rousseau, Gilles Berger-Sabbatel and Andrzej Duda, ?Perfor-
mance anomaly of 802.11b,? in Proc. of IEEE INFOCOM, March 2003.
[23] Pei Liu, Zhifeng Tao and Shivendra S. Panwar, ?A Co-operative MAC Protocol for
Wireless Local Area Networks,? in Proc. IEEE Int Conf. on Communications (ICC),
Seol, Korea, May 2005, pp. 2962-2968.
[24] B. Sadeghi, V. Kanodia, A. Sabharwal, and E. Knightly, ?Opportunistic Media Access
for Multirate Ad Hoc Networks,? in Proc. ACM MobiCom?02, Sept. 2002.
[25] Pei Liu, Zhifeng Tao, Sathya Narayanan, Thanasis Korakis, and Shivendra S. Panwar,
?CoopMAC: A Cooperative MAC for Wireless LANs,? IEEE Journal on Selected Areas
in Communications, vol. 25, no. 2, Feb. 2007
[26] Sathya Narayanan, Pei Liu, and Shivendra S. Panwar, ?On the advantages of multi-hop
extensions to IEEE 802.11 infrastructure mode,? in Proc. IEEE Wireless Commun. and
Networking Conf. (WCNC), New Orleans, USA, March 2005.
62
[27] Niraj Agarwal, Divya ChanneGowda, Lakshmi Narasimhan Kannan, Marco Tacca and
Andrea Fumagalli, ?IEEE 802.11b Cooperative Protocols: A Performance Study,? in
IFIP/TC6 NETWORKING 2007, Atlanta, March 2003, pp. 415-426.
[28] T. Camp, J. Boleng and V. Davies, ?A Survey of Mobility Models for Ad Hoc Network
Research,? in Wireless Communications and Mobile Computing, volume 2, 2002.
[29] David B. Johnson and David A. Maltz, ?Dynamic Source Routing in Ad Hoc Wireless
Networks,? Mobile Computing, Kluwer Academic Publishers, 1996.
[30] C. Bettstetter and H. Hartenstein and X. Perez-Costa, ?Stochastic Properties of the
Random Waypoint Mobility Model,? in ACM/Kluwer Wireless Networks, Special Issue
on Modeling and Analysis of Mobile Networks, 2004. pp. 181-190.
[31] J. Yoon, M. Liu and B. Noble, ?Random Waypoint Considered Harmful,? in Proceed-
ings of INFOCOM, 2003.
[32] T. Chu and I. Nikolaidis, ?On the artifacts of random waypoint simulations,? Proceed-
ings of the 1st International Workshop on Wired/Wireless Internet Communications
(WWIC2002), 2002.
[33] A. Jardosh, E. M. Belding-Royer, K. C. Almeroth and S. Suri, ?Towards Realistic
Mobility Models for Mobile Ad Hoc Networks,? in ACM Mobicom, 2003.
[34] Michael McGuire, ?Stationary distributions of random walk mobility models for wire-
less ad hoc networks,? in Mobile ad hoc networking and computing, 2005.
[35] S. PalChaudhuri, J. Y. L. Boudec, and M. Vojnovic, ?Perfect simulations for random
trip mobility models,? at 38th Annual Simulation Symposium, San Diego, CA, 2005.
[36] Santosh Kulkarni, Pratap Prasad and Prathima Agrawal, ?Performance Enhancement
of Mobile Ad Hoc Networks Using Nodal Cooperation,? in Proceedings of 4th Interna-
tional Wireless Internet Conference (WICON), Maui, Nov. 2008.
63