Ahmed Samir^{1}, Mahmoud M. Elmesalawy^{2}, Ahmed Salah ELDin Ali^{2}, Ihab Ali^{2}
^{1}IT Dept., EtisalatEgypt, Cairo, Egypt
^{2}Electronics, Communications and Computers Department, Helwan University, Cairo, Egypt
Correspondence to: Ahmed Salah ELDin Ali, Electronics, Communications and Computers Department, Helwan University, Cairo, Egypt.
Email:  
Copyright © 2016 Scientific & Academic Publishing. All Rights Reserved.
This work is licensed under the Creative Commons Attribution International License (CC BY).
http://creativecommons.org/licenses/by/4.0/
Abstract
The current specifications of the Random Access Channel (RACH) of the Long Term Evolution (LTE) and LTEAdvanced (LTEA) is not appropriate for MachinetoMachine (M2M) communications. This is because the massive number of M2M devices will lead to low access rate and large access delay. This paper presents a new protocol, based on the Distributed Queuing (DQ) algorithm, for improving the performance of the Random Access (RA) procedure of LTE to support the M2M services. The proposed protocol, Distributed Queuing Access for LTE (DQAL), minimizes the opportunity of collision in the access phase for M2M. The reduction in the collision will turn in enhancing both the access rate and the access delay. Furthermore the presented scheme is designed to keep the normal access procedures of HumantoHuman (H2H) communication without any impact. Results show that the access delay is decreased to half of the LTE access delay and the access success probability approaches unity.
Keywords:
Distributed Queuing, LTE, MachinetoMachine, Random Access Channel
Cite this paper: Ahmed Samir, Mahmoud M. Elmesalawy, Ahmed Salah ELDin Ali, Ihab Ali, Partial Contention Free Random access Protocol for M2M communications in LTE Networks, Journal of Wireless Networking and Communications, Vol. 6 No. 3, 2016, pp. 6672. doi: 10.5923/j.jwnc.20160603.02.
1. Introduction
The M2M communication introduced a huge number of low rate connections with long sleeping period in order to save the power [1]. The current implementation of the RACH in the LTE and LTEA is not suitable for this type of communication. This is one of the major reasons that made the 3GPP emphasize the need to revise the design of RACH in the nextgeneration cellular networks. Accordingly, there are many research works are proposed to improve the performance of the RACH procedure in LTE to support M2M communications [26].Optimized MAC which is based on transmitting the data of M2M devices either in RACH message 1 (preamble) or in message 3 (terminal identification message) [2]. This will be suitable for M2M applications having very small amount of data. Access Class Barring (ACB) which is based on defining 16 different classes with different priorities and backoff time for various traffic types [3]. Indeed, it is speciﬁed as a mechanism to control the access to the air interface in LTE and LTEA [4]. On the other hand, some studies coincide in suggesting that the ACB should not be used as a standalone solution to solve the congestion problem in the MTC networks [5] [6]. In dynamic allocation of RACH resources, the network allocates more Random Access (RA) slots for M2M devices if the radio access is under congestion [7]. Slotted access schema is based on assigning dedicated access resources for each single M2M terminal is proposed in [8]. Prioritized Random Access (PRA) is based on assigning different number of virtual resources for different traffic classes [3]. In case of overload, there are certain classes will be barred to minimize the collision probability. SelfOptimized Overload Control (SOOC) is continuously configure the RA resources based on the load condition [2]. Codeexpanded RA which increases the access opportunities by using the code expanded RA instead of using more preambles or RA slots [9]. All of the above proposals are based on ALOHA and slotted ALOHA multiple access techniques even though they have low throughput and possible instability under heavy load. There is another approach for improving the RACH which is based on the tree algorithm and the Distributed Queuing Random Access Protocol (DQRAP). The main concept of DQRAP depends on using a number of control minislots as access opportunities. The protocol operates as random access protocol in the light traffic case and switches automatically to a reservation protocol when traffic becomes heavy [10]. DQRAP was suggested by [11] to enhance the random access channel in Code Division Multiple Access (CDMA). It is also used to improve the throughput of the WLAN as proposed in [12]. All of these studies proved the stability of the protocol and its nearoptimum behavior in terms of access delay, channel utilization and power consumption. In this paper, a distributed queuing based access protocol for LTE (DQAL) is proposed to improve the random access performance for M2M while keeping the current LTE frame structure unchanged. As a result, the implementation will be very smooth with no need to change the existing RACH operation of the normal H2H in the LTE network.The reminder of this paper is organized as follows. In section 2, the proposed DQAL protocol and how the preamble status is detected as well as the proposed RA algorithm are presented. In section 3, we mathematically formulate the access delay and access success probability. The simulation results are given and analyzed in section 4. Finally, section 5 concludes this paper.
2. The Proposed DQAL
2.1. Protocol Description
In the current specification of LTE, the total number of preambles (N_{TL}) are divided into two parts, the contention based part (N_{CB}) and contention free (N_{CF}) part. The proposed access protocol is based on borrowing a part from the contention based preambles (N_{MD}) to be used by M2M devices (MDs) for access. In order to avoid any possible collision, H2H User Equipment (UE) is forced to see this part as a contention free using the notifications sent in System Information Block 2 (SIB2). This guarantees a normal RACH operation for H2H UEs. Figure 1 clarifies the preamble distribution from both H2H UEs and MDs perspectives.  Figure 1. Preamble distribution over MDs and H2H UEs 
Since original DQ protocol is based on using orthogonal minislots as access opportunities, direct implementation of it within LTE environment requires a change of the LTE frame structure. This is because the access opportunities in LTE (preambles) have not orthogonally in time. Therefore, the allocated number of preambles for MDs will be distributed among N_{g} virtual groups. Each virtual group has N_{p} preambles in which each preamble is equivalent to a minislot in the original DQRAP. Figure 2 elaborates the LTE frame structure and the proposed DQAL virtual frame structure. As shown, each main frame consists from 10 subframes. On the other hand, the DQAL frame consisted from Collision Resolution Intervals (CRIs) at which the collision will be detected and reported by the eNodeB. When the MD wants to access the system, it selects and sends one of the preambles to the eNodeB. Once the preamble is detected by eNodeB, it will sent the Random Access Response (RAR) within time window of 5 subframes [13]. Then, the eNodeB should receive the corresponding message 3 within a time window of one frame; otherwise it will know that there is a collision in that preamble. Consequently, the system needs a time of more than one frame to detect the collision. Since the operation of the DQAL is based on broadcasting information about the detection status of preambles, two frames time interval is selected as a collision resolution interval as shown in Fig.2. Thus, the DQAL protocol is virtually see the LTE frame periodicity as a number of consecutive CRIs.  Figure 2. The Collision Resolution Interval (CRI) structure 
2.2. Preamble Status Detection
Since the main operation of DQAL protocol is based on identifying the status of each sent preamble, the eNodeB should broadcast the preamble status at the start of each CRI. There are three status listed below: i. Successful: If message 3 is sent successfully to eNodeB, then the eNodeB will know that the corresponding preamble is sent without collision.ii. Collision: During the RACH procedure, there will be two possibilities for collision either in the preamble (message 1) or in message 3. In the first case, the collision will be detected by eNodeB in which message 3 will not be received within the predefined window. In the second case, the MDs will detect the collision in which message 2 will not be received during the RAR window. This can be resolved by MD as it will randomly select one of the remaining groups that are not selected by the other MDs.iii. Empty: If a preamble is not used within the CRI by any MD, the eNodeB will consider its status as empty.
2.3. DQAL Algorithm
The main operation of the proposed DQAL protocol is based on the distributed collision resolution queue. All the MDs have two counters (RQ and pRQ), where RQ is the number of collisions waiting in the queue. The second counter pRQ is the position of each MD in the collision resolution queue. At the beginning of each CRI, each MD makes some initialization based on the broadcast information (RQ value and preambles detection status). This initialization called queuing discipline rule. Another rule is the request transmission rule, used to resolve the collision. The whole process of DQAL protocol is described in algorithm 1 below. And elaborated in fig. 3.  Figure 3. DQAL Flow chart 
The main strength of the proposed algorithm inherits on allowing the new arrivals to choose preambles from the groups above G_{RQ}. This helps to avoid any further collision with the existing collided requests waiting in the queue. Furthermore, the algorithm helps the MDs to select the appropriate virtual group that can be used to reduce the probability of collision. This will enhance both the access rate and access delay.
3. DQAL Model and Analysis
The DQAL can be modelled as queuing system as long as we used exact discrete access time distribution. Each virtual group represents one server in this model as shown in Fig. 4. The feedback line indicates that any collide preamble must enter the queue again until it being transmitted successfully. The Enable Transmission Interval (ETI) represents the time taken by the MD while it is waiting till the start of the next CRI in order to transmit its preamble.  Figure 4. The DQAL model 
3.1. Mean Access Delay
The total access delay in DQAL can be calculated based on the service time of the ETI and the collision resolution delay as follows,  (1) 
Where denotes for the expected value. In the following subsections, the analysis is provided to determine the value of each term in (1).1) Service time of the enable transmission intervalThe time axis can be normalized in CRI units, consequently the service time can be considered as uniformly distrusted random variable in the interval from 0 to 1. Since the arrival rate of MDs access requests is independent on the CRI timing, therefore the expected value of service time .2) Collision resolution delayLet be the arrival rate of access requests to the system. The probability that the MD will find a free preamble in a given virtual group to access the system can be represented as,  (2) 
Where is the probability that an MD will choose free preamble in a given CRI and is the probability that there are m MDs trying to access the system in that CRI. Thus,  (3) 
Since the arrival rate of access requests is modeled with Poisson distribution for some M2M application [14] [15], equation (3) can be rewritten as follows,  (4) 
Since the MDs have the same probability to successfully send their preamble, so the service time can be modelled as a discrete geometric random variable with probability distribution function as follows,  (5) 
According to [11], the geometrical distribution can be approximated to the corresponding exponential distribution for a continuous service time. As a result, the system can be modelled as with a probability density function for the collision resolution system delay as follows,  (6) 
Hence, the average service time is given by,  (7) 
Where is the service rate that represents the rate of served MDs per CRI. Provided that the collision resolution system was modelled by Markov chain as shown in Fig. 5, the steady state probability can be obtained using [16] as follows:  Figure 5. Discretetime Markov chain for the M/M/N_{g} system 
 (8) 
