A Survey on Various Methods and Algorithms of Scheduling in Fog Computing

The Internet of Things (IoT) is deployed in most areas [1, 2]. This technology is based on connected objects, which are widely used. Cisco estimates that there will be around 50 billion connected devices by 2020 [3]. They generate a massive amount of data that needs to be transmitted, stored, processed and analyzed in Cloud data centers. This increases the Cloud load and transmission latency; therefore, the Cloud cannot meet the QoS requirements of IoT critical applications such as latency sensitive applications. These challenges require a new architecture to deal with it [4].

1.1 Overview of Fog Computing

In 2012, Cisco proposed a new paradigm named Fog Computing [5]. It is a highly virtualized platform that provides computation, storage, and networking services between end devices and traditional Cloud Computing Data Centers [5]. Its main role is to extend the Cloud to be closer to the objects that produce and act on IoT data [6]. The Fog Computing is defined by OpenFog Consortium [7] as “horizontal, system-level architecture that distributes computing, storage, control and networking functions closer to the users along a cloud-to-thing continuum”.

1.1.1 Architecture of Fog Computing

Recently several research studies proposed a Fog Computing architecture [7-10]. This architecture is divided into several layers, the number of layers depends on the point of view of the author or the application [8]. The majority of these studies presented a three hierarchical layers architecture [9, 11-14] as shown in Figure 1.

1.png

Figure 1. A hierarchical architecture of Fog Computing

1.1.2 Characteristics of Fog Computing

In the literature, several researchers [8, 13, 15-17] have proposed a comparison between the characteristics of Cloud and Fog Computing. Based on these studies, it is noticed that the Cloud Computing represents a large data centers available over the Internet, geographically centralized, on the other hand, the Fog Computing constituted of several small data centers, geographically widely distributed. This provides services to user requests at the edge of networks where the distance between client and server is one or few hops, which allows location awareness and reduces latency. In terms of resources, Cloud Computing has a high resources capacity (CPU, RAM, Storage, Bandwidth), which requires high energy consumption, and high-cost resources’ usage. By comparison, Fog Computing, has less resource capacity at lower cost, and which reduces energy consumption linked to the small data center, located at the edge networks.

The common differences between the characteristics of these two paradigms is summarized in Table 1.

Table 1. A comparison between the characteristics of Cloud and Fog Computing

1.1.3 Advantages, challenges and issues of Fog Computing

According to the comparative table (Table 1), we observe that the Fog Computing paradigm offers several advantages to applications such as: reduction of the computational load and the use of resources of Cloud servers [16], reduces network traffic, suitable for IoT applications [10], ensures low latency and real-time interactions, and supports for mobility [9].

Despite the advantages offered by Fog Computing, it poses many challenges and issues: security and privacy, energy management [9, 16], resource management and scheduling [8].

1.2 Scheduling in Fog Computing

The scheduling is a NP-hard problem, as defined by M.Pinedo in [18]: “Scheduling is a decision-making process that is used on a regular basis in many manufacturing and services industries. It deals with the allocation of resources to tasks over given time periods and its goal is to optimize one or more objectives”. Scheduling presents one of the major challenges in Fog computing paradigm. It plays a fundamental role to improve the performance of the whole system, by optimizing one or many objectives to map the tasks to the appropriate resources [19] in order to respond to the QoS required by the applications. At the same time, it aims to improve the degree of customer satisfaction [19].

Fog computing has a hierarchical architecture, where resources are distributed in the different layers of the paradigm. Each layer has its own characteristics and capacities. The scheduling problem in Fog computing presents a new aspect of scheduling compared to traditional scheduling in related paradigms.

In this paper, we present the most recent research work concerning the different scheduling methods and algorithms. The main purpose of these methods is to improve scheduling and optimize the performance of applications in Fog computing.

1.3 Related surveys and our contributions

In this section we present some surveys related to our work. The surveys of Naha et al. [8], Mouradian et al. [14] and Elavarasi et al. [20] have presented an overview of Fog computing: Architectures, Definitions, Research Directions and Challenges, state of the art and Fog applications. Mouradian et al. [14] presented the task scheduling algorithms and analyze them according to different criteria. In the paper [8], the authors discuss the existing research works and gaps in resource allocation and scheduling. In the survey [20], the authors compare various scheduling algorithms based on performance metrics. In another survey [21], the authors analyzed the research studies about task scheduling approaches in fog computing from 2015 to 2018. They proposed a classification of task scheduling approaches in two categories: static and dynamic.

