Robustness-oriented k Edge Server Placement

Mobile Edge Computing (MEC) is an emerging and prospective computing paradigm that supports low-latency content delivery. In a MEC environment, edge servers are attached to base stations or access points in closer proximity to end-users to reduce the end-to-end latency in their access to online content. From an edge infrastructure provider's perspective, a cost-effective k edge server placement (kESP) places k edge servers within a particular geographic area to maximize their coverage. However, in the distributed MEC environment, edge servers are often subject to failures due to various reasons, e.g., software exceptions, hardware faults, cyberattacks, etc. End-users connected to a failed edge server have to access online content from the remote cloud if they are not covered by any other edge servers. This significantly jeopardizes end-users' quality of experience. Thus, the robustness of an edge server network must be considered in edge server placement. In this paper, we formally model this Robustness-oriented k Edge Server Placement (RkESP) problem, and prove that finding the optimal solution to this problem is NP-hard. Thus, we firstly propose an integer programming based optimal approach, namely Opt, to find optimal solutions to small-scale RkESP problems. Then, we propose an approximate approach, namely Approx, for solving large-scale RkESP problems efficiently with an O(k)-approximation ratio. Finally, the performance of the two approaches is experimentally evaluated against five state-of-the-art approaches on a real-world dataset and a large-scale synthesized dataset.