雾计算是实现物联网中的计算密集型和时延关键型应用一种很有前景的解决方案。考虑到计算节点的布局会直接影响雾计算网络中任务卸载的性能，旨在解决雾计算网络中计算节点的最优布局问题。通过同时考虑计算节点的通信覆盖和计算能力，该问题可以建模为一个NP难的p中心问题。为解决这个问题，首先给出所需布局的计算节点数量的下界，然后提出2种有效的启发式算法以较低的复杂度对计算节点进行布局。数值结果验证了所提算法的性能和优点。
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.
[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.
