雾计算网络中计算节点的最优布局

doi:10.7523/j.ucas.2020.0028

中国科学院大学学报 ›› 2022, Vol. 39 ›› Issue (2): 260-266.DOI: 10.7523/j.ucas.2020.0028

• 电子信息与计算机科学 • 上一篇

雾计算网络中计算节点的最优布局

李炫锋^1,2,3, 罗喜良¹

1 上海科技大学信息科学与技术学院, 上海 201210;
2 中国科学院上海微系统与信息技术研究所, 上海 200050;
3 中国科学院大学, 北京 100049

收稿日期:2020-03-26 修回日期:2020-05-05 发布日期:2021-06-01
通讯作者: 罗喜良
基金资助:
国家自然科学基金（61971286）资助

Optimal computing node placement in fog-enabled networks

LI Xuanfeng^1,2,3, LUO Xiliang¹

1 School of Information Science and Technology, ShanghaiTech University, Shanghai 201210, China;
2 Shanghai Institute of Microsystem & Information Technology, Chinese Academy of Sciences, Shanghai 200050, China;
3 University of Chinese Academy of Sciences, Beijing 100049, China

Received:2020-03-26 Revised:2020-05-05 Published:2021-06-01

摘要/Abstract

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

关键词: 雾计算, 物联网, 任务卸载, 计算节点布局, 凸包

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

中图分类号:

TN913

李炫锋, 罗喜良. 雾计算网络中计算节点的最优布局[J]. 中国科学院大学学报, 2022, 39(2): 260-266.

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.

参考文献

[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.

雾计算网络中计算节点的最优布局

Optimal computing node placement in fog-enabled networks

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 6

编辑推荐

Metrics

本文评价

访问统计

联系我们

[1]	戴志明, 周明拓, 杨旸, 李剑, 刘军. 智能工厂中的雾计算资源调度[J]. 中国科学院大学学报, 2021, 38(5): 702-711.
[2]	沈国锋, 周明拓, 李剑, 王华俊, 李凯, 杨旸. 雾计算使能的移动机器人编队跟随研究与设计[J]. 中国科学院大学学报, 2021, 38(4): 557-566.
[3]	谭友钰, 陈蕾, 周明拓, 王昆仑, 杨旸, 张武雄. 动态雾计算网络中基于在线学习的任务卸载算法[J]. 中国科学院大学学报, 2020, 37(5): 688-698.
[4]	朱兆伟, 刘婷, 钱骅, 罗喜良. 非稳态雾赋能网络中的在线任务卸载方法[J]. 中国科学院大学学报, 2020, 37(5): 699-707.
[5]	金叶奇, 郑敏, 谭冲, 刘洪. 面向蜂窝物联网的RB动态预分配调度方案[J]. 中国科学院大学学报, 2019, 36(6): 825-831.
[6]	马晓辉, 林凤鸣, 申立勇. 平面Bézier曲线细分算法的参数优化[J]. 中国科学院大学学报, 2016, 33(3): 311-316.