Reducing Initial Cell-search Latency in
mmWave Networks
Yanpeng Yang, Hossein S. Ghadikolaei, Carlo Fischione, Marina Petrova, and Ki Won Sung

arXiv:1802.06450v1 [] 18 Feb 2018

School of Electrical Engineering and Computer Science, KTH Royal Institute of Technology, Stockholm, Sweden
E-mails: {yanpeng, hshokri, carlofi, petrovam, sungkw}@kth.se

Abstract—Millimeter-wave (mmWave) networks rely on directional transmissions, in both control plane and data plane,
to overcome severe path-loss. Nevertheless, the use of narrow
beams complicates the initial cell-search procedure where we
lack sufficient information for beamforming. In this paper, we
investigate the feasibility of random beamforming for cell-search.
We develop a stochastic geometry framework to analyze the
performance in terms of failure probability and expected latency
of cell-search. Meanwhile, we compare our results with the naive,
but heavily used, exhaustive search scheme. Numerical results
show that, for a given discovery failure probability, random
beamforming can substantially reduce the latency of exhaustive
search, especially in dense networks. Our work demonstrates that
developing complex cell-discovery algorithms may be unnecessary
in dense mmWave networks and thus shed new lights on mmWave
system design.
Index Terms—Millimeter-wave networks, cell-search, beamforming, dense networks, stochastic geometry.

I. I NTRODUCTION
Millimeter-wave (mmWave) technology is one of the essential components of future wireless networks to support
extremely high data rate services [1]. To compensate for
the severe path-loss, mmWave systems rely on directional
transmissions using large antenna arrays both at the transmitter
and at the receiver. Such directional transmission, albeit reduces the interference footprint and simplifies the scheduling
task [2], complicates the initial synchronization and cell-search
procedure as the antenna patterns of base stations (BS) –or
access points– and user equipment (UE) should be aligned to
be able to receive time-frequency synchronization signals.
Barati et al. [3] proposed a link-level procedure for directional initial access in a single cell scenario. The synchronization signals and the detection approach is such that timefrequency-spatial synchronization occurs jointly. In contrast,
[4] proposed a two-level synchronization architecture for a
multi-cell scenario where macro-level signals help BSs and
UEs synchronize in time and frequency domains, and a local
beam scanning executes the synchronization in the spatial
domain. [5] and [6] provide a system-level analysis of this
scheme for a spacial beam scanning approach: exhaustive
search. In particular, both BSs and UEs sequentially scan the
whole angular space to find “the best” link quality. However,
finding “an acceptable” link, formally defined in Section II,
may be much faster, reducing the latency for the establishment
of data plane. Fast initial access becomes even more important
for wireless sensor networks comprising many wake-up radios

in which the synchronization may take longer than the actual
data transmission, leading to a poor latency performance. As
we show throughout this paper, increasing the BS (or access
point) density can reduce the initial access latency, as opposed
to the exhaustive-search.
Random beamforming is an alternative to the exhaustive
search in which the BSs (and UEs) focus their antenna patterns
toward a randomly pick direction. Lee et al. [7] investigated
the data plane performance (in terms of sum-rate) of random
beamforming. References [4] and [8] have shown the feasibility of applying random beamforming for initial cell search
of mmWave networks. In particular, [4] analyzed the delay
statistics of initial access, assuming a noise-limited scenario
and a deterministic channel model, and showed promising
results for the performance of random beamforming. [8]
achieved a similar conclusion by analyzing the Cramér-Rao
lower bound for estimating directions of arrival and departure
(essentially spatial synchronization). The analysis, however, is
limited to a single-link scenario.
Motivated by these initial results, we substantially extend [4]
and [8] and provide a system-level framework to analyze the
performance of initial access based on random beamforming
in a multi-cell mmWave network. The main contributions of
this paper are:
•

•

•

•

By a stochastic geometry analysis, we evaluate the detection failure probability and delay distribution of random
beamforming for initial cell search.
We characterize the tradeoff between failure probability
and expected latency and show the superior latency
performance of the random beamforming compared to
the exhaustive search. This performance gain gets more
prominent in dense mmWave networks.
We formulate an optimization problem to find the optimal beamwidth subject to a minimum detection failure
probability.
We numerically analyze the performance of random
beamforming for cell-search and demonstrate that it may
be unnecessary to develop a complicated cell-search
algorithm in dense mmWave networks.

