{'fraction_non_alphanumeric': 0.02914345075077911, 'fraction_numerical': 0.00681839644914534, 'mean_word_length': 4.387260887260887, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 6, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Random Multiple Access for M2M Communications with QoS Guarantees

We propose a novel random multiple access (RMA) scheme with quality of service (QoS) guarantees for machine-to-machine (M2M) communications. We consider a slotted uncoordinated data transmission period during which machine type communication (MTC) devices transmit over the same radio channel. Based on the latency requirements, MTC devices are divided into groups of different sizes, and the transmission frame is divided into subframes of different lengths. In each subframe, each group is assigned an access probability based on which an MTC device decides to transmit replicas of its packet or remain silent. The base station (BS) employs successive interference cancellation (SIC) to recover all the superposed packets. We derive the closed form expressions for the average probability of device resolution for each group, and we use these expressions to design the access probabilities. The accuracy of the expressions is validated through Monte Carlo simulations. We show that the designed access probabilities can guarantee the QoS requirements with high reliability and high energy efficiency. Finally, we show that RMA can outperform standard coordinated access schemes as well as some of the recently proposed M2M access schemes for cellular networks.


I. INTRODUCTION
M ACHINE-to-machine (M2M) communications involve the communication between machine type communication (MTC) devices in a fully automated fashion without or with little human intervention. M2M communications have a wide range of applications ranging from smart metering, intelligent transportation systems, health monitoring to energy management and smart grids, etc. Unlike human-tohuman (H2H) communications which involve a relatively small number of devices with high data rate requirements and large message size, M2M communications are generally characterized by a massive number of devices with low-data rate sporadic transmissions of small payloads. Moreover, most MTC devices have fixed locations with low computational and storage capabilities as well as a low power budget. Although some of these requirements have been considered in the current wireless standards, the unique requirements and traffic characteristics of M2M require major changes in the air interface and core network. This has been identified as a key area in which major changes are required to enable cellular systems to handle M2M traffic [1]. R

A. Related Work
The third generation partnership project (3GPP) has identified issues and challenges related to M2M communications in the future release of Long Term Evolution (LTE), referred to as LTE-Advanced (LTE-A) [2]. In LTE-A, devices are required to establish an air interface connection prior to data transmission. Access requests are transmitted in an uncoordinated manner over the random access channel (RACH). Once an MTC device has been granted access, it is scheduled to specific radio resources over which data transmission takes place in a deterministic manner. However, with the massive number of MTC devices forecasted to operate in the near future, the RACH in current access schemes will be overloaded and will suffer from continuous collisions requiring multiple re-transmissions. This will result in a large energy expenditure, unexpected delays, and time-frequency resource wastage. Some solutions have been proposed and even standardized to mitigate the RACH overload problem [1], [3] e.g. access class barring schemes, separate RACH resources for M2M, dynamic allocation of RACH resources, backoff schemes, slotted access, pull-based and group-based schemes.
Aside from the RACH overload problem, establishing energy efficient access schemes with QoS guarantees is another design challenge in M2M networks. We list some of the works proposed in this direction. A group-based approach was proposed in [4] where devices are grouped based on their latency requirements. Each group is allocated specific time intervals with predefined duration over which data transmission takes place in a deterministic manner. The allocated time intervals are non-overlapping and their periodicity is proportional to their packet arrival rate. Thus, groups with higher packet arrival rates are assumed to have tighter latency requirements. An extension of this work can be found in [5] where this assumption is dropped and a generalized access management scheme was proposed with an adaptive resource allocation scheme based on the incoming traffic. In [6], devices with the same QoS requirement are scheduled to transmit over the same resources simultaneously. Using well-designed codes, the superposed codewords can be reliably decoded at the base station (BS) allowing for a more efficient use of resources and reduction in the number of retransmissions at the RACH. Other approaches [7]- [9] have studied uncoordinated access schemes which do not use any RACHs and instead assign all the resources as uplink data channels. These works have shown potential performance gains in supporting a larger number of devices in comparison to coordinated access schemes for small packet transmissions. In the following, we review the recent works tackling the massive access problem through uncoordinated access which is the main focus of this paper.
For a single cell scenario with a large number of devices contending to access the same BS, a slotted protocol has been widely studied [10]. An uncoordinated data transmission period is initiated by the BS where each device transmits multiple copies of its packet in different time slots chosen independently and uniformly at random. The BS stores all the observed slots and sorts them into three categories: idle slots (no packets received), singleton slots (one packet received) and collision slots (multiple packets received). In conventional slotted ALOHA, packets can only be recovered if an interference-free copy has been received at the BS, i.e., singleton slots. Therefore, idle slots are wasteful of resources, and collision slots are wasteful of energy. However, by employing successive-interference cancellation (SIC), one can cancel the recovered packets from the collision slots allowing for the resolution of a larger fraction of devices [11]- [13]. In [13], the number of transmissions of a given device is a random variable whose distribution is predetermined at the BS and broadcasted at the beginning of each transmission period. Authors draw an analogy between this scheme and the decoding of codeson-graph for binary erasure channels [14]. Thus, the same analytical tools, namely the AND-OR tree [15], can be used to find the necessary probabilities and the maximum load that can be supported. Many extensions have been proposed since that have further emphasized the scalability of RMA with SIC and its capability of supporting a large number of devices without prior identification [16]- [20]. By requiring little signalling overhead and centralized processing, it is being considered as a possible candidate for future M2M communications [21].
Authors in [22] extended this model to a heterogenous slotted ALOHA setting using the extended AND-OR tree framework derived in [23]. In [22], the heterogeneity in the network represented the different packet loss rates amongst the devices corresponding to their different channel conditions. Using a similar analytical framework, authors in [24] considered the heterogenous QoS requirements in the network and formulated an optimization problem to find the probabilities and the system load that maximize the overall system utility. All these schemes can be seen as a special case of our more generalized framework which is shown to be more suitable for M2M applications. We extend the analytical expressions and reformulate the designs and optimization problems to satisfy the unique requirements and design constraints of M2M communications.

B. Contributions and Organization
The main contributions of this paper are summarized in what follows.
1) Random Multiple Acess Scheme: We propose a generalized slotted uncoordinated data transmission scheme for the case of diverse QoS requirements. We consider two different schemes where devices are grouped based on their QoS requirements. The first scheme is called the ACK-All scheme. In this scheme, MTC devices from all groups transmit simultaneously over the same radio resources in all stages of the transmission frame. The second scheme is called the ACK-Group scheme. In this scheme, MTC devices from the same group transmit in distinct stages. We discuss the advantages of these schemes over coordinated access schemes. We show that the proposed RMA schemes can service a larger number of devices over the same number of resources when the number of resources is sufficiently large, while guaranteeing the diverse QoS requirements. We further show that the ACK-All scheme is advantageous over the ACK-Group scheme when the number of devices with tighter latency requirements are less than those with more flexible latency requirements.
2) AND-OR Tree Based Performance Analysis: We use the AND-OR tree to analyze the system performance expressed by the average probability of device resolution error for both transmission schemes: ACK-All and ACK-Group. These expressions can be seen as a generalization of those in [24] which only characterizes the error probabilities at the end of a single subframe. As the devices that are acknowledged do not retransmit in following subframes, the intermediate feedback introduced between the subframes results in graphs with reduced sets of nodes as well as reduced edges. We characterize these reductions by reformulating the AND-OR tree expressions based on the reduced sets of active devices and slots along with their reduced degree distributions. We validate the accuracy of the expressions under different settings using simulations.
3) System Design for QoS Guarantees: We show how the derived expressions can be used to design systems that can guarantee the QoS requirements of different groups with significantly high energy efficiency and high reliability for the proposed scheme. For this, we cannot use the optimization problem formulated in [24]. Authors in [24] target vanishing error probabilities. However, the error probabilities cannot be assumed to be vanishing at the end of each subframe in the proposed scheme. For example, lower priority groups can tolerate larger delays and, thus, their error probabilities will be far from vanishing in the early stages of transmission. Moreover, vanishing error probabilities are only relevant to ultra-reliable applications which are only a subset of M2M applications. Therefore, we need to guarantee the diverse latency requirements with diverse error probabilities. Accordingly, we propose a guideline that allows us to design the access probabilities using the AND-OR tree, which assumes asymptotically large systems, for a finite number of devices and resources.
The rest of this paper is organized as follows. In Section II, we present the system model and the proposed RMA schemes. In Section III, we consider a tree-based analytical framework and derive the expressions for the average probabilities of device resolution. An energy efficient system design is discussed in Section IV along with the limitations on the system load.
A reliable system design is discussed in Section V and is shown to be valid for a finite number of devices. Numerical results and practical considerations are presented in Section VI. Conclusions are drawn in Section VII.

