Design and Analysis of Real-Time Task Scheduling Algorithm for Fog-Cloud Computing

Since cloud computing platforms have powerful computing and data storage capabilities, they are widely used in the Internet of Things. However, as IoT services continue to expand, some IoT services have stringent latency requirements. Due to the long latency in communication between cloud data centers and IoT devices, cloud computing is no longer suitable for latency-sensitive IoT services.

Compared to cloud computing, fog computing resources are closer to terminal devices, which can reduce latency and improve service quality. However, the resources of the fog computing platform are limited and cannot process the large amounts of data generated by IoT devices. Therefore, effectively allocating tasks to cloud servers or fog servers for processing can meet the latency requirements of the tasks.

For the task scheduling problem, researchers have proposed scheduling algorithms based on different performance metrics, such as task execution time and deadline, task length, task security, etc. However, these scheduling algorithms do not adequately consider the resources required for executing tasks, and it is also difficult to accurately estimate the resources required for executing the task at the task submission stage.

Additionally, fuzzy logic algorithms can effectively allocate resources between fog and cloud computing and reasonably assign tasks to them, thereby reducing task latency, which is the main focus of this research. Due to the low complexity of fuzzy logic algorithms and their low requirements for computer processing power, they have been widely used in various fields.

However, due to the variability of task characteristics and the dynamics of the fog-cloud environment, scheduling tasks still faces challenges. Moreover, the diverse requirements of tasks and the varying resources available at fog nodes also affect the processing time of tasks. Therefore, how to allocate suitable tasks to nodes in the fog layer is crucial.

Research has confirmed that effectively selecting virtual machines (VMs) for tasks in a fog computing environment can improve task execution efficiency. Additionally, based on the resource requirements and acceptable latency, fog brokers (FBs) can manage resources and allocate tasks.

Literature proposed a three-way clustering optimal scheduling programming (TWOCP) algorithm, which clusters tasks using a three-way clustering algorithm and prioritizes scheduling core tasks of the cluster to reduce task completion time. However, this algorithm only focuses on task completion time and does not consider the correlation between tasks and service quality. Similarly, literature also proposed a task clustering algorithm based on three-way clustering, but this algorithm only emphasizes resource utilization and does not consider task completion time.

Literature proposed an improved particle swarm optimization (IPSO) algorithm for task scheduling, which decomposes tasks to reduce the continuous working time on each virtual machine. Although the IPSO algorithm can shorten completion time, it increases operational costs and energy consumption.

Based on the above research, this paper adopts a communication framework that combines fog and cloud layers. Compared to the cloud layer, the fog layer is closer to users. Therefore, executing some tasks in the fog-cloud can reduce task completion time. To this end, a fuzzy logic-based real-time task scheduling (FLTS) algorithm is proposed for the fog-cloud environment. The FLTS algorithm schedules tasks by considering the deadline, resource requirements of tasks, and resources accessible to fog nodes along with load information. The main work of this paper includes: ① proposing a fuzzy logic-based decision algorithm for the fog-cloud framework, thereby allocating tasks between the fog and cloud layers; ② adopting an improved task scheduling strategy to schedule tasks for heterogeneous fog nodes; ③ finally establishing a simulation system to analyze the performance of the algorithm.

1 System Model and Problem Description

1.1 Fog-Cloud Computing Architecture

Consider the three-layer fog-cloud computing network architecture shown in Figure 1. The bottom layer consists of terminal devices; the fog layer consists of fog brokers (FBs), fog servers, and virtual machines (VMs); the top layer is the cloud data center. IoT devices submit tasks to the fog layer; fog layer servers forward the received tasks to FB. FB manages the resources of fog servers and schedules tasks.

Figure 1 Fog-Cloud Computing Network Architecture

Since FBs are closer to fog servers, their communication latency is shorter. FB allocates tasks to the fog and cloud layers and selects suitable nodes to execute the assigned tasks.

Assuming the tasks received by the fog layer are independent. Let

represent the task set received by FB. Let t_i=(tid, in, ds, rs, dl, ct, st, bt) represent the ith task, where tid represents the task ID; in represents the instruction count; ds represents the data size of the task; rs represents the data size of the task result; dl represents the deadline of the task; ct, st, and bt represent the CPU rate, storage space, and bandwidth required to process the task, respectively.

Each fog server has multiple heterogeneous VMs and utilizes these VMs to execute tasks. Let V represent the set of all VMs in the fog layer. Let v_j=(vid, type, mc, cc, sc, bc) represent the jth VM, where vid represents the VM ID; type represents the VM type; mc, cc, sc, and bc represent the memory, CPU rate, storage space, and bandwidth of the VM, respectively.

1.2 Problem Description

The purpose of the proposed FLTS algorithm is to minimize the total latency of processing task t_i. Let T_proc(t_i) represent the total latency of processing task t_i:

