An Efficient Task Scheduling Algorithm in the Cloud and Edge Collaborative Environment

I.   Introduction

With the advent of the 5G era, the continuous and rapid development of cloud computing and edge computing will bring more and more convenience to people’s lives. Cloud computing tasks are received, collected and processed in a centralized data center. The centralized structure facilitates the management of cloud computing [1], but it is difficult to respond to requests from mobile devices quickly and effectively [2]. In order to reduce the network transmission delay and network congestion from mobile devices to the cloud, edge computing places analysis and calculation at the edge of the network, which provides a solution to the long response delay problem of cloud computing [3], [4]. Although edge computing can provide fast response to services, it still has performance bottleneck due to its limited computing power, and cloud centers can share their unlimited computing and storage resources. Therefore, the collaboration between edge nodes and cloud centers has attracted more and more attention from enterprises [5], [6].

In the cloud and edge collaborative environment, there are still some challenges. Edge computing extends computing resources, communication resources, and storage resources to the edge of the network. There are a large number of computing-sensitive and delay-sensitive applications at the edge [7], [8], such as face recognition, virtual reality, human-computer interaction, and natural language processing, etc. These applications have very strict requirements for time delay. However, the key problem is that the computational capability of edge nodes is limited, and only processing tasks at the edge nodes themselves will bring a high load to the nodes and make it impossible for a large number of tasks to respond quickly. If tasks with high computing requirements are dispatched to the central cloud for processing, there will be another problem, that is, although the central cloud has powerful computing capabilities, the longer transmission distance between edge nodes and the cloud center will inevitably bring higher delays. Therefore, how to achieve low-latency task scheduling in a cloud and edge collaborative environment has become a key issue to be solved urgently.

In order to solve the above problems, under the cloud and edge collaboration environment, we not only consider the collaboration between edge nodes and the cloud center, but also consider the collaboration among edge nodes to better utilize the resources of other adjacent edge nodes. Specifically, when a task arrives at an edge node, if the edge node has sufficient resources, the task will be processed at this edge node without migrating to other nodes for execution. When the load of the edge node is too high, tasks on this node can be migrated to other adjacent edge nodes which takes full advantage of nearby low-load nodes to share the pressure of high-load nodes, and they can also be scheduled to cloud centers for processing. In summary, we strive to find a task scheduling scheme in the cloud and edge collaborative environment, which aims to take full advantage of edge node and cloud center resources to maximize the number of tasks that can completed and meet the users’ low-latency requirements. The main contributions of this article are as follows:

• In order to make full use of the computing resources of edge nodes and the cloud, this paper considers the vertical collaboration between edge nodes and the cloud center and the horizontal collaboration among edge nodes, and proposes a task scheduling strategy in this environment which aims to maximize the number of tasks that can be completed under the constraint of the latest completion deadline.

• An edge node clustering algorithm (ENCA) according to the communication range of edge nodes is proposed. Tasks can be scheduled within the cluster. ENCA narrows the feasible domain of task scheduling decision and reduces the search time of scheduling strategy.

• The clustering is transformed into a bipartite graph, and a scheduling algorithm based on maximum matching (SAMM) is designed to find a local optimal strategy. Combining the above two algorithms, a task scheduling algorithm (ENCA+SAMM) suitable for the cloud-edge and edge-edge collaborative environment is obtained.

The rest of this paper is organized as follows. Section II discusses related work. The task scheduling model is introduced in Section III. In Section IV, we propose a task scheduling strategy based on bipartite matching. Section V discusses the experimental results in a simulation environment, which confirms the effectiveness of the method. Finally, Section VI draws the conclusion and outlines future work.

II.   Related Work

