# An Improved LTE RACH Protocol for M2M Applications

Authors: Ahmed Samir; Mahmoud M. Elmesalawy; A. S. Ali; Ihab Ali
Journal: Mobile Information Systems
 (2016)

---

## Abstract

Machine-to-machine (M2M) communications allow multiple devices to communicate directly without human intervention. There will be a huge number of devices in the M2M communications which results in enormous congestion in the current Random Access Channel (RACH) of LTE based cellular systems. This paper presents a protocol for improving the performance of the LTE RACH for M2M applications. This protocol, the Distributed Queuing Access for LTE (DQAL), is based on the Distributed Queuing (DQ) algorithm. One of the benefits of using that algorithm is minimizing the collision in the access phase for the M2M communications. The reduction in the collision will turn in enhancing both the access success probability and the access delay for M2M devices (MDs). Furthermore, the protocol is designed to guarantee that the normal User Equipment (UE) device can access the system using the traditional RACH procedures without any modification. This will assure a seamless implementation of the proposed protocol over the existing LTE cellular systems. The simulation results show how the access delay obtained by the proposed DQAL protocol outperforms the Extended Access Baring (EAB) which is the baseline solution recommended by the 3 GPP for M2M communication.


---

## Body

## 1. Introduction

The current implementation of the Random Access Channel in the LTE and LTE-A is suffering from high congestion when there are huge numbers of devices trying to access the network. This is one of the major reasons that made the 3 GPP emphasize the need to revise the design of the next-generation cellular networks in order to make it more capable to support M2M services. The M2M communications introduced a massive number of access requests that can overload the access channel of the current LTE network. This leads to an increase in the collision probability and produces a significant access delay [1]. This massive number of M2M devices has to be considered in the design of LTE Random Access Channel (RACH) procedures.In the past few years and according to the suggestions from the 3 GPP, there are many research groups working in enhancing the current implementation of the access technique for LTE in order to serve M2M. The scope and limitations of those approaches are compared in Table1. These groups try to improve the performance of the RACH mechanism through different solutions as described below.Table 1
Comparison of LTE RACH approaches.
⁢Solution
References
Metric
Validation
Traffic
Type
Subtype
Access delay
Access success probability
Simulation
M2M
H2H
Optimized MAC
Preceded preamble
[2]
Ok
—
—
—
—
Data in message 3
[2]
Ok
—
—
—
—
Access class barring schemes
Individual ACB scaling
[4]
Ok
Ok
—
—
—
Extended Access Barring
[9]
Ok
Ok
Ok
Ok
Ok
Other solutions
Dynamic allocation of RACH resources
[3]
Ok
Ok
Ok
Ok
—
Slotted access
[5]
Ok
—
—
—
—
Prioritized Random Access
[6]
Ok
Ok
Ok
Ok
Ok
Self-Optimizing Overload Control
[7]
Ok
Ok
—
—
—
Code-expanded RA
[8]
Ok
—
—
Ok
—Optimized MAC [2] deals with M2M applications having very small amount of data where the key idea is to attach the data of the M2M device (MD) either in message 1 (Random-Access Preamble Transmission) or in message 3 (terminal identification message). However, using the preamble solution is not scalable anymore due to the limited number of preambles and the User Equipment (UE) device is not synchronized in this stage, limiting the size of the transmitted data.In dynamic allocation of RACH resources [3], the network allocates more random access (RA) slots for MDs if the radio access is under congestion. One of the obstacles of that protocol is using the data transmission resource for the purpose of accessing under the congestion situation. Hence, it is not efficient for the overload traffic case, as there is a trade-off between the access opportunities and the data transmission resources.Access class barring (ACB) [4] is based on defining 16 different classes with different priorities for accessing the network and a backoff time for each class sent by the eNodeB to manage the priority of the device. This methodology will improve the access collision probability at the cost of the access delay.Slotted Access Schema [5] is based on assigning a dedicated access resource for each single M2M terminal. Then, the device will be in sleep mode till the time of its specified RA slot reached that is defined based on the terminal identity and the RA cycle. In order to avoid the preamble collision, a long RA cycle is defined to serve enormous number of M2M terminals; consequently there will be large access delay.Prioritized Random Access (PRA) [6] is based on virtual resource allocation and dynamic access barring. Virtual resource allocation is used to assign different number of virtual resources for different traffic classes. The dynamic access barring is used to minimize the access collision probability by barring some MDs in case of overload. This protocol has good performance in comparison with access class barring methods in terms of access delay and success probability.Self-Optimized Overload Control (SOOC) [7] is based on configuring and adjusting continuously the RA resources according to the load condition and the integration of separation of RACH resources solution, ACB, and slotted access algorithm. The main feature of this scheme is that the eNodeB will collect information from the UE devices in order to determine the congestion level and based on this information the eNodeB will update the distribution configuration of the RA resources. This information is simply the number of retrials performed by the UE device to transmit the preamble which is sent by the UE device in message 3. If the number of RA slots reaches the maximum limit, then the eNodeB will restrict the access from the low priority M2M class till the congestion level decreases to a certain limit at the cost of increased mean access delay.Code-expanded RA [8] is based on increasing the number of access resources by using the code-expanded random access instead of increasing the number of the preambles/access subframes. Here, there is a virtual frame that consists of multiple subframes and the expanded code is constituted from the combination between the preambles sent over these subframes. One of the benefits of that algorithm is that the collision probability will be decreased as the number of access resources is expanded based on the length of the virtual frame. However, the UE device will need to send the preamble multiple times in order to form the code and hence both of the delay and the energy consumption will increase.Finally, Extended Access Barring (EAB) [5] is chosen by the 3 GPP as the most feasible baseline solution and is adapted for the Radio Access Network (RAN) overload control. The main idea of this algorithm is based on permitting the low priority devices from accessing the system if the RAN is congested, leaving the access resources for the delay constrained devices. Simulation results presented in [9] show that the access success probability is improved at the expense of the access delay which is severely increased. Moreover, the EAB and all of the above proposals are based on ALOHA and slotted ALOHA techniques which have low throughput (around 0.18 and 0.36 maximum) and possible instability under heavy load. One of the efficient protocols, presented in the literature that can tackle these issues, is Distributed Queuing Random Access Protocol (DQRAP). The main concept of DQRAP is based on using control minislots for reservation of the Random Access Channel. This allows achieving high channel utilization and improved access performance. The protocol operates as random access protocol in the light traffic case and switches automatically and smoothly to a reservation protocol when traffic becomes heavy. Also, the protocol puts the traffic of the newly arrived packets in the data transmission queue and blocks their transmission till the traffic become light again. Therefore, the collision probability is decreased to a great level [10].Several researches have analysed the performance of DQRAP algorithm for a lot of case studies and all of them proved the stability of the protocol and its near-optimum behaviour in terms of access delay, channel utilization, and power consumption [10–12].The work in [12] suggested the use of DQRAP to improve the throughput of the WLAN. The simulation results show that the throughput was improved by 25% compared to 802.11 MAC protocol.DQRAP/CDMA was suggested by [10, 13] to enhance the Random Access Channel in CDMA based systems. The simulation results show great enhancement in the throughput and the delay after applying this algorithm compared with ALOHA and slotted ALOHA. Nevertheless, the protocol introduced major change in CDMA frame structure as this algorithm is based on splitting the frame into slots and each slot consists of two sections. The first section is data transmission and the second one is access request. Again the access request section is split into different minislots. This major change might be one of the main reasons for nonproliferation of this protocol.In this paper, we present Distributed Queuing Access for LTE (DQAL) protocol to improve the random access performance for M2M without changing the current LTE frame structure. The new protocol is designed to guarantee that the random access procedure of the normal UE device will not be impacted resulting in seamless implementation for the proposed protocol.More specifically, the main contributions in this paper are as follows:(i)
Propose a seamless splitting technique for the LTE access resources between the UE devices and the MDs in such a way that the UE devices will not be impacted while applying the new RA algorithm.
(ii)
Virtually map the LTE access resources of the MDs to virtual groups. This virtualization is introduced to allow for applying the distributed collision resolution approach without any modification in the LTE frame structure. Hence, the employment will be soft without any need to change the current operation of the regular Human-to-Human (H2H) communications in the LTE network.
(iii)
Clarify how the preamble status will be identified and broadcasted to the MDs.
(iv)
Simulate the presented algorithm to estimate the mean access delay and the access success probability of the RACH controlled by the proposed algorithm.The reminder of this paper is organized as follows: In Section2 we describe the background of LTE, EAB, and DQRAP access mechanisms. Section 3 presents the system architecture and how the preamble status is detected as well as the DQAL algorithm and procedure. The simulation results are given and analysed in Section 4. Finally, the paper is concluded in Section 5.


