1

Multi-Cell-Aware Opportunistic Random Access
for Machine-Type Communications
Huifa Lin, Member, IEEE, and Won-Yong Shin, Senior Member, IEEE

arXiv:1708.02861v1 [cs.IT] 9 Aug 2017

Abstract
Due to the difficulty of coordination in multi-cell random access, it is a practical challenge how to achieve the optimal
throughput with decentralized transmission. In this paper, we propose a decentralized multi-cell-aware opportunistic random
access (MA-ORA) protocol that achieves the optimal throughput scaling in an ultra-dense K -cell random access network
with one access point (AP) and N users in each cell, which is suited for machine-type communications. Unlike opportunistic
scheduling for cellular multiple access where users are selected by base stations, under our MA-ORA protocol, each user
opportunistically transmits with a predefined physical layer data rate in a decentralized manner if the desired signal power to
the serving AP is sufficiently large and the generating interference leakage power to the other APs is sufficiently small (i.e., two
threshold conditions are fulfilled). As a main result, it is proved that the aggregate throughput scales as K
(1−ǫ) log(snr log N )
e
K−1

in a high signal-to-noise ratio (SNR) regime if N scales faster than snr 1−δ for small constants ǫ, δ > 0. Our analytical result
is validated by computer simulations. In addition, numerical evaluation confirms that under a practical setting, the proposed
MA-ORA protocol outperforms conventional opportunistic random access protocols in terms of throughput.
Index Terms
Decentralized transmission, inter-cell interference, machine-type communications (MTC), multi-cell-aware opportunistic
random access (MA-ORA), multiuser diversity, throughput scaling.

✦

1

I NTRODUCTION

Recently, random access in wireless communications is receiving growing attention due to the fast development of machinetype communications (MTC) and Internet of Things networks with the necessity of a relatively low protocol overhead and
high spectral efficiency [1], [2]. For several decades, various random access protocols have been developed based on
ALOHA and its variation with carrier sensing [3]. In MTC, transmission activity of vast devices tends to be irregular and
unpredictable with short packets [1]. Under the assumption of such a traffic pattern, state-of-the-art media access control
(MAC) protocols such as carrier-sense multiple access with collision avoidance (CSMA/CA) are not suitable because of a
great volume of protocol overheads [4], and rather uncoordinated random access protocols that incur much less protocol
overheads (e.g., slotted ALOHA) become favorable. However, the major problem of slotted ALOHA is its low MAC layer
efficiency. To solve this problem, there have already been research efforts on improving the MAC throughput by introducing
coded slotted ALOHA [5] and cooperative slotted ALOHA for multiple base station systems [6].
Furthermore, along with the explosive growth of users and their generated data packets in MTC, there is a trend of
densely deploying access points (APs), e.g., network densification in ultra-dense networks (UDN) [7]. Thus, it is crucial
to fully understand the nature of random access networks that consist of multiple cells sharing the same frequency band,
so called multi-cell random access networks.1 In such networks, besides the intra-cell collision (simultaneous transmission
from multiple users in the same cell), transmission without coordinated scheduling among APs will cause interference to
other-cell APs, which may lead to a failure of packet decoding at the receivers. Hence, inter-cell interference should be
carefully managed in multi-cell random access networks. In this paper, we address a challenging and fundamental issue of
multi-cell random access for MTC.
•
•

H. Lin is with the Communications & Networking Laboratory, Dankook University, Yongin 16890, Republic of Korea.
Email: huifa.lin.dr@ieee.org.
W.-Y. Shin is with the Department of Computer Science and Engineering, Dankook University, Yongin 16890, Republic of Korea.
E-mail: wyshin@dankook.ac.kr
1. Here, we use the term “cell” to denote the domain of an AP and the associated users.

2

1.1 Related Work
On the one hand, there are extensive studies on handling interference management of cellular networks with multiple base
stations [8], [9]. While it has been elusive to find the optimal strategy with respect to the Shannon-theoretic capacity in
multiuser cellular networks, interference alignment (IA) was recently proposed for fundamentally solving the interference
problem when there are multiple communication pairs [10]. It was shown that IA can asymptotically achieve the optimal
degrees of freedom, which are equal to K
2 , in the K -user interference channel with time-varying coefficients. Subsequent
work showed that interference management schemes based on IA can be well applicable to various communication
scenarios [11], [12], [13], including interfering multiple access networks [14], [15], [16]. In addition to the multiple access
scenarios in which collisions can be avoided, it is of significant importance how to manage interference in random access.
For multi-cell random access networks, several studies were carried out to manage interference by performing IA [17],
[18], [19] or successive interference cancellation (SIC) [6], [20]. In [21], [22], decentralized power allocation approaches were
introduced by means of interference mitigation for random access with capabilities of multi-packet reception and SIC at
the receiver.
On the other hand, there have been a great deal of studies on the usefulness of fading in single-cell broadcast channels
by exploiting the multiuser diversity gain as the number of users is sufficiently large, where opportunistic scheduling
[23], opportunistic beamforming [24], and random beamforming [25] were employed. Moreover, scenarios obtaining the
multiuser diversity gain were studied in multi-cell environments. In particular, opportunism can be utilized in multi-cell
broadcast networks through a simple extension of [25]. More recently, for multi-cell multiple access networks, the optimal
throughput scaling was analyzed by showing that the full multiuser diversity gain can be achieved by a distributed user
scheduling strategy in each cell, provided that scheduling criteria are properly determined and the number of users in each
cell is larger than a certain level [26]. Besides the aforementioned multiple access scenarios, the benefits of opportunistic
transmission can also be exploited in random access networks. The idea of single-cell-aware opportunistic random access
(SA-ORA) (also termed channel-aware slotted ALOHA in the literature) was proposed for slotted ALOHA random access
networks with a single AP [27], [28]. By assuming that channel state information (CSI) can be acquired at the transmitters,
the SA-ORA protocols in [27], [28] were shown to achieve the multiuser diversity gain without any centralized scheduling.
This idea was further extended to slotted ALOHA random access networks with imperfect CSI [29], a scenario with
discontinuous channel measurements [30], carrier sense multiple access networks [31], and multichannel wireless networks
[32], [33]. Nevertheless, all the protocols in [27], [28], [29], [30], [31], [32], [33] deal only with the single-AP problem, and
thus cannot be straightforwardly applied to multi-cell random access networks where the inter-cell interference exists.
1.2 Motivation and Contributions
In this paper, we consider an ultra-dense K -cell slotted ALOHA random access network, consisting of one AP and N users in
each cell, which is suited for MTC. We then introduce a decentralized multi-cell-aware opportunistic random access (MA-ORA)
protocol that achieves the optimal throughput scaling by effectively exploiting the multiuser diversity gain in the network
model. Precisely, not only a multiplexing gain of K
e but also a power gain of log log N can be achieved in the K -cell slotted
ALOHA random access network under consideration. First of all, it is worthwhile to address the fundamental differences
between our MA-ORA protocol and the two aforementioned different types of opportunistic transmission protocols:
•

•

Unlike opportunistic scheduling in [23], [24], [25], [26] for cellular multiple access environments where base stations
select users based on feedback information, in our MA-ORA protocol designed for random access, both the intra-cell
collision and inter-cell interference are mitigated solely by users’ opportunistic transmission in a decentralized manner.
The SA-ORA protocol in [27] was shown to achieve the multiuser diversity gain (i.e., the power gain) for single-AP
slotted ALOHA random access, but its extension to multi-cell random access is not straightforward due to the existence
of inter-cell interference. Moreover, in addition to the power gain, it remains open in the literature how to provide the
K -fold increase in the multiplexing gain via properly mitigating the inter-cell interference in the K -cell slotted ALOHA
random access network.

