Two-Stage Robust Edge Service Placement and Sizing under Demand Uncertainty

Edge computing has emerged as a key technology to reduce network traffic, improve user experience, and enable numerous Internet of Things applications. In this article, we study an optimal resource procurement problem for a service provider (SP), who can purchase resources from various edge nodes in the edge computing market to serve its users' requests. How to jointly optimize the service placement, resource sizing, and workload allocation decisions is a challenging problem, which becomes even more complicated when considering demand uncertainty. To this end, we propose a novel two-stage adaptive robust optimization framework to help the SP optimally determine the locations for installing its service (i.e., placement) and the amount of computing resource to purchase from each location (i.e., sizing). The proposed placement and sizing solution can hedge against any possible realization within a predefined demand uncertainty set. Given the first-stage robust solution, the optimal resource and workload allocation decisions are computed in the second stage after the uncertainty is revealed. To solve the two-stage model, this article presents an iterative solution approach by employing the column-and-constraint generation method that decomposes the underlying problem into a master problem and a max-min subproblem associated with the second stage. Extensive numerical results are shown to illustrate the efficacy of the proposed model.