## 2. Background

### 2.1. LTE

The LTE RACH consists of time-frequency resources named RA slots, which are allocated for the transmission of access requests. While the duration of each RA slot in the time domain depends on the access requests, each RA slot occupied 1.08 MHz that encountered the bandwidth of six physical resource blocks (PRBs). There are two different forms of RA procedure in LTE, contention-based and contention-free. The contention-based RA procedure, which is our concern in this paper, consists of four handshake messages between UE device and the eNodeB. Message 1, Random-Access Preamble Transmission: the preamble is the access request in the LTE. The terminal transmits this preamble in the first available RA slot whenever it has data that needs to be sent. There are 64 orthogonal preambles available for random access. These preambles are transmitted using six resource blocks (RBs) on one or more than one subframe according to the system configuration [14]. Message 2, Random Access Response (RAR): the eNodeB transmits this message for each successfully decoded preamble. This message includes the uplink resource allocation that will be used by the UE device in order to transmit message 3. Message 3, Terminal Identification: the UE device transmits its identity in this message. Message 4, Contention Resolution: the eNodeB transmits this message as an answer to message 3. A device which does not receive message 4 declares a failure in the contention resolution and schedules a new access attempt.


### 2.2. Extended Access Baring (EAB)

In the EAB, the devices are classified into specific number of Access Classes (ACs). The main concept of the algorithm is to bar the low priory ACs if the network is congested through a bitmap message broadcasted by the eNodeB indicating the barred ACs [9]. Whenever the bitmap message is changed, a paging message will be broadcasted in a predetermined paging occasion (PO) for each MD to notify the MDs that the bitmap is changed so they will read it. The number of the subframes between two consecutive paging cycles is considered as T
p; then the UE device might wait up to the paging cycle till it receives the changed bitmap.During the light traffic, the MDs are accessing the system using the normal procedure of the LTE [9], and there are several researches that present the time at which the EAB will be enabled and the normal LTE access procedures will be disabled. The switching point depends on the access request’s arrival process and the number of users currently accessing the system. In [3], Intel proposed an algorithm for determining the switching point based on the congestion coefficient which is calculated from the difference between the number of the collided UE devices and the number of successful UE devices in a certain duration normalized by the number of successful UE devices. The timing of the switching point also studied in [6] is to be determined based on the average admission rate that is calculated from the number of the available resources and the number of the contended UE device.As illustrated in [9], increasing the paging cycle will enhance the access success probability as the MDs will be barred for longer time. However, this increase will cause severe increase in the access delay which is the main issue in the EAB [11].


### 2.3. Distributed Queuing Random Access Protocol (DQRAP)

The main concept of DQRAP [15] is based on the tree control minislots. These minislots will be used to provide extra feedback for the purpose of allowing the optimum number of simultaneous access requests and data transmission. Therefore, the collision will be minimized to a great extent by reducing the number of the empty and collided slots and reserve data slots for data transmission.In DQRAP, the time axis is divided into slots and each slot consists of two parts. The first part is used for accessing the system while the second part is used for data transmission. The access part in each timeslot is divided into a number of minislots in which each minislot is considered as one access opportunity as shown in Figure1.Figure 1
DQRAP frame structure.There are two queues in DQRAP, collision resolution queue for resolving the previous collision in the access phase and data transmission queue that contains the messages that their access requests were succeeded and they are ready for transmission [15]. The order of the collided UE devices in the collision resolution queue is based on the order of the selected minislot by the UE device among the remaining minislots. Each UE device will receive the status of its minislot (empty, collided, and successful) from the base station along with the status of the reaming minislots and the number of collisions waiting in the collision resolution queue. Then if the minislot of the UE device is collided, it will enter the collision resolution queue with the same order of his selected minislot between the remaining collided minislots.


