Exact and Approximation Algorithms for the Planning and Design of Fog Networks

Fog computing has attracted lots of attention from industry and research communities. However, due to the decentralized and heterogeneous nature of fog networks, planning a fog network can be challenging. To deal with this problem, we first propose a multi-objective mathematical model that simultaneously addresses the fog node placement, fog node dimensioning and demand routing. The model optimizes the tradeoff 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 offer a good balance between the Pareto optimality and computation efficiency. Inspired by existing evolutionary algorithms, we proposed a new evolutionary algorithm (PSONSGA). Among the three evolutionary algorithms, PSONSGA gives the best solution and it can be a valuable planning tool for real-world fog network planning.