An Improved Graph Partitioning Algorithm Based Approach for Workflow Offloading in a Fog Environment

The paper addresses the critical problem of application workflow offloading in a fog environment. Resource constrained mobile and Internet of Things devices may not possess specialized hardware to run complex workflows locally and hence, need to offload these tasks to fog nodes. As compared to cloud-based servers, fog nodes can provide responses in a more-timely manner and are preferred for latency-sensitive applications. Workflow applications are characterized by inter-task dependencies and hence, can be readily represented as directed acyclic graphs. Therefore, the proposed offloading solution approach utilizes an improved graph partitioning algorithm based on the Louvain community detection algorithm. The aim of the algorithm is to partition the workflow graph in such a manner that the workflow tasks having high communication costs between them are transferred or offloaded to the same fog node. The benefits of the proposed algorithm have been verified by simulation experiments where it was observed that it results in a lower makespan as compared to the related approaches.