In edge environments, researchers have done a lot of work on task scheduling to meet the latency requirements of the tasks. When it came to the solving of task execution delays, Miao et al. [9] used long and short-term memory (LSTM) to predict computing tasks, and designed a prediction-based computing offloading strategy that minimizes the response delay in an edge computing environment. Yuan et al. [10] used online learning to estimate network conditions and server loads in real time, and then dynamically assigned the task to the best edge server. At the same time, in each edge server, an online task dispatching and fair scheduling (OTDS) method is proposed by combining the loop mechanism with deep reinforcement learning, which can allocate appropriate resources for each task according to the time sensitivity of each task to achieve efficient task scheduling. Zhao et al. [11] designed a collaborative computing offloading and resource allocation optimization scheme and a distributed computing offloading and resource allocation algorithm to reduce task execution delay. Xu et al. [12] proposed a multi-objective evolutionary algorithm based on decomposition (MOEA/D) to minimize transmission delay and maximize resource utilization. Zheng et al. [13] proposed an extended Hungarian algorithm in an edge computing environment to obtain smaller delays and achieve sustainable services. Edinger et al. [14] proposed a decentralized low-latency task scheduling method that can minimize job execution time. Sun et al. [15] were committed to computing offloading in the edge computing environment, and proposed a solution to the time delay minimization problem with energy consumption constraints.

When it came to reducing the energy consumption of task scheduling in edge environments, Dinh et al. [16] aimed to find a multi-task offloading solution to multiple different access points and edge servers, and to achieve the joint goal of minimizing delay and energy consumption. Xu et al. [17] proposed a multi-objective evolutionary algorithm based on NSGA-II to optimize the offloading time of computing tasks and the energy consumption of edge nodes at the same time. Zhang et al. [18] studied the problem of minimizing the energy cost of offloading tasks to multiple nodes. Subsequently, they modeled energy consumption from task calculation and communication respectively, and a scheme based on artificial fish swarm algorithm was developed to solve the energy optimization problem [19].

In summary, although some of the current work in the edge environment can meet the latency requirements of tasks, the adoption of machine learning algorithms and meta-heuristic algorithms in the edge environment brings a large computational latency due to the limitation of its own resources and computational capacity. Meanwhile, edge nodes often face the problem of insufficient capacity when dealing with computationally intensive and latency-sensitive applications. Hence, researchers start to take advantage of cloud computing and focus on task scheduling in cloud and edge collaborative environments.

In the cloud and edge collaborative environment, the task scheduling problem becomes more complicated. More researchers mainly focus on energy consumption in a cloud and edge collaborative environment. Long et al. [20] used game theory to solve the task scheduling problem in the cloud and edge collaborative environment, and it was constructed as a non-cooperative game among multi-agents. For each agent, they defined a function about the expected cost of a task as its utility function, and they tried to minimize the function value under user quality of service constraints. Tan et al. [21] studied the online task scheduling algorithm in the cloud and edge system to minimize the total response time of all tasks. Long et al. [22] studied offloading tasks of applications to edge servers or the cloud to minimize energy consumption. Du et al. [23] discussed computing offloading in a cloud and edge collaborative environment, and designed a heuristic task offloading algorithm to save overhead. Liu et al. [24] studied the energy saving problem of multiple devices, expressed the problem as a 0-1 nonlinear integer programming one, and proposed an iterative decoupling algorithm composed of decision variable relaxation and convex optimization to obtain approximate optimal decision making. Duan et al. [25] constructed a prediction algorithm based on fractal mathematics, and designed an improved ant colony algorithm based on the prediction results to search the scheduling strategy, which minimizes energy consumption while ensuring the QoS of users. Gai et al. [26] proposed a novel task allocation algorithm between heterogeneous cores and mobile cloud to reduce the total energy consumption of mobile heterogeneous embedded systems. Li et al. [27] focused on the parallel job scheduling problem composed of a set of independent tasks, and considered the energy consumption in the scheduling process. They proposed an algorithm to solve the single-task scheduling problem and designed an online scheduler. Peng et al. [28] proposed three constrained multi-objective evolutionary algorithms to solve the problem of computing offloading supporting the Internet of things in cloud and edge collaborative environment. Wang et al. [29] proposed a task scheduling algorithm based on the Cataclysm strategy on the basis of genetic algorithm, which realized the goal of minimum total execution time.

Task scheduling in cloud and edge collaborative environments solves the problem of insufficient computing power at the edge nodes, but it also brings some new problems along with it. If tasks generated by mobile devices are simply scheduled to the nearest edge node, it can lead to too many mobile devices competing for limited computational resources, resulting in load imbalance and performance degradation at the edge nodes. In the above work, they can execute tasks inside the edge nodes or offload them to the cloud. However, these approaches do not fully utilize the resources of the adjacent edge nodes.

