Iman Hmedoush
email: iman.hmedoush@inria.fr

Cédric Adjih

Paul Mühlethaler

Vinod Kumar

On the Performance of Irregular Repetition Slotted Aloha with Multiple Packet Reception

Keywords: modern random access, Irregular Repetition Slotted Aloha, IRSA, density evolution, multi-packet reception, successive interference cancellation

A modern method of random access for packet networks, named "Irregular Repetition Slotted Aloha (IRSA)", had been proposed: it is based repeating transmitted packets, and on the use of successive interference cancellation at the receiver. In classical idealized settings of slotted random access protocols (where slotted ALOHA achieves 1/e), it has been shown that IRSA could asymptotically achieve the maximal throughput of 1 packet per slot. Additionally, IRSA had previously been studied for many different variants and settings, including the case where the receiver is equipped with "multiple-packet reception" (MPR) capability. In this article, we extensively revisit the case of IRSA with MPR. First, one of our major results is the proof that K-IRSA cannot reach the natural bound of throughput, and we prove a new, lower bound for its performance. Second, we give a simple expression for its excellent loss rate at lower loads. Third, we show how to formulate the search for the appropriate parameters of IRSA as an optimization problem, and how to solve it efficiently. By doing that for a comprehensive set of parameters, and by providing this work with simulations, we give numerical results that shed light on the performance of IRSA with MPR.

I. INTRODUCTION

The Internet of Things is expected to provide communication capabilities to billions of objects. One of the main challenges of IoT cellular wireless networks is to ensure efficient connectivity for all devices in the specific scenarios of dense networks deployed in order to satisfy the requirements of massive numbers of nodes with irregular traffic demands. The traditional paradigm of resource reservation in cellular networks becomes inefficient when the traffic is infrequent, unpredictable and limited to a few packets per node.

A recent family of modern random access protocols [START_REF] Paolini | Coded Random Access: Applying Codes on Graphs to Design Random Access Protocols[END_REF], frequently referred to as the Coded Slotted Aloha (CSA) family, is a good candidate to address this issue. The main underlying principle of these protocols is to make each terminal physically send multiple copies of the same MAC packet (also called replicas), with an identical preamble and payload information bits. The payload contains signaling information concerning the temporal positions of the corresponding replicas of each packet. This enables an iterative decoding process whereby Successive Interference Cancellation (SIC) is applied to resolve collisions between different packets by physically This work was partly partly supported by the Inria-Nokia Bell Labs common labs under research action "Network Information Theory".

removing the signal of a successfully decoded packet, at the position of its replicas. This operating mode has been introduced by Contention Resolution Diversity Slotted Aloha (CRDSA) [START_REF] Casini | Contention resolution diversity slotted aloha (crdsa): An enhanced random access schemefor satellite access packet networks[END_REF] where each packet is sent twice, and in Irregular Repetition Slotted Aloha (IRSA) in [START_REF] Liva | Graph-based analysis and optimization of contention resolution diversity slotted aloha[END_REF] where the number of repetitions can be different for different users (i.e. on a probability distribution function). In particular, some recent publications [START_REF] Ghanbarinejad | Irregular repetition slotted aloha with multiuser detection[END_REF][START_REF] Lázaro | Finite-length analysis of frameless aloha with multi-user detection[END_REF][START_REF] Stefanović | Asymptotic performance of coded slotted aloha with multipacket reception[END_REF][START_REF] Baiocchi | Analysis of pure and slotted aloha with multi-packet reception and variable packet size[END_REF] have focused on the variants where the receiver has the capability of simultaneously decoding more than one packet from multiple concurrent transmissions, denoted Multiple Packet Reception [START_REF] Lu | A Survey on Multipacket Reception for Wireless Random Access Networks[END_REF] (MPR). The ability to decode K or fewer packets simultaneously is usually denoted K-MPR, a derivative of the collision channel. In this article, we focus on IRSA with K-MPR. It is denoted K-IRSA, and supposes that the transmissions occur in fixed slots (as for slotted ALOHA). Considering the throughput, under this collision model, K-IRSA can recover at most K packets per slot. Classical IRSA, which is 1-IRSA, asymptotically reaches this performance [START_REF] Krishna | Iterative collision resolution for slotted aloha: An optimal uncoordinated transmission policy[END_REF]. Hence a natural question arises: can K-IRSA reach the bound of K? Since K-MPR can typically be obtained at a cost of a decrease in modulation rate by a factor K, this is the essential design information for IRSA.

Previous studies have explored the question, [START_REF] Ghanbarinejad | Irregular repetition slotted aloha with multiuser detection[END_REF][START_REF] Stefanović | Asymptotic performance of coded slotted aloha with multipacket reception[END_REF], by describing a non-asymptotic bound for K-IRSA, and numerically exhibiting some specific modification of CSA. These studies show results close to their bound for K = 3 and 4, but they are not able to fully answer the bound reaching question for K-IRSA. The main contribution of this article is to prove that classical K-IRSA cannot actually reach this bound of K packet per slot, even in the asymptotic case. A new bound is provided. Furthermore, after formulating an efficient search for optimal K-IRSA parameters, we show numerically how it can be approached. We also provide a simple asymptotic expression for the loss rate at low loads (the error floor), evidencing that increasing K dramatically decreases it.

