Rémi Bonnefoi
email: remi.bonnefoi@centralesupelec.fr

Tarcisio F Maciel
email: maciel@ufc.br

C Estêvão
email: estevao@ufc.br

R Fernandes

Latency Efficient Request Access Rate for Congestion Reduction in LTE MTC

The development of Machine-Type Communication (MTC) in the Long Term Evolution (LTE) standard can lead to an overuse of the Physical Random Access Channel (PRACH). An efficient way to avoid it consists in reducing the number of requests done by end-devices. In this paper, we first study the probability of collision in a congested LTE-MTC network. As a second step, we analyze the latency in the network as a function of the request access rate. Then, we propose a closed-form for a sub-optimal request access rate. We finally conduct numerical simulations in order to assess the performance of the proposed approximation.

I. INTRODUCTION

The development of the Internet of Things (IoT) has led to an increase in the number of devices 1 with wireless connectivity and to the development of Machine-Type Communication (MTC). MTC can be done in dedicated networks or can operate in already deployed cellular networks [START_REF] Raza | Low Power Wide Area Networks: An Overview[END_REF].

This second solution can be limited as cellular networks, such as the Long Term Evolution (LTE) standard developed by the Third Generation Partnership Project (3GPP), are not designed to be used by a very large number of IoT devices. As a consequence, the development of MTC in LTE networks can be restricted by the congestion of the Radio Access Network (RAN) and more precisely of the Physical Random Access Channel (PRACH) [START_REF] Cheng | Overload control for Machine-Type-Communications in LTE-Advanced system[END_REF].

The problem of congestion in LTE MTC can be solved using different techniques. Among others, the evolved Node B (eNB) can prevent devices from accessing the network during predefined periods [START_REF] Chang | Congestion Control for Machine-Type Communications in LTE-A Networks[END_REF] or can adapt the backoff interval [START_REF] Zhan | Throughput optimization for massive random access of M2M communications in LTE networks[END_REF]. Another efficient solution to reduce congestion in LTE-MTC lies in adapting the Request Access Rate. This solution is called Access Class Barring (ACB). With it, the eNB broadcasts an ACB factor q. Then, each time a device wants to transmit to the eNB, it computes a uniform random number in [0; 1] and, if this number is below q, transmits the request [START_REF] Duan | Dynamic access class barring for M2M communications in LTE networks[END_REF], [START_REF] Tavana | Congestion control for bursty M2M traffic in LTE networks[END_REF].

Part of the literature about congestion reduction, including [START_REF] Duan | Dynamic access class barring for M2M communications in LTE networks[END_REF], [START_REF] Tavana | Congestion control for bursty M2M traffic in LTE networks[END_REF], does not consider the effect of retransmissions on the probability of collision in the network. In this paper, we consider this effect, where the retransmission mechanism of an end-device can be modeled using a Markov chain. This modeling is inspired by the one proposed in [START_REF] Bianchi | Performance analysis of the IEEE 802.11 distributed coordination function[END_REF] for WiFi (IEEE 802.11) networks. Moreover, a similar modeling has been proposed in [START_REF] Yang | Performance Analysis and Parameter Optimization of Random Access Backoff Algorithm in LTE[END_REF] for LTE MTC. In [START_REF] Zhan | Throughput optimization for massive random access of M2M communications in LTE networks[END_REF], this modeling is 1 Herein, we use the term device to refer to User Equipment (UEs). used for congestion reduction. However, therein the authors focus on the optimization of the throughput whereas, in the present paper, we focus on the latency.

In this article, we study a solution similar to ACB, we assume that instead of starting a Random Access (RA) procedure each time devices have data to transmit, they start fewer RA procedures and transmit more data in the Physical Uplink Shared Channel (PUSCH) once the access is granted. In other words, suppose a sensor that makes a measure each time there is a change in the measured physical parameter. Instead of making a RA procedure after every measure, the device makes a RA procedure with a probability p R . The aim of this paper is to find a closed-form approximation for the value of p R which minimizes the latency. For this purpose, we proceed in two steps: as a first step, we derive an approximation for the probability of collision in congested LTE-MTC networks; then, as a second step, we express the latency in the considered scenario and we use our approximation for the probability of collision in order to derive a closed-form approximation for the value of p R which minimizes the latency.