In our ultra-dense multi-cell random access network, users in each cell contend for the same channel at random without
centralized coordination from the serving AP. Consequently, without carefully designing a random access protocol, it is
impossible to entirely avoid the inter-cell interference as well as the intra-cell collision, which may result in a failure of
packet decoding at the receivers. Under our network model, each user needs to determine whether to transmit or not
by itself, without any centralized coordination from the serving AP. The nature of such random access imposes another

3

difficulty on the protocol design. We thus aim to respond to these challenges by introducing the MA-ORA protocol.
To do so, we first assume that uplink channel gains to multiple APs are available at the transmitters by exploiting the
uplink/downlink reciprocity in time-division duplex (TDD) mode. We utilize this partial CSI at the transmitter (CSIT) (but
not the global CSIT) to design our protocol. In the initialization phase, two thresholds and a physical layer (PHY) data
rate are computed offline and are broadcast over the network as system parameters. Thereafter, each user in a cell first
estimates the uplink channel gains via the downlink channel in each time slot. Then, each user determines whether both
1) the channel gain to the serving AP is higher than one threshold and 2) the total inter-cell interference leakage generated
by this user to the other APs is lower than another threshold. Users opportunistically transmit with the PHY data rate if
the above two conditions are fulfilled. By virtue of such opportunistic transmission, when N is large in our ultra-dense
random access setup, we are able to successfully decode the desired packets sent from multiple users in different cells with
high probability, while guaranteeing the optimal throughput scaling. Note that during the communication phase, no control
signaling from the APs is required, i.e., all the users independently perform opportunistic transmission. To the best of our
knowledge, multi-cell random access in a PHY perspective has not been well investigated before in the literature.
Our main results are twofold and summarized as follows.
•

•

In the ultra-dense K -cell slotted ALOHA random access network, it is shown that the aggregate throughput achieved
by the proposed MA-ORA protocol scales as K
e (1 − ǫ) log(snr log N ) in a high signal-to-noise ratio (SNR) regime,
K−1
provided that N scales faster than snr 1−δ for an arbitrarily small constant ǫ > 0 and a constant 0 < δ < 1. This reveals
that even without any centralized scheduling from the APs, the proposed protocol is able to achieve the full multiuser
diversity gain, while obtaining the multiplexing gain of 1e in a cell, which is the best we can hope for under slotted
ALOHA-type protocols [3].
Our analytical result is validated by numerically evaluating the aggregate throughput through Monte-Carlo simulations. We evaluate the throughput in finite SNR (or N ) regimes. Under a practical setting, it is also shown that our
MA-ORA protocol with a slight modification outperforms the conventional SA-ORA protocol in terms of throughput
for almost all realistic SNR regimes. In addition, to check the robustness of our MA-ORA protocol in the presence of
channel uncertainty, we perform simulations under the assumption of imperfect partial CSIT. It is examined that the
MA-ORA protocol with the imperfect partial CSIT achieves comparable performance on the aggregate throughput to
the case with the perfect partial CSIT if the amount of uncertainty is below a tolerable level and still outperforms the
SA-ORA protocol.

Some interference management protocols for multi-cell random access that employ IA and/or the AP cooperation [18],
[20] showed implementation successes based on industrial standards such as IEEE 802.11. Our MA-ORA protocol also
sheds important insights into a simple implementation of multi-cell random access, since neither the dimension expansion
nor the AP cooperation is required.
1.3 Organization and Notations
Section 2 presents system and channel models. Section 3 describes the proposed MA-ORA protocol. Section 4 shows how
to asymptotically achieve the optimal aggregate throughput scaling and the corresponding user scaling law. Section 5
provides numerical results to validate our analysis. Section 6 summarizes the paper with some concluding remarks.
Throughout the paper, C denotes the field of complex numbers. We use the following asymptotic notation: g(x) =
Ω(f (x)) means that there exist constants C and c such that g(x) ≤ Cf (x) for all x > c.

2

S YSTEM AND C HANNEL M ODELS

As illustrated in Fig. 1, we consider an ultra-dense multi-cell random access network consisting of K ≥ 1 APs using
the same frequency band, where N users are served in each cell and N is sufficiently large. We assume that there is no
cooperation among the APs for decoding, i.e., each AP attempts to decode the received packets from the belonging users
independently.2 All the users and APs are equipped with a single antenna. A slotted ALOHA-type protocol is adopted
and we assume perfect slot-level synchronization not only between the users and the serving AP but also among the APs.
We assume fully-loaded traffic such that each user has a non-empty queue of packets to transmit, similarly as in [34]. For
each user, a head-of-line packet is transmitted with probability p at random, regardless of the number of retransmissions,
2. Unlike [6], we do not utilize decoding cooperation among APs but our developed idea can be extended to to another framework allowing
cooperation among APs as future work.

4

User i
in cell j
AP j

Cell k

AP k

Fig. 1. The system model of an ultra-dense K -cell random access network with one AP and N users in each cell.

i.e., each packet is assumed to be the same for all retransmission states. We adopt a modified signal-to-interference-plusnoise ratio (SINR) capture model, where each AP is able to decode the received packet if its SINR exceeds a given decoding
threshold, while treating the inter-cell interference (the interfering signals from the other-cell users) as noise. The concurrent
intra-cell transmission such that two or more users in the same cell simultaneously transmit causes collision, and thus the
corresponding receiver (AP) fails to decode any packet. That is, in order to simplify system modeling and protocol design,
we do not adopt multi-packet reception and multiuser detection studied in [35], [36].
Let hij→k denote the fading channel coefficient from the i-th user in the j -th cell to the k -th AP for i ∈ {1, · · · , N } and
j, k ∈ {1, · · · , K}, where hij→k ∈ C is modeled by an independent and identically distributed (i.i.d.) complex Gaussian
random variable. In the UDN scenario where the APs and users are densely located, the large-scale path-loss components
from users to APs are assumed to be almost identical and thus are omitted. We assume the partial CSIT such that the users
can acquire the uplink channel gains to multiple APs. For instance, the channel gain from the i-th user in the j -th cell to the
i
k -th AP, denoted by gj→k
= |hij→k |2 , is available at the i-th user. The partial CSIT can be acquired via the downlink channel
by exploiting the uplink/downlink reciprocity in TDD mode. Practical CSIT acquisition methods have also been introduced
for various multi-cell multi-antenna systems [37], [38] and wireless local area networks [39], [40]. In the previous seminal
literature on SA-ORA with one AP deployment [27], [28], the partial CSIT and the corresponding distribution information
were assumed to be available. Recently, the CSIT acquisition process was described in more detail for the multichannel
SA-ORA [32]. Inspired by [27], [28], [32], a channel gain acquisition process for our model deploying multiple APs (i.e., our
multi-cell random access model) is described as follows. Under the slotted ALOHA protocol, each AP broadcasts (0, 1, e)
feedback to inform the belonging users of the reception status after each time slot via the downlink channel, where 0 means
that no packet is received (idle); 1 means that only one packet is received (successful transmission); and e indicates that two
or more packets are transmitted simultaneously (collision). In our multi-cell random access scenario, each AP broadcasts
the feedback message in an orthogonal mini-time slot, which requires a small amount of coordination among the APs.
By exploiting the uplink/downlink channel reciprocity, each user is capable of estimating the channel gains to multiple
APs through the received feedback messages. That is, it is possible for each user to perform multi-cell-aware channel gain
estimation. It is worth noting that since only the amplitude information of the CSIT (but not the phase information) is
required in our protocol, the length of feedback messages can be greatly shortened by using quantization.
We consider a quasi-static fading model, i.e., the channel coefficients are constant during one time slot and vary
independently in the next time slot. The received signal yk ∈ C at the k -th AP is given by