Where, is the utilization factor. Given the condition that, , we can obtain the value of as follows,  (9) 
As the queuing in the system starts once the preambles in all virtual groups are already used, therefore the queuing probability can be obtained as below,  (10) 
The expected number of MDs waiting in the queue is defined as , which can be obtained as follows,  (11) 
Using Little’s theorem, the average time (W) that the MD has to wait in the queue can be expressed as follows,  (12) 
By substituting with the service rate in the utilization factor equation, we can obtain,  (13) 
Using the calculated values of , average service time, and the average waiting time, the expected value for the total access delay of the system can be expressed as follows,  (14) 
3.2. Access Success Probability
The 3GPP in [13] defines the access success probability in LTE as the probability of successfully completing the random access procedure within the maximum number of preamble retransmissions. We will refer to the maximum number of preamble retransmissions with . Since the random access response window is 5 subframes as defined in [13], then each retrial takes 10ms (one frame length). Accordingly, the success probability can be defined as the probability of successfully completing the random access procedure within , which is the equivalent time period for CRIs. Hence, by substituting with t equal in (6), we can obtain the access success probability as follow,  (15) 
By substitute with in (15), the access success probability can be obtained as,  (16) 
4. Performance Evaluation and Comparison
The 3GPP recommended settings defined in [13] and depicted in Table 1 are used to evaluate the performance of the proposed DQAL protocol.Table 1. The 3GPP suggested parameters for comparison 
 