II. SYSTEM MODEL A. Overview
We consider a scenario where K uniformly distributed MTC devices communicate with a BS located at the origin. The devices are assumed to have fixed locations. We consider the uplink of an orthogonal frequency division multiple access (OFDMA) system, where the frequency resources are divided into several sub-channels each with a bandwidth ∆f . A radio resource unit consists of a sub-channel along with a time slot of duration T . We characterize the QoS of MTC devices in terms of the delay as diverse M2M applications have diverse latency requirements. More specifically, we consider different delay groups denoted by C 1 , C 2 , ..., C r , and their respective delay requirements are quantified in terms of time slots and denoted by N 1 , N 2 , . . . , N r , where N i < N i ′ for i < i ′ , i.e., devices from the group C i have a tighter latency requirement than devices from the group C i ′ for i < i ′ . The notations used in this paper are summarized in Table I for quick reference.
The resources allocated for M2M may either be fixed or may vary from one frame to the other. For every transmission frame, the BS is assumed to be capable of estimating the number of active devices and grouping them based on their QoS requirements. Similarly, the number of active devices and the number of groups may either be fixed or may vary from one frame to the other. Active devices are devices with at least one packet to transmit. Furthermore, we assume devices transmit one packet within one transmission frame. Packets are assumed to be of equal size and can be transmitted in one radio resource unit.
We assume a block fading channel, i.e., the channel gains remain unchanged for the duration of the transmission frame and vary randomly and independently from one frame to the other. Channels are also assumed to be reciprocal, i.e., uplink and downlink channel states are the same. Therefore, each device can estimate the uplink channel gain from the pilot signal sent periodically over the downlink channel by the BS. The devices also use these pilot signals to synchronize their timing to that of the BS [25], [26]. The devices perform channel inversion such that they all have the same received signal-to-noise ratio (SNR) γ ref [5]. γ ref is determined by the coding and modulation schemes adopted in the system such that the BS can reliably recover a device's packet if its SNR is greater than or equal to γ ref . In reality, MTC devices are power limited. For channels with low SNR, the device may not always be able to perform channel inversion. In this case, the device's channel is said to be in outage and the device remains silent.