yk =

nk
X

π(u ) π(uk )

hk→kk xk

uk =1

|

π(u )

{z

desired signal

}

+

nj
K X
X
j=1
j6=k

|

π(u ) π(uj )

hj→kj xj

+zk ,

(1)

uj =1

{z

inter-cell interference

}

where xk k is the transmitted signal from the π(uk )-th user in the k -th cell and the binomial random integer nk ∼ B(N, p)
is the number of transmitting users in the k -th cell. The received signal is corrupted by the i.i.d. complex additive white
Gaussian noise (AWGN)
zk ∈C with zero-mean and the variance N0 . For each transmission, there is an average transmit

power constraint E

π(uk ) 2

xk

≤ PTX . We define the average SNR at each receiver as snr ,

PTX
N0 .

5

Users (Transmitters)

APs (Receivers)
Initialization phase:
Broadcast
over the network

2. Receive three parameters
broadcasted by APs

1. Obtain optimal
offline

.
.
.

3. Estimate uplink channel
gains and transmit
a packet opportunistically

Data packet

Feedback
message

4. Receive and
decode the packet

.
.
.

Fig. 2. The initialization phase of the proposed MA-ORA protocol.

3

M ULTI -C ELL -AWARE O PPORTUNISTIC R ANDOM ACCESS (MA-ORA)

In this section, we describe the entire procedure of our MA-ORA protocol including the selection of system parameters.
Under the proposed MA-ORA protocol, users opportunistically transmit with a properly selected PHY data rate R if
both the channel gain to the serving AP exceeds a given threshold ΦG and the sum of channel gains to the other APs is
below another given threshold ΦI . Compared to the conventional SA-ORA protocols that aim at enhancing the desired
signal power by only using ΦG , in our ultra-dense multi-cell setup, confining the inter-cell interference leakage to a given
sufficiently low level is more crucial to achieve the multiplexing gain. Hence, provided with the channel gains to other-cell
APs, we introduce another threshold ΦI , used to control the inter-cell interference leakage by exploiting the opportunism.
Our MA-ORA protocol operates in a decentralized manner without any additional control signaling from the APs after the
initialization phase, and hence fits well into ultra-dense random access networks. The detailed description of the protocol
is elaborated on in the following subsections.
3.1 The Overall Procedure
In this subsection, we describe the overall procedure of the proposed MA-ORA protocol. As illustrated in Fig. 2, in the
initialization phase, the APs broadcast two thresholds ΦG and ΦI , as well as the PHY data rate R for opportunistic
transmission in our ultra-dense multi-cell random access network. During the data communication phase, as shown in Fig.
3, it is examined that the maximum MAC throughput of the conventional slotted ALOHA protocol deploying one AP is
achieved at the transmission probability p = N1 for large N (see, e.g., the MAC throughput performance for N = 100 in
Fig. 3).3 Similarly, in our MA-ORA protocol, the transmission probability p is also set to N1 to avoid excessive intra-cell
collisions or idle time slots, thus enabling us to find a relationship between ΦG and ΦI (to be discussed in Section 3.2).
In each time slot, each user first estimates the uplink channel gains by using the feedback messages sent from the APs.
Then, for i ∈ {1, · · · , N } and j ∈ {1, · · · , K} (i.e., for all the users), the i-th user in the j -th cell compares the channel gains
with the given two thresholds to examine whether the following two inequalities are fulfilled:
i
gj→j
≥ ΦG

and

K
X

i
gj→k
≤ ΦI ,

(2)

(3)

k=1
k6=j

where (2) indicates a “good” channel condition to the serving AP that leads to a large desired signal power and (3) means
that the inter-cell interference leakage generated by this user is well confined due to a “weak” channel condition to the
3. The MAC throughput here is defined as the average number of successful transmissions per time slot, where only one user transmits in a
cell, and thus is given by N p(1 − p)N−1 .

6

Fig. 3. The MAC throughput versus transmission probability p, where N = 100 and the conventional slotted ALOHA with one AP deployment is
assumed.

other APs. In each cell, users satisfying both (2) and (3) transmit with the PHY data rate R (to be selected in Section 3.3),
while the other users keep idle in this time slot. Each AP then receives and decodes the desired packet by treating all the
interference as noise. By virtue of such opportunistic transmission, when N is sufficiently large in our ultra-dense random
access network, it is possible for the desired packets that are simultaneously sent from multiple users in different cells to
be successfully decoded at the receivers with high probability.
Note that our MA-ORA protocol operates for general K values. As a special case, for K = 1, each user just checks
whether the condition (2) is fulfilled or not, which corresponds to the conventional SA-ORA protocol.
3.2 The Selection of Two Thresholds
In this subsection, we show how to select the thresholds ΦG and ΦI . First, according to the opportunistic transmission
conditions (2) and (3), the probability that each user accesses the channel is expressed as


K
X
 i

i
≥ ΦG ,
≤ ΦI 
gj→k
p = Pr gj→j
k=1
k6=j

i
= Pr gj→j




K
X
 

i
≥ ΦG Pr 
gj→k
≤ ΦI  ,
k=1
k6=j

where the second equality holds since the channel gains to different APs are independent of each other. From the fact that
p is set to N1 , we have


K
 X
1

i
i
Pr gj→j
≥ ΦG Pr 
gj→k
≤ ΦI  = .
N
k=1
k6=j

Then, the relationship between ΦG and ΦI is given by


ΦG = FG−1 1 − (FI (ΦI )p−1 )−1

= FG−1 1 − (FI (ΦI )N )−1 ,

i
where FG and FI denote the cumulative distribution functions (CDFs) of gj→j
and

PK

i
gj→k
, respectively.
In our MA-ORA protocol, the threshold ΦI is set to snr−1 so that the optimal throughput scaling (i.e., the multiplexing
gain of 1e in a cell and the power gain) can be achieved for our slotted ALOHA random access as snr increases (to be
proven in Section 4). More precisely, due to the fact that the SINR at the receivers is lower-bounded by

snr · ΦG
,
1 + snr · ΦI

k=1
k6=j

(4)

7

