Explore-Before-Talk: Multichannel Selection Diversity for Uplink Transmissions in Machine-Type Communication

I. INTRODUCTION

THE Internet of things (IoT) has sparked the upsurge in uplink machine-type communication (MTC) traffic [1], [2]. The conventional wireless systems postulate their sporadic traffic with small payload size (e.g., thermometers, barometers) [3]. However, emerging IoT applications are envisaged to require higher MTC transmission rates. For instance, e-health wearables generate time-series data. Real-time surveillance cameras report video frames. Furthermore, edge learning devices exchange ondevice machine learning models, some of which comprise millions of model parameters [4].

In MTC, random access approaches are considered to support a number of MTC devices. In particular, 4-step random access procedure is considered in [5]. In the first step, devices or MTC user equipment (UE) is to randomly choose a preamble within a pool of preambles (that is to be shared with all UEs). After the response from a base station (BS) in the second step, the UEs can transmit their data packets through allocated channels to the BS in the third step. In this paper we propose a resource allocation approach for uplink transmissions in the third step, termed explore-before-talk (EBT). As illustrated in Fig. 1(b), at the first phase of EBT, every MTC UE sends pilot signals through [TeX:] $$W(\geq 1)$$ channels that are initially allocated by the BS for exploration, and then the BS informs a subset of initially allocated channels that are associated with high signal-to-noise ratios [TeX:] $$(\mathrm{SNRs}), \text { say } \bar{W}$$ channels of highest SNRs, where [TeX:] $$\bar{W} \leq W,$$ for data packet transmission by the UE while releasing the rest of the channels for other UEs. Then, at the second data packet transmission phase, each UE uploads data only using [TeX:] $$\bar{W}$$ highest SNR channels.

Compared to a conventional approach whose [TeX:] $$W=\bar{W}$$ (i.e., no exploration) as depicted in Fig. 1(a), EBT exploits a multichannel selection diversity gain during the data transmission phase, at the cost of the channel exploration during the pilot transmission phase. To illustrate this, consider an example with three unit-bandwidth channels, in which one good channel provides the unity spectral efficiency, while the other two poor channels have ignorable spectral efficiencies. In the conventional approach with [TeX:] $$\bar{W}=W=1,$$ a single channel is uniformly randomly selected, and therefore the mean data rate is 1=3. By contrast, in EBT with W = 3 and [TeX:] $$\bar{W}=1,$$ the mean data rate achieves 1 by selecting the best channel after exportation. With less exploration, W = 2, the mean data rate decreases to 2=3, showing the trade-off between the exploring bandwidth and the data rate at exploitation.

Focusing on this exploration-exploitation trade-off, we aim to answer the question whether EBT achieves higher data rate, by fairly comparing the conventional method and EBT under a common traffic model and a resource outage requirement.

RelatedWorks. To improve the uplink performance of MTC, random access techniques have been studied, such as device grouping methods [6], coded random access [7], non-orthogonal multiple access (NOMA) [8], and sparse code multiple access (SCMA) [9]. While the variety of works have addressed reducing random access collision, improving MTC data rates has recently attracted much attention from both academia and industry, towards supporting emerging applications categorized as broadband IoT [10]. Next, in terms of the exploring operations before exploitation, this work has been partly inspired by listen-before-talk (LBT) in dynamic spectrum access (DSA), in which secondary users sense the channel before transmission,

in order to avoid the channels occupied by primary users [11]. A resource allocation method for MTC is discussed in [12] to improve the energy efficiency by taking into account the SNR or channel quality indicator (CQI). In our proposed EBT, MTC users explore the channels providing the highest SNRs for data transmission, which is similar to that in [12]. However, we consider multiple channels per MTC user to exploit selection diversity as illustrated in Fig. 1 (while in [12], one channel per MTC user is considered). Lastly, ordered selection rules have been applied in various applications. In [13] channel inversion power control is performed in the order of SNR to improve energy efficiency in uplink NOMA. In [14], interfering signals are canceled in order of their eigenvalues, thereby efficiently utilizing the multi-antenna degrees of freedom. In EBT, data transmission channels are selected in order of SNR for maximizing the data rates under limited bandwidth.

It is noteworthy that the proposed approach is suitable for MTC UEs with a number of data packets for uplink transmissions, e.g., data packets to exchange machine-learning models [4]. On the other hand, there would be a large number of MTC UEs that have short messages. For them, 2-step random access approaches are preferable [15]–[18].

Contributions and Organization. The contributions of this paper can be summarized as follows.

We propose a resource allocation approach based on multichannel selection diversity in MTC, i.e., EBT, and derive its data rate in closed-form for given [TeX:] $$W \text { and } \bar{W}$$ (see Proposition 1) to see the performance gain by selection diversity.

We provide the optimality condition of [TeX:] $$\bar{W}$$ guaranteeing a target outage probability in an overall system is provided (see Proposition 2), thereby proposing an algorithm that finds the optimal [TeX:] $$\bar{W}$$ for a given w (see Algorithm 1).

Numerical evaluations corroborate that EBT achieves higher mean transmission rate with less bandwidth while abiding by the same outage constraint compared to the conventional method.

