Medium Access Control (MAC)

Protocols for Ad hoc Wireless

Networks - I

CS: 647
Advanced Topics in Wireless Networks
Drs. Baruch Awerbuch & Amitabh Mishra
Department of Computer Science
Johns Hopkins University
Amitabh Mishra & Baruch Awerbuch 2008

2-1

Reading
C. K. Toh, Ad Hoc Mobile Wireless

Networks, Chapter 4 Ad Hoc Wireless

Media Protocols, Prentice Hall
Bob OHara and Al Petrick, IEEE 802.11
Handbook: A Designers Companion, IEEE
Press, 1999.
Jochen Schiller, Mobile Communications,
Section 7.3, Addison-Wesley, 2000.

2-2

Further Readings
Lots of MAC protocols published in Mobicom,
Infocom, Globecom, ICC, Mobihoc, WCNC, VTC,
etc.
CSMA: L. Kleinrock and F. A. Tobagi, Packet
Switching in Radio Channels: Part I Carrier Sense
Multiple Access Modes and Their ThroughputDelay Characteristics, IEEE Trans. On
Communications, Vol. COM-23, No. 12, Dec. 1975,
pp. 1400-1416
MACA: P. Karn, MACA A New Channel Access
Protocol for Packet Radio, ARRL/CRRL Amateur
Radio 9th Computer Networking Conference, 1990,
pp. 134-140.

2-3

Further Readings
FAMA: C. L. Fullmer and J. J. Garcia-Luna_Aceves,
Floor Acquisition Multiple Acsess (FAMA) for
Packet-Radio Networks, Proceedings of ACM
Sigcomm95, Cambridge, MA, Aug. 1995, pp. 262273.
MACAW: V. Bharghavan, A. Demers, S. Shenker,
and L. Zhang, MACAW: A Media Access Protocol
for Wireless LANs, Proceedings of ACM
Sigcomm94, London, UK, Sept. 1994, pp. 212-225.
IEEE Computer Society LAN/MAN Standards
Committee, Wireless LAN Medium Access
Protocol (MAC) and Physical Layer (PHY)
Specifications, IEEE Std. 802.11

2-4

Outline
Wireless MAC Issues

Hidden terminal problem

Exposed terminal problem
Capture

MAC Performance Metrics

Wireless MAC Classification

Distributed Wireless MAC Protocols

Aloha
Slotted Aloha
CSMA
CSMA/CA
802.11 MAC
DCF
Backoff

Hiper Lan MAC

2-5

Introduction

Multiple access control channels

Each Mobile Station (MS) is attached to a transmitter /

receiver which communicates via a channel shared by
other nodes
Transmission from any MS is received by other MSs in
the neighborhood
MS 3

MS 2

MS 1

Shared Multiple
Access Medium

MS 4

Node N
2-6

Introduction (Contd)
Multiple access issues
Wireless Channel (Wireless medium) is shared
among multiple neighboring nodes

If more than one MS transmit at a time on the shared

media, a collision occurs
How to determine which MS can transmit?
MS 3

MS 2

MS 1

Shared Multiple
Access Medium

MS 4

Node N

2-7

Wireless Medium Access Control Why?

Access Control protocols define rules for orderly

access to the shared medium

Need to avoid packet collisions at the receiver due

to interference

Fairness in sharing
Efficient sharing of bandwidth

Different types:
Contention protocols resolve a collision after it occurs or
try to avoid it. These protocols execute a collision
resolution protocol after each collision
Conflict-free protocols (e.g., TDMA, FDMA, CDMA) ensure
that a collision can never occur.

Mobility
Energy Constraints
Wireless MACs have been studied heavily since
1970s
2-8

Channel Sharing Techniques

Static
Channelization

Medium Sharing
Techniques

Scheduling
Dynamic
Medium Access
Control

Random
Access

2-9

Classification of Wireless MAC

Protocols
Wireless MAC Protocols

Distributed

Random Access

Centralized

Random Access

Guaranteed Access

Hybrid Access

RRA

Demand Assignment

2-10

Wireless MAC Issues (1)

Wireless medium makes the MAC design

more challenging than the wireline

networks.
The three important issues are:
1.
2.
3.

Half Duplex operation > Either send or

receive but not both at a given time
Time varying channel
Burst channel errors

2-11

Wireless MAC Issues (2)

1. Half Duplex Operation

In wireless, Its difficult to receive data when

the transmitter is sending the data, because:
When node is transmitting, a large fraction of the
signal energy leaks into the receiver path
The transmitted and received power levels can differ
by orders of magnitude
The leakage signal typically has much higher power
than the received signal -> Impossible to detect a
received signal, while transmitting data
Collision detection is not possible, while sending data
CSMA/CD (Ethernet MAC) cannot be used as it is

2-12

Wireless MAC Issues (3)

Half Duplex Operation (Contd.)
As collision cannot be detected by the sender,
all proposed protocols attempt to minimize the
probability of collision -> Focus on collision
avoidance

2-13

Wireless MAC Issues (4)

2. Time Varying Channel

Three mechanisms for radio signal propagation

(T. Rappaports book)
Reflection occurs when a propagating wave
impinges upon an object that has very large
dimensions than the wavelength of the radio wave
e.g. reflection occurs from the surface of the earth
and from buildings and walls
Diffraction occurs when the radio path between
the transmitter and the receiver is obstructed by a
surface with sharp edges
Scattering occurs when the medium through which
the wave travels consists of objects with dimensions
smaller than the wavelength of the wave

2-14

Wireless MAC Issues (5)

2. Time Varying Channel (Contd.)

The received signal by a node is a

