A Multistart Power of d Choices Strategy for Edge Server Placement Problem

Edge computing systems have become increasingly important in recent years due to the exponential growth of data generated by the Internet of Things (IoT) and other connected devices. The placement of edge servers in edge computing systems plays a crucial role in optimizing performance and enhancing user experience. This paper addresses the edge server placement (ESP) problem and its implications for efficient and scalable mobile edge computing. The problem aims to determine the optimal locations for deploying edge servers that maximize performance and minimize access delay. The paper introduces the multistart power of d choices algorithm, named MPdC, which combines multistart procedure and greedy-randomized technique to solve the ESP problem. The algorithm consists of two phases. The first phase generates a solution using an adaptive greedy-randomized technique with the aim of minimizing a predefined objective. In the second phase, the adaptive greedy-randomized algorithm is embedded in a multistart framework in which the best solution over all iterations is reported as the final solution for the problem. Performance evaluation is conducted using a real dataset from Shanghai Telecom, consisting of Internet access requests through base stations. The proposed algorithm is evaluated by comparing its performance to that of baseline methods, in terms of load balancing and average distance. The experimental results indicate that the proposed algorithm achieves better performance in the case of d=16. Also, it can be observed that selecting the average distance as the objective function in the proposed algorithm is a better criterion.