On Improving Throughput of Multichannel ALOHA using Preamble-based Exploration

I. INTRODUCTION

IN order to support the connectivity of a large number of devices and sensors for the Internet of things (IoT), machinetype communication (MTC) has been considered in cellular systems [1]-[3]. In fifth generation (5G) systems, it is expected to have more standards for MTC [4]-[6]. In general, in order to support a large number of devices (in this paper, we assume that devices and users are interchangeable) with sparse activity (i.e., only a fraction of them are active at a time), random access is widely considered as it can avoid high signaling overhead. In particular, most MTC schemes are based on (slotted) ALOHA[7],and ALOHA is extensively studied for MTC as in IN order to support the connectivity of a large number of devices and sensors for the Internet of things (IoT), machinetype communication (MTC) has been considered in cellular systems [8]-[11].

Since ALOHA plays a key role in MTC, various approaches are considered for ALOHA in order to improve the performance in terms of throughput (which may result in the increase of the number of devices to be supported). In [12], contention resolution repetition diversity (CRRD) is considered together with successive interference cancellation (SIC) for a better throughput. The notion of coding is applied to CRRD in [13],[14], which results in coded random access, where it is shown that the throughput (in the average number of successfully trans mitted packets per slot) can approach 1. In [15], a finite-length analysis (as opposed to asymptotic analysis) is carried out for coded random access. Coded random access is also considered for massive MTC with decoding that is based on statistical channel knowledge only in [16].

Furthermore, in [17],[18], the notion of non-orthogonal multiple access (NOMA) [19],[20] is applied to ALOHA so that multiple virtual access channels in the power domain are available without any bandwidth expansion, and it is shown that the throughput can be significantly improved at the cost of high power budget at users. Note that as in coded random access, SIC has to be used at a base station (BS) to remove interfering signals. In [21], the performance of NOMA-based random access is further analyzed.

In this paper, we consider a different approach than coded random access [14] and NOMA-based random access [17]. The proposed approach uses exploration for multichannel ALOHA to improve the performance, while it does not require SIC at a BS. Thus, whenever SIC is not affordable at a BS or a receiver, the proposed approach can be used to improve the throughput. As in multi-armed bandit problems [22],[23], exploration can help improve the performance of multichannel ALOHA. For exploration, in the proposed approach, each active user (i.e., a user with packet to transmit) is to send a preamble prior to packet transmission, and a BS sends the feedback information to active users to inform the numbers of transmitted preambles in multiple channels. We show that the feedback information, which is the outcome of exploration, can improve the throughput of multichannel ALOHA (as well as single-channel ALOHA). In particular, in terms of the maximum throughput, it is shown that the performance can be improved by a factor of[TeX:] $$2-e^{-1} \approx 1.632$$ thanks to exploration.

It is noteworthy that the exploration by sending preambles becomes possible if the BS is able to estimate the number of transmitted preambles in each channel. Thanks to the notion of compressive random access [24]-[28], the BS can estimate the number of transmitted preambles in each channel precisely. In addition, the proposed approach does not use SIC and CRRD, which makes it easy to implement. In general, while SIC is promising to improve the performance of random access as mentioned earlier, the implementation of SIC is known to be difficult. In particular, since SIC requires to reproduce the received signals of individual transmitted signals, a precise channel estimation is required with propagation delay estimation as well as frequency offset estimation (in uplink channels, each user has different frequency offset and propagation delay). Thus, a small BS or gateway has difficult to implement SIC due to limited hardware and computing resources. We believe that the proposed approach would be suitable for the case that low-cost small base stations or gateways are used for MTC.

We also consider fast retrial and analyze the steady-state performance to see the impact of exploration on delay performance with fast retrial. It is shown that the delay outage probability can be significantly reduced by exploration when the system is lightly loaded.

In summary, the main contributions¹ of the paper are as follows: [TeX:] $$i)$$ A multichannel ALOHA scheme is proposed with preamble-based exploration to improve the throughput;[TeX:] $$\text { ii) }$$performance analysis is carried out, which shows that the maximum throughput of the proposed is higher than that of conventional ALOHA by a factor of [TeX:] $$2-e^{-1} ; \text {iii })$$ using a steady-state analysis, it is shown that the exploration can significantly reduce the delay outage probability when fast retrial is employed for a lightly loaded system.