## 2.1. LTE

The LTE RACH consists of time-frequency resources named RA slots, which are allocated for the transmission of access requests. While the duration of each RA slot in the time domain depends on the access requests, each RA slot occupied 1.08 MHz that encountered the bandwidth of six physical resource blocks (PRBs). There are two different forms of RA procedure in LTE, contention-based and contention-free. The contention-based RA procedure, which is our concern in this paper, consists of four handshake messages between UE device and the eNodeB. Message 1, Random-Access Preamble Transmission: the preamble is the access request in the LTE. The terminal transmits this preamble in the first available RA slot whenever it has data that needs to be sent. There are 64 orthogonal preambles available for random access. These preambles are transmitted using six resource blocks (RBs) on one or more than one subframe according to the system configuration [14]. Message 2, Random Access Response (RAR): the eNodeB transmits this message for each successfully decoded preamble. This message includes the uplink resource allocation that will be used by the UE device in order to transmit message 3. Message 3, Terminal Identification: the UE device transmits its identity in this message. Message 4, Contention Resolution: the eNodeB transmits this message as an answer to message 3. A device which does not receive message 4 declares a failure in the contention resolution and schedules a new access attempt.


## 2.2. Extended Access Baring (EAB)

In the EAB, the devices are classified into specific number of Access Classes (ACs). The main concept of the algorithm is to bar the low priory ACs if the network is congested through a bitmap message broadcasted by the eNodeB indicating the barred ACs [9]. Whenever the bitmap message is changed, a paging message will be broadcasted in a predetermined paging occasion (PO) for each MD to notify the MDs that the bitmap is changed so they will read it. The number of the subframes between two consecutive paging cycles is considered as T
p; then the UE device might wait up to the paging cycle till it receives the changed bitmap.During the light traffic, the MDs are accessing the system using the normal procedure of the LTE [9], and there are several researches that present the time at which the EAB will be enabled and the normal LTE access procedures will be disabled. The switching point depends on the access request’s arrival process and the number of users currently accessing the system. In [3], Intel proposed an algorithm for determining the switching point based on the congestion coefficient which is calculated from the difference between the number of the collided UE devices and the number of successful UE devices in a certain duration normalized by the number of successful UE devices. The timing of the switching point also studied in [6] is to be determined based on the average admission rate that is calculated from the number of the available resources and the number of the contended UE device.As illustrated in [9], increasing the paging cycle will enhance the access success probability as the MDs will be barred for longer time. However, this increase will cause severe increase in the access delay which is the main issue in the EAB [11].


## 2.3. Distributed Queuing Random Access Protocol (DQRAP)

The main concept of DQRAP [15] is based on the tree control minislots. These minislots will be used to provide extra feedback for the purpose of allowing the optimum number of simultaneous access requests and data transmission. Therefore, the collision will be minimized to a great extent by reducing the number of the empty and collided slots and reserve data slots for data transmission.In DQRAP, the time axis is divided into slots and each slot consists of two parts. The first part is used for accessing the system while the second part is used for data transmission. The access part in each timeslot is divided into a number of minislots in which each minislot is considered as one access opportunity as shown in Figure1.Figure 1
DQRAP frame structure.There are two queues in DQRAP, collision resolution queue for resolving the previous collision in the access phase and data transmission queue that contains the messages that their access requests were succeeded and they are ready for transmission [15]. The order of the collided UE devices in the collision resolution queue is based on the order of the selected minislot by the UE device among the remaining minislots. Each UE device will receive the status of its minislot (empty, collided, and successful) from the base station along with the status of the reaming minislots and the number of collisions waiting in the collision resolution queue. Then if the minislot of the UE device is collided, it will enter the collision resolution queue with the same order of his selected minislot between the remaining collided minislots.


## 3. The Proposed DQAL Protocol

In this section, we present the suggested system model, the challenges of applying the DQRAP on the LTE, preamble status detection, and DQAL rules.


### 3.1. Protocol Description

In the suggested protocol, we capitalize on applying the DQRAP for accessing the system in order to keep the current LTE frame structure without any modification by applying the minislots on the time frame; we distributed the preambles to virtual groups where the DQRAP will be applied on each virtual group to enhance the access delay and the access success probability. However, the data transmission will follow the normal LTE procedure to eliminate any impact on the normal UE devices while accessing the system or during the data transmission phase. So, the first challenge in applying the DQRAP on LTE is how to implement this algorithm on the LTE without impacting the current operation of the normal UE devices. The second challenge is how to virtually restructure the LTE frame in such a way to be able to apply the DQRAP algorithm on the LTE. The final challenge is how to detect the order and status of the collided preamble between the others so the corresponding MD will enter the collision resolution queue based on its order. In this section, we will show how these challenges will be resolved.In the current specification of LTE, the total number of preambles (N
T
L) is divided into two parts: the contention-based part (N
C
B) available for user access and the contention-free (N
C
F) part reserved by eNodeB for special circumstances such as handover. The proposed access protocol is based on borrowing a part from the contention-based preambles (N
M
D) to be used by MDs in the access phase. This part should not be used by Human-to-Human (H2H) UE devices in order to avoid any possible collision. This can be done by making the UE devices see this part as contention-free. The notification takes place through the broadcast channel. The System Information Block 2 (SIB2) is used for this purpose. Thus, the available resources for both types are completely separated. These procedures guarantee that the normal UE device can use the traditional LTE technique to access the network. Figure 2 clarifies the preamble distribution from both UE devices and MDs perspective.Figure 2
Preamble distribution over MDs and UE devices.Direct implementation of DQRAP protocol within LTE requires a change of the LTE frame structure. This is because the access opportunities in the LTE (preambles) are implemented to be used at the same time due to its orthogonality which is not compatible with the DQRAP frame structure (minislots of the access part along with the data part). Therefore, in this paper, the LTE frame will be virtually restructured to obtain access part similar to minislots. The allocated number of preambles for MDs (N
M
D) will be distributed among N
g virtual groups. Each virtual group (denoted as G
i) has a number of preambles (N
p) in which each preamble is equivalent to a minislot in the original DQRAP. Figure 3 shows the distribution of preambles allocated for MDs among the virtual groups in both time and frequency directions.Figure 3
The distribution of the preambles among the virtual groups.When the MD wants to access the system, it selects one of the allocated preambles for MDs and sends it to the eNodeB. These preambles are sent in the allowed subframe for the random access request based on PRACH configuration index [14]. The configuration index indicates which subframe can be used to transmit the preamble. When the preamble is detected by the eNodeB, it will send the RAR within time window of 5 subframes [16]. 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 as shown in Figure 4. Since the operation of the DQAL is based on broadcasting information about the detection status of the preambles sent by the MDs, two-frame time interval is selected as the required time by eNodeB to detect the collision for any sent preamble. This interval is denoted by a Collision Resolution Interval (CRI). Thus, the DQAL protocol will virtually see the LTE frame periodicity as a number of consecutive CRIs. Each CRI can be seen as two parts, the data part and the access part. Within each CRI, the available number of access opportunities depends on the number of allocated RA slots in the two frames. By using this new virtual structure, the minislots of DQRAP are virtually mapped to the preambles of LTE.Figure 4
The Collision Resolution Interval (CRI) structure.