In this survey, we summarize our main contributions as follows:

(1) Present a literature review of the various methods and scheduling algorithms recently proposed and used in Fog computing.

(2) Propose a taxonomy, which classifies the different methods and scheduling algorithms.

(3) Compare the different types of scheduling algorithms according to QoS criteria and their appropriate applications.

(4)Compare a number of tools used to evaluate the different proposed approaches.

1.4 Paper organization

The reminder of this article is organized as follows: in Section 2, we present a taxonomy of the different methods and scheduling algorithms used in Fog computing. Section 3 reviews the literature and analyses various existing research works in this field. Sections 4 compares the different algorithms and methods according to the QoS criteria, and it classifies them according to the appropriate type of application. In section 5, we present and compare the different scheduling algorithms and simulation tools used in research work. Section 6 discusses the techniques and methods used to improve scheduling. We conclude our paper in Section 7.

This section presents a literature review of the various recent research works proposed to demonstrate the different techniques and scheduling algorithms used in Fog computing to improve the performance of applications. According to the taxonomy proposed in this survey, we classify the different scheduling methods.

3.1 Scheduling based on optimization methods

These methods use heuristic, meta-heuristic or hybrid techniques. These proposed algorithms are compared to traditional algorithms in terms of performance in order to adapt them to Fog computing paradigm.

3.1.1 Heuristics algorithms based scheduling

Choudhari et al. [22] proposed a priority levels-based task scheduling algorithm (PLTS) in the Fog layer by combining two algorithms. The first one is an efficient resource allocation (ERA) algorithm proposed by Agarwal et al. [23]. It is implemented in the Fog layer and uses a three-layer architecture model (Client-Fog-Cloud). The second algorithm is a priority-based scheduling algorithm, proposed by Dakshayini et al. [24] and implemented in cloud computing environment.

PLTS algorithm starts by checking the availability of resources in the Fog nodes that satisfy the clients’ requirements. If the resources are sufficient in this layer and the requests can be served by the deadline, the algorithm assigns a priority level to the client request and processes it later. However, if resources are not sufficient then it sends the requests to the Cloud layer.

The authors performed several simulation scenarios with CloudAnalyst tool. For each scenario, the results of the performance metrics of the algorithm proposed are compared to those of the following three policies: Optimize Response Time (ORT), Reconfigure Dynamically (RD), and Efficient Resource Allocation (ERA) [23]. This study showed that the proposed prioritized scheduling algorithm has reduced the response time and has considerably decreased the cost. However, it used the static priority settings in response to request traffic load.

3.1.2 Meta-heuristics and hybrid algorithms based scheduling

Wang et al. [25] proposed a task scheduling algorithm in Fog computing based on the improvement of the bio-inspired Firework Algorithm (FA) [26].

The authors proposed two contributions. First, they improved Firework Algorithm (I-FA) by the introduction of an explosion radius detection mechanism. Second, they used the proposed task scheduling algorithm (I-FASC) which takes into account the characteristics of the tasks and the resources. They have classified the tasks into three clusters according to expected storage space, expected time and expected bandwidth. Then, they integrated resources which are of three types: computing, storage and bandwidth.

The experimental results showed that the algorithm (I-FA) has an average explosion radius smaller than (FA) algorithm, and performed better than the other algorithms such as ACO-based algorithm (Rank-ACO) [27], double-fitness Genetic algorithm (DFGA) [28] and FA [26]. It reduces the number of iterations with the fastest convergence speed. The algorithm (I-FASC) reduces the task completion time compared to the other three algorithms: FSFC, Rank-ACO and DFGA. It allocates the resource in a more balanced way, which improves the performance of the entire system.