Compared to previous work, we consider scheduling tasks in the environment of cloud-edge collaboration and edge-edge collaboration. Meanwhile, to reduce the computational latency, we consider clustering the edge nodes to reduce the size of the search space. First, a heuristic algorithm is used for all nodes to filter out the tasks that the edge nodes can handle by themselves, which significantly reduces the computation time for task scheduling. Then, for the remaining tasks, we use bidirectional matching to schedule them to other edge nodes within the cluster to obtain the overall optimal allocation result.

III.   Framework for the Model

As illustrated in Figure 1, We consider the system with one cloud center and $m$ edge nodes is denoted by a set ${{E}}=\{E_1,E_2,\ldots,E_m\}$. Edge node $i$ is denoted as $E_i=({\rm{lx}}_i,{\rm{ly}}_i,p_i)$, where ${\rm{lx}}_i$ and ${\rm{ly}}_i$ represent the two-dimensional coordinates of edge node $i$, respectively, and $p_i$ is the computational capability of edge node $i$. $C=({\rm{bw}}_c,p_c)$ is used to denote the cloud center, where ${\rm{bw}}_c$ and $p_c$ represent bandwidth and computational capability of the cloud center, respectively. $p_i$ and $p_c$ are measured by the CPU clock speed (i.e., the number of CPU cycles per second). In this paper, we assume that edge nodes have received computation tasks from mobile computing devices. Therefore, they all have a task processing queue. Each edge node can decide where the task will be processed, such as being processed at the current edge node, or migrated to another edge node, or uploaded to the cloud center. We denote ${\cal{J}}_{ij}= (L_{ij}, S_{ij},D_{ij})$ as the $j$-th computation task in the edge node $i$, where $L_{ij}$ is the input data-size of the task, $S_{ij}$ represents the number of CPU cycles required to accomplish one-bit data of ${\cal{J}}_{ij}$, and $D_{ij}$ denotes the deadline of the computation task ${\cal{J}}_{ij}$. Note that the information of computation task is known by the scheduler in advance. Moreover, each edge node connects with the others through a wireless channel, and edge nodes communicate with the cloud center through different backhaul links.

Figure  1.  System model representation of the concept lattice.

DownLoad: Full-Size Img PowerPoint

Therefore, the problem to be studied in this paper can be described as how to determine the processing location of the task, that is, execute it on the local node or migrate to another edge node or upload to the cloud, so as to maximize the number of computing tasks that meets the deadline constraint.

1   Computation model

We model both the edge node and the cloud center as a single service system, which means that tasks have to wait to be computed (i.e., there is a waiting time before task processing). The number of CPU cycles needed for accomplishing the computation task ${\cal{J}}_{ij}$ is $L_{ij}S_{ij}$. According to the computation model in [30] and [31], the computation delay for processing task ${\cal{J}}_{ij}$ at edge node $k$ can be expressed as

where ${\rm{WT}}_{ij}^k$ is the waiting time for computation task ${\cal{J}}_{ij}$ in edge node $E_k$. Similarly, the computation delay for task ${\cal{J}}_{ij}$ in cloud center is denoted by

where ${\rm{WT}}_{ij}^c$ is the waiting time for computation task ${\cal{J}}_{ij}$ at the cloud center. ${\rm{WT}}_{ij}^k$ and ${\rm{WT}}_{ij}^c$ may change when the scheduling strategy changes, their values are closely relevant to the decision of edge nodes. Since the paper does not consider the problem of the device layer, the edge node channel is smooth enough, ignoring the time of task transmission between nodes. The transmission time ${\rm{TT}}_{ij}$ of task $j$ from edge node $i$ to cloud center is

where ${W_c}^{-1}$ represents the time required for the backhaul line to transmit 1 bit data [32], [33].

2   Problem formulation

Edge nodes will make decisions at the beginning of a time interval, and schedule the tasks which arrive at the last time interval. Denote the time interval of all edge nodes and the cloud center is $\tau$. There are $m$ edge nodes ${{E}}=\{E_1,E_2,\ldots,E_m\}$, and we assume that edge node $E_i$ has to deal with $n_i$ computation tasks ${{{\cal{J}}_i}}=\{{\cal{J}}_{i1},{\cal{J}}_{i2}, \ldots,{\cal{J}}_{in_i}\}$. We ignore tasks with a deadline bigger than $\tau$ in this paper. Actually, those tasks are non-delay sensitive in general, they are more suitable for uploading to the cloud for processing. For all tasks waiting for scheduling, we try to maximize the number of computation tasks satisfying the constraint of deadline. For the beauty of the formula, we denote $M^+=\{1,2,\ldots,m\}$, $M^-=\{1,2,\ldots,m+1\}$, $N_i=\{1,2,\ldots,n_i\}$. Let $x_{ijk}$ represents the processing decision of tasks, which can be defined as follows:

Then, the optimization problem is defined as follows:

where $k=m+1$ means that the task will be uploaded to the cloud center.

Equation (6) guarantees that each task will be allocated to only one device. Equation (7) indicates that computing requirements of all tasks assigned to an edge node must be less than the computational capability that the edge node can provide. Equations (8) and (9) are the deadline constraints of each task.

If the value of all tasks is regarded as 1, and the execution length ($L_{ij}S_{ij}$) of the task is regarded as the weight of the task. Edge nodes and cloud center are regarded as knapsacks. The knapsack size is the product of computational capability and time interval ($p_i\tau$). Then, equation (7) means the sum weight of items which is allocated to knapsack $k$ is less than the capacity of knapsack $k$, equations (8) and (9) are the assignment constraints. Then, the optimization problem can be converted to a multiple knapsacks problem with assignment restrictions (MKAR) which has been proved to be a strongly NP-hard problem [34]. It is hard to find the optimal solution and dynamic programming is impractical for it [35]. In addition, edge nodes are distributed on the edge of the network, and they provide low latency services for customers. Therefore, meta-heuristic algorithms which have large algorithm execution delay are impractical in edge computing environment.

Since the primal problem is a NP-hard problem, and edge nodes have high real-time requirements. Designing a heuristic algorithm to find a local optimal solution is an appropriate approach. The problem can be turned into a typical single core task scheduling problem when only considering an edge node without the cloud center. Thus, we can use a single core task scheduling algorithm, which has been full researched, to decide which tasks are processed on local node. If all nodes employ a single core task scheduling algorithm first (we call it as the filtering method in the rest of the paper), then the whole system can be turned to a bipartite graph as shown in Figure 2.

Figure  2.  Bipartite graph.

DownLoad: Full-Size Img PowerPoint

The yellow vertexes (underload nodes) represent edge nodes which can finish all tasks belonging to them and adhere to all task completion time constraints, the other edge nodes are the blue vertexes (high load nodes), the cloud center is the green vertex. Let $m^\prime$ denote the number of high load nodes, the number of underload nodes is $m-m^\prime$, then the number of the cloud data center is defined as $m-m^\prime+1$. After filtering method, most of computation tasks in ${{{\cal{J}}_i}}$ will be processed on the edge node $E_i$. We assume the number of remaining tasks is $n_i^\prime$. Then, problem P1 can be rewritten as

and the constraints are similar to (5)–(9), but $(M^+, M^-, N_i, x_{ijk})$ is changed to $({{\cal{M}}^+}, {{\cal{M}}^-}, \,{\cal{N}}_i, \, y_{ijk})$, accordingly, in which ${{\cal{M}}^+}=\{1,2,\ldots, m^\prime\}$, ${{\cal{M}}^-}= \{1,2,\ldots,m-m^\prime, m-m^\prime+1\}$, and ${\cal{N}}_i=\{1,2,\ldots,n_i^\prime\}$. It is easy to find that the feasible region is reduced through the filtering method, $n_i^\prime$ might be much less than $n_i$, and $||{{\cal{M}}^+}|| + || {{\cal{M}}^-} || = ||M^-||$. $||M^-||$ denotes the overall set of edge nodes and cloud nodes in P1. In addition, the precedence relations between tasks can be ignored, i.e., there is a specific collation by using the filtering method.

IV.   Scheduling Algorithm

We have described the original scheduling problem and analyzed that it is difficult to solve the problem in polynomial time. Therefore, in this section, we first adopt a filtering method to reduce the number of tasks to be scheduled. Even in this way, the solution space is still too huge to satisfy the real-time requirements of tasks in the edge computing environment. Furthermore, in order to further reduce the solution space, we propose an adaptive clustering algorithm based on the communication range of the edge node to cluster edge nodes. Finally, we provide a scheduling algorithm based on maximum bipartite matching for every clustering.

