Edoardo Longo

Alessandro E C Redondi

Matteo Cesana

Pairing Wi-Fi and Bluetooth MAC Addresses Through Passive Packet Capture

The majority of smart devices used nowadays (e.g., smartphones, laptops, tablets) is capable of both Wi-Fi and Bluetooth wireless communications. Both network interfaces are identified by a unique 48-bits MAC address, assigned during the manufacturing process and unique worldwide. Such addresses, fundamental for link-layer communications and contained in every frame transmitted by the device, can be easily collected through packet sniffing and later used to perform higher level analysis tasks (user tracking, crowd density estimation, etc.). In this work we propose a system to pair the Wi-Fi and Bluetooth MAC addresses belonging to a physical unique device, starting from packets captured through a network of wireless sniffers. We propose several algorithms to perform such a pairing and we evaluate their performance through experiments in a controlled scenario. We show that the proposed algorithms can pair the MAC addresses with good accuracy. The findings of this paper may be useful to improve the precision of indoor localization and crowd density estimation systems and open some questions on the privacy issues of Wi-Fi and Bluetooth enabled devices.

I. INTRODUCTION

The majority of smart mobile devices (smartphones, laptops, tablets, etc.) used nowadays are equipped with both Wi-Fi and Bluetooth wireless communication interfaces. The former type of interface is generally used for internet access, while the latter is the standard for building wireless personal area network (WPAN) and exchanging data over short distances to other devices or communicating with input/output wireless interfaces (keyboards, headphones, etc.).

Both the Wi-Fi and Bluetooth interfaces are identified by 48-bits addresses, known as the Media Access Control (MAC) addresses. Such addresses are unique worldwide, and are embedded into the network hardware during the manufacturing process, or stored in firmware, and designed not to be modified. These addresses are fundamental for link layer communications and are therefore contained in every frame transmitted by a mobile device on either the Wi-Fi or Bluetooth interface. Interestingly, there are some management frames which mobile devices transmit on the Wi-Fi and Bluetooth interfaces even without a proper association with a network and without any user data to deliver. For what concerns Wi-Fi, probe requests frames are used to collect information on the network served by access points in range. As for Bluetooth, inquiry scan frames are transmitted to discover available devices and their information. Both kind of frames are transmitted without encryption, may be easily captured with cheap off-the-shelves sniffers and a large body of literature has recently studied how to exploit such information to provide higher layer services. Indeed, capturing and analyzing wireless packets carrying a unique device identifier allows to track users in space and time, forming the basis for passive device localization, user behavior estimation, market analysis and many others [START_REF] Redondi | Building up knowledge through passive Wi-Fi probes[END_REF].

Although in some devices the Wi-Fi and Bluetooth MAC addresses are assigned at the same time during the manufacturing process and are therefore consecutive [START_REF] Martin | A study of MAC address randomization in mobile devices and when it fails[END_REF], in the majority of the cases they are completely unrelated. Therefore, in this work we present a system capable of pairing a device Wi-Fi MAC address with its corresponding Bluetooth MAC identifier. We observe that pairing such two different identifiers, linking them to a single physical device may be used in several situations:

• In localization systems, a device can be tracked more precisely by fusing information coming from the two network interfaces [START_REF] Jindan | Improving crowdsourced Wi-Fi localization systems using Bluetooth beacons[END_REF], or switching between the two depending on the availability. The same applies to pedestrian flow estimation [START_REF] Naini | Population size estimation using a few individuals as agents[END_REF], [START_REF] Schauer | Estimating crowd densities and pedestrian flows using Wi-Fi and Bluetooth[END_REF] or crowd density estimation systems [START_REF] Weppner | Participatory Bluetooth scans serving as urban crowd probes[END_REF], [START_REF] Bullock | Anonymous Bluetooth probes for airport security line service time measurement: the Indianapolis pilot deployment[END_REF].

• Due to the large spread of Wi-Fi sniffers and probe requests analysis systems [START_REF] Barbera | Signals from the crowd: Uncovering social relationships through smartphone probes[END_REF], [START_REF] Cunche | I know your MAC Address: Targeted tracking of individual using Wi-Fi[END_REF], device vendors are recently inserting privacy mechanisms to transmit Wi-Fi probe requests with a fake, randomized MAC address [START_REF] Vanhoef | Why MAC address randomization is not enough: An analysis of Wi-Fi network discovery mechanisms[END_REF]. Since this is not done in Bluetooth, pairing the same Bluetooth MAC address with multiple randomized Wi-Fi MAC addresses belonging to the same device basically cracks this privacy mechanism.

• The mechanism can also be used as an adversary weapon: a malicious entity can double is effectiveness by committing blended attacks on both interfaces creating denial of services (DoS) attacks, battery drain attacks or exploiting other vulnerabilities. As an example, Moyers et al. [START_REF] Moyers | Effects of Wi-Fi and Bluetooth battery exhaustion attacks on mobile devices[END_REF] demonstrate that such attacks can accelerate battery depletion by as much as 18.5%.

II. SCENARIO

The proposed system leverages a network of N synchronized sniffers deployed at fixed and known locations in the environment, equipped with both Wi-Fi and Bluetooth wireless interfaces and able to capture packets transmitted with both technologies. Assume M Wi-Fi and Bluetooth enabled mobile devices are present in the environment. For each packet transmitted by the m-th device on any interface and captured by the n-th sniffer, two pieces of information are extracted and stored in a local database: the Wi-Fi (w m ) or Bluetooth (b m ) address of the transmitting device, and the RSSI r m (s m ) associated with the captured packet on the Wi-Fi (Bluetooth) interface. The system is operated according to discrete time slots: at the end of each slot, the local information from the N sniffers are periodically transmitted to a central controller, which constructs two M × N matrices R and S where each element r m,n (s m,n ) contains the average RSSI measurement of the overall Wi-Fi (Bluetooth) packets transmitted by device m and received by the n-th sniffer. Note that each row of R (S) corresponds to a different Wi-Fi (Bluetooth) MAC address w m (b m ). In the following, we present different algorithms for pairing each w m with the corresponding b m , starting only from the knowledge of matrices R and S. Two different types of methods are presented: signal mapping algorithms and location-based algorithms.

A. Signal mapping algorithms

