Ch4-Multiple Radio Access

CSI-531:Wireless and Mobile Computing
Chapter 4 :
Multiple Radio Access
Dr. Imen Achour

Assistant Professor,
Department of Computer Science & Information,
Majmaah University, Az- Zulfi Campus, KSA.
Slides based on publisher’s slides for 1st and 2nd edition of:
Introduction to Wireless and Mobile Systems by Agrawal & Zeng
© 2003, 2006, Dharma P. Agrawal and Qing-An Zeng. All rights reserved. 1
Chapter 4
Multiple Radio Access
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved 2
Outline
n Introduction
n Contention Protocols
n ALOHA
n Slotted ALOHA
n CSMA (Carrier Sense Multiple Access)
n CSMA/CD (CSMA with Collision Detection)
n CSMA/CA (CSMA with Collision Avoidance)
6.1. Introduction ch
an
ne
l
l
n tro el
c o n
n Recall l i nk)
l c ha
n
wn tro l
n Large # of traffic ( d o c o n n ne
a rd n k) c ha
channels on each BS Fo rw
( u pli
tr a ffic
l
s e ) ne
n Bec. traffic channels used by ve
r
lin
k
ha
n
Re w n
fic
c
1 MS exclusively for call duration ( do a f
a rd k ) tr
rw lin
n Small # of control F o
e(
u p
r s
channels on each BS R e ve
n Bec. control channels MS BS
shared by many MSs
for short periods
n Too expensive/inefficient to assign control channnel for call duration
n MSs compete for these few shared control channels

n For call setup, etc.
© 2007 by©Leszek
Copyright T. LilienP. Agrawal and Qing-An Zeng. All rights reserved
2003, Dharma 4
Introduction – cont. 1
n Multiple access control channels
n Each MS attached to a transmitter/receiver
n Communicates with its BS via a control channel (CC)
n CC shared by other MSs
=> “multiple access” CC

n Transmission from any MS is received by all MSs within
its radio range
MS 3
MS 4
MS 2 Shared Multiple
Access Medium
…
…
MS 1 MS n
Introduction – cont. 2
MS 3
MS 2 Shared Multiple
MS 4
Access Medium
……
MS 1 MS n
n Multiple access issue
n If more than one MS transmits at a time on a CC to BS,
a collision occurs on this CC

n How to determine which MS can transmit to BS?
n Multiple (radio) access protocols (a.k.a. MAC sublayer protocols)

n Solve multiple access issues
n Specify how shared control channels are to be accessed by M
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved (Modified by LTL) 6
Medium (Channel) Sharing Techniques
Static
Channelization
Medium-
sharing
Techniques Scheduled
Dynamic
Medium
Access Control Random
Access
n Static channelization (static medium access control) – channel

assigned in a pre-specified way and not changed
n Dynamic channelization (dynamic medium access control) -
channel allocated as needed and not changes with time
6.2. Multiple (Radio) Access Protocols =
MAC Sublayer Protocols
n Recall ISO Open Systems Interconnection Reference Model
for networks
n Communication subnetwork = 3 lowest layers of OSI
n Network layer (NET)
n Data link layer (DLL)
n Physical layer (PHY)
© 2007 by©Leszek
2003, Dharma 8
6.2. Multiple (Radio) Access Protocols = MAC Sublayer Protocols – cont. 1
n Comm subnet in wired LANs, MANs, PRNs, PANs

LAN = local area network / MAN = metropolitan area network
PAN = personal area network / PRN = paceket radio network
n Classic (wire!): point-to-point full-duplex channels

n Comm subnet in wireless systems
n Broadcast half-duplex channels
n Broadcast over airwaves - not point-to-point
n Radio transmission goes from transmitter to receiver - not full-
duplex
n Can emulate point-to-point transmission in wireless
systems
n In order to use solutions (e.g., protocols) from wired netwroks
over wireless
n Note: broadcast possible in some wired net topologies
n E.g. bus, ring, ...
© 2007 by©Leszek
2003, Dharma 9
6.2. Multiple (Radio) Access Protocols = MAC Sublayer Protocols – cont. 1
n Q: How to emulate point-to-point xmission in wireless

systems?
n A: Modify OSI for point-to-point xmission in wireless systems
n Specifically, split DLL into 2 sublayers:
NET
n Logical link control (LLC)
sublayer (upper sublayer)

DLL
n Medium access control
(MAC) sublayer (lower sublayer)
n MAC sublayer protocols = multiple access protocols =

multiple radio access protocols (see above)
© 2007 by©Leszek
2003, Dharma (Modified by LTL) 10
Types of Multiple Access Protocols
n Types of multiple access protocols (cf. next slide):

n Contention-based protocols - resolve a collision after it
occurs
n Execute a collision resolution protocol after each collision
n Collision-free protocols (a.k.a. conflict free p.) - ensure that a

collision never occurs
n E.g., a bit-map protocol and binary countdown protocol
Classification of
Multiple Access Multiple-access protocols
Protocols Contention-based Collision-free
Random access Random access Collision resolution

protocols – upon
FDMA
collision, retrans-
mit after a ran- ALOHA TREE TDMA
dom delay CSMA WINDOW CDMA
Collision etc.
BTMA, Token Bus
resolution
protocols - upon ISMA DQDB
collision,
retransmit etc. etc.
according to a BTMA: Busy Tone Multiple Access
more sophisti- ISMA: Idle Signal Multiple Access DQDB: Distributed Queue Dual Bus
cated method
ALOHA and CSMA protocols will be discussed in this section.

6.3. Contention-Based Protocols
n Major categories of contention-based protocols
1) ALOHA (a.k.a. Pure ALOHA)
2) Slotted ALOHA
3) CSMA (Carrier Sense Multiple Access)
... discussed in turn below ...
© 2007 by©Leszek
2003, Dharma 13
6.3.1. ALOHA (a.k.a. Pure ALOHA)
n Developed in the 1970s for a packet radio network by
University of Hawaii
n To interconnect islands’ campuses / Single-hop network
n Principles:
n Sender S may transmit a packet at any time (hoping no
collision will occur)
n S finds out whether transmission was successful or
experienced a collision by listening for an ACK broadcast
from the destination station
n Successful if an ACK arrrives within a time-out period T
n If no ACK within T, S assumes that there was a collision
n => packet was lost after colliding with pckt of another station
n If there was a collision, S retransmits after some random
time
n Analogy: 2 people entering a doorway simultaneously
n Collision can occur
6.3.1. ALOHA – cont.
n Recall ALOHA principles:
n Sender S may xmit a packet at any time
n S waits for an ACK broadcast from the destination station
n If there was a collision, S retransmits after some random time
n Example: Packet 2 from MS2 & Packet 3 from MS3 collide