The rest of this paper is organized as follows. The system model is introduced in section II. The closed-form approximation for the probability of collision is proposed in section III. In section IV, we derive the expression of the latency in the network and then an approximation for the value of p R which minimizes it. Numerical simulations are conducted in section V and section VI concludes this paper.

II. SYSTEM MODEL

We assume an LTE eNB which is shared by N end-devices (e.g. sensors). These devices make uplink communications to the eNB. When one of them wants to transmit data to the LTE eNB, it makes a request into the PRACH. If the request is successful, some resource blocks are granted to this device in the PUSCH. Then, these resource blocks are used by the end-device to transmit its packets. We assume that we have one PRACH slot per frame and we denote by T f the frame duration.

We model the behavior of an end-device with the Markov chain of Fig. 1, which is inspired by the one proposed in [START_REF] Zhan | Throughput optimization for massive random access of M2M communications in LTE networks[END_REF]. It is also similar to the model used in [START_REF] Yang | Performance Analysis and Parameter Optimization of Random Access Backoff Algorithm in LTE[END_REF], but where we have neglected the probability to reach the maximum number of repetitions. In idle mode, the device collects data (i.e., by making some measurements). The probability that a device makes a new measure follows a Poisson process of intensity λ. Thus, there is a probability p = λT f that a device has new data to transmit between two PRACH slots. We assume that λ is small enough so that at most one measurement is done between two PRACH slots. As to reduce contention in the network, instead of requesting access to the eNB each time it has a packet to transmit, a device makes a request with a probability p R < p. Moreover, in our analysis of the latency, we assume that p R is small compared to p.

For the sake of simplicity, we suppose that, once the device starts the transmission procedure, it stops collecting data. The request access is a four-step procedure [START_REF] Hasan | Random access for machineto-machine communication in LTE-advanced networks: issues and approaches[END_REF]. We consider a contention-based RA and, in that case, during the first step the end-device that needs to access the eNB chooses one of the N zc = 64 possible preambles. If this preamble is chosen by only one device, it can be decoded and the request can be granted by the eNB. If this preamble is chosen by more than one device, there is a collision and the request fails. If the request is successful, we assume that the end-device can transmit its data to the eNB. The first step of this procedure is the focus of this paper, in which we assume that the PRACH channel is the limiting factor. In case of failure, the enddevice waits for a random number of PRACH slots uniformly distributed between 0 and m -1, where m denotes the length of the backoff interval. The value of m depends on the Backoff Indicator (BI) transmitted by the eNB [START_REF] Gpp | Technical Specification Group Radio Access Network Evolved Universal Terrestrial Radio Access (E-UTRA) Medium Access Control (MAC) protocol specification[END_REF]. In all this paper, we assume that we have one PRACH slot per frame and we denote T f = 10 ms as the frame duration, which thus corresponds to the delay between two PRACH slots.

In case of success of the RA procedure, all the data collected since the last transmission is transmitted to the eNB in the PUSCH. After the end of the transmission process, the device switches to idle mode and collects new data for the next transmission. In the following, p c denotes the probability that a request transmitted by a device collides with another request sent by another device. In other words, p c is the probability that the preamble chosen by the end-device is chosen by at least one other end-device.

III. CLOSED-FORM APPROXIMATION FOR THE PROBABILITY OF COLLISION IN HEAVY TRAFFIC

In this section, we derive a closed-form approximation for the probability of collision in the studied network. As a first step, we compute the probability that a device is transmitting. In the case where p R > 0 and p c > 0 the Markov chain of Fig. 1 is ergodic, assuming a steady state, we can compute the probability that a device is in each state by finding the expression of the vector:

x = x i x t x w m-1 . . . x w 1 T , (1)
where x i is the probability that the device is in idle mode, x t the probability that the device is transmitting a request and x w k is the probability that the device is in waiting state k (see Fig. 1). This vector verifies:

Mx = x, ( 2
)
where M is the transition matrix of the Markov chain introduced in Fig. 1. This matrix can be expressed as:

M =                  1 -p R 1 -p c 0 • • • 0 0 p R p c m 0 • • • 0 1 0 p c m 0 • • • 0 0 . . . . . . 1 • • • 0 0 . . . . . . . . . . . . . . . . . . 0 p c m 0 • • • 1 0                  . ( 3
)
Solving the linear system of (2) and using the normalization equation of the Markov chain, we derive the expression of x t , the probability that the device is transmitting a request, as:

x t = 1 1 + (1-p c ) p R + p c (m-1) 2 . ( 4
)
Moreover, assuming that the probability of collision follows a Bernoulli process, we can express it as:

p c = 1 -1 - x t N zc N -1 ≈ N ≫1 1 -e -N x t Nz c . (5)
As x t is a function of p c , equation ( 5) is an implicit expression of p c . In the following, we use a first order Taylor expansion in order to derive a closed-form approximation for the probability of collision when p c is close to 1. For that purpose, we rewrite x t as:

x t = 2 m + 1 1 1 + 2(1-p c ) m+1 1 p R -(m-1) 2 . ( 6
)
In case where p c is close to 1 or where m-1 2 ≈ 1 p R , we can use the first order Taylor expansion:

1 1+x ≈ x≈0 1 -
x, in order to provide an approximation for the probability of transmission:

x t ≈ 2 m + 1 1 - 2(1 -p c ) m + 1 1 p R - (m -1) 2 . ( 7
)
Inserting the approximation of equation ( 7) in [START_REF] Duan | Dynamic access class barring for M2M communications in LTE networks[END_REF], we obtain:

p c ≈ 1 -e -N Nz c 2 m+1 1-2(1-pc ) m+1 1 p R -(m-1) 2 .
(8) This equality can be rewritten:

-N N zc 4(1 -p c ) (m + 1) 2 1 p R - m -1 2 e -N Nz c 4 (m+1) 2 (1-p c ) 1 p -m-1 2 ≈ -N N zc 4 (m + 1) 2 1 p R - m -1 2 e -N Nz c 2 m+1 . (9)
Moreover, equation ( 9) has a solution if and only if:

p R ≥ 1 e N Nz c 2 m+1 -1 N z c N (m+1) 2 4 + m-1 2 . ( 10
)
In order to find a closed-form approximation for p c , we apply the W-Lambert function in equation ( 9). This function is the reciprocal bijection of the function x → xe x [START_REF] Corless | On the Lambert W function[END_REF]. In order to obtain realistic values for the probability of collision, i.e., that belong in [0; 1], we apply the main branch of this function denoted W 0 . We finally obtain a closed-form approximation for the probability of collision:

p c ≈ 1 + W 0 -N N z c 4 (m+1) 2 1 p R -m-1 2 e -N Nz c 2 m+1 N N z c 1 p R -m-1 2 4 (m+1) 2 . ( 11
)
We now conduct some numerical simulations in order to validate the proposed approximation. In Fig. 2, we display the probability of collision versus the probability of access in the studied network with N = 2000 users and for different values of m. These values of m are compliant with the LTE standard [START_REF] Gpp | Technical Specification Group Radio Access Network Evolved Universal Terrestrial Radio Access (E-UTRA) Medium Access Control (MAC) protocol specification[END_REF]. The probability of collision is either computed using empirical simulations or using the approximation of equation [START_REF] Corless | On the Lambert W function[END_REF]. We can see that the proposed approximation is very precise when the probability of collision is high. Moreover, we can see that the precision of the proposed approximation is reduced when the backoff interval is larger and the probability of collision lower.

In the following, we use the approximation derived here to find the value of p R which minimizes the latency.

IV. VALUE OF p R WHICH MINIMIZES THE LATENCY

A. Latency

