IEEE COMMUNICATIONS LETTERS, VOL. 19, NO. 5, MAY 2015 843 Resource Allocation in a New Random Access for M2M Communications Ningbo Zhang, Guixia Kang, Jing Wang, Yanyan Guo, and Fabrice Labeau, Member, IEEE Abstract—To increase the number of successful accesses for machine-to-machine (M2M) communication, we propose a new random access (RA) procedure. The proposed RA procedure al- lows evolved NodeB (eNB) to know the preamble collisions in the first step by attaching user equipment (UE) identity information in physical random access channel (PRACH). This improvement prevents eNB from scheduling physical uplink shared channel (PUSCH) to the collided preambles, which improves the resource efficiency. Based on the enhanced RA procedure, a resource allo- cation scheme is proposed. By estimating the number of successful preamble, the proposed scheme achieves a reasonable resource tradeoff between PRACH and PUSCH. Simulation results show that the proposed RA procedure significantly improves the num- ber of successful accesses as well as the resource efficiency. Index Terms—Machine-to-machine communications, random access, preamble collision, resource allocation. I. INTRODUCTION L OOKING ahead to the year of 2020 and beyond, hundreds of billions of machine-to-machine (M2M) connections will be made in cellular networks. Due to the massive connec- tions, how to support more M2M UEs simultaneously connect- ing to the cellular network is an important issue [1]. Random access (RA) is the first step to access cellular network. In a RA procedure, two uplink channels are required, i.e., physical ran- dom access channel (PRACH) for preamble transmission and physical uplink shared channel (PUSCH) for data transmission [2]. In M2M communications, there are two bottlenecks. The first one is preamble collisions on PRACH, i.e., if more than one M2M UE selects the same preamble on the same PRACH, they will share the same PUSCH for data transmission. When eNB schedules the same PUSCH to multiple UEs, this PUSCH is wasted because eNB cannot decode any data packet due to the co-channel interference. The second one is resource allocation between PRACH and PUSCH. Even if an M2M UE successfully selects a preamble without collision, it still fails if there are not enough resource blocks (RBs) allocated to the corresponding PUSCH. There have been several studies on the first bottleneck. In [3], an extended access barring (EAB) is introduced to control PRACH overload in which the delay tolerant UEs are not al- lowed to perform RA when PRACH overload is serious. In [4], a novel RA scheme to effectively increase the number of avail- able preambles is proposed. The proposed scheme provides additional preambles by spatially partitioning a cell coverage into multiple group regions and reducing cyclic shift size in RA preambles. For fixed-location M2M UEs, a new RA scheme in [5] is proposed. Based on the fixed timing alignment, a fixed-location M2M UE predetermines the possible occurrence of collisions, which can significantly reduce the probability of collisions. In [6], the authors review several RA overload control mechanisms to avoid congestion. Above studies mainly focus on how to lower the probability of preamble collision. When counting the number of successful accesses, the common assumption is that the number of PUSCH is sufficient. However, in practical systems, if more RBs are allocated to PUSCH, the number of RBs allocated to PRACH will correspondingly decrease because the total number of up- link RBs is fixed. This in turn impacts the number of available preamble. On the other hand, some PUSCH may be wasted on the collided preamble, which further decreases the efficiency of resource usage. Therefore, there are two problems on re- source allocation: 1) How to avoid resource wasting caused by collisions. 2) How to allocate resources between PRACH and PUSCH. To solve these problems, we propose a new RA procedure and a resource allocation scheme in this letter. The remainder of this letter is organized as follows. Section II presents the traditional RA procedure. Section III elaborates the improved RA procedure and the proposed resource allocation scheme. Evaluation results are given in Section IV, while the letter is concluded in Section V. Manuscript received November 21, 2014; revised February 21, 2015; accepted March 10, 2015. Date of publication March 18, 2015; date of current version May 7, 2015. This work was supported by Open Project of Key Laboratory of Ministry of Education for Wireless Communication: No. (KFKT-2014103), the National Science and Technology Major Project of China (No. 2013ZX03006001), the National High Technology Research and Development Program of China (“863”Program, No. SS2015AA011303), the National Natural Science Foundation of China (61471064, 61301146), and the Fundamental Research Funds for the Central Universities. The associate editor coordinating the review of this paper and approving it for publication was A. Lioumpas. (Corresponding author: Jing Wang.) N. Zhang and G. Kang are with Key Laboratory of Universal Wireless Communications, Ministry of Education, Beijing University of Posts and Telecommunications, Beijing 100876, China. J. Wang is with the College of Information Science and Technology, Beijing Normal University, Beijing 100875, China (e-mail: j.wang@bnu.edu.cn). Y. Guo is with the College of Physics and Electronic Engineering, ShanXi University, Taiyuan 030006, China. F. Labeau is with the Department of Electrical and Computer Engineering, McGill University, Montreal, QC H3A 0E9, Canada. Digital Object Identifier 10.1109/LCOMM.2015.2413961 II. TRADITIONAL RANDOM ACCESS PROCEDURE In long term evaluation (LTE) systems, there are two types of RA procedure: contention-based and contention-free [7]. This letter only focuses on the contention-based manner. A contention-based RA procedure consists of the following four steps: Step 1: An UE randomly selects one preamble from all avail- able preambles with equal probability and transmits it on PRACH. Step 2: After detecting the preamble, eNB transmits the cor- responding random access response (RAR) through downlink channels. The RAR conveys the identity of detected preamble, uplink grant for scheduled message in step 3, timing alignment (TA) information and the assignment of a temporary identifier. 1558-2558 © 2015 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information. 