### 3.2. Preamble Status Detection

DQAL algorithm is based on the preamble status detection. Each MD tries to access the network, selects a virtual group, and sends an access request using one of the preambles that belong to this group. Each certain preamble has one of three states which are listed below along with the detection criteria. DQAL rules are based on these states.


#### 3.2.1. Successful State

If message 3 is sent successfully to eNodeB, then the eNodeB will know that the corresponding preamble is sent without collision.


#### 3.2.2. Collision State

There are two possibilities for collision; the first one will be detected by eNodeB and the second one will be detected by the MD. First collision might happen if two MDs (or more) send the same preamble in the same subframe while they are accessing the network and this preamble was decoded successfully by the eNodeB. In this case, message 3 for those MDs will collide and will not be decoded successfully by eNodeB. Accordingly, if eNodeB did not receive message 3 within one frame starting from the RAR, it will consider this preamble collided. Second collision might happen if two MDs (or more) send the same preamble in the same subframe while they are accessing the network and generate corrupted preamble. This preamble is not decoded successfully by eNodeB. In this case, the MD will not receive message 2 within one CRI and hence it will randomly select one of the remaining groups that is not selected by the other MDs to transmit its preamble, where the MD can know the occupied groups and the empty groups based on the status of each preamble and the resolution queue (RQ) value which is the number of the collided preambles waiting for retransmission.


#### 3.2.3. Empty State

If a preamble is not used within the CRI by any MD, the eNodeB will consider it empty and will send the corresponding status as empty to all MDs


### 3.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 collision resolution queue. All MDs have the same RQ value. The second counter pRQ is the position of each MD in the collision resolution queue. Each MD has a specific value based on his order in the queue. These counters are updated at the start of each CRI based on the information broadcasted by the eNodeB about the preambles detection status (successful, empty, or collided), bearing in mind the value of RQ is also broadcasted by the eNodeB before the start of each CRI.The same concept of switching mechanism, which enables or disables the EAB while using LTE, will be used in our DQAL algorithm. The following procedures describe the operation of the DQAL if it is enabled.At the beginning of each CRI, each MD makes some initialization based on the broadcast information (RQ value and preambles detection status). This initialization is called queuing discipline rule. Another rule is the request transmission rule, used to resolve the collision. The details of these two rules are described as follows.


#### 3.3.1. Queuing Discipline Rule (Initialization)

(a)
At the beginning of each CRI, the MD will increment the value of RQ by one for each collided preamble.
(b)
IfR
Q
>
0, each MD reduces the value of RQ by min
⁡
(
R
Q
,
N
g
) units.
(c)
If the MD has no collided preamble, then it will setp
R
Q
=
0.
(d)
If the MD preamble in the previous CRI was collided, then the MD will calculate the value of pRQ based on the order of its preamble sequence between the other collided preambles and set it at the end of RQ. If the MD has not sent any preamble or the eNodeB did not detect the status of its sent preamble then the value of pRQ will follow the same update rule as RQ, but only if the initial value is other than zero.


#### 3.3.2. Request Transmission Rule (Preamble Selection)

(a)
IfR
Q
<
N
g, each MD that has p
R
Q
=
0 [first access or its preamble status is not detected by eNodeB] randomly selects one of the preambles on group G
R
Q
+
1.
(b)
If the MD has (0
<
p
R
Q
<
N
g), it randomly selects one of the preambles of group G
p
R
Q.The process of DQAL protocol after being enabled is described in Algorithm1.Algorithm 1:Distributed queuing access protocol for LTE (DQAL).
(1)    Each step of the following will be repeated with every CRI
(2)    Initialization
(3)    eNodeB broadcast the RQ value and the preamble detection status
(4)    Each MD increment RQ by one for each collided preamble
(5)    if  (R
Q
>
0)  then
(6)     MDs Reduce the value of RQ by min
⁡
(
R
Q
,
N
g
)
(7)    end if
(8)    if  (MD’s preamble status detected as collided)  then
(9)     Calculate pRQ based on the preamble order
(10) end if
(11) Preamble selection
(12) if  (R
Q
<
N
g and p
R
Q
=
0)  do
(13)   Randomly select one of preambles on group G
R
Q
+
1
(14) end if
(15) if  (p
R
Q
<
N
g and p
R
Q
>
0)  do
(16)   Randomly select one of preambles of group G
p
R
Q
(17) end if
(18) else
(19)   Wait to the next CRI
(20) end ifAs can be seen from Algorithm1, the main strength of the proposed algorithm is based on allowing the new arrivals to choose preambles from the groups above G
R
Q. This allows avoiding any further collision with the existing collided requests waiting in the collision resolution queue. Furthermore, the algorithm helps the MDs to select the appropriate preamble that can be used to reduce the probability of collision. This will enhance both the success probability and access delay for MDs.The example shown in Figure5 clarifies how both the MDs and the normal UE device will access the network. The MDs will use the proposed algorithm to access the system while the normal UE devices will use the normal procedure of the LTE RACH. For simplicity, we assume that in the proposed algorithm there are three virtual groups; each one has three preambles as illustrated in the figure. On the other hand, the LTE frame has 6 preambles. The access request of the new arrival is represented with (∙) and the old collided access request that needs to be retransmitted is represented with (x). The operation of the proposed algorithm in each CRI is clarified as follows.Figure 5
Example of the operation of MDs and UE devices in the proposed algorithm.In the First CRI. There is no previous collision; therefore, RQ equal 0. The 2nd and the 3rd preambles are collided where two MDs select the same preamble to access the system while one MD selects the 1st preamble.In the 2nd CRI. The access requests sent on the 2nd collided preamble of the previous CRI were resolved on the first virtual group, while the access requests sent on the 3rd collided preamble in the previous CRI were retransmitted on the second virtual group. All the new access requests were sent over the 3rd virtual group where the number of the previous collisions waiting in the collision resolution queue is 2 (i.e., RQ equal 2).In the 3rd CRI. The previous collided preambles are resolved as follows:(i)
Second virtual group collided preambles: the access requests sent on the 3rd collided preamble were resolved on the first virtual group in the 3rd CRI.
(ii)
Third virtual group collided preambles: the access requests sent on the 2nd collided preamble were resolved on the second virtual group in the 3rd CRI. However, the access requests sent on the 3rd collided preamble were retransmitted on the third virtual group in the 3rd CRI.
(iii)
RQ =N
g = 3, therefore no new access requests are sent in this CRI.
In the 4th CRI. The access requests sent on the 2nd collided preamble of the previous CRI are resolved on the first virtual group in the 4th CRI. All the new access requests were sent over the 2nd virtual group where RQ equal 1.


