欢迎访问中国科学院大学学报,今天是

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

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

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

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

  1. 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 Xuanfeng1,2,3, LUO Xiliang1   

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

摘要: 雾计算是实现物联网中的计算密集型和时延关键型应用一种很有前景的解决方案。考虑到计算节点的布局会直接影响雾计算网络中任务卸载的性能,旨在解决雾计算网络中计算节点的最优布局问题。通过同时考虑计算节点的通信覆盖和计算能力,该问题可以建模为一个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

中图分类号: