Exact and Approximation Algorithms for the Planning and Design of Fog Networks
Decheng Zhang · 2018
As a promising computing architecture, fog computing has attracted lots of attention from industry and research communities in recent years.With the huge number of heterogeneous and distributed devices performing computational and storage tasks between the cloud and users, fog computing can be an answer to the surging challenges in today's networks.However, due to the decentralized and heterogeneous nature of fog networks, planning a fog network can be a complicated and challenging task.To our best knowledge, little work has been done on the planning and designing of fog computing networks.To deal with this problem, we first propose a multi-objective mathematical model that simultaneously deals with the fog node placement, fog node dimensioning and demand routing.The model optimizes the tradeo↵ front (Pareto front) between capital expenditure and network delay in dual objective functions.Then, we analyze the performance of an exact algorithm (branch and bound) and two evolutionary algorithms (genetic algorithm and particle swarm algorithm) on this problem, showing that the evolutionary algorithms o↵er a good balance between the Pareto optimality and computation time e ciency.Inspired by the existing evolutionary algorithms, we proposed a new evolutionary algorithm, named PSONSGA, which combines the convergence e ciency from NSGA-II and the searching e ciency from SMPSO.The results demonstrate that the evolutionary algorithms are highly e cient compared to the exact algorithm.Among the three evolutionary algorithms, the algorithm we proposed (PSONSGA) gives the best Pareto front solutions which shows the good convergence to the true optimal front and the evenly distribution character.The proposed algorithm can be a valuable planning tool for real-world fog network planning.iii 5.10 Planning result of SMPSO, cost: $1,004,900 delay: 323.8ms . . . . .5.11 Planning result of PSONSGA, cost: $1,004,900 delay: 322.7ms . . . .5.12 HV indicator comparison (instance-1) . . . . . . . . . . . . . . . . . .5.13 HV indicator comparison (over four instance sets) . . . . . . . . . . .5.14 Delay gaps (instance-1) . . . . . . . . . . . . . . . . . . . . . . . . . .5.15 CPU time comparison (instance-1) . . . . . . . . . . . . . . . . . . .5.16 CPU time comparison (over four instance sets) . . . . . . . . . . . . .x C.1 CPU time comparison (instance-2) . . . . . . . . . . . . . . . . . . .C.2 CPU time comparison (instance-3) . . . . . . . . . . . . . . . . . . .C.3 CPU time comparison (instance-4) . . . . . . . .