## 3.1. Protocol Description

In the suggested protocol, we capitalize on applying the DQRAP for accessing the system in order to keep the current LTE frame structure without any modification by applying the minislots on the time frame; we distributed the preambles to virtual groups where the DQRAP will be applied on each virtual group to enhance the access delay and the access success probability. However, the data transmission will follow the normal LTE procedure to eliminate any impact on the normal UE devices while accessing the system or during the data transmission phase. So, the first challenge in applying the DQRAP on LTE is how to implement this algorithm on the LTE without impacting the current operation of the normal UE devices. The second challenge is how to virtually restructure the LTE frame in such a way to be able to apply the DQRAP algorithm on the LTE. The final challenge is how to detect the order and status of the collided preamble between the others so the corresponding MD will enter the collision resolution queue based on its order. In this section, we will show how these challenges will be resolved.In the current specification of LTE, the total number of preambles (N
T
L) is divided into two parts: the contention-based part (N
C
B) available for user access and the contention-free (N
C
F) part reserved by eNodeB for special circumstances such as handover. The proposed access protocol is based on borrowing a part from the contention-based preambles (N
M
D) to be used by MDs in the access phase. This part should not be used by Human-to-Human (H2H) UE devices in order to avoid any possible collision. This can be done by making the UE devices see this part as contention-free. The notification takes place through the broadcast channel. The System Information Block 2 (SIB2) is used for this purpose. Thus, the available resources for both types are completely separated. These procedures guarantee that the normal UE device can use the traditional LTE technique to access the network. Figure 2 clarifies the preamble distribution from both UE devices and MDs perspective.Figure 2
Preamble distribution over MDs and UE devices.Direct implementation of DQRAP protocol within LTE requires a change of the LTE frame structure. This is because the access opportunities in the LTE (preambles) are implemented to be used at the same time due to its orthogonality which is not compatible with the DQRAP frame structure (minislots of the access part along with the data part). Therefore, in this paper, the LTE frame will be virtually restructured to obtain access part similar to minislots. The allocated number of preambles for MDs (N
M
D) will be distributed among N
g virtual groups. Each virtual group (denoted as G
i) has a number of preambles (N
p) in which each preamble is equivalent to a minislot in the original DQRAP. Figure 3 shows the distribution of preambles allocated for MDs among the virtual groups in both time and frequency directions.Figure 3
The distribution of the preambles among the virtual groups.When the MD wants to access the system, it selects one of the allocated preambles for MDs and sends it to the eNodeB. These preambles are sent in the allowed subframe for the random access request based on PRACH configuration index [14]. The configuration index indicates which subframe can be used to transmit the preamble. When the preamble is detected by the eNodeB, it will send the RAR within time window of 5 subframes [16]. 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 as shown in Figure 4. Since the operation of the DQAL is based on broadcasting information about the detection status of the preambles sent by the MDs, two-frame time interval is selected as the required time by eNodeB to detect the collision for any sent preamble. This interval is denoted by a Collision Resolution Interval (CRI). Thus, the DQAL protocol will virtually see the LTE frame periodicity as a number of consecutive CRIs. Each CRI can be seen as two parts, the data part and the access part. Within each CRI, the available number of access opportunities depends on the number of allocated RA slots in the two frames. By using this new virtual structure, the minislots of DQRAP are virtually mapped to the preambles of LTE.Figure 4
The Collision Resolution Interval (CRI) structure.


## 3.2. Preamble Status Detection

DQAL algorithm is based on the preamble status detection. Each MD tries to access the network, selects a virtual group, and sends an access request using one of the preambles that belong to this group. Each certain preamble has one of three states which are listed below along with the detection criteria. DQAL rules are based on these states.


### 3.2.1. Successful State

If message 3 is sent successfully to eNodeB, then the eNodeB will know that the corresponding preamble is sent without collision.


### 3.2.2. Collision State

There are two possibilities for collision; the first one will be detected by eNodeB and the second one will be detected by the MD. First collision might happen if two MDs (or more) send the same preamble in the same subframe while they are accessing the network and this preamble was decoded successfully by the eNodeB. In this case, message 3 for those MDs will collide and will not be decoded successfully by eNodeB. Accordingly, if eNodeB did not receive message 3 within one frame starting from the RAR, it will consider this preamble collided. Second collision might happen if two MDs (or more) send the same preamble in the same subframe while they are accessing the network and generate corrupted preamble. This preamble is not decoded successfully by eNodeB. In this case, the MD will not receive message 2 within one CRI and hence it will randomly select one of the remaining groups that is not selected by the other MDs to transmit its preamble, where the MD can know the occupied groups and the empty groups based on the status of each preamble and the resolution queue (RQ) value which is the number of the collided preambles waiting for retransmission.


### 3.2.3. Empty State