The rest of the paper is organized as follows. In Section II, the system model for EBT is presented. In Section III, the mean

data rate is studied. In Section IV, the exploration and exploitation [TeX:] $$\text { (i.e., } W \text { and } \bar{W})$$ are optimized for a given outage requirement, which is validated by numerical evaluations in Section IV, followed by our conclusion in Section V.

II. SYSTEM MODEL

In this section, we present the system model to study resource allocation for uplink in MTC with multiple UEs and a BS.

Suppose that uplink transmissions are carried out based on 4- step random access procedure [3], [19], which is illustrated in Fig. 2. The first step is random access to establish connection to the BS with a pool of preambles consisting of L sequences. In the first step, an active UE transmits a randomly selected a preamble through physical random access channel (PRACH). In the second step, the BS detects the transmitted preambles and sends responses. Once an active UE is connected to the BS, it can transmit data packets in the third step through dedicated resource blocks (RBs) or channels¹, which are physical uplink shared channel (PUSCH).

¹ We will use the terms resource block and channel interchangeably.

In this paper, we focus on the third step with preamble detection carried out in the first step as in [20]. Thus, it is assumed that the UEs without preamble collision can move to the third step, while the UEs with preamble collision would be backlogged. Note that in this case, the fourth step can be absorbed into the second step. As shown in Fig. 3, at slot t, there are K(t) active UEs that transmit preambles. Among the K(t) UEs in the first step, Z(t) UEs are admitted for uplink transmissions in the third step. Here, [TeX:] $$Z(t) \leq K(t)$$ due to preamble collisions. Thus, every time slot t, it is necessary to allocate RBs to Z(t) newly admitted UEs (without preamble collision) for uplink transmissions (in the third step). It is assumed that each newly admitted UEs needs s + 1 slots for uplink transmissions. As will be explained later, the first slot is used to transmit a pilot signal to allow the BS to estimate the UE’s channel in PUSCH. In addition, s can vary from one UE to another as will be considered in

Section IV.

Suppose that there are N radio RBs for the UEs in the third step, i.e., uplink transmissions. Let [TeX:] $$h_{n, k}$$ denote the channel coefficient of the nth channel from UE k to the BS. Note that the newly admitted UEs in the third step transmit their signals through PUSCH, which is different from PRACH. Thus, the channel state information (CSI) estimation in the first step with preamble transmission does not provide the estimates of the [TeX:] $$h_{n, k} \text { 's }$$ (which are the channel coefficients the RBs of PUSCH). This means that a newly admitted UE in the third step needs to transmit pilot signals together with data packets over s slots as illustrated in Fig. 1 to allow the BS to estimate [TeX:] $$h_{n, k}.$$ Thus, for each UE in the third step, a total of 1 + s slots are required. For convenience, let [TeX:] $$\gamma_{n, k}=\left|h_{n, k}\right|^{2} / \sigma^{2}$$ be the signal-to-noise ratio (SNR) of the nth channel from UE k to the BS, where [TeX:] $$\sigma^{2}$$ is the noise variance.

With known CSI of all the UEs in the third step, the BS can perform optimal channel allocation with N RBs. For example, suppose that N = 1000 and each UE needs to have 10 RBs for uplink transmissions. Then, there can be up to 100 UEs that are connected simultaneously. In this case, in order to allocate 10 RBs for each UE, the CSI estimation of all N = 1000 channels per UE is required, which may require excessive pilot signaling. In addition, since the optimal channel allocation has to be updated when a set of new UEs join in every slot, it requires not only a high computational complexity, but also existing UEs to change their channels for uploading in every slot.

To avoid the difficulties stated above, a random subset of available channels can be simply allocated to a new admitted UE for uplink transmissions in the third step, which is regarded as a conventional approach.

III. MULTICHANNEL SELECTION DIVERSITY GAIN IN MEAN DATA RATE

In this section, we mainly focus on the performance gain of each UE in the third step by EBT, which can exploit multichannel selection diversity, in terms of the mean rate for given W, [TeX:] $$\bar{W},$$ and s as in Fig. 1. To understand the overall performance, it is also necessary to find the number of UEs in the third step for given N, which will be studied in Section IV.

Suppose that the BS randomly chooses W channels and allocates them to a new UE, say UE k. For convenience, let [TeX:] $$\mathcal{W}=\{1, \cdots, W\}$$ be the index set of the allocated W channels. Note that since W is a set of randomly selected channels from [TeX:] $$\mathcal{N}=\{1, \cdots, N\}$$ as mentioned earlier, W can be any subset of N. Then, UE k transmits pilot signals through the W channels so that the BS can estimate their SNRs. The [TeX:] $$\bar{W}$$ best channels among W in terms of SNR are selected and their indices are fed back to UE k so that the UE can transmit their data packets through the selected [TeX:] $$\bar{W}$$ channels as shown in Fig. 1, where s represents the number of slots UE k sends packets. In doing so, EBT can exploit the multichannel selection diversity gain to increase the transmission rate, where [TeX:] $$W \text { and } \bar{W}$$ are referred to as the number of the channels for exploration (to select the best [TeX:] $$\bar{W}$$ channels) and exploitation (to transmit data packets), respectively.

In MTC, since UEs may have short messages to transmit and their mobility is limited, throughout the paper, it is assumed that i) each UE transmits packets over a finite number of slots, i.e., s is finite; ii) the channel coefficients remain unchanged for s slots.