superposition of time-shifted and attenuated
versions of the transmitted signals The
received signal varies with time
The time varying signals (time varying channel)
phenomenon also known as multipath
propagation
The rate of variation of channel is determined
by the coherence time of the channel
Coherence time is defined as time within which the
received signal strength changes by 3 dB

2-15

Wireless MAC Issues (6)

2. Time Varying Channel (Contd.)

When a nodes received signal strength drops

below a certain threshold the node is said to
be in fade
Handshaking is widely used strategy to ensure
the link quality is good enough for data
communication
A successful handshake between a sender and
a receiver (small message) indicates a good
communication link

2-16

Wireless MAC Issues (7)

3. Burst Channel Errors

As a consequence of time varying channel and varying

signals strengths errors are introduced in the
transmission (Very likely)
For wireline networks the bit error rate (BER) is typically
i.e. the probability of packet error is small
10 6
For wireline networks the errors are due to random noise
For wireless networks the BER is as high as 10 3
For wireless networks the errors are due to node being in
fade as a result errors occur in a long burst
Packet loss due to burst errors - mitigation techniques

Smaller packets
Forward Error Correcting Codes
Retransmissions (Acks)

2-17

Location Dependent Carrier Sensing

In free space signal decays with the square

of distance

Implication is that the carrier sensing becomes

a function of the position of the receiver
relative to the transmitter
In wireless medium due to multi-path
propagation, the signal strength decays
according to a power law with distance

Only nodes within a specific radius of the

transmitter can detect the carrier on the channel

2-18

Location Dependent Carrier Sensing

Location Dependent Carrier Sensing results in
three types of nodes that protocols need to deal
with:
Hidden Nodes

Exposed Nodes

Even if the medium is free near the transmitter, it may

not be free near the intended receiver
Even if the medium is busy near the transmitter, it may
be free near the intended receiver

Capture

Capture occurs when a receiver can cleanly receive a

transmission from one of two simultaneous transmissions

2-19

Hidden Node/Terminal Problem

A hidden node is one that is within the

range of the intended destination but out

of range of sender
Node B can communicate with A and C both
A and C cannot hear each other
When A transmits to B, C cannot detect
the transmission using the carrier sense
mechanism C falsely thinks that the
channel is idle
If C transmits, collision will occur at node B
A

C
2-20

Hidden Node Problem

Range of Terminal A

Range of Terminal C

Currently Transmitting

C
Wants to Transmit to B

Will collide with Transmission from A at B

2-21

Exposed Nodes
An exposed node is one that is within the range of the sender but
out of range of destination

D
A

2-22

Exposed Nodes
1. Consider the case that node B is attempting to transmit to A

D
A

2. Node C can hear the transmission from B. When B senses

the channel it finds the channel to be busy.
3. However, any transmission by C cannot reach A (not in
range), hence does not interfere with any reception at A.
2-23

Exposed Nodes
4. In theory C can therefore have a parallel transmission with any

D
A

node that cannot hear the transmission from B, i.e. out of

range of B.
5. But C will not transmit to any node because its an exposed
node. Exposed nodes waste bandwidth.
2-24

Exposed Terminal Problem

Range of Terminal B

Range of Terminal C
Wants to Transmit to D

A
Currently
Transmitting

Cannot send to D due to Carrier sense

2-25

Capture
D
A

Capture is said to occur when a receiver can cleanly receive

a transmission from one of two simultaneous transmissions
both within its range

2-26

Capture
D
A

Assume node A and D transmit simultaneously to B. The signal

strength received from D is much higher than that from A, and Ds
transmission can be decoded without errors in presence of
transmissions from A.
D has captured A
Capture is unfair because it gives preference to nodes that are
closer to the receiver
It may improve protocol performance
2-27

Capture - Example

2-28

Outline
Wireless MAC Issues

Hidden terminal problem

Exposed terminal problem
Capture

MAC Performance Metrics

Wireless MAC Classification

Distributed Wireless MAC Protocols

Aloha
Slotted Aloha
CSMA
CSMA/CA
802.11 MAC
DCF
Backoff

Hiper Lan MAC

2-29

MAC Performance Metrics

There are hundreds of MAC protocols

proposed for wireless networks.

We need performance metrics so that we
can compare one protocol from the other
The key metrics are:
Delay
Throughput
Fairness
Stability
Robustness against channel fading
Power Consumption
Support for multimedia

2-30

MAC Performance Metrics

Delay
Defined as the average time spent by a packet
in the MAC queue, i.e. from the instant it is enqueued till its transmission is complete
Sensitive to traffic characteristics, so two
MAC protocols should be compared under
identical traffic conditions
Throughput
Fraction of channel capacity used for data
transmissions
MAC need to maximize throughput while
keeping the access delay to minimum
2-31

MAC Performance Metrics

For a P bits message size, on a channel of capacity
C bits/sec, T seconds are elapsed,
So throughput of the channel is

Fairness

P
=
TC

When all nodes are treated equally, and no node is given

preference
Leads to fair sharing of bandwidth
Traffic with different priorities can bias this definition

For multimedia traffic, usually the MAC is considered

fair when (voice, data, video) get their allocated
bandwidth

2-32

MAC Performance Metrics

Stability
System need to be stable if instantaneously
high load is seen by the MAC

Robustness against channel fading

Wireless channel is time varying and error
prone
Fading may make channel unusable for short
durations
MAC needs to work reliably while channel in
fade

Power Consumption
Wireless nodes have limited battery power ->
MAC should conserve energy
2-33

MAC Performance Metrics

Support for multimedia
MAC should support multimedia applications
(voice, video, data)
Multimedia data implies data with real-time
constraints
By using priorities and scheduling delay can
be controlled and/or guaranteed

2-34