1   Edge node clustering algorithm

Edge nodes communicate with each other through a wireless network, and each node has a communication range. When an edge node wants to migrate tasks to a distant edge node, it may need to request some intermediate nodes to help with the transmission work. There will be much more transmission time and higher network load in this way. Therefore, we design an adaptive clustering algorithm based on the communication range of edge nodes, named edge node clustering algorithm (see Algorithm 1).

We improve the naive K-means algorithm to an adaptive clustering algorithm based on the communication range of edge nodes. The steps of the algorithm are as follows. First, it initializes the cluster list, and randomly selects $k$ centroids (lines 1−2). Second, each edge node calculates its distance to the centroid of each cluster, and adds the closest cluster to it (lines 5−7). Then, it finds the point farthest from the centroid of all edge nodes. If the distance between this node and the centroid is greater than ${r}/{2}$, it moves the node out of the cluster and creates a new cluster. The centroid of the new cluster is the coordinates of the node (lines 9−11). Later, it updates clusters, deletes empty clusters (line 12) and updates the centroid of each cluster (line 13). Finally, it determines whether each centroid has been changed, and returns the results if there is no change. Otherwise, it repeats lines 4−13.

2   Scheduling algorithm based on bipartite matching

This section describes the task scheduling algorithm. It can be seen from Section III that after all edge nodes use the heuristic algorithm to preprocess tasks, the blue nodes in Figure 2 have a queue of tasks to be scheduled, while the yellow and green nodes have remaining computing resources. Because the cloud center is far away, considering that if the task cannot be completed within the cluster, it will be transferred to the cloud center for completion. To convert the set of edge nodes into a bipartite graph, the first task in the to-be-scheduled task queue of the blue node $E_i$ can be scheduled to the yellow node $E_j$, if and only if the following two conditions are met:

a) After the scheduling is completed, the tasks that needed to be processed by the yellow node $E_j$ itself meet the latest completion deadline.

b) After the scheduling is completed, the current scheduling tasks meet the latest completion deadline.

Satisfying the above two conditions means that $E_i$ can match $E_j$, that is, there exists a line connecting $E_i$ to $E_j$ in the bipartite graph. Through a bipartite graph, a maximum match is found which determines the task schedulable task relationship. If no match can be found, tasks to be scheduled will be uploaded to the cloud center. The search for the maximum match will be repeated until the number of blue nodes is 0. The specific process is described in Algorithm 2.

The SAMM algorithm considers each cluster in turn. For a cluster, it uses a heuristic algorithm for all nodes to determine the blue (${\rm{migSide}}$) and yellow node set (${\rm{recSide}}$), and sorts all the blue nodes’ pending task queues in ascending order according to the execution length of the tasks (lines 2−3). Then, it transforms the relationship among nodes into a bipartite graph through conditions a) and b) and ${\rm{migSide}}$, ${\rm{recSide}}$, and finds the bipartite graph maximum matching (lines 5−6);

For the blue node matched, it tries to transfer multiple tasks at once. And for the blue node that does not find a match, it uploads the first task of the node’s pending task queue to the cloud (lines 7−11). Finally, it updates ${\rm{migSide}}$ and ${\rm{recSide}}$. If there are still edge nodes that need to schedule tasks, it repeats (lines 5−12).

The time complexity of ENCA+SAMM is analyzed in the following. Algorithm 1 (ENCA): 1) Determine whether the center of mass has changed (lines 3), which costs $O(n)$; 2) Traverse all edge nodes to calculate the distance to the centroid of each cluster (lines 5−6), which costs $O(n)$. Therefore, the total time complexity of Algorithm 1 is $O(n^2)$. Algorithm 2 (SAMM): 1) Traverse all nodes within all clusters (lines 1), which costs $O(n^2)$; 2) Sort according to task length (lines 2−3), which costs $O(n{\rm{log}}2^n)$; 3) Traverse all blue nodes and find the largest match of the bipartite graph (lines 4−6), which costs $O(n)$, Therefore, the total time complexity of Algorithm 2 is $O(n^3)$. Therefore, the time complexity of ENCA+SAMM is $O(n^3)$.

V.   Performance Evaluation

This section conducts experiments and demonstrates the performance of the proposed algorithm by designing a cloud and edge collaborative simulation environment. As shown in Table 1.