This first class of algorithms maps directly one matrix into the other and performs address pairing according to signal similarity.

1) RSSI normalization: The RSS indicator depends primarily on the transmitter-receiver distance and on the transmitter output power. In our scenario, the Wi-Fi and Bluetooth interfaces of a mobile device are colocated (hence the transmitterreceiver distances are the same), but the output power of the two interfaces may be different. A possible method to remove such difference is to normalize each row of R and S to its maximum RSSI value, so that it contains only values between 0 and 1. After normalization, rows of R and S can be compared through standard distance metrics (e.g. Euclidean distance, cosine similarity) for finding the best-matching pair. This algorithm is very simple and cheap to execute, and does not require any training.

2) RSSI-to-distance: A more complex approach consists in converting both Wi-Fi and Bluetooth RSS measurements in physical distances. Once converted to distance measurements, the rows of two matrices can be compared. In this work, the well known log-distance path loss model is used to convert a RSSI measurement s into a distance measurement d, that is:

r = r 0 -α log d d 0 (1)
where r 0 is the RSSI measured at d 0 meters and α is the path loss exponent. In this work, r 0 and α are estimated a priori for each interface (Wi-Fi or Bluetooth) and independently for several device manufacturers using training data. In details, each transmitter device is located at known distances from a sniffer and RSSI data is collected. The log-distance path loss model is then estimated used least square fitting, as shown in Figure 1(a) and (b).

3) RSSI-to-RSSI: Another option to perform signal mapping is to learn a transformation from one domain to the other. Assuming again that Wi-Fi and Bluetooth signals propagate according to the log-distance path-loss model, we have:

r = r 0 -α log d d 0 (2)
s = s 0 -β log d d 0 , (3)
where r 0 , s 0 and α, β capture the difference output powers and the path loss exponents of the Wi-Fi and Bluetooth interfaces, respectively. After some algebra, it is easy to show that:

r = (r 0 - α β s 0 ) + α β s = θ 0 + θ 1 s (4)
The last equation [START_REF] Naini | Population size estimation using a few individuals as agents[END_REF] shows that there exists a linear transformation between Wi-Fi and Bluetooth measurements corresponding to the same device. Therefore, we first learn the linear coefficients θ 0 and θ 1 for each device manufacturer using training data (see Figure 1(c)), and we use them to transform one matrix measurements into the other. Finally, the rows of the two matrices can be compared using standard distance metrics.

B. Location-based algorithms

The second class of algorithms performs first a localization process, in which each address is assigned to a position in a 2D coordinate system. Address pairing is then performed by linking to each Wi-Fi address its closest Bluetooth address in space.

1) Trilateration:

This method builds on the RSSI-todistance algorithm presented in Section II-A2, further processing the estimated distance measurements to obtain a 2D location for each captured device. First, each row of the Wi-Fi measurement matrix R is converted into distance measurements using the log-distance path loss models learned for each device manufacturer. Each row of the resulting distance matrix is composed of measurements d m,n capturing the distance from the m-th device to the n-th sniffer, whose 2D coordinates are x n . Localization can be performed solving a trilateration problem of the form:

min xm N n=1 ( x m -x n 2 -d m,n ) 2 ∀m, (5)
using the gradient descent method. The process is repeated starting from the Bluetooth measurement matrix S. Finally, address pairing is performed comparing the estimated locations. 2) Fingerprint: The fingerprint method consists of two phases. In a first off-line phase, the system is calibrated by sampling uniformly the environment at p spatial positions. A test device is placed at each position x p , and two fingerprinting databases are constructed by collecting the Wi-Fi and Bluetooth RSSI measurements received at the sniffers, along with a label indicating the test position. In the on-line phase, upon receiving the RSSI measurements from the sniffer, k-nearest neighbor search is used to retrieve the k closest entries (in signal space) and the corresponding labels. The final location x m is retrieved computing a weighed average of the k closest position labels. Weights are chosen to be inversely proportional to the distance (in signal space) between the input fingerprint and the k closest in the database.

III. EXPERIMENTS

In order to evaluate the performance of the proposed algorithms we carried out an experiment in a controlled scenario. Six sniffer devices are deployed in an indoor environment of approximately 50 square meters, as reported in Figure 2. Each sniffer is built on top of a Raspberry Pi 3 model B board, equipped with Wi-Fi and Bluetooth communication capabilities. The OS running on the machines is Raspbian Jessy version 4.9.24. The system is synchronized using NTP servers and it is remotely controlled through ClusterSSH over the Wi-Fi network. This facilitated the experimenter to have complete control over the whole system remotely. Each sniffer runs a Python script implementing a simple multi-thread architecture with two processes that respectively manage the Wi-Fi and the Bluetooth interfaces. The Wi-Fi sniffing process is handled by Airodump-ng, a Linux network utility used for packet capturing of raw 802.11 frames. The Bluetooth inquiry scanning is done in parallel by hcitool spinq and hcidump, provided by BlueZ, the Linux Bluetooth stack. The software is in charge to run the process, parse the data and upload it on a local MySQL database.

As for the mobile devices, we consider five different mobile devices: Samsung Galaxy S3 mini with CyanogenMode 12 (based on Android Lollipop 5.1.1), LG E450 with Android KitKat 4.1.2, Samsung S Advance with Android KitKat 4.4.2, iPad with iOS 10, and Samsung Galaxy Tab S2 with Android Nougat 7.0. The devices are placed randomly and their positions are changed three times to simulate 15 different positions. All the devices are connected to the same Wi-Fi network, the screens are always active and the Bluetooth interfaces visible. Data is collected for exactly 10 minutes for each device, capturing approximately a Wi-Fi (Bluetooth) packet every second for each device. Such data is used to build the two matrices R and S.

The two matrices are processed with the algorithms presented in Section II. Each row of matrix R, corresponding to the Wi-Fi address w m is compared to all rows of matrix S according to each algorithm logic. Bluetooth addresses b m are then sorted in ascending order of similarity using Euclidean distance. A top-k approach is then used to perform algorithms evaluation: for each Wi-Fi address w m , we check if the ground-truth corresponding address b m is in the first k positions of the ordered list of Bluetooth addresses. We then evaluate top-k accuracy as the percentage of correctly paired addresses over all tested devices. Such an approach of measuring accuracy reflects particularly those scenarios in which the user is interested in obtaining a list of possible pairing devices rather than just one (e.g., an attacker who wants to direct its attack on a subset of Bluetooth interfaces possible matching a specific Wi-Fi address).

