{'fraction_non_alphanumeric': 0.03442490523830237, 'fraction_numerical': 0.006338159448207295, 'mean_word_length': 4.4872144561882035, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Finite Length Performance of Random Slotted ALOHA Strategies

Multiple connected devices sharing common wireless resources might create interference if they access the channel simultaneously. Medium access control (MAC) protocols gener- ally regulate the access of the devices to the shared channel to limit signal interference. In particular, irregular repetition slotted ALOHA (IRSA) techniques can achieve high-throughput performance when interference cancellation methods are adopted to recover from collisions. In this work, we study the finite length performance for IRSA schemes by building on the analogy between successive interference cancellation and iterative belief- propagation on erasure channels. We use a novel combinatorial derivation based on the matrix-occupancy theory to compute the error probability and we validate our method with simulation results.


I. INTRODUCTION
When networked devices share common wireless resources, signal interference might be experience. Medium access control (MAC) strategies need to properly control users transmission to limit this interference [1]- [3]. However, in future networks a massive number of devices will be connected to the Internet (e.g., Internet of Things and machine-to-machine communications) and MAC protocols need to be more and more distributed. Random slotted ALOHA (SA) with successive interference cancellation (SIC) strategies, for example, have recently gained attention because they do not require coordination, and they are able to recover from interfering signals.
Bipartite graphs are a useful framework to study random MAC strategies or, more generally, transmission of successive signals from several sources in different time slots. When edges in the bipartite graph are randomly generated, the analysis of belief propagation (BP) decoding is usually performed asymptotically, i.e., for an infinite number of sources and time slots. Finite length analysis has been investigated when edges are randomly selected from the transmission time slots, as the case of finite length analysis for LDPC codes [4]. However, the reverse case in which the source nodes randomly create the edges is still an open topic that we address in this work.
In this work, we consider random SA with SIC strategies as the main target application, where each source sends information to a central base station (BS) in time slots that are uniformly selected at random independently from the other sources. Packets sent in the same time slot from different users interfere among each others and cannot be immediately decoded. However, SIC strategies are able to mitigate the effect of these collisions through iterative message-passing techniques and recover corrupted data at the decoder. Within this framework, we study the decoding performance of BP schemes in finite length settings, namely for small MAC frame size. Within a MAC frame, each source follows a transmission probability distribution that drives the replication rate of the sources, hence the performance of the system. Our objective is to compute the decoding error probability, i.e., the probability of not decoding correctly the source information. We first introduce a combinatorial derivation of the packet collision probability using the matrix occupancy framework. Then, we evaluate iteratively the decoding error probability by studying the number of collisions that can actually be resolved by interference cancellation. The proposed analysis is exact but it has a computational complexity that grows with the MAC frame size. We therefore show how achieve an approximated but still accurate analysis at a reduced computational cost. Simulation results validate our study in different transmission settings with small MAC frames.
In the seminal work of [5], a key connection has been drawn between SIC strategies in irregular repetition slotted ALOHA (IRSA) and the iterative BP decoder of erasure codes on graphs. This has opened the possibility to apply theory of rateless codes to IRSA schemes and analyze their performance [6], [7], which is essential to optimize users' transmission strategy (e.g., transmission probability) [8]. These works are mainly focused on deriving asymptotic system performance for large MAC size frames. They however cannot be easily applied in optimizing resource allocation strategies in actual IRSA schemes, as shown in [8]. To the best of our knowledge, only the works in [9], [10] investigated finite-length performance analysis for IRSA scheme. Both look at the average stopping sets and derive an upper bound on the error probability in IRSA. These bounds have low computational complexity but they are not necessarily tight for very small MAC frames. In our work, we rather derive a semi-analytic analysis for finite length IRSA schemes, which permits to compute error probabilities exactly, even for small frames.

II. SYSTEM MODEL
We consider a system of k sources that communicate with a common BS. The IRSA strategy is the adopted MAC protocol [5]. We assume the time axis to be discretized in MAC frames, each of those composed of t time slots. Within a MAC frame, each source transmits d replicas of the source packet p, as depicted in Fig. 1. The d distinct time slots used for transmission are selected uniformly at random among the t total available slots. The replication rate d is randomly selected by each user following the transmission probability distribution Λ Λ Λ = [Λ 1 , . . . , Λ Dmax ], where Λ d is the probability that a user transmits d replicas, and D max is the maximum number of allowed packet replicas per MAC frame. Within a MAC frame, each source selects its replication rate independently from the others, leading to replication vector (named in the following as source degree Each realization of k sources accessing the time slots of a MAC frame can be described by a k ×t binary matrix M = (m ij ), called collision matrix, with rows and columns corresponding to users and slots, respectively. We have m ij = 1 if the ith user transmits in the jth slot, and m ij = 0 otherwise. The collision matrix M associated with the example in Fig. 1 is given by The weight of a column m j in M is given by k i=1 m ij and it represents the number of packets sent in the time slot j. Thus, columns with unity weight, e.g., [100] T , represent singleton slots that allow an immediate decoding of the message. On the contrary, columns with a weight greater than one, e.g., [110] T , represent slots in which messages collide and cannot be directly decoded. Collided messages can however be recovered by SIC strategies. If packets are sent by two users in the same time slot but one of them can be recovered from a singleton slot, then the second packet can be decoded by interference cancelation. For example, message p 1 in M is recovered from the first slot, which is a singleton one. Then, canceling the message p 1 from the other interfering messages we obtain M ′ = [0 0 0 0; 0 1 0 1; 0 1 1 1] and message p 3 can also be decoded. As long as one singleton slot is experienced, the iterative decoding process proceeds. If the SIC process resolves all collisions, then no source packets are lost within the MAC frame of interest. If the SIC process stops before completion, it leaves packets undecoded and the SIC process fails.
In this work, we are interested in evaluating the probability of failure in the SIC process, i.e., the probability that a packet is lost when transmitted through the IRSA protocol. We denote this packet loss rate (PLR) by P L , and it can be written as 1 where P Λ Λ Λ (u) is the probability of having u unrecovered packets when k users transmit over a frame of t slots with degree distribution Λ Λ Λ. We condition to a given degree distribution vector as follows with D denoting the set of all the possible packet repetition vectors allowed by the distribution Λ Λ Λ. Denoting by D the number of possible replication rates, i.e., replication rates with Λ d > 0, |D| = D k . In the next section, we compute the PLR P L for small MAC frame size t.

III. FINITE LENGTH PERFORMANCE A. Matrix-Based Formulation
Because of the source independence, collision matrices are equivalent in terms of PLR upon permutations (both across rows or columns). We can therefore study the IRSA performance by only looking at the column vectors which are present within a given matrix M. This is possible exploiting the combinatorial matrix-occupancy theory [11], dealing with sets of balls randomly assigned into groups of bins. Random access channel problems can be viewed as occupancy problems by considering packets and slots as balls and bins, respectively. The number of bins with only one ball, for example, represents the number of singleton slots.
In Finally, we define C l ⊆ C as the subset of column vectors with weight w(c q ) = k j=1 c (j) q = l, and C l,i ⊆ C l as the subset of column vectors with weight l and c i = 0. It is worth noting that each occupancy vector corresponds to multiple collision matrices that are equivalent in terms of PLR.
We are now interested in finding conditions under which an occupancy vector represents a collision matrix in the case of k sources, t time slots, and degree vector d. First, we impose that exactly t columns are present in the matrix: Then, we impose that the degree vector is respected. This means that an occupancy vector is feasible if it leads to a matrix in which exactly d i entries are non-zero in the ith row of the collision matrix. This translates in the following set of constraints Since C k has only one column vector (i.e., the vector with all 1 entries) and C k−1 has k possible column vectors (i.e., each vector with only one out of k null entry), we can impose the above k + 1 constraints - (3) and (4)

B. Packet Loss Probability
Equipped with the matrix-occupancy representation, we can express the error probability P (u | d) in (2) as where P (n|d) is the probability of experiencing an occupancy vector [n f (n, d)], when k users transmit over t slots given the repetition vector d. The indicator function Q u (k, n) returns 1 if the the SIC process with a collision matrix associated with n stops at u undecoded packets and returns 0 otherwise. We compute both terms below. The probability P (n|d) is zero if I(n) = 0, otherwise it is evaluated as the ratio between the number of collision matrices with occupancy vector [n f (n, d)] and the total number of collision matrices in the same transmission settings. The former is given by the following multinomial coefficients while the total number of collision matrices that can be experienced under the settings (k, t, d) is k j=1 t di from the independency of the sources. This leads to We then derive Q u (k, n) iteratively. We consider the jth iteration of the decoding process, where k−j packets are undecoded, and n (j) = [n (j) c1 , n (j) c2 , . . .] is the occupancy vector of the collision matrix at the jth decoding step. Note that n = n (0) is the occupancy vector before the decoding process starts. At the jth iteration of the decoding process, one message is decoded only if there exists at least one weight-1 column vector, i.e., if ∃ c ∈ C 1 s.t. n (j) If the condition is satisfied, then the decoder can proceed to the next step. At the decoding iteration j + 1, there are k − j − 1 undecoded packets and the occupancy vector of the collision matrix is denoted by n (j+1) . The latter is derived recursively from n (j) . Let us consider the column vector with the m-th entry being non-zero, i.e., c ∈ C \ ∪ l C l,m , and let us denote by c We thus recursively evaluate the indicator function Q u as If there are no weight-one columns in the collision matrix, the decoder terminates at iteration j with k − j undecoded packets and Q u becomes Finally, denoting by N the set of reduced occupancy vectorsn such that I(n) = 1, the decoding error probability of (2) results in We now comment on the complexity of the proposed semi-analytical study. Both the combinatorial and iterative steps in (9) are performed over all possible degree vectors d ∈ D and all possible reduced occupancy vectorsn ∈ N . The cardinality of D and N is given respectively by The upper bond on |N | is derived as follows. We first recall thatĈ is the dimension of the reduced occupancy vectorn and that the entries ofn need to satisfy (3). Looking at the problem as t balls into R bins, the number of possible combinations of the reduced vector is Ĉ +t−1 t . Among these, only the reduced occupancy vectors that satisfy (4) belong to N .
It is worth noting that the cardinality of D and N both scales with k and t. However, the probability of experiencing a given reduced vector and a given degree vector can be easily derived from (2). Therefore, an approximated PLR can be evaluated by performing the iterative procedure Q u (k, n) only for the most likely reduced vectors. This substantially reduces the computational complexity while preserving accuracy.

IV. NUMERICAL RESULTS
We now provide the simulation results to validate the proposed solution in finite-length systems, i.e., with small size MAC frames t ∈ [4,7]. We consider different settings with k sources and t time slots. For each (k, t) pair we consider different transmission probabilities, i.e., different degree distributions Λ(x), following [5]. For each of these scenarios, we evaluate the decoding error probability from (9). Then, for each Λ(x), we generate 1000 realizations of collision matrices and simulate the  IRSA protocol and the SIC decoding with belief propagation and we evaluate u/k. We then average this ratio over the 1000 realization to evaluate the average loss probability. We now provide simulation results in terms of normalized throughput, defined as (1 − P L )k/t. This metric is usually adopted to evaluate the performance of MAC strategies and it directly reflects the error probability P L . In Fig. 2, we provide the normalized throughput as a function of the traffic G = k/t for a scenario with t = 6 and Λ(x) = 0.2x + 0.5x 2 + 0.3x 4 . Results are provided for both simulation results and theoretical ones, namely the finite length analysis proposed in this work and the asymptotic analysis derived in [5]. We also provide an approximated solution (labeled MLV -most likely vectors), where the iterative evaluation of Q u in (9) is performed only over the occupancy vector with a probability P (d) ≥ 10 −3 . The results show a weak match between asymptotic theory and the simulations results, from here the need for finite length analysis. From the results, we also observe a good match between finite length theory (both exact and approximated) and simulations, showing the accuracy of our study. The model is validated also in the results provided from Table I, where we provide the final packet loss rate P L but also a partial performance of the decoding process (i.e., the probability of stopping the decoding step at u unknown denoted by P r[U = u]). The good match between theory and simulation is confirmed in these experiments.
Finally, in Table II we compare our analysis with the asymptotic analysis of [5] and the finite-length analysis of [9]. We see that, especially for small value of the traffic network G, the asymptotic analysis is far away from the actual performance, and that our study is more precise than [9] especially for large values of the traffic network G. This accuracy comes at a price of a large computational complexity. Because of the complexity factor, (9) might be too expensive to evaluate for realistic MAC frames (hundreds of time slots). However, in Table II we observe that the approximated solution MLV nicely scales with the MAC frame without significantly affecting the accuracy.

V. CONCLUSIONS
We carried out an evaluation of the IRSA performance in finite-length settings, using combinatorial theory and matrixoccupancy theory. Simulation results validate the derived analysis for small MAC frames and show the improved match between theory and simulation results with respect to the state of the art performance studies.