Budget-Constrained Edge Server Expansion Deployment via Genetic Algorithm and Particle Swarm Optimization

Mobile edge computing enhances the performance of low-capability end devices by offloading tasks to nearby edge servers, enabling timely responses for delay-sensitive, computation-intensive tasks. However, the rapid and continuous growth of such tasks may soon exceed the capacity of the initially deployed edge server system. This calls for deploying new servers while re-using deployed ones for saving investment, leading to the emergence of a novel paradigm named as Edge Server Expansion Deployment (ESED) here. For this ESED paradigm, aiming to simultaneously minimize the average access delay between end devices and edge servers and the workload deviation among servers, we studied the Budget-Constrained ESED (BC-ESED) problem under the condition of a specified budget constraint. We formulate the problem as a multi-objective optimization problem and prove its NP-hardness. We then propose an algorithm, by combining Genetic Algorithm (GA) and Particle Swarm Optimization (PSO), named GA-PSO. GA-PSO utilizes a four-step iteration framework of selection, crossover, mutation, and correction, where a novel three-party globalbest-localbest-individual crossover operation, inspired by PSO, complements the traditional two-party crossover operation in the crossover step. The convergence and time complexity of GA-PSO are established and analyzed. Simulation results, based on realistic network topologies and workload data from the Shanghai Telecom base station dataset, demonstrate that GA-PSO outperforms other benchmark algorithms in terms of average access delay and workload deviation.