Lecture 2

Media Access Control I

Reading:
• “Multiple Access Techniques,” in Ad Hoc Wireless
Networks: Architectures and Protocols, Chapter 1.6.
• A. Chandra, V. Gummalla, and J. Limb,
“Wireless Medium Access Control Protocols,”
IEEE Communications Surveys, Second Quarter 2000.
http://www.comsoc.org/livepubs/surveys/public/2q00issue/gummalla.html
 Media Access Control (MAC)
„ Protocols that enable multiple users to share a finite
amount of frequency and time resources
„ Needed for efficient operation and good performance
for wireless systems
„ Goal: minimize overhead while maximizing overall
network capacity

2
 MAC Performance Parameters
„ Throughput (S): average number of messages successfully
transmitted per unit time
„ Delay (D): average delay experienced by a packet
„ Fairness: how well a MAC protocol shares the bandwidth
among multiple users
„ Stability: performance under load fluctuations
„ Robustness against channel fades
„ Power consumption: power-saving features of the protocol
„ Multimedia support: how well the protocol supports different
types of traffic (e.g., real-time, high-priority data, etc.)

3
 Main Types of MAC
„ Fixed assignment techniques
„ Frequency-division multiple access (FDMA)
„ Time-division multiple access (TDMA)
„ Spread-spectrum multiple access (SSMA)
„ Frequency-hopped spread-spectrum (FHSS)
„ Direct-sequence spread-spectrum (DSSS) / Code-division
multiple access (CDMA)
„ Space-division multiple access (SDMA)
„ Random access (RA) techniques
„ Packet-radio techniques (PR)
„ Controlled random access
„ Combination fixed assignment and RA
„ Use RA to obtain fixed resources
4
 Party Analogy
„ Suppose there are people at a party who all want to talk
„ If everyone talked at once, no one would be able to hear
anyone
„ If one person raises his voice to be heard, others will raise
their voices and eventually everyone will be shouting and no
one will be able to communicate
„ How can this situation be resolved?
„ Each person could be given a turn to speak (TDMA)
„ Each group could be given a language in which to speak to
each other (CDMA)
„ Each group could be given a corner of the room to hold their
conversation (SDMA)
„ Each person talks with a certain probability p when they
determine that no one else is currently speaking (PR)
5
 Frequency-Division MA
„ Radio spectrum broken into frequency bands
(channels)
„ Each channel allocated to a different user (only 1
user per frequency band)
„ Each channel must contain guard bands
Code

Channel n

Channel 2
Channel 1 Time

Frequency
6
 FDMA (cont.)
„ Channels can be assigned on-demand when a user
needs to communicate
„ Each user can only be assigned 1 channel Æ if not
enough users for the number of channels, the radio
spectrum is unused (i.e., wasted)
„ FDMA usually used in narrowband systems (e.g., 30
kHz frequency bands)
„ Large symbol time compared to average delay
spread Æ low ISI
„ Little synchronization required because transmission
is continuous in FDMA Æ reduces overhead
7
 FDMA (cont.)
„ Requires expensive filters to reduce adjacent
channel interference
„ Intermodulation (IM)
„ Nonlinearities in power amplifiers cause signal
spreading in freq domain
„ Undesired RF radiation that leaks into other channels
in FDMA systems
„ Adjacent-channel interference
„ Generation of undesirable harmonics that cause
interference to other users in mobile system or other
systems in adjacent spectrum bands

8
 Time Division MA (TDMA)
„ Users access entire radio spectrum for a given time slot
(channels) Code

Time
Channel 1

Channel 2

Channel n
Frequency
„ Only 1 user can transmit or receive data per slot
„ Time divided into frames
„ Preamble (with synchronization info)
„ Several slots of data
„ Number of data slots per frame depends on modulation, bandwidth,
average data rates and required latencies
9
 TDMA (cont.)
„ Slot contains
„ Preamble for addressing and synchronization
„ Data
„ Guard times between the slots to reduce cross-talk
between channels

One Frame
Preamble Slot 1 Slot 2 Slot n Trail Bits Preamble Slot 1

Guard
Pream Data
Time
10
 TDMA (cont.)
„ Can use multi-slot assignments to support
increased user data rate
„ Channels can be assigned on-demand when a user
needs to communicate

11
 TDMA Advantages
