Irregular Repetition Slotted ALOHA over the
Rayleigh Block Fading Channel with Capture

arXiv:1706.09927v1 [cs.IT] 29 Jun 2017

Federico Clazzer∗ , Enrico Paolini† , Iacopo Mambelli‡ , Čedomir Stefanović§
∗ Institute of Communications and Navigation of DLR (German Aerospace Center), Wessling, Germany.
† Department of Electrical, Electronic, and Information Engineering, University of Bologna, Cesena, Italy.
‡ Fores Engineering S.R.L., Forlı̀, Italy.
§ Department of Electronic Systems, Aalborg University, Aalborg, Denmark.

Abstract—Random access protocols relying on the transmission
of packet replicas in multiple slots and exploiting interference
cancellation at the receiver have been shown to achieve performance competitive with that of orthogonal schemes. So far
the optimization of the repetition degree profile, defining the
probability for a user to transmit a given number of replicas,
has mainly been performed targeting the collision channel model.
In this paper the analysis is extended to a block fading channel
model, also assuming capture effect at the receiver. Density
evolution equations are developed for the new setting and,
based on them, some repetition degree profiles are optimized
and analyzed via Monte Carlo simulation in a finite frame
length setting. The derived distributions are shown to achieve
throughputs largely exceeding 1 [packet/slot].

I. I NTRODUCTION
Framed slotted ALOHA (FSA) [1] is a random access
scheme in which link-time is divided in frames and frames
consist of slots. Users are frame- and slot-synchronized; a
user contends by transmitting its packet in a randomly chosen
slot of the frame. For the collision channel model, the maximum value of the expected asymptotic throughput of FSA is
1/e [packet/slot].
A substantial throughput gain can be achieved by modifying
FSA such that (i) the users transmit replicas of their packets
in several slots chosen at random, where each replica embeds
pointers to slots containing the other replicas, and (ii) when a
replica has been decoded at the receiver, all the other replicas
are removed through the use of interference cancellation (IC)
[2], [3]. Specifically, it has been shown that this enhanced version of FSA, named irregular repetition slotted Aloha (IRSA)
[3], bears striking similarities to the erasure-correcting coding
framework in which the decoding is performed with iterative
belief-propagation. These insights were followed by a strand of
works applying various concepts and tools of erasure-coding
theory to design slotted ALOHA-based schemes, commonly
referred to as coded slotted ALOHA.1 The overall conclusion
is that coded slotted ALOHA schemes can asymptotically
achieve the expected throughput of 1 [packet/slot], which is
the ultimate limit for the collision channel model.
On the other hand, the collision channel model is a rather
simple one, which assumes that (i) noise can be neglected,
1 We

refer the interested reader to [4] for an overview.

such that a transmission can be decoded from a singleton slot
by default, and (ii) no transmission can be decoded from a
collision slot. This model has a limited practical applicability
and does not describe adequately the wireless transmission
scenarios where the impact of fading and noise cannot be
neglected. In particular, fading may incur power variations
among signals observed in collisions slot, allowing for the
capture effect to occur, when sufficiently strong signals may be
decoded. In the context of slotted ALOHA, numerous works
assessed the performance of the scheme for different capture
effect models [5]–[10]. One of the standardly used models is
the threshold-based one, in which a packet is captured, i.e.,
decoded, if its signal-to-interference-and-noise ratio (SINR) is
higher then a predefined threshold, c.f. [8]–[11].
A brief treatment of the capture effect in IRSA framework
was made in [3], pointing out the implications related to the
asymptotic analysis. In [12], the method for the computation of
capture probabilities for the threshold-based model in singleuser detection systems with Rayleigh fading was presented and
instantiated for the frameless ALOHA framework [13].
In this paper, we extend the treatment of the threshold-based
capture effect for IRSA framework. First, we derive the exact
expressions of capture probabilities for the threshold-based
model and Rayleigh block-fading channel. Next we formulate
the asymptotic performance analysis. We then optimize the
scheme, in terms of deriving the optimal repetition strategies
that maximize throughput given a target packet loss rate (PLR).
Finally, the obtained distributions are investigated in the finite
frame length scenario via simulations. We show that IRSA
exhibits a remarkable throughput performance that is well over
1 [packet/slot], for target PLR, SNR and threshold values that
are valid in practical scenarios. This is demonstrated both for
asymptotic and finite frame length cases, showing also that the
finite-length performance indeed tends to the asymptotic one
as the frame length increases.
The paper is organized as follows. Section II introduces
the system model. Section III deals with derivation of capture
probabilities for Rayleigh block-fading channels, which are
used in Section IV to evaluate the asymptotic performance of
IRSA. The study of optimal repetition strategies is done in
Section V, including their characterization in the finite-frame
length case. Section VI concludes the paper.