For convenience, we omit the index of UE k in the rest of this section. Let

where [TeX:] $$\gamma(w)$$ represents the wth lowest element. Then, for given [TeX:] $$\left\{\gamma_{w}\right\}, \text { the } \gamma_{(w)} \text { 's }$$ are order statistics [21]. Since the UE will keep [TeX:] $$\bar{W}$$ highest SNRs, the mean transmission rate (in bits per second per Hz) per slot becomes the channels of the

In (2), we assume that the transmission rate of each selected channel is set to its achievable rate (i.e., the channel capacity [22]).

For comparisons, consider a conventional approach where [TeX:] $$W_{\mathrm{c}}$$ channels are randomly allocated to a UE regardless of their SNRs. This can be seen as a special case of EBT with [TeX:] $$W=\bar{W}=W_{\mathrm{c}}.$$ Due to the random selection of [TeX:] $$W_{\mathrm{c}}$$ channels, it can be assumed that [TeX:] $$\gamma_{w}, w \in \mathcal{W}_{\mathrm{c}}=\left\{1, \cdots, W_{\mathrm{c}}\right\},$$ is independent. Furthermore, for tractable analysis, we assume that [TeX:] $$\gamma_{w}$$ is independent and identically distributed (iid). In this case, the mean transmission rate of the conventional approach becomes

For example, suppose that the UE has the SNR of channel [TeX:] $$w \in \mathcal{W}$$ that is distributed as follows:

where [TeX:] $$\bar{\gamma}$$ is the mean SNR. That is, each channel is modeled as an independent and identical Rayleigh² fading channel and [TeX:] $$\gamma_{w} , w \in \mathcal{W}$$ is seen as a realization from the distribution in (4). Then, from [23], we have

² Other fading channels can be considered for [TeX:] $$\gamma_{w},$$ while we consider Rayleigh fading in this section as an example to demonstrate the gain from selection diversity in the third step. It is also assumed that power control is used to compensate large-scale fading. As a result, allW channels have the same mean SNR.

where [TeX:] $$E_{n}(x)=\int_{1}^{\infty} e^{-x t} / t^{n} \mid d t$$ is the exponential integral function of order n.

In a similar way, we derive the mean transmission rate of EBT in closed-form in the following lemma.

Lemma 1: For independent Rayleigh fading in (4), the mean transmission rate (per slot) of EBT is given as:

where [TeX:] $$a_{m, w}=W-w+1+m.$$

Proof: From (2), it can be shown that

where

which is the probability density function (pdf) of the wth order statistic [21]. Applying the binomial expansion to (8), we obtain

Plugging this into (7) completes the proof.

Next, for a large W, we can further simplify the mean transmission rate of EBT as follows.

Proposition 1: For independent Rayleigh fading in (4) with [TeX:] $$W \gg W \gg 1,$$ the mean transmission rate of EBT is:

Proof: For [TeX:] $$W \gg \bar{W} \gg 1,$$ the wth highest SNR [TeX:] $$\gamma_{w}$$ with [TeX:] $$w \leq \bar{W}$$ is large with a high probability. In this regime, the expectation of the logarithmic function increasing with diminishing returns in (2) is approximated as

Next, we focus on [TeX:] $$\mathbb{E}\left[\gamma_{w}\right]$$ in (11). Let [TeX:] $$F(\gamma)$$ denote the probability that [TeX:] $$\gamma_{w} \leq \gamma.$$ This cumulative distribution function (cdf) of the SNR is given by integrating its pdf in (8). For independent Rayleigh fading channels, following [21], the cdf is bounded as

Therefore, for [TeX:] $$W \gg 1$$ we obtain

Since [TeX:] $$F(\gamma)$$ is monotonically increasing, we can take the inverse function, yielding

The last equality follows from the quantile function [TeX:] $$F^{-1}(p)$$ of the SNR distribution in (4) with [TeX:] $$p=w / W \in[0,1].$$ Applying (14) with (11) to (2) and inverting the order of the summation finalize the proof.

In (10), considering the summation of the smallest values, i.e., [TeX:] $$i=\bar{W},$$ yields the following corollary.

Corollary 1: For independent Rayleigh fading in (4) with [TeX:] $$W \gg \bar{W} \gg 1,$$ the mean transmission rate of EBT is lower bounded as:

In (15), we can clearly see the gain from the multichannel selection diversity as the approximate rate increases withW when [TeX:] $$\bar{W}$$ is fixed. In particular, we can see that the SNR term in the logarithm is effectively increased by a factor of ln [TeX:] $$(W / \bar{W}).$$

For a fair comparison between the conventional and proposed approaches, the number of channels of the conventional approach is decided as

so that the total number of channels is the same as that of EBT, which is [TeX:] $$W+s \bar{W}.$$ In Fig. 4, under the assumption of independent Rayleigh fading in (4), the mean transmission rates (per slot) as functions of [TeX:] $$W \text { when } \bar{W}=5, s=10, \text { and } \bar{\gamma}=10$$ dB are shown for the conventional and proposed approaches. Note that in the conventional approach, [TeX:] $$W_{\mathrm{c}}$$ is decided as in (16) for given [TeX:] $$\bar{W} \text { and } W.$$ The approximate mean transmission rate of EBT is given by (15) (shown by the solid line with cross markers). Clearly, for a fixed [TeX:] $$\bar{W},$$ a higher selection diversity gain can be achieved as W increases in EBT, i.e., the number of channels for exploration increases, there is a higher chance to choose the better [TeX:] $$\bar{W}$$ channels for exploitation, which results in a higher mean transmission rate than that of the conventional one as shown in Fig. 4. Note that the mean transmission rate of the conventional approach also increases with [TeX:] $$W \text { as } W_{\mathrm{c}}$$ increases with W.

In Fig. 5, the mean transmission rates as functions of [TeX:] $$\bar{W}$$ when [TeX:] $$W=20, s=10, \text { and } \bar{\gamma}=10 \mathrm{~dB}$$ are shown for the conventional and proposed approaches. It is interesting to see that the conventional approach has a better performance when the number of channels for exploitation is small, e.g., [TeX:] $$\bar{W} \leq 2.$$ In particular, when [TeX:] $$\bar{W}=1$$ in EBT, [TeX:] $$W_{\mathrm{c}}$$ in the conventional approach becomes 2.727. Thus, although the multichannel selection diversity gain can help improve the transmission rate of EBT, a large number of channels for exploitation is still necessary for a higher transmission rate. It is also noteworthy that when [TeX:] $$W=\bar{W}=W_{\mathrm{c}}=20,$$ EBT becomes the conventional approach, which results in the same mean transmission rate.

IV. EXPLORATION-EXPLOITATION OPTIMIZATION UNDER AN OUTAGE CONSTRAINT

As shown in Figs. 4 and 5, if the numbers of the channels for exploration and exploitation [TeX:] $$\text { (i.e., } W \text { and } \bar{W}, \text { respectively) }$$ are well chosen, EBT can provide a higher transmission rate than the conventional approach subject to (16). However, from a multiuser system point of view, for a fair comparison, we also need to consider the number of UEs in the third step for a given number of RBs, N. To this end, in this section, we consider the overall uplink system that includes the first and third³ steps, which is illustrated in Fig. 3.

³In 4-step random access procedure, the second and fourth steps are for downlink, which will be ignored for the uplink performance analysis.

The numbers of UEs in the first and third steps are random variables. As a result, although a new UE without preamble collision can move to the third step, it may not have a sufficient number of channels for uplink transmissions. This event is referred to as the outage event. The system has to be designed to keep the outage probability low or the outage probability less than [TeX:] $$e^{-d}, d>0,$$ is a design parameter. Thus, in this section, we first obtain an upper-bound on the outage probability and then consider an optimization problem formulation for a fair comparison between EBT and the conventional approach in terms of the mean transmission rate and outage probability.

A. Outage Probability

This subsection focuses on the outage event at a certain time, when the total N channels are exceeded by the allocated channels Q to newly admitted UEs as well as the remaining UEs who are previously admitted. For mathematical amenability, we consider the following assumptions in the outage probability analysis.

A1) Recall that K(t) is the number of new UEs that send preambles to upload their data to the BS in slot t, where K(t) is Poisson-distributed, i.e.,

