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 LTE-A 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 next-generation cellular networks. Accordingly, there are many research works are proposed to improve the performance of the RACH procedure in LTE to support M2M communications [2-6].

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 back-off time for various traffic types [3]. Indeed, it is specified as a mechanism to control the access to the air interface in LTE and LTE-A [4]. On the other hand, some studies coincide in suggesting that the ACB should not be used as a stand-alone 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. Self-Optimized Overload Control (SOOC) is continuously configure the RA resources based on the load condition [2]. Code-expanded 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 near-optimum 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 interval

The 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 delay

Let 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. Discrete-time Markov chain for the M/M/Ng 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 Np

Figure 7. Utilization factor with different values for Np

Figure 8 shows the maximum value of N_p that allows the highest arrival under system stability constraint. The non-monotonic 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 Configuration 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. Np

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.