¹ A conference version of the paper is [29], where the main idea of the proposed approach is presented without steady-steady analysis.

The rest of the paper is organized as follows. In Section [TeX:] $$\text { II, }$$we present the motivation and system model for the proposed approach. To see the performance, we consider the maximum throughput analysis in Section III. A steady-state analysis is carried out with fast retrial in Section IV. We discuss some implementation issues in Section V and present simulation results in Section VI. The paper is concluded with remarks in Section VII. Notation: Matrices and vectors are denoted by upperand lower-case boldface letters, respectively. [TeX:] $$\mathbb{E}[\cdot]$$ denotes the statistical expectation. [TeX:] $$\mathcal{C} \mathcal{N}(\mathbf{a}, \mathbf{R})$$ represents the distribution of circularly symmetric complex Gaussian (CSCG) random vectors with mean vector a and covariance matrix R.

II. MOTIVATION AND SYSTEM MODEL

Throughout this paper, we only consider a slotted ALOHA system consisting of one BS and multiple users for uplink transmissions, where the BS periodically transmits a beacon signal for synchronization.

A. Motivation

Consider a single-channel ALOHA system. Let [TeX:] $$T_{\mathrm{d}}$$denote the length of data packet. Throughout the paper, it is assumed that the data packets of users have the same length. If an active user (with a data packet to transmit) knows that there are other active users, she may not transmit to avoid collision. In order to see whether or not there are other active users, suppose that each user has a unique preamble and an active user transmits its preamble sequence before data packet transmission, which can be seen as the exploration to learn the environment. Let[TeX:] $$T_{\mathrm{p}}$$denote the length of preamble. It is assumed that [TeX:] $$T_{\mathrm{p}}T_{\mathrm{d}}$$ in general. At the end of preamble transmission, we assume that the BS is able to detect all the transmitted preamble sequences and sends a feedback signal to inform the number of the transmitted preamble sequences. The length of feedback signal is denoted by [TeX:] $$T_{\mathrm{f}}$$.

An active user can make a decision whether or not she transmits her data packet based on the feedback from the BS. If there is only one preamble transmitted, the active user should send a data packet as there is no other active user. However, if the number of transmitted preambles is larger than 1, each active user may transmit a packet with a certain probability that might be less than 1. For example, in order to maximize the probability of successful transmission, the access probability might be[TeX:] $$1 / K$$, where K represents the number of active users or transmitted preambles that is fed back from the BS. Therefore, for a given [TeX:] $$K>1$$, the throughput, which is the average number of transmitted packets without collisions, becomes

As [TeX:] $$K \rightarrow \infty$$, we can see that [TeX:] $$\eta_{\mathrm{sa}}$$ approaches [TeX:] $$e^{-1}$$. On the other hand, if[TeX:] $$K=1, \eta_{\mathrm{sa}}=1$$. From [1], the average throughput can be shown to be higher than [TeX:] $$e^{-1}$$as follows:

On the other hand, suppose that the access probability, denoted by p, is decided without knowing K. In this case, if K is a Poisson random variable with mean[TeX:] $$\lambda$$, where [TeX:] $$\lambda$$is seen as the packet arrival rate, the throughput becomes

where the upper-bound can be achieved by p = 1/λ for λ ≥ 1. Therefore, there is a gain²(i.e., the difference between [2] and [3] ) obtained by the exploration that allows active users to know how many are in contention, i.e, the number of active users, K. In addition, as shown in[1]the gain increases if K is small, which is also illustrated in Fig. 1.

² The gain can be offset by the overhead due to exploration, i.e., the overhead due to preamble transmissions. However, if[TeX:] $$T_{\mathrm{p}} \ll T_{\mathrm{d}}$$, the offset might be negligible. We will discuss more details later.

B. The Proposed System based on Preamble-based Exploration