B. Probabilistic Data Transmission
Each transmission frame is of length N = N r time slots. The frame is divided into r subframes, where the length of subframe s is denoted by ∆N s and is equal to N s − N s−1 , for 1 ≤ s ≤ r and N 0 = 0. For a given subframe s, the BS assigns every group C i an access probability p i . We emphasize that the number of probabilities that are to be distributed to the devices is equal to the number of different groups and not the number of devices. Therefore, the signaling overhead is fairly small and can be easily incorporated alongside the pilot signals, beacons,  The BS is assumed to be able to distinguish between idle slots, singleton slots, and collision slots. This is feasible with the assumed power control strategy. Once the BS detects the reception of a singleton slot, the transmitted packet is recovered and the respective device is said to be resolved. The BS and the devices can share a common pseudo-random generator function that computes a random seed based on the device's identity. The devices use these seeds to generate the indices of the slots they want to transmit in. Once a device's packet is recovered at the BS, the BS can extract the respective device's identity from the header file. Then, the BS can generate the seed and the necessary indices of slots to perform SIC. That is, the copies of the recovered packet are cancelled from the remaining slots. This allows for the potential of having more singleton slots in the following iteration, and, thus, the potential of recovering more packets.
The BS performs SIC at the end of each subframe s using all the received packets over the N s time slots. We assume a perfect feedback channel. A batch of acknowledgements is sent at the end of each subframe to all successfully resolved devices, and all acknowledged devices do not transmit in future time slots. We refer to this scheme as the ACK-All scheme. The transmission scheme in [24] can be seen as a special case with a single subframe of our more generalized ACK-All scheme. The main motivation behind dividing the transmission frame into subframes separated by intermediate feedback is to better service the lower prioritized devices which suffer from a degraded performance when sharing resources with more prioritized devices. This behaviour has been noted for codeson-graph [27] as well as random access [24].
An example of the ACK-All scheme is illustrated in Fig. 1 in terms of a bipartite graph. The circles represent the devices and are referred to as variable nodes (VNs). The squares represent the time slots and are referred to as check nodes (CNs). An edge between two nodes indicates that the device transmitted in the respective time slot. No edge between two nodes indicates that the device was silent in the respective time slot. As mentioned before, the BS performs SIC by cancelling Bipartite graphs of the ACK-All scheme with r = 4 in three consecutive subframes. The dotted and dashed lines denote the edges that were removed at the receiver side after the first and second subframe respectively, and the solid lines denote the edges that have remained. the copies of the recovered packet from the remaining slots. In that case, the edges connecting the resolved VN to the CNs are removed from the graph. Moreover, we denote by C (s) i,k the subset of devices in group C i that transmitted in the first k subframes, where 1 ≤ k ≤ s. Fig. 1 assumes flexible latency requirements as unresolved devices continue to transmit even after their delay has been violated. For stricter latency requirements, unresolved devices are dropped from the network at that point. This is illustrated in Fig. 2(a). In Fig. 2(b), we consider a variant of the ACK-All scheme: the case of separate transmissions. We refer to this scheme as the ACK-Group scheme where devices from the group C i are scheduled to transmit in subframe i only and remain silent otherwise. Thus, transmissions of devices from different groups are shown to be separated.

III. AND-OR ANALYSIS OF THE PROPOSED RMA SCHEMES
The number of edges branching out of a node is said to be the degree of the respective node. These degrees are random variables that play an important role in the system performance. In this section, we first derive the expressions of the degree distributions of the VNs and the CNs. We also introduce the AND-OR tree which is a well-known tool for calculating the decoding error probabilities of information symbols in codes on graph. Then, we propose a more generalized AND-OR tree to model the system with the ACK-All and ACK-Group schemes.

A. Degree Distributions
For generality purposes, we assume flexible latency requirements, i.e., p (s) i ≥ 0 for i > s. We denote by G s the bipartite graph formed by the first s subframes. As mentioned before, for a given subframe s, each group C i can be divided into s subsets: The probability that a device from C (s) i,s transmits in a given time slot of subframe s is a Bernoulli random variable with a success probability of p (s) i . As this probability is independent of previous transmissions, the probability that a device from the group C i,d . This is equivalent to the following binomial distribution: Furthermore, the probability that d devices from the group C For convenience, let p i,s | is the average number of devices from the group C (s) i,s that access a given time slot of subframe s. For sufficiently large K and N , the expression in (1) can be approximated by the following Poisson distribution where ζ is the average number of time slots from subframe s that are selected by a given device from the group C (s) i,s . Similarly, the expression in (2) can be approximated by the following We now consider the generator polynomial Ψ (s) i,s in the bipartite graph G s . With a slight abuse of notation, the superscript here denotes the sum degree over the first s subframes rather than that of a single subframe s as in (1). For every VN, we define a vector m of dimension s, where its i th element, m i , corresponds to its number of transmissions in the i th subframe. m i is an independent binomial random variable with a distinct success probability as given in (1). The overall degree of a VN is the sum of all elements of m and, thus, follows a Poisson binomial distribution. We also define M contains all possible realizations of m whose elements add up to an overall degree of j. Therefore, in the subgraph G s , the probability that a VN of group C (s) i,s is of degree j can be expressed as We also consider the generator polynomial to represent the overall degree distribution of a CN in subframe s. For every CN, we define a vector l of dimension r, where its i th element, l i , corresponds to the number of transmissions from the i th group, C i . l i is an independent binomial random variable with a distinct success probability as given in (2). Thus, the overall degree also follows a Poisson binomial distribution. We also define L contains all possible realizations of l whose elements add up to an overall degree of j. Then, we can write For sufficiently large K and N , the sum degree can be seen as the sum of independent Poisson random variables with different averages, which is also a Poisson random variable with an average equal to the sum of its individual components. Accordingly, we can rewrite (5) as Based on the same argument, we can rewrite (6) as From an edge perspective, the generator polynomials corresponding to the degree distributions of both VNs and CNs are defined as follows: are the average degrees of the devices and the slots in subframe s, respectively.