The rest of the paper is organized as follows. In Section II,
we describe the system model. Main results are presented in
Section III, followed by numerical performance evaluation in
Section IV. The paper is concluded in Section V.

Transmission frame

Cell search

Data transmission

UE beam m
BS
BS
beam beam
1
2

...

BS
beam
NBS

...

t
1 scan cycle

k scan cycles
k = 0, 1, 2...

Fig. 1: Illustration of transmission frame with random beamforming.

II. S YSTEM M ODEL
A. Network and Antenna Models
We consider a mmWave cellular network where the BSs
are distributed according to a two-dimensional Poisson point
processes (PPP) Φ , {xi } with density λ. The UEs follow
another independent PPP, from which the typical UE, located
at the origin, is our focus according to the Slivnyak’s theorem [9].
Each BS and UE is equipped with multiple antennas and
supports analog beamforming. We believe that digital or
hybrid beamforming does not suit initial cell-search due to the
existence of many antenna elements and lack of prior channel
knowledge, translated into the need for costly pilot transmission schemes. We consider half-power beamwidths of θBS and
θUE at the BSs and UEs, respectively, with the corresponding
antenna gains GBS and GUE . For analytical tractability, we
model the actual antenna patterns by a sectorized antenna
model as in [4]. In an ideal sectorized antenna pattern, the
antenna gain Gx , x ∈ {BS, UE}, as a function of beamwidth
θx is a constant in the main lobe and a smaller constant in the
side lobe, given by
 2π−(2π−θx )
, in the main lobe,
θx
Gx (θx ) =
(1)
,
in the side lobe,
where typically   1. For sake of mathematical simplicity,
we assume  = 0, i.e., no sidelobe gain, and only one RF
chain at the BSs and UEs, though the analysis can be readily
extended for the general case.
For a given θBS and θUE , which are a non-increasing
function of the number of antenna elements, BSs and UEs
sweep the entire angular space by NBS = d2π/θBS e and
NUE = d2π/θUE e beamforming vectors, respectively. Without
loss of generality of the main conclusions, we assume that
2π/θBS and 2π/θBS are integers and drop d·e operator.
B. Propagation and Blockage Models
We adopt a simple distance-dependent attenuation model
with path-loss exponent α > 2 as [4] and [6]. The path-loss
from a BS located at xi to the typical UE, located at the origin,
is
α

