A Hybrid metaheuristic Algorithm for Edge Site Deployment with User Coverage Maximization and Cost Minimization

Recent years, edge computing has been getting increased attention due to its ultra-low delay service deliveries. Plenty of works have focused on the performance improvement of edge computing by e.g., edge server deployment, edge caching, and task offloading. While, there is a lack of work on improving the investment cost for building or upgrading the edge site deployment by making a decision on which places edge sites are deployed. In this paper, we focus on the edge site deployment problem (ESDP) to maximize user coverage with fewest edge sites. We first formulate ESDP into a binary nonlinear programming with two optimization objectives of user coverage maximization and edge site minimization, and prove that ESDP is NP-complete. Then, we propose a hybrid metaheuristic algorithm to solve ESDP with polynomial time complexity, which combining the crossover and mutation operators of genetic algorithm with self-and social-cognition of particle swarm optimization. At last, we conduct extensive simulated experiment based on a real data set to evaluate the performance of our proposed algorithm. The results show that our algorithm achieves 100% user coverage with much fewer edge sites than other seven metaheuristic algorithms, and has a good scalability.

@article{Xing2023,
  title     = {A Hybrid metaheuristic Algorithm for Edge Site Deployment with User Coverage Maximization and Cost Minimization},
  journal   = {International Journal of Advanced Computer Science and Applications},
  volume    = {14},
  number    = {10},
  year      = {2023},
  publisher = {The Science and Information Organization},
  author    = {Xiaodong Xing and Ying Song and Bo Wang},
  doi       = {10.14569/IJACSA.2023.01410100},
  url       = {https://doi.org/10.14569/IJACSA.2023.01410100}
}