If a preamble is not used within the CRI by any MD, the eNodeB will consider it empty and will send the corresponding status as empty to all MDs


## 3.2.1. Successful State

If message 3 is sent successfully to eNodeB, then the eNodeB will know that the corresponding preamble is sent without collision.


## 3.2.2. Collision State

There are two possibilities for collision; the first one will be detected by eNodeB and the second one will be detected by the MD. First collision might happen if two MDs (or more) send the same preamble in the same subframe while they are accessing the network and this preamble was decoded successfully by the eNodeB. In this case, message 3 for those MDs will collide and will not be decoded successfully by eNodeB. Accordingly, if eNodeB did not receive message 3 within one frame starting from the RAR, it will consider this preamble collided. Second collision might happen if two MDs (or more) send the same preamble in the same subframe while they are accessing the network and generate corrupted preamble. This preamble is not decoded successfully by eNodeB. In this case, the MD will not receive message 2 within one CRI and hence it will randomly select one of the remaining groups that is not selected by the other MDs to transmit its preamble, where the MD can know the occupied groups and the empty groups based on the status of each preamble and the resolution queue (RQ) value which is the number of the collided preambles waiting for retransmission.


## 3.2.3. Empty State

If a preamble is not used within the CRI by any MD, the eNodeB will consider it empty and will send the corresponding status as empty to all MDs


## 3.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 collision resolution queue. All MDs have the same RQ value. The second counter pRQ is the position of each MD in the collision resolution queue. Each MD has a specific value based on his order in the queue. These counters are updated at the start of each CRI based on the information broadcasted by the eNodeB about the preambles detection status (successful, empty, or collided), bearing in mind the value of RQ is also broadcasted by the eNodeB before the start of each CRI.The same concept of switching mechanism, which enables or disables the EAB while using LTE, will be used in our DQAL algorithm. The following procedures describe the operation of the DQAL if it is enabled.At the beginning of each CRI, each MD makes some initialization based on the broadcast information (RQ value and preambles detection status). This initialization is called queuing discipline rule. Another rule is the request transmission rule, used to resolve the collision. The details of these two rules are described as follows.


### 3.3.1. Queuing Discipline Rule (Initialization)

(a)
At the beginning of each CRI, the MD will increment the value of RQ by one for each collided preamble.
(b)
IfR
Q
>
0, each MD reduces the value of RQ by min
⁡
(
R
Q
,
N
g
) units.
(c)
If the MD has no collided preamble, then it will setp
R
Q
=
0.
(d)
If the MD preamble in the previous CRI was collided, then the MD will calculate the value of pRQ based on the order of its preamble sequence between the other collided preambles and set it at the end of RQ. If the MD has not sent any preamble or the eNodeB did not detect the status of its sent preamble then the value of pRQ will follow the same update rule as RQ, but only if the initial value is other than zero.


### 3.3.2. Request Transmission Rule (Preamble Selection)

(a)
IfR
Q
<
N
g, each MD that has p
R
Q
=
0 [first access or its preamble status is not detected by eNodeB] randomly selects one of the preambles on group G
R
Q
+
1.
(b)
If the MD has (0
<
p
R
Q
<
N
g), it randomly selects one of the preambles of group G
p
R
Q.The process of DQAL protocol after being enabled is described in Algorithm1.Algorithm 1:Distributed queuing access protocol for LTE (DQAL).
(1)    Each step of the following will be repeated with every CRI
(2)    Initialization
(3)    eNodeB broadcast the RQ value and the preamble detection status
(4)    Each MD increment RQ by one for each collided preamble
(5)    if  (R
Q
>
0)  then
(6)     MDs Reduce the value of RQ by min
⁡
(
R
Q
,
N
g
)
(7)    end if
(8)    if  (MD’s preamble status detected as collided)  then
(9)     Calculate pRQ based on the preamble order
(10) end if
(11) Preamble selection
(12) if  (R
Q
<
N
g and p
R
Q
=
0)  do
(13)   Randomly select one of preambles on group G
R
Q
+
1
(14) end if
(15) if  (p
R
Q
<
N
g and p
R
Q
>
0)  do
(16)   Randomly select one of preambles of group G
p
R
Q
(17) end if
(18) else
(19)   Wait to the next CRI
(20) end ifAs can be seen from Algorithm1, the main strength of the proposed algorithm is based on allowing the new arrivals to choose preambles from the groups above G
R
Q. This allows avoiding any further collision with the existing collided requests waiting in the collision resolution queue. Furthermore, the algorithm helps the MDs to select the appropriate preamble that can be used to reduce the probability of collision. This will enhance both the success probability and access delay for MDs.The example shown in Figure5 clarifies how both the MDs and the normal UE device will access the network. The MDs will use the proposed algorithm to access the system while the normal UE devices will use the normal procedure of the LTE RACH. For simplicity, we assume that in the proposed algorithm there are three virtual groups; each one has three preambles as illustrated in the figure. On the other hand, the LTE frame has 6 preambles. The access request of the new arrival is represented with (∙) and the old collided access request that needs to be retransmitted is represented with (x). The operation of the proposed algorithm in each CRI is clarified as follows.Figure 5
Example of the operation of MDs and UE devices in the proposed algorithm.In the First CRI. There is no previous collision; therefore, RQ equal 0. The 2nd and the 3rd preambles are collided where two MDs select the same preamble to access the system while one MD selects the 1st preamble.In the 2nd CRI. The access requests sent on the 2nd collided preamble of the previous CRI were resolved on the first virtual group, while the access requests sent on the 3rd collided preamble in the previous CRI were retransmitted on the second virtual group. All the new access requests were sent over the 3rd virtual group where the number of the previous collisions waiting in the collision resolution queue is 2 (i.e., RQ equal 2).In the 3rd CRI. The previous collided preambles are resolved as follows:(i)
Second virtual group collided preambles: the access requests sent on the 3rd collided preamble were resolved on the first virtual group in the 3rd CRI.
(ii)
Third virtual group collided preambles: the access requests sent on the 2nd collided preamble were resolved on the second virtual group in the 3rd CRI. However, the access requests sent on the 3rd collided preamble were retransmitted on the third virtual group in the 3rd CRI.
(iii)
RQ =N
g = 3, therefore no new access requests are sent in this CRI.
In the 4th CRI. The access requests sent on the 2nd collided preamble of the previous CRI are resolved on the first virtual group in the 4th CRI. All the new access requests were sent over the 2nd virtual group where RQ equal 1.