c
,
`(kxi k) =
4πkxi kfc

where c is the light speed, fc is the operating frequency and
kxi k represents the distance between xi and the origin.
Let Si be a binary variable taking 1 iff there is a LoS
condition between BS xi and the typical UE. We apply an
exponential blockage model [10]. Formally, Si = 1 with probability e−βkxi k , where β is a constant parameter determined
by the size and density of the obstacles, and β −1 represents the
average length of a LoS link. Similar to [11], we assume that
mmWave signals cannot penetrate blockages. This assumption
is also motivated by [12] which shows that neglecting NLoS
links comes at almost no penalty in the accuracy of statistical
analysis. The impact of NLoS links is left for a future work.
Small-scale fading hi between BS xi and the typical UE
follow a unit-mean Rayleigh distribution. Compared to more
realistic models for LoS paths such as Nakagami fading,
Rayleigh fading provides very similar design insights while
leads to more tractable results [5].
Denoting pBS as the BS transmit power and W as the thermal noise, the signal-to-interference-plus-noise ratio (SINR)
when the typical UE is receiving from BS xi is given by
SINRi =

P

hi `(kxi k)Si
,
hj `(kxj k)Sj + σ 2

xj ∈Φ\xi

where σ 2 = W (pBS GBS GUE )−1 is the normalized noise power.
C. Random Beamforming Model
The transmission frame under random beamforming is illustrated in Fig. 1. The cell-search period comprises of several
mini-slots. In each mini-slot, every BS independently and
uniformly at random picks a direction out of NBS . We define
a scan cycle as the period within which every BS sends cellsearch pilots to NBS directions. In each scan cycle, the UE
antenna points to a random direction out of NUE , and the
BS covers all non-overlapping NBS directions. Different from
exhaustive search in which the BS and UE need to cover
all the NBS NUE possible directions [5], the cell-search period
of random beamforming can be dynamically adjusted. Once
the UE received a pilot signal that meets a predefined SINR
threshold, it is associated to the corresponding BS. Note that
it may not be the final association of that UE, but once the
UE is registered to the network, it can establish data plane,
and the reassociation phase (to the best BS) could be smooth
without service interruption [4].
Let t denote the duration of one mini-slot. Unlike [5] where
a fixed t is considered, our mini-slot duration depends on
the beamwidths and therefore on NBS and NUE . This is a
more realistic model because communication with narrower
beams (higher antenna gains) requires less time than that
with wider beams to ensure collecting the same energy at the
receiver. Nevertheless, there exist a minimum value of minislot duration t0 which corresponds to the minimum length
of the symbols (e.g., the duration of one OFDM symbol).
Using the simulation parameters of [13], we set NBS = 12
(θBS = 30◦ ) and NUE = 4 (θUE = 90◦ ) as our baseline
to achieve t0 mini-slot duration. Namely, t = t0 when

NBS NUE = 48, and in general it is inversely proportional to
NBS NUE . For a general NBS and NUE , the mini-slot duration
is
48t0
t = max(t0 ,
),
(2)
NBS NUE
and the number of search mini-slots in every scan cycle is
NBS .
D. Performance Metrics
We say the typical UE successfully detects the cell if the
strongest signal it receives in any mini-slot from one of the
directions achieves a minimum SINR threshold T . Namely,
the success event is I{maxxi ∈Φ SINRi ≥ T }, where I{·} is
the indicator function. For any realization of the topology Φ
and channel fading h, detection failure may happen due to two
reasons: there is no BS inside the UE’s main beam or the ones
inside cannot meet the detection threshold T .
Now, we define two performance metrics, for the typical
UE, evaluated throughout the paper.
Definition 1. The detection failure probability Pf (Nc ) is the
probability that the UE is not detected by any BS within Nc
mini-slots.
Definition 2. Given a time-budget of Nc mini-slots, the cellsearch latency L(Nc ) of a UE is defined as the time period
by which the UE successfully detects a cell-search pilot and
can be registered with the corresponding BS.
Remark 1. For all Nc ∈ N, we have t0 ≤ L(Nc ) ≤ Nc t.
The lower-bound of L(Nc ) is due to the need for sending
at least one pilot. Note that smaller Nc values correspond to
smaller L(Nc ), and that L(1) = t, but the price is higher
failure probability. In fact, reducing Nc means limiting the
search budget and registering only a few users that can detect
pilot signals within Nc mini-slots. L(∞) characterizes the
latency of UEs that can be detected ultimately. In some
realizations of the random network topology, there is no BS
close enough to the origin to detect the typical UE with the
target SINR threshold. In those cases, the latency is undefined
as the UE is fundamentally unable to find the pilot signals,
independent of the cell-search policy. We formally characterize
this issue in Lemma 1.
III. M AIN RESULTS
In this section, we present our main results and some
insights on the performance of initial access using random
beamforming. Proofs are provided in Appendix.
Lemma 1. The probability that the typical UE has no LoS
link to any BS is
Pno-LoS = exp(−

2λπ
).
β2

(3)

Proposition 1. The detection failure probability Pf (Nc ) of a
UE is

Pf = max (1 − Ps )Nc , Pno-LoS ,
(4)

where Pno-LoS is given in (3), and Ps is the successful detection
probability in one mini-slot, given by


Z ∞
Z ∞
2π
T rα e−βv
−T r α σ 2
Ps =
e
exp −
vdv
λb
NBS NUE
vα + T rα
0
0
2π
e−βr
λrdr .
NBS NUE
Next, we derive the expected search latency, normalized
to the mini-slot duration t. Proposition 2 shows the average
number of mini-slots required for detection a cell-search
signal.
Proposition 2. The normalized expected search latency given
that the UE can be detected over Nc mini-slots is
1 − (Nc + 1)(1 − Ps )Nc + Nc (1 − Ps )Nc +1
E[L(Nc )]
=
.
t
(1 − Pf )Ps
(5)
Remark 2. When Nc → ∞, the search latency
L(Nc ) becomes geometrically distributed, implying that
limNc →∞ t−1 E[L(Nc )] → Ps−1 .
Proposition 1 and 2 characterize two important aspects
of the cell-search under random beamforming. Increasing
the search budget Nc reduces the failure probability while
increases the average search-latency. In the following, we
optimize this tradeoff.
Consider the characterizations of the detection failure probability and latency, formulated in (3), (4), and (5). We aim
to design the BS beamwidth (θBS or equivalently NBS ) to
minimize the cell search latency given a failure probability
constraint Pfmax ∈ [0, 1]. Recall that θBS = 2π/NBS . Moreover,
from Fig. 1, each scan cycle has NBS mini-slots. The optimal
number of sectors for k ∈ N scan cycles (so Nc = kNBS ) is
min E[L(kNBS )]
NBS

s.t. Pf (kNBS ) ≤ Pfmax ,
NBS ∈ N ,

(6a)
(6b)
(6c)

where Pfmax and k are inputs to this optimization problem.
The problem can be utilized for system design in mmWave
networks. With the knowledge of network deployment (BS
desntiy), we can set the configuration of BS antennas to
meet the requirements of various applications with different
reliability and/or latency constraints. An example of the solutions to the problem can be observed from the figures in
the next section. We finish this section by characterizing the
performance of the exhaustive search.
Remark 3. For the exhaustive search, given any NBS and
NUE , the search space of one scan cycle is Nc = NBS NUE
mini-slots. The detection failure
probability is Pf (Nc ) =

max (1 − Ps )NBS NUE , Pno-LoS and the expected search latency
is E[L(Nc )] = NBS NUE t.
To illustrate Remark 3, we note that the exhaustive search
has a fixed duration for scanning cycles (NBS NUE mini-slots).
If the UE is not detected in one cycle, which may happen

TABLE I: Main simulation parameters.

due to random deep fading or random strong interference, it
might be detected in the next cycles (in next frame perhaps).
However, the UE cannot terminate the search process right
after detecting one cell-search signal, as it is looking for
the “best” one. In random beamforming, however, the UE
is looking for a “sufficiently good” one and will probably
terminate the process sooner than NBS NUE mini-slots. In
the next section, we show that this stop policy substantially
reduces the cell-search latency.
IV. N UMERICAL R ESULTS
In this section, we present the numerical results of cell
search under random beamforming. The simulation parameters
are summarized in Table I. Unless otherwise specified, we set
λ = 10−3 /m2 , θBS = 30◦ (NBS = 12), θUE = 90◦ (NUE = 4).
As we mentioned in Introduction, state-of-the-art cell-search
algorithms either work on the link-level or are designed for a
single-cell scenario, which are not fairly comparable with our
system-level multi-cell scenario. The closest ones to our work
are [5] and [6], which investigate exhaustive search with minislots of constant duration. To compare our proposed random
beamforming with these works from the literature, we consider
an exhaustive search that admits mini-slot duration based on
(2).
Fig. 2 shows the cell-search performance against BS density
λ. We observe a good matching between mathematical analysis
and Monte Carlo simulations. From Fig. 2(a), the detection
failure probability reduces with the BS density. Besides, Pf
converge to Pno-LoS as k → ∞, shown in Proposition 1.
From Fig. 2(b), the expected search latency decreases for
denser networks. The main reason is the availability of more
candidate BSs to register the UE. Consistent with Remark 2,
the latency converge to Ps−1 as Nc → ∞. Noting that the
best possible values for the failure probability and normalized
expected latency are 0 and 1, respectively. By employing
random beamforming, we can get close to those values in
dense mmWave networks.
Fig. 3 compares the performance of exhaustive search
and random beamforming for cell-search, and it shows the
normalized expected search latency corresponding to the same
search budget Nc = NBS NUE . As predicted by Remark 3 and
its related discussions, there is a huge gap between the latency
of random beamforming and that of exhaustive search.
Fig. 4 illustrates the tradeoff between detection failure
probability and the cell-search budget. The area above the
lines illustrate the feasible performance regions of cell-search,

1
0.8
Pf (kNBS )

Value
30 dBm
3
0.02
0 dB
28GHz
1MHz
7dB
-174 dBm/Hz

k = 1, 2, 100, 1000

0.6
0.4
0.2

Analysis
Simulation
Pno-LoS

0
10−6

10−5

10−4
BS density, λ

10−3

10−2

(a) Detection failure probability.
104
Analysis
E[L(kNBS )] (mini-slots)

Description
BS transmit power
Path-loss exponent
Blockage exponent
SINR threshold
Operating frequency
Control plane bandwidth
Noise figure
Thermal noise

Simulation

1/Ps

103

102

101
k = 1, 2, 100, 1000
100 −6
10

10−5

10−4
BS density, λ

10−3

10−2

(b) Expected searching latency.
Fig. 2: Effect of BS density λ on the performance metrics (NBS = 12).
Detection failure probably for k = 100 and k = 1000 coincide with Pno-LoS .
80
Exhaustive search
Random beamforming
60
E[L]/t0

Parameter
pBS
α
β
T
fc
B
NF
W

40

20

0

4

8
12
16
Number of sectors at BS, NBS

20

Fig. 3: Expected latency of random beamforming and exhaustive search.

namely there are some settings for NBS and NUE that allow realizing any (E[L], Pf ) point above the line. For the exhaustive
search, the feasible region is a sequence of step functions due
to its quantized latency, which is a subset of that of the random
beamforming. Moreover, denser mmWave networks have a
larger feasible region, which gives more flexibility to optimize
the tradeoff between detection probability and latency.
Fig. 5 shows the objective and constraint functions of
optimization problem (6). Increasing NBS means decreasing
θBS . As shown in the figure, the detection failure probability is
a decreasing function of NBS and therefore narrower beams are

performance, especially in dense BS deployment scenarios.
Consequently, it may be unnecessary to develop complex
algorithms for cell search process in future dense mmWave
networks. Meanwhile, random beamforming scheme can be
selected as a new benchmark in future initial access studies
considering its simplicity and good performance.
The current work focused on LoS links and control plane
performance. Future extensions can incorporate NLoS pathloss models and the performance of the data plane.

Detection failure probability, Pf

100

10−2

10−4

10−6

RB, λ = 10−4
RB, λ = 10−3
EH, λ = 10−3
20

40
60
80
100
Cell-search latency constraint, Nc

18
Pf , k = 1
E[L], k = 1

0.5

Pf , k = 2
E[L], k = 2

15
12

0.4
0.3

9

0.2

6

0.1

3

0

5

10
15
Number of sectors at BS, NBS

Expected search latency, E[L(kNBS )]

Detection failure probability, Pf (kNBS )

Fig. 4: Tradeoff between the detection failure probability and average latency.
“RB” and “EH” stand for random beamforming and exhaustive search,
respectively.
0.6

A PPENDIX
P ROOFS

120

0
20

Fig. 5: Detection failure probability and expected search latency against
number of scan cycles k and number of BS sectors NBS .

always beneficial. The floor of Pf is due to both the blockage
and deep fading, which can be improved either by increasing
the BS density (λ) or search budget (kNBS ). Meanwhile, as
long as the mini-slot duration t is a decreasing function of
NBS , namely narrower beams can reduce mini-slot duration,
E[L(Nc )] is a decreasing function of NBS as well. After
a critical point where t = t0 , the search latency increases
with NBS . In this situation, narrower beams cannot reduce
the mini-slot duration anymore but linearly increase NBS so
linearly increases the search space. The optimal beamwidth
(or equivalently the optimal NBS ) depends on the maximum
allowable detection failure probability Pfmax .
V. C ONCLUSION AND F UTURE W ORKS
In this paper, we investigated the performance of random
beamforming in initial cell-search of mmWave networks. We
developed an analytical framework leveraging stochastic geometry to evaluate the detection failure and latency performance. Numerical results showed that random beamforming,
though being very efficient from signaling and computational
perspectives, can provide near optimal detection and latency

A. Lemma 1
Define by B(o, R) a ball of radius R centered at the origin,
by nR the number of BSs in B(o, R), and by mR the number
of BSs in B(o, R) that has LoS to the typical UE. Clearly,
mR ≤ nR . Given the Poisson distribution of the BSs, we
have
Pr(mR = 0) =

∞
X

Pr(mR = 0 | nR = n) Pr(nR = n)

n=0

n
 R
Z
∞
−λπR2
X
(λπR2 )n
2r
(a)
 (1 − e−βr ) dr e
=
2
R
n!
k=0
0


2λπ(1 − (βR + 1)eβR )
= exp −
,
(7)
β2
where (a) follows from the properties of PPP, given a fixed
number of points in an area, the points are independently and
uniformly distributed over the area, and the the assumption of
independent blockages on each link. By setting R to infinity,
we extend the ball to the whole plane


2πλ
.
Pno-LoS = lim Pr(mR = 0) = exp − 2
R→∞
β
B. Proposition 1
Denote P
BSi as the BS located at xi , r = kxi k and
Ixi ,
hj `(kxj k)Sj . Then, the successful detection
xj ∈Φ\xi