844 IEEE COMMUNICATIONS LETTERS, VOL. 19, NO. 5, MAY 2015 Fig. 1. Resource allocation in a RA cycle. Step 3: After receiving the corresponding RAR, UE adjusts uplink transmission time according to the received TA and transmits a scheduled message on PUSCH. If more than one UE selects the same preamble in step 1, they will receive the same RAR and send their scheduled messages on the same PUSCH. There- fore, multiple scheduled messages are collided on PUSCH. Step 4: If eNB correctly decodes scheduled message from step 3, it transmits the contention resolution to the corresponding UE. If UE cannot receive the RAR message or contention resolution within correspond- ing timing window, it regards preamble transmission as a collision and reattempts RA procedure after a random back-off. It is known that uplink RBs are divided into PRACH subset and PUSCH subset in a RA cycle, as shown in Fig. 1. In traditional random access, eNB knows the occurrence of pream- ble collisions only when it cannot decode scheduled messages in step 3. Meanwhile, numbers of RBs are already assigned to those PUSCH where collisions happen. As a result, these assigned RBs are wasted. Obviously, if eNB can detect the collisions in step 1 and does not assign RBs to the collided PUSCH, resource wasting can be prevented. III. PROPOSED RANDOM ACCESS PROCEDURE AND RESOURCE ALLOCATION SCHEME A. Proposed Random Access Procedure In LTE systems, the preambles consist of the Zadoff-Chu sequence and the length of preamble sequence for format 0, 1, 2, and 3 is 839 [8]. A PRACH consists of 6 physical RBs (PRBs) in a subframe, which occupies 864 subcarriers. 64 preamble sequences are mapped to the central 839 subcarriers while the rest 25 subcarriers are reserved for guard band. After receiving the preambles on PRACH, eNB calculates the value of power delay profile (PDP). If the estimated PDP is higher than a predefined threshold, the preamble is regarded as active. eNB can detect if a preamble is active, but it does not know how many UEs select this preamble. We extend the traditional preamble transmission by trans- mitting not only preamble but also the UE identity (UE ID) information and a cyclic redundancy check (CRC) on PRACH. All UEs’ ID information and CRC are mapped to the same reserved subcarriers in the guard band. The length of UE ID and the position of mapping subcarriers are predefined. Given that every UE has a unique ID, when more than one UE selects the same preamble and transmits their IDs on the same predefined subcarriers, eNB cannot correctly decode UE ID because of the Fig. 2. The proposed PRACH mapping pattern. Fig. 3. Proposed RA procedure. interferences. Thus, eNB thinks that collisions happen and will not schedule PUSCH to this preamble. Therefore, resources wasting can be avoided. Fig. 2 gives an example of the proposed PRACH mapping pattern. In this example, we assume four bits of UE ID and four bits of CRC with quadrature phase shift keying (QPSK) modulation are transmitted on four predefined subcarriers (yel- low part in Fig. 2). Preamble sequences are still mapped to the central 839 subcarriers. Based on the new designed PRACH, a proposed RA pro- cedure is described in the following. Fig. 3 presents the procedure. Step 1: An M2M UE transmits a preamble, UE ID informa- tion and CRC on PRACH. Step 2: eNB first calculates the PDP of a preamble to detect if this preamble is active. If this preamble is active, eNB begins to decode the UE ID. After successfully de- coding the UE ID, eNB schedules PUSCH and sends the corresponding RAR. Otherwise, this preamble is regarded as a collision and eNB will stop sending the corresponding RAR. Step 3: Data packets are attached to the scheduled mes- sage to reduce the overhead of scheduling signal- ing considering the small size data packet of M2M communication. 