„ Narrowband filters not needed Æ cheaper than
FDMA
„ Mobile devices can save battery power by turning
off transmitter and receiver during slots when not
transmitting or receiving data
„ Can allocate multiple time slots to a user to provide
increased data rate Æ more BW efficient than
FDMA

12
 TDMA Disadvantages
„ Requires guard time between time slots to separate
users and accommodate
„ Time inaccuracies due to clock instability
„ Delay spread of transmitted symbols
„ Transmission time delay
„ Requires signal processing techniques and high
overhead for synchronization due to burst
transmissions

13
 Spread-Spectrum MA (SSMA)
„ Transmission bandwidth is several orders of magnitude
greater than minimum required bandwidth
„ Immunity to frequency-selective fades and multipath
interference
„ Multiple users share the same RF spectrum at the same time
„ No hard limit on the number of users
„ Bandwidth inefficient when few users sharing the channel
„ Bandwidth efficient when lots of users share the channel
„ Direct-sequence (DS): pseudo-noise (PN) sequence converts
narrowband signal to wideband signal with noise-like
properties
„ Frequency-hopped (FH) spread spectrum: pseudorandom
hopping sequence used to vary carrier signal
14
 SSMA Advantages
„ SS signals can be overlaid onto bands where other
systems are already operating with minimal impact
to or from the other systems
„ SS signals have good immunity to mutli-path and
frequency-selective fading
„ SS systems have greater flexibility and overall
system capacity than FDMA or TDMA systems Æ no
hard capacity limit
„ Unlicensed SS systems can be used in the ISM
bands
15
 Direct-Sequence SS (DSSS)
„ Each user occupies bandwidth several times larger than the
message bandwidth
„ Message signal multiplied by a very large BW “spreading
signal”, a PN-code sequence with a “chip rate” several
orders of magnitude larger than the message data rate
„ In CDMA (code-division multiple access), spreading signals
(codes) are approximately orthogonal
Code

Channel n Time

Channel 2
Channel 1

Frequency 16
 DSSS (cont.)
„ Receiver correlates received signal with a particular
codeword to detect desired signal
„ Correlating received signal r (t ) = ∑ mi (t )ci (t ) + n(t )
i
with code
∞
ci(t) will filter out other orthogonal signals
since ∫ ci (t )c j (t )dt = 0
−∞
„ In theory, only noise corrupts received signal
„ SNR determined by the power of the other users
relative to the power of the desired user
„ DSSS systems reject interference by spreading it in
time-frequency

17
 Near-Far Problem
„ If all mobiles transmit with the same power, the signals from
mobiles closest to the BS will be received with much larger
power than signals from mobiles further away. Therefore,
the SNR for signals from mobiles far from the BS will be low
„ Signals from mobiles close to the BS will drown out signals
from mobiles far away from the BS
„ Requires power control to ensure the power of all signals
received at the base station is approx. equal
„ BS determines received power from each mobile (using RSSI—
received signal strength indicator)
„ Tells the mobile to increase or decrease its transmit power to
ensure all signals received with the same power
„ Power control conserves battery power and minimizes
interference to other users
18
 Advantages of DSSS
„ Multipath fading and frequency-selective fading effects
reduced due to spreading of the signal bandwidth
„ Channel data rates high Æ chip duration is short and usually
much less than channel delay spread
„ PN-sequences have low autocorrelation, multipath which is
delayed more than a chip will appear as noise
„ RAKE receiver can be used to improve reception by collecting
time-delayed versions of the signal
„ Soft capacity limit on the number of users—each user sees
degradation in performance as # of users increased and
improvement in performance as # of users decreased
„ Can take advantage of voice activity patterns that cannot be
effectively exploited in FDMA or TDMA systems
„ Security: need to know spreading code to intercept signal
19
 Disadvantages of DSSS
„ Implementation complexity: high channel data rates
„ Expensive receivers
„ Self-jamming due to non-perfect orthogonality of
spreading codes
„ Other users’ signals will appear as noise and reduce
SNR of desired signal
„ Near-far problem causes reduced performance if
receiver cannot control the power level of the near
mobile

20
 Frequency-Hopped SS (FHSS)