Figure 3 reports the top-k accuracy of all algorithms, when k is set to be in the range {1,3,5}. As one can see, all algorithms exceed 80% top-5 accuracy and 60% top-3 accuracy. The RSSI-to-distance algorithm performs best in all cases. It reaches 100% top 5 accuracy and 87% top 3-accuracy.

We also analyze the accuracy of the best algorithm (RSSI-todistance) when changing the number of deployed sniffers N from 2 to 6. This corresponds to increasing the sniffer density from approximately 1 sniffer every 25 square meters up to 1 sniffer every 8 square meters. For a particular number of sniffers we show the mean accuracy, obtained by averaging the accuracy of the 6 N possible combinations of the 6 sniffers shown in Figure 2. As one can see from Figure 4 the number of sniffer devices used impacts on the accuracy of pairing almost linearly. However, with only 2 sniffers the top-5 accuracy of the RSSI-to-distance its still around 80%.

IV. CONCLUSIONS

In this paper, we have investigated the possibility of pairing a Wi-Fi MAC address and a Bluetooth MAC address of a mobile device in a controlled environment. First, we have presented the sniffers hardware and software architecture. Then, we have described different address pairing algorithms based on two different methodological approaches. The proposed system was tested in a controlled environment achieving promising results. As a future research direction, we plan to (i) validate the results in a real scenario, also dealing with non-static devices, (ii) investigate machine-learning based methods, including other features different from the RSS to perform pairing (e.g., the Bluetooth/Wi-Fi Round Trip Time or the MAC addresses themselves) and (iii) evaluate the performance increase of the pairing algorithms when applied as preprocessing step in localization and crowd estimation systems, or when applied with malicious intentions to attack a device identity or a device battery.

Fig. 1 .Fig. 2 .

 12 Fig. 1. Models used for training the signal-mapping algorithms

Fig. 4 .Fig. 3 .

 43 Fig. 4. Top-k {1,3,5} accuracy of the RSSI-to-distance algorithm using different sniffers configuration.


Luis Tello-Oquendo

José-Ramón Vidal

Vicent Pla

Luis Guijarro

Dynamic Access Class Barring Parameter Tuning in LTE-A Networks with Massive M2M Traffic

Keywords: Access class barring (ACB), cellular-systems, machine-to-machine communications, performance analysis, 5G. I

Machine-to-machine (M2M) communication is one of the leading facilitators of the Internet of Things environment by offering ubiquitous applications and services. Using cellular networks for providing M2M connectivity brings several advantages such as extended coverage, security, robust management, and lower deployment costs; however, coexistence with a large number of M2M devices is still an essential challenge in LTE-A networks, in part due to the difficulty in allowing simultaneous access. Although the random access procedure in LTE-A is adequate for human-to-human (H2H) communications, when M2M communications are involved congestion control is required. One of the congestion control schemes suggested by the 3GPP is Access Class Barring (ACB), which can reduce the number of simultaneous users contending for access. However, it is still not clear how to adapt ACB parameters in bursty and heavy-loaded scenarios, such as those that appear in M2M communications. We propose a dynamic ACB scheme in which an estimate of the current number of M2M devices in backoff state is used to adjust in real-time the barring rate parameter. We evaluate the key performance indicators (KPIs) of dynamic ACB in several scenarios with different degrees of traffic load and compare them with those of a static ACB with optimal parameters. We show that the dynamic ACB outperforms the static one offering shorter access delay and higher successful access probability, while its impact on H2H communications KPIs is negligible. Besides, our proposed scheme conforms with the LTE-A specification so that it can be included as a viable solution.

networks is no longer a matter of choice; there are already M2M subscriptions supported by cellular operators worldwide, enhanced techniques are currently under standardization by 3GPP, and M2M connectivity is driving the development of 5G cellular systems [START_REF] Dawy | Toward massive machine type cellular communications[END_REF]- [START_REF]Service Requirements for Machine-Type Communications[END_REF].

Handling the massive number of connections generated by a large number of M2M devices (UEs) is an important challenge in cellular networks that has received a significant amount of attention nowadays. Specifically, the signaling in the connection attempts and the limited resources of the physical channels in the random access procedure are the main factors to take into account. Furthermore, the ability to adapt to changing conditions while at the same time providing new services is a constant challenge that cellular network operators have to face and one that very often implies new investments on infrastructure.

For avoiding that the above challenges become limitations that hinder the widespread horizons of M2M applications, the access class barring (ACB) scheme is included in the LTE-A radio resource control specification [6] as a viable congestion control scheme. It spreads the UE accesses through time by randomly delaying the beginning of the UE access attempts according to a barring rate and a barring time.

There is a trade-off between relieving congestion and the key performance indicators (KPIs) of the network when the ACB is operating [START_REF] Tello-Oquendo | Performance Analysis and Optimal Access Class Barring Parameter Configuration in LTE-A Networks With Massive M2M Traffic[END_REF]. Thus, its parameters must be adjusted adequately. The proper tuning of ACB parameters according to the traffic intensity is critical; however, how to implement this scheme effectively and tuning their parameter configuration so that it can dynamically and autonomously adapt to the network load is not a trivial task and has not been specified. The dynamic adaptation of the barring rate is desirable since the implementation of a static ACB affects the access delay of every UE, even in cases of no congestion, when the scheme is not needed at all.

The aim of this paper is to provide an algorithm for the dynamic tuning of the barring rate according to the traffic load in the random access channel (RACH) and its capacity. Our solution uses a comprehensive view of the access attempts in the random access procedure and fits the incoming traffic to the capacity of the RACH by tuning the barring rate appropriately. Furthermore, it conforms with current system specifications allowing efficient congestion control and facilitating the coexistence of H2H and M2M traffic.

Specifically, the main contributions of this paper are the following:

• We devise both an estimator of the UEs that are in backoff state and a mechanism for fitting this traffic jointly with the new arrivals into the RACH capacity.

ISBN 978-3-903176-05-8 c 2018 IFIP