In this article, we focus on the latency of the access to the eNB which is the delay between the first PRACH slot in which the request for a packet can be transmitted (i.e., the first PRACH slot after the measure) and the successful reception of the PRACH preamble for this packet. We recall here that, instead of transmitting a request each time it has a packet to transmit, i.e., with a probability p, each device transmits a request to the eNB with a probability p R . And, in case of success of the RA procedure, transmits more data in the PUSCH. Moreover, the device stops collecting data once it starts the RA procedure. In such case, the average latency of the access can be decomposed as: where E[L w ] is the queueing delay which is the time between the first PRACH slot during which the device could make its request for this packet and the PRACH slot during which it starts the RA procedure. E[L a ] denotes the delay between the beginning of the random access procedure and the successful decoding of the preamble by the eNB. We start by calculating E[L w ]. Assuming that p R is small compared to p, we can model the packet queue in each device, in idle mode, with the queue of Fig. 3. In the steady state, we can compute the probability that there is k packets in the queue which is the probability that the queue is in state k. For that purpose, we can deduce, from Fig. 3, a system of linear equations that represents the state of the system. Solving this system and using the normalization equation of the Markov chain, we derive the probability that the queue is in state k:

E[L ] = E[L w ] + E[L a ], (12)
x k = p p + p R k p R p + p R , (13)
where x k is the probability that the device has k packets waiting in its queue. We can deduce from equation ( 13) the average number of packets in the queue:

E[N p ] = p R p + p R ∞ k=1 k p p + p R k = p p R . (14)
Equation ( 14) is derived using the formula of the derivative of a geometric series. We can now use the Little's formula [START_REF] Little | A Proof for the Queuing Formula: L = λW[END_REF] to derive the average delay in the queue:

E[L w ] = T f p R . ( 15
)
We now compute the latency between the beginning of the RA procedure and the successful reception of the preamble. For that purpose, we use the law of total expectation:

E[L a ] = +∞ k=1 P(N t = k)E[L a |N t = k], (16)
where N t denotes the number of times the device transmits the preamble until a transmission without collision. Its expression can be written as:

P(N t = k) = p k-1 c (1 -p c ).
(17) Moreover, the average time required to transmit N t times a preamble is:

E[L a |N t = k] = (k -1)E[T fail ] = (k -1)mT f 2 , ( 18
)
where E[T fail ] is the average time between a collision and the next transmission of a preamble by the end-device. Then,

E[L a ] = mT f 2 (1 -p c )p c +∞ k=1 (k -1)p k-2 c = mT f 2 1 1 -p c - mT f 2 (19)
Equation ( 19) is obtained using the derivative of a geometric series. Finally, the total latency can be expressed as:

E[L ] = mT f 2 1 1 -p c - mT f 2 + T f p R . (20)
We can see in equation ( 20) that E[L w ] decreases with p R whereas E[L a ] increases with p R . In the following, we derive a closed-form approximation for the value of p R which minimizes the delay. This optimum is a trade-off between

E[L w ] and E[L a ].
B. An approximation for the optimal Request Access Rate

In the following, we denote γ = 1 p R . The function E[L ](γ) has a linear asymptote for γ → +∞ and an asymptotic behavior for γ → 1. This can be explained as follows:

• When γ is large, the probability of collision becomes negligible and the latency is equal to E[L w ] which is a linear function of γ. • When γ is low, the probability of collision is high and, p c can be approximated by equation [START_REF] Corless | On the Lambert W function[END_REF]. We will see that, in that case, the latency can be approximated by a linear function. A consequence of these observations is that the optimum can be approximated by the intersection of these two asymptotes.

We start by calculating the asymptote when γ → +∞. In that case, p c → 0 and the asymptote of the latency is:

E[L ](γ) ≈ γ →+∞ E[L w ](γ) = y(γ) = T f γ. (21)
We now analyze the asymptotic behavior of the latency for low values of γ. When γ is low, the network is congested and p c can be approximated by equation [START_REF] Corless | On the Lambert W function[END_REF]. As a consequence, the latency can be approximated by:

E[L ] = T f γ - mT f 2 + - mT f 2 N Nz c γ -m-1 2 4 (m+1) 2 W 0 -N Nz c 4 (m+1) 2 γ -m-1 2 e -N Nz c 2 m+1 . (22)
Moreover, we have x W 0 (x) = e W 0 (x) , ∀x ≥ -e -1 [START_REF] Corless | On the Lambert W function[END_REF]. Using this property, the latency of equation ( 22) can be rewritten:

E[L ] = T f γ - mT f 2 + m T f 2 e W 0 -N Nz c 4 (m+1) 2 γ-m-1 2 e -N Nz c 2 m+1 + N Nz c 2 m+1 . ( 23
)
The function x → e W 0 (x) can be approximated by a linear function [START_REF] Hoorfar | Inequalities on the Lambert W function and hyperpower function[END_REF]. We can consequently approximate (23) by one of the tangents of the latency. A good choice is to approximate the latency by its tangent at the point γ = m-1 2 . Indeed, at this point, the approximation of equation ( 7) is always valid. The derivative of

E[L ] at γ = m-1 2 is: ∂E[L ] ∂γ m -1 2 = T f - mT f N 2N zc 4 (m + 1) 2 . ( 24
)
We can use this derivative in order to approximate the latency by its tangent at the point γ = m-1 2 . The equation of this tangent is: And the optimal value of γ can be approximated by the value of γ denoted γ i which verifies y(γ i ) = z(γ i ). We finally derive,

z(γ) = ∂E[L ] ∂γ m -1 2 × γ - m -1 2 + E[L ] m -1 2 . ( 25
)
γ i = N N z c 2(m-1) (m+1) 2 + e N Nz c 4 (m+1) 2 -1 N N z c 4 (m+1) 2 . ( 26
)
The optimal value of p R is the inverse of γ i .

V. SIMULATION RESULTS

We now use numerical simulations in order to validate our approach. Besides, we assess the performance of the proposed approximation. For that purpose, we compute the latency with (20) for different values of p R (or γ) and we compare the latency obtained with our approximation of γ with the optimal value of the latency.

As a first step and in order to validate our approach, we display in Fig. 4 the two asymptotes with N = 2000 and m = 24. We can see that the value γ i at which the asymptotes intersect is near the optimal value of γ.

In order to analyze the performance of the proposed solution, we display in Fig. 5 the evolution of the latency versus N, the number of users, for different values of m, the backoff interval. In these figures, we compare four strategies: the proposed one, the optimal one, and two strategies with a fixed value of p R . We can see that, for a given value of m, the proposed policy provide near optimal performance over a wide range of values of N. The performance of the proposed solution is reduced when N is large or low. This result can be explained by analyzing the probability of collision p c . In the case where N is low, the probability of collision is lower when the network is saturated. In that case, the proposed approximations for p c is less precise. This causes errors and reduces the performance of the proposed solution. Moreover, when N is large, p c is near 1 and a small error on p c causes large error on the latency which depends on 1 1-p c . The proposed solution is consequently less accurate.

We now compare our strategy with a situation in which p R does not vary with the number of users. As an example, we analyze in Fig. 5c that choosing p R = 0.01 provides near optimal performance when the number of devices is between 3000 and 4000. However, this value of p R is no longer optimal when N increases. In the case where N = 5000, the proposed policy provides a 33% gain compared to the use of a fixed value of p R equal to 0.01.

VI. CONCLUSION

In this paper, we first derive a closed-form approximation for the probability of collision in the PRACH of a congested LTE MTC network. Then, we derive the expression of the latency in the studied network. Afterwards, we use the approximation previously derived to derive a closed-form approximation for the value of the request access rate which minimizes the latency. Finally, we conduct numerical simulations in order to validate our approach. In our future work, we will use the results provided in this paper to optimize other parameters such as the backoff interval. We also envision to analyze the effect of clustering in LTE MTC.

Fig. 1 .

 1 Fig. 1. Markovian modeling of the behavior of an end-device.

Fig. 2 .

 2 Fig. 2. Probability of collision with 2000 users and for different values of m, the length of the backoff interval.

Fig. 3 .

 3 Fig.3. The behavior of a device in idle mode can be modeled by a queue. We have a probability p to have a new packet in the queue and a probability p R that the device starts the transmission process and transmits all the packets.

Fig. 4 .

 4 Fig. 4. Evolution of the latency versus γ with N = 2000, m = 24 and with different values of p. The proposed approximation provides sub-optimal results.

Fig. 5 .

 5 Fig. 5. Evolution of the latency as function of the number of devices N for different values of m: comparison of the proposed approach versus the optimum one and strategies with fixed p R .

ACKNOWLEDGEMENT

This work has been funded by Université Bretagne Loire (UBL) and by Région Bretagne, France. T. F. Maciel would like to acknowledge CNPq for its financial support under the grants 426385/2016-0 and 308398/2015-7.