In order to support highest possible arrival rate, we should select the best value for N_{p} and N_{g} that maintain the system stability (utilization factor to be less than one). Under fixed capacity (fixed number of preambles reserved for MDs), there is one tuning parameter left (N_{p}). As the N_{p} value increases, the probability that MD will find free preamble in the virtual group will increase, and accordingly the total access delay will decrease as shown in Fig. 6. However, the choice of N_{p} is limited by the stability constraint. Figure 7 demonstrates the relation between the utilization factor and the arrival rate with different values for N_{p}. It can be observed that at N_{p} = 6, 18, and 30 preambles, the system can support up to 500, 550, and 500 requests/sec respectively. This means that the maximum arrival rate is directly proportional to the N_{p} till certain value, and then the relation is inversed which is an anticipated partitioning phenomenon.  Figure 6. Average access delay with N_{p} 
 Figure 7. Utilization factor with different values for N_{p} 
Figure 8 shows the maximum value of N_{p} that allows the highest arrival under system stability constraint. The nonmonotonic relation between the utilization factor and N_{p} can be explained due to the lossless distribution of the preambles on the virtual groups. For different PRACH Conﬁguration Indices (0, 3, 6 and 9), the obtained maximum N_{p} values are 18, 22, 18, and 30. For a while, N_{p} = 18 is taken as optimum value where the other values lead to left unused preambles.  Figure 8. Utilization factor vs. N_{p} 
The average access delay was shown in Fig. 9 at different numbers for RA slots. As the number of RA slots increases, the system can support much more arrival rate with lower delay.  Figure 9. Average access delay for MD 
The 3GPP in [13] define the access success probability as the probability of completing the random access procedure within the maximum number of preamble retransmissions. This is equivalent to 100ms maximum access delay [13]. According to Fig. 9, the maximum obtained access delay for DQAL is less than 55ms which is less than 100ms. Hence; we can consider the access success probability equal one for DQAL. It is also important to note that the average access delay for DQAL is less than half of slotted ALOHA’s delay at different values for RA slots as shown in Table 2.Table 2. Results comparison for LTE and DQAL 
 

