MAC Protocols for Ad-Hoc Wireless

Networks

1
 Introduction
 Multiple access control channels
 Each node is attached to a transmitter/receiver which
communicates via a channel shared by other nodes
 Transmission from any node is received by other nodes

2
 Introduction (Cont’d)
 Multiple access issues
• If more than one node transmit at a time on the control channel
to BS, a collision occurs
• How to determine which node can transmit to BS?
 Multiple access protocols
• Solving multiple access issues
• Different types:
• Contention protocols resolve a collision after it occurs. These
protocols execute a collision resolution protocol after each
collision
• Collision-free protocols (e.g., a bit-map protocol and binary
countdown) ensure that a collision can never occur.

3
 Channel Sharing Techniques

Static
Channelization

Channel Sharing
Techniques
Scheduling

Dynamic Medium
Access Control
Random Access

4
Classification of Multiple Access Protocols

5
 Issues
 The main issues need to be addressed while designing a MAC
protocol for ad hoc wireless networks:
• Bandwidth efficiency is defined at the ratio of the bandwidth used for
actual data transmission to the total available bandwidth. The MAC protocol
for ad-hoc networks should maximize it.
• Quality of service support is essential for time-critical applications. The
MAC protocol for ad-hoc networks should consider the constraint of ad-hoc
networks.
• Synchronization can be achieved by exchange of control packets. [data
integrity]

6
 Issues
 The main issues need to be addressed while designing a MAC
protocol for ad hoc wireless networks:
• Hidden and exposed terminal problems:
• Hidden nodes:
– Hidden stations: Carrier sensing may fail to detect another station.
For example, A and D.
– Fading: The strength of radio signals diminished [become low]
rapidly with the distance from the transmitter. For example, A and C.
• Exposed nodes:
– Exposed stations: B is sending to A. C can detect it. C might want to
send to E but conclude it cannot transmit because C hears B.
– Collision masking: The local signal might drown out the remote
transmission.
• Error-Prone Shared Broadcast Channel
• Distributed Nature/Lack of Central Coordination
• Mobility of Nodes: Nodes are mobile most of the time.
7
 Contention Protocols
 ALOHA
 Developed in the 1970s for a packet radio network by Hawaii University.
 Whenever a station has a data, it transmits. Sender finds out whether
transmission was successful or experienced a collision by listening to the
broadcast[ack] from the destination station. Sender retransmits after some
random time if there is a collision.
 Slotted ALOHA
 Improvement: Time is slotted and a packet can only be transmitted at the
beginning of one slot. Thus, it can reduce the collision duration.

8
 Contention Protocols (Cont’d)
 CSMA (Carrier Sense Multiple Access)
 Improvement: Start transmission only if no transmission is ongoing
 CSMA/CD (CSMA with Collision Detection)
 Improvement: Stop ongoing transmission if a collision is detected
 CSMA/CA (CSMA with Collision Avoidance)
 Improvement: Wait a random time and try again when carrier is quiet. If
still quiet, then transmit
 CSMA/CA with ACK
 CSMA/CA with RTS/CTS

9
ALOHA

10
 Throughput of ALOHA
• The probability that n packets arrive in two packets time is given by
n
(2G) e2G
P n  
n!
where G is traffic load.
• The probability P(0) that a packet is successfully received without
collision is calculated by letting n=0 in the above equation. We get

P  0   e 2 G
• We can calculate throughput S with a traffic load G as follows:

S  G  P 0   G  e 2G

• The Maximum throughput of ALOHA is

1
S max   0.184
2e
11
 Slotted ALOHA

Node 1 Packet

Nodes 2 & 3 Packets

Retransmission Retransmission

1 2&3 2 3
Time

Slot Collision

Collision mechanism in slotted ALOHA

12
 Throughput of Slotted ALOHA

• The probability of no collision is given by

P 0  e G

• The throughput S is

S  G  P 0  G  e G

• The Maximum throughput of slotted ALOHA is

1
S max   0.368
e

13
 Throughput
0.5

0.4

0.3

0.2

0.1

00 2 4 6 8
G