B. Tree Assumption
Consider an edge (v, c) chosen uniformly at random from G s connecting a VN v to an arbitrary CN c. By removing that edge, a subgraph is generated by v and all the neighbors of v within distance 2ℓ. This subgraph was shown in [15] to be a tree asymptotically with v being its root at depth 0 and its leaves at depth 2ℓ. Nodes at depth i have children at depths i + 1. The CNs are located at depth 1, 3, ..., 2ℓ − 1, and the VNs are located at depth 0, 2, ..., 2ℓ. For a given iteration of the SIC process, an edge of a CN can be removed if and only if all remaining edges have been removed in previous iterations. Thus, CNs act as AND-nodes. Conversely, an edge of a VN can be removed if at least one of the remaining edges has been removed in previous iterations. Thus, VNs act as OR-nodes. Hence these trees are often referred to as AND-OR trees [15].
AND-nodes are categorized into s different types where each type corresponds to one of the subframes. Similarly, ORnodes are categorized into r different types where each type corresponds to one group of devices. For each graph G s , we consider r trees where the i th tree is denoted by T (s) i,ℓ with depth 2ℓ and a Type-i OR-node at its root (depth 0). Initially, each Type-i OR-node at depth 2ℓ is assigned a value 0 with a probability q (s) and is 1 otherwise. We are interested in finding the probability that the root of each tree evaluates to 0.

C. ACK-All Transmission Scheme
We define ǫ (s) i as the average fraction of devices in C i that remain unresolved at the end of subframe s. The following lemma models the evolution of the average error probabilities in a given SIC iteration at the end of the transmission subframe s for the ACK-All scheme (Fig. 2a) and calculates ǫ (s) i for 1 ≤ i, s ≤ r.

Lemma 1.
For the ACK-All scheme, the probability that a device from the group C i remains unresolved at the end of subframe s is given below as: Readers are referred to Appendix A for the proof of this lemma.

D. ACK-Group Transmission Scheme
In the case of separate transmissions, the transmissions of devices within a group are non-overlapping with the transmissions of devices from other groups. Therefore, the CNs in each subframe are only connected to one group of VNs. In other words, Type-i AND-nodes are only connected to Type-i OR-nodes, for 1 ≤ i ≤ r. Following on the proof of Lemma 1, the ACK-Group scheme is a special case of our proposed scheme where g (s) i = 0 for i = s. The following proposition is then derived.

Proposition 1.
For the ACK-Group scheme, the probability that a device from the group C i remains unresolved at the end of subframe i is given below as: Another possible data transmission scheme is to acknowledge the resolved devices from C i only at the end of subframe i. Based on the work in [28] on codes-on-graph, authors showed that the encoding of already decoded information symbols is useful in the evolution of the decoding process at the receiver. However, we found that the transmissions of resolved devices in the following subframes are unnecessary and actually degrade the performance of the SIC process at the BS. The scheme performed poorly in comparison to the ACK-All scheme and demonstrated little performance gains in comparison to the ACK-Group scheme [29]; therefore, we will not consider it in the paper.

A. Performance Metrics
For ease of notation, we denote the size of each group C i by α i K where 0 < α i < 1 and i α i = 1. We also define a set of ratios β 1 , β 2 , ..., β r , where β i Ni N . We now list the main performance metrics to be considered: 1) System Load: The system load is denoted by L and is defined as the ratio of the number of active devices K to the number of time slots in the transmission frame N .
2) Device Resolution Error: We define another QoS requirement, namely, the target average probability of device resolution error ǫ * i , for 1 ≤ i ≤ r. This is the maximum acceptable fraction of devices from group C i that violate their latency requirement, on average. That is, we need to ensure that ǫ

3) Blocking Probability:
In some cases the system load may be very large that there is no solution that can satisfy the QoS requirements, i.e., delay and probability of device resolution. The system is said to be overloaded. In this case, the BS enforces some access barring techniques [1] to block some devices from accessing the network so as not to jeopardize the system performance. Details on this will be explained in Section IV-D.
4) Average Number of Transmissions: M2M devices are notorious for having low power budgets. The average number of transmissions required for a device to meet its QoS requirement should be limited below a certain threshold for an energy efficient system. The average number of transmissions for each group can be calculated from the following proposition. Readers are referred to Appendix B for the proof of this proposition.

