Optimal computing node placement in fog-enabled networks

doi:10.7523/j.ucas.2020.0028

Abstract

Abstract: Fog computing is a promising solution to enable computation-intensive and latencycritical applications in Internet of Things (IoT). Considering that the placement of computing nodes (CNs) directly affect the task offloading performance, this paper addresses the optimal CN placement problem in a fog-enabled network. By jointly considering the communication and computing abilities of CNs, the problem is formulated as a p-center problem, which is NP-hard. To solve such a problem, we first give a lower bound on the number of required CNs and then propose two efficient heuristic algorithms to place the CNs with low complexity. Numerical results verify the advantages of the proposed algorithms.

Key words: fog computing, Internet of Things, task offloading, computing node placement, convexhull

CLC Number:

TN913

LI Xuanfeng, LUO Xiliang. Optimal computing node placement in fog-enabled networks[J]. Journal of University of Chinese Academy of Sciences, 2022, 39(2): 260-266.

References

[1] Chiang M, Zhang T. Fog and IoT: an overview of research opportunities[J]. IEEE Internet of Things Journal, 2016, 3(6):854-864.DOI:10.1109/JIOT.2016.2584538.
[2] You C S, Huang K B, Chae H, et al. Energy-efficient resource allocation for mobile-edge computation offloading[J]. IEEE Transactions on Wireless Communications, 2017, 16(3):1397-1411.DOI:10.1109/TWC.2016.2633522.
[3] Dinh T Q, Tang J H, La Q D, et al. Offloading in mobile edge computing: task allocation and computational frequency scaling[J]. IEEE Transactions on Communications, 2017, 65(8):3571-3584.DOI:10.1109/TCOMM.2017.2699660.
[4] Yang Y, Wang K L, Zhang G W, et al. MEETS: maximal energy efficient task scheduling in homogeneous fog networks[J]. IEEE Internet of Things Journal, 2018, 5(5): 4076-4087.DOI:10.1109/JIOT.2018.2846644.
[5] Mao Y Y, Zhang J, Song S H, et al. Stochastic joint radio and computational resource management for multi-user mobile-edge computing systems[J]. IEEE Transactions on Wireless Communications, 2017, 16(9):5994-6009.DOI:10.1109/TWC.2017.2717986.
[6] Yang Y, Zhao S, Zhang W X, et al. DEBTS: delay energy balanced task scheduling in homogeneous fog networks[J]. IEEE Internet of Things Journal, 2018, 5(3): 2094-2106.DOI:10.1109/JIOT.2018.2823000.
[7] Pu L J, Chen X, Xu J D, et al. D2D fogging: an energy-efficient and incentive-aware task offloading framework via network-assisted D2D collaboration[J]. IEEE Journal on Selected Areas in Communications, 2016, 34(12): 3887-3901.DOI:10.1109/JSAC.2016.2624118.
[8] Zhu Z W, Liu T, Yang Y, et al. BLOT: bandit learning-based offloading of tasks in fog-enabled networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2019, 30(12): 2636-2649.DOI:10.1109/TPDS.2019.2927978.
[9] Yang F Q, Zhu Z W, Zhao S S, et al. Optimal task offloading in fog-enabled networks via index policies[C]//2018 IEEE Global Conference on Signal and Information Processing (GlobalSIP). November 26-29, 2018, Anaheim, CA, USA. IEEE, 2018: 688-692.DOI:10.1109/GlobalSIP.2018.8646376.
[10] Mozaffari M, Saad W, Bennis M, et al. Efficient deployment of multiple unmanned aerial vehicles for optimal wireless coverage[J]. IEEE Communications Letters, 2016, 20(8):1647-1650.DOI:10.1109/LCOMM.2016.2578312.
[11] Lyu J B, Zeng Y, Zhang R, et al. Placement optimization of UAV-mounted mobile base stations[J]. IEEE Communications Letters, 2017, 21(3):604-607.DOI:10.1109/LCOMM.2016.2633248.
[12] Alzenad M, El-Keyi A, Lagum F, et al. 3-D placement of an unmanned aerial vehicle base station (UAV-BS) for energy-efficient maximal coverage[J]. IEEE Wireless Communications Letters, 2017, 6(4): 434-437.DOI:10.1109/LWC.2017.2700840.
[13] Maiti P, Shukla J, Sahoo B, et al. QoS-aware fog nodes placement[C]//2018 4th International Conference on Recent Advances in Information Technology (RAIT). March 15-17, 2018, Dhanbad, India. IEEE, 2018: 1-6.DOI:10.1109/RAIT.2018.8389043.
[14] Bonomi F, Milito R, Zhu J, et al. Fog computing and its role in the internet of things[C]//MCC′12: Proceedings of the first edition of the MCC workshop on Mobile cloud computing. 2012: 13-16.DOI:10.1145/2342509.2342513.
[15] Zhang H Q, Xiao Y, Bu S R, et al. Computing resource allocation in three-tier IoT fog networks: a joint optimization approach combining Stackelberg game and matching[J]. IEEE Internet of Things Journal, 2017, 4(5): 1204-1215.DOI:10.1109/JIOT.2017.2688925.
[16] Li K Q. A game theoretic approach to computation offloading strategy optimization for non-cooperative users in mobile edge computing[J]. IEEE Transactions on Sustainable Computing, 2018. DOI: 10.1109/TSUSC.2018.2868655.
[17] Kumar K, Lu Y H. Cloud computing for mobile users: Can offloading computation save energy?[J]. Computer, 2010, 43(4): 51-56.DOI:10.1109/mc.2010.98.
[18] Jain A K, Murty M N, Flynn P J. Data clustering: a review[J]. ACM Computing Surveys, 1999, 31(3): 264-323.DOI:10.1145/331499.331504.
[19] Welzl E. Smallest enclosing disks (balls and ellipsoids)[M]// Maurer H. New results and new trends in computer science. Springer/Berlin Heidelberg, Springer-Verlag, 1991: 359-370.DOI:10.1007/bfb0038202.
[20] Ghosh S, Dubey S K. Comparative analysis of k-means and fuzzy c-means algorithms[J]. International Journal of Advanced Computer Science and Applications, 2013, 4(4): 35-39.DOI:10.14569/ijacsa.2013.040406.