ZHANG et al.: RESOURCE ALLOCATION IN A NEW RANDOM ACCESS FOR M2M COMMUNICATIONS Step 4: The same procedure is processed as the tradi- tional RA. B. Resource Allocation Scheme Between PRACH and PUSCH In this subsection, a resource allocation scheme for the proposed RA procedure is analyzed. As we know, before a RA cycle begins, eNB allocates the uplink RBs to PRACH and PUSCH, and broadcasts the PRACH configuration to all M2M UEs via the broadcast or the control channel. This subsection discusses the resource allocation between PRACH and PUSCH. The overall resource efficiency is defined as the number of RBs for successful random accesses over the total number of RBs for M2M communications. We assume that eNB can perfectly detect the preamble collisions in step 1 so that no RBs are wasted on collided preambles. A fixed uplink modulation and coding scheme (MCS) for M2M transmission is assumed. We define the number of active M2M UEs in a RA cycle with Nm, where Nm includes reattempting UEs which failed in previous RA cycles and the new arrived UEs in the current RA cycle. eNB can obtain the value of Nm by a load estimation algorithm [9]. Assuming that the total number of RBs in a RA cycle is q, that the number of RBs allocated to PRACH is l, and the number of RBs allocated to PUSCH is d, then we have: q = d + l. (1) Suppose the numbers of RBs constituting one preamble and one PUSCH are k and n, respectively. Therefore, the total number of RBs for one successful access is k + n. The overall resource efficiency can be written as: BAcc · (n + k) r = q , (2) where BAcc denotes the number of successful accesses. Let H and I denote the number of available PUSCH and the number of successful preamble constructed from d and l RBs, respectively. Then we have: H = , I = , (3) Psl k d n where Ps is the estimated probability of a successful preamble (i.e., a preamble that is selected only by one UE) in step 1, and denotes the bottom integer function. Theorem 1: The maximum r can be achieved when the resource allocation between PRACH and PUSCH satisfies: (4) H = I. Proof: When H = I, n and Psl k can be written as the sum of the bottom integer part and the decimal part in the following, . The values of d Psl k = d n , = = d n d n + dec + dec Psl k Psl k Psl k d , (5) n where dec(·) denotes the decimal function. In practical systems, since the numbers of available PUSCH and successful pream- bles are much larger than 1, the value of the decimal part in (5) must be much smaller than the value of the integer part, therefore, the decimal part in (5) can be neglected. In this way, (4) can be written as: d n = Psl k . (6) dtr = nq k + n . (13) 845 (7) (8) The overall resource efficiency is calculated as: d n · (n + k) q r1 = = d + Psl q . When H < I, under the above approximation, we have d Psl k . The overall resource efficiency becomes: d + Psl · (n + k) d n n < r2 = q < q = r1. Similarly, we can also obtain an inequality when H > I. Therefore, we conclude that the maximum r can be achieved when the number of PUSCH equals the number of successful preambles. In theorem 1, Ps is a key parameter. Suppose the number of . In step 1, preamble , there- available preamble is Np, then Np = selection follows a Binomial distribution with mean 1 Np fore, Ps is calculated as: Ps = P (Bi = 1) = binom(Nm, 1) · Nm−1 , l k 1 Np 1 − 1 Np (9) where Bi denotes the number of UEs which select the same (y!)×(x−y)! . Substituting (1), preamble i, and binom(x, y) = (3) and (9) into (4), yielding: x! Nm 1 − k (q − d) Nm−1 d n = . (10) Due to the nonlinear function of the left side in (10), it is difficult to directly obtain d. However, since d is a positive integer in the internal of [1, q − 1], we can use an exhaustive algorithm to search the optimal value, which is: Nm−1 dopt = arg min 1≤d≤q−1 Nm 1 − k (q − d) d n − (11) Equation (11) means that the optimal d can be achieved when the gap between the number of successful preamble and the number of available PUSCH is minimum. The number of successful access is expected as: BAcc = min{H, I} = min Nm−1 Nm 1− 1 Np dopt n . , IV. PERFORMANCE EVALUATION (12) In this section, we present the performance of the proposed RA procedure in terms of the number of successful attempts, the resource efficiency and the probability of preamble col- lisions. To simplify the simulation, the miss detections and false alarms during preamble detection are neglected. In the traditional RA procedure, Ps is set to 1 because eNB cannot de- tect the preamble collisions before scheduling PUSCH. Let dtr denotes the number of RBs allocated to PUSCH. By Theorem 1, we have q−dtr n . Note that dtr is an integer, so k = dtr 