In this subsection, we propose a multichannel ALOHA system with exploration using preamble transmissions.

Suppose that there are M orthogonal radio resource blocks for multiple access channels. We assume that each active user can randomly choose one channel and transmit a preamble signal to the BS in the exploration phase (EP). After the EP, the BS can find the number of active users for each channel. Let [TeX:] $$k_{m}$$denote the number of active users transmitting their preambles through the mth channel. Then, the BS broadcasts the numbers of active users for all the channels, [TeX:] $$\left\{k_{1}, \cdots, k_{M}\right\}$$so that all the active users can see the state of contention. For example, an active user transmits a preamble through the 1st channel and sees that[TeX:] $$k_{1}=1$$. In this case, clearly, the user is only one active user using channel 1.

Let[TeX:] $$\mathcal{S}=\left\{m \mid k_{m}=1, m=1, \cdots, M\right\}, \text { i.e., } \mathcal{S}$$istheindexset of the channels with only one active user transmitting preamble. For convenience, let [TeX:] $$\mathcal{S}^{c}$$denote the complement of S. In the data transmission phase (DTP), if a user transmitting a preamble through channel m sees that[TeX:] $$k_{m}=1 \text { or } m \in \mathcal{S}$$, the user can send a data packet through the mth channel. For convenience, this user is referred to as a contention-free user. The group of contention-free active users is also referred to as Group I. On the other hand, when[TeX:] $$m \in \mathcal{S}^{c}$$(which implies that [TeX:] $$k_{m} \geq 2$$ 2 as the user transmits a preamble through channel m and[TeX:] $$m \notin \mathcal{S})$$,the user is referred to as a user in contention, and the group of active users in contention is referred to as Group II.

An example is shown in Fig.2 with [TeX:] $$K=3$$and[TeX:] $$M=4$$.Active user 2 chooses channel 3 to transmit a preamble and two other active users (users 1 and 3) choose channel 4. From this, the feedback information from the BS to the active users is [TeX:] $$\left\{k_{1}, k_{2}, k_{3}, k_{4}\right\}=\{0,0,1,2\}$$. As a result,[TeX:] $$k_{m}$$. As a result, [TeX:] $$\mathcal{S}=\{3\}$$ and [TeX:] $$\mathcal{S}^{c}=\{1,2,4\}$$, and active user 2 belongs to Group I and active users 1 and 3 belong to Group II.

If the user in contention transmits a packet through channel m, it will be collided with others. To avoid packet collision, the user can choose a different channel, say channel[TeX:] $$l \in \mathcal{S}^{c}$$, and transmits a packet. However, since another user in contention can choose channel [TeX:] $$l$$, there can be packet collision.

Although it is not possible to prevent collisions for users in contention, in order to mitigate packet collisions, we can assume that each user in contention can randomly choose a channel in[TeX:] $$Sc$$with an access probability, [TeX:] $$p_{\mathrm{dtp}}$$, in the DTP to transmit a packet, while a user in contention does not transmit a packet with probability[TeX:] $$1-p_{\mathrm{dtp}}$$

It is noteworthy that since the feedback after EP in the proposed approach is not used for access control, it is different from existing collision-resolution algorithms[30]. In the proposed multichannel ALOHA with EP, thanks to multiple channels, the feedback after EP is used to keep a selected channel (in Group I) or re-choose a channel (in Group II) by each active user. According to Fig. 2, a frame consists of EP, feedback, and DTP. After each frame, another feedback can be transmitted from the BS to inform success or collision of packet transmissions, which can be used for access control as in conventional random access schemes.

C. Estimation of Number of Transmitted Preambles

In multichannel ALOHA with EP, we have assumed that the BS can estimate [TeX:] $$\left\{k_{m}\right\}$$. In this subsection, we provide examples to demonstrate the estimation of [TeX:] $$\left\{k_{m}\right\}$$.

