Compressive random access with multiple resource blocks and fast retrial
Jinho Choi




















1




E
M
H
K
X
Y
G
Q
F
H
T
d
ℤ
ℝ
ℂ
𝔼
𝕂
ℤ

definitionDefinition 
mypropertyProperty 
mytheoremTheorem 
mylemmaLemma 
myconjectureConjecture 
corollaryCorollary 
myproblemProblem 
myobservationObservation 
myremarkRemark 
myalgorithmAlgorithm 
myassumptionAssumption 
myexampleExample 


 def = 
 = 
 ·= 
 
    x y c d b q g i s a r u m n k h p z o e f v w A B C D E F G H I J K L M N S V P Q R W U X Y Z 1ξ0̱ 0ΦΨΓΣΔΩΛÂ A B C D F R I N S U V W R D EB I SINR SNR MSE h I S R D SR RD 15pt
         0pt
        
        
         15pt
         0pt
        
          =2500
          Compressive Random Access 
        with Multiple Resource Blocks and Fast Retrial
            Jinho Choi
        The author is with
        the School of Information Technology,
        Deakin University, Geelong, VIC 3220, Australia
        (e-mail: jinho.choi@deakin.edu.au).
            today
        ===========================================================================================================================================================
        
        
        In this paper, we propose a compressive random access (CRA) scheme 
        using multiple resource blocks (RBs) to support
        massive connections for machine type communications (MTC).
        The proposed CRA scheme is scalable. As a result, if the
        number of devices increases, more RBs can be added to support them.
        Thanks to multiple RBs, we 
        can employ fast retrial between RBs for re-transmissions of collided packets, 
        which can result in short access delay.
        For stable CRA with fast retrial,
        we derive conditions (with a rate control scheme),
        and analyze the steady state performance to find the throughput and 
        delay. 
        Through analysis and simulation results,
        we can see that the proposed scheme can perform better than
        conventional multichannel ALOHA and enjoy a trade-off between
        the performance and complexity in terms of the number of RBs.
        
        Internet of things; random access; machine type communications
         26pt
        
        
        § INTRODUCTION
        
        
        
        In 5th generation (5G) systems,
        there has been a growing interest in
        machine-type communications (MTC)
        for the Internet of Things (IoT) <cit.><cit.><cit.>.
        The applications of MTC are diverse from health care
        to smart grid,
        where a huge number of devices exist in the system, but
        only a few of them are active at a particular timing instance.
        Therefore, random access is suitable for MTC to accommodate
        a number of devices with sparse
        activity  <cit.>.
        
        A random access scheme, called random access
        (RACH) procedure, has been proposed for
        a cellular system, i.e., the long term evolution-advanced (LTE-A) system
        <cit.>.
        RACH procedure is a contention-based random access method,
        which is similar to the slotted ALOHA protocol <cit.>.
        In RACH procedure, there are multiple preambles
        in a preamble pool, 
        and a device can select a preamble randomly from 
        the pool and transmits the selected one for access. 
        It can be connected if there is no collision, i.e., 
        the preamble is not transmitted by any other devices.
        In addition to RACH procedure, there is a similar approach 
        in LTE-A for MTC, which is called narrowband-IoT (NB-IoT)
        <cit.>.
        
        Recently, the notion of compressive sensing (CS)
        <cit.> is employed
        to exploit the sparsity of active devices 
        for multiuser detection (MUD) in random access
        <cit.><cit.><cit.><cit.><cit.>.
        Among many devices present in MTC, only a few of them 
        attempt to access the network by transmitting their signature waveforms.
        The sparse activity of devices, which can be modeled as a sparse vector,
        allows the principle of 
        CS to be effectively applied to
        MUD with low complexity.
        When CS based MUD is employed,
        the resulting random access scheme is often called
        compressive random access (CRA) <cit.>.
        CRA is similar to code division multiple access (CDMA)
        <cit.><cit.>
        in a way to transmit data symbols 
        (where spreading codes are used to transmit data symbols with multiple
        access), while 
        it is a random access scheme that requires active user detection 
        as the spreading codes used are unknown in advance at a receiver.
        In CRA, spreading codes are not 
        necessarily orthogonal
        due to MUD that can detect multiple signals in the
        presence of interference <cit.><cit.>.
        Consequently, the main advantage of CRA over conventional multichannel
        random access schemes based on orthogonal channels (e.g.,
        multichannel ALOHA) is the increase of the number of channels that
        can reduce the probability of collision and improve the throughput
        <cit.>
        at the cost of increased complexity at a receiver.
        In addition, CRA supports grant-free transmissions.
        Thus, as in <cit.>, grant-free CRA can be more efficient
        than grant-based schemes (e.g., <cit.>, <cit.>)
        since it does not need to wait for the grant from an access point (AP).
        
        Grant-free CRA schemes <cit.> can be characterized by 
        a unique signature sequence for each device.
        Thus, the number of devices 
        becomes limited by the number of signature sequences.
        To support many devices in MTC, 
        although a wide bandwidth is considered,
        this can result in two difficulties: 
        i) a long sequence is required to accommodate a number of devices
        regardless of sparse activity;
        ii)
        the complexity of CS algorithms for MUD can be high due to 
        a large number of columns (or signature vectors) in a measurement matrix
        (a high computational complexity).
        To avoid the above difficulties,
        we can apply the approach used in the RACH procedure 
        to grant-free CRA.
        That is, instead of assigning a unique signature to each device,
        a randomly selected signature 
        from a pool of pre-determined signatures can be used when an active
        device is to transmit signals to a receiver or AP,
        where a signature code is used as a spreading code
        to transmit data symbols as in CRA.
        This approach is studied in <cit.>,
        while it suffers from collision that
        happens when multiple active devices choose the same signature.
        
        In this paper, we generalize the CRA scheme in <cit.>
        using multiple resource blocks (RBs) 
        in a multicarrier system with a certain re-transmission strategy. 
        In the proposed scheme,
        we divide subcarriers into multiple groups, or RBs,
        so that it becomes scalable,
        since more RBs can be added to support more devices in MTC.
        At the AP, parallel multiple CS-based detectors can be employed 
        for MUD with low complexity.
        In addition, thanks to multiple RBs,
        we can employ fast retrial <cit.> between RBs
        for re-transmissions of collided packets.
        In fast retrial, when a device experiences collision in the current
        time slot, this device can re-transmit 
        in the next time slot without random backoff. As a result,
        the access delay can be short.
        In summary,
        the main advantage of the proposed CRA
        scheme over other grant-free CRA schemes (with single big RB)
        <cit.>
        is mainly three-fold: 
         i) scalability;
         ii) a low computational complexity for CS based MUD; 
         iii) fast retrial between RBs for short access delay.  
        The main contributions[Note that multiple 
        RB based CRA has been studied in <cit.>.
        However, in <cit.>, no re-transmission is considered
        (this paper is an extension of <cit.>).]
        of the paper can also be summarized
        as follows:  a) a scalable grant-free CRA scheme is proposed
        not only to support a large number of devices with a reasonably
        low complexity for CS based MUD, but also to accommodate
        fast retrial;
         b) the stability and steady-state performance are analyzed
        under certain assumptions to see the impact of
        the number of RBs as well as other parameters
        on the performance of the proposed CRA scheme.
        
        
        
        The rest of the paper is organized as follows.
        In Section <ref>, we present a system model for CRA
        with multiple RBs in a multicarrier system.
        We discuss CS based MUD in Section <ref>
        and propose a model for its recovery performance in CRA.
        With a rate control scheme, we analyze the stability of the proposed CRA
        scheme with fast retrial in Section <ref>.
        To understand the throughput and access delay,
        we study a steady state analysis in Section <ref>.
        In Section <ref>,
        simulation results are presented with theoretical results
        obtained from Section <ref>.
        We finally conclude the paper with some remarks in Section <ref>.
        
        
        
         Notation:
        Matrices and vectors are denoted by upper- and lower-case
        boldface letters, respectively.
        The superscripts  and 
        denote the transpose and complex conjugate, respectively.
        
        
        [·]
        and Var(·)
        denote the statistical expectation and variance, respectively.
        (, )
        represents the distribution of
        circularly symmetric complex Gaussian (CSCG)
        random vectors with mean vector  and
        covariance matrix .
        
        
        
        
        § SYSTEM MODEL
        
        
        Consider uplink transmissions from a number of devices to an AP.
        Suppose that 
        when a device becomes active to transmit a packet,
        it can transmit its packet without any permission (i.e.,
        grant-free transmissions are assumed) <cit.>.
        For uplink transmissions,
        a radio resource block is divided into
        M RBs and each RB is orthogonal to each other.
        In each RB, there are N spreading codes (SCs) of length L.
        For grant-free CRA, an active device 
        is to randomly choose an RB and an SC for data transmissions.
        Throughout the paper, we assume a multicarrier system
        that has J = L M subcarriers. Thus, an RB
        consists of L subcarriers and each SC
        is a multicarrier spread sequence of length L<cit.>.
        In Fig. <ref>, we illustrate multiple RBs
        with J subcarriers in the frequency domain.
        
        
        
        
        Let = [_0  …_N-1] denote
        a matrix of N SC vectors
        where _n denotes the nth SC, which is a multicarrier 
        spread sequence of length L.
        Thus, the size of  becomes L × N, and
        in general L ≤ N,
        which implies that the SC sequences can be non-orthogonal.
        For convenience, let
        
            η = N/L,
        
        which is referred to as the virtual bandwidth expansion factor.
        Note that if SC sequences are orthogonal to each other,
        we have η = 1 (i.e., N = L).
        We assume the same set of SC sequences for all RBs.
        
        Suppose that
        a packet consists of T symbols and 
        each active device can choose one of M
        RBs uniformly at random.
        At the AP, the received signal vector at (symbol) time t over the mth RB
        is given by
        
            _m,t    = [y_m,t,0 … y_m,t,L-1]^    = _m,t + _m,t,
             t = 0,…,T-1,
        
        where y_m,t,l represents the received signal
        at time t
        through the lth subcarrier of the mth RB,
        _m,t is a random access vector at time t, and
        _m,t =  [n_m,t,0 … n_m,t,L-1]^∼(0, N_0 ) is the background noise.
        Note that the RBs are orthogonal. Thus, there is no interference
        from the other RBs. 
        
        Let _m,n denote
        the index set of the active devices that
        choose the mth RB and the nth SC.
        Assuming that the channel gain remains
        unchanged within the duration of a packet 
        transmission, 
        the nth element of _m,t is given by
        
        [_m,t]_n = ∑_k ∈_m,n h_k,m x_k,t,
        	
        where h_k,m denotes the (frequency-domain) channel coefficient
        from device k to the AP over the mth RB and x_k,t represents the 
        signal from device k at time t.
        In (<ref>), we assume that the bandwidth of an RB
        is sufficiently narrow so that the frequency-domain channel gain
        remains unchanged within the bandwidth of an RB.
        The total number of active devices is given by
        K = ∑_m=1^M ∑_n=1^N |_m,n|
        and the number of active devices that choose the mth RB is given by
        K_m =  ∑_n=1^N |_m,n|.
        Thus, we have K = ∑_m=1^M K_m.
        In general, we expect to have K_m ≪ N
        due to sparse activity.
        
        For convenience,
        the above random access
        system with multiple RBs (i.e., M > 1) is referred to as the 
        multiple RB (MRB) based CRA 
        (MRB-CRA) system in this paper.
        In addition, we employ fast retrial <cit.> between RBs
        to re-transmit collided packets for short access delay.
        That is, if an active device has a collided packet,
        this packet can be immediately re-transmitted in the next time 
        slot[In the paper, we assume that the length of packet
        is equivalent to the length of time slot.]
        through a randomly selected RB among M RBs.
        
        It is noteworthy that the resulting system
        becomes scalable. Thus, if the number of devices increases,
        we can add more RBs,
        which of course increases the system bandwidth
        as shown in Fig. <ref>.
        In addition, at an AP, there can be M parallel MUDs
        to recover sparse signals in each RB.
        This feature might be important to reduce the processing time
        at the AP since the total processing time becomes identical
        to the processing time of MUD for one RB if a parallel processor
        is used to implement the receiver <cit.>.
        
        
        Although we assume that 
        an RB is selected uniformly at random in this paper,
        it is also possible to choose it based on the channel
        state information (CSI) at each active device to lower the transmission power.
        In (<ref>), we need to adjust 
        the amplitude of x_k,t to overcome
        fading if the channel gain, |h_k,m|, is low.
        In general, each device can choose the
        amplitude of x_k,t to be inversely proportional to
        the channel gain to equalize the overall signal gain.
        In this case, if |h_k,m| is low,
        the transmit power has to be high, which is not desirable.
        In the MRB-CRA system, this problem
        can be mitigated if an active device can choose
        the RB of the highest channel gain.
        That is, active device k can choose the RB as follows:
        m(k) = _m |h_k,m|,
        where m(k) denotes the index of the selected RB by active
        device k. Since the channel gains are random,
        the selection of RBs by active devices becomes also random
        and active devices could be uniformly distributed over multiple
        RBs in this case as well 
        (provided that h_k,1, …, h_k,M are iid).
        From this, throughout the paper, we assume
        that the power control
        is adopted to equalize
        the overall signal gain as follows:
        
            |h_k,m(k) x_k,t| = √(P),  ,
        
        where P is the transmit power.
        Thus, the signal to noise ratio (SNR) becomes SNR = P/N_0.
        Throughout the paper, 
        we assume that the SNR is sufficiently high.
        Note that a similar approach is considered in <cit.>,
        where the phase of the signal is also compensated.
        
        
        
        
        § CS BASED MUD
        
        
        In this section, we focus on CS based MUD for one RB
        (as each RB has the same structure)
        to recover multiple signals and propose a model for the performance
        analysis.
        
        
        
         §.§ CS based Signal Recovery
        
        
        For convenience, since we consider 
        one RB, we omit the RB index m if there is no risk of confusion.
        Let = [_0  … _T-1],
        = [_0  … _T-1],
        and = [_0  … _T-1].
        Then, (<ref>) becomes
         =  + .
        	
        Let  denote the support of _t.
        If  is seen as a measurement matrix,
        the estimation of  
        from  in (<ref>) is a typical multiple measurement
        vectors (MMV) problem <cit.><cit.> as
        the support of _t is the same for all t.
        Under the high SNR assumption or ignoring ,
        the MMV sparse recovery problem can be formulated as follows
        <cit.>:
        = _ | supp ()| 
           = ,
        	
        where supp () represents the support of
        matrix , which is defined by
        supp () = ⋃_i  supp(_i).
        Here, _i denotes the ith column vector of .
        In this case, 
        a sufficient and necessary condition to estimate <cit.>
        is given by
        
        N <  spark() -1 +  rank()/2,
        	
        where spark() is
        the smallest number of columns from   that are linearly dependent
        <cit.>.
        It can be readily shown that
        rank() ≤min{N, T}.
        Since each element of  is iid, 
        we have
        rank() = N if T ≥ N with probability (w.p.) 1.
        From this, (<ref>) is reduced to 
        
            N    ≤ D
             spark() - 2,
        
        where D is the sparsity threshold for a recovery guarantee.
        If  is random
        (e.g., all the elements of  are independent CSCG random variables)
        and K ≥ L,
        spark() -1 =  rank() = L w.p. 1
        <cit.>.
        In this case, we have
        
        D = L - 1.
        	
        However, in practice, the sparsity threshold 
        might be smaller than 
        L-1 due to various reasons. 
        For example, for low-complexity implementations,
        greedy algorithms 
        can be used, which result in suboptimal performances.
        In addition, due to the background noise, there might be performance
        degradation.
        
        
        
         §.§ A Model for Recovery Performance
        
        
        
        Throughout the paper, we assume that 
        the AP is able to recover the signals of up to D-sparsity in each RB,
        where D < L. That is, we consider
        the following assumptions.
        
           A1 If the number of active devices in an RB is greater than
        D, the AP cannot recover them at all.
        
           A2 If the number of active devices in an RB is less
        than or equal to D, the AP recovers the active devices whose SCs
        do not collide with each other.
        
        Clearly, D is a threshold value and
        depends on the properties of  including its
        size, i.e., N and L.
        Note that although there are more than D active devices,
        the AP may be able to recover some of
        them. However, for tractable analysis,
        we simply assume  A1.
        In  A2, it is assumed that
        although the AP can recover all the signals,
        it cannot resolve collided signals from the devices that choose
        the same SC.
        In general, in this paper, D is seen as a performance 
        indicator of CS based MUD to be estimated.
        
        Based on the assumptions of  A1 and  A2,
        when there are K_m active devices in RB m,
        since there are N SCs per RB,
        the average number of unsuccessful devices becomes
        
        U (K_m) = {[ K_m - 
        K_m (1 - 1/N)^K_m -1,                         K_m,                              ].
        	
        In Fig. <ref>, we show the average
        number of unsuccessful devices, i.e., U(K_m)
        when the simultaneous
        orthogonal matching pursuit (S-OMP) algorithm proposed in <cit.><cit.>
        is used for CS based MUD.
        Here, for simulations, we assume that each element of 
        is an independent CSCG random variable with zero mean and variance
        1/L.
        It is shown that U(K_m) from the simulation results
        follows K_m - K_m 
        (1 - 1/N)^K_m -1 when K_m is small.
        However, as K_m approaches a certain value, 
        U(K_m) increases rapidly. Thus, the model 
        in (<ref>) can be used to 
        analyze the performance of MRB-CRA,
        where we assume that there exists
        a threshold value D such that U(K_m) = K_m if K_m > D
        (i.e.,  A1). 
        
        Note that
        according to Figs. <ref> (a) and (b), D might be dependent on
        L. For example, 
        when L = 32, as shown in Fig. <ref> (a), 
        we can say D ≈ 0.6 L,
        while D ≈ 0.8 L when
        L = 64 according to Fig. <ref> (b).
        Furthermore, D also depends on the SNR.
        In addition, as mentioned earlier, although K_m > D,
        it is also possible that some signals can be recovered
        as shown in Fig. <ref>.
        If a better recovery algorithm is used, we expect to have
        a larger D, which results in a better performance.
        In <cit.>, the performances of different algorithms can be found,
        while we only consider S-OMP (for simulations) in this paper.
        
        
        
        
        
        In Fig. <ref>, we also show the number of unsuccessful
        devices of 
        conventional multichannel ALOHA, which is given by
        U_ aloha (K_m) = K_m - K_m ( 1 - 1/L)^K_m-1,
        where each RB has only L (not N) orthogonal[In order to
        increase the number of channels for a high
        throughput in multichannel ALOHA,
        non-orthogonal SCs can be used. In this case,
        a bank of correlators cannot be used at a receiver due to 
        interference and a CS based MUD approach needs to be
        used as in <cit.>, which results in CRA. Thus,
        by conventional multichannel ALOHA, we mean multichannel ALOHA
        with L orthogonal channels in this paper.]  SCs.
        In conventional multichannel ALOHA, it is not
        necessary to use CS based MUD due to orthogonal SCs. That is,
        a bank of correlators can be used to recover multiple signals.
        Although there is no interference, due to a smaller number of channels
        (not N, but L),
        the probability of collision is higher than that of CRA.
        As a result, as shown in 
        Fig. <ref>, the performance of conventional multichannel ALOHA
        would be worse that that of CRA.
        From this, we can claim that the advantage of CRA
        over conventional multichannel ALOHA is a low probability
        of collision thanks to an increased number of  (non-orthogonal virtual)
        channels (from L to N) at the cost of high recovery
        complexity at a receiver.
        Note that as we only consider S-OMP in this paper,
        it might be useful to consider the computational complexity
        of S-OMP. Since S-OMP is a greedy algorithm <cit.><cit.>,
        its computational complexity is not significantly high, which is
        mainly O ( c L^2 + N) per RB,
        where c > 1 is a constant.
        On the other hand, the complexity per RB at a receiver in conventional
        multichannel ALOHA might be O(L^2).
        
        It is important to note that the receiver complexity of MRB-CRA 
        with S-OMP decreases with M when J is fixed.
        Since the total computational complexity is
        O(M (c L^2 + η L)) = O ( c J^2/M + η J),
        we can clearly see that a large M (or more  RBs)
        is desirable for a low computational
        complexity.
        However, as shown in Fig. <ref>, if L decreases,
        D/L tends to decrease, which degrades
        the recovery performance. Thus, we can see that there might be a
        trade-off between the performance and complexity
        (this will be confirmed by simulations in Section <ref>).
        
        
        
        
        § STABILITY ANALYSIS WITH FAST RETRIAL
        
        
        In <cit.>, for multichannel ALOHA,
        a re-transmission strategy which is called fast retrial
        is proposed, where a collided packet is re-transmitted at the next
        slot without any random backoff delay thanks
        to the existence of multiple channels.
        Since we assume multiple RBs for CRA, i.e., MRB-CRA, 
        fast retrial can be employed
        as a re-transmission strategy for collided SCs as mentioned in
        Section <ref>.
        In this section, we study the stability of MRB-CRA with fast retrial.
        
        
        
        Suppose that a device experiencing SC collision
        attempts re-transmission in the next
        slot based on fast retrial <cit.>. 
        For re-transmission,
        the device chooses
        an RB among M RBs and an SC within the selected
        RB uniformly at random.
        There are also new active devices.
        For convenience, let A_m (q) denote the number of new active devices
        to RB m at time slot q. Here, q is used for 
        the time
        slot index.
        Thus, K_m (q) is a sum of 
        the numbers of new packets[We assume that
        packets and active devices are interchangeable in this section
        as an active device transmits a packet.]
        and re-transmitted packets,
        where K_m (q) represents the number of active devices
        transmitting packets to RB m at time slot q.
        Throughout the paper,
        we consider 
        an independent Poisson random variable for A_m(q) as follows:
        (A_m(q) = n) = λ^n e^-λ/n!,
        	
        where λ is the arrival rate per RB,
        i.e., A_m (q) ∼ Pois (λ). Here,
        Pois (λ) denotes the distribution
        of a Poisson random variable with mean λ.
        
        In fast retrial, thanks to multiple RBs, we consider the following 
        rate control strategy.
        
           A3 If K_m(q) > K̅, the AP informs the devices not to 
        send any new packets, where K̅ (> D)
        is a pre-determined threshold.
        
        This rate control strategy is necessary to avoid
        the growth of K_m (q) so that the access delay cannot be arbitrarily long.
        Note that there can be other rate control strategies. However,
        for simplicity, we only consider  A3.
        According to  A3, 
        the AP needs to broadcast the binary signals that inform
        the states of RBs (whether or not K_m(q) is greater than K̅).
        Thus, at the beginning of
        each (uplink) time slot, there should be a broadcast signal 
        of M bits from the AP to devices
        for the rate control.
        
        
        Let (q) = [K_1 (q)  … K_M (q)]^.
        Under the assumptions of  A1 and  A2,
        we define the number of unsuccessfully recovered packets
        in RB m at time slot t as 
        
        [K_m (q)]_D = {[ K_m (q),       i,          ].
        
        where
        β (K_m,i) represents the probability
        that there are i
        collided SCs when there are K_m  (≤ N) packets 
        and each packet independently chooses one among N SCs.
        Clearly, [K_m (q)]_D is a random variable.
        
        
        
        
        
        
        
        
        
        
        With fast retrial, the unsuccessfully recovered packets are 
        scheduled to re-transmit in the next time slot.
        The number of re-transmitted packets 
        from RB m at time slot q to RB l at time slot q+1 
        is denoted by _m,l (i), where i represents the 
        number of unsuccessfully recovered packets in RB m at time slot q.
        Then, the total number of packets 
        in RB m at time slot q+1 can be expressed as
        
        K_m (q+1) = ∑_l = 1^M _m,l ([K_l (q)]_D) + 
        Ã_m (q+1),
        	
        where 
        Ã_m (q+1) = {[ A_m (q+1),       ;
        0,            ].
        
        Note that (<ref>) is due to the rate control of  A3.
        From (<ref>) and (<ref>), we can see that (q) becomes
        a Markov process.
        We derive a sufficient condition for stability
        as follows.
        
        
        Let A̅_m = [A_m (q)]. With the rate control of  A3,
        if 
        A̅_m = λ < 
        B_D,N D (1 - 1/N)^D-1,  ,
        	
        then (q) is positive recurrent.
        
        See Appendix <ref>.
        
        
        In (<ref>), it is noteworthy that
        B_D, N≈ D if N ≫  D.
        This indicates that the new arrival rate
        per RB is to be less than D for stable MRB-CRA when N ≫ L > D.
        This indicates that the estimation of D
        plays a crucial role in MRB-CRA with fast retrial.
        
        
        
        § PERFORMANCE ANALYSIS OF MRB-CRA
        
        
        In this section, 
        in order to find the throughput and delay of MRB-CRA,
        we consider a steady state analysis 
        with a receiver that is capable of recovering D multiple signals.
        
        
        
         §.§ A Steady State Analysis
        
        
        In general, the throughput analysis of 
        MRB-CRA with fast retrial is not easy due to the interaction
        between multiple RBs in terms of their numbers of
        the packets to be re-transmitted.
        That is, K_m(q+1) depends on
        K_l (q), l = 1,…, M, as shown in (<ref>).
        To avoid this difficulty, in the steady state, we assume that
        the number of packets to be re-transmitted 
        (or collided packets in the previous time slot) in each RB 
        is an independent Poisson random variables with mean λ_2,
        i.e., 
        
            ∑_l=1^M _m,l ( [K_l (q)]_D ) 
            ∼ Pois (λ_2),  m = 1,…,M,
        
        where λ_2  =
        [
        ∑_l=1^M _m,l ( [K_l (q)]_D ) ].
        Clearly, this assumption is not true. However,
        if M is sufficiently large,
        it might be a reasonable approximation such as
        the Kleinrock independence approximation <cit.><cit.>.
        
        Suppose that the arrival rate
        is sufficiently low so that Ã_m (q) = A_m (q) for all q,
        i.e., the rate control of  A3 is hardly imposed.
        Although this is an approximation, 
        we assume this for tractable analysis (i.e., the approximation
        allows us to simplify the analysis, while simulation
        results in Section <ref> show that this approximation
        is reasonable).
        Since the packets to be re-transmitted
        are to be re-allocated to the RBs uniformly at random,
        from (<ref>),
        we assume that 
        K_m (q+1) becomes a Poisson 
        random variable[Since the sum of two independent
        Poisson random variables with means
        λ_a and λ_b is a Poisson random variable
        with the mean λ_a + λ_b, we can assume
        that K_m (q+1) is also a Poisson random variable.]
        with mean λ + λ_2.
        For convenience, let
        λ_1 = λ + λ_2,
        	
        which is the average number of packets to be transmitted per RB
        as illustrated in Fig. <ref>.
        
        
        
        
        Suppose that 
        K_m (q) ∼ Pois (λ_1).
        Under  A1 and  A2, 
        λ_2 can be given by
        
            λ_2 
            = λ_1 ( 1 - e^-λ_1/NΓ(D,ν_1)/(D-1)!),
        
        where ν_1 = λ_1 ( 1  - 1/N)
        and Γ(d, x) = ∫_x^∞
        t^d-1 e^-t dt is the upper incomplete gamma function.
        
        See Appendix <ref>.
        
        
        To satisfy (<ref>) and (<ref>),
        we can show that
        λ has to be bounded as
        
            λ≤λ_ max 
            = max_λ_1λ_1 
             e^-λ_1/NΓ(D, ν_1)/(D-1)!,
        
        where λ_ max denotes the maximum of λ.
        In addition, denote by λ_1^* the solution to (<ref>).
        Clearly, if λ is less than or equal to 
        λ_ max, the steady state solution that satisfies
        (<ref>) and (<ref>) exists.
        
        Since e^-λ_1/N < 1,
        from (<ref>),
        an upper-bound on λ_ max can be found as follows:
        λ̅_ max 
        = max_λ_1λ_1 
        Γ(D, ν_1)/(D-1)!≥λ_ max.
        	
        Note that as N increases, 
        λ̅_ max becomes tighter and
        approaches λ_ max.
        
        
        For D > 1,
        there exists N > 0 such that
        λ̅_ max < B_D,N,
        	
        which guarantees stable MRB-CRA with fast
        retrial (according to Theorem <ref>) for
        λ≤λ_ max
        (since λ_ max < λ̅_ max).
        
        See Appendix <ref>.
        
        
        Consequently, for a given D,
        we can find the maximum arrival rate,
        λ_ max from (<ref>).
        As long as the arrival rate is lower than or equal to
        λ_ max, we can also guarantee stable MRB-CRA with fast
        retrial according to Theorems <ref> and  <ref>.
        In fact, with λ≤λ_ max(< λ̅_ max < B_D,N),
        we can also expect that the rate control of  A3 may not be frequently
        used as K_m (q) might stay around λ_1 which is smaller
        than D, i.e., most transmitted packets become successful packets.
        However, to decide λ,
        we first estimate D based on the performance of CS based MUD
        for a given set of parameters (e.g., L, N, and SNR).
        Thus, as mentioned earlier, the estimation of D 
        is important in MRB-CRA.
        
        
        
        
         §.§ Throughput and Delay in the Steady State
        
        
        In the steady state, 
        for a given λ satisfying (<ref>),
        we can find λ_1
        by solving (<ref>) and (<ref>) as shown above.
        With λ_1,
        under  A1 and  A2,
        the throughput per RB
        can be given by
        
            T_ cra    = ∑_n=0^D e^-λ_1λ_1^n/n!
            n (1 - 1/N)^n-1    = λ_1 e^-λ_1∑_n=0^D 1/n!( λ_1 (1 - 1/N) )^n    ≤λ_1 e^-λ_1/N ,
        
        where the upper-bound becomes tight when D - λ_1 is large.
        Recall that η = N/L. Then, it follows
        
            T_ cra≤λ_1 e^-λ_1/N 
            = λ_1 e^- Λ_1/η J,
        
        where Λ_1 = M λ_1.
        
        We can find the average access
        delay from the relationship between λ_1
        and λ as shown in Fig. <ref>.
        The average number of packets to be transmitted
        (in a time slot), λ_1,
        can be seen as the number of devices in a system, while
        λ is the average number of devices (within a time slot)
        entering into the system.
        Based on Little's law <cit.>,
        the average access delay (in the number of slots) can be found 
        as
        τ = λ_1/λ.
        	
        
         §.§ Comparison with Multichannel ALOHA
        
        
        It might be interesting to compare the throughput of MRB-CRA
        with that of conventional multichannel ALOHA.
        
        Suppose that there are L orthogonal
        channels 
        per RB in conventional
        multichannel ALOHA.
        In an RB, when there are n active devices,
        the number of successfully transmitted packets is
        given by n (1 - 1/L)^n-1.
        Thus, the average number of successfully transmitted packets is
        
            T_ aloha 
            = ∑_n n (1 - 1/L)^n-1λ^n e^-λ/n! 
            = λ e^-λ/L.
        
        According to <cit.>, the maximum stable throughput
        (per RB)
        becomes 
        
        T_ aloha≤T̂_ aloha = L e^-1.
        
        
        Let Λ = M λ, which is the total arrival rate
        to the system. In MRB-CRA, since D < L, 
        from (<ref>) and (<ref>),
        we can have the following inequality:
        
            λ = Λ/M < B_D, N < L,
        
        which shows that the total arrival rate, Λ, cannot be 
        greater than J, i.e.,
        Λ < M L = J.
        	
        However, if Λ is sufficiently close to J so that
        Λ_1 = J 
        (note that since Λ < Λ_1, the inequality
        in (<ref>) is valid in this case),
        from (<ref>), we have
        
        T_ cra≈λ_1 e^-1/η≤ L e^-1/η.
        
        
        As η≫ 1, we have e^-1/η > e^-1, from which 
        it can be claimed that
        the throughput of MRB-CRA can be higher than that of conventional multichannel
        ALOHA. 
        For example, under
        the optimistic assumption that λ_1 is sufficiently close to L,
        if η≥ 3.258, we can claim that the throughput of MRB-CRA
        can be higher than that of multichannel ALOHA by
        at least a factor of 2.
        
        It is noteworthy that in <cit.>,
        it is shown that the throughput of MRB-CRA can be about two-time higher
        than that of multichannel ALOHA when a certain controlled access
        probability strategy is employed.
        Unfortunately, in this paper, we cannot find the throughput of MRB-CRA
        with fast retrial as a closed-form expression (i.e.,
        no closed-form expression for λ is obtained).
        Thus, we can consider 
        simulations 
        (as shown in Fig. <ref> 
        and in the next section)
        for comparisons with conventional
        multichannel ALOHA.
        
        
        
        § SIMULATION RESULTS
        
        
        In this section, we present simulation results
        for MRB-CRA with fast retrial.
        For simulations, we consider
         whose elements are
        independent CSCG random variables with zero mean and variance
        1/L. As mentioned earlier, the S-OMP 
        algorithm is used for CS based MUD to detect multiple signals at an AP.
        To see the performance, we mainly
        consider the average number of transmitted packets per RB,
        [K_m (q)], and
        the average number of successful packets per RB,
        which might be identical to λ
        (wile λ_1 =[K_m (q)]) in the steady state for 
        stable MRB-CRA.
        From (<ref>), for short access delay,
        we expect that 
        the average number of transmitted packets per RB
        is not too larger than that of successful packets per RB.
        
        We consider two different approaches to decide the arrival
        rate per RB, λ. In the first approach,
        we fix D for given (L, N) and decide λ 
        to be λ_ max in (<ref>).
        In the second approach, λ is directly decided.
        In Fig. <ref>,
        we present the evolution of ∑_m K_m (q)
        and ∑_m A_m (q) over time slots when 
        (L, M) = (32, 8), η = 10, K̅ = 2L, and SNR = 20 dB.
        In the upper figure in 
        Fig. <ref>, the first approach is used to decide
        λ with D = 25. In this case, λ becomes
        16.04. 
        On the other hand, 
        in the lower figure in
        Fig. <ref>, the second approach is used with λ = 20.
        We can see that the determination of D can help decide
        a proper arrival rate, λ, to keep K_m (q) low
        so that the access delay is short.
        On the other hand, if λ happens to be high,
        it may result in large K_m (q)'s and unstable MRB-CRA. 
        Note that λ = 20
        corresponds to about D = 31 from (<ref>).
        Thus, in order to support λ = 20, CS based MUD or
        the recovery algorithm
        should be capable of detecting D = 31 multiple signals.
        If we use an ideal method, it might be achievable
        according to (<ref>) as L = 32.
        However, the S-OMP algorithm is a greedy algorithm that has a suboptimal
        performance. Thus, a more realistic value for D might 
        be considered. From Fig. <ref>, D = 25 seems a reasonable
        estimate of D to decide λ.
        
        
        
        Fig. <ref> (a) shows 
        the number of successful packets
        (or successfully recovered packets) 
        and the number of transmitted packets per RB
        for different values of D to decide λ
        according to the first approach
        (i.e., using (<ref>) for given D)
        when (L, M) = (32, 8), η = 10, K̅ = 2D, and SNR = 20 dB.
        This shows that if the value of D is less than
        80% of L (i.e., D ≤ 26), 
        the arrival rate might be sufficiently low so that
        K_m (q) does not significantly grow.
        In other words, D ≤ 26 might be an underestimate of the recovery
        performance.
        On the other hand, if D is decided to be too high or
        the performance of CS based MUD is overestimated,
        K_m (q) grows 
        and the rate control of  A3 has to be imposed to avoid
        any excessive delay.
        In Fig. <ref> (b), we present the normalized
        access delay, which is the ratio of 
        the number of transmitted packets to
        the number of successful packets as in (<ref>),
        where it is shown that
        an overestimate of D results in a relatively long access delay.
        
        
        
        
        For comparison with 
        conventional multichannel ALOHA,
        the throughput (i.e., the average number of successful packets per RB)
        is shown for different values of arrival rate,
        λ,
        in Fig. <ref>
        when (L, M) = (32,8), η = 10, K̅ = 2L, and SNR =20 dB.
        For conventional multichannel ALOHA, we consider
        the controlled access probability 
        proposed in <cit.> 
        with the assumption that the number of transmitted packets
        at each slot is available at the devices to decide their access probability.
        We can see that MRB-CRA outperforms conventional multichannel ALOHA
        in terms of both the throughput and access delay.
        
        
        
        Note that in Fig. <ref>, the throughput and access delay
        of MRB-CRA behave differently when λ/L ≥ 0.6 or λ≥ 19. 
        As mentioned earlier, if λ is too high,
        the rate control of  A3 is imposed to keep the access delay
        reasonable, which, however, results in a lower throughput.
        
        
        
        In order to see the impact of L on the performance,
        we show the total number of successful
        packets and the total number of transmitted packets (i.e.,
        [∑_m K_m (q)]) as well as the complexity
        for different values of L 
        when the total number of
        subcarriers is fixed as J = 512 in Fig. <ref> 
        with SNR =20 dB and Λ = 0.8J
        (or λ = 0.8 L).
        As mentioned earlier, the performance
        of S-OMP is improved as L increases, which means that D can increase
        with L (which can be confirmed by Fig. <ref>).
        Thus, for given λ = 0.8 L, 
        D should be at least greater than 0.8 L
        for reasonable performances of MRB-CRA 
        or stable MRB-CRA (with reasonably short access delay). 
        As shown in Fig. <ref> (a), we need L ≥ 32
        for reasonably good performances. 
        Furthermore, as L increases, we can see that the performance
        is improved as expected. However, 
        Fig. <ref> (b) shows that the complexity
        increases with L (as M decreases with L since J is fixed).
        Thus, one big RB is not desirable for CRA due to high computational
        complexity.
        As mentioned earlier, this exhibits the trade-off between
        the performance and complexity.
        
        
        
        
        
        
        Fig. <ref>, we show
        the number of successful packets
        and the number of transmitted packets
        for different values of the virtual bandwidth expansion
        factor, η,
        when (L, M) = (32,8), D = 25, and SNR =20 dB.
        It is shown that as η increases, the number of
        transmitted packets per RB, [K_m(q)], decreases. Thus,
        it is desirable to have a large
        η (i.e., greater than 5)
        to generate more virtual channels per RB to reduce the probability of
        collision and result in a better performance.
        However, since N increases with η, the increase of η
        results in  a higher computational complexity. Thus,
        η should not be too large. From
        Fig. <ref>, η = 6 or 7 seems a reasonable
        choice to provide a good performance with a relatively low complexity.
        
        
        
        § CONCLUDING REMARKS
        
        
        We have proposed an MRB-CRA scheme with fast
        retrial in this paper. It was shown that
        the proposed scheme is not only scalable, but also
        computationally efficient in terms of receiver's complexity
        due to multiple RBs. We carried out
        the stability analysis based on
        the Foster-Lyapunov stability criterion,
        and derived a maximum arrival rate 
        for stable MRB-CRA with fast retrial. Furthermore,
        we studied a steady state analysis
        to find the throughput and delay of MRB-CRA.
        Through analysis and simulation results,
        it was shown that the proposed MRB-CRA scheme can have a higher
        throughput than
        conventional multichannel ALOHA with a lower
        access delay and enjoy a trade-off between
        the performance and complexity in terms of the number of RBs.
        
        
        
        
        § PROOF OF THEOREM <REF>
        
        
        To show that (q) is positive recurrent,
        we can use the notion of Lyapunov function that is a nonnegative
        potential function <cit.>.
        In particular, from a Lyapunov function, we can have the drift function,
        which represent the variation of Lyapunov function in time.
        If the drift function satisfies certain conditions,
        we can show that (q) is positive recurrent.
        
        Let V(q) = ∑_m=1^M K_m (q) be the Lyapunov function,
        which is a nonnegative function for 
        
            Ω = { = [K_1  … K_M]^ |  K_m ∈{0, …, MK̅}}.
        
        Note that Ω is a finite set 
        as the maximum 
        value of K_m (q) is M K̅ due to the assumption of  A3.
        Based on Foster's theorem <cit.>,
        using the Lyapunov function V(q),
        we can show that (q) is positive recurrent if (<ref>)
        holds.
        
        In (<ref>), since the next RB is uniformly chosen
        at random by an active device
        experiencing collision, it can be shown that
        [_m,l ([K_l (q)]_D) |  [K_l (q)]_D = i]
        = i/M.
        	
        Suppose that K_m ≤ D. 
        Then, [K_m]_D can be expressed as
        
        [K_m]_D  = K_m  - ∑_n=1^N  (X_n^K_m = 1),
        	
        where X_n^K_m denotes the number of active devices
        that choose SC n when there are K_m active
        devices in RB m.
        From (<ref>) and (<ref>),
        we have
        [_m,l ([K_l (q)]_D) |  K_l (q) = K_l] =
        K_l - ∑_n=1^N (X_n^K_l = 1)/M.
        	
        Since the event of X_n^K_l = 1
        means that there is only one device choosing
        SC n and the other devices choosing the other SCs
        when there are K_l active devices in RB l,
        it can be shown that
        
            (X_n^K_l = 1)
             = K_l/N(1 - 1/N)^K_l-1.
        
        Substituting (<ref>) into (<ref>), and from
        (<ref>), 
        it can be shown that
        
            [K_m(q+1) | (q)]     = [ ∑_l=1^M _m,l ([K_l(q)]_D) + 
            Ã_m (q+1)  | (q)
            ]     =  1/M∑_l=1^M U_D ( K_l (q) ) + 
            A̅_m (K_m (q) ≤K̅),
        
        where
        
        U_D (K_l) = 
        {[                       K_l, K_l (1 - ( 1 - 1/N)^K_l-1)                            ].
        
        
        Let
        = { |  K_m <  B_D,N  D < K_m ≤ M K̅,
         m = 1,…, M}.
        Suppose that (q) ∈Ω -.
        In this case, 
        we have B_D,N≤ K_m(q) ≤ D.
        Since
        
            U_D (K_l(q))     = 
            K_l (q) (1 - ( 1 - 1/N)^K_l (q)-1) A̅_m (K_m (q) ≤K̅)     = A̅_m,
        
        the drift of V(q) can be found as
        
            [V(q+1) | (q)] - V(q)     = ∑_m=1^M U_D (K_m(q)) - K_m (q) + A̅_m     = ∑_m=1^M A̅_m - K_m (q) 
             ( 1 - 1/N)^K_m (q)-1.
        
        Consider the function of k, g(k) = k (1 - 1/N)^k-1,
        which is an increasing function of k when 
        0 ≤ k ≤ - 1/ln( 1 - 1/N) < N.
        From this and noting that D ≤ N, we have
        
            K_m (q) 
             ( 1 - 1/N)^K_m (q)-1≤ D ( 1 - 1/N)^D-1 = B_D,N,
        
        which implies that
        [V(q+1) | (q)] - V(q) ≤∑_m=1^M (A̅_m - B_D,N).
        	
        From (<ref>), if (<ref>) holds, we can conclude that
        [V(q+1) | (q)] - V(q) < 0,
          (q) ∈Ω - .
        	
        On the other hand, if (q) ∈,
        we have either
        U_D(K_l(q)) - K_l(q) + A̅_m 
        (K_m (q) ≤K̅)
        ≤A̅_m (when K_l (q) > D) or 
        U_D(K_l(q)) - K_l(q) + A̅_m
        ≤A̅_m
        (when K_l (q) < B_D,N).
        Thus, we have
        [V(q+1) | (q)] - V(q) ≤∑_m=1^M A̅_m,
          (q) ∈.
        	
        From (<ref>) and (<ref>),
        we can see that (q) is positive recurrent
        under the Foster-Lyapunov stability criterion
        <cit.>.
        
        
        
        
        § PROOF OF THEOREM <REF>
        
        Under  A1 and  A2,
        from (<ref>),
        it can be shown that
        
            [ [K_m (q)]_D ]
            =  ∑_n=0^D (n - 
            n ( 1 - 1/N)^n-1) p_n 
            + ∑_n=D+1^∞ n p_n,
        
        where p_n = (K_m (q)= n).
        Since K_m (q) ∼ Pois (λ_1),
        we have
        
            [ [K_m (q)]_D ]
                = λ_1 - λ_1 ∑_n=0^D-1
            n ( 1 - 1/N)^nλ_1^n e^-λ_1/n!    = λ_1
            (
            1 - e^- λ_1/NΓ(D, ν_1)/(D-1)!),
        
        which completes the proof.
        
        
        § PROOF OF THEOREM <REF>
        
        
        For convenience, let λ̅_1^* represent
        the solution to (<ref>).
        In <cit.>,
        it is shown that
        λ̅_1^* is smaller than D for D > 1,
        i.e., λ̅_1^* < D.
        We can also show that
        λ̅_ max < λ̅_1^* < D,   D > 1.
        	
        The first inequality in
        (<ref>) is obtained by the fact that
        λ̅_1 e^-λ̅_1
        (1 - 1/N)∑_n=0^D-1(λ̅_1(1-1/N) )^n/n!
        < λ̅_1 from (<ref>).
        Thus, there exists 
        ϵ > 0, which is independent of N,
        such that
        λ̅_ max = D- ϵ.
        For given D, there exists a N_* such that the following
        holds for N ≥ N_*:
        
            B_D,N - λ̅_ max    = D (1 - 1/N)^D-1 - D + ϵ   ≥ D ( 1 - D-1/N - 1 + ϵ/D)     = D (  ϵ/D - D-1/N) > 0,
        
        which completes the proof.
        
        ieeetr