Xu et al. [29] proposed a method of scheduling tasks in the Fog-Cloud environment (LBP-ACS). This latter is based on the combination of two algorithms: Laxity-Based Priority (LBPA) [29] and Ant Colony System (ACS) [30]. The aim is to schedule the tasks’ execution in a way to respect the deadlines, and to minimize the total energy consumption. The authors started with the algorithm (LBPA), which calculates the laxity time for each task and assigns a priority to the laxity (the smaller the laxity of the task, the higher the priority of the task). They also proposed a constrained optimization algorithm based on the Ant Colony System algorithm, which chooses the right Cloud or Fog resources for the task based on its propriety.

After testing and evaluating the proposed method, they compared its performance to three other algorithms: Greedy for Energy (GFE), Heterogeneous Earliest Finish Time (HEFT) [31], and Differential Evolution Ant Colony Optimization (DEACO) [32]. The results showed that the proposed algorithm (LBP-ACS) outperformed the other algorithms. It balances the benefits between schedule length and energy consumption for Cloud or Fog resources, with Lower failure ratio rate.

The authors of the work [33] focused on task scheduling problem for Bag-of-Tasks applications in Cloud Fog computing environment. They proposed an algorithm called a Time-Cost aware Scheduling algorithm (TCaS) based on an evolutionary algorithm (Genetic Algorithm). They used the same Fitness Function to compare its performance (trade-off between the Makespan and Total Cost) to the following algorithms: Modified Particle Swarm Optimization (MPSO) [34], Bee Life Algorithm (BLA) [35] and a traditional simple Round Robin (RR) algorithm. They carried out several experiments in two different scenarios: one in a local Fog environment and another in a Cloud-Fog environment. The results show that for the first scenario TCaS has a better makespan and total cost; for the second scenario TCaS has a better makespan than the other algorithms, however MPSO has a better total cost than the other algorithms.  They also demonstrated that (TCaS) is less convergent compared to the other algorithms (MPSO, BLA), however, it generates a more optimal solution.

Xu et al. [36] focused on scheduling Workflow in the Cloud-Fog environment. They presented a scheduling method that solves the mapping process between tasks and resources to minimize the makespan of Workflow and the cost. This method is an optimization of PSO algorithm. They introduce a new non-linear function (inertia weight), which enhances the global and local search capabilities of particles.

Bitam et al. [37] proposed a new bio-inspired algorithm for scheduling tasks, based on Bee Swarm optimization algorithm called Bees Life Algorithm (BLA) [35]. This new algorithm focuses on scheduling improvement in the fog computing environment. They designed a better allocation of tasks among the available Fog resources, by finding an optimal trade-off between CPU execution time and allocated memory. To achieve this goal, the authors proposed an optimization of the BLA algorithm using a Greedy approach to optimize the local search and improve the global solution. This way they reduced the latency and the cost to satisfy mobile users’ requests.

All the authors’ works discussed in this section are summarized and compared in Table 3.

Table 3. Comparison of meta-heuristics and hybrid algorithms based scheduling (S: Simulation, E: Evaluation on a real server or platform)

All works studied previously aim to improve the quality of scheduling and increase the performance of solution in terms of reducing latency, energy consumption, makespan and the cost. They are based on heuristics [22], meta-heuristics [33, 36] or hybrids [25, 29, 37] approaches.

It is noticed that the hybridization of the scheduling algorithms brought potential benefits where authors in [29] combined Greedy algorithm with ACO in order to have better performance and in [25] improved the firework algorithm by a genetic algorithm. In [37], the authors proposed a Bees Life Algorithm combined with Greedy approach to improve the local search process in order to reach the optimal individual. Other works favored the use of meta-heuristic algorithms such as in [33] where the authors propose a modification of GA in the Parental Selection part, this modification improved the value of the fitness function compared to the BLA and MPSO algorithms. In [36], the authors proposed an improvement of the PSO algorithm, by a novel update method of inertia weight

that influences search capability of particles, and which facilitates to enhance the global search capability of particles.

3.2 QoS constraints-based scheduling

In this class of scheduling methods, the approaches proposed by the researchers focus on optimizing QoS constraints, in order to meet the performance requirements of the types of applications deployed on Fog computing.

3.2.1 Energy-efficiency based scheduling

Among the problems encountered in the Fog computing paradigm is the energy consumption management [9, 16] of the distributed nodes that must be efficient. The proposed works use the scheduling methods with the common objective of decreasing the energy dissipated by IoT nodes. In this section, we present research works that deal with this type of problem.