There can be two different cases when an active user transmits a preamble. In the first case, a common set or pool of preambles, denoted by[TeX:] $$\mathcal{C}=\left\{\mathbf{c}_{1}, \cdots, \mathbf{c}_{L}\right\}$$, can be used. Here,[TeX:] $$\mathbf{c}_{l}$$ represents the [TeX:] $$l$$h preamble sequence (of length[TeX:] $$T_{\mathrm{p}}$$) and[TeX:] $$L$$denotes the number of the preambles in[TeX:] $$\mathcal{C}$$. Any active user is to randomly choose one in[TeX:] $$\mathcal{C}$$. At the BS, the signal received through the [TeX:] $$m$$th channel can be expressed as follows:

where [TeX:] $$\mathbf{C}=\left[\begin{array}{lll} \mathbf{c}_{1} \cdots \mathbf{c}_{L} \end{array}\right]$$ and [TeX:] $$\mathbf{n}_{m} \sim \mathcal{C} \mathcal{N}\left(\mathbf{0}, N_{0} \mathbf{I}\right)$$ is the back-ground noise vector.Here, the [TeX:] $$l$$th element of [TeX:] $$\mathbf{s}_{m}$$, denoted by [TeX:] $$S_{m, l}$$, is given by [TeX:] $$s_{m, l}=\sum_{k \in \mathcal{K}_{m, l}} h_{k} \sqrt{P_{k}}$$, where [TeX:] $$h_{k}$$is the channel coefficient from active user[TeX:] $$k$$to the BS, [TeX:] $$P_{k}$$ is the transmit power of active user [TeX:] $$k$$, and [TeX:] $$\mathcal{K}_{m, l}$$is the index set of the active users choosing the lth preamble in the [TeX:] $$m$$th channel. Suppose that active users can decide their transmit powers to reach a target signal-to-noise ratio (SNR), i.e.,[TeX:] $$\left|h_{k}\right|^{2} P_{k} / N_{0} \geq \Gamma$$, where[TeX:] $$\Gamma$$ is the target SNR. It is expected that s [TeX:] $$m$$ is a[TeX:] $$k_{m}$$-sparse vector (recall that[TeX:] $$k_{m}$$is the number of the active users in the[TeX:] $$m$$th channel). Then, when[TeX:] $$L>T_{\mathrm{p}}$$, using compressive sensing algorithms [31], the BS is able to estimate[TeX:] $$\mathbf{s}_{m}$$ under certain conditions (of [TeX:] $$\mathrm{C}$$ and the maximum sparsity of[TeX:] $$\mathbf{S}_{m}$$) [32],[33], which has been discussed in the context of compressive random access[34]-[37]. Once [TeX:] $$\mathbf{s}_{m}$$ is estimated, the determination of the number of active users or the estimation of[TeX:] $$k_{m}$$ becomes straightforward (because [TeX:] $$k_{m}$$can be found from the sparsity of[TeX:] $$\mathbf{s}_{m}$$), while preamble collision³[34],[35]can result in errors in estimating[TeX:] $$k_{m}$$. From [36], for the[TeX:] $$m$$th channel, the conditional probability of no preamble collision can be found as

³ It can happen as a preamble can be chosen by multiple active users.

where the approximation is actually a lower-bound (thus,[TeX:] $$1-e^{-k_{m}\left(k_{m}-1\right) /(2 L)}$$ is an upper-bound on the conditional probability of preamble collision). If[TeX:] $$K$$ active users are uniformly distributed over[TeX:] $$M$$channels and [TeX:] $$K$$ is assumed to follow a Poisson distribution with mean[TeX:] $$\lambda$$, it can be shown that

where[TeX:] $$\lambda / M1$$. Thus,[TeX:] \lambda^{2} /\left(2 L M^{2}\right)$$ becomes the probability of preamble collision. It can be shown that

where[TeX:] $$\delta \ll 1$$is a threshold probability of preamble collision. To keep [TeX:] $$\delta,$$we need

In the second case, it is assumed that all users have unique preamble sequences. In this case, there is no preamble collision. However, there are a large number of columns of the matrix of preambles (which is the same as the number of all users), which makes the sparse signal estimation (and the determination of the number of active users) difficult. To avoid it, as suggested in [37], sparse preamble sequences can be used.

