A graph partitioning-based heuristic for runtime IoT data placement strategies in a fog infrastructure
Mohammed Naas, Laurent Lemarchand, Jalil Boukhobza, Philippe Raipin · 2018
Fog computing is a dense, heterogeneous and geographically distributed infrastructure. With the rise of IoT applications, objects may generate large amounts of data that may be processed at different locations of the Fog infrastructure. Data placement strategies have been designed to investigate the best storage location for data in order to reduce its access time for different IoT services spread over the infrastructure. Unfortunately, due to the large number of Fog nodes and the amount of data to be managed, placing data in such infrastructure is an NP-Hard problem. In this paper, we propose a divide and conquer heuristic for data placement strategies in Fog infrastructures. Our idea consists in dividing the original data placement problem into several balanced sub-problems using graph modeling and partitioning methods. Using our heuristic makes it possible to reduce the solving time by more than 450 times with less than 5% of optimality loss as compared to the exact solution (without subdivision). For a given number of partitions, our solution proved to be at least as close to the optimal as state-of-the-art solutions and 30% closer to the optimal for many workloads. In addition, our solution allowed for a better optimization in solving time as it is more flexible and scalable in terms of number of partitions.