the term snr · ΦI in (4) should scale as a positive constant independent of snr in order to achieve the multiplexing gain of
1
e in a cell under the slotted ALOHA-type protocol. In consequence, the two thresholds are given by
(
ΦI = snr−1

ΦG = FG−1 1 − (FI (snr−1 )N )−1 .
3.3 The Selection of PHY Data Rate

In this subsection, we show how to optimally select the PHY data rate R in terms of maximizing the throughput scaling
law. We start from computing the resulting successful decoding probability. At the receiver, even if an AP receives only
one packet from one of the belonging users, this packet may still be corrupted by the noise and the inter-cell interference.
Thus, it is required that the received SINR of the desired packet exceeds a certain decoding threshold given by 2R − 1. The
successful decoding probability ps is then expressed as




i


PTX gj→j


R
ps = Pr 
>
2
−
1
,
nk
K P


P
π(u)
 N0 +

PTX gk→j
k=1
k6=j

(5)

u=0

where the binomial random variable nk ∼ B(N, p) is the number of simultaneously transmitting users in the k -th cell and
π(u) denotes the index of transmitting users in each cell. Using the successful decoding probability in (5), the throughput
(j)
at the j -th AP for j ∈ {1, · · · , K}, denoted by Rsum , is given by
(j)
Rsum
= N p(1 − p)N −1 ·R · ps ,
|
{z
}
MAC throughput

where N p(1 − p)N −1 is the MAC throughput and R is the target PHY data rate. From the fact that p =
throughput of the K -cell random access network is given by

Rsum =

K
X

1
N,

the aggregate

(j)
Rsum

j=1



1 N −1
· R · ps
=K 1−
N




1 N −1
ΦG
R
≥K 1−
· R · Pr
>
2
−
1
,
N
snr−1 + ñΦI

(6)

where ñ ∼ B((K − 1)N, p) is a binomial random variable, representing the total number of interfering signals from the
PK
other cells, and is given by ñ = k=1 nk . Here, the inequality comes from (2) and (3).
k6=j
Now, we focus on computing a lower bound on the successful decoding probability, denoted by p̃s , shown below:


ΦG
R
>
2
−
1
p̃s = Pr
snr−1 + ñΦI
(7)


(K−1)N
X
ΦG
R
Pr
=
> 2 − 1 Pr(ñ = i).
snr−1 + iΦI
i=0
Let us consider an integer ν ∈ {0, 1, · · · , (K − 1)N }. If R is set to a value such that

ΦG
ΦG
< 2R − 1 ≤
,
−1
+ (ν + 1)ΦI
snr + νΦI


ΦG
R
then the probability Pr snr−1
≥
2
−
1
is given by 1 and 0 for i ∈ {0, 1, · · · , ν} and i ∈ {ν + 1, · · · , (K − 1)N },
+iΦI
respectively. Based on this observation, the entire feasible range of 2R − 1 (i.e., the decoding threshold) can be divided into
the following (K − 1)N + 1 sub-ranges:


ΦG
,··· ,
0,
snr−1 + (K − 1)N ΦI




ΦG
ΦG
ΦG
,
,∞
.
,··· ,
snr−1 + (ν + 1)ΦI snr−1 + νΦI
snr−1
snr−1

8
ΦG
( snr
−1 , ∞),

In particular, for R ∈
wehave p̃s = 0, which is thus neglected in our work.
ΦG
R
(7) is an indicator function of R, we set R to the maximum
Using the fact that the term Pr snr−1
+iΦI ≥ 2 − 1 in 
i
ΦG
R
G
value under the condition that 2 − 1 lies in each sub-range snr−1 +(ν+1)Φ
, snr−1Φ+νΦ
, which is given by
I
I

R = log2 1 +

ΦG
snr−1 + νΦI



.

(8)

Here, the parameter ν ∈ {0, 1, · · · , (K − 1)N } in (8) can be interpreted as a tolerable number of interfering signals from the
other-cell users. That is, a relatively high successful decoding probability can be guaranteed even when the desired signal
at the receiver is interfered by ν signals caused by the other-cell users. Note that we can improve p̃s for each transmitted
packet at the cost of a lower R (corresponding to a larger ν ). In other words, we can trade a lower PHY data rate for a
higher successful decoding probability (refer to (7)).
Remark 1: It is worth noting that the optimal PHY data rate can be found by solving the aggregate throughput
maximization problem as follows: R̂ = arg max Rsum (R). However, as an alternative approach, it is sufficient to set R
R

to (8) in the sense of guaranteeing the optimal throughput scaling because i) selecting a proper finite ν leads to a successful
decoding probability ps approaching 1, which plays a crucial role in showing the optimality of our protocol, and ii) the
expression in (8) is analytically tractable and thus enables us to derive a closed-form expression of the aggregate throughput
scaling law. Detailed analytical discussions are addressed in the next section.

4

A NALYSIS OF AGGREGATE T HROUGHPUT S CALING L AW

In this section, we show that the proposed MA-ORA protocol asymptotically achieves the optimal throughput scaling,
i.e., K
e (1 − ǫ) log(snr log N ) for an arbitrarily small constant ǫ > 0, in the ultra-dense K -cell slotted ALOHA random
access network, provided that N scales faster than a certain level. To be specific, we first provide some preliminaries
including a simplification of p̃s and a tractable lower bound on FI (x). We then present our main result by analyzing
the aggregate throughput scaling under a certain user scaling condition. In addition, we show an upper bound on the
aggregate throughput scaling and compare the proposed MA-ORA protocol with the existing opportunistic scheduling
approach for the interfering multiple access channel (IMAC).
4.1 Preliminaries
In this subsection, we introduce two important lemmas to present our main result. To obtain the first lemma, we start
from revisiting the lower bound on the aggregate throughput in (6). To simplify this lower bound, we derive an explicit
i
expression of ΦG as a function of ΦI . Due to the fact that the channel gain gj→j
follows the exponential distribution whose
−x
CDF is given by FG (x) = 1 − e , it is possible to establish the following relationship between ΦG and ΦI :

ΦG = FG−1 1 − (FI (ΦI )p−1 )−1
(9)
= ln (FI (ΦI )N ) .
By using (9) in (6), we have




ln (FI (ΦI )N )
1 N −1
R
>
2
−
1
.
Rsum ≥K 1 −
·R · Pr
N
snr−1 + ñΦI
|
|
{z
}
{z
}
MAC throughput

(10)

p̃s

For analytical convenience, the following lemma is presented since the resulting form of p̃s is still not analytically
tractable.
Lemma 1. When the PHY data rate R is selected from the discrete set in (8), we have

p̃s = I1− N1 ((K − 1)N − ν, ν + 1) ,

(11)

where Ix (y, z) is the regularized incomplete beta function.
Proof:
 As shown in (8),the PHY data rate R is a function of the integer ν ∈ {0, 1, · · · , (K − 1)N }. We recall that the term
ΦG
R
Pr snr−1
+iΦI ≥ 2 − 1 in (7) is given by 1 and 0 for i ∈ {0, · · · , ν} and i ∈ {ν + 1 · · · , (K − 1)N }, respectively, if R is
set to a value such that
ΦG
ΦG
< 2R − 1 ≤
.
snr−1 + (ν + 1)ΦI
snr−1 + νΦI

9

Fig. 4. The function p̃s = I1−

1
N

((K − 1)N − ν, ν + 1) versus ν for K = {2, 3, 4}.

Thus, by dividing the whole range of i into two sub-ranges, (7) can be expressed as
ν
X

p̃s =

i=0
ν
X

=

(K−1)N

1 · Pr(ñ = i) +

X

0 · Pr(ñ = i)

i=ν+1

Pr(ñ = i)

i=0

= Pr(ñ ≤ ν),
which is the CDF of the binomial random variable ñ ∼ B((K − 1)N, N1 ). It is known that this CDF can be expressed as the
regularized incomplete beta function [41], which is given by

p̃s = I1− N1 ((K − 1)N − ν, ν + 1) .
This completes the proof of this lemma.
From this lemma, we are able to equivalently transform the expression of p̃s in (10) to the well-known regularized
incomplete beta function. In Fig. 4, the function I1− 1 ((K − 1)N − ν, ν + 1) versus ν is plotted for various K = {2, 3, 4}.
N
This function tends to get steeply increased for small ν and then to gradually approach one. That is, it is monotonically
increasing with ν . For example, for K = 2, it is numerically found that the pairs of (p̃s , ν) are given by (0.9, 3), (0.99, 5),
and (0.999, 7). Based on this observation, it is possible to select a proper finite value of ν that makes p̃s approach almost
one.
Using (8), (10), and (11), the aggregate throughput is now lower-bounded by




