{'fraction_non_alphanumeric': 0.03103016625822035, 'fraction_numerical': 0.012623635818685097, 'mean_word_length': 4.65447113946765, 'pattern_counts': {'":': 0, '<': 14, '<?xml version=': 0, '>': 11, '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}}
Performance Analysis of a Novel Hybrid S-ALOHA/TDMA Protocol for Beta Distributed Massive MTC Access

Simultaneous random access of massive machine type communications (MTC) devices are expected to cause congestion in the radio access network. Not only the performance of MTC, but the coexisting human to human (H2H) communications would also degrade dramatically without an appropriate medium access control (MAC) protocol. However, most existing solutions focus on the random access procedure without dealing with the sunsequent data transmission procedure. In this paper, we firstly derive a packet size threshold based on the capacity analysis of slotted ALOHA (S-ALOHA) and time division multiple access (TDMA) protocols. Then a novel hybrid S-ALOHA/TDMA MAC protocol (HSTMAC) is presented for massive MTC access, in which the resources are separated for beta distributed machine to machine (M2M) traffic with small size packets and high priority H2H traffic with large size packets. Considering access class barring (ACB) scheme as an overload control method, the system equilibrium under arbitrary retransmission limit is analyzed rigorously, which can provide insights on quality of service (QoS) guarantee. Finally, a dynamic pre-backoff (DPBO) algorithm is designed for load balance by adaptively scattering the highly synchronized M2M traffic over the transmission interval. Numerical and simulation results validate our analysis and show that the HSTMAC protocol is superior to pure S-ALOHA protocol and pure TDMA protocol. The proposed DPBO algorithm can achieve a higher success probability and resource utilization ratio with a much reduced average delay than that of uniform pre-backoff (UPBO) scheme.


Introduction
Machine type communication (MTC), also known as machine to machine (M2M) communication, is envisioned as a main enabler for the Internet of Things (IoT) [1,2]. Featuring no (or little) human intervention, M2M applications have been experiencing rapid growth in various domains, such as intelligent transport systems, smart cities, e-Health, smart grids, industry automation, monitoring and control systems, etc. [3,4]. It is expected that there will be more than 50 billion M2M devices at 2020 [5]. Unlike traditional human to human (H2H) communications, M2M traffic is characterized by massive devices, low mobility, small data transmissions and large uplink-to-downlink traffic ratio [6]. Therefore, the long term evolved (LTE) and LTE-Advanced (LTE-A) networks have to be enhanced to accommodate such differentiated M2M services and the coexisting H2H traffic [7][8][9].
A simplified model of the random access procedure in LTE/LTE-A networks is depicted in Figure 1a, which shows that four handshake messages are needed before a successful data A simplified model of the random access procedure in LTE/LTE-A networks is depicted in Figure 1a, which shows that four handshake messages are needed before a successful data transmission [10]. If two or more devices select the same preamble in Msg1, they will receive the same random access response (RAR) message from the base station (BS) and then send Msg3 on the same granted uplink channel. However, the BS cannot decode the superposed Msg3 accurately. Hence the colliding devices fail in this random access attempt and would send retransmission requests on the next random access channel (RACH). As a result, the main concern of most works is the RACH congestion problem caused by simultaneous random access requests from massive devices [11][12][13][14][15][16]. The existing overload control mechanisms can be classified as push-based schemes (such as access class barring (ACB), dynamic RACH resources allocation, backoff, and slotted access), pull-based scheme (group paging) and a combination of these methods. The packet sizes of many M2M applications are usually small, some of them even on the order of bits or bytes (e.g., health or environment monitors and alarm devices) [17]. As to the random access procedure, shown in Figure 1b, just Msg1 occupies six resource blocks (RBs, a time-frequency resource unit which consists of 180 KHz in frequency domain and a time slot, i.e., 0.5 ms in time domain) in frequency and 1 ms in time (that is 12 RBs in total). Not to mention Msg3 and the retransmissions caused by collisions which can result in much more resource consumption. Thus the ratio of signaling overhead to effective payload may be unacceptable in practice [18]. However, a comprehensive investigation of both RACH congestion and the following data transmission is still lacking attention.
A few works have been aware of this problem [13,14,[19][20][21]. The authors in [19] demonstrated that the supportable arrival rate of one-stage protocol, like slotted-ALOHA (S-ALOHA), is higher than that of two-stage protocol, like time division multiple access (TDMA), if the payload size is small. In [20], the LTE/LTE-A random access procedure was tailored exclusively for M2M traffic to reduce the signaling overhead. Along with the surveys of various MAC protocols for M2M communications in [13,14], we present a novel hybrid S-ALOHA and TDMA MAC protocol (HSTMAC) for M2M and H2H coexisting scenario in [21]. This paper differs from [21] in the following aspects: (i) we assume that H2H traffic follows a Poisson distribution while M2M traffic follows a Beta distribution, which represents the worst case for random access procedure; (ii) we rigorously derive the system equilibrium under any retransmission limit (Q ≥ 1) instead of large value assumption (Q ≥ 9) in [21]; (iii) based on the equilibrium analysis, a dynamic pre-backoff (DPBO) algorithm is designed for load The packet sizes of many M2M applications are usually small, some of them even on the order of bits or bytes (e.g., health or environment monitors and alarm devices) [17]. As to the random access procedure, shown in Figure 1b, just Msg1 occupies six resource blocks (RBs, a time-frequency resource unit which consists of 180 KHz in frequency domain and a time slot, i.e., 0.5 ms in time domain) in frequency and 1 ms in time (that is 12 RBs in total). Not to mention Msg3 and the retransmissions caused by collisions which can result in much more resource consumption. Thus the ratio of signaling overhead to effective payload may be unacceptable in practice [18]. However, a comprehensive investigation of both RACH congestion and the following data transmission is still lacking attention.
A few works have been aware of this problem [13,14,[19][20][21]. The authors in [19] demonstrated that the supportable arrival rate of one-stage protocol, like slotted-ALOHA (S-ALOHA), is higher than that of two-stage protocol, like time division multiple access (TDMA), if the payload size is small. In [20], the LTE/LTE-A random access procedure was tailored exclusively for M2M traffic to reduce the signaling overhead. Along with the surveys of various MAC protocols for M2M communications in [13,14], we present a novel hybrid S-ALOHA and TDMA MAC protocol (HSTMAC) for M2M and H2H coexisting scenario in [21]. This paper differs from [21] in the following aspects: (i) we assume that H2H traffic follows a Poisson distribution while M2M traffic follows a Beta distribution, which represents the worst case for random access procedure; (ii) we rigorously derive the system equilibrium under any retransmission limit (Q ≥ 1) instead of large value assumption (Q ≥ 9) in [21]; (iii) based on the equilibrium analysis, a dynamic pre-backoff (DPBO) algorithm is designed for load balance of M2M traffic and quality of service (QoS) guarantee of H2H traffic. As a summary, the main contributions of this paper are as follows:

•
The framework of the proposed HSTMAC protocol is detailed in this paper. The reserved uplink RBs are divided into TDMA part for H2H traffic with large size packets and S-ALOHA part for M2M traffic with small size packets. The foundation of HSTMAC protocol is proved through system capacity analysis.

•
Considering the impact of ACB factor and backoff scheme, this paper derives the analytical performance of HSTMAC iteratively. Then the system equilibrium under arbitrary retransmission limit is analyzed rigorously, which can provide an insight on QoS provision. • Based on the equilibrium analysis, a dynamic pre-backoff algorithm is designed for QoS guarantee by adaptively scattering new M2M arrivals over the transmission interval according to the highly synchronized traffic load.

•
The superiority of HSTMAC in terms of success possibility, resource utilization ratio, delay and average access request number, is validated through numerical and simulation results. Compared to uniform pre-backoff (UPBO) algorithm, the proposed DPBO algorithm can achieve a higher success probability with a much reduced delay.
The remainder of this paper is organized as follows: Section 2 gives a brief review of the related works. Section 3 presents the frame structure of HSTMAC and its fundamental motivation. We exploit an iterative method to analyze the performance of HSTMAC in Section 4. Then we derive a more rigorous equilibrium analysis in Section 5, in which we also design a dynamic pre-backoff scheme. In Section 6, the performance of HSTMAC is analyzed through numerical and simulation results. We conclude this paper in Section 7.

Related Works
The differentiated characteristics of M2M traffic have been identified in [6], and are evaluated by field measurements in a large scale network in [17]. The most prominent features of M2M traffic are massive number of devices and uplink small data transmission. Therefore, the prime challenge faced with LTE/LTE-A networks is RACH congestion due to bursts of M2M access requests. Comprehensive surveys of load control mechanisms have been made in [12][13][14][15]. Third generation partnership project (3GPP) classifies these proposals into two main categories, namely push-based and pull-based methods [11]. As two of the push-based methods, ACB scheme aims at restricting the contending levels of services with different priorities, and dynamic resource allocation scheme aims at providing sufficient access opportunities according to traffic load. In ACB, BS firstly broadcasts an access barring factor p (0 ≤ p ≤ 1). Then each device generates a random number and proceeds with the following random access procedure if the number is not larger than p, otherwise the device has to wait for the next available access opportunity. Thus the determination of optimal ACB factor is the main concern.
In [22], both fixed and dynamic preamble allocation schemes are proposed. The ACB factor is adjusted based on load estimation without prior information. In [23], in order to maximize success probability and to satisfy the delay requirement, a Markov chain is exploited to jointly optimize the extended access barring factor and RACH resource allocation. In [24], the throughput is maximized by dynamically partitioning preambles for delay-sensitive and delay tolerant classes. In order to reduce the collision probability, the authors in [25] propose to reserve multiple uplink channels for Msg3 for a single detected preamble.
Another solution for congestion avoidance is to reuse the available preambles and uplink resources. In [26], the devices are grouped according to their spatial locations. Then for each group, a single root can generate more preamble sequences due to the reduced radius. Moreover, if the distance between two groups is larger than a threshold, the devices from different groups are allowed to reuse the same uplink channel for Msg3 [27]. The BS can decode the overlapped information through successive interference cancelation.
As a pull-based overload control method, the performance of group paging is analyzed by an iterative method in [28]. Compared to uniform distributed traffic, the devices in group paging are usually activated simultaneously in the first access slot, which results in an extremely high system load. Due to the similar reason, surge of beta distributed M2M traffic can also cause severe performance reduction [11,29,30]. Therefore, backoff based load balance schemes for synchronized M2M traffic have been widely adopted. The authors in [31] adjust the backoff indicator dynamically to ensure the delayed devices would not enter into the next paging cycle. In [32,33], uniform pre-backoff scheme has been applied to group paging. The authors also investigate the impact of backoff window size on the system performance. Further in [34], based on the stability analysis, an optimal pre-backoff scheme has been proposed for group paging to reduce energy consumption. In [35], the UPBO mechanism is also used for beta distributed traffic.
The above works mainly focus on the M2M traffic issues. However, the H2H traffic is still taking an important role in current cellular networks. Then how to accommodate both H2H and M2M traffics at the same time becomes an urgent issue. One of the possible solutions is resources splitting. The authors in [36] analyze the impact of M2M traffic on H2H traffic. Simulation results show that H2H traffic has a better performance with RACH resource separation scheme while the M2M traffic prefers ACB scheme. A preamble set partition scheme is proposed in [37]. The impact of backoff indicator and retransmissions has been investigated by simulations. In [38,39], the RACH resources are divided into M2M section, H2H section and a sharing section. Then a mixed strategy game method in [38] and a continuous time Markov chain in [39] are used to determine the optimal allocation parameters. The authors in [40] introduce a power prioritized random access scheme. The H2H devices send preambles in a higher power level while the M2M devices in a lower power level. The BS can distinguish the requests from H2H devices from M2M devices based on two detection levels and a timing alignment matching mechanism.
Obviously, most existing works draw their attentions to RACH congestion problem without considering the following data transmission requirement. Taking signaling overhead into consideration, a theoretical analysis about supportable arrival rate against packet size is derived in [19]. The conclusion is that one stage protocol can accomodate more traffics with small size packets than two stage protocol. The advantages and drawbacks of various MAC protocols have been discussed in [13,14]. Due to the differentiated QoS requirements between M2M traffic and H2H traffic, the traditional four-way handshake random access procedure may be not applicable to such a complex scenario. Therefore, it's a reasonable idea to design a hybrid MAC protocol to combine the strength of different MAC protocols. In [20], M2M devices can send data on the granted channels for Msg3 immediately after preamble transmissions. The authors in [41] divide the resources into contention only period and transmission only period. In contention only period, the M2M devices contend for the collision free access opportunities in the transmission only period in the way of carrier sense multiple access (CSMA) mechanism. In order to reduce the signaling overhead, the authors split preamble set into H2H part and M2M part [42]. The reserved preamble sequences for M2M devices are used in a CSMA/CA manner. However, the H2H traffic is not considered in [20,41] while the data transmission is not considered in [42]. The HSTMAC proposed in [21] divides reserved uplink resources into S-ALOHA part for M2M small data transmission and TDMA part for traditional H2H traffic. A joint dynamic ACB and resource allocation algorithm has been designed to maximize the resource utilization under a fairness constraint. In this paper, we further analyze the equilibrium performance of HSTMAC under arbitrary retransmission limit. Based on the equilibrium analysis, a dynamic pre-backoff algorithm is designed for load balance of beta distributed M2M traffic and QoS provision for H2H traffic.

The Proposed HSTMAC Framework and System Model
We first demonstrate the basis of the proposed HSTMAC through capacity analysis. Then the details of HSTMAC framework and the essential assumptions are presented.

Foundation of the HSTMAC Protocol
We evaluate the performance of a MAC protocol in the view of resource utilization maximization. The concept of capacity is defined as the maximum amount of resource blocks used for successful data transmissions. We will show how packet size affects the system capacity.

System Capacity of S-ALOHA Protocol
Let d denote the packet size and L denote the total available resource blocks. If the number of active devices is X, the average resource utilization R is calculated as: where the available data channels is L/δ. Then the well-known capacity of S-ALOHA system C S-ALOHA is obtained when X = L/δ: where X * S−ALOH A is the maximum supportable devices of the S-ALOHA system.

System Capacity of TDMA Protocol
The resources in TDMA system are divided into two parts for contention based random access and the following contention free data transmission. The random access procedure in TDMA can be modeled as a multi-channel S-ALOHA system [43], where each preamble is regarded as an access slot. If the RACH occupies too many RBs, the reserved data channels would be insufficient for the successful devices. On the contrary, if the reserved RBs for data channels are too many, the devices may fail due to lack of random access opportunities, which may also cause underutilization of the reserved data channels. Therefore, a tradeoff must be made for the resource allocation between random access procedure and data transmission procedure.
In order to model the uplink signaling overhead in the random access procedure, we assume that a resource block can bear γ random access opportunities. Let θ denote the proportion of RBs reserved for RACH, the resource utilization of TDMA is: where Lθγ is the reserved random access opportunities and L(1−θ) is the reserved RBs for data channels. According to Equations (2) and (3), the resource utilization is maximized when: Then the capacity of TDMA system is obtained by solving Equation (4): where X * TDMA is the maximum supportable devices of the TDMA system. Solving the equation C S-ALOHA = C TDMA , we can get the packet size threshold: Remark 1. According to Equations (2) and (5), the S-ALOHA system is superior to the TDMA system if δ < δ.
On the contrary, the TDMA system is superior to the S-ALOHA system if δ > δ Considering that M2M traffic is usually in a small packet size while traditional H2H traffic is in a large packet size, it would be a feasible idea to design a hybrid S-ALOHA/TDMA MAC protocol for M2M and H2H coexisting scenario.

Optimal ACB Parameter
For both S-ALOHA system and TDMA system, the resource utilization is a concave function with the number of active devices. In order to maximize the resource utilization, all the devices should be allowed to pass the ACB check if X ≤ X*, while only X* out of X devices can be allowed to pass the ACB check if X > X*. Therefore, the optimal ACB parameter for both S-ALOHA and TDMA systems is: Remark 2. According to the above discussions, we can derive the concept of saturation as follows. For a certain number of available resource blocks L, the maximum number of supportable devices X* can be computed by Equations (2) and (5). We define the system is in a saturation state if the actual number of active devices is X ≥ X*, where some devices are barred to proceed the random access procedure. We define the system is in a non-saturation state if X < X*, where all the devices can participate in the contention of random access opportunities. Accordingly, the resource utilization of S-ALOHA and TDMA systems in different state can be computed as:

Frame Structure of the Proposed HSTMAC Protocol
As shown in Figure 2, in HSTMAC the BS schedules resources on a cycle-by-cycle basis in time domain and each access cycle spans τ ms.
In order to utilize the resources more efficiently, the HSTMAC protocol mainly divides the reserved resources into three sections: broadcast period (BP) for essential downlink control information, S-ALOHA period (SP) for M2M traffic with small size packets and TDMA period (TP) for H2H traffic with large size packets. The TDMA period is further split into random access period (RAP) for contention based random access and data transmission period (DTP) for contention free packet transmission. The optimal tradeoff between RAP and DTP is made according to Equation (4).

Frame Structure of the Proposed HSTMAC Protocol
As shown in Figure 2, in HSTMAC the BS schedules resources on a cycle-by-cycle basis in time domain and each access cycle spans τ ms.  In the broadcast period of each cycle, BS estimates the number of active devices based on the obtained statistics and calculates the optimal resource allocation and ACB parameters for M2M and H2H traffics respectively. Then the BS broadcasts a notification message which contains these parameters to all the devices for synchronization. In this paper, we mainly focus on the uplink transmission in a single cellular cell. Let L denote the reserved uplink resource blocks in each cycle and let L SP,i , L TP,i , L RAP,i , L DTP,i denote the allocated RBs for the corresponding part in the i-th cycle, we can have: In order to make the analysis more tractable, we assume that all the active devices, new and backlog, arrive at the beginning of a cycle and complete the transmission procedure in current cycle (no matter success or fail). Packet loss on the wireless channel is not considered in this paper yet. Hence, a packet transmission request may fail due to ACB check failure, contention collision, or insufficient data channels. The failed device would select a random backoff interval between 0 and W BO and start a retransmission attempt after the backoff counter expires. A packet will be dropped if it has not been sent successfully within the maximum Q transmission attempts.
In order to evaluate the performance of HSTMAC protocol in an extreme scenario, we assume that the arrival rate of H2H packets follows a Poisson distribution with mean λ in each access cycle and the arrival rate of M2M devices follows a Beta distribution g(t) defined in [11]: where B(α,β) is the Beta function and T is the activation time interval of M2M devices. The packet sizes of H2H traffic and M2M traffic are δ 1 , δ 2 respectively. Let N M2M denote the total number of M2M devices, then the number of new arrivals in cycle i is: where t i is the time of the i-th access cycle.

Analytical Performance Analysis
Due to the beta distribution of M2M traffic, the total transmission time interval is: For the readability of this paper, we use superscripts (·) M2M and (·) H2H to denote the variables for M2M traffic and H2H traffic respectively. As a general analytical model used in this paper, we usually omit the superscripts for brevity without causing ambiguity. Let X i,j [q] denote the average number of devices which first arrive at the j-th cycle and perform their q-th transmission attempts in the i-th cycle. Then the new arrivals in each cycle are: Let X ij [q] denote the average number of devices which perform their q-th transmission attempts in the i-th cycle and let X i denote the total number of devices which perform their transmission attempts in the i-th cycle. Considering the backoff indicator, we can derive that: According to the discussions in Section 3, optimal ACB parameters should be adjusted according to the actual number of devices in each cycle. For M2M traffic, the number of reserved data channels in the i-th cycle is: As to the number of reserved random access opportunities for H2H traffic, we should first estimate whether the system is in a saturation state or not. According to Equations (4) and (5) and Remark 2, we can have: Therefore, the optimal ACB parameter can be computed as: So the average number of devices which pass the ACB check is X i p i and the average number of successful devices is: Because each device has the same success probability, if we let Z i,j [q] denote the average number of devices which first arrive at the j-th cycle and succeed in their q-th transmission attempts in the i-th cycle, we can derive that: where Z i [q] is the number of devices which succeed in their q-th access attempts in the i-th cycle.
In each cycle, the failed device which uses up its retransmission opportunities would drop the packet and experiences a final transmission failure. Otherwise, the failed device would randomly select a backoff interval ω BO ∈ [0,W BO ] and retry access to the network in the i+ω BO +1-th cycle. So the backlogged devices due to backoff can be computed as follows:

Performance Metrics
Four performance metrics, which are average success probability, resource utilization ratio, the statistics of delay and the number of transmission request, are chosen to evaluate the performance of the HSTMAC protocol. These four performance metrics are defined as follows.
The average success probability, i.e., P S , is defined as the ratio of the total number of successful devices to the total number of newly arrived devices during I max cycles: The resource utilization ratio U is defined as the ratio of the total number of RBs used for successful packet transmissions to the total number of reserved RBs: The delay of a successful device is defined as the time intervals (granularity in cycle) between its first arrival time and the time when it sends its packet successfully. So the statistical average delay D is computed as: The average request number B is defined as the average number of access attempts that a successful device has conducted:

System Balance Equation
The authors in [44] analyzed the system equilibrium point of the random access procedure without considering the following data transmission procedure and ACB scheme. In [21], the system equilibrium is derived asymptotically for joint optimization of random access and data transmission under a large transmission limit (Q ≥ 9). Compared to [21], this section would provide a more rigorous system equilibrium analysis under arbitrary transmission limit Q(Q ≥ 1).
Apparently, when the system with uniform distributed traffic converges to the equilibrium state, there must be X i = X j , ∀i,j and Z i = Z j , ∀i,j. Let f denote the one-shot success probability in each cycle, according to Equation (24) we can derive that: where λ is the average number of new arrivals. Therefore, in a recursive way, we can have the following equation: Omitting the time subscript i, the system balance equation is derived as follows: Remark 3. According to Equations (31)-(33), we can find that the components of devices in each cycle are the same with and without backoff scheme. Therefore, the uniform backoff scheme has no impact on the system performance except delay. Then according to the definitions in Subsection 4.2, the performance metrics in equilibrium state are computed as: where L is the reserved resource blocks and is the average delay caused by backoff.

Equilibrium Analysis for S-ALOHA System
We define the system load as ρ = λ L/δ . When ACB is enabled, the average number of contending devices on a data channel is defined as s = X p L/δ . Let p = 1, i.e., disable the ACB scheme, we can have the same system balance equation as Equation (11) in [44]: That is to say if the ACB is not considered, we can obtain all the system equilibrium points by solving Equation (35). Then according to [44], there may be multiple solutions and some of which are on s ∈ (1,+∞). However, when ACB scheme is enabled, there must be s = X p L/δ ≤ 1. Therefore, we have to discuss the system equilibrium under different system load and retransmission limit case by case.

Equilibrium Analysis in the Saturation State
If the S-ALOHA system is in a saturation state when it converges to the equilibrium state, there must be s = 1 according to Section 3.2. A successful device should first pass the ACB check and then succeed in the data transmission procedure without collision. Therefore, we can rewrite the system balance equation as follows: Then we can derive that: (37) Due to ACB scheme, there must have 0 ≤ p ≤ 1, so we can derive the following inequation: In this paper, we define the saturation threshold in the equilibrium state as: When L = L S−ALOH A th , the system load ρ th at the saturation threshold is obtained as: Remark 4. Based on the above analysis, there must be ρ ≥ ρ th L ≤ L S−ALOH A th if the system converges to a saturated equilibrium state. Until this step we just have demonstrated that ρ ≥ ρ th L ≤ L S−ALOH A th is the necessary condition for a saturated equilibrium state. In the following subsections, we still need to prove that is also the sufficient condition to ensure the system is saturated and to prove that there is only one equilibrium point on s∈ (0,1] if ρ < ρ th .

Equilibrium Analysis in the Non-Saturation State for Q ≤ 8
Let we define function h(s) as follows: Obviously, the solutions for Equation (35) are the cross points of line s/ρ and curve h(s). Function h(s) has exactly one convex piece on (0,s 0 ) and one concave piece on (s 0 ,+∞) for Q ≥ 1. Especially for Q ≤ 8, there is only a single solution for Equation (35) on (0,+∞) (the proof is not a contribution of this paper, readers may refer to [44] for more details). Apparently, s/ρ th has a cross point with h(s) at point s = 1. Therefore, as shown in Figure 3, there must be precisely a single equilibrium point on (0,1) if ρ < ρ th . On the other hand, there must be precisely a single solution for Equation (35) on (1,+∞) if ρ > ρ th , which means that the system is in a saturation state. h(s) has exactly one convex piece on (0,s0) and one concave piece on (s0,+∞) for Q ≥ 1. Especially for Q ≤ 8, there is only a single solution for Equation (35) on (0,+∞) (the proof is not a contribution of this paper, readers may refer to [44] for more details). Apparently, s/ρth has a cross point with h(s) at point s = 1. Therefore, as shown in Figure 3, there must be precisely a single equilibrium point on (0,1) if ρ < ρth. On the other hand, there must be precisely a single solution for Equation (35) on (1,+∞) if ρ > ρth, which means that the system is in a saturation state.
As shown in Figure 4b, if we can prove that s2 ≥ 1, there must be precisely a single equilibrium point on (0,1) for ρ < ρth.  As shown in Figure 4b, we can have the tangent φ(s) of h(s) at s = 1: The vertical intercept of φ(s) is computed as: So we must have s2 ≥ 1. That is to say, there is only a single equilibrium point on (0,1) if ρ < ρth. For ρ > ρth, all the solutions for Equation (35) are on (1,+∞), which means that the system is in a saturation state.
To sum up, if the ACB scheme is enabled, we can derive the following conclusions for S-ALOHA system under Q ≥ 1 1. If ≤ , i.e., ρ ≥ ρth, the system would surely converge to a saturated equilibrium state. Therefore, the equilibrium point cannot be computed by Equation (35)   As shown in Figure 4b, if we can prove that s 2 ≥ 1, there must be precisely a single equilibrium point on (0,1) for ρ < ρ th .
As shown in Figure 4b, we can have the tangent ϕ(s) of h(s) at s = 1: The vertical intercept of ϕ(s) is computed as: So we must have s 2 ≥ 1. That is to say, there is only a single equilibrium point on (0,1) if ρ < ρ th . For ρ > ρ th , all the solutions for Equation (35) are on (1,+∞), which means that the system is in a saturation state.
To sum up, if the ACB scheme is enabled, we can derive the following conclusions for S-ALOHA system under Q ≥ 1 1.
If L ≤ L S−ALOH A th , i.e., ρ ≥ ρ th , the system would surely converge to a saturated equilibrium state. Therefore, the equilibrium point cannot be computed by Equation (35) directly and the ACB scheme would ensure that s = 1. Then the average success probability and resource utilization ratio can be computed as: 2.
If L > L S−ALOH A th , i.e., ρ < ρ th , the ACB scheme would ensure the system converges to an equilibrium state which is non-saturate. The single unique equilibrium point s ∈ (0,1) can be computed by Equation (35). In the non-saturation state we can have:

Equilibrium Analysis for TDMA System
For the TDMA system, we can define the system load as ρ = λ/Lθγ. Considering the ACB factor, the average number of contending devices on a random access opportunity is defined as s = Xp/Lθγ. Substituting ρ,s into Equation (35), we can have the balance equation for the TDMA system. The following condition must be satisfied: The capacity of TDMA system is achieved when θ = θ*. Hence, in a similar way to the S-ALOHA system, we can obtain the saturation threshold in the equilibrium state as: Therefore, we can derive the following conclusions for TDMA system under Q ≥ 1: 1.
If L < L TDMA th , the system would surely converge to a saturated equilibrium state. Therefore, the ACB scheme would ensure that s = 1. Then the average success probability and resource utilization ratio can be computed as:

2.
If L > L TDMA th , the ACB scheme would ensure the system converges to an equilibrium state which is non-saturate. The single unique equilibrium point s ∈ (0,1) and the corresponding θ can be computed by Equations (35) and (46). In the non-saturation state we can have:

QoS Guaranteed Resource Allocation and Dynamic Pre-Backoff Algorithm
For Poisson distributed H2H traffic, a backoff scheme can only increase delays without improving the other performance metrics. Hence, in this paper the backoff scheme is not used for H2H traffic. We will first satisfy the resource requirement of H2H traffic due to its high priority. Then according to the prior equilibrium analysis, the reserved resource blocks L TP for a given QoS requirement can be computed by Equations (34), (48) and (49).
As to the M2M traffic, the maximum supportable arrival rate for a given available resources L SP can be computed by Equation (39): The pre-backoff scheme should be enabled to balance the system load for beta distributed M2M traffic if λ ≥ λ M2M th . Therefore in this paper, we design an aggressively increase conservatively decrease based dynamic pre-backoff scheme as stated in Algorithm 1, in which η is a pre-defined time parameter to control the pre-backoff window size. In the view of the base station, X i [1] is the actual rate of new arrivals. Each new arrival in the i-th cycle would randomly select a backoff interval ω PBO ∈ [0,W PBO ] and send its first access request in the i + ω PBO -th cycle. Solve Equation (10) and return L SP ; 8.
Step2: for each cycle i = 1 : I max do 10.

Numerical and Simulation Results
In this paper, we consider a TDD cellular cell and the corresponding system parameters are defined in Table 1 [11]. The simulations are performed using Matlab and the Monte-Carlo results are obtained after 1000 runs. As to the QoS provision for H2H traffic, we assume that the reserved RBs would ensure H2H traffic converges to the equilibrium state which is precisely at the saturation threshold. The corresponding success probability at the saturation threshold under different transmission limit is listed in Table 2. In order to compare the performance of the proposed HSTMAC protocol with pure S-ALOHA protocol and pure TDMA protocol, we assume that the resources in S-ALOHA and TDMA protocols are also split for M2M traffic and H2H traffic separately.

System Performance versus Packet Size
In this and the next subsections, we will validate the analysis of system capacity and system equilibrium for the pure S-ALOHA protocol and pure TDMA protocol. For this purpose, we assume that the arrival rate of new packets follows a Poisson distribution and the evaluation time is set to 500 cycles. Shown in Figure 5, the system performance of S-ALOHA and TDMA protocols with different packet size are derived by the iterative method. For small packet size δ = 0.5, as shown in Figure 5a,b, when the available resource blocks are insufficient, both the average success probability and resource utilization ratio of S-ALOHA protocol is higher than that of TDMA protocol. At the same time, as shown in Figure 5c, the average request number of S-ALOHA protocol is lower than that of TDMA protocol. When the number of available resource blocks is large enough, the success probability and resource utilization ratio of S-ALOHA protocol are almost the same with that of TDMA protocol while the average request number of S-ALOHA protocol is still lower than that of TDMA protocol. For large packet size δ = 2, on the contrary, when the available resource blocks are insufficient, both the average success probability and resource utilization ratio of S-ALOHA protocol is lower than that of TDMA protocol and the average request number of S-ALOHA protocol is higher than that of TDMA protocol. When the number of available resource blocks is large enough, the success probability and resource utilization ratio of S-ALOHA protocol are almost the same with that of TDMA protocol while the average request number of S-ALOHA protocol is still higher than that of TDMA protocol. Therefore, we can validate the analysis in Section 3.1 and make a conclusion that the S-ALOHA protocol is superior to the TDMA protocol for small packet transmission while the TDMA protocol is superior to the S-ALOHA protocol for large packet transmission.

Equlibrium Analysis
As shown in Figure 6, the simulation results (Sim in the figure) match well with the equilibrium analysis (EA in the figure) and analytical results (Ana in the figure). For S-ALOHA protocol, the maximum difference is found in the average request number, which is 5.54%. For TDMA protocol, though the simulation results are shifting to the right, they have the same tendencies with the equilibrium analysis and analytical results.
As shown in Figures 7 and 8, when the available RBs are insufficient, the ACB scheme would ensure the system converges to a saturated equilibrium state. Then according to Equations (44) and (48), for both the S-ALOHA and TDMA protocols, the average success probability is increasing linearly with the number of available RBs and the resource utilization ratio remains constant. The transmission limit has no impact on the success probability and resource utilization ratio under such a condition. However, as shown in Figure 8, the average request number for Q = 10 is much higher than that for Q = 5.

Equlibrium Analysis
As shown in Figure 6, the simulation results (Sim in the figure) match well with the equilibrium analysis (EA in the figure) and analytical results (Ana in the figure). For S-ALOHA protocol, the maximum difference is found in the average request number, which is 5.54%. For TDMA protocol, though the simulation results are shifting to the right, they have the same tendencies with the equilibrium analysis and analytical results.
As shown in Figures 7 and 8, when the available RBs are insufficient, the ACB scheme would ensure the system converges to a saturated equilibrium state. Then according to Equations (44) and (48), for both the S-ALOHA and TDMA protocols, the average success probability is increasing linearly with the number of available RBs and the resource utilization ratio remains constant. The transmission limit has no impact on the success probability and resource utilization ratio under such a condition. However, as shown in Figure 8, the average request number for Q = 10 is much higher than that for Q = 5. As shown in Figure 7, when the number of available RBs is around the saturation threshold, the average success probability is still increasing but the growth is decreasing. The success probability for Q = 10 is a little higher than that for Q = 5. And the request number for Q = 10 is still higher than that for Q = 5. This demonstrates that the device can increase its success probability by trying more times.
When the number of RBs is large enough, almost all the devices can succeed in their transmission attempts. However, the resource utilization ratio is decreasing due to the underutilization of RBs. On the other hand, as shown in Figures 7-9, the performance results for Q = 10 and Q = 5 are almost the same.
As a conclusion, the system performance can be improved dramatically by increasing the available resources when it is in the saturation state. However, the performance improvement would be slight when the system is in the non-saturation state. Increasing the transmission limit can impose a positive impact on the success probability at a cost of increasing in the average request number, which means more energy consumption and higher delay.   As shown in Figure 7, when the number of available RBs is around the saturation threshold, the average success probability is still increasing but the growth is decreasing. The success probability for Q = 10 is a little higher than that for Q = 5. And the request number for Q = 10 is still higher than that for Q = 5. This demonstrates that the device can increase its success probability by trying more times.
When the number of RBs is large enough, almost all the devices can succeed in their transmission attempts. However, the resource utilization ratio is decreasing due to the underutilization of RBs. On the other hand, as shown in Figures 7-9, the performance results for Q = 10 and Q = 5 are almost the same.
As a conclusion, the system performance can be improved dramatically by increasing the available resources when it is in the saturation state. However, the performance improvement would be slight when the system is in the non-saturation state. Increasing the transmission limit can impose a positive impact on the success probability at a cost of increasing in the average request number, which means more energy consumption and higher delay. As shown in Figure 7, when the number of available RBs is around the saturation threshold, the average success probability is still increasing but the growth is decreasing. The success probability for Q = 10 is a little higher than that for Q = 5. And the request number for Q = 10 is still higher than that for Q = 5. This demonstrates that the device can increase its success probability by trying more times.
When the number of RBs is large enough, almost all the devices can succeed in their transmission attempts. However, the resource utilization ratio is decreasing due to the underutilization of RBs. On the other hand, as shown in Figures 7-9, the performance results for Q = 10 and Q = 5 are almost the same.
As a conclusion, the system performance can be improved dramatically by increasing the available resources when it is in the saturation state. However, the performance improvement would be slight when the system is in the non-saturation state. Increasing the transmission limit can impose a positive impact on the success probability at a cost of increasing in the average request number, which means more energy consumption and higher delay.

Performance of the HSTMAC Protocol without Backoff Scheme
As shown in Figure 10a, the average success probability of M2M traffic is always decreasing with the arrival rate of H2H packets. On the other hand, shown in Figure 10c, the average resource utilization ratio is increasing with the arrival rate of H2H packets. That is because the number of reserved RBs for M2M traffic is decreasing and the reserved resources are insufficient to satisfy the QoS requirement of M2M traffic. Under such a condition, according to the equilibrium analysis in Section 5, the resource utilization ratio is increasing with the system load.

Performance of the HSTMAC Protocol without Backoff Scheme
As shown in Figure 10a, the average success probability of M2M traffic is always decreasing with the arrival rate of H2H packets. On the other hand, shown in Figure 10c, the average resource utilization ratio is increasing with the arrival rate of H2H packets. That is because the number of reserved RBs for M2M traffic is decreasing and the reserved resources are insufficient to satisfy the QoS requirement of M2M traffic. Under such a condition, according to the equilibrium analysis in Section 5, the resource utilization ratio is increasing with the system load.

Performance of the HSTMAC Protocol without Backoff Scheme
As shown in Figure 10a, the average success probability of M2M traffic is always decreasing with the arrival rate of H2H packets. On the other hand, shown in Figure 10c, the average resource utilization ratio is increasing with the arrival rate of H2H packets. That is because the number of reserved RBs for M2M traffic is decreasing and the reserved resources are insufficient to satisfy the QoS requirement of M2M traffic. Under such a condition, according to the equilibrium analysis in Section 5, the resource utilization ratio is increasing with the system load. As the number of M2M devices is increasing from 10,000 to 50,000, there is a growth in the system load, which results in a higher resource utilization ratio. The reserved RBs are insufficient to satisfy the QoS requirement of M2M traffic. Hence, as shown in Figure 10a,b, there is a remarkable decrease in the average success probability and there is a remarkable increase in the average request number.
Apparently, Figure 10 shows that the average success probability and resource utilization ratio of the proposed HSTMAC protocol are always higher than that of S-ALOHA and TDMA protocols while the average request number is always lower than that of S-ALOHA and TDMA protocols. The reason is that S-ALOHA is appropriate for small size packet transmission while TDMA is appropriate for large size packet transmission. In order to satisfy the QoS requirement of H2H traffic, the number of reserved RBs for H2H traffic in S-ALOHA protocol is much higher than that in TDMA protocol. As shown in Figure 10, for a high H2H traffic load in the S-ALOHA protocol, the QoS cannot be satisfied even if H2H traffic occupies all the RBs. Therefore, comparing the HSTMAC protocol to the TDMA protocol, the number of reserved RBs for M2M traffic are the same. However, comparing the HSTMAC protocol to the S-ALOHA protocol, the number of reserved resource blocks for M2M traffic As the number of M2M devices is increasing from 10,000 to 50,000, there is a growth in the system load, which results in a higher resource utilization ratio. The reserved RBs are insufficient to satisfy the QoS requirement of M2M traffic. Hence, as shown in Figure 10a,b, there is a remarkable decrease in the average success probability and there is a remarkable increase in the average request number.
Apparently, Figure 10 shows that the average success probability and resource utilization ratio of the proposed HSTMAC protocol are always higher than that of S-ALOHA and TDMA protocols while the average request number is always lower than that of S-ALOHA and TDMA protocols. The reason is that S-ALOHA is appropriate for small size packet transmission while TDMA is appropriate for large size packet transmission. In order to satisfy the QoS requirement of H2H traffic, the number of reserved RBs for H2H traffic in S-ALOHA protocol is much higher than that in TDMA protocol. As shown in Figure 10, for a high H2H traffic load in the S-ALOHA protocol, the QoS cannot be satisfied even if H2H traffic occupies all the RBs. Therefore, comparing the HSTMAC protocol to the TDMA protocol, the number of reserved RBs for M2M traffic are the same. However, comparing the HSTMAC protocol to the S-ALOHA protocol, the number of reserved resource blocks for M2M traffic is much higher. As a result, the proposed HSTMAC protocol is superior to the pure TDMA protocol and pure S-ALOHA protocol especially in a high system load scenario.

Performance of the HSTMAC Protocol with Dynamic Pre-Backoff Scheme
As shown in Figure 11, we validate the analytical analysis of DPBO algorithm through simulation results. For DPBO algorithm, jitters can be found in the resource utilization ratio and average request number. The reason is that the pre-backoff window size of DPBO is changing dynamically according to the traffic load, which results in the dynamically changing of the transmission interval I max and the distribution of devices in different transmission stages.
Sensors 2017, 17, 2875 21 of 25 is much higher. As a result, the proposed HSTMAC protocol is superior to the pure TDMA protocol and pure S-ALOHA protocol especially in a high system load scenario.

Performance of the HSTMAC Protocol with Dynamic Pre-Backoff Scheme
As shown in Figure 11, we validate the analytical analysis of DPBO algorithm through simulation results. For DPBO algorithm, jitters can be found in the resource utilization ratio and average request number. The reason is that the pre-backoff window size of DPBO is changing dynamically according to the traffic load, which results in the dynamically changing of the transmission interval max I and the distribution of devices in different transmission stages. When the arrival rate of H2H packets is λ = 20, the reserved RBs are sufficient to satisfy the QoS requirement of M2M traffic. Shown in Figure 12a, almost all the M2M devices can send their packets successfully, and the resource utilization ratio of M2M traffic shown in Figure 12b is increasing linearly with the number of M2M devices. Under this condition, the pre-backoff window size in DPBO algorithm would remain close to zero. The time interval Imax is increasing with the pre-backoff and backoff window size. Hence, as shown in Figures 10 and 11, the resource utilization ratio and the average request number in the DPBO algorithm is higher while the average delay is much lower than that in the UPBO algorithm.
When the arrival rate of H2H packets is λ = 50, the system quickly becomes congested due to the growth in the number of M2M devices. Shown in Figures 12a and 13a, the performance results without backoff scheme are the worst. On the other hand, though the average success probability is decreasing with the number of M2M devices, the results in DPBO algorithm is better than that in scenarios with UPBO algorithm. In a scenario with high system load, as shown in Figures 12b and  13a, the resource utilization ratio in DPBO algorithm is higher while the average request number is lower than that in UPBO algorithm. Moreover, as shown in Figure 13b, the average delay in DPBO algorithm is lower or in the same order with that in UPBO algorithm. As a conclusion, we can derive that pre-backoff scheme can improve the success probability at cost of lowering the resource utilization ratio and increasing the delay. However, the proposed DPBO algorithm can improve the system performance at a much lower cost when compared to the UPBO algorithm. When the arrival rate of H2H packets is λ = 20, the reserved RBs are sufficient to satisfy the QoS requirement of M2M traffic. Shown in Figure 12a, almost all the M2M devices can send their packets successfully, and the resource utilization ratio of M2M traffic shown in Figure 12b is increasing linearly with the number of M2M devices. Under this condition, the pre-backoff window size in DPBO algorithm would remain close to zero. The time interval I max is increasing with the pre-backoff and backoff window size. Hence, as shown in Figures 10 and 11, the resource utilization ratio and the average request number in the DPBO algorithm is higher while the average delay is much lower than that in the UPBO algorithm.
When the arrival rate of H2H packets is λ = 50, the system quickly becomes congested due to the growth in the number of M2M devices. Shown in Figures 12a and 13a, the performance results without backoff scheme are the worst. On the other hand, though the average success probability is decreasing with the number of M2M devices, the results in DPBO algorithm is better than that in scenarios with UPBO algorithm. In a scenario with high system load, as shown in Figures 12b and 13a, the resource utilization ratio in DPBO algorithm is higher while the average request number is lower than that in UPBO algorithm. Moreover, as shown in Figure 13b, the average delay in DPBO algorithm is lower or in the same order with that in UPBO algorithm.
As a conclusion, we can derive that pre-backoff scheme can improve the success probability at cost of lowering the resource utilization ratio and increasing the delay. However, the proposed DPBO algorithm can improve the system performance at a much lower cost when compared to the UPBO algorithm.

Conclusions
In order to jointly optimize the random access procedure and the following data transmission procedure, we propose a hybrid S-ALOHA/TDMA MAC protocol to address the radio access network congestion problem caused by massive M2M devices. We prove that there exists a packet size threshold ̅ when considered the signaling overhead in the random access procedure. The S-ALOHA protocol has superiority in small data transmission when < ̅ and the TDMA protocol has superiority in large data transmission when > ̅ . Then a more rigorous system equilibrium analysis is derived and the results demonstrate that the system performance can be improved dramatically by allocating more resource blocks when it is in a saturation state. However, the improvement becomes negligible when the system is in a non-saturation state. Therefore, the equilibrium analysis could provide the operator with more insights on QoS provision. At last, for the load balance of beta distributed M2M traffic, we design a dynamic pre-backoff scheme. The performance results show that the proposed HSTMAC protocol is superior to both the pure S-ALOHA protocol and pure TDMA protocol in terms of average success probability and resource utilization ratio, especially when the system load is high. The results also demonstrate that the

Conclusions
In order to jointly optimize the random access procedure and the following data transmission procedure, we propose a hybrid S-ALOHA/TDMA MAC protocol to address the radio access network congestion problem caused by massive M2M devices. We prove that there exists a packet size threshold ̅ when considered the signaling overhead in the random access procedure. The S-ALOHA protocol has superiority in small data transmission when < ̅ and the TDMA protocol has superiority in large data transmission when > ̅ . Then a more rigorous system equilibrium analysis is derived and the results demonstrate that the system performance can be improved dramatically by allocating more resource blocks when it is in a saturation state. However, the improvement becomes negligible when the system is in a non-saturation state. Therefore, the equilibrium analysis could provide the operator with more insights on QoS provision. At last, for the load balance of beta distributed M2M traffic, we design a dynamic pre-backoff scheme. The performance results show that the proposed HSTMAC protocol is superior to both the pure S-ALOHA protocol and pure TDMA protocol in terms of average success probability and resource utilization ratio, especially when the system load is high. The results also demonstrate that the

Conclusions
In order to jointly optimize the random access procedure and the following data transmission procedure, we propose a hybrid S-ALOHA/TDMA MAC protocol to address the radio access network congestion problem caused by massive M2M devices. We prove that there exists a packet size threshold δ when considered the signaling overhead in the random access procedure. The S-ALOHA protocol has superiority in small data transmission when δ < δ and the TDMA protocol has superiority in large data transmission when δ > δ. Then a more rigorous system equilibrium analysis is derived and the results demonstrate that the system performance can be improved dramatically by allocating more resource blocks when it is in a saturation state. However, the improvement becomes negligible when the system is in a non-saturation state. Therefore, the equilibrium analysis could provide the operator with more insights on QoS provision. At last, for the load balance of beta distributed M2M traffic, we design a dynamic pre-backoff scheme. The performance results show that the proposed HSTMAC protocol is superior to both the pure S-ALOHA protocol and pure TDMA protocol in terms of average success probability and resource utilization ratio, especially when the system load is high. The results also demonstrate that the proposed DPBO algorithm can improve the access success probability and resource utilization ratio at a much lower cost in delay when compared to the uniform pre-backoff algorithm.