„ System bandwidth (Bt) broken into smaller channels
(bandwidth = Bc), data stream broken into bursts
„ Carrier frequency varied for each data burst in a
pseudorandom fashion
„ User “hops” among the different channels
„ Th = hop period
„ Instantaneous bandwidth of each transmission is small, but
spread bandwidth is large
„ Multiple users can access the channel at the same time due
to pseudorandom hopping sequence
„ Ensures low probability of multiple users accessing same hop
frequency at the same time

21
 FHSS (cont.)
„ Fast frequency hopping
„ Th > Ts, there is a frequency hop for each
transmitted symbol
„ Hopping rate equals or exceeds the information
symbol rate
„ Slow frequency hopping
„ Th ≥ Ts, one or more symbols are transmitted in the
time interval between frequency hops
„ FHSS systems reject interference by trying to avoid
it
22
 FHSS (cont.)
„ Advantages of FHSS
„ Immunity to frequency-selective fades using channel coding,
interleaving, and disjointed frequency channels
„ Security: use of pseudorandom hopping pattern makes it hard
for others to intercept full message
„ Soft capacity
„ Immune to the near-far problem
„ Disadvantages of FHSS
„ Multi-user interference possible if two or more users
simultaneously occupy a frequency channel
„ Can use channel coding and interleaving to protect against this

23
 Space-Division MA (SDMA)
„ Segments a coverage area in space
„ Uses directional antennas that transmit signals only in a
certain direction
„ Within each space sector, can use TDMA, FDMA, or SSMA to
divide the time-frequency resources among users
„ Adaptive antennas track users and direct energy in direction
„ Ideal SDMA
„ Adaptive antennas with infinitesimal beamwidth and infinitely
fast tracking ability
„ Provides unique channel for each user with no interference
from other users in cell
„ All users could communicate at the same time using the same
channel
„ Not realizable!
24
 Hybrid MAC
„ FDMA/CDMA
„ Spectrum divided into channels
„ Each channel is a narrowband CDMA system with processing
gain lower than original CDMA system
„ DSSS/FHSS
„ Direct sequence modulate signal and hop center frequency
using pseudorandom hopping pattern
„ Avoid near-far effect
„ TDMA/CDMA
„ Different spreading codes assigned to different cells
„ One user per cell allotted particular time slot
„ Only 1 CDMA user tx in each cell at any given time
„ Avoids near-far effect
25
 Hybrid MAC (cont.)
„ TDMA/FHSS
„ Hop to new frequency at start of new TDMA frame
„ Avoids severe fades on particular channel
„ Used in GSM
„ Hopping sequence predefined, unique per cell
„ Avoid co-channel interference if other BSs transmit on
different frequencies at different times

26
 Random Access MAC Protocols
„ Users attempt to access the channel in an
uncoordinated manner
„ Collisions detected at destination
„ Destination sends ACKs
„ Perfect feedback via ACKs but traffic delay may be
high
„ Vulnerable period = Vp = time interval during which
packets are susceptible to collisions with
transmissions from other users

27
 Summary of RA Approaches
„ ALOHA
„ Pure ALOHA
„ Slotted-ALOHA
„ CSMA: carrier sense multiple access
„ 1-persistent CSMA
„ non-persistent CSMA
„ p-persistent CSMA
„ CSMA/CA: CSMA with collision avoidance
„ BTMA: Busy-tone MA
„ DSMA: Data-sense MA
„ MACAW: MA with CA for wireless networks

28
 Pure ALOHA
„ Data packetized
„ Nodes transmit whenever have information to send
„ Nodes transmit packets at arbitrary times
„ Collisions occur if packet transmissions overlap by
any amount of time
„ Collision Æ both packets must be retransmitted
„ Node waits for an ACK from receiver
„ If no ACK received, packet assumed lost in collision
and retransmitted after a random delay – why wait?

29
 Pure ALOHA (cont.)
„ Assume all packets have same length (L) and
require Tp seconds for transmission
„ Each packet vulnerable to collisions for time Vp = ??
„ Suppose packet A sent at time to
„ If pkt B sent any time between to – Tp and to Æ end
of packet B collides with beginning of packet A
„ If pkt C sent any time between to and to + Tp Æ start
of packet C will collide with end of packet A
„ Total vulnerable interval for packet A is 2Tp
Packet B Packet C
Tp Tp
Packet A
t 30
 Throughput of Pure ALOHA