Table 4 summarizes the Energy-Efficiency based Scheduling works.

Rahbari et al. [38] proposed a scheduling strategy called greedy knapsack-based scheduling (GKS) by combining the knapsack and Greedy algorithms. The knapsack algorithm was used for resource scheduling for allocation optimization of processing elements. Each application is a combination of a set of modules, and each module is assigned to a specific processing element. While a greedy algorithm was used to reduce the time delay in optimal allocation of resources to modules in the fog network. These two algorithms were used in order to optimize the objective of the knapsack problem by maximizing the profit and minimizing the weight. The results of different case studies of the proposed method GKS has reduced the number of application modules lunched by the processing elements of hosts in micro–Data centers, which has reduced energy consumption and cost at the same time.

Wan et al. [39] proposed an architecture for smart factory applications based on Fog Computing, which aims to solve the problem of energy consumption related to equipment workload. The authors proposed an energy-aware load balancing and scheduling method called (ELBS). It makes it possible to establish an energy model of the equipment deployed on the Fog nodes for load balancing. It has an objective function to be minimized for optimizing scheduling. The authors implemented an improved PSO algorithm in order to find better results. The multi-agent system is introduced, to realize dynamic scheduling of intelligent equipment using Fog nodes according to the load balancing scheduling strategy. The authors have performed experiments on a real environment, which presents a prototype platform of type intelligent manufacturing system. The results show that the proposed method has a better-balanced workload, and optimized the energy consumption.

Wang et al. [17] studied the task scheduling strategy in the Fog computing scenario. They proposed a task scheduling strategy based on a hybrid heuristic algorithm (HH). It deals with resource limitations and high energy dissipated by smart manufacturing devices. HH algorithm combines the advantages of two algorithms: the improved particle swarm optimization (IPSO) and the improved ant colony optimization (IACO). IPSO has a fast convergence and IACO has high precision characteristics to obtain the optimal solution of task scheduling. Based on experiment results, the proposed Hybrid Heuristic algorithm (HH) have outperformed other simple algorithms IPSO, IACO, Round-Robin. Also, the energy consumption is proportional to the completion time.

Luo et al. [40] proposed a new hierarchical architecture called multi-cloud to the existed multi-fog architecture based on containers technology. The multi-cloud aims to improve the resource utilization by Fog nodes and reduce the service delay. They also proposed a scheduling algorithm to deploy on the Fog nodes based on the energy balancing strategy. Its role is to control the transmission power of terminal devices, according to their energy levels, in order to extend the wireless sensor networks lifetime.

Furthermore, it aims to reduce the delay constraint of tasks through the collaboration of the Fog nodes and the Cloud according to the available resource threshold of the Fog node.

Wu et al. [41] proposed several models. They modeled the IoT system as a three-level model. The IoT application is modeled by a directed acyclic graph. They proposed a model to study the energy consumption of the overall three-tier IoT system. The DAG is divided into two parts, one part is assigned on the things tiers and processed locally, and the second part is sent to the Fog and Cloud tiers for further processing. The tasks assigned to the things tier are sorted by a heuristic method called bottom level (b-level) [42], and the tasks assigned to the Fog and Cloud tiers are sorted by the proposed Estimation of Distribution Algorithm with the partition operator (EDA-p). When these two processing sequences are determined, the tasks will be assigned to the nodes by the rule of Earliest Finish Time First (EFTF). The proposed scheduling algorithm EDA-p aims to achieve the trade-off between energy saving and shorten makespan. Its performance was evaluated using several cases of comparative studies. The experiment results show that the algorithm is effective, in reducing makespan and the energy consumption of devices, as well as extending the life time of IoT devices.

Table 4 recapitulates the previous discussed Energy-Efficiency based Scheduling works.

Several approaches and strategies have been used with scheduling algorithms for different applications to use energy in an efficient way. Wan et al. [39] proposed several techniques for Smart Factory type application to reduce the energy consumption by factory terminals equipment. Their scheduling method is based on load balancing mechanism. The scheduling method proposed by Wang and Li [17] is based on a reasonable allocation of resources.