14
 CSMA (Carrier Sense Multiple Access)
 Max throughput achievable by slotted ALOHA is 0.368.
 CSMA gives improved throughput compared to Aloha
protocols.
 Listens to the channel before transmitting a packet
(avoid avoidable collisions).

15
 Collision Mechanism in CSMA

Node 1 Packet
Node 5 sense
Node 2 Packet
Node 3 Packet Delay

1 2 3 4 5
Time
Delay Collision

Node 4 sense

16
 Kinds of CSMA
Unslotted Nonpersistent CSMA
Nonpersistent CSMA
Slotted Nonpersistent CSMA
CSMA
Unslotted persistent CSMA
Persistent CSMA
Slotted persistent CSMA

1-persistent CSMA

p-persistent CSMA

17
Nonpersistent/x-persistent CSMA Protocols
 Nonpersistent CSMA Protocol:
Step 1: If the medium is idle, transmit immediately
Step 2: If the medium is busy, wait a random amount of time and
repeat Step 1
 Random backoff reduces probability of collisions
 Waste idle time if the backoff time is too long

 1-persistent CSMA Protocol:

Step 1: If the medium is idle, transmit immediately
Step 2: If the medium is busy, continue to listen until medium
becomes idle, and then transmit immediately
 There will always be a collision if two nodes want to retransmit
(usually you stop transmission attempts after few tries)

18
Nonpersistent/x-persistent CSMA Protocols

 p-persistent CSMA Protocol:

Step 1: If the medium is idle, transmit with probability p, and delay
for worst case propagation delay for one packet with probability
(1-p)
Step 2: If the medium is busy, continue to listen until medium
becomes idle, then go to Step 1
Step 3: If transmission is delayed by one time slot, continue with Step
1

 A good tradeoff between nonpersistent and 1-persistent CSMA

19
 How to Select Probability p ?

 Assume that N nodes have a packet to send and the

medium is busy
 Then, Np is the expected number of nodes that will
attempt to transmit once the medium becomes idle
 If Np > 1, then a collision is expected to occur

Therefore, network must make sure that Np < 1 to

avoid collision, where N is the maximum number of
nodes that can be active at a time

20
 Throughput

1.0 0.01-persistent CSMA

0.9 Nonpersistent CSMA
0.8
0.7
0.1-persistent CSMA
0.6
0.5-persistent CSMA
0.5
S

1-persistent CSMA
0.4
0.3
Slotted Aloha
0.2
Aloha
0.1
0
0 1 2 3 4 5 6 7 8 9
G

21
 CSMA/CD (CSMA with Collision Detection)

 In CSMA, if 2 terminals begin sending packet at the same

time, each will transmit its complete packet (although
collision is taking place).
 Wasting medium for an entire packet time.
 CSMA/CD
Step 1: If the medium is idle, transmit
Step 2: If the medium is busy, continue to listen until
the channel is idle then transmit
Step 3: If a collision is detected during transmission,
cease transmitting
Step 4: Wait a random amount of time and repeats
the same algorithm
22
 CSMA/CD (Cont’d)
T0 A begins transmission
A B

T0+- B begins transmission

A B

T 0+  B detects collision
A B

T0+2 - A detects collision just

before end of transmission
A B
Time
( is the propagation time)
23
 CSMA/CA (CSMA with collision Avoidance)
 All terminals listen to the same medium as CSMA/CD.
 Terminal ready to transmit senses the medium.
 If medium is busy it waits until the end of current
transmission.
 It again waits for an additional predetermined time period
DIFS (Distributed inter frame Space).
 Then picks up a random number of slots (the initial value of
backoff counter) within a contention window to wait before
transmitting its frame.
 If there are transmissions by other terminals during this time
period (backoff time), the terminal freezes its counter.
 It resumes count down after other terminals finish transmission
+ DIFS. The terminal can start its transmission when the
counter reaches to zero.
24
 CSMA/CA (Cont’d)

Node A’s frame Node B’s frame Node C’s frame

Delay: B
Delay: C Time
Nodes B & C sense
the medium
Nodes C starts
Nodes B resenses the medium transmitting.
and transmits its frame.
Node C freezes its counter.

