Multiple Access Protocols
Performance Analysis
1/12
Slotted ALOHA
Assumptions
Operation
• all frames same size
• when node obtains fresh frame, it
• time is divided into equal size slots, transmits in next slot
time to transmit 1 frame
• if no collision, node can send new
• nodes start to transmit frames only frame in next slot
at beginning of slots
• if collision, node retransmits frame
• nodes are synchronized in each subsequent slot with prob.
• if 2 or more nodes transmit in slot, p until success
all nodes detect collision
2/12
to be the long-run fraction of successful slots in the case when there are a large
number of active nodes, each always having a large number of frames to send.
Slotted ALOHA
Node 1 1 1 1 1
Node 2 2 2 2
Node 3 3 3 3
Time
C E C S E C E S S
Key:
C = Collision slot
E = Empty slot
S = Successful slot
Figure 5.10 ! Nodes 1, 2, and 3 collide in the first slot. Node 2 finally
Pros succeeds in the fourth slot, node 1 in the eighth slot, and
• single active node can node 3 in the ninth slot Cons
continuously
transmit at full rate of channel • wasting slots and idle slots
• highly decentralized: only slots in • clock synchronization
nodes need to be in sync
3/12
Slotted Aloha
Definition
The offered load G [non-dimensional] or traffic is the total amount of packets
that the network nodes have ready to send per frame time.
Definition
The throughput or channel utilization [non-dimensional, symbol τ ] is the
average rate of successful message delivery over a communication channel.
4/12
Slotted Aloha
• Suppose N nodes with many frames to send on a shared segment
• average generation rate of data frames λ (packets/s)
• each time slot corresponds to the duration of a packet
• packet lengths are equal
• Obviously, λ ≤ 1
• For a specific node and a “regular” sending rate, one has
• P {Transmission} ∼ Poisson(λ)
5/12
Slotted Aloha
• Properties of the Poisson distribution
• Probability that k frames are generated during a timeslot is
(λ)k e−λ
Poisson(k ; λ) =
k!
• For a single node, the per-slot probability of transmission is
p ≜ P {has a frame to transmit}
= 1 − P {has no frame, i.e., k =0}
= 1 − exp (−λ)
• Average traffic: E [Poisson(k ; λ)] = λ = Gnode
• For a topology of N nodes
• P {any node transmits} ∼ Poisson(Nλ)
• G = N · Gnode
6/12
Slotted Aloha efficiency
• Suppose now N nodes with collisions (random access)
• data traffic is generated with rate λ
• retransmissions are generated with rate µ
• For the entire channel, one has
• total traffic G = N(λ + µ)
• channel throughput τ = N λ
• What is the probability of collision during a (re-)transmission?
P {any other node transmits} = 1 − e−N(λ+µ)
and we have the expression of the total traffic per slot
−N(λ+µ)
N(λ + µ) = | Nλ
{z } + N(λ + µ) 1 − e
| {z }
traffic generated traffic | {z }
retransmitted traffic
7/12
Slotted Aloha efficiency
• Isolating τ = Nλ yields
τ = G e−G
• Maximization: Gmax ≜ argmax τ
G
• Solution is Gmax = 1 and τmax = e−1 ≈ 37%
• a small increases in the channel load can drastically reduce its performance
• at best the channel used for useful transmissions 37% of time!
• for low values of λ, the behaviour is linear, i.e., τ ≈ Nλ
• perfect zone of operation for WSN (wireless sensor networks)
• need for (self-)regulation
8/12
Slotted Aloha efficiency
0.7
0.6
0.5
τ = G e−G
0.4
0.3
0.2
0.1
0 1 2 3 4 5 6
G
• Some comments:
• τ has a bell-shaped curve (ALOHA instability)
• τ = 0 when G = 0 or G ≫ 1
• G ≤ 1: suitable use of the channel (but τ ≤ 0.37!)
• G > 1: too much collisions !
9/12
ALOHA case, we find that the maximum efficiency of the pure ALOHA protocol is
only 1/(2e)—exactly half that of slotted ALOHA. This then is the price to be paid
Pure (unslotted) ALOHA
for a fully decentralized ALOHA protocol.
Carrier Sense Multiple Access (CSMA)
• unslottedInAloha: simpler,
both slotted no synchronization
and pure ALOHA, a node’s decision to transmit is made independ-
ently of the activity of the other nodes attached to the broadcast channel. In particu-
lar, a node
• when frame firstneither pays attention
arrives, transmit to whether another node happens to be transmitting
immediately.
when it begins to transmit, nor stops transmitting if another node begins to interfere
• collision with its transmission. In our cocktail party analogy, ALOHA protocols are quite like
probability increases:
• frame sent at t0 collides with other frames sent in [t0 − 1,t0 + 1]
Will overlap Will overlap
with start of with end of
i ’s frame i ’s frame
Node i frame
Time
t0 – 1 t0 t0 + 1
Figure 5.11 ! Interfering transmissions in pure ALOHA
10/12
Pure Aloha efficiency
• What is the probability of collision during a (re-)transmission?
P {collision} = 1 − P {no other node transmits in [t0 − 1,t0 + 1]}
= 1 − P {no tx in [t0 − 1]} · P {no tx in [t0 + 1]}
= 1 − e−2 N(λ+µ)
• The throughput is
τ = G e−2G
• Maximization: Gmax ≜ argmax τ
G
• Solution is Gmax = 0.5 and τmax = 1 ≈ 18%
2e
• This is even worse !
11/12
Slotted Aloha efficiency
0.5
τ
0.4 τ = G e−G
0.3
Slotted ALOHA
0.2 τ = G e−2G
ALOHA
0.1
0 1 2 3 4 5 6
G
12/12