A Two-Phase Optimization for Radio Base Station Deployment in Heterogeneous Networks

This paper introduces a two-stage optimization framework for base station placement in heterogeneous networks, addressing the dual challenge of maximizing network quality while achieving cost-effective deployment. The initial stage leverages Binary Integer Programming (BIP) on a discretized hexagonal grid to find the least expensive combination of macro and micro stations that guarantees full coverage. This BIP formulation ensures cost optimality for the defined discrete problem, surpassing conventional heuristic approaches. The second stage employs Differential Evolution (DE), a meta-heuristic, to refine these positions using continuous coordinates, maximizing the network-wide Signal-to-Interference-plus-Noise Ratio (SINR) while coverage is enforced via a penalty-based objective function. This decomposition facilitates a more scalable approach, yielding high-quality solutions where the first stage guarantees full coverage, while the second stage employs an adjustable penalty function to allow for maintaining this coverage during refinement. Although the general problem is NP-hard, the two-stage approach effectively tackles complexity, leading to superior solutions compared to competing methods, primarily by combining the guarantee of cost optimality in the first phase with the continuous refinement of network quality in the second.