In summary, by exploiting the notion of compressive sensing, it is possible to determine[TeX:] $$k_{m}$$ at the BS. Note that, in the first case, it is not necessary that the preamble sequences are orthogonal. For example, we can use Zadoff-Chu or Alltop sequences [38]for preambles with reasonably low crosscorrelation. In this case, the number of preambles becomes[TeX:] $$L=T_{\mathrm{p}}^{2}$$(for Alltop sequences) when [TeX:] $$T_{\mathrm{p}} \geq 5$$ is a prime. That is, a large number of preambles to keep the probability of preamble collision low can be obtained with a reasonable length of preamble,[TeX:] $$T_{\mathrm{p}}$$

III. MAXIMUM THROUGHPUT COMPARISON

In this section, we focus on the maximum throughput for two schemes, namely conventional multichannel ALOHA and multichannel ALOHA with EP. As mentioned earlier, it is assumed that the length of data packet,[TeX:] $$T_{\mathrm{d}}$$ is the same for all active users. We show that the ratio of the maximum throughput of multichannel ALOHA with EP to that of conventional multichannel ALOHA becomes[TeX:] $$2-e^{-1} \approx 1.632$$, which can be seen as the gain of exploration.

A. Throughput of Conventional Multichannel ALOHA

In conventional multichannel ALOHA, we can find the average number of packets without collisions as follows:

For a large[TeX:] $$K$$, it can be shown that

where[TeX:] $$\bar{N}_{\mathrm{ma}}(M)$$is the maximum throughput of multichannel ALOHA, which can be achieved if [TeX:] $$K=M$$. In addition, as in [39], the arrival rate has to be lower than[TeX:] $$M e^{-1}$for system stability.

B. Throughput of Multichannel ALOHA with EP

One of the main results of the paper can be stated as follows.

Theorem 1: The ratio of the maximum throughput of multichannel ALOHA with EP to that of conventional multichannel ALOHA is

In the rest of this subsection, we prove Theorem 1.

Prior to the proof, we can briefly compare the normalized maximum throughput (per channel) with those of well-known schemes as follows:

where[TeX:] $$N_{\mathrm{co}}$$represents the throughput of coded random access. As in [14], the normalized throughput of coded random access can approach 1 under ideal conditions (i.e., all the transmitted packets can be recovered regardless of collisions). Furthermore, for NOMA-based random access, the maximum normalized throughput can be higher than 1 thanks to virtual multiple channels in the power-domain. However, both coded and NOMA-based random access schemes need to have SIC at the BS. On the other hand, the proposed scheme (i.e., multichannel ALOHA with EP) does not require SIC like conventional multichannel ALOHA.

Let[TeX:] $$S=|\mathcal{S}|$$, where S represents the number of active users that can transmit packets without collisions. Clearly, [TeX:] $$S \leq$$[TeX:] $$\min \{K, M\}$$ In addition, let[TeX:] $$W=K-S$$, where W becomes the number of active users in contention. For convenience, let

Clearly, L is the number of the channels that are available for contention-based transmissions for W active users in contention or Group II. In addition, suppose that among W , U active users in contention are to transmit their packets through L channels. Clearly, for given W , U has the following distribution:

Throughout the paper, we assume that

which maximizes⁴he average number of packets without collisions in Group[TeX:] $$\text { II. }$$

⁴For Group II, we can consider a multichannel ALOHA system with L channels and W users. In this case, pdtp is seen as the access probability that can maximize the throughput if it is given in (14)[39],[10]

For a given U, the conditional average number of the packets that can be successfully transmitted from U users without collisions in contention during DTP becomes U [TeX:] $$(1-1 / L)^{U-1}$$As a result, the conditional average number of packets without collisions (for given U, L, and S) is given by

where the first term on the right-hand side (RHS) in (15) is the number of packets without collisions from Group I and the second term is that from Group II. For convenience, let

which is the average number of packets without collisions (for given K and M ) in multichannel ALOHA with EP.

Lemma 1: Suppose that M and K are sufficiently large so thatLandW arealsolarge. Theupperboundon[TeX:] $$N_{\mathrm{ep}}(K, M)$$is given by