## 3.3.1. Queuing Discipline Rule (Initialization)

(a)
At the beginning of each CRI, the MD will increment the value of RQ by one for each collided preamble.
(b)
IfR
Q
>
0, each MD reduces the value of RQ by min
⁡
(
R
Q
,
N
g
) units.
(c)
If the MD has no collided preamble, then it will setp
R
Q
=
0.
(d)
If the MD preamble in the previous CRI was collided, then the MD will calculate the value of pRQ based on the order of its preamble sequence between the other collided preambles and set it at the end of RQ. If the MD has not sent any preamble or the eNodeB did not detect the status of its sent preamble then the value of pRQ will follow the same update rule as RQ, but only if the initial value is other than zero.


## 3.3.2. Request Transmission Rule (Preamble Selection)

(a)
IfR
Q
<
N
g, each MD that has p
R
Q
=
0 [first access or its preamble status is not detected by eNodeB] randomly selects one of the preambles on group G
R
Q
+
1.
(b)
If the MD has (0
<
p
R
Q
<
N
g), it randomly selects one of the preambles of group G
p
R
Q.The process of DQAL protocol after being enabled is described in Algorithm1.Algorithm 1:Distributed queuing access protocol for LTE (DQAL).
(1)    Each step of the following will be repeated with every CRI
(2)    Initialization
(3)    eNodeB broadcast the RQ value and the preamble detection status
(4)    Each MD increment RQ by one for each collided preamble
(5)    if  (R
Q
>
0)  then
(6)     MDs Reduce the value of RQ by min
⁡
(
R
Q
,
N
g
)
(7)    end if
(8)    if  (MD’s preamble status detected as collided)  then
(9)     Calculate pRQ based on the preamble order
(10) end if
(11) Preamble selection
(12) if  (R
Q
<
N
g and p
R
Q
=
0)  do
(13)   Randomly select one of preambles on group G
R
Q
+
1
(14) end if
(15) if  (p
R
Q
<
N
g and p
R
Q
>
0)  do
(16)   Randomly select one of preambles of group G
p
R
Q
(17) end if
(18) else
(19)   Wait to the next CRI
(20) end ifAs can be seen from Algorithm1, the main strength of the proposed algorithm is based on allowing the new arrivals to choose preambles from the groups above G
R
Q. This allows avoiding any further collision with the existing collided requests waiting in the collision resolution queue. Furthermore, the algorithm helps the MDs to select the appropriate preamble that can be used to reduce the probability of collision. This will enhance both the success probability and access delay for MDs.The example shown in Figure5 clarifies how both the MDs and the normal UE device will access the network. The MDs will use the proposed algorithm to access the system while the normal UE devices will use the normal procedure of the LTE RACH. For simplicity, we assume that in the proposed algorithm there are three virtual groups; each one has three preambles as illustrated in the figure. On the other hand, the LTE frame has 6 preambles. The access request of the new arrival is represented with (∙) and the old collided access request that needs to be retransmitted is represented with (x). The operation of the proposed algorithm in each CRI is clarified as follows.Figure 5
Example of the operation of MDs and UE devices in the proposed algorithm.In the First CRI. There is no previous collision; therefore, RQ equal 0. The 2nd and the 3rd preambles are collided where two MDs select the same preamble to access the system while one MD selects the 1st preamble.In the 2nd CRI. The access requests sent on the 2nd collided preamble of the previous CRI were resolved on the first virtual group, while the access requests sent on the 3rd collided preamble in the previous CRI were retransmitted on the second virtual group. All the new access requests were sent over the 3rd virtual group where the number of the previous collisions waiting in the collision resolution queue is 2 (i.e., RQ equal 2).In the 3rd CRI. The previous collided preambles are resolved as follows:(i)
Second virtual group collided preambles: the access requests sent on the 3rd collided preamble were resolved on the first virtual group in the 3rd CRI.
(ii)
Third virtual group collided preambles: the access requests sent on the 2nd collided preamble were resolved on the second virtual group in the 3rd CRI. However, the access requests sent on the 3rd collided preamble were retransmitted on the third virtual group in the 3rd CRI.
(iii)
RQ =N
g = 3, therefore no new access requests are sent in this CRI.
In the 4th CRI. The access requests sent on the 2nd collided preamble of the previous CRI are resolved on the first virtual group in the 4th CRI. All the new access requests were sent over the 2nd virtual group where RQ equal 1.


## 4. Simulation Results and Comparison