n MS3 retransmits Packet 3 pretty soon (random wait)
n MS2 retransmits Packet 2 much later (random wait)
n Note: Collision can block channel for period up to 2T
Wait for a random time

MS 1 packet MS 3 packet
MS 2 packet
Retransmission Retransmission
1 2 3 3 2
Time
Collision
t-T t t+T
T
Collision in Pure ALOHA (can last up to 2T)
** OPTIONAL ** Throughput of ALOHA
• T – packet length (duration)
• Probability P(n) that n packets arrive in time 2T
-- If 2 packets of length T arrive in time > 2T, they didn’t collide
n -2G
Analogy: two people sufficiently
(2G) e
P(n ) = distant from each other do not
n! collide in a doorway
where G is normalized offerred traffic load for the channel

• Probability P(0) that a packet is successfully received (without
collision) - calculated by letting n=0 in P(n)
P(0 ) = e -2G
• Throughput S
S = G × P(0 ) = G × e -2G
• Maximum throughput for ALOHA (occurs for G = ½ - cf. p. 129)

1
S max = » 0.184
2e
6.3.2. Slotted ALOHA
n Improvements over Pure ALOHA:
n Time is slotted
n Slot length = packet length (duration) = T

n Packet transmission can start only at the
beginning of a slot
n This reduces collision duration
n Pure ALOHA: If Packet 1 is almost finished when it
collides with just-starting Packet 2, collision can lasts
for nearly T+T = 2T (details: Slide +2)
n Slotted ALOHA: 2 Packets can collide only when both
are just starting => collision can last at most T
(details: Slide +4)
6.3.2. Slotted ALOHA – cont.
n Recall Slotted ALOHA improvements:
n Time is slotted / Packet can only start at the beginning of a slot
n This reduces collision duration
n Collision can block channel for max. T
n Example: Packet 2 from MS2 & Packet 3 from MS3 collide