1 N −1
ln (FI (ΦI )N )
Rsum ≥K 1 −
· log2 1 +
N
snr−1 + νΦI
|
{z
}
(12)
PHY data rate (R)

· I1− N1 ((K − 1)N − ν, ν + 1) .

However, it is still not easy to find a closed form expression of (12) due to the complicated form of FI (ΦI ). This
motivates us to introduce the following lemma.
Lemma 2. For any 0 ≤ x < 2, the CDF of

K
P

k=1
k6=j

i
gj→k
, FI (x), is lower-bounded by

FI (x) ≥ c1 x(K−1) ,
where c1 =

e−1 2−(K−1)
(K−1)Γ(K−1)

is a constant independent of N and SNR. Here, Γ(x) = (x − 1)! is the Gamma function.

Proof: We refer to [26, Lemma 2] for the proof.

10

Using this lemma leads to a more tractable lower bound on the aggregate throughput, which will be analyzed in the
next subsection.
4.2 Aggregate Throughput Scaling and User Scaling Laws
As our main result, we are now ready to establish the following theorem, which presents the aggregate throughput scaling
law achieved by the proposed MA-ORA protocol.
Theorem 1. Consider the MA-ORA protocol in the ultra-dense K -cell slotted ALOHA random access network. Suppose that ΦI =
snr−1 . Then, the MA-ORA protocol achieves an aggregate throughput scaling of

with high probability in the high SNR regime if

K
(1 − ǫ) log(snr log N )
e

(13)



K−1
N = Ω snr 1−δ ,

(14)

where ǫ > 0 is an arbitrarily small constant and 0 < δ < 1 is a certain constant.
Proof: Using ΦI = snr−1 , (12) can be rewritten as




1 N −1
snr · ln(FI (snr−1 )N )
Rsum ≥K 1 −
· log2 1 +
N
ν +1

(15)

· I1− N1 ((K − 1)N − ν, ν + 1) .

We then select a finite value of ν that makes the function I1− 1 ((K − 1)N − ν, ν + 1) approach almost one by following
N
the equation below:
(16)
I1− 1 ((K − 1)N − ν ∗ , ν ∗ + 1) = 1 − ǫ,
N

4

where ǫ > 0 is an arbitrarily small constant. Since the function I1− 1 ((K − 1)N − ν, ν + 1) is monotonically increasing
N
with ν as shown in Fig. 4, we can find finite ν ∗ (K, ǫ) by taking the inverse of the regularized incomplete beta function in
(16).
By substituting (16) and ν = ν ∗ (K, ǫ) into (15), we have




snr · ln(FI (snr−1 )N )
1 N −1
· log2 1 +
Rsum ≥K 1 −
N
ν ∗ (K, ǫ) + 1

· (1 − ǫ).

N −1
From the fact that 1 − N1
is monotonically decreasing with increasing N and lim 1 −
N →∞
aggregate throughput is lower-bounded by


snr · ln(FI (snr−1 )N )
K
· (1 − ǫ)
· log2 1 +
Rsum ≥
e
ν ∗ (K, ǫ) + 1
!

K−1
snr · ln(c1 snr−1
N)
K
· (1 − ǫ),
· log2 1 +
≥
e
ν ∗ (K, ǫ) + 1


1 N −1
N

=

1
e,

the

where the second inequality holds owing to Lemma 2. In order to achieve the logarithmic gain (i.e., the power gain with
K−1
increasing N ), it is required that c1 snr−1
N ≥ N δ for 0 < δ < 1, which finally yields


K−1
N = Ω snr 1−δ .
(17)
In consequence, under the user scaling condition in (17), the aggregate throughput can be lower-bounded by


K
δ · snr ln(N )
Rsum ≥ (1 − ǫ) · log2 1 + ∗
,
e
ν (K, ǫ) + 1

(18)

∗
which scales as K
e (1 − ǫ) log(snr log N ) since δ and ν (K, ǫ) are some constants independent of N . This completes the
proof of the theorem.

4. Note that ǫ is a given design parameter and ν ∗ can be expressed as a function of given ǫ and K .

11
K
e

Theorem 1 indicates that the proposed MA-ORA protocol can achieve not only the near
multiplexing gain
(corresponding to the pre-log term in (13)) but also the power gain of log log N in our multi-cell random access network.
To obtain such gains, the inter-cell interference leakage generated by a certain user needs to be well confined by setting
ΦI = snr−1 . This implies that a larger N is necessary to confine the total interference to a lower level by virtue of the
multiuser diversity gain for a higher snr. More precisely, in order to achieve the optimal throughput scaling, the number of
per-cell users, N , is required to scale with snr as shown in (14). Based on the analytical result in Theorem 1, the following
interesting observations are provided with respect to the parameters K , δ , and ǫ.
Remark 2: According to (13) and (14), it is found that the aggregate throughput scaling linearly increases with K at the
cost of more stringent user scaling condition (note that N needs to exponentially increase with K for given snr). In ultradense random access networks with many users, our MA-ORA protocol can improve the multiplexing gain by deploying
more APs, but more per-cell users are required to guarantee this improvement.
Remark 3: We now turn to the effect of δ on the aggregate throughput performance. Although increasing δ leads to
the aggregate throughput increment (refer to (18)), it does not fundamentally change the aggregate throughput scaling
law. However, increasing δ yields a more stringent user scaling condition. Thus, it is sufficient to select a proper value of
0 < δ < 1 according to the given network condition.
Remark 4: The pre-log term 1 − ǫ corresponds to the successful decoding probability, which can be interpreted as a
penalty of random access without any coordination. This penalty cannot be totally resolved because there is always a nonzero probability of unsuccessful decoding caused by the excessive inter-cell interference generated by random transmission
(refer to (16)). This is a distinctive phenomenon of multi-cell random access, compared to the IMAC scenario where each
base station performs user selection.
To increase the successful decoding probability, we can decrease ǫ by selecting a larger ν ∗ according to (11). However,
this results in a lower PHY data rate R in (8) that affects the resulting aggregate throughput. Thus, we need to carefully
balance this trade-off between ǫ and ν ∗ when selecting system parameters in practice. Nevertheless, it is sufficient to
assume a finite ν ∗ leading to an arbitrarily small ǫ > 0 to analyze our throughput scaling result.
4.3 Discussions
In this subsection, we first present an upper bound on the aggregate throughput scaling that matches our analytically
achievable result. Then, we compare the proposed MA-ORA protocol with the opportunistic scheduling protocol for the
IMAC [26].
An upper bound on the aggregate throughput scaling: An aggregate throughput scaling of K
e log(snr log N ) can be obtained
by a genie-aided removal of all the inter-cell interference, which is explained as follows. Consider an ideal scenario for
the multi-cell random access network in which concurrent interfering signals sent from other cells are completely canceled
out. This corresponds to a system consisting of K interference-free parallel SA-ORA networks. Since the throughput scales
as 1e log(snr log N ) in each cell of such SA-ORA networks [27], the aggregate throughput scales as K
e log(snr log N ). This
corresponds to an upper bound on the aggregate throughput scaling for our K -cell random access network, which matches
the achievable aggregate throughput scaling in (13) to within a factor of ǫ > 0.
Comparison with the opportunistic scheduling protocol for the IMAC: The aggregate throughput scaling of K log(snr log N )
is achieved by the opportunistic scheduling protocol for the IMAC, where collisions can be avoided by adopting user
selection at each base station [26]. By comparing our MA-ORA protocol with this scheduling protocol, we observe some
interesting consistency as follows: 1) user scaling conditions required by the two protocols are exactly the same and 2)
under this user scaling condition, after removing the intra-cell contention loss factor (note that the MAC throughput in a
cell is given by 1 and 1e in multiple access and slotted ALOHA random access, respectively), these two protocols achieve
the same throughput scaling to within an arbitrary small ǫ > 0 gap. Hence, essential similarities are revealed by applying
opportunism to both multiple access and random access networks.
In contrast to the observed similarities, there are fundamental differences between the two protocols. Under the
opportunistic scheduling protocol in [26], users in each cell who fulfill the given channel conditions send transmission
requests to the base station. Then, each base station randomly selects one user and informs the user of the PHY data rate
for transmission via the downlink channel. On the other hand, under our MA-ORA protocol, without controlling from the
APs, each user determines whether to transmit by comparing its own channel gains with the two thresholds. Besides, the
PHY data rate does not need to be sent from the APs since it is already broadcast in the initialization phase and keeps the
same afterwards. These features make our MA-ORA protocol suitable for uncoordinated random access networks.