Nodes C resenses the

medium and starts
decrementing its counter.

25
 CSMA/CA Explained

Contention DIFS Contention window

DIFS window
Medium Busy Next Frame
Time
Defer access Slot

Backoff after defer

DIFS – Distributed Inter Frame Spacing

26
 CSMA/CA with ACK

 Immediate Acknowledgements from receiver

upon reception of data frame without any need for
sensing the medium.
 ACK frame transmitted after time interval SIFS
(Short Inter-Frame Space) (SIFS < DIFS)
 Receiver transmits ACK without sensing the
medium.
 If ACK is lost, retransmission done.

27
 CSMA/CA/ACK

DIFS Time
Data
Source
SIFS
ACK
Destination
DIFS Contention window

Next Frame
Other
Defer access Backoff after defer

SIFS – Short Inter Frame Spacing

28
 CSMA/CA with RTS/CTS

 Transmitter sends an RTS (request to send) after

medium has been idle for time interval more than
DIFS.
 Receiver responds with CTS (clear to send) after
medium has been idle for SIFS.
 Then Data is exchanged.
 RTS/CTS is used for reserving channel for data
transmission so that the collision can only occur in
control message.

29
 CSMA/CA with RTS/CTS (Cont’d)

DIFS SIFS
RTS Data Time
Source
SIFS SIFS

CTS ACK
Destination
DIFS
Contention window

Next Frame
Other

Defer access Backoff after defer

30
 RTS/CTS
Node A Node B

Propagation delay RTS

CTS

Data

ACK

31
The 802.11 MAC Sublayer Protocol

(a) The hidden station problem.

(b) The exposed station problem.
32
 Design goals of a MAC Protocol
 Design goals of a MAC protocol for ad hoc wireless networks
• The operation of the protocol should be distributed.
• The protocol should provide QoS support for real-time traffic.
• The access delay, which refers to the average delay experienced by any
packet to get transmitted, must be kept low.
• The available bandwidth must be utilized efficiently.
• The protocol should ensure fair allocation of bandwidth to nodes.
• Control overhead must be kept as low as possible.
• The protocol should minimize the effects of hidden and exposed terminal
problems.
• The protocol must be scalable to large networks.
• It should have power control mechanisms.
• The protocol should have mechanisms for adaptive data rate control.
• It should try to use directional antennas.
• The protocol should provide synchronization among nodes.
33
 Classifications of MAC protocols
 Ad hoc network MAC protocols can be classified into three types:
• Contention-based protocols
• Contention-based protocols with reservation mechanisms
• Contention-based protocols with scheduling mechanisms
• Other MAC protocols
MAC Protocols for Ad Hoc
Wireless Networks

Contention-based Contention-based Other MAC

Contention-Based
protocols with protocols with Protocols
Protocols
reservation mechanisms scheduling mechanisms
Directional
RI-BTMA
Antennas
Sender-Initiated Receiver-Initiated Synchronous Asynchronous MACA-BI
MMAC
Protocols Protocols Protocols Protocols MARCH
MCSMA
RI-BTMA D-PRMA MACA/PR
PCM
Single-Channel MACA-BI CATA RTMAC
Multichannel RBAR
Protocols Protocols MARCH HRMA
SRMA/PA
MACAW BTMA
FAMA DBTMA FPRP
ICSMA 34
 Classifications of MAC Protocols
 Contention-based protocols
• Sender-initiated protocols: Packet transmissions are initiated by the sender
node.
• Single-channel sender-initiated protocols: A node that wins the
contention to the channel can make use of the entire bandwidth.
• Multichannel sender-initiated protocols: The available bandwidth is
divided into multiple channels.
• Receiver-initiated protocols: The receiver node initiates the contention
resolution protocol.
 Contention-based protocols with reservation mechanisms
• Synchronous protocols: All nodes need to be synchronized. Global time
synchronization is difficult to achieve.
• Asynchronous protocols: These protocols use relative time information for
effecting reservations.

35
 Classifications of MAC Protocols
 Contention-based protocols with scheduling mechanisms
