HR-kESP: A Heuristic Algorithm for Robustness-Oriented k Edge Server Placement

Mobile edge computing develops a new paradigm to deliver low-latency services to mobile users by deploying edge servers at base stations or access points close to the users. From the perspective of service providers, in this paper, we consider how to deploy k edge servers on suitable base stations to maximize network robustness and user coverage. Accordingly, the above two metrics are focused on constructing an optimization model for deploying a given number (i.e., k) of edge servers in the edge computing network. In order to solve the model efficiently, a Heuristic algorithm for Robustness-oriented k Edge Server Placement (HR-kESP) is designed. In the proposed algorithm, the initial base station is first selected in a greedy manner. Then, a heuristic policy by considering the increment of network robustness is designed to gradually expand the deployment solution until the server budget constraint is satisfied. The comparison experiments have been conducted on a public dataset, showing that our HR-kESP algorithm achieves a better optimization effect than the other four benchmark algorithms in most cases.