• We propose an algorithm for tuning the barring rate dynamically according to the traffic load based on the devised estimator. We closely follow the 3GPP directives [START_REF]Medium Access Control (MAC) Protocol Specification[END_REF]- [START_REF]Physical layer procedures[END_REF] so that our proposed solution is aligned with the network specifications and can be successfully integrated in the system. • Besides testing several traffic loads following the traffic model and configuration parameters for M2M communications suggested by the 3GPP [START_REF]Study on RAN Improvements for Machine Type Communications[END_REF], we evaluate the impact on the H2H traffic. We assess our proposed algorithm regarding the key performance indicators (KPIs) suggested by the 3GPP [START_REF]Study on RAN Improvements for Machine Type Communications[END_REF] for this kind of studies. The rest of the paper is organized as follows. In Section II, a review of the literature regarding ACB is conducted. Then, the random access procedure in LTE-A and the ACB are presented in Section III-A and Section III-B, respectively. A detailed explanation of the proposed dynamic ACB jointly with its procedures for its proper functioning is presented in Section IV. The performance evaluation, selected traffic model, parameter configuration, KPIs, and our most relevant results are presented in Section V. Finally, our conclusions are presented in Section VI.

II. RELATED WORK

There have been a number of research efforts devoted to optimizing ACB for handling massive M2M connection attempts on the RACH through either static or dynamic approaches. However, many of them offer complex procedures, use questionable assumptions for getting high performance, or do not conform with LTE-A specifications (e.g., without considering the updating period of notification information by the eNodeB) [START_REF] Kim | Dynamic extended access barring for improved M2M communication in LTE-A networks[END_REF]- [START_REF] Chou | Loading prediction and barring controls for machine type communication[END_REF].

In [START_REF] Lo | Enhanced LTE-Advanced Random-Access Mechanism for Massive Machine-to-Machine (M2M) Communications[END_REF], a self-organizing mechanism which aims to optimize the performance of the random access procedure is proposed for M2M and H2H traffic. However, unlike the 3GPP specifications, the authors assume that a control-loop for congestion between the UEs and the eNodeB is available, which creates signaling overhead. In [START_REF] Hwang | Uplink access control for machine-type communications in LTE-A networks[END_REF], a dynamic mechanism for access control in LTE-A is proposed, to reduce the impact that massive M2M communications can have on H2H traffic. Also, in this work the authors classify the traffic, allowing prioritization. However, this approach modifies ACB so that it can send different parameters for different classes, in a similar way to the extended access barring scheme. Since the number of UEs trying to access the cellular network is dynamic, and its number is not known a priori, any mechanism that aims at optimizing ACB has to develop an estimation of this value. In [START_REF] Tavana | Congestion control for bursty M2M traffic in LTE networks[END_REF], a dynamic scheme for adjusting the ACB factor is proposed. It is based on the estimation of the contending UEs in the RACH using Kalman filtering. This solution enhances the overall performance but assuming full state information of the system. Although in this work no modifications are done over the ACB mechanism, it is not possible to estimate the impact that M2M traffic has over H2H traffic, since only the first one was considered. Also in [START_REF] Duan | D-ACB: Adaptive Congestion Control Algorithm for Bursty M2M Traffic in LTE Networks[END_REF], an optimal value of the barring rate parameter is obtained in an ideal case, i.e., assuming full state information about the system. Some heuristics which resemble this optimal solution are provided as well; one of them changes the barring rate and the other changes both the barring rate and the number of preambles that can be acknowledged. This solution assumes that when a UE suffers a collision, it will retry in the following random access opportunity, which is not consistent with the LTE-A specifications.

To successfully address the above limitations, we propose a dynamic ACB based on the estimation of UEs that are in backoff state and a mechanism for fitting this traffic jointly with the incoming one into the RACH capacity. Our solution tunes the barring rate according to the traffic load in realtime and deactivates itself when the traffic is below the RACH capacity. It conforms with current system specifications and constraints, offering effective access control.

III. LTE-A RANDOM ACCESS PROCEDURE

In this section, we provide a general overview of the random access procedure in LTE-A networks. Then, we explain both the contention-based random access and the ACB in Section III-A and Section III-B, respectively.

Two modes were defined for the random access: contentionfree and contention-based. The former is used for critical situations such as handover, downlink data arrival or positioning. The latter is the standard mode for network access; it is employed by the UEs to change the radio resource control state from idle to connected, to recover from a radio link failure, to perform uplink synchronization or to send scheduling requests [START_REF]Medium Access Control (MAC) Protocol Specification[END_REF].

The random access attempts of UEs are allowed in predefined time/frequency resources herein called RAOs. Before initiating the random access procedure, the UEs must first obtain some configuration parameters such as the RAOs in which the transmission of preambles is allowed. The eNodeB broadcasts this information periodically through the Master Information Block (MIB) and the System Information Blocks (SIBs). Two uplink channels are required for the access attempts, namely, the physical random access channel (PRACH) for preamble transmission and the physical uplink shared channel (PUSCH) for additional signaling data. Particularly, the PRACH is used to signal a connection request when a UE attempts to access the cellular network. In the frequency domain, the PRACH is designed to fit in the same bandwidth as six resource blocks of normal uplink transmission (6×180 kHz); this fact makes it easy to schedule gaps in normal uplink transmission to allow for RAOs. In the time domain, the periodicity of the RAOs is determined by the parameter prach-ConfigIndex provided by the eNodeB; a total of 64 PRACH configurations are available. Thus, the periodicity of the RAOs ranges from a minimum of 1 RAO every two frames to a maximum of 1 RAO every subframe, i.e., from 1 RAO every 20 ms to 1 RAO every 1 ms [START_REF]Radio Resource Control (RRC), Protocol specification[END_REF].

As mentioned above, the PRACH carries a preamble (signature) for initial access to the network; up to 64 orthogonal preambles are available per cell. In the contention-free mode, collision is avoided through the coordinated assignment of preambles, but eNodeBs can only assign these preambles during specific slots to specific UEs. In the contention-based mode, preambles are selected in a random fashion by the UEs, so there is a risk of collision, i.e., multiple UEs in the cell might pick the same preamble signature in the same RAO; therefore, contention resolution is needed. In the sequel, we focus on the analysis of the contention-based random access procedure.