n MS2 retransmits Packet 2 pretty soon (random wait)
n MS3 retransmits Packet 3 much later (random wait)
n Note: Shows again that collision can block channel for period T
MSs 2 & 3 packets Wait for a random time

MS 1 packet
Retransmission Retransmission
1 2&3 2 3
Time
Slots Collision
Collision in Slotted ALOHA (can last max. T)
** OPTIONAL **
Throughput of Slotted ALOHA
• Probability of no collision
P(0 ) = e - G
• Throughput S
S = G × P(0 ) = G × e - G
• Maximum throughput for slotted ALOHA (occurs for G = 1 - cf. p. 130)

1
S max = » 0.368
e
Comparison of Throughputs
for ALOHA and Slotted ALOHA
0.5
§ Max. throughput for
ALOHA (A) Sth = 0.184
0.4 at G = ½
0.368
§ Max. throughput for
Throughput Sth
Slotted ALOHA (SA) Sth

0.3
= 0.368 at G = 1
Slotted Aloha
§ Notice that Sth for SA
0.2 0.184 is exactly 2 x bigger
than Sth for A
Aloha § Hypothesis: bec.
0.1
max. duration of a
collision for SA
(=2T) is 2 x
00 2 4 6 8 smaller than for A
G
Traffic load G (=T)
6.3.2-B. CSMA (Carrier Sense Multiple
Access) Group of Protocols
n Max. throughputs for Pure & Slotted ALOHA are 0.184 &
0.368
n CSMA protocols give better throughput than both Aloha
protocols
n By avoiding collisions
n Basic improvement in all CSMA protocols over ALOHA

protocols:
Listen to the channel (“sense” for the presence of the “carrier”) before
transmitting a packet
n Don’t transmit if channel busy
n Avoids some collisions - but not all
n See Fig - next slide
Perspective on MAC & Access Methods
n Medium Access Control (MAC) NET
n Different nodes must gain access to
the shared medium in a controlled DLL

fashion (otherwise there will be
collisions)
n Access methods
n FDMA - assigning channels in frequency domain
n TDMA - assigning time slots in time domain
n CDMA - assigning code sequences in code domain
n CSMA - assigning transmission opportunities in time
domain on a statistical basis
© 2006, ©
Copyright Michael Hall, Helsinki
2003, Dharma P. AgrawalUniv. of Technology
and Qing-An Zeng. All rights reserved 22
Basic Collision Mechanism in CSMA Protocols
MS 5 senses,
MS 2 senses, avoids collision
sends packet
MS 1 senses, MS 7 senses, sends packet
MS 3 senses,
sends packet sends packet MS 5 Delay
7
1 2 3 6
Delay for MS 4 Collision Time
MS 4 senses,
avoids collision MS 6 senses, sends packet
n Some collisions avoided
n Packet 4 was not sent so it did not collide with Packet 2
n Packet 5 was not sent so it did not collide with Packet 3
n Collisions can still occur if sensing occurs nearly simulta-

neously
n Packet 6 collided with Packet 7
Types of CSMA Protocols
1) Basic CSMA, often just CSMA (Carrier Sense Multiple Access)