B. Design Objectives
We denote by G an r × r matrix given as The main design objective is to find a matrix G that satisfies the latency requirements with an acceptable average probability of device resolution error. In all what follows, for simplicity, we only consider strict latency requirements, i.e., g (s) i = 0 for i > s, which is a special case of the previously derived expressions. Therefore, we have to solve for r i=1 r − i + 1 variables instead of r 2 variables. The main design objective becomes to find a matrix G that satisfies the following constraint: Let L * (ǫ) denote the maximum load for which a group of devices can be resolved within the required time with an average error probability of ǫ. The load of each group in each subframe is defined as the ratio of the number of unresolved devices in that group to the number of time slots in that subframe. Based on this definition, we present the following proposition with the cases where it is possible to satisfy the constraints in (10). Readers are referred to Appendix C for proof of this proposition.

Proposition 3. There exists a matrix G that can satisfy the latency requirements of all the groups in the ACK-All and ACK-Group schemes if and only if the following condition is satisfied:
where ǫ (0) i = 1 and 1 ≤ i ≤ r.
For the special case when the actual load of a particular group is approximately equal to the bound in (11), the devices of the respective group have to transmit separately to guarantee their QoS requirements in the two schemes: ACK-All and ACK-Group. Furthermore, when the actual load of all groups is approximately equal to L * , the matrix G that best satisfies the necessary constraints is the same for both schemes. In other words, the best performance is achieved with separate transmissions.
The arguments of the min function imply that some subframes may have a lower system load than others. Consider the case when the number of devices in group C 1 is relatively small in comparison to its latency requirement. Then, it is likely that devices of the first group will be resolved with less than β 1 N time slots. In fact, from the definition of L * (ǫ), these devices can satisfy their QoS requirement with only α1K L(ǫ * 1 ) time slots. Therefore, for fair comparison, the length of every subframe s < r is set to a length of min β s N, αsK L(ǫ * s ) which will allow the remaining groups more time slots to meet or improve their performance, if needed.

C. Special case of r = 2
We compare the two transmission schemes for the same system loads and QoS requirements. Consider the case where r = 2. We set ǫ * 1 = ǫ * 2 = 10 −3 and use differential evolution [30] to find G that minimizes the sum of average transmissions M 1 + M 2 whose expressions were given in Proposition 2. Fig.  3 shows the analytical results for both schemes as well as the simulation results for K = 4000. The simulation results closely match those calculated from the AND-OR tree. For the ACK-All scheme, we can see that group C 1 achieves the desired error probability of 10 −3 after βN time slots. As C 2 participates in encoding in this subframe, C 1 needs more time to reach its target error probability in comparison to the ACK-Group scheme where only devices of C 1 participate in encoding. However, we see the disadvantage of ACK-Group in Fig. 4. The achievable error probabilities are plotted for a larger system load. In this figure, we can see that even though group C 1 maintains the same performance, group C 2 fails to satisfy its QoS with the ACK-Group scheme. Thus, we say that the ACK-All scheme can service more devices in this case. We will elaborate on this in Section V.
The other disadvantage of the ACK-Group scheme is shown in Fig. 5(a). Although M 1 is the same in both schemes, M 2 is reduced in the ACK-All scheme leading to a reduction in the overall average number of transmissions of all devices in the system as in shown in Fig. 5(b). As the average number of transmissions is related to the energy expenditure, we say that the ACK-All scheme is more energy efficient in this case. Nevertheless, we can see that the average number of transmissions for both RMA schemes is quite comparable to the number of transmissions allowed in cellular access networks over the RACH [6] which further supports RMA as a good candidate for future M2M communication networks.

D. Access Barring
Finally, let L * r (α, β, ǫ * ) be the maximum system load that the BS can service for the parameters α = [α 1 , α 2 , ..., α r ], β = [β 1 , β 2 , ..., 1] and constraints ǫ * = [ǫ * 1 , ǫ * 2 , ..., ǫ * r ]. Conventionally, whenever a device has a packet to transmit, it needs to locate and synchronize to a suitable BS based on its broadcast information. When the number of active devices is larger than L * r N , granting all devices access into the network will jeopardize the performance of all groups. In this case, the system may implement some form of access barring to limit the number of active devices in a given transmission frame. A simple example is given in the proposition below.  Given α, β, ǫ * and N , the system can guarantee the required QoS requirements for at most L * r (α, β, ǫ * )N devices. Proposition 4 shows that when K ≤ L * r (α, β, ǫ * )N , all active devices are allowed access into the system (b = 0). On the other hand, when K > L * r (α, β, ǫ * )N , an average of only (1 − b)K = L * r (α, β, ǫ * )N active devices are allowed access into the system. Otherwise, the system will be overloaded and will fail to satisfy the QoS requirements. This access barring technique is often referred to as dynamic access barring (DAB) as the probability is updated in each transmission frame based on the current load and is not fixed a priori. It is worthy of noting that access class barring (ACB) schemes [1] can also be implemented to block more devices of the less important applications rather than all applications equally.