A. Contention-Based Random Access Procedure

Once the UE has acquired the basic configuration parameters, it may proceed with the four-message handshake illustrated in Fig. 1. Next, we describe both the four-message handshake and the backoff procedure. The interested reader is referred to [START_REF]Medium Access Control (MAC) Protocol Specification[END_REF]- [START_REF]Physical layer procedures[END_REF], [START_REF] Gpp | Feasibility study for Further Advancements for E-UTRA[END_REF] for further details.

RACH preamble (Msg1): Whenever a UE attempts transmission, it sends a randomly chosen preamble in a RAO (Msg1). Due to the orthogonality of the different preambles, multiple UEs can access the eNodeB in the same RAO, using different preambles. The eNodeB can, without a doubt, decode a preamble transmitted (with sufficient power) by exactly one UE and estimate the transmission timing of the terminal. In this study, we assume that a collision occurs whenever two or more UEs transmit the same preamble at the same RAO. This goes in line with the 3GPP recommendations for the performance analysis of the RACH [START_REF]Study on RAN Improvements for Machine Type Communications[END_REF] and with most of the literature [START_REF] Tello-Oquendo | Performance Analysis and Optimal Access Class Barring Parameter Configuration in LTE-A Networks With Massive M2M Traffic[END_REF], [START_REF] Tavana | Congestion control for bursty M2M traffic in LTE networks[END_REF], [START_REF] Lin | PRADA: Prioritized random access with dynamic access barring for MTC in 3GPP LTE-A networks[END_REF], [START_REF] Arouk | General Model for RACH Procedure Performance Analysis[END_REF].

Random access response-RAR-(Msg2): The eNodeB computes an identifier for each successfully decoded preamble, ID = f(preamble,RAO), and sends the Msg2 through the physical downlink control channel (PDCCH). It includes, among other data, information about the identification of the detected preamble (ID), time alignment (TA), uplink grants (reserved PUSCH resources) for the transmission of Msg3, the backoff indicator (B), and the assignment of a temporary identifier.

Exactly two subframes after the preamble transmission has ended (this is the time needed by the eNodeB to process the received preambles), the UE begins to wait for a time window, W RAR , to receive an uplink grant from the eNodeB through Msg2. There can be up to one RAR message in each subframe, but it may contain up to three uplink grants. Each uplink grant is associated to a successfully decoded preamble. The length of the W RAR , in subframes, is broadcast by the eNodeB through the SIB Type 2 (SIB2) [START_REF]Radio Resource Control (RRC), Protocol specification[END_REF]. Hence, there is a maximum number of uplink grants that can be sent within the W RAR . Only the UEs that receive an uplink grant can transmit the Msg3.

Connection request (Msg3): After receiving the corresponding Msg2, the UE adjusts its uplink transmission time according to the received TA and transmits a scheduled connection-request message, Msg3, to the eNodeB using the reserved PUSCH resources; hybrid automatic repeat request (HARQ) is used to protect this message transmission.

Contention Resolution (Msg4): The eNodeB transmits Msg4 as an answer to Msg3. The eNodeB also applies an HARQ process to send Msg4 back to the UEs. If a UE does not receive Msg4 within the contention resolution timer, then it declares a failure in the contention resolution and schedules a new access attempt. For doing so, the failed UEs ramp up their power and re-transmit a new randomly chosen preamble in a new RAO, based on a uniform backoff scheme (explained next) that uses the value of B received with Msg2.

Note that each UE keeps track of its preamble transmissions. When a UE has transmitted a certain number of preambles (preambleTransMax notified by the eNodeB through the SIB2 [START_REF]Radio Resource Control (RRC), Protocol specification[END_REF]) without success, the network is declared unavailable by the UE, an access problem is indicated to upper layers, and the random access procedure is terminated.

Backoff procedure: According to the LTE-A standard [START_REF]Medium Access Control (MAC) Protocol Specification[END_REF], if the random access attempt of a UE fails, regardless of the cause, the UE has to perform a backoff procedure before starting the random access process all over again. In this procedure, the UE waits for a random time, T BO [ms], until it can attempt a new preamble transmission as follows

T BO = U (0, B), ( 1
)
where U (•) stands for uniform distribution, B is the backoff indicator defined by the eNodeB, and its value ranges from 0 to 960 ms. The value of B is sent in the Msg2, which is read by all the UEs that sent a RACH preamble in the previous RAO. This means that every UE that failed the access attempt receives the parameter B.

B. Access Class Barring

Access Class Barring (ACB) is a congestion control scheme designed for limiting the number of simultaneous access attempts from certain UEs. The main purpose of ACB is to redistribute the access requests of UEs through time to reduce the number of access requests per RAO. This fact helps to avoid massive-synchronized accesses demands to the RACH, which might jeopardize the accomplishment of QoS objectives. For that purpose, all UEs are assigned to 16 mobile populations, defined as access classes (ACs) 0 to 15. The population number is stored in UE's SIM/USIM. Each UE belongs to one out of the first 10 ACs (from ACs 0 to 9) and can also belong to one or more out of the five special categories (ACs 11 to 15). Thus, M2M UEs may be assigned an AC between 0 and 9, and if a higher priority is needed, other classes may be used.

If ACB is not implemented, all ACs are allowed to access the RACH. When ACB is implemented, the eNodeB broadcasts (through SIB2) barring rates, P ACB ∈ {0.05, 0.1, . . . , 0.3, 0.4, . . . , 0.7, 0.75, 0.8, . . . , 0.95}, and mean barring times, T ACB ∈ {4, 8, 16, . . . , 512 s}, that are applied to ACs 0-9. Then, at the beginning of the random access procedure, each UE determines its barring status with the information provided by the eNodeB. For this, the UE generates a random number denoted by g, g = U [0, 1). If g ≤ P ACB , the UE selects and transmits its preamble. Otherwise, the UE waits for a random time calculated as follows data / g = U [0, 1) [START_REF]Radio Resource Control (RRC), Protocol specification[END_REF] jointly with the random access procedure. Note that ACB is applied to the UEs before they perform the random access procedure explained in Section III-A. It is worth noting that ACB is only useful for relieving sporadic periods of congestion, i.e., when a massive number of UEs attempt transmission at a given time but the system is not continuously congested.