2) CSMA/CD (CSMA with Collision Detection)
3) CSMA/CA (CSMA with Collision Avoidance)
© 2007 by©Leszek
2003, Dharma 24
6.3.3 (Basic) CSMA Protocol
n (Basic) CSMA improvement over ALOHAs:
Sender S starts transmission only if no transmission is
ongoing
© 2007 by©Leszek
2003, Dharma 25
Types of CSMA Protocols
Unslotted nonpersistent CSMA
Nonpersistent
CSMA
Slotted nonpersistent CSMA
CSMA
Unslotted persistent CSMA
Persistent CSMA
Slotted persistent CSMA
1-persistent CSMA
p-persistent CSMA
Nonpersistent/x-persistent CSMA Protocols
n 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
then go to Step 1
n Note:
n Random backoff reduces probability of collisions
n Wasted idle time if the backoff time is too long
n 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
n Note:
n There will always be a collision if two or more nodes wait
for idle medium
n Usually senders stop transmission attempts after a few
unsuccessful tries
Nonpersistent/x-persistent CSMA Protocols – cont.
n p-persistent CSMA Protocol:

Slotted time required.
Step 1: If the medium is idle, transmit with probability p, or delay
till next time slot with probability (1-p)
Step 2: If transmission was delayed by one time slot, go to Step 1
Step 3: If the medium is busy, continue to listen until medium
becomes idle, then go to Step 1
n Note:
n P-persistent CSMA is a good tradeoff between nonpersistent
and 1-persistent CSMA
How to Select Probability p ?
n Assume:
N - # nodes that can be active at a time
(i.e., ready to send a packet)
n => Np - the expected number of nodes that will attempt to
transmit once the medium becomes idle
n Np ≥ 1 => a collision is expected to occur
n => to avoid collisions,
network must make sure that Np < 1
Throughput for Different ALOHA and CSMA
Protocols with a=0.01 a = t / T (p. 132)
t - propagation
1.0 0.01-persistent CSMA delay
0.9 Nonpersistent CSMA T – packet
0.8 transmission
time
Throughput Sth
0.7
0.1-persistent CSMA
0.6
Recall:
0.5-persistent CSMA p-persistent:
0.5
1-persistent CSMA transmit with
0.4 probability p if
0.3 medium idle
Slotted Aloha
0.2 Observe:
Aloha
0.1 p = 0.01 is best
0 in this Fig. (others
suffer more
0 1 2 3 4 5 6 7 8 9
collisions reducing
Traffic Load G thruput => “don’t
hurry too much”)
6.3.4. CSMA/CD
(CSMA with Collision Detection)
n In Basic CSMA: If 2 terminals begin sending packets at the
same time, each will transmit its complete packet
n Even if collision is taking place
n Problem: Wasting medium for an entire packet duration
n Solution principle (main CSMA/CD idea):

Backoff immediately after a collision
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved Modified by LTL 31
6.3.4. CSMA/CD (CSMA with Collision Detection) – cont.
n Solution: CSMA/CD (CD = collision detection)

Step 1: If the medium is idle, then transmit
Step 2: If the medium is busy, continue to listen until
the channel is idle, then transmit
Step 3: When a collision is detected during transmission,
cease xmitting immediately
Step 4: Wait a random amount of time & go to Step 1
n Improvement over Basic CSMA:

Able to terminate xmission as soon as collision detected
n Prevents wasting whole time slot (slot = packet duration)
Copyright © 2003, Dharma P. Agrawal and Qing-An Zeng. All rights reserved Modified by LTL 32
T – packet xmission
time
G = gT – normalized
offered load
t - propagation delay
a= t / T - normalized
time unit
g’ = g / T, where g is
propagation path
loss slope
6.3.5. CSMA/CA
(CSMA with Collision Avoidance)
n A basic collision avoidance (CA) scheme
n CSMA/CA rule: Backoff before collision (to avoid collisions)
MS A’s frame MS B’s frame Time

