TY - GEN
T1 - Cost-efficient resource provision for multiple mobile users in fog computing
AU - Lu, Shuaibing
AU - Wu, Jie
AU - Duan, Yubin
AU - Wang, Ning
AU - Fang, Juan
N1 - Funding Information:
ACKNOWLEDGEMENT This research was supported in part by Beijing Natural Science Foundation 4192007, and NSF grants CNS 1757533, CNS 1629746, CNS 1564128, CNS 1449860, CNS 1461932, CNS 1460971, and IIP 1439672.
Publisher Copyright:
© 2019 IEEE.
PY - 2019/12
Y1 - 2019/12
N2 - Fog computing is an emerging paradigm that brings the computing capabilities close 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 demand 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 two 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 one of bipartite graph matching. Then we consider a more complicated case that each user can upload multiple replications on fog nodes in the resource provisioning. For different transmission cost models, 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 2/3W+1/3OPT. 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 the computing capabilities close 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 demand 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 two 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 one of bipartite graph matching. Then we consider a more complicated case that each user can upload multiple replications on fog nodes in the resource provisioning. For different transmission cost models, 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 2/3W+1/3OPT. 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=85078914547&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85078914547&partnerID=8YFLogxK
U2 - 10.1109/ICPADS47876.2019.00067
DO - 10.1109/ICPADS47876.2019.00067
M3 - Conference contribution
AN - SCOPUS:85078914547
T3 - Proceedings of the International Conference on Parallel and Distributed Systems - ICPADS
SP - 422
EP - 429
BT - Proceedings - 2019 IEEE 25th International Conference on Parallel and Distributed Systems, ICPADS 2019
PB - IEEE Computer Society
T2 - 25th IEEE International Conference on Parallel and Distributed Systems, ICPADS 2019
Y2 - 4 December 2019 through 6 December 2019
ER -