In this paper, we address the edge station deployment problem (ESDP), which aims to determine optimal sites for deploying edge stations so as to maximize user coverage and minimize deployment cost. We first formulate the ESDP as a binary linear programming model and prove its NP-hardness by reducing the set covering problem to a specialized instance of ESDP. To solve the ESDP in polynomial time, we propose a novel heuristic algorithm that prioritizes covering users who are within range of the fewest candidate sites. Our algorithm iteratively selects the site that can cover the most users from among the candidate sites capable of covering those least-covered users. To evaluate the performance of our algorithm, we conduct simulation experiments based on a real-world dataset. Experimental results demonstrate that our algorithm achieves 100% user coverage with lower deployment cost compared to several classical and state-of-the-art algorithms.
Shao et al. (Thu,) studied this question.