Research Area:  Edge Computing

Abstract:

We study the problem of Resilient Service Provisioning for Edge computing (RSPE), i.e., how to determine a service placement strategy to maximize the expected overall utility by service provisioning, in the presence of uncertain service failures. RSPE is extremely challenging to tackle, because the explicit expression of its objective function is difficult to obtain, and it is a resilient max-min problem subject to knapsack constraints, which is unexplored so far and cannot be addressed by existing resilient optimization techniques. We first explore the potential properties of the implicit objective function, and reveal that it is monotone submodular under certain conditions. We further prove that the knapsack constraints form a q-independence system constraint, where q>0 is a constant related to the constraints. We propose two novel solutions for the general RSPE and homogeneous case, respectively. Firstly, for the general problem, we propose a “two-step greedy” algorithm achieving constant approximation ratio within polynomial time. Secondly, for the homogeneous case where one of the knapsack constraints reduces to a matroid constraint, we propose an improved “first-greedy-then-local search” polynomial time algorithm achieving better approximation ratio than the previous one. Both extensive simulations and field experiments validate the effectiveness of our proposed algorithms.

Keywords:  
Edge computing
service provisioning
resiliency.

Author(s) Name:   Yuben Qu; Dongyu Lu; Haipeng Dai; Haisheng Tan; Shaojie Tang; Fan Wu; Chao Dong

Publisher name:  IEEE

DOI:  10.1109/JIOT.2021.3078620

Volume Information:   Page(s): 1 - 1

Paper Link:   https://ieeexplore.ieee.org/abstract/document/9446963