Where: if the fog layer (or cloud layer) executes the task, then T_trans(t_i) represents the transmission latency incurred when forwarding the task from the device to the fog layer (or cloud layer). The value of T_trans(t_i) is calculated using the ratio of the task’s data size ds to the data transmission rate. T_exec(t_i) represents the time consumed by the selected VM to execute the task (execution time); T_queue(t_i) represents the waiting time incurred when accessing the VM; T_rep(t_i) represents the time required for the terminal device to obtain the processing result, which is equal to the ratio of the result size rs to the transmission rate. Furthermore, the total latency T_proc(t_i) for processing task t_i should be less than dl(t_i).

Once a task is received, FB decides whether to execute the task in the fog layer or forward it to the cloud layer for execution. If executed in the fog layer, FB assigns the task to an appropriate VM. To this end, a mapping function is constructed:

Where: Cloud represents the cloud layer; Fog represents the fog layer.

Then, an optimization problem is constructed to select a VM from the fog layer:

Where: g(t_i, v_j) represents the turnaround time for directing task t_i to VM v_j.

2 FLTS Algorithm

FLTS algorithm consists of two phases: the first phase involves using fuzzy logic to allocate tasks between the fog and cloud layers (task scheduling); the second phase involves selecting the optimal VM to execute the task (task execution).

2.1 Fuzzy Logic-Based Task Scheduling

When scheduling tasks, consider four factors: the resource requirements of the task, the latency requirements of the task, the maximum resource rate accessible in the fog layer, and the latency between the fog and cloud layers. To this end, if task t_i is allocated to the fog layer, the required CPU utilization rate, storage space utilization rate, and bandwidth utilization rate for executing the task are calculated as normalized values, defined as in Equation (4):

The CPU utilization rate, storage space utilization rate, bandwidth utilization rate, task deadline, and network latency are used as inputs to the fuzzy logic system. The output of the fuzzy logic system is the decision opinion. Let the Boolean variable D_decision represent the decision opinion. If D_decision=1, it indicates that task t_i is executed by the cloud layer; if D_decision=0, it indicates that task t_i is executed by the fog layer, as shown in Figure 2.

Figure 2 Fuzzy Logic-Based Task Scheduling Framework

Using the membership functions shown in Figure 3, the CPU utilization rate, storage space utilization rate, bandwidth utilization rate, task deadline, and network latency are fuzzified to form a fuzzy logic set, as shown in Table 1. For example, the normalized value of CPU utilization rate c_min(t_i) is fuzzified into three levels {Low, Medium, High}. Additionally, the output variable is fuzzified into two levels {Fog Layer, Cloud Layer}.

Figure 3 Membership Functions of Five Input Variables

The fuzzy logic system adopts the rule base shown in Table 2 to generate output variables. Since there are 243 rules in total, only a portion of the rules is listed in Table 2.

2.2 Task Execution

Section 2.1 generates the value of D_decision. D_decision=1 indicates that task t_i is executed by the cloud layer; D_decision=0 indicates that task t_i is executed by the fog layer. Once task t_i is executed by the fog layer, it is added to the fog queue (fog queue, FQ). The tasks in queue FQ are then sorted in ascending order based on their deadlines dl(t_i), prioritizing tasks with earlier deadlines. In other words, urgent tasks are given priority.

Algorithm 1: Constructing Available VM Set V‘ and Task Execution:

Then, by confirming the availability of each VM, an available VM set is constructed. Let V’ represent the available VM set. Initially, V’ is empty, i.e., V’=∅. The process of constructing V’ is shown in Algorithm 1. First, the CPU rate ct(t_i), storage space st(t_i), and bandwidth bt(t_i) required by the task are compared with the available CPU rate cc(v_j), storage space sc(v_j), and bandwidth bc(v_j) of the virtual machine. If ct(t_i) is less than cc(v_j), and st(t_i) is less than sc(v_j), and bt(t_i) is less than bc(v_j), then v_j is added to V’.

After constructing V’, the resource utilization rates of each VM in V’ are calculated, as shown in Equation (5).

In the fourth step, select the VM with the lowest resource utilization rate from V’ and assign that VM to task t_i:

In the fifth step, transfer task t_i to v’. If v’ is busy, insert task t_i into the queue and wait for processing; otherwise, process the task directly, as shown in Algorithm 1.

3 Simulation and Performance Analysis

3.1 Simulation Environment

The experiments were simulated on a PC with Windows 7 operating system, 8 GB RAM, and Core i7 CPU. The iFogSim software was used to construct the cloud simulation framework. The resource configuration of the fog-cloud architecture is shown in Table 3. Additionally, fuzzy logic was used to implement the fuzzy logic strategy. The transmission delay between the fog and cloud layers was randomly generated between 300 and 800 ms.

Table 4 presents the task characteristic parameters in the simulation, including instruction count, deadline, required storage space, and bandwidth.

3.2 Performance Metrics

To thoroughly analyze the performance of the FLTS algorithm, completion time (Makespan), latency rate, and success rate were selected as performance metrics.

Completion time refers to the total time required to complete all tasks, defined as in Equation (7):

