.png){kind=icon}
.png){kind=icon}
Return
Resilient Service Provisioning for Edge Computing
.png){kind=icon}
PRE
AI
DOI：10.1109/JIOT.2021.3078620.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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. First, for the general problem, we propose a two-step greedy algorithm achieving a constant approximation ratio within polynomial time. Second, 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:
Resilience
Approximation algorithms
Servers
Schedules
Optimization
Linear programming
Edge computing
resiliency
service provisioning
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
8.9
Papers:
1.4W
Citations:
7.8W
View more organizations