Backoff -
delay for B Backoff -
delay for C
MSs B & C sense
the medium
MS B resenses the
medium and transmits its
frame
MS C resenses the medium
but defers to MS B
6.3.5. CSMA/CA (CSMA with Collision Avoidance) – cont. 1
n When medium idle for a period ≥ DIFS => can xmit

immediately
n DIFS = Distributed InterFrame Space
n In 802.11b networks, DIFS = 50 μs
->
DIFS
© 2006, ©
and Qing-An Zeng. All rights reserved (Modified by LTL) 35
Types of CSMA/CA
n Types of CSMA/CA
1) Basic CSMA/CA
2) CSMA/CA with ACK
3) CSMA/CA with RTS and CTS
... discussed in turn ...
© 2007 by©Leszek
2003, Dharma 36
1) Basic CSMA/CA
n Terminal T senses the medium before xmission
1) If medium is busy, T defers access until the end of current xmission - (b1) in Fig.
2) If medium is idle or once it becomes idle:
n T defers access for time period DIFS - (a) and (b2) in Fig.
n T picks a random backoff period - (c) in Fig.
n As long as medium idle during this backoff period, T keeps counting down
n Whenever medium busy during this backoff period, T freezes its counter
n After medium becomes idle again:
n T defers access for the DIFS period
n T resumes countdown
n T can start transmission when backoff counter = 0
≤ DIFS DIFS Contention window (cf. next slide)
Medium Busy Medium Busy

Time
b1 b2
Deferred access (b) Slot (cf. next slide)
- deferred till idle (b1) +
deferred for DIFS after Rand. backoff period (c)
became idle (b2) (after deferments)
Could not start xmission (a)
since medium became
busy in ≤ DIFS
1) Basic CSMA/CA – cont. 1
All except red text repeated (in larger font)
n Terminal T senses the medium before xmission
1) If medium is busy, T defers access until the end of current
xmission
2) If medium is idle or once it becomes idle:
n T defers access for time period DIFS
n T picks a random backoff period

n Backoff counter - initialized with the value of backoff period
n As long as medium idle during this backoff period, T
keeps counting down = decreases its backoff counter
n I.e., count down as long as medium idle, stop countdown
when medium busy again
n Whenever medium busy during this backoff period, T
freezes its counter
n After medium becomes idle again:
n T defers access for the DIFS period
n T resumes countdown
n T can start transmission when backoff counter = 0
n Fragment of the CSMA/CA protocol:

n As long as medium idle during this backoff period, T keeps
counting down = decreases its backoff counter

n I.e., count down as long as medium idle, stop
countdown when medium busy again

Idle – starts countdown Busy – stops countdown
≤ DIFS DIFS Contention window

Time
Medium Busy Medium Busy

b1 b2
Deferred access (b) Slot
- deferred till idle (b1) +
deferred for DIFS after Rand. backoff period (c)
became idle (b2) (after deferments)
Could not start xmission (a)
since medium became
busy in ≤ DIFS
n Use of slots: Backoff counter is decreased by 1
each time medium is idle for 1 time slot interval
Contention Window (CW)
n Recall: Backoff counter is decreased by 1 each time medium is detected to be idle for an
interval of one time slot
=> backoff period = backoff number (bn) = # of idle slots
within CW to wait before being allowed to xmit a frame
n Random bn value is chosen based on CW size
n CW_size: 31 - 1023 slots (=> bn can be from 31 to 1032)
n bn value: uniform distribution over 0 … CW_size
n If transmission of a frame unsuccessful & frame to be re-
transmitted => CW_size is doubled before retran. (up to 1023)
©
© 2006,
2007 by©
Copyright Michael
Leszek T.Hall,
LilienHelsinki
and Qing-An (sl.19)
Zeng. All rights reserved (Modified by LTL) 40
Selection of Random Backoff Value

n Recall: If transmission of a frame unsuccessful & frame allowed to
be retransmitted =>
=> before each retransm. CW_size is doubled (up to 1023)
=> Pr{ bn value is larger } is higher