• Node scheduling is done in a manner so that all nodes are treated fairly and
no node is starved of bandwidth.
• Scheduling-based schemes are also used for enforcing priorities among flows
whose packets are queued at nodes.
• Some scheduling schemes also consider battery characteristics.
 Other protocols are those MAC protocols that do not strictly fall
under the above categories.

36
 Contention-based protocols
 MACAW: A Media Access Protocol for Wireless LANs is based
on MACA (Multiple Access Collision Avoidance) Protocol
 MACA
• When a node wants to transmit a data packet, it first transmit a RTS
(Request To Send) frame.
• The receiver node, on receiving the RTS packet, if it is ready to receive the
data packet, transmits a CTS (Clear to Send) packet.
• Once the sender receives the CTS packet without any error, it starts
transmitting the data packet.
• If a packet transmitted by a node is lost, the node uses the binary exponential
back-off (BEB) algorithm to back off a random interval of time before
retrying.
 The binary exponential back-off mechanism used in MACA might
starves flows sometimes. The problem is solved by MACAW.
37
 MACA Protocol

The MACA protocol. (a) A sending an RTS to B.

(b) B responding with a CTS to A.
38
 MACA examples
 MACA avoids the problem of hidden terminals
• A and C want to
send to B
• A sends RTS first
RTS
• C waits after receiving
CTS from B CTS CTS
A B C

 MACA avoids the problem of exposed terminals

• B wants to send to A, C
to another terminal
• now C does not have RTS RTS
to wait for it cannot CTS
receive CTS from A A B C
39
 MACAW
 Variants of this method can be found in IEEE 802.11 as
DFWMAC (Distributed Foundation Wireless MAC),
 MACAW (MACA for Wireless) is a revision of MACA.
• The sender senses the carrier to see and transmits a RTS (Request To
Send) frame if no nearby station transmits a RTS.
• The receiver replies with a CTS (Clear To Send) frame.
• Neighbors
• see CTS, then keep quiet.
• see RTS but not CTS, then keep quiet until the CTS is back to the
sender.
• The receiver sends an ACK when receiving an frame.
• Neighbors keep silent until see ACK.
• Collisions
• There is no collision detection.
• The senders know collision when they don’t receive CTS.
• They each wait for the exponential backoff time. 40
MACA variant: DFWMAC in IEEE802.11

sender receiver

idle idle
packet ready to send; RTS
data;
ACK
RxBusy time-out;
wait for the RTS RTS;
time-out  CTS
ACK right to send data;
time-out 
NAK
NAK;
RTS CTS; data
wait for
wait for ACK data

ACK: positive acknowledgement RxBusy: receiver busy RTS; RxBusy

NAK: negative acknowledgement
41
 Contention-based protocols
 Floor acquisition Multiple Access Protocols (FAMA)
• Based on a channel access discipline which consists of a carrier-sensing
operation and a collision-avoidance dialog between the sender and the
intended receiver of a packet.
• Floor acquisition refers to the process of gaining control of the channel. At
any time only one node is assigned to use the channel.
• Carrier-sensing by the sender, followed by the RTS-CTS control packet
exchange, enables the protocol to perform as efficiently as MACA.
• Two variations of FAMA
• RTS-CTS exchange with no carrier-sensing uses the ALOHA protocol
for transmitting RTS packets.
• RTS-CTS exchange with non-persistent carrier-sensing uses non-
persistent CSMA for the same purpose.

42
 Contention-based protocols
 Busy Tone Multiple Access Protocols (BTMA)
• The transmission channel is split into two:
• a data channel for data packet transmissions
• a control channel used to transmit the busy tone signal
• When a node is ready for transmission, it senses the channel to check
whether the busy tone is active.
• If not, it turns on the busy tone signal and starts data transmissions
• Otherwise, it reschedules the packet for transmission after some random
rescheduling delay.
• Any other node which senses the carrier on the incoming data channel
also transmits the busy tone signal on the control channel, thus, prevent
two neighboring nodes from transmitting at the same time.
 Dual Busy Tone Multiple Access Protocol (DBTMAP) is an