where is the mean of the number of new active UEs per slot. In addition, K(t) is independent for every t.

A2) An admitted UE transmits its data over a number of slots and the number of slots required for each device to upload its data varies from one UE to another. Let [TeX:] $$\nu_{s}$$ denote the probability that a UE requires s slots to upload its data. In addition, assume that [TeX:] $$s_{\max }$$ is the maximum number of slots to upload data from any UE. Thus, we have [TeX:] $$\sum_{s=1}^{s_{\max }} \nu_{s}=1.$$

Recall that Z(t) is the number of the admitted UEs (into the 3rd step), which are the UEs without preamble collisions, and [TeX:] $$C_{l}(t)$$ the number of active UEs that choose the lth preamble out of L preambles. Provided that an active UE chooses a preamble uniformly at random, under A1, we can show that

where

Thus, we can see that Z(t) has the binomial distribution with parameter L and p, denoted by Bin(L, p), or

where [TeX:] $$p=(\lambda / L) e^{-(\lambda / L)}.$$ The Poisson approximation can be used for Z(t), which results in the following distribution for Z(t):

For convenience, let [TeX:] $$Z_{0}=Z(t),$$ and at time slot t, let [TeX:] $$Z_{s}$$ be the number of the UEs that are admitted in the last s slot. Then, [TeX:] $$Z_{s}$$ has the same distribution of [TeX:] $$Z_{0}.$$ In addition, let [TeX:] $$Y_{s}$$ be the number of the UEs that still upload data among [TeX:] $$Z_{s}.$$ Fig. 6 depicts the relationship between [TeX:] $$Z_{s} \text { and } Y_{s}.$$ It is clear that [TeX:] $$Y_{0}= Z_{0} \text { and } Y_{s}$$ might decrease with s (as more UEs likely finish their uploading as s increases). For [TeX:] $$s \geq 1,$$ under A2 with the Poisson approximation in (21), a fraction [TeX:] $$\sum_{i=s}^{s_{\max }} \nu_{i} \text { of } Z_{s}$$ remains at time t, leading to