probability in one mini-slot under strongest BS association
can be derived as follows:
!


[
Ps = Pr max SINRxi ≥ T = Pr
SINRi ≥ T
xi ∈Φ

(a)

= E

"

xi ∈Φ

#

X

1(SINRi ≥ T )

xi ∈Φ

Z
θBS
λ
Pr(SINRi ≥ T | r)dr
2π
R2
Z ∞
θUE θBS
=
λ Pr(SINRi ≥ T |Si = 1, r)Pr(Si = 1 | r)rdr
2π
0
Z ∞
α 2
2π
(c)
=
λ
LIxi (T rα )e−T r σ e−βr rdr ,
(8)
NBS NUE 0

(b)

=

where (a) follows from Lemma 1 in [14] 1 , (b) follows from
Campbell Mecke Theorem [15] and (c) follows the Rayleigh
fading assumption. The use of θUE and θBS λ/2π are due to BS
and UE beamwidth. Here LIxi (T rα ) is the Laplace transform
of the interference Ixi . Denote Rj as the distance from the jth
interfering BS to the typical UE, LIxi (T rα ) can be expressed
as:




LIxi (T rα ) = EΦ,hi exp −T rα


X

(a)

= E

Y

Pr[ne = n | C] = (1 − Ps )n−1 Ps .
Therefore, the average number of mini-slots for discovering
the UE is
Nc
X

Rj−α hj Sj 

n Pr(ne = n | C)

n=1

xj ∈Φ\xi



thus Pr(C) = 1 − Pf (Nc ). Denote ne as the number of minislots after which the typical UE can be detected. Since each BS
chooses a direction uniformly, we have the probability mass
function for ne > 0 as:




Ehj exp(−T rα Rj−α hj ) e−βRj + 1 − eβRj 

=

Nc
X
1
n(1 − Ps )n−1 Ps
1 − Pf n=1

=

1 − (Nc + 1)(1 − Ps )Nc + Nc (1 − Ps )Nc +1
.
(1 − Pf )Ps

xj ∈Φ\xi





T rα e−βRj 
Rjα + T rα
xj ∈Φ\xi


Z ∞
θBS
T rα e−βv
(c)
= exp −θUE
λb
vdv ,
2π
v α + T rα
0

(b)

= E

Y

1−

This is indeed the normalized expected cell-search latency.
(9)

where (a) follows that Sj is a Bernoulli random variable with
parameter e−βRi , (b) follows that hj is an exponential random
variable and (c) is derived from the probability generating
function of the PPP. Substituting (9) into (8) we obtain the
successful detection probability in one mini-slot. Thus the
detection failure probability after Nc mini-slots is (1 − Ps )Nc .
As we have shown in the numerical results, (1 − Ps )Nc is
very tight for realistic BS density values (e.g., more than 1
BS in every 10000 m2 ). For a very sparse BS deployment,
however, this equation is not valid as it implies Pf → 0 as
Nc → ∞ regardless of other parameters. To fix this problem,
we note that
Pf = lim Pf |mR =0 Pr(mR = 0) + Pf |mR >0 Pr(mR > 0)
R→∞
(a)

≥ lim Pr(mR = 0) = Pno-LoS ,
R→∞

Pf |mR =m is the failure probability given the existence of m
LoS BSs in B(0, R), and (a) follows from that Pf |mR =0 = 1
and that Pf |mR >0 Pr(mR > 0) ≥ 0 for any R > 0. This
completes the proof.
To elaborate on the lower-bound, by setting Nc → ∞,
channel fading cannot contribute to the failure probability
anymore. In this case, Pf (∞) is solely due to having no
close-enough LoS BS to the typical UE, which is Pno-LoS in
Lemma 1. In other words, Pf |mR >0 Pr(mR > 0) → 0 as
λ → 0 and Nc → ∞, making the lower-bound very tight,
asymptotically.
C. Proposition 2
Denfine event C as
C = {A UE can be detected within Nc mini-slots},
1 Note that Lemma 1 in [14] is based on T > 1 (0dB). It also provides a
tight upper bound until T = 0.4 (-4dB).

R EFERENCES
[1] T. S. Rappaport, S. Sun, R. Mayzus, H. Zhao, Y. Azar, K. Wang, G. N.
Wong, J. K. Schulz, M. Samimi, and F. Gutierrez, “Millimeter wave
mobile communications for 5G cellular: It will work!” IEEE Access,
vol. 1, pp. 335–349, 2013.
[2] H. Shokri-Ghadikolaei and C. Fischione, “The transitional behavior of
interference in millimeter wave networks and its impact on medium
access control,” IEEE Trans. Commun., vol. 62, no. 2, pp. 723–740,
Feb. 2016.
[3] C. N. Barati, S. A. Hosseini, M. Mezzavilla, T. Korakis, S. S. Panwar,
S. Rangan, and M. Zorzi, “Initial access in millimeter wave cellular
systems,” IEEE Trans. Wireless Commun., vol. 15, no. 12, pp. 7926–
7940, Dec. 2016.
[4] H. Shokri-Ghadikolaei, C. Fischione, G. Fodor, P. Popovski, and
M. Zorzi, “Millimeter wave cellular networks: A MAC layer perspective,” IEEE Trans. Commun., vol. 63, no. 10, pp. 3437–3458, Oct. 2015.
[5] Y. Li, J. G. Andrews, F. Baccelli, T. D. Novlan, and C. J. Zhang, “Design
and analysis of initial access in millimeter wave cellular networks,” IEEE
Trans. Wireless Commun., vol. 16, no. 10, pp. 6409–6425, Oct. 2017.
[6] Y. Li, F. Baccelli, J. G. Andrews, and J. C. Zhang, “Directional cell
search delay analysis for cellular networks with static users,” arXiv
preprint arXiv:1709.00779v1, 2017.
[7] G. Lee, Y. Sung, and M. Kountouris, “On the performance of random
beamforming in sparse millimeter wave channels,” IEEE J. Sel. Topics
Signal Process., vol. 10, no. 3, pp. 560–575, Apr. 2016.
[8] Z. Abu-Shaban, H. Wymeersch, X. Zhou, G. Seco-Granados, and T. Abhayapala, “Random-phase beamforming for initial access in millimeterwave cellular networks,” in Proc. IEEE Global Communications Conf.
(GLOBECOM), Dec. 2016, pp. 1–6.
[9] M. Haenggi, Stochastic geometry for wireless networks. Cambridge
University Press, 2012.
[10] T. Bai, R. Vaze, and R. Heath, “Analysis of blockage effects on urban
cellular networks,” IEEE Trans. Wireless Commun., vol. 13, no. 9, pp.
5070–5083, Sept. 2014.
[11] J. Park, S. L. Kim, and J. Zander, “Tractable resource management
with uplink decoupled millimeter-wave overlay in ultra-dense cellular
networks,” IEEE Trans. Wireless Commun., vol. 15, no. 6, pp. 4362–
4379, Jun. 2016.
[12] H. Shokri-Ghadikolaei, C. Fischione, and E. Modiano, “Interference
model similarity index and its applications to mmWave networks,” IEEE
Trans. Wireless Commun., to be published.
[13] M. Giordani, M. Mezzavilla, and M. Zorzi, “Initial access in 5G
mmwave cellular networks,” IEEE Commun. Mag., vol. 54, no. 11, pp.
40–47, Nov. 2016.
[14] H. S. Dhillon, R. K. Ganti, F. Baccelli, and J. G. Andrews, “Modeling
and analysis of k-tier downlink heterogeneous cellular networks,” IEEE
J. Sel. Areas Commun., vol. 30, no. 3, pp. 550–560, Apr. 2012.
[15] S. N. Chiu, D. Stoyan, W. S. Kendall, and J. Mecke, Stochastic geometry
and its applications. John Wiley & Sons, 2013.

