Cost-Efficient Resource Provisioning in Delay-Sensitive Cooperative Fog Computing

Recently, fog computing has become a highly virtualized platform that provides computation, storage, and networking services between end devices and traditional cloud data centers. In this paper, we address the resource provision (RP)problem for delay-sensitive users in cooperative fog computing. Our objective is to find a feasible provision scheme that minimizes the total monetary cost proportional to the number of fog nodes for network operators under the deadline and capacity constraints by considering the cooperation of fog nodes. We consider two cases of our RP problem: the Unlimited-Processor Fog Nodes (UPFN)case and the Limited-Processor Fog Nodes (LPFN)case. For the UPFN case, each fog node has unlimited processors. The requests on each fog node can be processed in parallel ideally, i.e. with no scheduling delay. The LPFN case corresponds to a more realistic scenario where the scheduling delay is non-eligible. In either case, our RP problem is proven to be NP-hard. For the UPFN case, we propose two greedy algorithms which iteratively remove fog nodes according to their global or local cooperative influences until there is no feasible provision that can guarantee users' deadlines. For the LPFN case, it is not trivial to check the existence of a feasible provision due to the interactive influence on the scheduling delay for requests. We find a near-optimal solution with bound $\frac{8}{3}OPT+\frac{\epsilon^{2}}{8m\alpha}$ using the continuous congestion game and check the feasibility, where $m$ is the number of fog nodes and $\alpha$ is a constant value related to the delay function. Extensive simulations demonstrate the efficiency of our schemes.