where [TeX:] $$\lambda_{s}=\lambda e^{-(\lambda / L)} \sum_{i=s}^{s_{\max }} \nu_{i}.$$

Finally, using [TeX:] $$Y_{s},$$ we can express the number of allocated channels at a certain time slot as follows:

where [TeX:] $$V=\sum_{s=1}^{s_{\max }} Y_{s}.$$ Then, using the Chernoff bound [24], an upper-bound on the outage probability becomes

It can also be shown that

where

The terms [TeX:] $$M_{y}(\theta)=\log \mathbb{E}\left[e^{\theta Y_{0}}\right] \text { and } M_{v}(\theta)=\log \mathbb{E}\left[e^{\theta V}\right]$$ are the logarithmic moment generating functions (LMGFs) of [TeX:] $$Y_{0}$$ and V , respectively. An upper bound on the outage probability is given by

It is well-known that the LMGF is convex (e.g., [25]). Thus, there exists a unique solution to the minimization on the righthand side (RHS) in (27). We can also have the following monotonic property of [TeX:] $$\psi(\cdot).$$

Lemma 2: For [TeX:] $$\bar{W}^{\prime}<\bar{W}^{\prime \prime} \leq W,$$ it satisfies

Proof: Let [TeX:] $$\psi_{1}(\theta)=\psi\left(\theta ; W, \bar{W}^{\prime}\right) \text { and } \psi_{2}(\theta)= \psi\left(\theta ; W, \bar{W}^{\prime \prime}\right) . \text { Since } \bar{W}^{\prime}<\bar{W}^{\prime \prime},$$ we have [TeX:] $$\psi_{2}(\theta)-\psi_{1}(\theta)=M_{v}\left(\bar{W}^{\prime \prime} \theta\right)-M_{v}\left(\bar{W}^{\prime} \theta\right)=\ln \frac{\mathbb{E}\left[e^{\bar{W}^{\prime \prime} \theta V}\right]}{\mathbb{E}\left[e^{\bar{W}^{\prime} \theta V}\right]} \geq 0$$ or [TeX:] $$\psi_{1}(\theta) \leq \psi_{2}(\theta), \theta \geq 0 . \text { Let } \theta^{*}=\operatorname{argmin}_{\theta>0} g_{2}(\theta).$$ Note that since the LMGF is convex, [TeX:] $$\theta^{*}$$ exists. Then, we have

which completes the proof.

It is noteworthy that if [TeX:] $$M_{v}(\theta)$$ is a monotonic increasing function of [TeX:] $$\theta,$$ we have the strict inequality in (28), i.e., [TeX:] $$\leq$$ is replaced with [TeX:] $$<$$ . In addition, an upper-bound on the outage probability of the conventional approach can be found using (27) by letting [TeX:] $$W=\bar{W}=W_{\mathrm{c}}$$ as a special case.

B. Optimization and Trade-off

In this subsection, we consider an optimization problem to decide the numbers of channels for admitted UEs in the 3rd step to upload their data packets with a quality-of-service (QoS) constraint.

From (27), it can be shown that

where [TeX:] $$d>0$$ can be seen as the negative QoS exponent [25], [26]. For the inequality on the left-hand side (LHS) term in (30), we need the following result.

Lemma 3: Under the Poisson approximation in (22), we have

where [TeX:] $$\bar{s}=\sum_{s=1}^{s_{\max }} s \nu_{s}$$ is the mean of the number of slots for uploading.

Proof: Since the sum of independent Poisson random variables is also Poisson, we have (31). We omit the detail as the derivation of (31) is straightforward.

For convenience, let [TeX:] $$\lambda_{0}=\lambda e^{-(\lambda / L)} \text { and } \lambda_{1}=\lambda e^{-(\lambda / L)} \bar{s}.$$ Then, from Lemma 3, it can be shown that

From this, [TeX:] $$\psi(\cdot)$$ can be re-written as

Let [TeX:] $$\theta(W, \bar{W})$$ be the solution that minimizes [TeX:] $$\psi(\theta, W, \bar{W}).$$ From (33), it can be shown that [TeX:] $$\theta(W, \bar{W})$$ is the solution of the following equation:

Since the LHS in (34) is an increasing function of [TeX:] $$\theta,$$ a sufficient condition for the existence of [TeX:] $$\theta(W, \bar{W}) \geq 0,$$ which is unique, is

Prior to discussing the optimization of [TeX:] $$W \text { and } \bar{W}$$ in EBT, consider the optimization for the conventional approach where [TeX:] $$W=\bar{W}=W_{c}.$$ In this case, it can be shown that