n Since it is unlikely that several stations will choose the same
value of bn, collisions are avoided
©
© 2006,
2007 by©
Copyright Michael
Leszek T.Hall,
LilienHelsinki
and Qing-An (sl. 20)
2) CSMA/CA with ACK
n Positive Acknowledgement (ACK) frame from receiver upon
reception of each data frame
n ACK sent after receipt + after time interval SIFS
n SIFS = Short Interframe Space
n Receiver transmits ACK without sensing the medium (cf. next)
n If ACK lost, retransmission of ACK
n SIFS < DIFS
E.g., in 802.11b networks:
DIFS n SIFS = 10 μs / DIFS = 50 μs
Source Data
MS Time
SIFS
Destination ACK
MS
DIFS Contention window
Other Medium Busy

MS
Defer access Backoff after defer
CSMA/CA with ACK – cont. 1
->
->
n When a frame is received without bit errors,

receiving station B sends ACK back to vmitting station A
©
© 2006,
2007 by©
Copyright Michael
Leszek T.Hall,
LilienHelsinki
and Qing-An Zeng. All rights reserved 43
n Receiver transmits ACK without sensing the medium

n It works well because medium (radio channel) is “reserved” for
ACK
->
->
n Medium “reserved” during the transmission sequence:

Transmitted frame + SIFS + ACK
n Next frame (from any station) can be transmitted at earliest after ACK
and after next DIFS period
© 2006, ©
and Qing-An Zeng. All rights reserved (Modified by LTL) 44
n Recal: SIFS < DIFS -- E.g., in 802.11b: SIFS = 10 μs / DIFS = 50 μs
n When 2 stations try to access the medium at the same time,

the one that has to wait for the shorter SIFS period “wins
over” the one that has to wait for the longer DIFS period
n “Wins over” = waits for shorter time
n Just bec. SIFS < DIFS
n In other words, ACK frame waiting for SIFS has higher

priority over Data frame waiting for DIFS
n Now you see why Data
medium “reserved”
in quotes - not real
SIFS
reservation, just
DIFS
given an advantage
to guarantee it
Data
always wins a race
C -> D
Figure
© 2007 based onDharma
by©Leszek
Copyright 2003, ©Lilien
T. 2006, Michael
P. Agrawal andHall, Helsinki
Qing-An Zeng. Univ. of reserved
All rights Technology (Modified by LTL) 45
n When Station S wants to send a frame & channel busy

=> S must wait a backoff time before it may to xmit frame
n Reason? Next two slides…
©
© 2006,
2007 by©
Copyright Michael
Leszek T.Hall,
LilienHelsinki
Zeng. All rights reserved 46
n No backoff => collision is certain

n Suppose that stations B and C waiting to access channel
n When channel becomes idle,
B & C start sending their packets at the same time
=> collision!
©
© 2006,
2007 by©
Copyright Michael
Leszek T.Hall,
LilienHelsinki
n Random backoff => Pr { collision } is reduced
n Contending stations generate random backoff numbers bn
n Backoff counters count down, starting from bn
n When backoff counter reaches zero,
station allowed to send its frame
n All other counters stop counting until the channel becomes idle
again
n Example below (fig): B & C back off after deferring for DIFS
n C has small bn – xmits sooner
n B has large bn – waits longer
©
© 2006,
2007 by©
Copyright Michael
Leszek T.Hall,
LilienHelsinki
Example for CSMA/CA with ACK
n Four stations: A, B, C, D
n Observe:
n C attempts to access medium before B does
n Coincidentally, C’s backoff number is smaller
©
© 2006,
2007 by©
Copyright Michael
Leszek T.Hall,
LilienHelsinki
Example for CSMA/CA with ACK – cont. 1
n Observe backoff counter for B:

n Frozen when medium becomes busy
n When C starts xmission (when C’s backoff counter becomes 0)
n B resumes countdown when medium becomes idle
n After C completes its xmission
© 2006, ©
and Qing-An (sl.22)
Example for CSMA/CA with ACK – cont. 2
n Observe backoff counter for D:

n Frozen when medium becomes busy
n When B starts xmission (when B’s backoff counter becomes 0)
n D resumes countdown when medium becomes idle
n After B completes its xmission
© 2006, ©
3) CSMA/CA with RTS and CTS
n Transmitter sends an RTS (Request To Send) after medium
has been idle for time interval > DIFS
n Receiver responds with CTS (Clear To Send) after medium
has been idle for SIFS
n Data can be xmitted (after SIFS)
n ACK sent after SIFS
DIFS SIFS
RTS Data Time
Source MS
SIFS SIFS
Destination CTS ACK

MS
DIFS
Contention window
Medium Busy
Other MS
Defer access Backoff
3) CSMA/CA with RTS and CTS – cont. 1a
Ladder Diagram for CSMA/CA with RTS/CTS
Compare this diagram to the previous one
Source MS Destination MS Other MS
DIFS
RTS
Propagation delay
SIFS
CTS
Propagation delay
SIFS Data
Propagation delay
SIFS
A CK Propagation delay
DIFS
3) CSMA/CA with RTS and CTS – cont. 1b
n RTS/CTS performs channel reservation for data xmission

n Collision can occur at worst during sending RTS control
message
n Bec. SIFS (preceding CTS, Data, ACK) < DIFS (preceding other
MS’s RTS)
DIFS SIFS
RTS Data Time
Source MS
SIFS SIFS
Destination CTS ACK

MS
DIFS
Contention window
Medium Busy
Other MS
Defer access Backoff

3) CSMA/CA with RTS/CTS – cont. 1c
n RTS = Request To Send / CTS = Clear To Send
n RTS/CTS scheme - used as a countermeasure against the

“hidden node” problem
n Hidden node problem
n WS 1 & WS 2 can hear
AP but not each other

n => If WS 1 sends a packet,
WS 2 does not notice this

(and vice versa)
=> collision!
© 2006, ©
3) CSMA/CA with RTS/CTS – cont. 1b
n RTS/CTS scheme makes reservation of the medium to avoid

collisions
n RTS reserves medium for time needed for xmission of:
n CTS + Data + ACK + 3 * SIFS
n = SIFS + CTS + SIFS + Data + SIFS + ACK
n CTS reserves medium for time needed for xmission of:
n Data + ACK + 2 * SIFS (original: “3 * SIFS [?])
n = SIFS + Data + SIFS + ACK
©Copyright
2006, Michael Hall, Helsinki
© 2003, Dharma Univ.
P. Agrawal and of Technology
Qing-An Zeng. All(sl. 26)reserved
rights 56
3) CSMA/CA with RTS/CTS – cont. 2
n Danger of collision only during RTS

+ SIFS (see Fig. below), because:
n WS 2 does not hear the RTS
frame from WS 1 to AP
n => WS 2 misses reservation for
CTS + Data + ACK + 3 * SIFS
n WS 2 can hear the CTS frame
from AP to WS 1
n => WS 2 knows about reservation
for Data + ACK + 2 * SIFS
©Copyright
Qing-An Zeng. All rights reserved 57
Advantages of RTS & CTS
n Advantage #1 of RTS/CTS:
Reduces collision probability if the data frame is very long
compared to the RTS frame
n Does not prevent collisions during very short RTS frames
n Not a big problem - they are not very likely
n Prevents more likely collisions during long data frame
©Copyright
rights 58
Advantage of RTS & CTS – cont.
n Advantage #2 of RTS/CTS
Avoids having long intervals with high collision danger (same Fig)
n Good! Long interval w/ high collision danger should be