12

Fig. 5. The aggregate throughput versus SNR, where the proposed MA-ORA protocol is employed as N scales according to the user scaling
condition.

5

N UMERICAL E VALUATION

In this section, we validate the proposed MA-ORA protocol by intensively performing numerical evaluation through
Monte-Carlo simulations, where the channels in (1) are randomly generated 1 × 105 times for each system parameter.
First, our analytical result is validated by comparing the aggregate throughput through numerical evaluation with
the corresponding theoretical one. Performance of the proposed MA-ORA protocol is also compared with that of the
conventional SA-ORA and slotted ALOHA protocols in practical simulation environments. In addition, performance of
both the MA-ORA and SA-ORA protocols is evaluated under the assumption of imperfect partial CSIT.
5.1 Validation of Analytical Results
In this subsection, we validate our analytical result in an ultra-dense multi-cell random access setup by evaluating the
aggregate throughput [bps/Hz] of the proposed MA-ORA protocol in Sections 3 and 4. Suppose that we set ǫ = 0.01
and δ = 0.1. Then, the parameter ν can be found according to the relationship between ǫ and ν in (16). We assume that
ΦI = snr−1 and ΦG = ln(FI (ΦI )N ) (see (9)). Based on these parameters, the PHY data rate R can be computed from (8).
In Fig. 5, we evaluate the aggregate throughput achieved by the MA-ORA protocol versus snr in dB scale for K = {2, 3}.
K−1
The parameter N is set to a different scalable value according to snr, i.e., N = snr 1−δ in (14). In the figure, the dotted lines
are also plotted from the theoretical result in Theorem 1 with a proper bias to check the slopes of K
e (1 − ǫ) log(snr log N )
for K = {2, 3}. One can see that the slopes of the simulated curves coincide with the theoretical ones in the high SNR
regime. This numerical results are sufficient to guarantee our achievability (i.e., the throughput scaling under the given
user scaling law) in Section 4.
Now, in Fig. 6, we evaluate the aggregate throughput versus N , where K = 2 and snr = {10, 15, 20, 25}dB.5 We adopt
the aforementioned parameter setting except for δ that is used to specify the user scaling condition in (14). One can see that
all the curves tend to increase at most logarithmically with N owing to the multiuser diversity gain, which corresponds to
the throughput scaling in (13). It is also observed that for large N , increasing the snr leads to superior performance on the
aggregate throughput due to the power gain. As illustrated in the figure, it is worth noting that this superior throughput
performance can be achieved when N is sufficiently large (or the user scaling law in (14) is fulfilled).
5.2 Performance Evaluation in a Practical Setting
In this subsection, to further ascertain the efficacy of our MA-ORA protocol, performance on the aggregate throughput is
evaluated in finite SNR (or N ) regimes. Under this practical setting, instead of using the original MA-ORA protocol, we
5. Even if it seems unrealistic to have a great number of users even in ultra-dense random access models, the wide range of parameter N is
taken into account to precisely see some trends of curves varying with N .

13

Fig. 6. The aggregate throughput versus N , where the proposed MA-ORA protocol is employed for K = 2.

K\N
2
3
4
2
3
4
2
3
4

50

100

snr = 10dB
(1.40, 2.32) (1.70, 3.64)
(1.70, 2.14) (1.90, 2.45)
(1.90, 1.54) (2.10, 1.60)
snr = 20dB
(0.90, 4.40) (0.80, 4.88)
(1.70, 2.33) (1.60, 2.77)
(1.70, 1.70) (1.90, 1.89)
snr = 30dB
(0.60, 4.65) (0.65, 5.70)
(1.40, 2.42) (1.45, 3.05)
(1.90, 1.54) (2.00, 1.89)

200
(2.20, 3.91)
(2.30, 2.72)
(2.20, 2.02)
(1.10, 5.61)
(1.30, 3.18)
(2.20, 2.09)
(0.70, 6.57)
(1.50, 3.16)
(1.80, 2.13)

TABLE 1
The lookup table of (Φ∗G , R∗ ) according to various K , N , and snr.

slightly modify the MA-ORA protocol in Sections 3 and 4 by numerically finding the optimal parameters Φ∗G and R∗ in
terms of maximizing the resulting aggregate throughput Rsum (ΦG , R),6 which is given by

(Φ∗G , R∗ ) = argmax Rsum (ΦG , R).

(19)

ΦG ,R

The corresponding Φ∗I can be found by using Φ∗G in (9). The optimal values of (Φ∗G , R∗ ) can be found via exhaustive search
for given parameter configuration including K, N , and snr. The optimal values of (Φ∗G , R∗ ) are summarized in Table 1.
From the table, some insightful observations are made as follows. For given snr and N , the optimal PHY data rate R∗ tends
to decrease with K . This is because more inter-cell interference is generated for larger K , thus leading to a lower SINR at
the receivers and the resulting lower R∗ . Moreover, for given snr and K , R∗ tends to increase with N . This follows from
the fact that for larger N , the inter-cell interference can be better mitigated with the help of the multiuser diversity gain,
thereby leading to a higher SINR at the receivers. This enables us to adopt a higher R∗ .
In Fig. 7, the aggregate throughput of the proposed MA-ORA protocol versus snr in dB scale is plotted for K = 2 and
N = 100. As baseline schemes, performance of the SA-ORA and slotted ALOHA protocols is also
in the figure.
 shown 
ΦG PTX
Under the SA-ORA protocol, each user opportunistically transmits with the PHY data rate of log2 1 + N0
if its uplink
channel gain exceeds ΦG [27]. This protocol can be treated as a special case of our MA-ORA protocol with K = 1 and thus
leads to worse performance as K ≥ 2. For the slotted ALOHA protocol, since both details of the PHY layer and the effects
of fading are neglected in the protocol design phase, we adopt the PHY data rate of log2 (1 + snr) for fair comparison. It
is observed that the MA-ORA protocol outperforms the slotted ALOHA and SA-ORA protocols in the low and moderate
SNR regimes, and then gets saturated to a certain value in the high SNR regime. This throughput saturation comes from
6. Note that the MA-ORA protocol needs to be slighted modified when it is evaluated in practical settings since it is inherently designed for
asymptotically achieving the optimal throughput scaling.

14

Fig. 7. The aggregate throughput versus snr, where the proposed MA-ORA protocol (K = 2) as well as the conventional SA-ORA and slotted
ALOHA protocols are employed for N = 100.

Fig. 8. The aggregate throughput versus snr, where the proposed MA-ORA protocol is employed for K = {2, 3, 4} and N = 100.
TABLE 2
The lookup table of (Rsum , snr) according to various K and N , where snr denotes a crossover where two curves coincide.