where [TeX:] $$\lambda_{\mathrm{c}}=\lambda_{0}+\lambda_{1}.$$ It is trivial to show that [TeX:] $$\theta$$ minimizing [TeX:] $$\psi_{\mathrm{c}}\left(\theta, W_{\mathrm{c}}\right)$$ is given by

Thus, the minimum of [TeX:] $$\psi_{\mathrm{c}}\left(\theta, W_{\mathrm{c}}\right)$$ becomes

which is an increasing function of [TeX:] $$W_{\mathrm{c}}$$ (its derivative is positive when [TeX:] $$\left.N>W_{\mathrm{c}} \lambda_{\mathrm{c}}\right).$$ Thus, for given QoS exponent d, the following rate maximization problem can be considered in the conventional approach:

Since [TeX:] $$R_{\mathrm{c}}$$ increases with [TeX:] $$W_{\mathrm{c}}$$ as in (3) and [TeX:] $$\psi_{\mathrm{c}}\left(\theta\left(W_{\mathrm{c}}\right), W_{\mathrm{c}}\right)$$ is also an increasing function of [TeX:] $$W_{\mathrm{c}},$$ the solution becomes

where [TeX:] $$\mathbb{Z}^{+}=\{1,2, \cdots\}$$ represents the set of positive integers. In Fig. 7, we illustrate [TeX:] $$R_{\mathrm{c}} \text { and } \psi_{\mathrm{c}}\left(\theta\left(W_{\mathrm{c}}\right), W_{\mathrm{c}}\right),$$ where [TeX:] $$W_{\mathrm{c}}^{*}(d)$$ is shown to be the solution. Note that due to the fact that [TeX:] $$\min _{\theta \geq 0} \psi_{\mathrm{c}}\left(\theta, W_{\mathrm{c}}\right)$$ increases with [TeX:] $$W_{\mathrm{c}},$$ by letting [TeX:] $$W_{\mathrm{c}}=1,$$ we can find the following condition for the existence of a feasible solution:

From Fig. 7, we can also observe a trade-off relationship between the mean transmission rate, [TeX:] $$R_{\mathrm{c}},$$ and the QoS exponent, -d. That is, since the mean transmission rate decreases when -d decreases for a lower outage probability, it can be seen that the increase of the mean transmission rate results in a higher outage probability, vice versa.

In EBT with the QoS constraint, the rate maximization problem can be formulated as

Clearly, if [TeX:] $$W=\bar{W}=W_{\mathrm{c}},$$ the problem in (42) reduces to that in (39).

To find the optimal solution of the problem in (42), we need to have few properties as follows.

Proposition 2: For given W, consider the following subproblem of (42):

where

Let

which is, if exists, the optimal solution of (43).

Proof: According to Lemma 2, [TeX:] $$\psi(\theta(W, \bar{W}) ; W, \bar{W})$$ is an increasing function of [TeX:] $$\bar{W}$$ (due to the strict inequality when V is Poisson). In addition, according to (2), [TeX:] $$R(W, \bar{W})$$ is an increasing function of [TeX:] $$\bar{W}$$ for givenW. As a result, for givenW, if (45) has a solution for a given d, it is unique and the solution of (43).

Thanks to the fact that [TeX:] $$\psi(\theta(W, \bar{W}) ; W, \bar{W})$$ is an increasing function of [TeX:] $$\bar{W},$$ for given W, we can find [TeX:] $$\bar{W}^{*}(d, W)$$ in (45) by incrementing [TeX:] $$\bar{W}$$ by 1 from [TeX:] $$\bar{W}=1.$$ While we can search for allW fromW = 1 to N to find feasible [TeX:] $$\{W, \bar{W}\},$$ the following property helps reduce the search interval.

Lemma 4: Suppose that [TeX:] $$\bar{W}^{*}(d, W)$$ does not exist for given [TeX:] $$W=W^{\prime}.$$ Then, it is also true for any [TeX:] $$W^{\prime \prime}$$ that is greater than [TeX:] $$W^{\prime}.$$

Since it can be easily proved by using the fact that [TeX:] $$\psi(d, W, \bar{W})$$ is also an increasing function of W, we do not provide details for the proof of Lemma 4. Note that [TeX:] $$\min _{\theta \geq 0} \psi(\theta ; W, \bar{W})$$ becomes the smallest if [TeX:] $$W=\bar{W}=1.$$ Thus, in order to find any [TeX:] $$W \geq 1, \bar{W} \geq 1,$$ the following condition is required:

which is equivalent to (41).

Based on the above results, in order to obtain a set of feasible pairs [TeX:] $$\{W, \bar{W}\},$$ we can have the algorithm in Algorithm 1. Once the set of feasible [TeX:] $$\{W, \bar{W}\}$$ is obtained, the optimal [TeX:] $$\{W, \bar{W}\}$$ is the pair that has the highest [TeX:] $$R(W, \bar{W}).$$

Note that the complexity of Algorithm 1 depends on the complexity of finding [TeX:] $$\bar{W}(d, W)$$ in (45). Since [TeX:] $$\bar{W} \leq W$$, for each