„ Channel throughput S = average number of successful
packet transmissions per time interval Tp
„ G = total traffic offered to the channel = number of packet
transmissions attempted per packet time Tp, including new
packets as well as retransmissions of old packets
„ Standard unit of traffic flow is the Erlang
„ If channel segmented into intervals of Tp seconds, a traffic
flow of one packet per Tp seconds has a value of 1 Erlang
„ Throughput cannot exceed 1 Erlang without collisions
„ 0≤S≤1
„ If G small, few collisions, few retransmissions, so S~G
„ If G large, many collisions, many retransmissions, so S << G
and S Æ 0
31
 Traffic Model
„ Probability that k packets generated during given
packet time
„ Obeys Poisson distribution with a
„ Mean of l packets per second
„ Mean of G packets per packet period Tp
„ G = lTp
„ P(k) = Pr(k packets generated in time Tp)
= Gke-G / k!
„ Poisson arrival model provides good approximation
for network serving large numbers of nodes
32
 Throughput Analysis
„ Throughput S = G * Pr(no collisions)
„ Vp = 2Tp
„ P’(k) = (2G)ke-(2G) / k! = Pr(k pkts gen. in time 2Tp)
„ Pr(no collisions) = Pr(no other packet generated
during the vulnerable interval = 2 packet slots) =
P’(0) = e-2G
„ S = Ge-2G

33
 Maximum Throughput
„ Max Throughput
„ dS/dG = e-2G – 2Ge-2G = 0
„ Gmax = 1/2 Æ Smax = 1/(2e) ~ 0.184
„ ALOHA can achieve maximum throughput of 18.4%
„ Ex.
„ System supports 10 Mbps
„ Using pure ALOHA, nodes can get at most 1.84 Mbps of info
through network
„ At that peak, total traffic from terminals is
0.5*10Mbps = 5 Mbps
Æ 1.84 Mbps is successfully delivered pkts (old and new)
Æ 3.16 Mbps is packets that suffer collisions
34
 Slotted ALOHA
„ Can increase efficiency of ALOHA using slotted system
„ Transmission time divided into time slots, each slot equal to
packet Tx time
„ All users synchronized to these time slots
„ Packets held until next time slot for transmission if generated
in-between transmission slots
„ Synchronization achieved by transmitting periodic synch pulses
from one designated station in the network
„ Vulnerable period reduced to Tp

35
 Throughput of Slotted ALOHA
„ Pr(no collisions) = Pr(no other pkts generated
during Tp) = P(0) = e-G
„ S = Ge-G

36
 Maximum Throughput
„ dS/dG = e-G – Ge-G = 0
„ Gmax = 1.0 Æ Smax = 1/e ~ 0.368
„ 2x Smax for pure ALOHA
„ 37% of slots have successful data transmissions
„ G = 1 Æ Pr(0 packets offered) = e-G = 1/e ~ 0.368
„ 37% of slots are empty
„ 26% of slots are in collision
„ At higher traffic loads, number of successful slots and empty
slots decreases and number of collision slots increases
„ Slotted ALOHA also not efficient

37
 Carrier Sense Multiple Access
„ ALOHA is an unstable protocol
„ If G increases to greater than 1 due to fluctuation in
offered load, S will decrease
„ Reduction in throughput means fewer successful
packet transmissions and more collisions
„ Number of retransmissions increases, backlogging
messages to be transmitted and traffic load G
„ This in turn decreases S
„ Results in operating point moving to right and S Æ 0
„ Random access protocols can be made stable using
backoff parameters
38
 CSMA (cont.)
„ Inefficiency of ALOHA
„ Users do not take note of transmissions of other
users
„ Leads to high collision probability
„ Collisions can be reduced by reducing offered load
„ Leaves channel underutilized
„ More efficient approach: users listen to the channel
before attempting to transmit a packet
„ Basis for CSMA or “listen-before-talk” protocols

39
 CSMA (cont.)
„ Detection and propagation delay important parameters
„ Detection delay = time required for node to sense whether or
not channel is idle
„ Propagation delay = time required for packet to travel from
one node to the furthest node on the network
„ Want both small detection time and small propagation delay to
minimize collisions
„ Several flavors of CSMA
„ 1-persistent CSMA
„ non-persistent CSMA
„ p-persistent CSMA

40
 1-persistent CSMA
