TY - JOUR
T1 - Towards cost-efficient resource provisioning with multiple mobile users in fog computing
AU - Lu, Shuaibing
AU - Wu, Jie
AU - Duan, Yubin
AU - Wang, Ning
AU - Fang, Juan
N1 - Funding Information:
This work of the first author was done during her stay as a visitor scholar at Temple University. This research was supported in part by National Natural Science Foundation of China 61202076 , Beijing Natural Science Foundation, China 4192007 , and NSF grants CNS 1757533 , CNS 1629746 , CNS 1564128 , CNS 1449860 , CNS 1461932 , CNS 1460971 , and IIP 1439672 .
Funding Information:
This work of the first author was done during her stay as a visitor scholar at Temple University. This research was supported in part by National Natural Science Foundation of China61202076, Beijing Natural Science Foundation, China4192007, and NSF grants CNS 1757533, CNS 1629746, CNS 1564128, CNS 1449860, CNS 1461932, CNS 1460971, and IIP 1439672.
Funding Information:
Shuaibing Lu is currently a lecture of Faculty of Information Technology of Beijing University of Technology. She received her Ph.D. degree in Computer Science and Technology from Jilin University, Changchun, in 2019. She is supported by the China Scholarship Council as a visiting scholar supervised by Prof. Jie Wu in the Department of Computer and Information Sciences at Temple University (2016–2018). She is a member of IEEE. Her current research focuses on distributed computing, cloud computing and fog computing.
Publisher Copyright:
© 2020 Elsevier Inc.
PY - 2020/12
Y1 - 2020/12
N2 - Fog computing is an emerging paradigm that brings computing capabilities closer to distributed IoT devices, which provides networking services between end devices and traditional cloud data centers. One important mission is to further reduce the monetary cost of fog resources while meeting the ever-growing demands of multiple users. In this paper, we focus on minimizing the total cost for multiple mobile users to provide an efficient resource provisioning scheme in fog computing. The total cost includes two aspects: the replication cost and the transmission cost. We consider three cases for the resource provision problem by focusing on different cost models. First, one simple case where users can only upload one replication is discussed, and an optimal solution is proposed by converting the original problem into a bipartite graph matching. Then we consider a more complicated case in which each user can upload multiple replications on fog nodes in the resource provisioning. Specifically, two models are discussed: the 0–1 transmission cost model and the different transmission cost model. For the 0–1 transmission cost model, each user can upload multiple replications with a constant transmission cost, and one optimal greedy solution is proposed. For the different transmission cost model, the transmission cost is related to the distance of each pair of fog nodes. This problem is proven to be NP-hard. We first propose a non-adaptive algorithm which is proved to be bounded by [Formula presented]. Another 3+ϵ-approximation algorithm is proposed based on local search, which has better performance with higher complexity. Extensive simulations also prove the efficiency of our schemes.
AB - Fog computing is an emerging paradigm that brings computing capabilities closer to distributed IoT devices, which provides networking services between end devices and traditional cloud data centers. One important mission is to further reduce the monetary cost of fog resources while meeting the ever-growing demands of multiple users. In this paper, we focus on minimizing the total cost for multiple mobile users to provide an efficient resource provisioning scheme in fog computing. The total cost includes two aspects: the replication cost and the transmission cost. We consider three cases for the resource provision problem by focusing on different cost models. First, one simple case where users can only upload one replication is discussed, and an optimal solution is proposed by converting the original problem into a bipartite graph matching. Then we consider a more complicated case in which each user can upload multiple replications on fog nodes in the resource provisioning. Specifically, two models are discussed: the 0–1 transmission cost model and the different transmission cost model. For the 0–1 transmission cost model, each user can upload multiple replications with a constant transmission cost, and one optimal greedy solution is proposed. For the different transmission cost model, the transmission cost is related to the distance of each pair of fog nodes. This problem is proven to be NP-hard. We first propose a non-adaptive algorithm which is proved to be bounded by [Formula presented]. Another 3+ϵ-approximation algorithm is proposed based on local search, which has better performance with higher complexity. Extensive simulations also prove the efficiency of our schemes.
UR - http://www.scopus.com/inward/record.url?scp=85089733152&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85089733152&partnerID=8YFLogxK
U2 - 10.1016/j.jpdc.2020.08.002
DO - 10.1016/j.jpdc.2020.08.002
M3 - Article
AN - SCOPUS:85089733152
SN - 0743-7315
VL - 146
SP - 96
EP - 106
JO - Journal of Parallel and Distributed Computing
JF - Journal of Parallel and Distributed Computing
ER -