Where: N represents the number of tasks; K represents the total number of virtual machines in the system.

Latency rate refers to the ratio of the actual latency incurred in executing tasks to the expected latency for executing those tasks. The expected latency refers to the minimum time required for processing the task. The definition of latency rate is as shown in Equation (8):

Where: ∑turnRound represents the latency incurred in executing tasks; ∑length represents the expected latency for executing tasks.

Success rate refers to the ratio of the number of tasks completed within the deadline to the total number of tasks.

3.3 Performance Analysis

Literature proposed real-time task processing (RTTP) algorithm, TWOCP algorithm, and IPSO algorithm as references for performance comparison analysis, considering the impact of task count and virtual machine count on the performance of each scheduling algorithm.

3.3.1 Impact of Task Count on Performance

First, the impact of task count on completion time, latency rate, success rate, and average turnaround time was analyzed, with task counts varying from 27 to 510, while the number of virtual machines was fixed at 12.

The variation of completion time with task count is shown in Figure 4. It can be seen that completion time increases with the number of tasks. This is expected: the more tasks there are, the heavier the processing load, requiring more resources, thereby increasing the time consumed in processing tasks. Compared to RTTP, IPSO, and TWOCP algorithms, the FLTS algorithm shortened completion time. This is attributed to the FLTS algorithm selecting the least loaded virtual machine in the fog layer to execute tasks, thus reducing the latency for processing tasks.

Figure 4 Variation of Completion Time with Task Count

Figure 5 shows the variation of latency rate with task count. It can be seen that the latency rates of TWOCP, IPSO, RTTP, and FLTS algorithms all increase with the number of tasks, but the rate of increase varies. Compared to TWOCP, IPSO, and RTTP algorithms, the FLTS algorithm controlled the rate of increase of latency as the number of tasks increased. In heavier task environments (task counts of 300 and 500), the latency rate of the FLTS algorithm is much lower than that of TWOCP, IPSO, and RTTP algorithms.

Figure 5 Variation of Latency Rate with Task Count

Figure 6 presents the success rates of FLTS algorithm, RTTP, and IPSO, TWOCP algorithms. It can be seen that the success rate decreases with the increase in task count. The reason is that as the number of tasks increases, the system load becomes heavier, resource competition intensifies, reducing the number of tasks successfully completed within the deadline, ultimately decreasing the success rate.

Figure 6 Variation of Success Rate with Task Count

Moreover, compared to RTTP and IPSO algorithms, the FLTS algorithm still maintains a high success rate. The FLTS algorithm considers not only the task deadlines during task scheduling but also the transmission latency, optimizing the task scheduling strategy. However, in heavy task environments, the success rate of the FLTS algorithm is lower than that of the TWOCP algorithm. This is because the TWOCP algorithm uses clustering algorithms for task clustering. The more tasks there are, the more evident the performance advantages of clustering algorithms.

3.3.2 Impact of Virtual Machine Count on Performance

This section analyzes the impact of virtual machine count on completion time, latency rate, and success rate, with the number of tasks fixed at 60; the number of virtual machines varying from 12 to 120. The simulation results are shown in Figures 7 and 8.

The number of resources accessible in the fog layer is directly proportional to the number of virtual machines. In other words, the more virtual machines there are, the more resources available for processing tasks, improving task processing efficiency. Therefore, completion time and latency rate decrease as the number of virtual machines increases, as shown in Figures 7 and 8.

Figure 7 Variation of Completion Time with Virtual Machine Count

Figure 8 Variation of Latency Rate with Virtual Machine Count

Additionally, since the FLTS algorithm uses fuzzy logic to select some tasks for execution in the cloud layer, the number of tasks executed in the fog layer is less than that of RTTP, IPSO, and TWOCP algorithms. Therefore, the performance of the FLTS algorithm is superior to that of RTTP, IPSO, and TWOCP algorithms.

Finally, the impact of virtual machine count on success rate is analyzed, as shown in Figure 9. It can be seen that the success rate of the FLTS algorithm is better than that of RTTP, IPSO, and TWOCP algorithms. Furthermore, when the number of virtual machines is low, the advantage of the FLTS algorithm in terms of success rate performance is more significant. The fewer the virtual machines, the more tasks assigned to each virtual machine, but this increases waiting time.

Figure 9 Variation of Success Rate with Virtual Machine Count

4 Conclusion

This paper addresses the task scheduling problem between the fog and cloud layers, proposing a fuzzy logic-based task scheduling algorithm. This algorithm considers the computational capacity, storage space, bandwidth requirements for executing tasks, as well as the latency requirements of tasks. By optimally selecting virtual machines to execute tasks in the fog layer, the efficiency of task execution is improved. Simulation results indicate that the proposed FLTS algorithm enhances the success rate of task execution and reduces the latency of task completion.

This paper considers the requirements and constraints of tasks during scheduling. Future work will continue to address security and privacy issues and expand the FLTS algorithm to larger network environments.