„ Node listens to channel to determine if idle or busy
„ If channel is busy, node listens continuously,
waiting until the channel becomes free
„ Once channel is free, node sends pkt immediately
„ Strategy: transmit packet with Pr = 1 when channel
is free
„ Node waits for an ACK
„ If no ACK received, node waits a random amount of
time and resumes listening to the channel
„ When channel again sensed idle, pkt immediately
retransmitted
41
 1-persistent CSMA (cont.)
„ Collisions can occur
„ Propagation delays: Node A might sense idle channel
even though Node B already began transmitting
„ If Node A and Node B are sensing a busy channel at
the same time, as soon as the channel is free, both A
and B will begin transmitting their data
„ Throughput performance much better than ALOHA
„ Slotted 1-persistant CSMA where nodes begin
transmission at given time slots

42
 Nonpersistent CSMA
„ Node listens to channel
„ If channel idle, node transmits data
„ If channel busy, node waits a randomly selected
interval of time before sensing again
„ If channel idle, node transmits data immediately
„ Otherwise, node again waits a randomly selected
interval of time before sensing again
„ Randomized waiting times between channel
sensings eliminate most collisions resulting from
multiple users transmitting simultaneously upon
sensing the transition from busy to idle
43
 Nonpersistent CSMA (cont.)
„ Throughput values much higher than 1-persistent
CSMA at high traffic loads
„ Max throughput values of 80% or higher
„ At low traffic loads, throughput poor because waiting
strategy does not give benefit when there are few
users trying to transmit
„ Slotted version of nonpersistent CSMA

44
 p-persistent CSMA
„ Slotted channels where slot length typically chosen to be
maximum propagation delay
„ Node senses the channel
„ If the channel is idle, node transmits with probability p
„ With probability 1-p the node defers action to the next slot,
where it senses the channel again
„ If that slot is idle, the station transmits with probability p or
defers again with probability 1-p
„ Procedure repeated until either the packet transmitted or the
channel sensed to be busy
„ When channel detected busy, node senses continuously
„ When the channel again becomes free, the node starts the
procedure again

45
 p-persistent CSMA (cont.)
„ For low/intermediate values of propagation delay
and with p optimized, throughput of p-persistent
CSMA lies between that of slotted and unslotted
nonpersistent CSMA
„ For long propagation delays, p-persistent CSMA
throughput exceeds that of nonpersistent CSMA

46
 Comparison
„ Throughput performance
„ For CSMA protocols, S is a function of a = tTp where
Tp = pkt. transmission time and t = propagation
delay
„ a is the time interval, normalized to packet duration
time, during which a transmitted packet can suffer a
collision
„ t = d m / 3x108 m/s = 3.33 ms/km so a << 1

47
 Comparison (cont.)
„ Comparison of throughput vs traffic load (a=0.01)

48
 Throughput Comparison
(cont.)
„ Slotted and unslotted 1-persistent CSMA essentially
indistinguishable
„ For low levels of traffic, persistent protocols provide
best throughput
„ For high levels of traffic load, nonpersistent
protocols are by far the best
„ Slotted nonpersistent CSMA has a peak throughput
almost twice that of persistent CSMA
„ Capacity = peak value of S over entire range of
offered traffic load G
49
 Throughput Comparison
(cont.)
„ For CSMA protocols, capacity a function of a
„ For large a, ALOHA has better capacity
„ With long propagation delay relative to packet transmission
time, channel state information arrives too late to be used
effectively in reducing collisions Æ large time in which sender’s
packet is vulnerable to collisions
„ Typically want a < 0.01 for good performance using CSMA
protocols
„ If max distance between nodes is 100 m, t = 0.33 ms
„ Tp should be greater than 33 ms to keep a < 0.01
„ If Rb = 1 Mbps Æ minimum packet length = 33 bits
„ If Rb = 10 Mbps Æ minimum packet length = 333 bits

50
 CSMA/CD: CSMA with Collision
Detection (CD)
„ Node monitors its own transmission to detect collision
„ Node must receive while transmitting—if received data
different from transmitted data Æ collision
„ Requires transmitter and receiver capable of “listen-while-
talk” operation
„ Easy to perform CD over Ethernet Æ check voltage levels and
if different than what was sent, a collision has occurred
„ Hard to detect collisions in wireless media
„ Transmitter drowns out interfering signal at transmitting node
„ Hidden terminal problem
„ Too complex to be implemented in most systems

51