Since U depends on W and W depends on K, we have

From (13), after some manipulations, it can be shown that

If[TeX:] $$p_{\mathrm{dtp}} / L \ll 1$$, it follows that[TeX:] $$p_{\mathrm{dtp}} W\left(1-p_{\mathrm{dtp}} / L\right)^{W-1} \approx$$[TeX:] $$p_{\mathrm{dtp}} W e^{-\frac{p_{\mathrm{dt} p} w}{L}} \leq L e^{-1}$$The upper bound can be achieved if

As a result, since[TeX:] $$L=M-S$$, it can be shown that

Substituting (19) and (22) into (18), we have

which completes the proof.

From (17), the maximum throughput of multichannel ALOHA with EP is given by

For a sufficiently large[TeX:] $$K, \bar{S}(K) \approx K e^{-K / M}$$. Thus, if we consider the throughput gain using the ratio of the maximum throughput of multichannel ALOHA with EP to that of conventional ALOHA, it can be shown that

which finally proves Theorem 1. From this, it is clear that the EP can improve the performance of multichannel ALOHA (in terms of the throughput) by a factor of 1.632.

IV. STEADY-STATE ANALYSIS WITH FAST RETRIAL

In this section, a steady-state analysis is carried out when fast retrial in [40]is used. The throughput and probability of collision are found when the total arrival rate is modeled as a Poisson randomvariable.

A. Steady-State Analysis of Conventional Multichannel ALOHA

Suppose that the number of new arrivals follows a Poisson distribution with mean[TeX:] $$\lambda_{0}$$. As in[40], we assume that the total of the new and back-logged arrivals, which is K, follows a Poisson distribution with mean[TeX:] $$\lambda$$that is given by

where[TeX:] $$q_{\mathrm{ma}}$$ istheprobabilityofcollisionofconventionalmulti- channel ALOHA

For a given[TeX:] $$\lambda$$, under the assumption that K is a Poisson ran- dom variable with mean[TeX:] $$\lambda$$,the average number of packets without collisions becomes

where[TeX:] $$p_{\lambda}(k)=e^{-\lambda} \lambda^{k} / k !$$is the probability mass function of a Poisson random variable with mean[TeX:] $$\lambda$$As in [40],[TeX:] $$q_{\mathrm{ma}}$$can be given by the following ratio:

Then, from (26) and (28), we can see that [TeX:] $$\lambda$$ is the solution of the ollowing equation:

Furthermore, it can be shown that[TeX:] $$N_{\mathrm{ma}}(M)=\lambda_{0}$$, which means that in the steady state, the input arrival rate, i.e.,[TeX:] $$\lambda_{0}$$, is identical to the output rate that is the average number of packets without collisions.

B. Steady-State Analysis of Multichannel ALOHA with EP

For given K and M , the number of packets without collisions can be re-written as

where[TeX:] $$Z_{w} \in\{0,1\}$$ is 1 if the[TeX:] $$w$$th active user in Group[TeX:] $$\text { II }$$transmits a packet, and otherwise it becomes 0. For steady-state analysis, as in Subsection[TeX:] $$\text { IV.A, }$$, we need to find[TeX:] $$\mathbb{E}\left[N_{\mathrm{ep}}(K, M)\right]$$, where the expectation is carried out over K. Unfortunately, it is not easy to find a closed-form expression for[TeX:] $$\mathbb{E}\left[N_{\mathrm{ep}}(K, M)\right]$$.Thus, we resort to a bound as follows.

Theorem 2: Suppose that K follows a Poisson distribution with mean[TeX:] $$\lambda$$Then, a lower-bound on the average number of packets without collisions is given by

where[TeX:] $$F_{\lambda}(M)=\sum_{m=0}^{M} p_{\lambda}(m)$$is the cumulative distribution function of a Poisson random variable with mean[TeX:] $$\lambda$$.

Proof: In(30),it can be shown that

Suppose that[TeX:] $$KM$$.In this case, we have L/W=(M− S)/(K − S)[TeX:] $$\geq 1, p_{\mathrm{dtp}}$$ has to be 1 according to (14). Thus, it can be shown that