K\N
2
3
4

50

100

150

200

(2.83, 17dB)
(1.91, 9dB)
(1.69, 7dB)

(3.59, 22dB)
(2.35, 12dB)
(2.08, 10dB)

(4.05, 26dB)
(2.68, 14dB)
(2.28, 11dB)

(4.31, 28dB)
(2.88, 16dB)
(2.45, 12dB)

the fact that the multiplexing and multiuser diversity gains are not fully achieved due to the limited N (which is less than
the one required by our user scaling condition) in the network suffering from the severe inter-cell interference.
Figure 8 illustrates the aggregate throughput of the MA-ORA protocol versus snr in dB scale for K = {2, 3, 4} and
N = 100. It is seen that when K becomes large, the MA-ORA protocol achieves superior aggregate throughput in the low
SNR regime, but gets saturated earlier due to a more stringent user scaling condition (note that N needs to exponentially
increase with K for given snr). The curve for K = 2 achieves inferior performance to the other curves for K = {3, 4} in
the low SNR regime, but tends to increase steadily with snr and then get saturated at a relatively high snr point. Thus,
it is worthwhile to investigate a crossover where two curves meet when the aggregate throughput of the MA-ORA and
SA-ORA protocols versus snr is plotted. The crossover snr and the resulting aggregate throughput Rsum (i.e., (Rsum , snr))
are summarized in Table 2 according to various K and N .

15

Fig. 9. The aggregate throughput versus σ2 under the imperfect partial CSIT assumption, where the proposed MA-ORA (K = 2) and SA-ORA
protocols are employed for snr = 10dB and N = 100.

5.3 Performance Evaluation Under the Assumption of Imperfect Partial CSIT
The numerical results in the previous subsections were obtained based on the assumption of perfect partial CSIT (i.e.,
perfect channel gain acquisition). However, it is hardly possible to acquire the perfect partial CSIT due to the channel
estimation or feedback error in practice. To check the robustness of our MA-ORA protocol in the presence of channel
i
uncertainty, we perform simulations by assuming the imperfect channel gain ĝj→k
= |ĥij→k |2 at each transmitter, where
i
i
i
i
ĥj→k = hj→k + ∆hj→k . Here, the error component, ∆hj→k , is modeled as an i.i.d. and complex Gaussian random variable
with zero-mean and the variance σ 2 [42]. In the MA-ORA protocol, we use the optimal parameters Φ∗G and R∗ found based
on (19).
As illustrated in Fig. 9, it is obvious to see that the aggregate throughput of both MA-ORA and SA-ORA protocols
gets degraded as σ 2 increases. It is also observed that in the presence of the error component, our MA-ORA protocol still
outperforms the SA-ORA protocol and achieves acceptable performance if the error variance σ 2 is below a tolerable level
(e.g., σ 2 < 10−2 ). Moreover, when σ 2 is large (e.g., σ 2 > 10−1 ), the performance gap between the MA-ORA and SA-ORA
protocols tends to be wider, showing that our MA-ORA protocol is less sensitive to the channel gain inaccuracy.

6

C ONCLUDING R EMARKS

The MA-ORA protocol operating in a decentralized manner, appropriate for MTC, was proposed for the ultra-dense K cell slotted ALOHA random access network, where no centralized coordination from the serving APs is required. The
aggregate throughput scaling achieved by the proposed protocol was then analyzed. As our main result, it was proved that
the MA-ORA protocol asymptotically achieves the aggregate throughput scaling of K
e (1−ǫ) log(snr log N ) in our multi-cell
K−1
random access network, provided that N scales faster than snr 1−δ for small constants ǫ > 0 and 0 < δ < 1. Extensive
computer simulations were also performed to validate the MA-ORA protocol and its analytical result—the throughput
scaling and user scaling laws were confirmed numerically; the superiority of our protocol over baseline schemes was
shown in a practical setting; and the robustness of our protocol was investigated when imperfect partial CSIT is assumed.
Our random access framework would shed important insights for intelligently solving intra-cell collision and inter-cell
interference problems.
Future research directions include extensions to networks with multiple antennas, opportunistic random access with
user fairness, and cooperative slotted ALOHA systems.

ACKNOWLEDGMENTS
This research was supported by the Basic Science Research Program through the National Research Foundation of Korea
(NRF) funded by the Ministry of Education (2017R1D1A1A09000835) and by the Ministry of Science, ICT & Future Planning
(MSIP) (2015R1A2A1A15054248). The material in this paper has been presented in part at the IEEE International Conference
on Communications 2017 [43] and the IEEE International Symposium on Information Theory 2017 [44]. Won-Yong Shin is
the corresponding author.

16

R EFERENCES
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
[10]
[11]
[12]
[13]
[14]
[15]
[16]
[17]
[18]
[19]
[20]
[21]
[22]
[23]
[24]
[25]
[26]
[27]
[28]
[29]
[30]
[31]
[32]

