﻿ 雾计算网络中计算节点的最优布局
 中国科学院大学学报  2022, Vol. 39 Issue (2): 260-266 PDF

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

Optimal computing node placement in fog-enabled networks
LI Xuanfeng1,2,3, LUO Xiliang1
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
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.

1 系统模型 1.1 网络模型

 Download: JPG larger image 图 1 具有多个任务节点的雾计算网络 Fig. 1 A fog-enabled network with multiple TNs

1.2 问题建模

 $\begin{array}{ll} \min \limits_{\left|f_{n}, \mathcal{A}_{n}\right|_{n \in N}} & |\mathcal{N}| \\ \text { s. t. } & \sum\limits_{n \in N}\left|\mathcal{A}_{n}\right| = K, \\ & \left\|\omega_{k}-f_{n}\right\|_{2} \leqslant r, \forall k \in \mathcal{A}_{n}, \forall n \in N, \\ & \frac{1}{\mu-\sum\limits_{k \in \mathcal{A}_{n}} \lambda_{k}} \leqslant \tau_{\max }, \forall n \in N, \end{array}$ (1)

 $K \geqslant N \geqslant \frac{\tau_{\max }}{\tau_{\max } \mu-1} \sum\limits_{k = 1}^{K} \lambda_{k}.$ (2)

 $\mu-\sum\limits_{k \in \mathcal{A}_{n}} \lambda_{k} \geqslant \frac{1}{\tau_{\max }}, \forall n \in N,$ (3)

N个不等式加和，得

 $\mu N-\sum\limits_{k = 1}^{K} \lambda_{k} \geqslant \frac{N}{\tau_{\max }},$ (4)

 $N \geqslant \frac{\tau_{\max }}{\tau_{\max } \mu-1} \sum\limits_{k = 1}^{K} \lambda_{k},$ (5)

2 计算节点布局算法 2.1 二分K均值聚类算法

 $\begin{array}{ll} \min \limits_{\boldsymbol{f}_{n}} & r_{n} \\ \text { s. t. } & \left\|\omega_{k}-f_{n}\right\|_{2} \leqslant r_{n}, \quad \forall k \in \mathcal{A}_{n}, \end{array}$ (6)

 $s_{n} = \left\{\begin{array}{c} 0, & r_{n} \leqslant r, \frac{1}{\mu-\sum\nolimits_{k \in \mathcal{A}_{n}} \lambda_{k}} \leqslant \tau_{\max }, \\ 1, & \text { 其他. } \end{array}\right.$ (7)

 $\mathcal{C} = \left\{n \mid s_{n} = 1\right\}$ (8)

 Download: JPG larger image 图 2 SCNP算法示例 Fig. 2 An example of SCNP algorithm
2.3 复杂度分析

MBKC算法   对于二维欧几里德空间中的K均值聚类算法[20]，其时间复杂度为O(KNI)，其中K, N, I分别表示任务节点数量、计算节点数量和算法收敛迭代次数。解最小覆盖圆问题时间复杂度为O(K′)[19]，其中K′是被覆盖的任务节点数量，且有K′≤K。因此算法总时间复杂度为O(K2NI)，上界为O(K3I)。

SCNP算法    计算当前未被覆盖的任务节点的凸集其复杂度为O(Klog(Kb))，Kb表示当前处于边界上的任务节点的数量。解最小覆盖圆问题的复杂度上界为O(K)。另外，处理问题(9)中的约束2和约束3带来的复杂性是$2\left|\mathcal{K}_{C}\right|$，部署的计算节点的最大数量为任务节点数量K。总体复杂度有上界$O\left(K^{2} \log K+K^{3}+2 K\left|\mathcal{K}_{C}\right|\right)$

3 仿真实验分析

 Download: JPG larger image 图 3 平均任务处理延迟的累积分布函数对比 Fig. 3 Cumulative distribution function of average task processing delay

 Download: JPG larger image 图 4 不同算法下计算节点随任务节点数量变化对比 Fig. 4 Number of CNs with the number of TNs under various placement algorithms

4 结论