846 IEEE COMMUNICATIONS LETTERS, VOL. 19, NO. 5, MAY 2015 TABLE I CALCULATION OF dtr AND dopt Fig. 4. Comparison of the number of successful accesses between traditional RA procedure and new RA procedure. In the simulation, we set q = 300 and n = 1. Assuming there are 24 preamble sequences assigned to M2M UEs in every 6 PRBs, so k = 1 4 . By (11) and (13), dopt and dtr with different values of Nm are calculated in Table I. It can be seen that dopt is adaptively adjusted according to different values of Nm, while dtr is a fixed value. Fig. 4 shows the comparison of the number of successful accesses between the traditional RA procedure and the pro- posed RA procedure for different values of Nm. Theoretical analysis in (12) and simulation results in LTE systems are also compared. On PRACH, we use 4 subcarriers for UE ID transmission. Nm ranges from 50 to 1000. It can be seen that with the increase of Nm, the number of successful accesses in the traditional RA procedure significantly decreases, especially when Nm exceeds Np. This is because the probability of preamble collisions becomes larger, and more and more RBs are wasted on the collided PUSCH in step 3. In contrast, the proposed RA procedure achieves a stable number of successful accesses even when the number of active UEs is much higher than the number of available resources. This gain comes from the proposed resource allocation scheme and the pre-detection of preamble collisions. Furthermore, we observe that the theo- retical results match the simulation results. Fig. 5 presents the comparison of the overall resource efficiency in (2), the PUSCH resource efficiency and the probability of preamble collisions between the traditional RA procedure and the proposed RA procedure. The PUSCH re- source efficiency is defined as ratio between the number of PUSCH for successful accesses and the total number of avail- able PUSCH. In Fig. 5, when Nm is smaller than the number of available resources, the overall resource efficiencies for both the traditional RA and the proposed RA are very low. However, with the increase of Nm, the proposed RA scheme outperforms the traditional RA thanks to a more reasonable resource allocation between PRACH and PUSCH. It is worth observing that in traditional RA, the overall resource efficiency is the same as PUSCH resource efficiency. This is because the number of available PRACH is the same as the number of Fig. 5. Comparison of resource efficiency and preamble collision probability between traditional PA procedure and proposed RA procedure. available PUSCH. Regarding the PUSCH resource efficiency, the proposed RA maintains a value of almost 100% even when the probability of preamble collisions increases. In contrast, the PUSCH resource efficiency in traditional RA drops greatly due to serious preamble collisions. Moreover, the probability of preamble collisions in the proposed RA is also lower than that of traditional RA because the wasted RBs are reallocated to PRACH and PUSCH. V. CONCLUSION In this letter, we propose a new RA procedure and a resource allocation scheme for M2M communications. In the proposed RA procedure, eNB can detect the preamble collisions in the first step, and will not schedule PUSCH to the collided preambles. Based on the proposed RA procedure, a resource allocation scheme which achieves a reasonable resource allo- cation between PRACH and PUSCH is proposed. Simulation results show that the proposed RA outperforms the traditional RA procedure in terms of successful accesses, the resource efficiency and the probability of preamble collisions. REFERENCES [1] M. Islam, A.-E. Taha, and S. Akl, “A survey of access management tech- niques in machine type communications,” IEEE Commun. Mag., vol. 52, no. 4, pp. 74–81, Apr. 2014. [2] A. Laya, L. Alonso, and J. Alonso-Zarate, “Is the random access channel of LTE and LTE-a suitable for M2M communications? A survey of alter- natives,” IEEE Commun. Surveys Tuts., vol. 16, no. 1, pp. 4–16, 1st Quart., 2014. [3] T. Kwon and J.-W. Choi, “Multi-group random access resource allocation for M2M devices in multicell systems,” IEEE Commun. Lett., vol. 16, no. 6, pp. 834–837, Jun. 2012. [4] H. S. Jang, S. M. Kim, K. S. Ko, J. Cha, and D. K. Sung, “Spatial group based random access for M2M communications,” IEEE Commun. Lett., vol. 18, no. 6, pp. 961–964, Jun. 2014. [5] K. S. Ko et al., “A novel random access for fixed-location machine-to- machine communications in OFDMA based systems,” IEEE Commun. Lett., vol. 16, no. 9, pp. 1428–1431, Sep. 2012. [6] M. Hasan and E. Hossain, “Random access for machine-to-machine com- munication in LTE-advanced networks: Issues and approaches,” IEEE Commun. Mag., vol. 51, no. 6, pp. 86–93, Jun. 2013. [7] “Evolved universal terrestrial radio access (E-UTRA) medium access con- trol (MAC),” 3rd Generation Partnership Project, Sophia Antipolis Cedex, France, 3GPP TS 36.321, V12.2.1, Jun. 2014. [8] “Evolved universal terrestrial radio access (E-UTRA); Physical channels and modulation,” 3rd Generation Partnership Project, Sophia Antipolis Cedex, France, 3GPP TR 36.211, V12.2.0, Jun. 2014. [9] D. T. Wiriaatmadja and K. W. Choi, “Hybrid random access and data transmission protocol for machine-to-machine communications in cellular networks,” IEEE Trans. Wireless Commun., vol. 14, no. 1, pp. 33–46, Jan. 2015.