T barring = [0.7 + 0.6 U [0, 1)] T ACB . ( 2
[g > PACB] SIB2 ACB timeout / g = U [0, 1) [g ≤ PACB] ACB timeout / g = U [0, 1) [g > PACB] SIB2 RAO / Msg1 RAR timeout [!max preamble-tx] Msg2 / Msg3 [!max Msg3 re-tx] Msg2 / Msg3 [max Msg3 re-tx] RAR timeout [max preamble-tx] ACK timeout Msg4 backoff timeout ACCESS CONTROL RANDOM ACCESS PROCEDURE

IV. DYNAMIC ACCESS CLASS BARRING FOR CONGESTION

CONTROL The ultimate goal of the ACB is to control the arrival of M2M UEs to the RACH so that the number of transmitted preambles stays below a certain threshold. To achieve this, the eNodeB must tune in real-time the P ACB value accordingly to the traffic conditions. We propose to implement the P ACB updating based on an estimate of the number of UEs that are in backoff state. In Section IV-A we derive analytically the estimation of the number of UEs in backoff state and in Section IV-B we describe the mechanism for tuning the P ACB dynamically.

A. Estimation of the number of UEs in backoff state

At RAO(i), let n b (i) be the estimate number of UEs in backoff state , n s (i) the number of UEs that accessed successfully, n t (i) the number of UEs that transmitted a preamble and n r (i) the number of UEs in backoff state that retransmitted. The estimated number of UEs in backoff state at RAO(i) (see Fig. 3) is given by UEs that fail the access, mainly because they reach the pream-bleTransMax value, are not considered in Eq. ( 3). Therefore, the estimation presented here is valid only when the success probability is high enough, which is a reasonable assumption when congestion control performs effectively, as we show in the following sections.

n b (i) = n b (i -1) -n r (i) + n t (i) -n s (i). (3)
The eNodeB knows n s (i) by observing the preambles that have been detected and decoded correctly. Since the number of uplink grants that the eNodeB can send in an RAO is limited to N UL grants, n s (i) is given by

n s (i) = min{preambles decoded, N UL }. ( 4
)
The value of n t (i) is unknown because, in our collision model, the preambles that collided (transmitted by more than one UE) are not decoded, and therefore the eNodeB does not know how many UEs transmitted them. Instead, we will use the estimated expectation of n t , obtained from the number of used preambles n u (preambles transmitted at least by one UE). Let Y j ∈ {0, 1} be the random variable that denotes the transmission of preamble j given that the total number of transmissions is n t . Then, Y j = 0 when preamble j has not been transmitted by any UE, and Y j = 1 otherwise. The probabilities of Y j are

P{Y j = 0} = 1 -1 R nt , P{Y j = 1} = 1 -1 -1 R nt , ( 5
)
where R is the number of available preambles in the system. The expected value of Y j is given by

E{Y j } = 0 • P{Y j = 0} + 1 • P{Y j = 1} = 1 -1 - 1 R nt .
(6) Then, the number of used preambles, n u , is

n u = R j=0 Y j , (7)
and its expected value is

E{n u } = E ⎧ ⎨ ⎩ R j=0 Y j ⎫ ⎬ ⎭ = R 1 -1 - 1 R nt . ( 8
)
If we assume that E{n u } changes slowly, it can be estimated from a short term time average of n u . Let nu (i) be an estimate of the time average of n u obtained by exponential smoothing of n u at RAO(i). Then, with α < 1, and from Eq. ( 8), n t (i) is

E{n u }(i) ≈ nu (i) = α nu (i -1) + (1 -α) nu (i) (9) x 0 x 1 • • • RAO(i -1) RAO(i) x K-1 T RAO B t 0
n t (i) = log 1 -E{nu}(i) R log 1 -1 R . ( 10
)
The value of n r (i) is estimated from n b (i-1). Firstly, from n b (i-1) we estimate the expected number of UEs that entered the backoff state during the period of length B (maximum backoff duration) previous to RAO(i -1). Let n A denote this number. Secondly, from n A we estimate the expected number of UEs that entered the backoff state during the period of length B + T RAO previous to RAO(i), that we denote as n B . Finally, from n B we estimate the expected value of n r (i).

Let X be the random variable that represents the UE backoff start time in the interval [0, B]. The UEs enter the backoff state at a fixed time t 0 after the transmission of a preamble, where t 0 depends on the RACH configuration parameters. Besides, preambles are transmitted at a RAO subframe, so all values of X are grouped in subframe intervals every T RAO . We approximate these values to the discrete set {x 0 . . . x K-1 }, being x i = t 0 + i T RAO , as shown in Fig. 4. We assume that at any time window B = K T RAO , all backoff times have the same probability (i.e., P(X = x i ) = 1/K).

Let T BO be the random variable that represents the backoff duration, with uniform distribution given by Eq. ( 1). If we denote by p the probability that a UE starting backoff in the interval [0, B] is still in backoff at time B, p is computed as

p = K-1 k=0 P(X = x k , x k + T BO > B) = 1 K K-1 k=0 x k B = = 1 K K-1 k=0 k T RAO + t 0 B = 1 K 1 B K x 0 + x K-1 2 = = 1 2B (t 0 + (K -1)T RAO + t 0 ) = = 1 2 1 - T RAO B + t 0 B . ( 11
)
The number of UEs in backoff at RAO(i -1) is a random variable that follows a binomial distribution with success probability p, n A attempts, and expected value p n A . Note that we do not consider those UEs that ended the backoff and started a new one before RAO(i -1). But, if the congestion control performs effectively, the probability of a second backoff will be low, and the error that is incurred by this approximation is negligible. If we take n b (i -1) as the expected value of the number of UEs in backoff, we can estimate n A from

n b (i -1) = p n A . ( 12
)
We also assume that users will start backoff at x K-1 +T RAO with the same probability as in x i , i ∈ {0, . . . , K -1}. Then, n B can be estimated from

n B = n A + n A K = 1 + T RAO B n A . ( 13
)
Let Z be the discrete random variable that represents the UEs backoff start time during the interval [0, B + T RAO ], with values {x 0 . . . x K } and probabilities P(Z = z i ) = 1/(K + 1). If we denote by q the probability that a UE starting backoff in the interval [0, B + T RAO ] retransmits in the interval [B, B + T RAO ], q is computed as

q = K k=0 P(Z = z K , B < z k + T BO < B + T RAO ) = = 1 K + 1 P(T BO > B -z 0 )+ + 1 K + 1 K-1 k=1 P(B -z k < T BO < B -z k + T RAO )+ + 1 K + 1 P(T BO < B -z k + T RAO ) = = 1 K + 1 t 0 B + K-1 k=1 T B + B + T RAO -(kT RAO + t 0 ) B = = 1 K + 1 (K -1) T RAO B + T RAO B = T RAO B + T RAO . ( 14
)
The number of UEs in backoff that retransmit at RAO(i) is a random variable that follows a binomial distribution with success probability q, n B attempts, and expected value q n B . If we take n b (i) as the expected value of this variable, we can estimate n r (i) as n r (i) = q n B , (

and, from Eqs. ( 11)- [START_REF] Lo | Enhanced LTE-Advanced Random-Access Mechanism for Massive Machine-to-Machine (M2M) Communications[END_REF], it follows that

n r (i) = 2 T RAO B -T RAO + 2 t 0 n b (i -1). (16)
Finally, n b (i) is computed by replacing Eqs. ( 16), [START_REF]Physical layer procedures[END_REF], and (4) in Eq. (3).

Fig. 5 shows an example, obtained by discrete-event simulation, of the performance of this estimator. In this example, the estimator operates during a congestion episode induced by the M2M traffic benchmark described in Section V, with the UEs implementing ACB. As can be seen, the error in the estimation is minimal.

B. Dynamic Barring Rate Tuning

In this section, we describe a mechanism for tuning the barring rate dynamically using the information provided by the estimation of the number of users in backoff state, n b (i). We assume that the eNodeB has no information about the number of new arrivals. Nevertheless, by estimating n b (i), the expected number of retransmissions, n r (i), is also estimated. From this, the unused capacity of the RACH can be evaluated and the incoming traffic can be modulated accordingly, that is, by computing P ACB as a function of n r (i): The number of access requests per RAO that maximizes the expected number of UEs that access the channel successfully is given as a function of the available preambles, R, by [START_REF] Lin | PRADA: Prioritized random access with dynamic access barring for MTC in 3GPP LTE-A networks[END_REF]

P ACB = f (n r (i)).
n * t (R) = [log(R/(R -1)] -1 . ( 17
)
At RAO(i), if n r (i) ≥ n * t (R), all new arrivals should be barred, so f (n r (i) ≥ n * t (R)) = 0. On the other hand, if n r (i) = 0 there is no reason to reduce the incoming traffic, so f (0) = 1. Between these two boundary conditions, f (•) should be a decreasing function. We have tested by simulation linear, quadratic, and cubic functions and we have found that, although all of them work quite well, the cubic function shown in Fig. 6 provides a better performance. Thus, we propose to compute P ACB as

P ACB (i) = f (n r (i)) = 2 n r (i) 3 n * t (R) 3 - 3 n r (i) 2 n * t (R) 2 + 1. (18)
The value of P ACB is notified to the UEs by the eNodeB through the SIB2 message with a periodicity of T SIB2 = 80 ms ≡ 16 RAOs.

Finally, the dynamic ACB implementation can be summarized as

• Every RAO(i),
1) Estimate E{n u }(i) with Eq. ( 9), 2) Estimate n t (i) with Eq. ( 10), 3) Estimate n r (i) with Eq. ( 16), 4) Estimate n b (i) with Eq. ( 4). • Every T SIB2 , 1) Compute P ACB (i) with Eq. ( 18), 2) Update P ACB (i) in SIB2.