Table  1.  Experimental parameter table of heuristic task allocation

Parameter	Value
$m$	(85, 150)
${\rm{power}}_i$	(0, 100) GHz
$r$	10 m
$t$	0.5 s
$D_{ij}$	(0, 0.5) s
$L_{ij}$	(0, 20000) bit
$S_{ij}$	(200, 1000)
${\rm{bw}}_{c}$	1000 Mbps
${\rm{power}}_c$	10 GHz
$k$	12
$\epsilon$	1E−10
Upper limit of task numbers	[100, 300, 500, 800, 1000]

 | Show Table

DownLoad: CSV

The number of edge nodes m is randomly generated in (85, 150). The coordinates ${\rm{lx}}_i$ and ${\rm{ly}}_i$ of the edge nodes are random values in (0, 100). And the computational capability ${\rm{power}}_i$ of the node is randomly selected from [1, 2, 3, 4] GHz. The communication radius $r$ is 10 m. The properties of the task are configured as follows. The data size of the task $L_{ij}$ takes a random value within (0, 20000) bit. The clock cycle required to consume 1 bit data is randomly obtained within (200, 1000), and the latest completion period is within the range of (0, 0.5) s (allocation time interval is 0.5 s). The bandwidth ${\rm{bw}}_c$ of the cloud center is 1000 Mbps. The computational capability of the cloud center is 10 GHz. Assume that the number of tasks that the node needed to be assigned take the random value in these five groups (0, 100), (0, 300), (0, 500), (0, 800), (0, 1000). The initial number of clusters $k$ is 12. The experiments are carried out on a computer with a CPU model of i7 8700k and a memory of 16 GB.

Firstly, we evaluate the heuristic algorithm used by the edge nodes, and further explain the clustering algorithm and the SAMM algorithm.

Figure 3 shows the distribution of edge nodes, the location of the cluster centroids (orange point) and the communication range of the centroids. Through the ENCA algorithm, edge nodes are divided into 25 clusters. It can be observed that there is at least one node in the communication range of all cluster centroids, which is not included in the communication range of other cluster centroids. That is, the clusters obtained by the ENCA algorithm will not be superfluous, and at the same time, the communication between any edge nodes within the cluster does not need to be transferred through other nodes.

Figure  3.  Distribution of edge nodes.

DownLoad: Full-Size Img PowerPoint

We choose two non-preemptive task scheduling algorithms to test the performance of the heuristic algorithm inside the edge nodes, which are based on 100 random experiments to select the best. The two algorithms are as follows: 1) Earliest deadline first (EDF): It gives priority to tasks with earlier deadlines; 2) Shortest task first (STF): It gives priority to tasks with shorter execution time. Generally speaking, STF can complete more tasks inside edge nodes, but due to the latest completion deadline for tasks, the scheduling performance inside nodes is not as good as EDF. Compared to the STF algorithm, tasks in EDF algorithm with later completion deadlines, which indicates that tasks have more time margin to wait to be scheduled execution at the current node to meet the tasks’ latest completion deadline. As a result, the EDF algorithm ensures that more tasks are completed within the node, i.e., fewer tasks need to be migrated secondarily to other nodes for execution. And from a global perspective, EDF performance is even better. As shown in Figure 4, when the maximum number of tasks on the nodes are 100, 300, 500, 800, and 1000, EDF completes more tasks inside the edge node compared to STF, and fewer tasks are needed to be migrated twice for execution.

Figure  4.  Performance comparison of edge nodes under STF and EDF.

DownLoad: Full-Size Img PowerPoint

Figure 5 shows the number of tasks that violates the deadlines in the system after applying these two algorithms. Obviously, compared to STF, the number of tasks that violate deadlines in EDF is smaller. In summary, the performance of the EDF algorithm is more excellent, so in all subsequent experiments, the EDF algorithm will be adopted for task filtering inside the edge nodes.

Figure  5.  Global performance comparison under STF and EDF.

DownLoad: Full-Size Img PowerPoint

