Optimizing fog colony layout and service placement through genetic algorithms and hierarchical clustering

Abstract

[eng] Fog computing has emerged as a promising paradigm for distributed data processing, but managing numerous devices in fog domains is complex due to the scale of the infrastructure. To address this challenge, organizing fog devices into fog colonies allows independent management on a smaller scale. We present a genetic algorithm (GA) approach that utilizes hierarchical clustering to define the fog colony layout. The GA selects a subset of colony candidates from the dendrogram obtained with hierarchical clustering and optimizes the network communication time between users and applications and the execution time of algorithms that manage application placement in each colony. We deployed an NSGA-II, a multi-objective approach for GAs, to evaluate our proposal. Our experimental results demonstrate that combining a GA with hierarchical clustering improves both optimization objectives. We conducted nine experiment scenarios, varying the number of applications and fog devices. Our results show that even in the worst-case scenario, the GA’s results dominated the solutions obtained by two control algorithms after only 137 generations. Additionally, the number of genetic solutions and their homogeneous distribution in the Pareto front were satisfactory.