5. Conclusions
In this paper we introduced a new protocol (DQAL) to solve the access issue of M2M communications over LTE. The protocol is designed in such a way to be used by the MDs while not affecting the normal access operation of H2H communication. The original DQRAP is adapted to fit with the frame structure and specifications of LTE. The optimum design parameters in terms of the number of virtual groups and the number of preambles per each group are determined. The results show that the performance of the proposed DQAL protocol outperforms the original access protocol used by LTE in both access delay and success probability.
References
[1]  P. Popovski, “Reliable Reporting for Massive M2M Communications With Periodic Resource Pooling,” IEEE Wirel. Commun. Lett., vol. 3, no. 4, pp. 429–432, 2014. 
[2]  A. Laya, L. Alonso, and J. AlonsoZarate, “Is the random access channel of LTE and LTEA suitable for M2M communications? A survey of alternatives,” IEEE Commun. Surv. Tutorials, vol. 16, no. 1, pp. 4–16, 2014. 
[3]  J. P. Cheng, C. H. Lee, and T. M. Lin, “Prioritized Random Access with dynamic access barring for RAN overload in 3GPP LTEA networks,” 2011 IEEE GLOBECOM Work. GC Wkshps 2011, pp. 368–372, 2011. 
[4]  3GPP TS 36.331 V10.5.0, “Evolved Universal Terrestrial Radio Access (EUTRA); Radio Resource Control (RRC),” Mar. 2012. 
[5]  S.Y. Lien, K.C. Chen, and Y. Lin, “Toward ubiquitous massive accessesin 3GPP machinetomachine communications,” IEEE Commun. Mag.,vol. 49, no. 4, pp. 66–74, April 2011. 
[6]  M.Y. Cheng, G.Y. Lin, H.Y. Wei, and A.C. Hsu, “Overload control for MachineTypeCommunications in LTEAdvanced system,” IEEE Commun. Mag., vol. 50, no. 6, pp. 38–45, June 2012. 
[7]  3GPP TSG RAN WG2 #71 R2104662, “MTC simulation results with speciﬁc solutions ,” ZTE, Madrid, Spain, 23rd Aug. 2010. 
[8]  3GPP TR 37.868 V11.0.0, “Study on RAN Improvements for MachineType Communications,” Sep. 2011. 
[9]  Pratas, Nuno K., et al. "Codeexpanded random access for machinetype communications." 2012 IEEE Globecom Workshops. IEEE, 2012. 
[10]  W. Xu and G. Campbell, “A Near Perfect Stable Random Access Protocol for a Broadcast Channle,” in IEEE Proc. ICC92, vol. 1, 1992, p. 370374. 
[11]  L. Alonso and O. Sallent, “A NearOptimum MAC Protocol Based on the Distributed Queueing Random Access Protocol ( DQRAP ) for a CDMA Mobile,” in IEEE J. Sel. Areas Commun., vol. 18, no. 9, Sep. 2000, pp. 1701–1718. 
[12]  L. Alonso, R. Ferrus, and R. Agusti, “WLAN throughput improvement via distributed queuing MAC,” IEEE Commun. Lett., vol. 9, no. 4, pp. 310–312, 2005. 
[13]  3GPP TSG RAN WG2 #71 R2104663, “[100bis#11] LTE: MTC LTE simulations ,” ZTE, Madrid, Spain, 23rd Aug. 2010. 
[14]  Zeng, Qi, Husheng Li, and Daiyuan Peng. "Frequencyhopping based communication network with multilevel QoSs in smart grid: code design and performance analysis." Smart Grid, IEEE Transactions on 3.4 (2012): 18411852. 
[15]  Cao, Yang, et al. "QoSoriented wireless routing for smart meter data collection: Stochastic learning on graph." Wireless Communications, IEEE Transactions on 13.8 (2014): 44704482. 
[16]  D. Bertsekas and R. Gallager, DATA NETWORKS. Englewood Cliffs, NJ: PrenticeHall International, 1987. 