Table 4. Comparison of energy efficiency based scheduling

In battery-based applications, where system life is a major issue, Luo et al. [40] have proposed a multi-cloud to multi-fog based on containers architecture, which uses a scheduling algorithm based on the energy balancing strategy, between terminal devices and an energy harvesting equipment. Another solution proposed by Wu et al. [41], uses scheduling algorithm to minimize the energy consumed by IoT devices.

All these strategies proposed previously, are used with scheduling algorithms, in order to improve the energy efficiency. Most of these proposed algorithms are of heuristic and meta-heuristic type [38, 40, 41] and hybrid [17, 39].

3.2.2 Time-efficiency based scheduling

One of the major problems encountered by these types of critical IoT applications, is the time constraint (or the real-time interaction) requiring application tasks to complete within an expected deadline. Next, we discuss the researches about different scheduling methods, which aim to reduce the applications’ response time. In what follows, we will review some Time-Efficiency based Scheduling works and compare them in the Table 5.

Stavrinides et al. [43] proposed a new approach, which attempts to schedule computationally demanding tasks, with low communication requirements on the Cloud, and communication intensive tasks, with low computational demands on the Fog computing layer. By contrast other approaches perform the IoT tasks on the Fog computation layer. This approach is based on a hybrid Fog and Cloud-aware heuristic, for the dynamic scheduling of multiple real-time IoT workflows in a three-tiered architecture. This heuristic approach allows the scheduling of a ready task of a workflow on either Fog or Cloud layer based on its potential communication and computational requirement. The proposed scheduling strategy is divided in two phases. A task selection phase that prioritizes tasks according to the Earliest Deadline First (EDF) policy, and a VM selection phase, which allocates the selected task to VM using estimated Earliest Finish Time (EFT) policy.

The authors compared the performance of this approach with a proposed alternative version of Cloud-unaware scheduling strategy called Fog-EDF. The obtained results show that the Hybrid-EDF method reduces the deadline miss ratio in a significant way by comparison to Fog-EDF.

Auluck et al. [44] proposed an improvement in real-time task scheduling using the Fog computing, which is based on three-tiers architecture: local embedded, Fog and Cloud. This approach allows application tasks to be assigned to the appropriate tier for successful execution, which ensures minimal overall communication time. First of all, the authors divided the tasks into three categories according to their delay tolerance hard real-time, firm real-time and soft real-time. To improve the scheduling of these tasks, they proposed two types of algorithms.

The first algorithm is Static LFC (Local, Fog, Cloud), which statically assigns the tasks to be executed to the appropriate queue of different layers by the application of schedulability test, and the use of an optimization model. This leads to minimizing the total communication delay between Local, Fog and Cloud. The second algorithm is Self-Contained LFC (Local, Fog, Cloud), which schedules tasks without the use of schedulability test. It starts by scheduling the hard real-time type tasks on the local embedded processors. Then if the other types of tasks fail to meet their deadlines in this layer, they are scheduled in their appropriate layers with the use of an optimization model to minimize the total communication delay, which includes the tasks’ constraint deadline. The authors implemented their approach based on EDF scheduling algorithm, and compared it to other algorithms based on the same scheduling algorithm, which uses one of the following: Embedded-Cloud, Embedded-Fog or Fog-Cloud. The obtained results showed that the proposed approach improves the throughput, success ratio and response time.

Mukherjee et al. [45] aim to minimize the failure probability, to meet the different delay deadlines for the tasks that have arrived at the fog. They considered the system to be composed of a set of Fog nodes and end-users that are uniformly and randomly distributed over the entire network. The end-users offload their entire tasks to a nearby Fog node referred to as primary Fog node. If the computing resources are not sufficient at the level of primary Fog node, it will offload these tasks to the other neighboring Fog nodes. They assign a priority to the tasks according to the value of delay-deadlines. They consider that each Fog node maintains two virtual queues namely high-priority queue and low-priority queue. The scheduling of these queues is done using Lyapunov optimization function. The authors run a series of experiments using Monte Carlo simulations. The obtained results show that the scheduling method which uses the offloading tasks and Lyapunov drift-plus-penalty function, improved reliability (how many tasks meet their deadlines) compared to random scheduling.