The paper is organized as follows: Section II introduces the concepts of IRSA, K-MPR, notations, models, and related work. Then before theoretical results, Section III shows how to compute optimal parameters (degree distributions) efficiently, and show properties of optimal solutions, necessary to understand the following section. Section IV describes the derivation of our new bound on the performance of K-MPR with IRSA, and also our error floor approximation. The numerical results are in Section V. Section VI concludes.

II. SYSTEM OVERVIEW AND RELATED WORK

A. IRSA main principles

We adopt a system model commonly found in the IRSA literature. An IoT network with M user nodes contending to send their packets to a single base station through a connectionless random access scheme is considered. The time is divided into slots of equal length, and successive slots are regrouped in fixed size frames of N slots. The load is defined by G = M N and it measures the average number of users per slot. We focus on one frame, and assume that each user has exactly one data packet to transmit in the frame.

IRSA works as follows. Each user sends his packet l times within the same MAC frame, where the repetition rate of each user is selected randomly from a probability distribution Λ defined by n probabilities : (Λ i ) i=2,...,n . For i = 2, . . . n, Λ i is the probability that the packet is repeated i times. At the end of the frame, the receiver attempts to decode the packets: each time that a packet is successfully received, e.g. only one transmission is present on the slot (or fewer than K with K-MPR), IRSA will use SIC to remove the physical copy of this packet on all other slots. This process is iterative, as new decoding opportunities can appear. In the example of Fig 1,4 users are transmitting in a frame of 4 slots; the packet P K 2 can be recovered on the slot 4. When its copy is physically subtracted from slot 2 (and slot 1), the P K 4 can be recovered, and removed from slot 3, and then P K 3 is recovered, and so on. Another example with 2-IRSA is in Appendix A.

B. IRSA decoding process modeling

Liva [START_REF] Liva | Graph-based analysis and optimization of contention resolution diversity slotted aloha[END_REF] introduces in parallel with the decoding of LDPC codes (on a binary erasure channel [START_REF] Paolini | Coded Random Access: Applying Codes on Graphs to Design Random Access Protocols[END_REF]) the way to analyze the decoding process of IRSA as follows: as for codes, one can construct a Tanner graph, that is, a bipartite graph G(B, S, E), where B is the set of burst nodes (corresponding to users), S, is the set of sum nodes (corresponding to slots) and E is the set of edges. An edge connects a burst node b i ∈ B and to a sum node s j ∈ S, if and only if a replica of the i-th burst is transmitted in the j-th slot. The number of edges connected to a node is referred to as the node degree. Fig 2 shows an example of a graph representation of the IC process in Fig. 1. The circles correspond to the bursts (and are denoted as burst nodes), while the rectangles correspond to the slots (slot nodes). The IC process starts by searching for the slots where only one replica was sent (degree-1 slots) and decoding these replicas. If the burst that is transmitted on a certain slot is revealed, the corresponding edge is labeled by '1', otherwise, it is labeled by '0'. The contribution of each Fig. 2: Equivalent Tanner graph representation of Fig. 1 revealed burst is removed from the other slots where a replica of this burst was transmitted through SIC. Thus, we can say that the first iteration has ended. After the first iteration, new clean bursts can be detected and revealed. The IC process can be blocked if in one iteration, no clean bursts could be detected. The analysis of IRSA assumes that we can always decode clean bursts where no collision has happened and then, we can remove their contributions in other slots.

C. Density Evolution

Density evolution is the probabilistic analysis of the decoding process, given the system parameters Λ, M, N, K: can we expect to recover all packets, or how many of them?

For later mathematical convenience, one first introduces the concept of burst-and slot-perspective degree distributions,

Λ(x) Λ x and Ψ(x) Ψ x
where Λ l , is the probability that a user will send replicas of his packet, and Ψ is the probability that a slot has collided packets. Λ (1) = 1 lΛ l is the average burst repetition rate.

We define the rate R as R 1 Λ (1) . Notice, in IRSA, the "rate" R is loosely connected to throughput, since with SIC, removed replicas do not consume slots. The probability that one user sends a packet on a given slot is: Λ (1) N = G RM . Then Ψ follows a binomial distribution Bin(M, 1 RM ). When M → ∞, the distribution Ψ becomes a Poisson distribution with a parameter G RM . The corresponding edge distributions from the burst and slot perspective are respectively:

λ(x) λ x -1 = Λ (x) Λ (1) and ρ(x) ρ x -1 = Ψ (x) Ψ (1)
When M → ∞, we have ρ(x) → e -G R (1-x) . Still following [START_REF] Liva | Graph-based analysis and optimization of contention resolution diversity slotted aloha[END_REF], the decoding process is iterative, and is modelled probabilistically, tracking variables representing probabilities that information (slot content, bursts) is unknown over iterations. Each edge in Fig. 2 connects one slot node, and one burst node. Let p be the probability that a random selected edge is connected to a burst node that is not revealed yet and q is the probability that a random selected edge is connected to an unknown slot node.