extension of the BTMA scheme.
• a data channel for data packet transmissions
• a control channel used for control packet transmissions (RTS and CTS
packets) and also for transmitting the busy tones. 43
 Contention-based protocols
 Receiver-Initiated Busy Tone Multiple Access Protocol (RI-
BTMA)
• The transmission channel is split into two:
• a data channel for data packet transmissions
• a control channel used for transmitting the busy tone signal
• A node can transmit on the data channel only if it finds the busy tone to be absent
on the control channel.
• The data packet is divided into two portions: a preamble and the actual data packet.
 MACA-By Invitation (MACA-BI) is a receiver-initiated MAC
protocol.
• By eliminating the need for the RTS packet it reduces the number of
control packets used in the MACA protocol which uses the three-way
handshake mechanism.
 Media Access with Reduced Handshake (MARCH) is a receiver-
initiated protocol. 44
 Contention-based Protocols with
Reservation Mechanisms
 Contention-based Protocols with Reservation Mechanisms
• Contention occurs during the resource (bandwidth) reservation phase.
• Once the bandwidth is reserved, the node gets exclusive access to the
reserved bandwidth.
• QoS support can be provided for real-time traffic.
 Distributed packet reservation multiple access protocol (D-
PRMA)
• It extends the centralized packet reservation multiple access (PRMA)
scheme into a distributed scheme that can be used in ad hoc wireless
networks.
• PRMA was designed in a wireless LAN with a base station.
• D-PRMA extends PRMA protocol in a wireless LAN.
• D-PRMA is a TDMA-based scheme. The channel is divided into fixed-
and equal-sized frames along the time axis.
45
 Access method DAMA: Reservation-
TDMA
 Reservation Time Division Multiple Access
• every frame consists of N mini-slots and x data-slots
• every station has its own mini-slot and can reserve up to k data-slots using
this mini-slot (i.e. x = N * k).
• other stations can send data in unused data-slots according to a round-robin
sending scheme (best-effort traffic)

e.g. N=6, k=2

N mini-slots N * k data-slots

reservations other stations can use free data-slots

for data-slots based on a round-robin scheme
46
Distributed Packet Reservation Multiple
Access Protocol (D-PRMA)
 Implicit reservation (PRMA - Packet Reservation Multiple
Access):
• a certain number of slots form a frame, frames are repeated
• stations compete for empty slots according to the slotted aloha principle
• once a station reserves a slot successfully, this slot is automatically
assigned to this station in all following frames as long as the station has
data to send
• competition for this slots starts again as soon as the slot was empty in the
last frame
reservation 1 2 3 4 5 6 7 8 time-slot
ACDABA-F frame1 A C D A B A F
ACDABA-F frame2 A C A B A
AC-ABAF- frame3 A B A F collision at
reservation
A---BAFD frame4 A B A F D attempts
t 47
ACEEBAFD frame5 A C E E B A F D
 Contention-based protocols with
Reservation Mechanisms
 Collision avoidance time allocation protocol (CATA)
• based on dynamic topology-dependent transmission scheduling
• Nodes contend for and reserve time slots by means of a distributed
reservation and handshake mechanism.
• Support broadcast, unicast, and multicast transmissions.
• The operation is based on two basic principles:
• The receiver(s) of a flow must inform the potential source nodes about
the reserved slot on which it is currently receiving packets. The source
node must inform the potential destination node(s) about interferences
in the slot.
• Usage of negative acknowledgements for reservation requests, and
control packet transmissions at the beginning of each slot, for
distributing slot reservation information to senders of broadcast or
multicast sessions. 48
 Contention-based protocols with
Reservation Mechanisms
 Hop reservation multiple access protocol (HRMA)
• a multichannel MAC protocol which is based on half-duplex, very slow
frequency-hopping spread spectrum (FHSS) radios
• uses a reservation and handshake mechanism to enable a pair of
communicating nodes to reserve a frequency hop, thereby guaranteeing
collision-free data transmission.
• can be viewed as a time slot reservation protocol where each time slot is
assigned a separate frequency channel.
 Soft reservation multiple access with priority assignment