V. DESIGN OF RELIABLE RMA SCHEMES FOR A FINITE NUMBER OF DEVICES
When concerned with maximizing the system reliability, i.e., minimizing the device resolution error probabilities, the inaccuracy of the asymptotic AND-OR tree results for finite values of K and N has been noted in previous works [16]. In this section, we elaborate on this discrepancy and propose a guideline that enables us to use the AND-OR tree expressions to design the access probabilities for a finite number of devices. We start off by considering only a single group (r = 1) of K devices transmitting with an access probability of g K , where g = g 1 > 0 is the average number of devices that access a given time slot.
Let us denote by ǫ g, K N the average probability of device resolution error ǫ (1) 1 (ref. Section II) when the system load is K N and the access probability is g K . Here, we add the arguments g and K N to distinguish between the error probabilities achievable under different system loads and using different access probabilities. It is also to emphasize that they are the only parameters necessary to calculate the average probability of device resolution error in the asymptotic case. We calculate ǫ g, K N from Proposition 1 under different settings and plot the results in Fig. 6 along with the simulation results for N = 200 and N = 2000. Let us denote by g * the corresponding values of g at the extrema points, i.e., g * = arg min g ǫ g, K N . We notice that for both values of N there is a significant mismatch between the simulation results and the AND-OR expressions in the region [g * − σ, g * + σ], where σ is a positive decreasing function of N , i.e., σ → 0 when N → ∞.
Moreover, we also observe that the error probabilities for all loads decrease gradually as g approaches the extrema points g * . On the other hand, the error probability curves beyond that point become sharply increasing. For example, at N/K = 1.2, the error probability jumps from 0.02 to 0.61 when g increases from 3.49 to only 3.50. That is, in that region, the achievable error probability is very sensitive to the variations in g. Now, recall from Fig. 1a, that the probability of an edge connecting a pair of VN and CN is Bernoulli distributed with a success probability of g K . Therefore, the sum of edges in a bipartite graph is a Poisson distributed random variable with an average of gN . Accordingly, we can generate an infinite number of random bipartite graphs given the parameters K, N , and g. Let us denote by X the sum of edges of a random bipartite graph, and let G = X N . Then, G K denotes the effective access probability of this bipartite graph. It is straightforward to see that G is also a Poisson distributed random variable with an average of g/N . Thus, the variations in G and the effective access probability of the graph increases with the decrease in N . For example, for g ≤ 4, the standard deviation of G would be approximately 0.14 and 0.04 for N = 200 and N = 2000, respectively. Therefore, a system with a finite number of devices operating at the optimal points g * will exhibit large variations in system performance leading to the discrepancies observed between the actual average system performances and that predicted by the AND-OR tree in Fig. 6.
Based on all the above, it is now clear why the optimal values of g * for a finite number of devices cannot be calculated directly from the AND-OR tree expressions. This behavior was noted in [16] and was avoided by conducting an exhaustive search of the optimal access probabilities. While this approach may be acceptable for a small number of devices, it becomes very tedious with the increase in the number of devices as well as the number of groups. We find that a more accurate calculation of the achievable average error probability at g for a given number of devices K and number of time slots N is possible by taking the average of all three values: some positive constant c. The accuracy of our proposed design is shown in Fig. 7. We make note that was not necessary in the previous section as we were concerned with minimizing the number of transmissions rather than the error probabilities. In other words, we were not concerned with operating at the extrema points.
For the sake of completion, we extend our design to the case of multiple QoS requirements with 3 groups of devices. We set the acceptable average probability of device resolution error to 10 −3 for all groups. Furthermore, for the sake of energy efficiency, we limit the average number of transmissions, we only consider ranges of 0 ≤ g (s) i ≤ 4. In Fig. 8, we consider the case where all the groups in the system contain the same number of devices. We plot the achievable error probabilities with access probabilities designed directly from the AND-OR tree expressions and those designed using the aforementioned guideline. First of all, we observe the biggest mismatch between the two approaches for C 1 whose minimum average probability of device resolution error is above the required threshold. This validates the importance of our proposed guideline in determining suitable points of operation.
Interestingly, we observe that both schemes demonstrate the same performance. This validates the results of Proposition 3 that non-separate transmissions are only possible when the load per each group is larger than the given bound. Otherwise, the optimal performance converges to that of the ACK-Group scheme. In Fig. 9, we consider the same setup but for the case where the number of devices in each group is almost proportional to its delay requirement. In this case, the load per group is significantly larger than the bound in (11) which allows for the sharing of resources. We plot the achievable performance of each group for different loads. For N/K approximately larger than 2, the ACK-All scheme can significantly improve the performance of C 3 while guaranteeing C 1 and C 2 their required thresholds. Such an assumption on the sizes of the groups is practical when considering a Poisson packet arrival model where all devices arrive at the same rate. As devices with tighter delay requirements are served faster than others, the number of queuing devices in C i at the beginning of each transmission frame will be on average always less than those in C j , for i < j.