V. PERFORMANCE EVALUATION

In this section, we evaluate the performance of the proposed dynamic ACB scheme with T ACB = 4 s, and compare it with the performance of a static ACB with optimal parameters (P ACB = 0.5 and T ACB = 4 s). The parameters for static ACB are chosen based on a previous work [START_REF] Tello-Oquendo | Performance Analysis and Optimal Access Class Barring Parameter Configuration in LTE-A Networks With Massive M2M Traffic[END_REF] where we showed that the lowest access delay for a highly congested scenario given a requirement of P s ≥ 0.95 is achieved when P ACB = 0.5 and T ACB = 4 s. We measure three KPIs, namely the probability to successfully complete the random access procedure, P s ; the mean number of preamble transmissions needed by the UEs to successfully complete the random access procedure, W ; and the access delay (mean and percentiles), D. These KPIs are in conformance with the 3GPP directives [START_REF]Study on RAN Improvements for Machine Type Communications[END_REF] to assess the efficiency of the LTE-A random access procedure with M2M communications.

A single cell environment is assumed to evaluate the network performance. The system conveys traffic from both H2H and M2M UEs. The access requests of H2H UEs are distributed uniformly over time with a mean arrival rate of λ H = 1 arrivals/s. The M2M requests follow a Beta [START_REF] Dawy | Toward massive machine type cellular communications[END_REF][START_REF] Akyildiz | 5G roadmap: 10 key enabling technologies[END_REF] distribution over a period of 10 s, according to the traffic model 2 specified by the 3GPP in [START_REF]Study on RAN Improvements for Machine Type Communications[END_REF]. This traffic model can be seen as an extreme scenario in which a vast number of M2M UE arrivals occur in a highly synchronized manner (e.g., after an alarm that activates them). We developed a discrete-event simulator that fully reproduces the behavior of UEs, eNodeB, and RACH during the random access procedure described in Section III-A. We consider the typical PRACH configuration for these kind of studies, prach-ConfigIndex 6, in conformance to the LTE-A specification [START_REF]Medium Access Control (MAC) Protocol Specification[END_REF], [START_REF]Study on RAN Improvements for Machine Type Communications[END_REF], with the parameter values listed in Table I. The value of each KPIs is obtained as the mean of 100 simulation runs. Each simulation run uses a different random seed and ends when all the M2M UEs have completed their random access procedure.