II. S YSTEM M ODEL

slot nodes, S

A. Access Protocol
For the sake of simplicity, we focus on a single batch
arrival of m users each having a single packet (or burst)
and contending for the access to the common receiver. The
link time is organized in a medium access control (MAC)
frame of duration TF , divided into n slots of equal duration
TS = TF /n, indexed by j ∈ {1, 2, . . . , n}. The transmission
time of each packet equals the slot duration. The system load
G is defined as
m
[packet/slot] .
G=
n
According to the IRSA protocol, each user selects a repetition degree d by sampling a probability mass function (p.m.f.)
dmax
and transmits d identical replicas of its burst in d
{Λd }d=2
randomly chosen slots of the frame. It is assumed that the
header of each burst replica carries information about the
locations (i.e., slot indexes) of all d replicas. The p.m.f. {Λd }
is the same for all users and is sampled independently by
different users, in an uncoordinated
fashion. The average burst
Pdmax
repetition degree is d̄ = d=2
d Λd , and its inverse
R=

1
d̄

(1)

is called the rate of the IRSA scheme. Each user is then
unaware of the repetition degree employed by the other users
contending for the access. The number of burst replicas
colliding in slot j is denoted by cj ∈ {1, 2, . . . , m}. Burst
replicas colliding in slot j are indexed by i ∈ {1, 2, . . . , cj }.
B. Received Power and Fading Models
We consider a Rayleigh block fading channel model, i.e.,
fading is Rayleigh distributed, constant and frequency flat in
each block, while it is independent and identically distributed
(i.i.d.) on different blocks. Independent fading between different burst replicas is also assumed. In this way, the power of
a burst replica i ∈ {1, 2, . . . , cj } received in slot j, denoted
as Pij , is modeled as a random variable (r.v.) with negative
exponential distribution
(
 
1
exp − P̄p , p ≥ 0
P̄
fP (p) =
0,
otherwise
where P̄ is the average received power. This is assumed to
be the same for all burst replicas received in the MAC frame
by using, e.g., a long-term power control. The r.v.s Pij are
i.i.d. for all (i, j) pairs. If we denote by N the noise power,
the signal-to-noise ratio (SNR) r.v. Bij = Pij /N is also
exponentially distributed as
(


1
exp − B̄b , b ≥ 0
fB (b) = B̄
0,
otherwise
where the average SNR is given by
B̄ =

P̄
.
N

s1

s2

s3

...

sn

b1

b2

b3

...

bm

burst nodes, B
Fig. 1. Graph representation of MAC frame.

C. Graph Representation
In order to analyze the successive interference cancellation
(SIC) process, we introduce the graph representation of a MAC
frame [3]. As depicted in Fig. 1, a MAC frame is represented
as a bipartite graph G = (B, S, E) consisting of a set B of m
burst nodes (or user nodes), one for each user, a set S of n slot
nodes, one per slot, and a set E of edges, one per transmitted
burst replica. A burst node bk ∈ B is connected to a slot node
sj ∈ S if and only if user k has a burst replica sent in the
j-th slot of the frame. The node degree represents the number
of edges emanating from a node.
For the upcoming analysis it is convenient to resort to the
concept of node- and edge-perspective degree distributions.
The burst node degree distribution from a node perspective
dmax
is identified by the above-defined p.m.f. {Λd }d=2
. Similarly,
the slot node degree distribution from a node perspective is
m
defined as {Pc }c=0 , where Pc is the probability that a slot
node has c connections (i.e., that c burst replicas have been
received in the corresponding slot). The probability Pc may be
easily calculated by observing that (G/R)/m is the probability
that the generic user transmits a burst replica in a specific slot.
Since users behave independently of each other, we obtain
 
c 
m−c
m
G/R
G/R
Pc =
1−
.
c
m
m
The polynomial representations for both node-perspective
degree distributions are given by
Λ(x) =

dX
max
d=2

Λd xd

and

P(x) =

m
X

Pc xc .

c=0


For m → ∞ and constant G/R, P(x) = exp − GR (1 − x) .
Degree distributions can also be defined from an edgeperspective. Adopting a notation similar to the one used for the
node-perspective distributions, we define the edge-perspective
dmax
burst node degree distribution as the p.m.f. {λd }d=2
, where
λd is the probability that a given edge is connected to a burst
node of degree d. Likewise, we define the edge-perspective
m
slot node degree distribution as the p.m.f. {ρc }c=0 , where ρc
is the probability that an edge is connected to a slot node of

P
degree c. From the
P definitions we have λd = d Λd / ( t t Λt )
and ρc = c Pc / ( t t Pt ); it can be shown that, for m → ∞
and constant G/R, ρc = exp{−G/R}(G/R)c−1 /(c − 1)!.
The
corresponding polynomial
Pm representation are λ(x) =
Pdmax
d−1
and ρ(x) = c=0 ρc xc−1 . Note that λ(x) =
d=2 λd x
Λ0 (x)/Λ0 (1) and ρ(x) = P0 (x)/P0 (1).2
D. Receiver Operation
In our model, the receiver is always able to detect burst
replicas received in a slot, i.e., to discriminate between an
empty slot where only noise samples are present and a slot
in which at least one burst replica has been received. We
assume that the receiver is able to obtain perfect channel state
information, also in the slots undergoing packet collisions.
Moreover, a threshold-based capture model for the receiver is
assumed, by which the generic burst replica i is successfully
decoded (i.e., captured) in slot j if the SINR exceeds a certain
threshold b? , namely,
(
P
1, N+Iijij ≥ b?
(2)
Pr{burst replica i decoded} =
0, otherwise.
The quantity Iij in (2) denotes the power of the interference
impairing replica i in slot j. In our system model the threshold
b? fulfills b? ≥ 1, which corresponds to a conventional
narrowband single-antenna system. As we are considering a
SIC-based receiver, under the assumption of perfect IC Iij is
equal to sum of the powers of those bursts that have not yet
been cancelled from slot j in previous iterations (apart form
burst i). Specifically,
X
Iij =
Puj
(3)
u∈Rj \{i}

where Puj is the power of burst replica u not yet cancelled in
slot j and Rj denotes the set of remaining burst replicas in
slot j. Exploiting (3), after simple manipulation we obtain
Pij
B
P ij
.
=
N + Iij
1 + u∈Rj \{i} Buj
Hence, in the adopted threshold-based capture model the
P
condition N+Iijij ≥ b? in (2) may be recast as
Bij
1+

P

u∈Rj \{i}

Buj

≥ b? .

(4)

When processing the signal received in some slot j, if burst
replica i is successfully decoded due to fulfillment of (4), then
(i) its contribution of interference is cancelled from slot j, and
(ii) the contributions of interference of all replicas of the same
burst are removed from the corresponding slots.3 Hereafter, we
refer to the former part of the IC procedure as intra-slot IC and
to the latter as inter-slot IC. Unlike SIC in IRSA protocols over
a collision channel, which only rely on inter-slot IC, SIC over
a block fading channel with capture takes advantage of intraslot IC to potentially decode burst replicas interfering each
f 0 (x) denotes the derivative of f (x).
assume that the receiver is able to estimate the channel coefficients
required for the removal of the replicas.
2 Notation
3 We

other in the same slot. In this respect, it effectively enables
multi-user decoding in the slot.
Upon reception of a new MAC frame, slots are processed
sequentially by the receiver. By definition, one SIC iteration
consists of the sequential processing of all n slots. In each slot,
intra-slot IC is performed repeatedly, until no burst replicas
exist for which (4) is fulfilled. When all burst replicas in
slot j have been successfully decoded, or when intra-slot
IC in slot j stops prematurely, inter-slot IC is performed
for all burst replicas successfully decoded in slot j and the
receiver proceeds to process slot j + 1. When all n slots in
the MAC frame have been processed there are three possible
cases: (1) a success is declared if all user packets have been
successfully received; (2) a new iteration is started if at least
one user packet has been recovered during the last iteration, its
replicas removed via inter-slot IC, and there still are slots with
interfering burst replicas; (3) a failure is declared if no user
packets have been recovered during the last iteration and there
still are slots with interfering burst replicas, or if a maximum
number of SIC iterations has been reached and there still are
slots with interfering burst replicas.
Exploiting the graphical representation reviewed in Section II-C, the SIC procedure performed at the receiver may be
described as a successive removal of graph edges. Whenever a
burst replica is successfully decoded in a slot, the corresponding edge is removed from the bipartite graph as well as, due
to inter-slot IC, all edges connected to the same burst node.
A success in decoding the MAC frame occurs when all edges
are removed from the bipartite graph. Two important features
pertaining to the receiver operation, when casted into the graph
terms, should be remarked. The first one is that, due to capture
effect, an edge may be removed from the graph when it is
connected to a slot node with residual degree larger than one.
The second one is that an edge connected to a slot node with
residual degree one may not be removed due to poor SNR,
when (4), with Rj \ {i} = ∅, is not fulfilled.
III. D ECODING P ROBABILITIES
Consider the generic slot node j at some point during the
decoding of the MAC frame and assume it has degree r under
the current graph state. This means that r could be the original
slot node degree cj or the residual degree after some inter-slot
and intra-slot IC processing. Note that, as we assume perfect
IC, the two cases r = cj and r < cj are indistinguishable.
Among the r burst replicas not yet decoded in slot j, we
choose one randomly and call it the reference burst replica.
Moreover, we denote by D(r) the probability that the reference
burst replica is decoded starting from the current slot setting
and only running intra-slot IC within the slot. As we are
considering system with b? ≥ 1, the threshold based criterion
(4) can be satisfied only for one single burst replica at a time.
Therefore there may potentially be r decoding steps (and r −1
intra-slot IC steps), in order to decode the reference burst
replica. Letting D(r, t) be the probability that the reference
bust replica is successfully decoded in step t and not in any

qi = fb(pi−1)
pi−1 = fs(qi−1)
qi−1 = fb(pi−2)
pi−2 = fs(qi−2)
qi−2 = fb(pi−3)

Fig. 2. Tree representation of the MAC frame.

step prior to step t, we may write
D(r) =

r
X

D(r, t) .

t=1

Now, with a slight abuse of the notation, label the r burst
replicas in the slot from 1 to r, arranged such that: (i) the first
t − 1 are arranged by their SNRs in the descending order (i.e.,
B1 ≥ B2 ≥ . . . Bt−1 ), (ii) the rest have SNR lower than Bt−1
but do not feature any particular SNR arrangement among
them, (iii) the reference burst is labeled by t, i.e., its SNR by
Bt , and (iv) the remaining r − t bursts are labeled arbitrarily.
The probability of having at least t successful burst decodings
through successive intra-slot IC for such an arrangement is


B
B
P1r
Pr t
≥ b? , . . . ,
≥ b?
Pr
1 + i=2 Bi
1 + i=t+1 Bi
Z ∞
Z ∞
1
= r
dbr · · ·
dbt+1
B̄
0
Z ∞0
Z ∞
b1
br
×
dbt · · ·
db1 e− B̄ · · · e− B̄
P
P
=

b? (1+ ri=t+1 bi )
? Pt−1
? i
− bB̄
i=0 (1+b )

e

t(r− t+1
2 )

(1 + b? )

b? (1+

=

r
i=2

dX
max

(d)

λd qi

(1 + b? )t(r−

=

t+1
2

λd pd−1
i−1 =: fb (pi−1 )

(6)

where λd is the probability that an edge is connected to a
(d)
burst node of degree d (see Section II-C) and qi is the
probability that an edge carries an erasure message given that
it is connected to a burst node of degree d. In the second
equality we used the fact that the an outgoing message from a
burst node carries an erasure only if all incoming edges carry
(d)
d−1
an erasure, i.e., qi = pi−1
.
Similarly, the probability that an edge carries an erasure
message from SNs to BNs in i-th iteration is
pi =

)

dX
max
d=1

d=1

bi )

.

+∞
X

(c)

ρc pi

(7)

c=1

Further, the number of arrangements in which the SNR of the
reference replica is not among first (t − 1) largest is (r−1)!
(r−t)! ,
where it is assumed that all arrangements are a priory equally
likely. Thus, the probability that the reference burst is decoded
exactly in the t-th step is
D(r, t) =

qi =

? t

− B̄1 ((1+b ) −1)

e

purpose, we unfold the graph representation of the MAC frame
(Fig. 1) into a tree, choosing a random burst node as its root,
as depicted in Fig. 2. The evaluation is performed in terms
of probabilities that erasure messages are exchanged over the
edges of the graph, where the erasure message denotes that the
associated burst is not decoded.4 The message exchanges are
modeled as successive (i.e., iterative) process, corresponding
to the decoding algorithm described in Section II-D in the
asymptotic case, when the lengths of the loops in the graph
tends to infinity. Specifically, the i-th iteration consists of the
update of the probability qi that an edge carries an erasure
message from a burst node to a slot node, followed by the
update of the probability pi that an edge carries an erasure
message from a slot node to a burst node. These probabilities
are averaged over all edges in the graph. We proceed by
outlining the details.
The probability that an edge carries an erasure message from
burst nodes to slot nodes in i-th iteration is

(c)
pi

− B̄1 ((1+b? )t −1)

(r − 1)! e
, 1 ≤ t ≤ r.
(r − t)! (1 + b? )t(r− t+1
2 )

where ρc is the probability that an edge is connected to a slot
(c)
node of degree c, and where pi is the probability an edge
carries an erasure message given that it is connected to a slot
node of degree c. This probability may be expressed as

(5)

b?

We conclude this section by noting that D(1) = e− B̄ ≤ 1,
i.e., a slot of degree 1 is decodable with probability that
may be less than 1 and that depends on the ratio of the
capture threshold and the expected SNR. Again, this holds
both for slots whose original degree was 1 and for slots
whose degree was reduced to 1 via IC, as these two cases
are indistinguishable when the IC is perfect.
IV. D ENSITY E VOLUTION A NALYSIS AND D ECODING
T HRESHOLD D EFINITION
In this section, we apply the technique of density evolution
(DE) in order to evaluate asymptotic performance of the
proposed technique, i.e., when m → ∞ and n ∝ m. For this

c
X



c − 1 r−1
=1−
D(r)
q (1 − qi )c−r ,
r−1 i
r=1

(8)

where summation is done over all possible values of the
reduced
i.e., 1 ≤ r ≤ c, and where the term
 degree r, c−r
c−1 r−1
q
(1
−
q
)
corresponds to the probability that the
i
r−1 i
degree of the slot node is reduced to r and D(r) is the
probability that the burst corresponding to the outgoing edge
is decoded when the (reduced) degree of the slot node is r.5
4 For a more detailed introduction to the DE, we refer the interested reader
to [14].
5 As in the asymptotic case the loops in the graph are assumed to be of
infinite length, such that the tree representation in Fig. 2 holds, the reduction
of the slot degreehappens only via inter-slot IC, which is implicitly assumed
c−1 r−1
in the term r−1
qi (1 − qi )c−r . On the other hand, D(r) expresses the
probability that an outgoing edge from the slot node is decoded using intraslot IC (see Section III). In other words, inter- and intra-slot IC are in the
asymptotic evaluation separated over DE iterations.

It can be shown that in case of perfect IC, (9) becomes
c

r−1 X
+∞
+∞ G
X
G
D(r)
− GR
R (1 − qi )
qi
pi = 1 − e
(r − 1)! R
c!
r=1
c=0


+∞
r−1
X D(r)
G
G
= 1 − e− R qi
,
(10)
qi
(r
−
1)!
R
r=1
Pr
where D(r) = t=1 D(r, t), see (5). Further, defining zt =
(1 + b? )t , (10) becomes
r−1 X
1
r
+∞ 
X
e− B̄ (zt −1)
G
− GR qi
pi = 1 − e
qi
(r− t+1
R
2 )
t=1 (r − t)!zt
r=1
+∞ G r
+∞ G t−1
X
X
− B̄1 (zt −1)
− GR qi
R qi
R qi
e
=1−e
( t−1
)
r!ztr
2
r=0
t=1 zt


Gq
+∞ G t−1
X
−(zt −1) B̄1 + Rz i
t
R qi
=1−
e
=: fs (qi ) . (11)
( t−1
2 )
t=1 zt
A DE recursion is obtained combining (6) with (11), consisting of one recursion for qi and one for pi . In the former
case, the recursion assumes the form qi = (fb ◦ fs )(qi−1 ) for
i ≥ 1, with initial value q0 = 1. In the latter case, it assumes
the form pi = (fs ◦ fb )(pi−1 ) for i ≥ 1, with initial value
p0 = fs (1). Note that the DE recursion for pi allows expressing
the asymptotic PLR of an IRSA scheme in a very simple way.
More specifically, let p∞ (G, {Λd } , B̄, b? ) = limi→∞ pi be the
limit of the DE recursion, where we have explicitly indicated
that the limit depends on the system load, on the burst node degree distribution, on the average SNR, and
 on the threshold for
d
successful intra-slot decoding. Since p∞ (G, {Λd } , B̄, b? )
represents the probability that a user packet associated with a
burst node of degree d is not successfully received at the end
of the decoding process, the asymptotic PLR is given by
?

PLR(G, {Λd } , B̄, b ) =

dX
max
d=2


d
Λd p∞ (G, {Λd } , B̄, b? ) .

Next, we introduce the concept of asymptotic decoding
threshold for an IRSA scheme over the considered block fading channel model and under the decoding algorithm described
in Section II-D. Let PLR be a target PLR. Then, the asymptotic
decoding threshold, denoted by G? = G? ({Λd } , B̄, b? , PLR),
is defined as the supremum system load value for which the
target PLR is achieved in the asymptotic setting:
G? = sup{G : PLR(G, {Λd } , B̄, b? ) < PLR}.
G≥0

V. N UMERICAL R ESULTS
Table I shows some degree distributions designed combining
the DE analysis developed in Section IV with the differential
evolution optimization algorithm proposed in [15]. For each
design we set PLR = 10−2 , B̄ = 20 dB, and b? = 3 dB,

TABLE I
O PTIMIZED USER NODE DEGREE DISTRIBUTION AND CORRESPONDING
THRESHOLD G? FOR PLR = 10−2 .

d̄

Distribution Λ(x)

G?

4
3

Λ1 (x) = 0.59x2 + 0.27x3 + 0.02x5 + 0.12x16
Λ2 (x) = 0.61x2 + 0.25x3 + 0.03x6 + 0.02x7 +
0.07x8 + 0.02x10
Λ3 (x) = 0.66x2 + 0.16x3 + 0.18x4
Λ4 (x) = 0.65x2 + 0.33x3 + 0.02x4
Λ5 (x) = 0.49x2 + 0.25x3 + 0.01x4 + 0.03x5 +
0.13x6 + 0.01x13 + 0.02x14 + 0.06x16

1.863
1.820

2.5
2.25
4

1.703
1.644
1.734

1.8
1.6
1.4

Throughput T

Combining (8) and the expression for the edge-oriented slotnode degree distribution (see Section II-C) into (7) yields
∞  c−1 X
c
X
G
D(r) r−1
− GR
pi = 1−e
qi (1−qi )c−r . (9)
R
(r
−
1)!
c=1
r=1

1.2
1
Λ5 (x),
Λ4 (x),
Λ3 (x),
Λ2 (x),
Λ1 (x),
Λ1 (x),
Λ1 (x),
Λ1 (x),

0.8
0.6
0.4
0.2
0

1

200 slots
200 slots
200 slots
200 slots
200 slots
500 slots
1000 slots
10000 slots

1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9
Channel load G

2

Fig. 3. Throughput values achieved by the burst node distributions in Table I,
versus the channel load. Various frame sizes n, B̄ = 20 dB, b? = 3 dB.

and we constrained the optimization algorithm to find the
distribution {Λd } with the largest threshold G? subject to a
given average degree6 d̄ and maximum degree dmax = 16.
For all chosen average degrees, the G? threshold of the optimized distribution largely exceeds the value 1 [packet/slot],
the theoretical limit under a collision channel model. In
general, the higher the average degree d̄, the larger is the
load threshold G? . However, as d̄ increases, more complex
burst node distributions are obtained. For instance, under a
d̄ = 4 constraint, the maximum degree is dmax = 16 (i.e.,
a user may transmit up to 16 copies of its packet); when
reducing d̄, the optimization converges to degree distributions
with a lower maximum degree and degree-2 nodes become
increasingly dominant.
To assess the effectiveness of the proposed design approach,
tailored to the block fading channel with capture, we optimized
a distribution Λ5 (x) using the DE recursion over the collision
channel [3] and again constraining the optimization to d̄ = 4
and dmax = 16. As from Table I, due to the mismatched
channel model, a 7% loss in terms of G? threshold is observed
w.r.t. the distribution Λ1 (x) that fulfills the same constraints
but was obtained with the DE developed in this paper.
We tested the optimized distributions performance through
Monte Carlo simulations for finite frame lengths, setting
n = 200 (unless otherwise stated), B̄ = 20 dB, b? = 3
6 A constraint on the average degree d̄ can be turned into a constraint on
the rate R as there is a direct relation between the two; see also equation (1).

Packet loss rate PLR

100

10−1

Λ5 (x),
Λ4 (x),
Λ3 (x),
Λ2 (x),
Λ1 (x),
Λ1 (x),
Λ1 (x),
Λ1 (x),

200 slots
200 slots
200 slots
200 slots
200 slots
500 slots
1000 slots
10000 slots

10−2

10−3

10−4 1

1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9
Channel load G

2

Fig. 4. PLR values achieved by the burst node distributions in Table I, versus
the channel load. Various frame sizes n, B̄ = 20 dB, b? = 3 dB.

dB, and the maximum number of IC iterations to 20. Fig. 3
illustrates the throughput T, defined as the average number
of successfully decoded packets per slot, versus the channel
load. For relatively short frames of n = 200, all distributions
exhibit peak throughputs exceeding 1 [packet/slot]. The distribution Λ2 (x) is the one achieving the highest throughput
of 1.52 [packet/slot] although Λ1 (x) is the distribution with
the highest threshold G? . It is important to recall that, the
threshold is computed for a target PLR of PLR = 10−2 while
considering finite frame lengths, the threshold effect on the
PLR tends to vanish and a more graceful degradation of the
PLR curve as the channel load increases is expected. Moreover, as there are user nodes transmitting as high as 16 replicas,
the distribution Λ1 (x) is more penalized for short frame sizes
w.r.t. to Λ2 (x) where at most 10 replicas per user node are
sent.7 This effect, coupled with the fact that the threshold G? of
Λ1 (x) is only slightly better than the one of Λ2 (x), explains
the peak throughput behavior. To investigate the benefit of
larger frames, we selected Λ1 (x) and we increased the frame
size up to 10000 slots. As expected, the peak throughput is
greatly improved from 1.49 to 1.79 [packet/slot], i.e., 20% of
gain. The PLR performance is illustrated in Fig. 4. Coherently
with the optimization results, the Λ1 (x) distribution achieves
PLR = 10−2 for values of the channel load slightly larger than
the ones required by Λ2 (x). Indeed, the steeper PLR curve of
Λ1 (x) is the reason for the slightly larger peak throughput of
Λ2 (x) observed in Fig. 3. Finally, as expected, an increase of
the number of slots per frame yields an increase of the channel
load for which the target PLR is achieved.
VI. C ONCLUSIONS
The asymptotic analysis of IRSA access schemes, assuming
both a Rayleigh block fading channel and capture effect, was
presented in the paper. We derived the decoding probability
of a burst replica in presence of intra-slot IC. The DE
analysis is modified considering the Rayleigh block fading
channel model, and the user/slot nodes updates of the iterative
7 Results for frame size of 500 slots, not presented in the figures, show that
the peak throughput for Λ1 (x) is 1.61 while for Λ2 (x) is 1.60.

procedure are explicitly derived. Due to the presence of fading,
the optimization procedure target has been modified as well.
The distribution able to achieve the highest channel load
value without exceeding a properly defined PLR target is
selected. We designed some degree distributions with different
values of average degree. Remarkably, all of them present a
load threshold that guarantees PLR below 10−2 for values
well above 1 [packet/slot]. The best distribution exceeds
1.8 [packet/slot]. The derived distributions were shown to
perform well also for finite frame durations. In a frame with
200 slots, the peak throughput exceeds 1.5 [packet/slot] and
up to 1.45 [packet/slot] the PLR remains below 10−2 .
ACKNOWLEDGEMENT
The authors would like to thank Dr. Gianluigi Liva (German
Aerospace Center) and Prof. Marco Chiani (University of
Bologna)for fruitful discussions. The work of Č. Stefanović
was supported by the Danish Council for Independent Research under grant no. DFF-4005-00281. The work of E.
Paolini was supported by ESA/ESTEC under Contract no.
4000118331/16/UK/ND “SCAT”.
R EFERENCES
[1] H. Okada, Y. Igarashi, and Y. Nakanishi, “Analysis and Application
of Framed ALOHA Channel in Satellite Packet Switching Networks –
FADRA Method,” Electron. and Commun. in Japan, vol. 60, pp. 60–72,
Aug. 1977.
[2] E. Casini, R. De Gaudenzi, and O. del Rio Herrero, “Contention
Resolution Diversity Slotted ALOHA (CRDSA): An Enhanced Random
Access Scheme for Satellite Access Packet Networks,” IEEE Trans.
Wireless Commun., vol. 6, no. 4, pp. 1408–1419, Apr. 2007.
[3] G. Liva, “Graph-Based Analysis and Optimization of Contention Resolution Diversity Slotted ALOHA,” IEEE Trans. Commun., vol. 59, no. 2,
pp. 477–487, Feb. 2011.
[4] E. Paolini, C. Stefanovic, G. Liva, and P. Popovski, “Coded Random
Access: How Coding Theory Helps to Build Random Access Protocols,”
IEEE Commun. Mag., vol. 53, no. 6, pp. 144–150, Jun. 2015.
[5] L. G. Roberts, “Aloha Packet System with and without Slots and
Capture,” SIGCOMM Comput. Commun. Rev., vol. 5, no. 2, pp. 28–42,
Apr. 1975.
[6] C. Namislo, “Analysis of Mobile Radio Slotted ALOHA Networks,”
IEEE J. Sel. Areas Commun., vol. 2, no. 4, pp. 583–588, Jul. 1984.
[7] J. E. Wieselthier, A. Ephremides, and L. A. Michaels, “An Exact
Analysis and Performance Evaluation of Framed ALOHA with Capture,”
IEEE Trans. Commun., vol. 37, no. 2, pp. 125–137, Feb. 1989.
[8] M. Zorzi and R. R. Rao, “Capture and Retransmission Control in Mobile
Radio,” IEEE J. Sel. Areas Commun., vol. 2, no. 4, pp. 1289–1298, Oct.
1994.
[9] M. Zorzi, “Capture Probabilities in Random-Access Mobile Communications in the Presence of Rician Fading,” IEEE Trans. Veh. Technol.,
vol. 46, no. 1, pp. 96–101, Feb. 1997.
[10] A. Zanella and M. Zorzi, “Theoretical Analysis of the Capture Probability in Wireless Systems with Multiple Packet Reception Capabilities,”
IEEE Trans. Commun., vol. 60, no. 4, pp. 1058–1071, Apr. 2012.
[11] G. D. Nguyen, A. Ephremides, and J. E. Wieselthier, “On Capture in
Random-Access Systems,” in Proc. of IEEE ISIT 2006, Seattle, WA,
USA, Jul. 2006.
[12] C. Stefanovic, M. Momoda, and P. Popovski, “Exploiting Capture Effect
in Frameless ALOHA for Massive Wireless Random Access,” in Proc.
of IEEE WCNC 2014, Istanbul, Turkey, May 2014.
[13] C. Stefanovic, P. Popovski, and D. Vukobratovic, “Frameless ALOHA
Protocol for Wireless Networks,” IEEE Commun. Lett., vol. 16, no. 12,
pp. 2087–2090, Oct. 2012.
[14] T. Richardson and R. Urbanke, Modern Coding Theory. Cambridge
University Press, Cambridge, UK, 2007.
[15] R. Storn and K. Price, “Differential Evolution - A Simple and Efficient
Heuristic for global Optimization over Continuous Spaces,” Journal of
Global Optimization, vol. 11, no. 4, pp. 341–359, Dec. 1997.

