  Millimeter-wave (mmWave) communications rely on directional transmissions to
overcome severe path loss. Nevertheless, the use of narrow beams complicates
the initial access procedure and increase the latency as the transmitter and
receiver beams should be aligned for a proper link establishment. In this
paper, we investigate the feasibility of random beamforming for the cell-search
phase of initial access. We develop a stochastic geometry framework to analyze
the performance in terms of detection failure probability and expected latency
of initial access as well as total data transmission. Meanwhile, we compare our
scheme with the widely used exhaustive search and iterative search schemes, in
both control plane and data plane. Our numerical results show that, compared to
the other two schemes, random beamforming can substantially reduce the latency
of initial access with comparable failure probability in dense networks. We
show that the gain of the random beamforming is more prominent in light
traffics and low-latency services. Our work demonstrates that developing
complex cell-discovery algorithms may be unnecessary in dense mmWave networks
and thus shed new lights on mmWave network design.