(SRMA/PA)
• Developed with the main objective of supporting integrated services of
real-time and non-real-time application in ad hoc networks, at the same
time maximizing the statistical multiplexing gain.
• Nodes use a collision-avoidance handshake mechanism and a soft
reservation mechanism.
49
 Contention-based protocols with
Reservation Mechanisms
 Five-Phase Reservation Protocol (FPRP)
• a single-channel time division multiple access (TDMA)-based broadcast
scheduling protocol.
• Nodes uses a contention mechanism in order to acquire time slots.
• The protocol assumes the availability of global time at all nodes.
• The reservation takes five phases: reservation, collision report, reservation
confirmation, reservation acknowledgement, and packing and elimination
phase.
 MACA with Piggy-Backed Reservation (MACA/PR)
• Provide real-time traffic support in multi-hop wireless networks
• Based on the MACAW protocol with non-persistent CSMA
• The main components of MACA/PR are:
• A MAC protocol
• A reservation protocol
• A QoS routing protocol 50
 Contention-based protocols with
Reservation Mechanisms
 Real-Time Medium Access Control Protocol (RTMAC)
• Provides a bandwidth reservation mechanism for supporting real-time traffic
in ad hoc wireless networks
• RTMAC has two components
• A MAC layer protocol is a real-time extension of the IEEE 802.11 DCF.
– A medium-access protocol for best-effort traffic
– A reservation protocol for real-time traffic
• A QoS routing protocol is responsible for end-to-end reservation and
release of bandwidth resources.

51
 Contention-based protocols with
Scheduling Mechanisms
 Protocols in this category focus on packet scheduling at the nodes
and transmission scheduling of the nodes.
 The factors that affects scheduling decisions
• Delay targets of packets
• Traffic load at nodes
• Battery power
 Distributed priority scheduling and medium access in Ad Hoc
Networks present two mechanisms for providing quality of service
(QoS)
• Distributed priority scheduling (DPS) – piggy-backs the priority tag of a
node’s current and head-of-line packets o the control and data packets
• Multi-hop coordination – extends the DPS scheme to carry out scheduling
over multi-hop paths. 52
 Contention-based protocols with
Scheduling Mechanisms
 Distributed Wireless Ordering Protocol (DWOP)
• A media access scheme along with a scheduling mechanism
• Based on the distributed priority scheduling scheme
 Distributed Laxity-based Priority Scheduling (DLPS) Scheme
• Scheduling decisions are made based on
• The states of neighboring nodes and feed back from destination nodes
regarding packet losses
• Packets are recorded based on their uniform laxity budgets (ULBs) and the
packet delivery ratios of the flows. The laxity of a packet is the time
remaining before its deadline.

53
 MAC Protocols that use directional
Antennas
 MAC protocols that use directional antennas have several
advantages:
• Reduce signal interference
• Increase in the system throughput
• Improved channel reuse
 MAC protocol using directional antennas
• Make use of an RTS/CTS exchange mechanism
• Use directional antennas for transmitting and receiving data packets
 Directional Busy Tone-based MAC Protocol (DBTMA)
• It uses directional antennas for transmitting the RTS, CTS, data frames, and
the busy tones.
 Directional MAC Protocols for Ad Hoc Wireless Networks
• DMAC-1, a directional antenna is used for transmitting RTS packets and
omni-directional antenna for CTS packets.
• DMAC-1, both directional RTS and omni-directional RTS transmission are
used.
54
 Other MAC Protocols
 Multi-channel MAC Protocol (MMAC)
• Multiple channels for data transmission
• There is no dedicated control channel.
• Based on channel usage channels can be classified into three types: high
preference channel (HIGH), medium preference channel (MID), low
preference channel (LOW)
 Multi-channel CSMA MAC Protocol (MCSMA)
• The available bandwidth is divided into several channels
 Power Control MAC Protocol (PCM) for Ad Hoc Networks
• Allows nodes to vary their transmission power levels on a per-packet basis
 Receiver-based Autorate Protocol (RBAR)
• Use a rate adaptation approach
 Interleaved Carrier-Sense Multiple Access Protocol (ICSMA)
• The available bandwidth is split into tow equal channels
• The handshaking process is interleaved between the two channels. 55