An approach based on fog nodes collaboration and lottery algorithm for deadline-aware task placement and scheduling in fog computing

Fog computing is a distributed computing paradigm that extends the cloud services to the edge of the network to support real-time and delay-sensitive applications. One of the main issues in fog computing is how to effectively and fairly allocate the restricted resources of fog nodes to users' requests. The limited number of resources, the different requirements of user requests, and latency requirement of delay-sensitive applications have made resource allocation and scheduling challenging. This paper proposes an efficient approach for the placement and scheduling of deadline-aware tasks in fog computing. In the proposed approach, task placement is done with the collaboration of fog nodes and based on the estimation of the completion time of a request in different fog nodes. The lottery algorithm is also used for task scheduling, and the requests are prioritized based on their deadlines. The experimental results show that the combination of fog nodes collaboration for task placement and the lottery algorithm for scheduling reduces the response time and increases the acceptance ratio of user requests. According to the simulation results, the acceptance ratio and the response time of the proposed approach improved by 12.72% and 37.97 ms, respectively, compared to the baseline method that uses the FCFS algorithm for task scheduling. Also, in comparison with the existing approaches which use a central controller for fog nodes collaboration, the proposed approach increased the acceptance ratio by 2.57%, and decreased the response time by 20.42 ms.