Optimal Transmitter Placement in Realistic Urban Environments

In a wireless network, the spatial location of the transmitters has a large impact on the achievable rate at each user location. The optimal placement of -- for example -- cellular base stations is a difficult non-convex problem, and is usually addressed with simplified propagation models and simplified heuristics that may account for specifics such as the site topology, building locations, and user density. We propose a mathematically rigorous framework for optimal transmitter placement that explicitly integrates detailed site-specific maps, spatial material properties, and realistic signal attenuation. We introduce a novel aggregated network quality functional which captures the essential trade-off between maximizing network coverage and minimizing cost, and establish the problem's sub-modularity under certain practical conditions. To solve the resulting resource-constrained optimization problem for sparse, discrete transmitter configurations, we propose the Interference-Aware Submodular Placement Algorithm (IA-SPA) and prove theoretical performance guarantees on its gap from optimality. IA-SPA is general and can incorporate existing BS locations and prohibited areas (e.g. a lake), making it useful for either clean-slate or incremental deployments. We show the utility of our approach using a ray tracing-based simulation framework applied to 3D maps of San Francisco and Florence, where we compare to known base station deployments by AT&T, T-Mobile and Iliad. We demonstrate that our proposed placement strategy achieves significant increases in mean data rate (about 2x) and edge rate ($2-8$x) compared to existing tower deployments, using the same number of transmitters.