In order to evaluate the performance of the DQAL, we will use the recommended settings defined by the 3 GPP in [16] and illustrated in Table 2. Also the 3 GPP recommended traffic model is defined in Table 3 for the MDs.Table 2
The 3 GPP suggested parameters for comparison [16].
Parameter
Setting
Total number of preambles per RA slot(
N
M
D
)
54
Number of dedicated preambles (contention-free) (N
C
F
)
10
Maximum number of preamble retransmissions
10
RA response window size
5 ms
PRACH configuration index
6Table 3
The 3 GPP recommended traffic model [16].
Parameter
Setting
Number of MDs
5 K, 10 K, and 30 K only (however we run the simulation on 1 K, 2 K, …, 30 K)
Arrival distribution
Beta distribution overT
Distribution period (T)
10 secIn the simulations carried out, the performance of DQAL is evaluated and compared with both the EAB (10 ACs are used) scheme and the conventional LTE scheme [9]. The following measures were evaluated in this comparison as per the recommendation in [5]:(1)
Access success probability (P
s): defined as the probability of successfully completing the random access procedures within the maximum number of preamble retransmission which is 10.
(2)
Access delay (D
a): defined as the time elapsed between the generation of the access request and the time of RA procedure completion.Then we will study the impact of the selectedN
p value on P
s, D
a and the collision probability P
c, which is defined as the ratio between the number of occurrences when two or more MDs send the same preamble and the overall number of access opportunities.As illustrated in [9], the EAB results in terms of D
a and P
s are varying with the selected EAB parameters. These parameters are T
p which is the number of subframes within a paging cycle and T
s that is the number of subframes between two consecutive broadcasted SIB14s. Also DQAL results are varying with the selected value of N
p. That is why we will compare the access delay of the two algorithms along with the LTE while fixing the P
s to certain constraints. The value of N
p is selected based on the number of the MDs in order to optimize the access delay according to the chosen constraint. For example, when the number of MDs equals 10 K and access success probability constraint equals 80%, N
p is 8 preambles. However, when the number of MDs equals 15 K under the same constraint, N
p is 6 preambles. On the other hand, under fixed number of resources (preambles), the value of N
g equals (N
M
D
∗ total number of RA slots per CRI/
N
g), where the total number of RA slots per CRI equals 4 when PRACH configuration index equal 6. The same as for the EAB the values of T
p and T
s are selected based on the number of the MDs in order to optimize the access delay according to the chosen constraint.Figures6 and 7 demonstrate the comparison of the access delay between the three algorithms under the condition that P
s is greater than 70%, 80%, and 90%, respectively, where the optimum parmaters are selected to provide the minimum delay with the selected P
s constraint.Figure 6
Access delay comparison whenP
s is greater than 70%.Figure 7
Access delay comparison whenP
s is greater than 80%.As shown in Figure6, the EAB and DQAL are enabled at certain value for the MDs number, where the collision coefficient will be more than 0.4. However, there is a big difference for the access delay of the EAB before and after this switching point compared to the DQAL. This difference is caused by the barring time in the EAB at which the MD is waiting till it receives the bitmap indicating that its AC is eligible to access the system. As shown from the figure, the LTE is performing well for low arrival rate till certain number of MDs; then it cannot satisfy the selected constraint. Both the EAB and DQAL can support higher arrival rate under the required success probability constraint.In Figure6, the DQAL performs better than the EAB in terms of D
a until the number of MDs reaches 26 K.Figure7 illustrates that increasing the P
s constraint will result in increasing the access delay of the EAB, especially when the number of the MDs is greater than 27 K MDs. In order to satisfy the P
s constraint, the paging cycle will be increased and the MDs will be waiting for a long period till they detect the paging occasion and check the corresponding bitmap. So the access delay will increase.Figure8 demonstrates that the number of the maximum supported MDs for the LTE is decreased from 19 K MDS to 17 K MDS when the required P
s constraint is increased from 70% to 90%. This is because high number of MDs will cause more collisions between the MDs and accordingly the retrials will increase, causing lower success probability. On the other hand, the DQAL access delay results are better than the EAB especially when the required constraint for the access success probability increased. The reason behind this significant delay in the EAB is that having higher access success probability requires increasing the paging cycle. Accordingly, the access delay will increase where the MDs shall wait for longer time till they have permission to send their access requests.Figure 8
Access delay comparison whenP
s is greater than 90%.Figure9 demonstrates the access delay as a function of N
p given that there are 2 RA slots per frame. The performance of the DQAL was studied with two traffic scenarios: 10,000 MDs for medium traffic and 20,000 MDs for heavy traffic. Under fixed capacity condition (fixed number of preambles reserved for MDs), any increase in N
p will be reflected in the total number of the virtual groups (N
g). Therefore as shown in Figure 9, there are flipping points (6, 8, 13, 18, 24, 27, and 36), where after these points the access delay will increase rapidly. This is because the system capacity (total number of preambles per CRI) is completely utilized and distributed over the virtual groups without any loss, and, after these points, any increase in the N
p value will decrease the total number of the virtual groups by one leaving unused preambles. Therefore, the N
p value should be selected to achieve that condition and utilize all the M2M preambles. As demonstrated from Figure 9, there is switching point for N
p (8 preambles for 10 K MDs and 6 preambles for 20 K MDs) at which the minimum value for the access delay is obtained, where increasing N
p before this point will minimize the collision probability over the same virtual group. Consequently, the access delay will be decreased. Also after this point, increasing the N
p value will minimize the number of the virtual groups that are responsible for handling the collision of the previous CRI and the new access request. Therefore, the access delay will increase. Accordingly, in order to achieve minimum delay, the N
p value should be selected carefully based on the load of the system as clarified above.Figure 9
Average access delay as a function ofN
p.Figure10 shows that increasing the N
p value results in increasing the access success probability. Initially, there is rapid increase in P
s, and then it is going to be saturated a bit lesser than 100%. The reason of this rapid increase is that more access resources (preambles) on the same virtual group will result in increasing the probability of accessing the system successfully before reaching the maximum number of retrials, while the reason of the observed saturation is that further increase in N
p will result in accumulating the new access request and resolving the old collision, so the access success probability will tend to be saturated a bit lesser than 100%.Figure 10
Access success probability as a function ofN
p.Figure11 demonstrates that increasing N
p will result in reducing the collision probability rabidly to a certain extent where the probability of having a collision between the MDs over the same virtual groups will decrease.Figure 11
Collision probability as a function ofN
p.Figure12 compares the access delay with different values for the RA slots per frame under fixed value for N
p (6 preambles). After the activation of the DQAL, there was a rapid increase when the number of the RA slots was one per frame, although when there are 2 RAs per frame the access delay increases slowly. This is because the number of the increased preambles in the 2 RA slots scenario will result in more virtual groups. Accordingly, the first access for MDs will not be blocked for long time and also the old collision will be resolved fast.Figure 12
Average access delay for MD as a function on RA slots per frame.


## 5. Conclusion and Future Work

In this paper, we introduced an efficient protocol (DQAL) to solve the access issue of M2M communication over the LTE network using the Distributed Queuing algorithm. This protocol will keep the access procedure of LTE for H2H unchanged. Accordingly, its implementation will be very smooth. The original DQRAP is adapted to be fit with the frame structure and its specifications in LTE. The optimum design parameters in terms of the number of virtual groups and the number of preambles per each group are determined based on the traffic load. The performance of the proposed protocol is compared by the EAB algorithm which is chosen by the 3 GPP as the most feasible baseline solution to resolve the congestion of the RACH. Simulation results show that the access delay of DQAL is better than the EAB under certain access success probability constraints. This is because the proposed technique is designed to efficiently resolve the collision and utilize the access resources to a great extent. Finally, we can conclude that the proposed DQAL protocol performs efficiently for supporting M2M services over LTE.



---

*Source: 3758507-2016-08-18.xml*