value of [TeX:] $$W, \bar{W} \in\{1, \cdots, W\}.$$ Suppose that for a given pair of [TeX:] $$(\bar{W}, W),$$ the complexity to find [TeX:] $$\theta(W, \bar{W})$$ in (44) is [TeX:] $$\Omega_{0},$$ which is independent of [TeX:] $$W \text { and } \bar{W}.$$ Then, the total complexity is at most [TeX:] $$\Omega_{0} \sum_{W=1}^{N} W=\Omega_{0} N(1+N) / 2.$$ Furthermore, since [TeX:] $$\psi(\theta ; W, \bar{W})$$ is a convex function of [TeX:] $$\theta, \Omega_{0}$$ depends on a numerical technique for 1-dimensional convex optimization. However, in general, [TeX:] $$\Omega_{0}$$ is inversely proportional to a required precision. In summary, to compare the overall performance of the conventional and proposed approaches, we need to find the mean rates after optimizing [TeX:] $$(W, \bar{W})$$ for the proposed approach via (42) and [TeX:] $$W_{\mathrm{c}}$$ for the conventional approach via (39) for given key parameters, e.g., [TeX:] $$N, \lambda, L, \text { and } d.$$ Unfortunately, it is difficult to find closed-form expressions for the maximum mean transmission rates. Thus, we need to rely on numerical methods to find them, which will be considered in Section V.

V. SIMULATION RESULTS

In this section, we present simulation results to see the performance of the proposed and conventional approaches with

[TeX:] $$\{W, \bar{W}\} \text { and } W_{\mathrm{c}}$$ by solving (39) and (42) under the assumption of independent Rayleigh fading channels in (4). For convenience, we assume that [TeX:] $$by solving (39) and (42) under the assumption of independent Rayleigh fading channels in (4). For convenience, we assume that$$ for all UEs. Furthermore, independent Poisson arrivals are assumed for the UEs that send randomly selected preambles from a pool of L preambles with mean arrival rate [TeX:] $$\lambda.$$ For the number of slots for packet transmissions, s, is assumed to have a uniform distribution so that [TeX:] $$\nu_{s}=1 / s_{\max }, s=1, \cdots, s_{\max }.$$

In Fig. 8, we show the performance for different maximum numbers of slots for packet transmissions, [TeX:] $$s_{\max },$$ in terms of the mean transmission rate and QoS exponent when [TeX:] $$N=200, \lambda=8, L=32, \text { and } d=-\ln (0.05)(\text { i.e. }, \operatorname{Pr}(Q>N) \leq 0.05).$$ In addition, the corresponding optimal numbers of channels for exploration and exploitation (i.e., [TeX:] $$W \text { and } \bar{W},$$ respectively) are shown together with [TeX:] $$W_{\mathrm{c}}$$ in Table 1. It is shown that the mean transmission rate per slot, [TeX:] $$R(W, \bar{W}),$$ of EBT is higher than that of the conventional approach, [TeX:] $$R_{\mathrm{c}}\left(W_{\mathrm{c}}\right),$$ for a wide range of [TeX:] $$\boldsymbol{S}_{\max },$$ while all the QoS exponents are less than [TeX:] $$-d \approx 2.9957$$ (or [TeX:] $$\operatorname{Pr}(Q>N)=0.05).$$ We also see that the number of channels per UE (i.e., [TeX:] $$W \text { and } \bar{W}$$ in EBT and [TeX:] $$W_{\mathrm{c}}$$ in the conventional approach) decreases with [TeX:] $$s_{\max }$$ in Table 1, which also results in the decrease of the mean transmission rate as shown in Fig. 8. This is expected as there are more packets to be transmitted from UEs with a larger [TeX:] $$s_{\max }.$$

The impact of the total number of channels, N, on the performance performance is illustrated in Fig. 9 when [TeX:] $$s_{\max }=10, \lambda=8, L=32, \text { and } d=-\ln (0.05)(\text { i.e., } \operatorname{Pr}(Q>N)=0.05).$$ As shown in Fig. 9, the increase of N results in the increase of the mean transmission rate with keeping the QoS exponent lower than -d. Clearly, the increase of the mean transmission rate can be achieved by increasing [TeX:] $$W \text { and } \bar{W}$$ in EBT and [TeX:] $$W_{\mathrm{c}}$$ in the conventional approach as shown in Table 2. It is interesting to see a particular case that N = 300. According to Table 2, the optimal numbers of channels for exploration and exploitation in EBT are [TeX:] $$W=10 \text { and } \bar{W}=4,$$ respectively, while [TeX:] $$W_{\mathrm{c}}$$ in the conventional approach is 5. Since [TeX:] $$s_{\max }=10,$$ we have [TeX:] $$\bar{s}=5.5.$$ On average, each UE in the conventional approach sends a total of [TeX:] $$(\bar{s}+1) W_{\mathrm{c}}=6.5 \times 5=32.5$$ packets⁴. On the other hand, in EBT, each UE sends a total of [TeX:] $$W+\bar{s} \bar{W}=10+5.5 \times 4=32$$ packets on average. That is, the numbers of transmitted packets in both the approaches are almost the same. In this case, while their QoS exponents are comparable, we can see that the mean transmission of EBT is higher than that of the conventional approach as shown in Fig. 9.

