Trading off between user coverage and network robustness for edge server placement

Edge Cloud Computing (ECC) provides a new paradigm for app vendors to serve their users with low latency by deploying their services on edge servers in close proximity to mobile users. From the edge infrastructure provider's perspective, a cost-effective k-edge server placement aims to place k-edge servers within a particular geographic area to maximize the number of covered mobile users (i.e., user coverage). However, in the distributed and volatile ECC environment, edge servers are subject to failures due to various reasons, e.g., software exceptions, hardware faults, cyberattacks, etc. Users connected to a failed edge server have to access services in the remote cloud if they are not covered by any other edge servers. This significantly impacts users quality of experience. Thus, the robustness of the edge server network (i.e., network robustness) must be considered. In this paper, we formally model this joint user coverage and network robustness oriented k-edge server placement (kESP-CR) problem, and prove that finding the optimal solution to this problem is NP-hard. To tackle this kESP-CR problem, we propose an integer programming-based optimal approach for the small-scale kESP-CR problems and approximation approach for the large-scale kESP-CR problem. Finally, extensive experiments are conducted to evaluate their performance.