Han Fang, Fu Hui, Wang Bo, Xu Yaoli, Lv Bin
Huanghe Science and Technology University, Zhengzhou, China.
Software Engineering College, Zhengzhou University of Light Industry, Zhengzhou, China.
PeerJ Comput Sci. 2024 Oct 25;10:e2439. doi: 10.7717/peerj-cs.2439. eCollection 2024.
Edge computing has attracted wide attention due to its ultra-low latency services, as well as the prevalence of smart devices and intelligent applications. Edge server placement (ESP) is one of the key issues needed to be addressed for effective and efficient request processing, by deciding which edge stations to equip with limited edge resources. Due to NP-hardness of ESP, some works have designed meta-heuristic algorithms for solving it. While these algorithms either exploited only one kind of meta-heuristic search strategies or separately perform two different meta-heuristic algorithms. This can result in limit performance of ESP solutions due to the "No Free Lunch" theorem. In addition, existing algorithms ignored the computing delay of edge servers (ESs) on request process, resulting in overestimation of the service quality. To address these issues, in this article, we first formulate ESP problem with the objective of minimizing the overall response time, considering heterogeneous edge servers with various service capacity. Then, to search effective or even the best ESP solutions, we propose a hybrid meta-heuristic algorithm (named GP4ESP) by taking advantage of both the powerful global search ability of genetic algorithm (GA) and the fast convergence of particle swarm optimization (PSO). GP4ESP effectively fuses the merits of GA and PS by integrating the swarm cognition of PSO into the evolutionary strategy of GA. At last, we conducted extensive simulation experiments to evaluate the performance of GP4ESP, and results show that GP4ESP achieves 18.2%-20.7% shorter overall response time, compared with eleven up-to-date ESP solving algorithms, and the performance improvement is stable as the scale of ESP is varied.
边缘计算因其超低延迟服务以及智能设备和智能应用的普及而备受关注。边缘服务器放置（ESP）是有效且高效地处理请求所需解决的关键问题之一，它通过决定在哪些边缘站点配备有限的边缘资源来实现。由于ESP问题具有NP难性质，一些研究工作设计了元启发式算法来解决它。然而，这些算法要么仅采用一种元启发式搜索策略，要么分别执行两种不同的元启发式算法。根据“没有免费的午餐”定理，这可能导致ESP解决方案的性能受限。此外，现有算法在请求处理过程中忽略了边缘服务器（ES）的计算延迟，导致对服务质量的高估。为了解决这些问题，在本文中，我们首先考虑具有不同服务能力的异构边缘服务器，以最小化整体响应时间为目标来构建ESP问题。然后，为了搜索有效的甚至是最佳的ESP解决方案，我们利用遗传算法（GA）强大的全局搜索能力和粒子群优化（PSO）的快速收敛性，提出了一种混合元启发式算法（名为GP4ESP）。GP4ESP通过将PSO的群体认知融入GA的进化策略，有效地融合了GA和PSO的优点。最后，我们进行了广泛的模拟实验来评估GP4ESP的性能，结果表明，与十一种最新的ESP求解算法相比，GP4ESP的整体响应时间缩短了18.2% - 20.7%，并且随着ESP规模的变化，性能提升稳定。