The above experiments determine the heuristic algorithm used internally by the edge nodes. The following experiment will show the effectiveness of our proposed SAMM algorithm. Since SAMM algorithm is based on bipartite matching and uses both shortest task first technology and hill climbing method, we choose the following algorithms which may be the naive algorithm or only take one improvement method: the general bipartite matching (BM) strategy, the BM algorithm for shortest job first ($\rm BM\_Sort$), and the BM algorithm based on the hill climbing ($\rm BM\_Climb$). Our SAMM algorithm gives priority to small tasks, and uses the hill climbing to try to match as many tasks as possible at one time to get close to the local optimum, while reducing the number of searches for bipartite matching (searching for binary matching is time-consuming).

Figure 6 shows the total number of tasks that needed to be migrated to other edge nodes under different task scales. A larger value indicates that more tasks are scheduled to other edge nodes. We try to maximize the number of tasks that can be completed by making full use of the resources of other edge nodes. Obviously, SAMM still performs well under high load, and there is almost no difference between the effects of BM and $\rm BM\_Climb$, and the performance drops severely when the system is under high load. The experimental results of BM and $\rm BM\_Climb$ show that the experimental results are not ideal when the hill climbing method is used alone without reducing the number of binary matching. From the experimental results of SAMM and $\rm BM\_Sort$, it can be seen that the performance of the algorithm can be further optimized by using the hill climbing method in the case of shortest task first.

Figure  6.  The improvement effect of SAMM.

DownLoad: Full-Size Img PowerPoint

Then, we evaluate the performance of the proposed algorithm (ENCA+SAMM) and some benchmark algorithms. Our proposed ENCA+SAMM algorithm is first clustered according to the distance of edge nodes, and then mainly consideres migrating the unfinished tasks on the nodes to other edge nodes in the cluster or to the cloud center for execution. Therefore, when designing the comparison algorithm, the main concern is whether the tasks can be migrated to other nodes for execution and the range of target nodes for migration (target nodes belong to the same cluster or cloud center). The benchmark algorithms adopted in this paper are as follows:

Edge with no offloading (EWNO): Tasks only run on the edge nodes to which they belongs, and will not be scheduled to other edge nodes and the cloud center;

Edge with offloading (EWO): Tasks can run on the edge nodes to which they belongs, or be scheduled to other edge nodes;

Edge with clustering (EWC): Tasks can run on the edge nodes to which they belongs, or be scheduled to any nodes in the same cluster;

Edge cloud with offloading (ECWO): Tasks can run on the edge nodes to which they belongs, and can also be scheduled to other nodes or uploaded to the cloud center.

Among them, EWO and ECWO ignore the communication range of edge nodes, that is, tasks can be directly scheduled to any nodes. EWC uses the clustering algorithm designed in this paper to cluster edge nodes. The main performance comparison parameters are the total number of tasks that can be completed in the system, the total number of migration tasks between edge nodes, the running time, and the average task completion rate of nodes ($\delta$):

We compare the running time of each algorithm (except EWNO, because it does not schedule tasks), as shown in Figure 7. It can be seen from the figure that our ENCA+SAMM is far superior to EWO and ECWO in terms of running time, especially under high load conditions. The running time of our algorithm is only 2.1 seconds, while that of EWO and ECWO are 81.4 seconds and 48.2 seconds, respectively. EWC only schedules tasks within the cluster, while ENCA+SAMM schedules tasks within the cluster or the cloud, which slightly increases the range of solution space, so the performance of the two is comparable.

Figure  7.  The running time of different algorithms.

DownLoad: Full-Size Img PowerPoint

Figure 8 compares the number of tasks that can be completed by edge nodes themselves or other edge nodes or the cloud under different algorithms. When the maximum number of tasks of the node is small, that is, the system load is low, the performance of ENCA+SAMM algorithm is slightly inferior to that of ECWO and EWO. This is because there are many solutions when the system load is small, and the clustering algorithm used by the ENCA+SAMM algorithm limits the range of nodes that can be selected for the task. However, ECWO and EWO do not consider the communication range of nodes, and the running time of them are very long (see Figure 7), which cannot meet the real-time requirements. With the increase of the maximum task number of nodes, ENCA+SAMM shows obvious advantages. For example, when the maximum number of tasks for each edge node is 1000, our strategy increases the number of completed tasks that meet the latest deadline constraint by 32%–47.2% to other comparison algorithms, which shows that our method has superior performance when the system load is large.

Figure  8.  Comparison of the number of tasks completed.

DownLoad: Full-Size Img PowerPoint

