Computationally Efficient Optimal Millimeter Wave Base Station Deployment

Millimeter wave (mmWave) communication is a key technology to provide ultra-fast data rates and massive connectivity in wireless networks. This paper introduces a computationaland cost-efficient approach for deploying mmWave base stations (BSs) in urban environments. In addition to the physical blockage constraints that have been considered in various existing studies, we also account for the capacity constraints of mmWave BSs, which limit the maximum number of concurrent user requests. To address the inherently stochastic nature of mobile user traffic, we utilize teletraffic theory and specifically apply the Erlang Fixed-Point Approximation to accurately and efficiently estimate blocking probabilities. Then, we propose a low-complexity algorithm by identifying the submodularity structure of the deployment problem to determine the optimal deployment strategy that minimizes the number of BSs. Extensive numerical results demonstrate that our method outperforms existing approaches in both solution accuracy and computational efficiency.