⁴ It includes pilot signals transmitted by a UE to allow the BS to estimate the channel coefficients and SNR.

As discussed earlier, the optimal numbers of channels can be found by solving (39) and (42) for a given QoS exponent. In Fig. 10, we show the performance for different negative QoS exponent, d, when [TeX:] $$N=300, s_{\max }=10, \lambda=8, \text { and } L=32.$$ As shown in Fig. 10(b), it is possible to keep the upper-bound on the QoS exponent below -d by choosing optimal [TeX:] $$W \text { and } \bar{W}$$ in EBT.We see that the mean transmission rate of EBT is higher than that of the conventional approach for any value of d.

In Table 3, we can see the optimal numbers of channels for each UE associated with Fig. 10. There are two variables, W and [TeX:] $$\bar{W},$$ for the optimization in EBT, while there is only one variable, [TeX:] $$W_{\mathrm{c}},$$ in the conventional approach. Consequently, it is possible to jointly optimize the pair of [TeX:] $$W \text { and } \bar{W}$$ so that the resulting QoS exponent is sufficiently close to -d in EBT. However, in the conventional approach, the optimization result is coarse as there is only one variable, i.e., [TeX:] $$W_{\mathrm{c}} \in\{1,2, \cdots\},$$ to be optimized, which results in a QoS exponent that is a bit loose. For example, when [TeX:] $$d=-\ln (0.01) \approx 4.6,$$ the optimal number of channels in the conventional approach is [TeX:] $$W_{\mathrm{c}}=4.$$ However, with [TeX:] $$W_{\mathrm{c}}=5,$$ it results in d = 4.083, which is slightly lower than the target negative QoS exponent, d = 4.6. From this, we can see that another salient advantage of EBT over the conventional one is that the radio RBs can be more precisely allocated to meet a QoS requirement thanks to an additional variable in terms of optimization perspective.

In Fig. 11, we show the performance for different numbers of preambles, L, when [TeX:] $$N=300, s_{\max }=10, \lambda=20, \text { and } d=-\ln (0.05).$$ Since [TeX:] $$\lambda$$ is fixed, as L increases, there are less preamble collisions, which leads to more admitted UEs per slot in the third step. As a result, we can see that the mean transmission rate decreases with L, while the QoS exponents are all less than -d due to optimal allocation of channels per UE (as shown in Fig. 11 (b)). It is also observed that the numbers of channels per UE, [TeX:] $$W \text { and } \bar{W},$$ in EBT decrease with L, which is also true in the conventional approach as shown in Table 3.

According to Figs. 8(b)–11(b), it has been observed that the actual QoS exponents obtained by simulations are lower than the QoS exponents that are obtained from the theory (e.g., (38) for the conventional approach). The gap is due to a number of reasons as follows: i) The Poisson approximation in (21) and (22); ii) the Chernoff bound in (24). In particular, since Z in (20) is a binomial variable, Z cannot be larger than L. However, in (21), due to the Poisson approximation, Z can be larger than L, which results in a heavier tail probability of Q than the actual one and a loose upper-bound in (24). Thus, we need to consider different methods to find tighter bounds as a further research topic. Other further research topics are to be discussed in Section VI.

VI. CONCLUDING REMARKS

In this paper, we proposed EBT that can increase the mean transmission rate by exploiting the multichannel selection diversity gain for uplink transmissions in MTC. To exploit the channel selection diversity gain, in particular, a BS initially allocated W channels to a new admitted UE in the third step and estimated their SNRs. Then, the BS sent the indices of the best [TeX:] $$\bar{W}$$ channels so that the UE can use them to upload their data packets, where [TeX:] $$\bar{W}<W.$$ In general, for a fixed [TeX:] $$\bar{W},$$ it was shown that a higher multichannel selection diversity gain can be achieved as W increases. Compared with the conventional approach where [TeX:] $$W=\bar{W}=W_{\mathrm{c}},$$ it was shown that EBT can have an improved transmission rate. However, since the use of more channels for exploration can result in a higher outage probability, an optimization problem was formulated with an outage probability constraint to allow a fair comparison with the conventional approach from a multiuser system point of view. We also derived an algorithm to find the optimal numbers of channels for exploration and exploitation, i.e., [TeX:] $$W \text { and } \bar{W},$$ in EBT. From simulation results, we confirmed that EBT can provide a higher mean transmission rate than the conventional one under various conditions thanks to multichannel selection diversity.

There are a number of issues to be studied in the future. Firstly, time-varying channels need to be studied, while we only focus on static channels in this paper. In particular, for mobile UEs, it is necessary to generalize the channel selection to take into account time-varying channels. Second, a more realistic objective function (instead of mean transmission rate) can be considered with finite-length codes and re-transmission protocols (e.g., hybrid automatic repeat request (HARQ) protocols [27], [28]). Third, as mentioned earlier, it is interesting to find a tighter upper-bound on the outage probability as the Chernoff bound with Poisson approximation turns to be a bit loose.