Fig. 7a depicts the temporal distribution of preamble transmissions during a congestion episode of N M = 30 000 M2M UEs and no congestion control. As can be seen, an access control mechanism is required for alleviating congestion. Such a high number of preamble transmissions is the consequence of the fact that the higher the number of preamble transmissions in a RAO, the lower the probability of a successful preamble transmission. This, in turn, increases the probability of preamble retransmissions and reduces dramatically P s . Fig. 7b shows the above scenario for the static ACB with P ACB = 0.5 and T ACB = 4 s. Now, the total number of preamble transmissions is reduced while the number of not collided transmissions increases, what results in a higher probability of successful access. But the number of collisions is still high because it fails to maintain the preamble transmission rate close to the optimal number of access requests per RAO that maximizes the expected number of successful access, n * t (R), which is approximately 53 with R = 54 available preambles.

Fig. 7c illustrates the performance of our proposed dynamic ACB scheme in the same scenario. We see that the total number of preamble transmissions and the number of collided transmissions are both considerably reduced when compared to the static ACB. More importantly, this reduction is achieved under dynamic conditions and by adapting P ACB accordingly. Note that most of the time the preamble transmissions rate is maintained close to the optimal value (n * t (R) ≈ 53) and the not collided preambles rate is maintained close to the RACH capacity (approx. 20 [7, Eq. ( 4)]), using the available resources efficiently.

Fig. 8 shows how P ACB is tuned by the eNodeB with dynamic ACB operating during the congestion episode. As can be seen, before the congestion starts, P ACB = 1; it gradually decreases when the number of preamble transmissions rises, and grows again as the traffic diminishes, until it goes back to 1. Note that P ACB changes dynamically with a granularity of T SIB2 .

Fig. 9a depicts the successful access probability, P s , for both ACB types with different M2M traffic intensities (N M ). As can be seen, in heavy-loaded scenarios (N M > 26 000) the dynamic ACB provides a P s ≥ 0.99, clearly outperforming the static one. In terms of mean number of preamble transmissions needed to successfully complete the random access procedure, Fig. 9b shows that the dynamic ACB slightly increases this metric when (30 000 > N M ). Finally, Fig. 9c compares the mean access delay of both ACB types. We can see that the dynamic ACB decreases notably the mean access delay, even more in low-loaded scenarios, since our solution uses efficiently the available RACH resources.

In Table II, we can see several statistics for the three schemes: no control, static ACB, and dynamic ACB. For each of them, results for a heavy-loaded traffic scenario (N M = 30 000) are shown. We show the KPIs defined at the beginning of Section V for both H2H and M2M UEs.

It is evident from the results that the network with no access control suffers in terms of P s and W . However, the access delay is moderate. On the other hand, our proposed dynamic ACB scheme shows an improvement over the solution with static ACB, providing a P s ≥ 0.99 for both H2H and M2M communications while reducing considerably the M2M access delays without increasing the H2H access delays. This is important since one of the main requirements when introducing M2M communications into an LTE-A network is that it does not affect the preexisting H2H UEs.

VI. CONCLUSION We propose a dynamic ACB mechanism that adjusts the barring factor in real-time, based on the estimation of the number of UEs that are in backoff sate. We have evaluated this solution by means of extensive discrete-event simulations, and compared its performance with that of a static ACB with optimal parameters. We conclude that, in a heavy-loaded traffic scenario, the dynamic ACB increases noticeably the probability of successful access while shorting the access delay, and the number of preamble transmissions needed to successfully complete the random access procedure. Moreover, we have checked that the dynamic ACB does not have a significant impact on H2H traffic performance. Our solution is conforming with current system specifications and allows efficient congestion control, facilitating the coexistence of H2H and M2M traffic.

Figure 1 .

 1 Figure 1. LTE-A contention-based random access procedure.

  g = U [0, 1) [g ≤ PACB]

Figure 2 .

 2 Figure 2. State transition diagram of the random access procedure when access control is implemented for M2M UEs.

Fig. 2

 2 Fig.2illustrates the state transition diagram of the ACB mechanism [6],[START_REF]Radio Resource Control (RRC), Protocol specification[END_REF] jointly with the random access procedure. Note that ACB is applied to the UEs before they perform the random access procedure explained in Section III-A. It is worth noting that ACB is only useful for relieving sporadic periods of congestion, i.e., when a massive number of UEs attempt transmission at a given time but the system is not continuously congested.

Figure 3 .

 3 Figure 3. Variables and traffic flows used in the estimation of n b .

Figure 4 .

 4 Figure 4. Backoff starting times.

Figure 5 .

 5 Figure 5. Performance of the estimator during a congestion episode. (a) Dynamic ACB. (b) Static ACB.

Figure 6 .

 6 Figure 6. Computation of P ACB from the expected number of retransmissions.

Figure 7 .

 7 Figure 7. Average number of preambles per RAO when H2H UEs and massive M2M UEs (N M = 30 000) attempt to access. (a) No access control. (b) Static ACB (0.5,4 s) implemented. (c) Dynamic ACB operating.

Figure 8 .

 8 Figure 8. Evolution of P ACB in dynamic ACB during a congestion episode.

Figure 9 .

 9 Figure 9. KPIs of the LTE-A network for static ACB and the proposed dynamic ACB. (a) Successful access probability. (b) Expected number of preamble transmissions per RAO. (c) Expected access delay.

Table II KPIS

 II OBTAINED FOR LTE-A AND DIFFERENT ACB IMPLEMENTATIONS IN A HEAVY-LOADED TRAFFIC SCENARIO.

	Key Performance Indicator	No ACB	ACB(0.5, 4 s)	Dynamic ACB
			H2H M2M H2H	M2M H2H	M2M
	Success probability	Ps	0.66	0.31	0.99	0.97	0.99	0.99
	Number of preamble transmissions, W	E [W ]	2.15	3.45	1.60	2.45	2.03	2.45
	Access delay, D [ms]	E [D]	46	71	32	4 111	42	2 367
		D99	203	217	125 24 676	151	9 700
		D95	141	186	67 15 744	104	8 242
		D80	59	117	43	7 865	56	4 742
		D10	17	18	16	22	17	21

This research has been supported in part by the Ministry of Economy and Competitiveness of Spain under Grants TIN2013-47272-C2-1-R and TEC2015-71932-REDT. The research of L. Tello-Oquendo was supported in part by Programa de Ayudas de Investigación y Desarrollo (PAID) of the Universitat Politècnica de València.