A. LTE Setting
In this section, we evaluate the performance of RMA in an LTE-based setting [31]. In each transmission frame, a number of resource blocks (RBs) is allocated for M2M communications. In LTE, an RB is the smallest radio resource unit that can be allocated to a device. It is made up of one time slot and one subchannel. Thus, the incorporation of RMA into an LTE-based setting requires an efficient resource management scheme of the two-dimensional resources. Although this is outside the scope of our work, we show that even with a simple setup, RMA can still score better performance over coordinated access.
As access barring is said to be the best currently available solution to the RACH overload problem and has been used in the standardization process of LTE-A [32], we consider two setups for access barring as benchmarks for comparison. In the first setup, the number of RBs allocated to the RACH in each frame is fixed a priori. In the second setup, the fraction of RBs allocated to the RACH in each frame is fixed a priori. However, for both setups, we consider DAB where the blocking probability is updated in each frame based on the current load. Devices that are blocked or unsuccessfully resolved are allowed to retransmit in the following frame. It was shown before that access barring and even DAB will not suffice as a stand alone solution in future cellular networks [3]; therefore, we consider the work of [31] which combines DAB with the dynamic resource allocation of RACHs and data channels as another benchmark. In our simulation setup, we assume that we can construct 8 preambles from each RB and that each packet can be transmitted within one RB.
For RMA, we use N to denote the number of RBs in a frame which is not necessarily the number of time slots. In fact, each transmission frame is assumed to be fixed in time duration, and the packet arrival rate λ is defined as the number of packets per frame. Fig. 10 shows the throughput of the system defined as the average number of resolved devices per transmission frame. In each transmission frame, the number of RBs reserved for M2M communications is a uniformly distributed random variable varying from 0 to 100. Simulation results are plotted for different packet arrival rates. The average number of resolved devices is shown to increase   Fig. 11. Expected delay in number of frames for RMA, DAB and the dynamic resource allocation scheme in [31] for all schemes with the increase in λ until it reaches a certain saturation point. We observe that RMA can achieve a higher throughput and, thus, can support a larger packet arrival rate. When the throughput saturates, the system is said to be unable to service all active devices and the blocking probability will start to increase. As more and more devices are barred from access, the expected delays increase, and the system becomes unstable. We note that the system is said to be stable provided that the expected delay experienced by the devices is bounded below a certain threshold. This is shown in Fig.  11, where the expected delay is expressed as the number of transmission frames. We can see that again RMA can support a larger packet arrival rate while guaranteeing small latencies. Finally, in Fig. 12, we show the capacity of these schemes for different average number of RBs. The capacity is defined as the maximum throughput that can be stably supported. The capacity of RMA is shown to be the largest when the number of resources available is sufficiently large.

B. Practical Considerations
We now shed light on a number of important practical considerations that arise with the considered framework.
1) Load Estimation: For batch arrivals, there are a number of existing load estimation algorithms based on statistical inferences that can be incorporated into this work, e.g., [33]. Similar inferences can be used for the case of continuous arrivals. For example, we can incorporate the number of resolved devices in each frame into the estimation. number of successfully resolved devices and the access barring probability, in frame i, respectively. Then, the estimated number of participating devices can be expressed as where the first, second and third terms correspond to the new packet arrivals in frame i, the unsuccessfully recovered packets in frame i − 1 and the barred packets in frame i − 1, respectively. In Fig. 12, we show that the performance degradation due to inaccurate load estimation is quite negligible. This estimate can be further improved by considering the statistical information of the previous singleton, collision, and idol slots. Performance can also be improved by designing the system for a value of K(1 + ρ), where ρ is the fractional offset error in estimation.
2) Lossy Feedback Channel: So far, we have assumed a perfect feedback. However, in some cases, acknowledgements to successfully resolved devices might be lost in the network. These unacknowledged devices will retransmit in the following subframes/frames assuming their packets have not been successfully recovered yet. This will induce a dynamic behavior in the system and can affect the stability of the system. We investigate the impact of lossy feedback channels on the system performance in Fig. 13. We can see that with an imperfect feedback channel, the losses in performance are minimal provided that the losses in acknowledgements are relatively small (< 0.01), as is generally assumed. Moreover, knowing the feedback channel state, one may redesign the system to a target error probability equal to the product of that of the SIC and that of the feedback channel. We refer the readers to the work in [34] for a study on the reliability of control information and techniques to increase this reliability. In addition, we emphasize that some of the newly proposed paradigms are considering open-loop communications, where packets are not acknowledged. In this case, device transmissions are either limited in number or within a certain time frame, after which the devices either start transmitting another packet or become idle. Such settings have been shown to have significant gains in terms of network latency in comparison to closed-loop communications [35] 3) Channel Estimation: Channel estimation is necessary in RMA for two main reasons. First of all, based on the received power and known CSI, the BS can distinguish between idle slots, singleton slots and collision slots. Second of all, the the received power needs to be large enough to allow correct de- coding of the information for the given coding and modulation scheme at the receiver. Therefore, our scheme does not require perfect channel estimation. One should note that coded random access only attempts to recover a packet when it is in a singleton slot. As mentioned before, the detection of a singleton slot is based solely on the received power level. Therefore, issues with inter-symbol interference can be resolved using the same techniques used for point to point scenarios. We assume the inter-symbol interference caused by the overlapping between different packets in different slots will have little impact on the SIC performance due to the very low interference levels for small synchronization errors. To prevent such misalignment, some guard zone can be added at the beginning and the end of each symbol. Since we assume small synchronization errors, the duration of the guard zone in each symbol is also negligible. Furthermore, once a packet is recovered from a singleton slot, the BS can determine its timing offset. As the devices are assumed to be static for the duration of the transmission frame, the BS can use this information to accurately cancel the packet out from other collision slots.
VII. CONCLUSION In this paper, we proposed a random multiple access scheme with QoS guarantees for a heterogenous M2M communication network. We considered two transmission schemes: ACK-All and ACK-Group. The ACK-All scheme allows for the simultaneous transmissions of different device groups over the same resources. Meanwhile, the ACK-Group scheme assumes that devices from different groups transmit over different resources. We drew an analogy between our proposed scheme and the codes on graph, and we derived the expressions for the average probability of device resolution for each of these two schemes based on the AND-OR tree. We showed the accuracy of these expressions in calculating the error probabilities and proposed a guideline to design the access probabilities in practical M2M settings. We showed that non-separate transmissions are only beneficial when the loads of the groups with tighter deadlines is relatively low to enable them to share their resources with the remaining groups. Otherwise, we showed through analysis and simulations that these schemes yield the same performance as the ACK-Group scheme. Finally, we showed that the proposed scheme is superior to coordinated access schemes when the number of active devices and available resources is large enough.