A. Rajandekar and B. Sikdar, “A survey of MAC layer issues and protocols for machine-to-machine communications,” IEEE Internet Things
J., vol. 2, no. 2, pp. 175–186, Jan. 2015.
C. Bockelmann, N. Pratas, H. Nikopour, K. Au, T. Svensson, C. Stefanovic, P. Popovski, and A. Dekorsy, “Massive machine-type
communications in 5G: physical and MAC-layer solutions,” IEEE Commun. Mag., vol. 54, no. 9, pp. 59–65, Sep. 2016.
D. Bertsekas and R. Gallager, Data networks (2nd Ed.). New Jersey, USA: Prentice-Hall, Inc., 1992.
G. Durisi, T. Koch, and P. Popovski, “Toward massive, ultrareliable, and low-latency wireless communication with short packets,” Proc. IEEE,
vol. 104, no. 9, pp. 1711–1726, Sep. 2016.
E. Paolini, G. Liva, and M. Chiani, “Coded slotted ALOHA: A graph-based method for uncoordinated multiple access,” IEEE Trans. Inf.
Theory, vol. 61, no. 12, pp. 6815–6832, Dec. 2015.
D. Jakovetić, D. Bajović, D. Vukobratović, and V. Crnojević, “Cooperative slotted ALOHA for multi-base station systems,” IEEE Trans.
Commun., vol. 63, no. 4, pp. 1443–1456, Feb. 2015.
S. Chen, R. Ma, H.-H. Chen, H. Zhang, W. Meng, and J. Liu, “Machine-to-machine communications in ultra-dense networks–a survey,” IEEE
Commun. Surveys Tuts., May 2017.
A. D. Wyner, “Shannon-theoretic approach to a Gaussian cellular multiple-access channel,” IEEE Trans. Inf. Theory, vol. 40, no. 6, pp. 1713–
1727, Aug. 1994.
O. Somekh and S. Shamai, “Shannon-theoretic approach to a Gaussian cellular multiple-access channel with fading,” IEEE Trans. Inf. Theory,
vol. 46, no. 4, pp. 1401–1425, Aug. 2002.
V. R. Cadambe and S. A. Jafar, “Interference alignment and degrees of freedom of the K -user interference channel,” IEEE Trans. Inf. Theory,
vol. 54, no. 8, pp. 3425–3441, Jul. 2008.
T. Gou and S. A. Jafar, “Degrees of freedom of the K user M × N MIMO interference channel,” IEEE Trans. Inf. Theory, vol. 56, no. 12, pp.
6040–6057, Nov. 2010.
V. R. Cadambe and S. A. Jafar, “Degrees of freedom of wireless X networks,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), Toronto, Canada, Jul.
2008, pp. 1268–1272.
H. J. Yang, W.-Y. Shin, B. C. Jung, C. Suh, and A. Paulraj, “Opportunistic downlink interference alignment for multi-cell MIMO networks,”
IEEE Trans. Wireless Commun., vol. 16, no. 3, pp. 1533–1548, Mar. 2017.
C. Suh and D. Tse, “Interference alignment for cellular networks,” in Proc. 46th Annu. Allerton Conf., Monticello, IL, Sep. 2008, pp. 1037–1044.
B. C. Jung and W.-Y. Shin, “Opportunistic interference alignment for interference-limited cellular TDD uplink,” IEEE Commun. Lett, vol. 15,
no. 2, pp. 148–150, Feb. 2011.
B. C. Jung, D. Park, and W.-Y. Shin, “Opportunistic interference mitigation achieves optimal degrees-of-freedom in wireless multi-cell uplink
networks,” IEEE Trans. Commun., vol. 60, no. 7, pp. 1935–1944, Jul. 2012.
S. Gollakota, S. D. Perli, and D. Katabi, “Interference alignment and cancellation,” ACM SIGCOMM Computer Communication Review, vol. 39,
no. 4, pp. 159–170, Aug. 2009.
K. C.-J. Lin, S. Gollakota, and D. Katabi, “Random access heterogeneous MIMO networks,” ACM SIGCOMM Computer Communication Review,
vol. 41, no. 4, pp. 146–157, Oct. 2011.
H. Jin, S.-W. Jeon, and B. C. Jung, “Opportunistic interference alignment for random access networks,” IEEE Trans. Veh. Technol., vol. 64,
no. 12, pp. 5947–5954, Jan. 2015.
W. Zhou, T. Bansal, P. Sinha, and K. Srinivasan, “BBN: Throughput scaling in dense enterprise WLANs with bind beamforming and nulling,”
in Proc. ACM 20th Annu. Int. Conf. on Mobile Computing and Networking, Maui, HI, Sep. 2014, pp. 165–176.
H. Lin, K. Ishibashi, W.-Y. Shin, and T. Fujii, “A simple random access scheme with multilevel power allocation,” IEEE Commun. Lett., vol. 19,
no. 12, pp. 2118–2121, Dec. 2015.
——, “Decentralized power allocation for secondary random access in cognitive radio networks with successive interference cancellation,”
in Proc. of IEEE Int. Conf. Commun. (ICC), Kuala Lumper, Malaysia, May 2016, pp. 1–6.
R. Knopp and P. A. Humblet, “Information capacity and power control in single-cell multiuser communications,” in Proc. IEEE Int. Conf.
Commun. (ICC), Seattle, WA, Jun. 1995, pp. 331–335.
P. Viswanath, D. N. C. Tse, and R. Laroia, “Opportunistic beamforming using dumb antennas,” IEEE Trans. Inf. Theory, vol. 48, no. 6, pp.
1277–1294, Aug. 2002.
M. Sharif and B. Hassibi, “On the capacity of MIMO broadcast channels with partial side information,” IEEE Trans. Inf. Theory, vol. 51, no. 2,
pp. 506–522, Jan. 2005.
W.-Y. Shin, D. Park, and B. C. Jung, “Can one achieve multiuser diversity in uplink multi-cell networks?” IEEE Trans. Commun., vol. 60,
no. 12, pp. 3535–3540, Dec. 2012.
X. Qin and R. A. Berry, “Distributed approaches for exploiting multiuser diversity in wireless networks,” IEEE Trans. Inf. Theory, vol. 52,
no. 2, pp. 392–413, Jan. 2006.
S. Adireddy and L. Tong, “Exploiting decentralized channel state information for random access,” IEEE Trans. Inf. Theory, vol. 51, no. 2, pp.
537–561, Jan. 2005.
S.-H. Wang and Y.-W. P. Hong, “Transmission control with imperfect CSI in channel-aware slotted ALOHA networks,” IEEE Trans. Wireless
Commun., vol. 8, no. 10, pp. 5214–5224, Oct. 2009.
H. Moon, “Channel-adaptive random access with discontinuous channel measurements,” IEEE J. Sel. Areas Commun., vol. 34, no. 5, pp.
1704–1712, Apr. 2016.
G. Miao, Y. Li, and A. Swami, “Channel-aware distributed medium access control,” IEEE/ACM Trans. Netw., vol. 20, no. 4, pp. 1290–1303,
Dec. 2012.
Z. Khanian, M. Rasti, F. Salek, and E. Hossain, “A distributed opportunistic MAC protocol for multichannel wireless networks,” IEEE Trans.
Wireless Commun., vol. 15, no. 6, pp. 1–1, Mar. 2016.

17

[33] Y. Liu and M. Liu, “To stay or to switch: Multiuser multi-channel dynamic access,” IEEE Trans. Mobile Comput., vol. 14, no. 4, pp. 858–871,
Apr. 2015.
[34] Y. Li and L. Dai, “Maximum sum rate of slotted Aloha with capture,” IEEE Trans. Commun., vol. 64, no. 2, pp. 690–705, Feb. 2016.
[35] Y. J. Zhang, P. X. Zheng, and S. C. Liew, “How does multiple-packet reception capability scale the performance of wireless local area
networks?” IEEE Trans. Mobile Comput., vol. 8, no. 7, pp. 923–935, Jul. 2009.
[36] Y. H. Bae, B. D. Choi, and A. S. Alfa, “Achieving maximum throughput in random access protocols with multipacket reception,” IEEE Trans.
Mobile Comput., vol. 13, no. 3, pp. 497–511, Mar. 2014.
[37] P. Komulainen, A. Tölli, and M. Juntti, “Effective CSI signaling and decentralized beam coordination in TDD multi-cell MIMO systems,”
IEEE Trans. Sig. Process., vol. 61, no. 9, pp. 2204–2218, May 2013.
[38] R. Rogalin, O. Y. Bursalioglu, H. Papadopoulos, G. Caire, A. F. Molisch, A. Michaloliakos, V. Balan, and K. Psounis, “Scalable synchronization
and reciprocity calibration for distributed multiuser MIMO,” IEEE Trans. Wireless Commun., vol. 13, no. 4, pp. 1815–1831, Apr. 2014.
[39] “Local and metropolitan area networksspecific requirements; part 11: wireless LAN medium access control (MAC) and physical layer (PHY)
specifications; amendment 4: enhancements for very high throughput for operation in bands below 6 GHz,” IEEE P802.11ac/D3.1, 2012.
[40] R. Liao, B. Bellalta, M. Oliver, and Z. Niu, “MU-MIMO MAC protocols for wireless local area networks: A survey,” IEEE Commun. Surveys
Tuts., vol. 18, no. 1, pp. 162–183, 2014.
[41] M. Abramowitz and I. A. Stegun, Handbook of Mathematical Functions. New York, NY, USA: Dover, 1966.
[42] X. Zhang, D. P. Palomar, and B. Ottersten, “Statistically robust design of linear MIMO transceivers,” IEEE Trans. Sig. Process., vol. 56, no. 8,
pp. 3678–3689, Aug. 2008.
[43] H. Lin and W.-Y. Shin, “Achieving the optimal throughput scaling in multi-cell random access networks,” in Proc. of IEEE Int. Conf. Commun.
(ICC), Paris, France, May 2017.
[44] ——, “Multi-cell aware opportunistic random access,” in Proc. of IEEE Int. Symp. Inf. Theory (ISIT), Aachen, Germany, Jun. 2017.