Substituting (33) into (30), we have

We now consider the case that [TeX:] $$K>M$$. It can be shown that

From (34) and (35), we have

Since K is a Poisson random variable with mean[TeX:] $$\lambda$$using (19),it can be shown that

After some manipulations, we have

Substituting (38) into (37), we can obtain the RHS term in (31), which completes the proof.

Suppose that[TeX:] $$\lambda$$is sufficiently smaller than M so that[TeX:] $$\mid 1-$$[TeX:] $$F_{\lambda}(M)|,| 1-F_{\lambda}(M-1) \mid \leq \epsilon, \text { where } 0\epsilon \ll 1$$.Then,from (31), we can show that

Since[TeX:] $$\lambda \geq \lambda e^{-\lambda / M}$$, it can be shown that[TeX:] $$\left(1-e^{-1}\right) \lambda e^{-\lambda / M}+$[TeX:] $$e^{-1} \lambda \geq \lambda e^{-\lambda / M}$$. Thus, ignoring the term of [TeX:] $$O(\epsilon)$$, it can be shownthat

which shows that the average number of packets without collisions of multichannel ALOHA with EP is larger than that of conventional multichannel ALOHA and the performance gap increases as λ increases. Furthermore, since (40) is re-written as

where[TeX:] $$\alpha=\lambda / M$, with a fixed [TeX:] $$\alpha$$, we can see that the gap grows linearly with M.

In general, we expect that[TeX:] $$\lambda M$$ to avoid a large number of back-logged packets. In this case, an approximation of[TeX:] $$N_{\mathrm{ep}}(M)$$can be found as follows.

Lemma 2: Suppose that M is sufficiently large. If[TeX:] $$\lambda M$[TeX:] $$N_{\mathrm{ep}}(M)$$ can be approximated by

Proof: Since[TeX:] $$\lambda M, N_{\mathrm{ep}}(K, M)$$ can be approximated by (34) (i.e., for the case of[TeX:] $$K \leq M)$$. In addition, in (34), wecan show that

Thus, an approximation of[TeX:] $$N_{\mathrm{ep}}(M)$$is given by

After some manipulations, we can show that

Substituting (45) into (44), we can obtain (42), which completes the proof.

Theorem 3: Suppose that[TeX:] $$\lambda$$ and M increase with a fixed ratio[TeX:] $$\alpha1$$. Then, the asymptotic normalized throughput can be given by

The function[TeX:] $$\psi(\alpha)$$ is a concave function of[TeX:] $$\alpha \in(0,1)$$and has a unique maximum.

Proof: Since lim[TeX:] $$M \rightarrow \infty A_{1} / M^{2}=\alpha^{2}$$, lim[TeX:] $$M \rightarrow \infty A_{2} / M^{2}=$$[TeX:] $$\alpha^{2} e^{-\alpha}$$and lim[TeX:] $$M \rightarrow \infty / A_{3} M^{2}=\alpha^{2} e^{-2 \alpha}$$, it can be easily shown that

which becomes[TeX:] $$\psi(\alpha)$$ in (46).

The 2nd derivative of [TeX:] $$\psi(\alpha)$$ is given by

which shows that[TeX:] $$\psi(\alpha)$$ is a concave function of[TeX:] $$\alpha \in(0,1)$$. This completes the proof.

The maximum of[TeX:] $$\psi(\alpha)$$lies between 0 and 1 as[TeX:] $$\psi^{\prime}(0)=1>0$$and[TeX:] $$\psi^{\prime}(1)=2 e^{-1}-10$whichisgivenby

Note that the normalized maximum throughput of the conventional multichannel ALOHA is

Clearly, when fast retrial is employed, multichannel ALOHA with EP can have a higher throughput than the conventional multichannel ALOHA and the performance gain (in terms of the throughput ratio) is max[TeX:] $$0 \leq \alpha \leq 1 \psi(\alpha) / e^{-1}=0.6149 / 0.3679 \approx$$1.6715, which is similar to the ratio of the maximum throughput of multichannel ALOHA with EP to that of conventional ALOHA in (25).