We can decode the burst of a user, if a replica of this packet has been decoded at least once on any other slot. Hence, q = p -1 . Similarly, in classical IRSA, we can remove the collision on the last edge which connects to a slot node of degree , if we have already removed the -1 contributions of the other collided packets on the same slot. Hence, (1-p) = (1-q) -1 .

Averaging over all possible degrees, we write p = λ q -1 , similarly for p and noting their values q i (resp. p i ) at iteration i, we obtain equations of the form:

q i = f b (p i-1 ) and p i = f s (q i ), thus p i = f s (f b (p i-1 )) (1)
with, functions corresponding to [START_REF] Liva | Graph-based analysis and optimization of contention resolution diversity slotted aloha[END_REF], for classical IRSA:

f b (p) = λ(p) and f s (q) = 1 -ρ(1 -q) (2) when M → ∞: f s (q) → F ( G R q) with F (x) 1 -e -x (3)
From the decoding point of view, we will be able to decode if the probabilities p i are decreasing towards zero which requires that

p i < p i-1 . When M → ∞, p i = F ( G R λ(p i-1
)), thus this is obtained when:

F ( G R λ(x)) < x for all x ∈]0, 1[ (4)
Given the parameters (Λ, G, . . . ), one can simply check the curve, e.g. equation ( 4), to determine if and where the decoding process will stop (asymptotically for M → ∞).

Following [START_REF] Liva | Graph-based analysis and optimization of contention resolution diversity slotted aloha[END_REF], one main property is that: given Λ (and here K), there exists a load threshold G * , such that, when the frame size converge towards infinity (M → ∞), for any load G < G * , all the packets are decoded with vanishing error probability. G * depends on the choice of the distribution Λ. Finding the Λ with the largest G * is our prime interest.

D. IRSA and K-IRSA (thoughput): related work and results

Different variants of IRSA and CSA have been studied, often by establishing new functions f b (q) and f s (p) (and F (x)) for (4).

[4] analyzed IRSA with K-MPR for the case of an infinite user population. They show that providing the receiver with multi-user detection capability allows larger load in the systems with low number of slots per frame, and also that the density evolution can be written with functions corresponding to:

f b (p) = λ(p) and f s (q) = 1 - K-1 k=0 ρ (k) (1 -q) k! q k (5)
where

ρ (k) (x)is the k-th derivative of ρ(x) f s (q) → F K ( G R q) with F K (x) 1 -e -x K-1 k=0 x k k! (6) when M → ∞
A major question is the performance of IRSA and K-IRSA: it is obvious that K-IRSA can at most recover K different users per slots, which thus yields an upper bound of the load threshold of G * /K ≤ 1. But: what is the maximum G * and what is the distribution Λ that can reach it ? [START_REF] Krishna | Iterative collision resolution for slotted aloha: An optimal uncoordinated transmission policy[END_REF] proved that for K = 1 (IRSA), the load threshold is asymptotically G * → 1 for a sequence of (truncated) soliton distributions. In [START_REF] Ghanbarinejad | Irregular repetition slotted aloha with multiuser detection[END_REF], some distributions were experimented with various values of K, and the load threshold was found to be G * /K between 0.8 and 0.96 (their Figure 4).

[6] developed a converse bound on the asymptotic load threshold of Coded Slotted ALOHA (CSA) schemes with K-MPR, that also applies to K-IRSA. They give examples close to the bound but this was not obtained for plain K-IRSA itself, but a variant using spatially-coupled (SC) CSA [START_REF] Liva | Spatiallycoupled random access on graphs[END_REF], with a more structured slot selection.

Their bound [6, (17)] in [START_REF] Baiocchi | Analysis of pure and slotted aloha with multi-packet reception and variable packet size[END_REF] yields G * /K → 1 when R → 0:

G * K ≤ 1 - 1 K e -G * R K-1 k=0 K -k k! G * R k (7)
SC-CSA has interesting performance, and variants such as Irregular Repetition Spatially-Coupled slotted ALOHA (IRSC-SA) have also been proposed and analyzed recently in [START_REF] Yu | Analysis of irregular repetition spatially-coupled slotted aloha[END_REF]. But all require "super-frames" (i.e. frames of frames), thus typically require several orders of magnitude more slots, hence our continued focus on K-IRSA 1 .

E. IRSA and K-IRSA (error floor): related work and results

In IRSA and K-IRSA, the decoding process is still subject to failure due to stopping sets in a similar way to LDPC codes [START_REF] Liva | Graph-based analysis and optimization of contention resolution diversity slotted aloha[END_REF], due to the presence of cycles in the Tanner graph (see Fig. 4). Stopping sets have a negative impact on the decoder performance and lead to an error floor of the decoding failure probability. Previous works including [START_REF] Lázaro | Finite-length analysis of frameless aloha with multi-user detection[END_REF] present a finite length analysis of frameless ALOHA with K-IRSA in the error floor region. Their recursive approach obtains the decoder state probabilities, allowing to compute numerically the Packet Error Rate (PER), also denoted Packet Loss Rate (PLR). Another analysis of the error floor due to stopping sets of irregular coded slotted ALOHA (CSA) for finite frame lengths over the packet erasure channel based on combinatorics was presented in [START_REF] Ivanov | Error floor analysis of coded slotted aloha over packet erasure channels[END_REF], among others.

III. FINDING OPTIMAL DISTRIBUTIONS

A. Objectives and Notations

In this section, we provide a method that finds one distribution Λ(x) (e.g., to find λ(x) first) with the highest load threshold G * when the number of coefficients is limited by n (e.g. Λ i = 0, ∀i > n). We denote it by L K n , and the load threshold by G K n . Notice that n is also the maximum number of replicas sent by a user.

B. Formulating an Optimization Problem

We start from condition (4) on λ(x), G, and R and apply it to the iteration functions for K-IRSA [START_REF] Stefanović | Asymptotic performance of coded slotted aloha with multipacket reception[END_REF]. We obtain the following inequality for the case where K = 2: (c) For 2-MPR, and for different n: difference between h 2 (x) and λ(x

F 2 ( G R λ(x)) < x =⇒ 1 -e -G R λ(x) (1 + G R λ(x)) < x (
) of L 3 n : h 2 (x) -G R λ(x)
Fig. 3: h 2 and h 3 compared to rescaled λ(x)

Taking the limit case of equality, we are able to find this closed formula for the function that satisfies the following equality:

λ(x) = R G h 2 (x) with h 2 (x) = -W -1 x -1 e -1 (9)
where h 2 (x) is expressed in terms of one of the branches of the Lambert W function. The Lambert function [START_REF] Corless | On the LambertW function[END_REF] is the inverse of the function w → we w = z , thus the function w(z)e w(z) = z , is a multivalued function defined in general for z complex and assuming complex values of W (z). For z ∈ [ -1 e , 0[, there are two real branches, one of which, satisfying

W (z) ≤ -1, is denoted W -1 (z)
, which is used here. It seems that taking the power series of h 2 (x), and by truncating it, we should be able to find functions λ(x) that correspond to (near) optimal distributions. However h 2 (x) does not have a proper power series as its derivative in 0 is infinite (and behaves like α √ x near 0 + ). But as it satisfies the equality, the function h 2 (x) still provides a bound for any Λ distribution. Indeed, any G, λ satisfying (8) must satisfy λ(x) < R G h 2 (x) equivalently. This can be generalized for any K:

λ(x) < R G h K (x) for x ∈]0, 1[ with h K (x) F -1 K (x) (10)
Notice that F -1 K cannot be written in closed form for K > 2 (or would require "Generalized Lambert functions"), and has the derivative

dF -1 K dx (x) → +∞ when x → 0 + for K ≥ 2. C. Finding L K
n through its optimal edge distribution λ(x) We start by fixing n, and search for L K n through its edge distribution λ(x). λ(x) verifies the bound formulated in [START_REF] Liva | Spatiallycoupled random access on graphs[END_REF] and provides the largest load threshold G * : it is an optimization problem.

The conditions on λ(x) can be derived from the following:

• The condition λ(1) = 1 (because it is a probability distribution) • The property that R is actually expressed in terms of [START_REF] Liva | Spatiallycoupled random access on graphs[END_REF], multiplied by G This yields the following optimization problem on the variables G, λ 2 , λ 3 . . . λ n (in IRSA and K-IRSA:

(λ i ) i as: R = R(λ) = 1 2 λ 2 + 1 3 λ 3 + . . . + 1 n λ n • The left inequality in
λ 1 = 0): maximize (λi) G subject to 0 ≤ λ i ≤ 1 ∀i i=n i=2 λ i = 1 G i=n i=2 λ i x i-1 < ( i=n i=2 λ i i )h K (x), ∀x ∈]0, 1[ (11)
Now, by using a technique introduced for LDPC codes, the last inequality of ( 11) can be transformed into multiple inequalities by taking a finite set of values for x. Furthermore, when G is fixed, this is a linear program in the variables (λ i ) i , and thus can be efficiently solved. Hence, our efficient technique is to perform a bisection on G: once G is fixed, we solve the linear program [START_REF] Yu | Analysis of irregular repetition spatially-coupled slotted aloha[END_REF] with arbitrary objective function (such as maximize R(λ)), finding whether the constraints can be satisfied, and if so, finding one λ. The largest G admissible through bisection yields L K n and G K n .

D. Numerical Results of Optimal Distributions

In this section, we explore the behavior of the optimal L K n numerically. By solving the OP which was presented in the previous section, we obtain optimal edge degree distributions for different number of coefficients and different K.

The load threshold G K n of these distributions will be analyzed later. But because the distributions are obtained through an optimization program with constraints, most insight can be obtained by considering how tightly the solutions meet these constraints. Ultimately, notice that the primary constraint is derived from the inequality (10) that is λ(x) < R G h K (x). To check for tightness, we equivalently scale (normalize) the λ(x) from numerically computed optimal solutions L K n , as G R ×λ(x) and compare them to h K (x), in Fig. 3.

It can be seen from Fig. 3a and Fig. 3b that as we increase the number of coefficients, we get closer to the bound. But one can notice that, there is always a gap between the bound and the scaled λ(x) of optimal distributions, increasing with K (K = 3 vs K = 2).

K n Distribution Λ(x)=L K n G=G K n 1 4
To confirm this effect, Fig. 3c directly shows the differences between each such optimal edge distribution and the theoretical bound: h K (x) -G R λ(x) for 2-MPR; we can see that in the range x ∈ [0.6, 1], scaled distributions are getting closer to h K (x) as n increases. However this is not the case in [0, 0.6], and they seem to converge quickly to a curve above 0 (e.g. for n > 3).

IV. PERFORMANCE BOUND A. A New Bound on the Load Threshold K-IRSA

The empirical results of the previous section made clear (through Fig. 3c) that there always seems to always exist a gap between any scaled λ(x) and the function h K it should approach, for values x until around x = 0.5. One question is whether the existence of this gap can be proven, and whether it always exists for any Λ, for any K-MPR case. This may answer the proposed question in our introduction: can K-IRSA reach the bound of G * = K?

The two following theorems of this section provide answers.

Theorem 1. There exist a value x K , and a function θ K (x), such that for any x ∈]0, x K [ and λ, R, G satisfying the necessary condition [START_REF] Liva | Spatiallycoupled random access on graphs[END_REF]: the gap between the bound, h K (x) and any normalized edge degree distribution, G R λ(x) verifies:

h K (x) -G R λ(x) > θ K (x) > 0 Proof. Consider the point M (x K , y K = h K (x K )) on the curve h K (x)
such that the tangent of h K in this point passes through the origin O(0, 0).

The function h K (x) is always above the tangent up to this point M. This can be analyzed by introducing the function which computes the gap between h K and that specific tangent in M:

θ K (x) h K (x) -h K (x K )x ( 12
)
This function will pass in zero for the first time in M, i.e:

θ K (x K ) h K (x K ) -h K (x K )x K = 0
By looking at this function in O(0, 0), we can deduce that h K (x) is above the tangent in zero, since: h K (x) → ∞ for x → 0 + . By combining the two facts: the function θ K (x) is positive in zero and zero in M , then, it can not be negative in ]0, x K [, since it would pass through zero, which is in a contradiction with the fact that it passes through zero for the first time in M . Then θ K (x) > 0 for 0 < x < x K . Consider any valid edge degree distribution λ(x) (and associated G < G * , R). λ is always a convex function (as a polynomial with only positive coefficients). Thus, in the range 0 < x < x K , λ(x) is below the line passing through points (0, 0) to (x K , λ(x K )), which is the tangent passing through points (0, 0) to (x K , h K (x K )). Now, considering that: our bound h K (x) is always above its tangent in M , and any λ(x) is below the tangent passing in O(0, 0) and in M , the gap between h K (x) and λ(x) must always exist. This proves the theorem.

The theorem also explicitly gives one such function θ K (x) in [START_REF] Ivanov | Error floor analysis of coded slotted aloha over packet erasure channels[END_REF], and the method to compute x K , e.g. x K satisfies:

h K (x K ) = h K (x K )x K ( 13
)
Notice that in the general case K > 2, h K has no closed form, but using the definition

h K = F -1 K , one can write h K (x) = 1/F k (h K (x)
) and find x K . For K = 2, x 2 is the solution of the following equation (which yields x 2 = 0.535...):

(x 2 -1 + e W-1( x 2 -1 e )+1 )(W -1 ( x 2 -1 e ) + 1) -x 2 = 0 (14)
One of our main result is then the following theorem:

Theorem 2. With K-IRSA, and for K > 0, the maximum load threshold verifies

G * /K ≤ 1 -∆ K where ∆ K > 0
Proof. Consider any λ(x) and its associated load threshold G * and R. For any G < G * , using a similar technique to [START_REF] Stefanović | Asymptotic performance of coded slotted aloha with multipacket reception[END_REF], we compute areas: we define the "gap" as the area between h K and G R λ(x) as in Fig. 3c (and Fig. 3a).

A K = x=1 x=0 (h K (x) - G R λ(x))dx (15)
First

x=1 x=0 G R λ(x)dx = G R 1 Λ (1) Λ(x)dx 1 0 = GΛ(1) = G
Then for K = 2, we can directly compute

1 0 h 2 (x)dx = - 1 0 (W -1 ( x-1
e )+1)dx = 2, while for all K, we can compute the integral considering h K = F -1 K and computing the integral area from the symmetric graph of F K instead.

1 0 h K (x)dx = ∞ 0 (1 -F K (y))dy = ∞ 0 e -y K-1 i=0 y i i! dy = -e -y ( K-1 i=0 (K -i)y i i! ) ∞ 0 = K Hence A K = K -G.
On the other hand, the inequality from theorem 1, implies:

A K ≥ x=x K x=0 (h K (x) -G R λ(x))dx > x K 0 θ K (x)dx
Combining the two, we obtain:

G/K < 1 -∆ K with ∆ K 1 K x K 0 θ K (x)dx (16)
true for any λ and valid G, which proves the theorem.

Theorem 1 and Theorem 2 provide a way to compute ∆ K . First compute x K through equation ( 13), then ∆ K with (16) using the definition of θ K in (12) simplified with [START_REF] Corless | On the LambertW function[END_REF]. For instance for K = 2, we obtain 2∆ 2 = 0.0553.., hence a bound G * ≤ 1.9448

B. Error Floor Approximation

In this section, we propose approximations of the error floor of K-IRSA. Compared to [START_REF] Lázaro | Finite-length analysis of frameless aloha with multi-user detection[END_REF], we stay in the framed version of K-IRSA, and obtain closed formulas, and compared to [START_REF] Ivanov | Error floor analysis of coded slotted aloha over packet erasure channels[END_REF], we consider K-IRSA (not just IRSA), and our expressions can be simpler through further "urn and ball" approximations [START_REF] Johnson | Urns Models and Their Applications: An Approach To Modern Discret Probability Theory[END_REF].

We start from their observations: in (K-)IRSA, at low channel loads (denoted by g), a most probable stopping set occurs when at least K + 1, degree-2 users send their packets on the same two slots ( [START_REF] Lázaro | Finite-length analysis of frameless aloha with multi-user detection[END_REF][START_REF] Ivanov | Error floor analysis of coded slotted aloha over packet erasure channels[END_REF] and others). The probability of having such a stopping set is the same as having at least K +1 users in the same "virtual" square in Figure 4.(b), where each square represents the choice of two unordered slots. The total number of all possible choices of two unordered slots for each user (number of squares) is m = N 2 . The problem of user distribution in the squares corresponds to the classic urns and balls problem(s) in the probability literature [START_REF] Johnson | Urns Models and Their Applications: An Approach To Modern Discret Probability Theory[END_REF]. The squares can be seen as urns, and the users can be seen as balls randomly thrown in urns. With M * users, the probability of having m r squares (urns) such that each square contains exactly r users (collisions) is given by [14, pp. 114 -116]:

P r [M r = m r ] = m-mr k=0 (-1) k m r + k m r S mr+k
where

S k = m k M * ! (r!) k (M * -kr)! (m-k) M * -kr m M *
. These expressions are, in general, difficult to evaluate. In the following, we use well-known approximations, considering limiting cases such as m → ∞ and M * → ∞. [14, pp. 315-320] has surveyed results for the approximation of the distribution of M r with r ≥ 2. We use the notation of [START_REF] Johnson | Urns Models and Their Applications: An Approach To Modern Discret Probability Theory[END_REF] but except denoting their λ as , and their M as M * , applied to our problem:

α M * m = 2M * N (N -1)
; a r α r r! e -α and r ma r (17)

In our case, only users transmitting exactly two replicas are considered for stopping sets, so M * ≈ Λ 2 M . And M * → ∞, α → 0 (at fixed load g * = M * /N ) and r → 0 (hence bounded). [14, Table 6.1 p320] has reproduced a summary of asymptotic distributions of M r depending on α and r (quoting Kolchin), and for us, the case is: M r has an asymptotic Poisson distribution with parameter r . Then, the packet loss rate (PLR) of all users is approximated as: n , that are optimal distributions Λ (with max. degree n, which varies on the x-axis); thick horizontal lines represent our bound 1 -∆ K from theorem 1; dotted lines near line y = 1 represent the bound of [START_REF] Stefanović | Asymptotic performance of coded slotted aloha with multipacket reception[END_REF] with the rate R of L K n At low loads, a simpler expression is obtained by considering only the dominant term, e.g., for r = K + 1, u = 1:

PLR ≈ (K + 1) K+1 M e -K+1 = Λ 2 α K K! e -α e -K+1 (19)

V. EXPERIMENTAL RESULTS AND NUMERICAL INSIGHTS

Our first primary focus is the asymptotic performance of K-IRSA on the normalized load threshold G * /K, which is bounded absolutely by 1. Remember that, it is a metric of interest because it represents the limit up to which K-IRSA can be used with vanishing packet losses (when M → ∞), and thus also corresponds to the maximum throughput of K-IRSA as "packet decoded/slot" with vanishing packet losses. To understand the performance, for K = 2, 3, 4, 5, we varied n = 2, . . . 100, the maximum degree of Λ: we computed, as previously, each optimal distribution L K n with the same method as in Section III, its associated load threshold G * and rate R. In Fig. 5, we represent the numerical results of the normalized load G * /K for these distributions L K n as plain lines with points. We also represent the bound of [START_REF] Stefanović | Asymptotic performance of coded slotted aloha with multipacket reception[END_REF] computed from [START_REF] Baiocchi | Analysis of pure and slotted aloha with multi-packet reception and variable packet size[END_REF] as dotted lines (from the rate also in Fig. 5). Finally, we represent our bound: 1 -∆ k , which was computed as in Section IV. It appears as thick horizontal lines in Fig. 5. We are then able to observe that: first, the known bound [START_REF] Baiocchi | Analysis of pure and slotted aloha with multi-packet reception and variable packet size[END_REF] is useful for higher rates as found in CSA for which it was first introduced, here, becomes quickly too loose for the optimal L K n . Indeed the dotted lines representing it are close to 1 for n ≥ 20. Our bound 1 -∆ K is closer to the actual performance G * /K of the optimal distributions L K n , and thus captures well their asymptotic behavior. Finally, one can observe that the performance of K-IRSA gradually decreases as K increases, and moves away from 1, contrary to what could have been previously thought. Computing for large K = 50, we get 1 -∆ 50 = 0.6555.... An open question is whether that new bound is asymptotically reached by L K n ?. Another open question is related to the rate R: G * /K → 1 implied R → 0, but we found that G * /K → 1 for K-IRSA. Fig. 6, shows the evolution of the rate R of L K n with n for different K-MPR cases. Each curve shows the same behavior of decreasing when the number of coefficients is increasing. It is unclear whether the rate R converges towards 0. Still, we conjecture it is the case (based on observing the last inequality of the optimization problem [START_REF] Yu | Analysis of irregular repetition spatially-coupled slotted aloha[END_REF] and the constraints on λ i ).

K = 2 K = 3 K = 4 K = 5
The previous results focused on the performance of K-IRSA in terms of throughput, thus G/K * . Additionally, we implemented a K-IRSA simulator in Python, validated it through density evolution (finding similar curves to the literature such as in [START_REF] Liva | Graph-based analysis and optimization of contention resolution diversity slotted aloha[END_REF]). Then, we have studied the probability for one packet not to be decoded (packet loss rate, PLR). We selected a frame of size M = 100, different values of K, using optimal distributions of degree 11 from Table I

(L 2 11 , L 3 11 , L 4
11 ), and varied the normalized load G/K. The simulation results are in Fig. 7 (with 10, 000 to 640, 000 simulations per point) with also corresponding plots of our approximation (18). First, as one can see, the approximation is very close to the actual performance at low load (should be a lower bound). Further, for all data points of our simulated scenarios, comparing numerically (18) to (19), we observed a relative difference of less than 5%; and we also observed α < 0.0769, and K+1 < 0.0357 (thus e -α > 0.92 and e -K+1 > 0.96).

Then, at lower loads, the PLR itself appears to decrease by one or two orders of magnitude as K increases. Indeed, the event of K + 1 users select the same 3 slots or more has a very small probability to happen at low loads, and that's why we considered only degree-2 users in our PLR analysis. This dramatic decrease of PLR shows that, for reliable communications, K-IRSA with K > 1 is a good choice. Eq. ( 19) helps understanding why: with e -α and e -K+1 close to 1, almost all variation in (19) will come from the other factors. Keeping g fixed, assuming Λ 2 does not vary (too much), we observe: (a) an increase of K by 1 yields a multiplication of the PLR by a factor α K+1 essentially, knowing that α 1; (b) a relative increase of the frame size M by a factor of η (with an identical increase of the number of users), leads to a division of the PLR by a factor ≈ η K . Both facts are notable for design.

Finally, note a different link between the low(er) error floor of K-IRSA with the fact that K-IRSA cannot reach the bound G * /K = 1 (for K > 1): the fact that at low loads K users are unlikely to be undecoded is linked to the fact that f s (q) from ( 5), and as a consequence F K , quickly approaches 0 for q near 0, e.g. O(x 2 ). In turn, it results in an infinite derivative in 0 + for h K = F -1 K . The infinite derivative causes concavity and the impossibility to approach it with a polynomial with positive coefficients and a bound G * /K < 1. Thus this presents a tradeoff between throughput and reliability. VI. CONCLUSION K-IRSA was studied. We presented a method to compute optimal IRSA degree distributions L K n with a given maximum degree n. A tighter bound (16) for the load threshold (G * /K) was proven, showing that plain K-IRSA cannot reach the asymptotic known bound G * /K = 1 for K > 1. Open questions are whether the tighter bound (16) can be reached and whether the rate R converges towards 0. Numerical results illustrate that optimal degree distributions can approach this bound. We also analyzed the error floor behavior of K-IRSA and provided an insightful approximation (19) Step 1 -before: ; after:

= 1 q 1 = p 1 13 14
Step 2 -before:

; after: Step 3 -before:

; after: Step 4 -before:

; after:

Fig. 1 :

 1 Fig. 1: Illustration of IRSA for 4 users in a frame of 4 slots

8 )

 8 λ(x) for different 2-MPR optimal distributions L 2 n for different maximum coefficient n compared with h 2 (x) λ(x) of 3-MPR optimal distributions L 3 n for different n compared with h 3 (x)

Fig. 4 :

 4 Fig. 4: Most probable stopping set for 2-MPR (left)

urFig. 5 :

 5 Fig.5: Normalized load threshold G * /K; dotted lines represent optimal G * /K from L K n , that are optimal distributions Λ (with max. degree n, which varies on the x-axis); thick horizontal lines represent our bound 1 -∆ K from theorem 1; dotted lines near line y = 1 represent the bound of[START_REF] Stefanović | Asymptotic performance of coded slotted aloha with multipacket reception[END_REF] with the rate R of L K

Fig. 6 : 4 Fig. 7 :

 647 Fig.6: Rate R of optimal distribution L K n when max. degree n increases

Fig. 8 :

 8 Fig. 8: Example with 2-IRSA (K=2)

TABLE I :

 I Examples of computed optimal distributions

  of the PLR at low loads, and showing its excellent performance. A final open question is: what is the best way of introducing more structure in the slot selection to improve performance?

	Initial state				IRSA decoding process
						A	B	C	D	E	F	A	B	C	D	E	F
											p 1
						slot 1		slot 2	slot 3		slot 4	slot 1	slot 2	slot 3	slot 4
						A	B	C	D	E	F	A	B	C	D	E	F
	A	B	C	D	E	F
						slot 1		slot 2	slot 3		slot 4	slot 1	slot 2	slot 3	slot 4
	slot 1	slot 2	slot 3		slot 4
						Final state
												A	B	C	D	E	F
												slot 1	slot 2	slot 3	slot 4

for instance[START_REF] Yu | Analysis of irregular repetition spatially-coupled slotted aloha[END_REF] Figure 6] presents simulation results of L = 40 superframes of ×400 slots= 16, 000 slots. In[START_REF] Yu | Analysis of irregular repetition spatially-coupled slotted aloha[END_REF] Table 1] SC-SA performance of 0.9585 with d = 4 with L = 30 or L = 40 super-frames is still well below the result 0.9767 of[START_REF] Liva | Spatiallycoupled random access on graphs[END_REF] for super-frames of L

= 200 sub-frames. Hence possibly super-frames of ≥ 100, 000 slots in practice

APPENDIX A EXAMPLE OF 2-IRSA

The Fig. 8 represents a simple example of K-IRSA (with K = 2) with 6 users and 4 slots. Λ 2 = 2 3 and Λ 3 = 1 3 (hence every node had a probability 2 3 to choose 2 repetitions, and a probability 1 3 to choose 3 repetitions). In Fig. 8, it happened that the probabilities are exactly matched. User A transmits replicas on slots 1 and 2; user B and user C as well; user D on slots 1 and 3; user E on slots 1, 2 and 3, and finally user F on slots 1, 3 and 4. The associated Tanner graph (see Section II-B) is shown. The 2-IRSA decoding process is started after the frame has been entirely received. On the left, in the odd-numbered steps (1 and 3), the decoder retrieves bursts from slots. In the even-numbered steps (2 and 4), the decoder removes their replicas. Known slots and users with decoded bursts are colored. Precisely: at step 1, slot 4 has only one burst from user F , hence it gets recovered (in IRSA or 2-IRSA). At step 2, the two other copies are located and their signal is physically removed from slots 1 and 3 (see [START_REF] Casini | Contention resolution diversity slotted aloha (crdsa): An enhanced random access schemefor satellite access packet networks[END_REF]). In step 3, only two bursts are remaining on slot 3, from users D and E. With plain IRSA, they would not be decoded, but with 2-IRSA (e.g. with 2-MPR capability), they can now be both recovered simultaneously. Then their replicas on slots 1 and 2 are removed in step 4. After that, the decoder cannot progress: indeed users A, B, C are transmitting in the same 2 slots. This is a stopping set.


Avi Elkharrat

Christiane Frougny

Jean-Pierre Gazeau

Symmetry groups for beta-lattices

come

Abstract. We present a construction of symmetry plane-groups for quasiperiodic point-sets named beta-lattices. The framework is issued from betaintegers counting systems. Beta-lattices are vector superpositions of beta-integers. When β > 1 is a quadratic PisotVijayaraghavan algebraic unit, the set of beta-integers can be equipped with an abelian group structure and an internal multiplicative law. When β = (1 + √ 5)/2, 1 + √ 2 and 2 + √ 3, we show that these arithmetic and algebraic structures lead to freely generated symmetry plane-groups for beta-lattices. These plane-groups are based on repetitions of discrete adapted rotations and translations we shall refer to as "beta-rotations and "beta-translations. Hence beta-lattices, endowed with beta-rotations and beta-translations, can be viewed like lattices. The quasiperiodic function ρ S (n), defined on the set of beta-integers as counting the number of small tiles between the origin and the nth beta-integer, plays a central part in these new group structures. In particular, this function behaves asymptotically like a linear function. As an interesting consequence, beta-lattices and their symmetries behave asymptotically like lattices and lattice symmetries, respectively.

‡

  Laboratoire de Physique Théorique de la Matière Condensée, Boîte 7020, Université Paris 7-Denis Diderot, 75251 Paris Cedex 05, France § Laboratoire d'Informatique Algorithmique : Fondements et Applications, UMR 7089 CNRS, Boîte 7014, Université Paris 7-Denis Diderot, 75251 Paris Cedex 05, France † Institut Fourier, Université Joseph Fourier Grenoble, CNRS URA 188, BP 74-Domaine Universitaire, 38402-Saint Martin d'Hères, France.