Aburukba et al. [46] modeled the problem of scheduling IoT devices’ requests in edge layer and assign them the adequate resources available at both Fog and Cloud layers in order to reduce the latency in the hybrid architecture Fog-Cloud computing. They proposed a customized implementation of Genetic algorithms.

Table 5. Comparison of time-efficiency based scheduling

Table 6. Comparison of cost efficiency-based scheduling

They included a procedure for penalizing infeasible solutions, which do not satisfy the constraints of the problem (each request is allocated to one and only one resource, and it must satisfy the deadline requirements), by reducing the probability of unsatisfactory chromosome selection.

The authors carried out experiments to determine the parameters such as the population size and maximum number of iterations, which have a direct impact on the quality of the solution. They also compared the proposed GA to an exact algorithm called Branch-and-Bound algorithm (B&B). These two algorithms gave almost the same result for the latency value; however, the B&B algorithm did not converge to a solution for problems with large size. This algorithm took almost two days to compute a solution for a problem with 10 requests and 3 resources. On the other hand, the proposed GA gives a solution within a period of less than one minute for the same problem. Once the suitable parameters were determined, a series of simulations for different scenarios have been performed, and compared with other traditional algorithms such as Waited Fair Queuing, Priority Strict Queuing, and Round Robin. The results demonstrate that the proposed algorithm gives better performance in terms of overall latency, and meeting the requests deadlines by comparison to other unoptimized algorithms. The experiments also show that Fog computing provides better service latency than using only Cloud computing.

The approaches discussed in this section, have common objectives, which are to minimize latency, meet deadlines, and

satisfy the requests of real-time applications. Several techniques and strategies offloaded tasks towards the most efficient nodes [44, 45], respected the deadline and minimized the delay. In the study [45], the authors detailed their scheduling strategy, and explained how to choose the appropriate node to offload the task. 

The second technique, used in ref. [43-45], leverages priority-based algorithms, by favoring tasks that have the earliest deadline. For the scheduling algorithms, we observe that the authors [43, 44] use the priority-based algorithm Earliest Deadline First (EDF), which is the most used algorithm in the scheduling of real-time systems. The authors of the work in [45] proposed a new scheduling method based on Lyapunov optimization function. A new scheduling method [46] to minimize latency is based on a genetic algorithm. This approach reduces the latency by comparison to non-optimized algorithms.

3.2.3 Cost Efficiency based scheduling

The applications, deployed on Fog computing nodes, use several types of resources (Bandwidth, CPU, Storage, etc.) from different layers of the paradigm, in order to perform their tasks. The massive use of these resources depending on the nature of the applications generates additional costs. One of the advantages of this paradigm is to reduce the use of paid resources. For this purpose, we need efficient scheduling algorithms, which share the workload on the different available nodes in order to reduce the cost.

In this section, we review and compare (see Table 6) few approaches designed for cost efficient management.

Ding et al. [47] proposed a cost-effective scheduling strategy for multi-workflow with time constraints in Fog computing. This scheduling strategy uses multi-layer resources of Fog and Cloud computing called (CTSF). The proposed algorithm is based on Particle Swarm Optimization (PSO), which allows tasks to be allocated to adequate resources, and uses the fitness function with an objective of finding a minimum value of resource execution cost under given deadlines. In the case where multiple tasks are allocated to the same resource at the same time, a second algorithm called Min-Min algorithm is used to resolve the resource allocation conflict.

In order to evaluate the performance of the proposed scheduling strategy, two evaluation aspects have been carried out. First, the CTSF algorithm is compared to two other strategies, which use the same PSO and Min-Min algorithms, however they use the resources from a single layer either Fog or Cloud. Second, they evaluated the CTSF algorithm using different resource conflict resolution algorithms in multi-layer Fog and Cloud resources. Based on the obtained results, it is recommended to execute tasks that require large workload and small data on cloud servers because of the communication time saving. However, tasks with small workload and large data set should be executed on Fog nodes. The CTSF strategy can find the best scheduling plan with lowest cost under given deadlines, using the PSO and Min-Min algorithms, by reducing the execution time of conflicting tasks.