APPENDIX A PROOF OF LEMMA 1
Consider an arbitrary graph G s constructed with the ACK-All scheme. Let q (s) i [ℓ] be the probability that a Type-i ORnode remains unresolved in the ℓ th iteration of the SIC process. This probability is initialized as q (s) AND-nodes are divided into s types corresponding to the s subframes. A Type-i AND-node is said to have d children with a probability δ (i) d . On the other hand, OR-nodes are divided into r types corresponding to the r groups. Each type of ORnode is further divided into s sub-Types corresponding to the s subsets, where the first s − 1 sub-Types have a value of 1 (having been resolved previously). A Type-i OR-node is said to have d children with a probability of ψ A Type-i OR-node is said to be connected to a Type-j ANDnode with a probabilityc (j) i . This probability is given below as the normalized selection probability of the corresponding subframe by group i.
for sub-Types 1, ..., j 0 otherwise . From Fig. 1, we find that the degrees of some AND-nodes are reduced in each subframe as more of their edges are removed. Based on (2), the probability that a Type-j AND-node is still connected to d Type-i OR-nodes in G s is given as : For K, N ≫, the Poisson approximation of the former equation is given as Moreover, given that an edge of a Type-j AND-node has not been removed in the previous ℓ − 1 iterations of the SIC, this edge is said to be connected to a Type-i OR-node with a probabilityv In general, each AND-Node at depth 2ℓ − 1 calculates its value by performing AND operation on its children at depth 2ℓ. Assume that a child of an AND-node has a value of 1 with a probability 1 − q c . Then, the probability that an AND-node of degree d has a value of 0 is 1 − (1 − q c ) d . Similarly, each OR-node at depth 2ℓ calculates its value by performing OR operation on its children at depth 2ℓ + 1. Assume that a child of an OR-node has a value of 1 with a probability q v . Then, the probability that an OR-node of degree d has a value of 0 is (q v ) d . More generally, we can write , where q c,j is the probability that a child of an AND-node of Type-j has a value of 0. Similarly, q v,i is the probability that a child of an OR-node of Type-i has a value of 1. By averaging this expression over the degree distribution in (14) and the different types of AND-nodes, we arrive at Similarly, by averaging q v,i over the degree distribution in (7), we arrive at Finally, with a slight modification in notations, it is straightforward to arrive at the expression in Lemma 1.

APPENDIX B PROOF OF PROPOSITION 2
In the ACK-All scheme, devices from the group C i continue to transmit in following subframes provided they have not been resolved in previous subframes. Let a (s) i,n be a Bernoulli random variable denoting the probability that a device D from the group C i has transmitted in the n th time slot of the s th subframe. Then, the average number of transmissions of a device from the group C i , denoted by M i , is derived as the sum of average number of transmissions of this device in each subframe.

APPENDIX C PROOF OF PROPOSITION 3
Following on the analogy between our RMA schemes and codes on graph, the system load is analogous to the code rate. The code rate is the ratio of the number of information symbols to the number of coded symbols. The channel capacity dictates the maximum achievable code rate for a given channel SNR at which reliable transmission is possible. Similarly, the bound L * (ǫ) dictates the maximum system load for a given target error probability ǫ at which a reliable communication is possible. While the channel capacity can be calculated from the Shannon bound, L * (ǫ) can be calculated from the AND-OR tree equations given in Proposition 1. For example, in Fig.  6, the achievable error probabilities are shown for different loads and different values of g for the case of r = 1. For ǫ = 0.02, the system load is said to be upper bounded by 1/1.2, i.e., there exists a g > 0 that can guarantee an average probability of device resolution error of 0.02 for every K/N less than 1/1.2. It is straightforward to generalize this concept for r > 1 for the ACK-Group scheme. Moreover, as the ACK-Group scheme is a special case of the ACK-All scheme, we can say that if there exists a matrix G that can satisfy the latency requirements of all the groups in the ACK-Group scheme, then, there exists a matrix G that can satisfy these requirements in the ACK-All scheme as well. The argument of L * in (11) takes into consideration that some of the devices of C i have been resolved in the previous i − 1 subframes. Therefore, the error probability is scaled according to the number of unresolved devices. For the ACK-Group scheme, ǫ (s) i = 1 for i ≤ s.