avoided
n Should be for the following reasons:
n Larger probability of collision
n Greater waste of capacity if a collision occurs and the frame
has to be retransmitted
n Frames shorter than a certain threshold value can be
transmitted without using RTS/CTS
n Because small waste of medium if collision occurs for short frames
=> low risk
n Threshold parameter (dot11RTSThreshold) set in a xmitting station
©Copyright
rights 59
Summary: Full Taxonomy of
CSMA (Carrier Sense Multiple Access) Protocols
1) (Basic) CSMA
1a) Nonpersistent CSMA
– Slotted
– Unslotted
1b) Persistent CSMA
Subcategories # 1 of Persistent CSMA:
– Slotted
– Unslotted
Subcategories # 2 (orthogonal) of Persistent CSMA:
–1-persistent CSMA
– p-persistent CSMA
2) CSMA/CD (CSMA with Collision Detection)

3) CSMA/CA (CSMA with Collision Avoidance)
3a) Basic CSMA/CA
3b) CSMA/CA with ACK
3c) CSMA/CA with RTS/CTS
© 2007 by©Leszek
2003, Dharma 60

Ch4-Multiple Radio Access

Uploaded by

Copyright:

Available Formats

Ch4-Multiple Radio Access

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Ch4-Multiple Radio Access

Uploaded by

Copyright:

Available Formats

CSI-531:Wireless and Mobile Computing

Dr. Imen Achour

n MSs compete for these few shared control channels

n Communicates with its BS via a control channel (CC)

n CC shared by other MSs

=> “multiple access” CC

a collision occurs on this CC

n Multiple (radio) access protocols (a.k.a. MAC sublayer protocols)

n Specify how shared control channels are to be accessed by M

n Static channelization (static medium access control) – channel

n Network layer (NET)

n Data link layer (DLL)

n Physical layer (PHY)

n Comm subnet in wired LANs, MANs, PRNs, PANs

n Classic (wire!): point-to-point full-duplex channels

n Q: How to emulate point-to-point xmission in wireless

sublayer (upper sublayer)

(MAC) sublayer (lower sublayer)

n MAC sublayer protocols = multiple access protocols =

n Types of multiple access protocols (cf. next slide):

n Collision-free protocols (a.k.a. conflict free p.) - ensure that a

Protocols Contention-based Collision-free

Random access Random access Collision resolution

ALOHA and CSMA protocols will be discussed in this section.

... discussed in turn below ...

n S waits for an ACK broadcast from the destination station

n If there was a collision, S retransmits after some random time

n Example: Packet 2 from MS2 & Packet 3 from MS3 collide

n MS2 retransmits Packet 2 much later (random wait)

n Note: Collision can block channel for period up to 2T

Wait for a random time

where G is normalized offerred traffic load for the channel

• Maximum throughput for ALOHA (occurs for G = ½ - cf. p. 129)

n Slot length = packet length (duration) = T

n This reduces collision duration

n Collision can block channel for max. T

n Example: Packet 2 from MS2 & Packet 3 from MS3 collide

n MS3 retransmits Packet 3 much later (random wait)

MSs 2 & 3 packets Wait for a random time

• Maximum throughput for slotted ALOHA (occurs for G = 1 - cf. p. 130)

Slotted ALOHA (SA) Sth

n Basic improvement in all CSMA protocols over ALOHA

the shared medium in a controlled DLL

n TDMA - assigning time slots in time domain

n CDMA - assigning code sequences in code domain

n CSMA - assigning transmission opportunities in time

domain on a statistical basis

n Packet 5 was not sent so it did not collide with Packet 3

n Collisions can still occur if sensing occurs nearly simulta-

1) Basic CSMA, often just CSMA (Carrier Sense Multiple Access)

n 1-persistent CSMA Protocol:

n p-persistent CSMA Protocol:

and 1-persistent CSMA

n Problem: Wasting medium for an entire packet duration

n Solution principle (main CSMA/CD idea):

n Solution: CSMA/CD (CD = collision detection)

n Improvement over Basic CSMA:

MS A’s frame MS B’s frame Time

n When medium idle for a period ≥ DIFS => can xmit