Figure 8 shows the total number of tasks that can be completed while meeting deadline constraints, and the comparative effect of the number of migration tasks of each algorithm is shown in Figure 9. The number of task migrations in the figure represents the number of tasks that can be completed by mutual assistance between edge nodes and meet the deadline requirements. Since ECWO and EWO do not consider the communication range of edge nodes, the performance is better when the solution space is not complicated (the system load is low). When the solution space becomes complicated (each node has a relatively high load), the performance of ECWO and EWO starts to be unsatisfactory, which is almost the same as EWC, and EWC considers the communication range of nodes. At the same time, because ECWO and EWO use the same scheduling strategy, the broken lines overlap. It can be seen from the figure that ENCA+SAMM steadily increases the total number of task migrations when the load gradually increases. Therefore, when the load is high, our algorithm can migrate more tasks to other edge nodes and show better performance.

Figure  9.  Comparison of the number of tasks migrated between edge nodes.

DownLoad: Full-Size Img PowerPoint

Figure 10 shows the number of tasks that the five algorithms can complete while meeting the deadline constraints when the maximum number of tasks on a node is 1000, through the node itself or to schedule tasks to other edge nodes or the cloud. Among the comparison algorithms, only ECWO takes into account the situation of the cloud, but from the experimental results, it can be seen that the total number of completed tasks (the sum of red, yellow and blue bars in Figure10) of our algorithm is far superior to ECWO and the other algorithms. Among them, compared with ECWO, the number of tasks transferred to the cloud by our algorithm has increased by 15.8%, the number of tasks transferred to other nodes has increased by 33%, and the number of tasks completed by the node themselves has increased by 53%. To make it clearer, we show the number of tasks completed by ENCA+SAMM in different locations under different loads, as shown in Figure 11. As can be seen from the figure, as the load increases, our algorithm can better utilize the resources of other edge nodes and the cloud to complete more tasks.

Figure  10.  Comparison of the number of tasks completed in different locations.

DownLoad: Full-Size Img PowerPoint

Figure  11.  Number of tasks completed by ENCA+SAMM in different locations.

DownLoad: Full-Size Img PowerPoint

Finally, the average task completion rate under different load conditions is compared, as shown in Figure 12. It is worth mentioning that the completed tasks here includes the tasks completed by the nodes themselves and other edge nodes and the cloud. Obviously, the five pentagons are particularly prominent on the ENCA+SAMM side, which shows that ENCA+SAMM performs best in terms of completion rate. At low load (the maximum number of tasks for a node is 100), all algorithms can basically complete all tasks. As the load increases, EWNO does not adopt a scheduling scheme, so the average task completion rate is very unsatisfactory, and ECWO, EWC, and EWO also perform poorly. When the maximum number of tasks arriving at the node is 1000, the average task completion rate of our algorithm can reach 82%, while other comparison algorithms are only 61% or lower.

Figure  12.  Average task completion rate.

DownLoad: Full-Size Img PowerPoint

All in all, our ENCA+SAMM strategy greatly reduces the solution search space and improves the response speed. Compared with the other benchmark algorithms, our strategy increases the number of completed tasks that meet the latest deadline constraint under different scenarios.

VI.   Conclusion

The rapid development of the Internet of Things and 5G era has accelerated the integration of cloud computing and edge computing. Edge computing can better meet the real-time requirements of edge devices, while cloud computing has powerful computing capabilities. In order to achieve unified management of resources on the edge and the cloud, cloud and edge collaboration is produced. In this paper, we propose a task scheduling strategy for edge nodes in the cloud and edge collaborative environment. The goal is to maximize the number of tasks that can be completed under the constraint of the deadline. Task scheduling is a strong NP-hard problem, and we solve it by designing a heuristic algorithm. Specifically, because edge nodes are more sensitive to delay, this paper designs a edge node clustering algorithm (ENCA) to reduce the solution space and reduce the algorithm running time. Then, we transform the task scheduling problem into a bipartite graph matching problem, and propose a task scheduling algorithm based on bipartite matching named SAMM for decision-making. Finally, the performance of our algorithm is verified through experimental results. The current research work investigates scheduling tasks that do not have dependencies. But practical scenarios exist for tasks with directed acyclic graph dependencies (workflow tasks). Scheduling these tasks requires attention to the sequence of tasks. Therefore, we will further research on workflow tasks in the future.