  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.