Stavrinides et al. [48] proposed a real-time scheduling strategy for the tasks of the multiple workflows, coming from IoT to Fog computing and which uses Cloud resources as a complement. This strategy is based on the trade-off between performance and monetary cost. It consists of two stages. A task selection stage, allows to prioritize the tasks of the global waiting queue for the central scheduler in Fog layer, according to their deadline using the Earliest Deadline First (EDF) policy. In the case where several tasks have the same priority, the task with highest average computational cost has highest priority. A virtual machine selection stage, which allocates the tasks, selected by the scheduler, to the adequate virtual machine of the Fog or Cloud tier, according to the minimum value given by the proposed objective function. This function takes into account the sum of two parameters (the estimated finish time and the estimated monetary cost of resource usage). Each one of these parameters is assigned a weight indicating its contribution factor. This weight is calculated using a proposed scheduling heuristic.

The authors compared the performance of their proposed approach to a baseline policy MinEFT-Fog that uses only the Fog layer’s resources. The obtained results show that the proposed approach assigns tasks that require high computation but low communication to virtual machine in the Cloud. However, it assigns tasks with low computation and intensive communication to Fog virtual machines. This reduces communication costs and saves the average monetary cost compared to the baseline policy.

Pham et al. [49] proposed a cost and makespan aware scheduling algorithm called (CMaS). The objective of this algorithm is to achieve a good trade-off between the application execution time and the cost, for the use of Cloud resources and satisfy the user defined deadline constraints. The algorithm is divided into three phases. The first phase is to order the tasks based on the length of the critical path. The second phase is the node selection that allows the assignment of each task to an appropriate processing node on the Cloud or Fog, to achieve the optimal value of a utility function. The third phase is deadline-based task reassignment, which limits the deadline violation by reallocating critical tasks to the best processing nodes. This can reduce the completion time of each critical task.

In order to demonstrate the performance of the proposed algorithm, the authors performed two types of evaluations. The first one is the evaluation of the CMaS algorithm efficiency compared with other algorithms. The results show that the algorithm can achieve better trade-off between the makespan and the cost of task execution than other methods. The second evaluation concerns the deadline-based task reassignment. The results show that the deadline-based CMaS algorithm also gave a better performance in terms of makespan. It guarantees the end of application execution before the predefined deadline to satisfy the user QoS requirements.

After detailing some of the works in Cost Efficiency-based Scheduling category, we observed that authors in [47, 48] have proposed scheduling methods and strategy for multi-workflow standard applications. While the author in [49] applied these methods on workflow standard applications. Both methods are interested in minimizing two constraints at the same time. The aim is to reduce the cost of using resources. The execution time is taken in consideration by reducing the makespan [47, 49] or respecting the deadlines for real-time applications [48]. For the cost calculation, both works [48, 49] considered the type of resources and to which layers of the paradigm belong (Fog or Cloud), however, the work in [47] and the work of previous sections such as [22, 36, 37] did not optimize the cost based on the type of resources.

The work in Ding et al. [47] is based on a hybrid type optimization algorithm (PSO and Min-Min) to improve the quality of the result. Stavrinides et al. [48], Pham et al. [49] incorporated priority algorithms in their approaches to respond efficiently to the deadline constraint.

3.3 Classification-based scheduling

Liu et al. [50] proposed a new data mining classifications-based scheduling approach. They proposed a Task Scheduling algorithm in Fog Computing (TSFC) based on a new improvement of the traditional Apriori algorithm called I-Apriori. The main TSFC algorithm process is divided into two steps. First, it uses the I-Apriori algorithm to generate association rules of nodes and tasks sets from scheduling transaction set. Then, these association rules are used with the TSFC algorithm to get the task scheduling relationship between the Fog nodes and the tasks. After comparing the TSFC algorithm to other heuristic algorithms, the results show that, this new scheduling approach is more efficient than the Minimum Completion Time algorithm (MCT) [51], Minimum Execution Time algorithm (MET) [51] and MIN-MIN algorithm [52], in terms of completion time and waiting time. However, TSFC algorithm did not ensure the multi-layered task scheduling and the scheduling optimization for other QoS parameters.

In this section we present, a comparison of the use of different types of scheduling algorithms and also the simulation tools used by the researchers in their work.

5.1 Simulation tools comparison