On the other hand, if the system is lightly loaded, i.e.,[TeX:] $$\lambda_{0} \ll M$$, the throughput difference between the two systems is not significant. To see this, let[TeX:] $$\alpha_{0}=\lambda_{0} / M$$, which is the normalized throughput or throughput per channel. Then, from (29), in conventional multichannel ALOHA, we have

Using[TeX:] $$\tilde{N}_{\mathrm{ep}}(M)$$ as an approximation of[TeX:] $$N_{\mathrm{ep}}(M)$$, for given[TeX:] $$\lambda_{0}$$, from (26) and (46) (for a large M ), it can be shown that

However, the exploration gain can lead to an improvement of access delay performance. To see this, let[TeX:] $$q_{\mathrm{ep}}$$ be the probability of collision of multichannel ALOHA with EP. From[TeX:] $$q_{\mathrm{ep}}$$, the outage probability of access delay with D re-transmissions can be given by

while the average access delay is [TeX:] $$1 /\left(1-q_{\mathrm{ep}}\right)$$. As in (26), it can be shown that

Then, for a large M, using[TeX:] $$\tilde{N}_{\mathrm{ep}}(M) \approx N_{\mathrm{ep}}(M)$$, it can be shown that

while

Then, when[TeX:] $$\alpha \approx \alpha_{0}$$is sufficiently small, it can be shown that[TeX:] $$q_{\mathrm{ep}} \approx \alpha(1-(1-\alpha))^{2} \approx \alpha_{0}^{3}$$and[TeX:] $$q_{\mathrm{ma}} \approx 1-(1-\alpha) \approx \alpha_{0}$$It demonstrates that the delay outage probability of multichannel ALOHA can be significantly lowered by exploration when the system is lightly loaded. For example, if[TeX:] $$\alpha_{0}=0.1$and the access delay threshold is[TeX:] $$D=2$$, according to (52), the delay outage probability of multichannel ALOHA with EP becomes[TeX:] $$0.1^{6}=10^{-6}$$, while that of conventional multichannel ALOHA is[TeX:] $$0.1^{2}=10^{-2}$$.

In Fig. 3(a), we show the relationship between[TeX:] $$\alpha_{0}=\lambda_{0} / M$$and [TeX:] $$\alpha$$for multichannel ALOHA with EP (from (51)) and that of conventional multichannel ALOHA. For a given normalized new arrival rate[TeX:] $$\text { (i.e., } \alpha=\lambda / M)$$, multichannel ALOHA with EP has a lower normalized total arrival rate[TeX:] $$(\mathrm{i.e.}, \alpha)$$ than conventional multichannel ALOHA, which means that the probability of collision in multichannel ALOHA with EP is lower than that in conventional multichannel ALOHA, which is illustrated in Fig. 3(b). When[TeX:] $$\alpha0.1$$(i.e., a lightly loaded case), we see that[TeX:] $$\alpha \approx \alpha_{0}$$in Fig. 3(a) as expected, while[TeX:] $$q_{\mathrm{ep}}$$is significantly lower than[TeX:] $$q_{\mathrm{ma}}$$in Fig. 3(b) (which implies a significant decrease of the delay outage probability). Note that the expression in (51) from (46) is valid when[TeX:] $$\alpha1$$. Thus, as[TeX:] $$\alpha$$approaches > 1, it cannot be used (which will also be discussed in Section VI).

VII. CONCLUDING REMARKS

In this paper, an exploration approach has been proposed for multichannel ALOHA by sending preambles prior to packet transmissions to allow active users to learn the state of contention. We found that the exploration gain is[TeX:] $$2-e^{-1}$$in terms of the ratio of the maximum throughput of multichannel ALOHA with EP to that of conventional multichannel ALOHA. As a result, with the same bandwidth, compared with conventional multichannel ALOHA, we could see that the proposed multichannel ALOHA with EP can support more sensors and devices in MTC. We also showed that the exploration can significantly decrease the delay outage probability when the system with fast retrial is lightly loaded.