3a.png

(a) Simulation VS Evaluation

3b.png

(b) Programming Language VS Simulator Toolkit

3c.png

(c) The list of Simulator Toolkit

Figure 3. Programming languages and simulation toolkit used in the experiment

Different Simulator Tool Kits Description:

(1) CloudSim: is an open-source extensible simulation toolkit, that enables modeling and simulation of Cloud computing systems and application provisioning environments. It allows the evaluation of the performance of resource provisioning and application scheduling techniques, under different usage and infrastructure scenarios [53].

(2) iFogSim: is a simulation toolkit developed based on the fundamental framework of CloudSim. It extends the abstraction of basic CloudSim classes, and offers scopes to simulate customized Fog computing environment with large number of Fog nodes and IoT devices. In addition, it facilitates evaluation of end-to-end latency, network congestion, power usage, operational expenses and QoS satisfaction [54].

(3) CloudAnalyst: extends the functionalities of CloudSim. This tool supports visual modeling and simulation of large-scale applications that are deployed on Cloud Infrastructures. The main objectives of CloudAnalyst are to separate the simulation experimentation exercise from a programming exercise. It allows description of application workloads, including users' geographical location information generating traffic and location of data centers, number of users and data centers, and number of resources in each data center. Using this information, CloudAnalyst generates information about response time of requests, processing time of requests, and other metrics [55].

(4) SimGrid: it is an open-source framework, which allows the simulation of distributed computer system used in studies on Grids, Clusters, High Performance Computing, P2P systems and Fog Computing [56].

(5) Matlab: is a tool often used in scientific fields to perform numerical calculations. It manipulates matrices, displays curves and data, and writes scripts and algorithms.

(6) C++: is a programming language, used in the development of applications that require high performance.

(7) Java: a general-purpose object-oriented programming language.

Based on our study of literature, we observe that the evaluations in a real environment present only 14% of experimental work. On the other hand, the authors tend to use simulation tools in their experimental work which presents 84%. This is due to the high cost and difficulty of implementation caused by the evaluation in a real environment (see Figure 3.a) [57].

These simulations are carried out by two different methods, either by programming or by the use of a Simulator Toolkit or Framework. Most of the simulations (56%) are carried out using a Simulator Toolkit (see Figure 3.b), because these tools facilitate the development, modeling and evaluation of the model to be simulated by using the functionalities offered by the Toolkit. This allows the researchers to focus on the simulation and analysis of the proposed approach’s behavior, analyze the results obtained in the various simulation scenarios [57, 58], and not focus on the details of programming the model to be simulated.

In the literature, the authors use several types of Simulator Toolkit as shown in. The majority of studies cited previously have generally used two types of Simulator Toolkit, the first is CloudSim specialized in the simulation of the scheduling in the Cloud Computing environment [59], and the second iFogSim is specialized in scheduling simulation in the Fog Computing environment as shown in Figure 3.c [54, 59].

5.2 Comparison of the type of algorithms used

According to the work cited above, we notice that most algorithms used to solve the scheduling problem, which is of NP-hard nature [54], are Heuristic or Meta-heuristic type (88%) as shown in Figure 4.a. This is due to the fact that this kind of algorithms have the ability to provide solutions close to the optimum within a reasonable time [60-62]. By comparison, exact algorithms give optimal solutions but in a very inefficient way. In the studies of the authors cited in this paper, we observe that the meta-heuristic algorithms are used more than heuristic algorithms (see Figure 4.a), because they provide better results closer to the optimal solution [60]. Among these meta-heuristic algorithms, we see that the most used algorithms are: PSO (27%), GA (20%) and ACO (13%). (see Figure 4.b). 67% the scheduling approaches, which use meta-heuristic algorithms are hybrid as shown in Figure 4.c. The hybridization of these meta-heuristic algorithms, improves the performance and the quality of the solution generated by the algorithm, as well as the speed of convergence [60, 63].

4a.png

(a) The use of Heuristic and Meta-heuristic Algorithms

4b.png

(b) The list of Heuristic and Meta-heuristic Algorithms

4c.png

(c) The use of type of Meta-heuristic Algorithms

Figure 4. The type of algorithms used in the scheduling