Integer particle swarm optimization based task scheduling for device-edge-cloud cooperative computing to improve SLA satisfaction

Resource and task model

For our problem formulation, we consider the DE3C environment with M user devices, E edge servers, and V cloud VMs. Without loss of generality, we use n_i, i ∈ [1, M + E + V] to represent these computing nodes, where n_i represent a device, an edge server, and a cloud VM respectively when i ∈ [1, M], i ∈ [M + 1, M + E], and i ∈ [M + E + 1, M + E + V]. The node n_i has C_i computing cores for processing tasks, and each core has g_i computing capacity which can be quantified by such as Hz, FLOPS, or any other computing performance metric. The network bandwidth is b_i,j (i ∈ [1, M], j ∈ [M + 1, M + E + V]) for transmitting data from device n_i to node n_j, which can be easily calculated according to the transmission channel state data (Du et al., 2019). If a device is not covered by an edge, i.e., there is no network connection between them, the corresponding bandwidth is set as 0.

In the DE3C environment, there are T tasks, t₁, t₂, …, t_T, requested by users for processing. We use binary constants x_o,i, ∀o ∈ [1, T], ∀i ∈ [1, M], to represent the ownership relationships between tasks and devices, as defined in Eq. (1), which is known. (1)${\displaystyle x_{o,i}=\left\{\begin{array}{c}1,\text{if}{t}_o\text{is launched by}{n}_i\hfill \\ 0,\text{else}\hfill \end{array}\right.,\forall o\in \left[1,T\right],\forall i\in \left[1,M\right].}$

Task t_o has r_o computing length for processing its input data with size a_o, and requires that it must be finished within the deadline d_o¹. Without loss of generality, we assume that d₁ ≤ d₂ ≤ ... ≤ d_T. To make our approach universal applicable, we assume there is no relationship between the computing length and the input data size for each task.

Task execution model

When t_o is processed locally, there is no data transmission for the task, and thus, its execution time is (2)${\displaystyle {\tau }_o=\sum _{i=1}^M\left(x_{o,i}\cdot \frac{r_o}{g_i}\right),\forall o\in \left[1,T\right].}$ In this paper, we consider that each task exhausts only one core during its execution, as done in many published articles. This makes our approach more universal because it is applicable to the situation that each task can exhaust all resources of a computing node by seeing the node as a core. For tasks with elastic degree of parallelism, we recommend to referring our previous work (Wang et al., 2019a) which is complementary to this work.

Due to EDF scheme providing the optimal solution for SLA satisfaction maximization in each core (Pinedo, 2016), we can assume all tasks assigned to each core are processed in the ascending order of deadlines when establishing the optimization model. With this in mind, the finish time of task t_o when it processed locally can be calculated by (3)${\displaystyle f{t}_o=\sum _{i=1}^M\sum _{q=1}^{C_i}\left(y_{o,i,q}\cdot \sum _{w=1}^o\left(y_{w,i,q}\cdot {\tau }_w\right)\right),\forall o\in \left[1,T\right],}$

where y_o,i,q indicates whether task t_o is assigned to the qth core of node n_i, which is defined in Eq. (4). ${\sum }_{w=1}^{o-1}\left(y_{w,i,q}\cdot {\tau }_w\right)$ is the accumulated sum of execution time of tasks which are assigned to qth core of m_i and have earlier deadline than t_o, which is the start time of t_o when it is assigned to the core. Thus, ${\sum }_{w=1}^o\left(y_{w,i,q}\cdot {\tau }_w\right)$ is the finish time when t_o is assigned to qth core of n_i (i ∈ [1, M]). (4)${\displaystyle y_{o,i,q}=\left\{\begin{array}{c}1,\text{if}{t}_o\text{is assigned to}q\text{th core of}{n}_i\hfill \\ 0,\text{else}\hfill \end{array}\right.,o\in \left[1,T\right],i\in \left[1,M+E+V\right],q\in \left[1,C_i\right].}$

As each task cannot be executed by any device which doesn’t launch it, (5)${\displaystyle \sum _{q=1}^{C_i}{y}_{o,i,q}\le x_{o,i},\forall o\in \left[1,T\right],\forall i\in \left[1,M\right].}$

When a task is offloaded to the edge or the cloud tier, it starts to be executed only when both its input data and the core it is assigned are ready. Based on the EDF scheme, the ready time of input data for each task assigned to a core in an edge server or a VM can be calculated as (6)${\displaystyle r{t}_o=\sum _{i=M+1}^{M+E+V}\sum _{q=1}^{C_i}\left(y_{o,i,q}\cdot \sum _{w=1}^o\left(y_{w,i,q}\cdot \frac{a_w}{b_{w,i}^T}\right)\right),\forall o\in \left[1,T\right],}$

where rt_o is the ready time of input data for task t_o when the task is offloaded to an edge server or a cloud VM, respectively. For ease of our problem formulation, we use $b_{o,i}^T$ to respectively represent the network bandwidths of transferring the input data from the device launching t_o to n_i (i ∈ [M + 1, M + E + V]). That is to say, $b_{o,i}^T={\sum }_{k=1}^M\left(x_{o,k}\cdot b_{k,j}\right)$. Then the transmission time of the input data for t_o is $a_o/b_{o,i}^T$ when it is offloaded to n_i). With the EDF scheme, the ready time of the input data for an offloaded task is the accumulated transmission time of all input data of the offloaded task and other tasks which are assigned to the same core and have earlier deadline than the offloaded task, i.e., ${\sum }_{w=1}^o\left(y_{w,i,q}\cdot a_w/b_{w,i}^T\right)$ for task t_o when it is offloaded to qth core in n_i (i ∈ [M + 1, M + E + V]).

In this paper, we don’t consider employing the task redundant execution for the performance improvement. Thus, each task can be executed by only one core, i.e., (7)${\displaystyle \sum _{i=1}^M\sum _{q=1}^{C_i}{y}_{o,i,q}\le 1,\forall o\in \left[1,T\right].}$

We use z_o to indicate whether t_o is assigned to a core for its execution, where z_o = 1 means yes and z_o = 0 means no. Then we have (8)${\displaystyle z_o=\sum _{i=1}^M\sum _{q=1}^{C_i}{y}_{o,i,q},\forall o\in \left[1,T\right].}$

And the total number of tasks which are assigned to computing cores for executions is (9)${\displaystyle Z=\sum _{o=1}^T{z}_o.}$

We use $f{t}_o^{off}$ to respectively represent the finish times of t_o when it is offloaded to the edge or cloud tier. For t_o assigned to a core, the core is available when all tasks that are assigned to the core and have earlier deadline than the task are finished. And thus, the ready time of the core for executing t_o is the latest finish time of these tasks, which respectively are (10)${\displaystyle r{c}_o=\sum _{i=M+1}^{M+E+V}\sum _{q=1}^{C_i}\left(y_{o,i,q}\cdot \underset{w<o}{max}\left\{y_{w,i,q}\cdot f{t}_w^{off}\right\}\right),\forall o\in \left[1,T\right].}$

The ready time of a task to be executed by the core it assigned to is the latter of the input data ready time and the core available time. The finish time of the task is its ready time plus its execution time. Thus, finish times of offloaded tasks are respectively (11)${\displaystyle f{t}_o^{off}=max\left\{r{t}_o,r{c}_o\right\}+\sum _{i=M+1}^{M+E+V}\sum _{q=1}^{C_i}\left(y_{w,i,q}\cdot \frac{r_o}{g_i}\right),\forall o\in \left[1,T\right].}$

Noticing that when a task is assigned to a tier, finish times of the task in other two tiers are both 0, as shown in Eqs. (3), and (11). Thus, the deadline constraints can be formulated as (12)${\displaystyle f{t}_o+f{t}_o^{off}\le d_o,\forall o\in \left[1,T\right].}$

As the occupied time of each computing node is the latest usage time of its cores², and the usage time of a core is the latest finish time of tasks assigned to it. Therefore, the occupied times of computing nodes are respectively (13)${\displaystyle o{t}_i=\underset{q\in \left[1,C_i\right]}{max}\left\{\underset{o\in \left[1,T\right]}{max}\left\{y_{o,i,q}\cdot f{t}_o\right\}\right\},\forall i\in \left[1,M\right],}$ (14)${\displaystyle o{t}_i=\underset{q\in \left[1,C_i\right]}{max}\left\{\underset{o\in \left[1,T\right]}{max}\left\{y_{o,i,q}\cdot f{t}_o^{off}\right\}\right\},\forall i\in \left[M+1,M+E+V\right].}$

Then the total amount of occupied computing resources for task processing is (15)${\displaystyle \Theta =\sum _{i=1}^{M+E+V}\left(o{t}_i\cdot C_i\cdot g_i\right).}$

And the overall computing resource utilization of the DE3C system is (16)${\displaystyle U=\frac{\sum _{o=1}^T\left(y_o\cdot r_o\right)}{\Theta },}$

where the numerator is the accumulated computing length of executed tasks, i.e., the amount of computing resource consumed for the task execution.

Problem model

Based on above formulations, we can model the task scheduling problem for DE3C as (17)${\displaystyle \mathbf{Maximizing}Z+U}$

subject to (18)${\displaystyle \left(2\right)-\left(16\right),}$

where the objective Eq. (17) is maximizing the number of finished tasks (Z), which is considered as the quantifiable indicator of the SLA satisfaction in this paper, and maximizing the overall computing resource utilization (U) when the finished task number cannot be improved (noticing that the resource utilization is no more than 1). The decision variables include y_o,i,q (q ∈ [1, C_i], i ∈ [1, M + E + V], o ∈ [1, T]). This problem is binary nonlinear programming (BNLP), which can be solved by existing tools, e.g., lp_solve (Berkelaar et al., 2020). But these tools are not applicable to large-scale problems, as they are implemented based on branch and bound. Therefore, we propose a task scheduling method based on an integer PSO algorithm to solve the problem in a reasonable time in the next section.

Integer encoding and decoding

Our IPSO exploits the integer encoding method to convert a task assignment to cores into the position information of a particle. We first respectively assign sequence numbers to tasks and cores, both starting from one, where the task number is corresponding to a dimension of a particle position, and the value of a dimension of a particle position is corresponding to the core the corresponding task assigned to. For cloud VMs, we only number one core for each VM type as all VM instances with a type have identical price-performance ratio in real world, e.g., a1.* in Amazon EC2 (https://aws.amazon.com/). For each task, the number of cores which it can be assigned to is the accumulated core number of the device launching it and the edge servers having connections with the device plus the number of VM types. Thus, for each dimension in each particle position, the minimal value ($p_d^{min}$) is one representing the task assigned to the first core of the device launching the task, and the maximal value ($p_d^{max}$) is (20)${\displaystyle p_d^{max}=\sum _{i=1}^M\left(x_{d,i}\cdot C_i\right)+\sum _{i=1}^M\sum _{j=M+1}^{M+E}\sum _{b_{i,j}>0}\left(x_{d,i}\cdot C_j\right)+NV,}$

where NV is the number of cloud VM types. The subscript d represents the dimension in each particle position. The dth dimension is corresponding to the dth task, t_d.

For example, as shown in Fig. 2, assuming a DE3C consisting of two user devices, one edge server, and one cloud VM type. Each of these two devices and the edge server has two computing cores, respectively represented as dc₁₁ and dc₁₂ for the first device, dc₂₁ and dc₂₂ for the second device, and ec₁ and ec₂ for the edge server. Both devices have network connections with the edge, that is to say, tasks launched by these two devices can be offloaded to the edge for processing. Then for each task, there are five cores that the task can be assigned to, i.e., $p_d^{max}=5$ for all d. Each device launches three tasks, where the first three tasks, t₁, t₂, and t₃, are launched by the first device, and the last three tasks, t₄, t₅, and t₆, are launched by the second device. Then we numbered two cores of each device as 1 and 2, respectively. Two cores of the edge server are numbered as 3 and 4, respectively. And the VM type is numbered as 5. By this time, the particle position [2, 3, 2, 1, 4, 5] represents t₁ is assigned to dc₁₂, t₂ is assigned to ec₁, t₃ is assigned to dc₁₂, t₄ is assigned to dc₂₁, t₅ is assigned to ec₂, and t₆ is assigned to the cloud.

Given a particle position, we use the following steps to convert it to a task scheduling solution, as outlined in Algorithm 2: (i) we decode the position to the task assignment to cores based on the correspondence between them, illustrated above; (ii) with the task assignment, we conduct EDF for ordering the task execution on each core, which rejects tasks whose deadline cannot be satisfied by the core, as shown in lines 2–3 of Algorithm 2. By now, we achieve a task scheduling solution according to the particle position. After this, we can calculate the number of tasks whose deadlines are satisfied, and the overall utilization using Eqs. (13)–(16). And then, we can achieve the fitness of the particle using Eq. (19).

IPSO

The IPSO, exploited by our method to achieve the best particle position providing the global best fitness, consists of the following steps, as shown in Algorithm 3.

1. Initializing the position and the fly velocity for each particle randomly, and calculating its fitness.

2. Setting the local best position and fitness as the current position and fitness for each particle, respectively.

3. Finding the particle providing the best fitness, and setting the global best position and fitness as its position and fitness.

4. If the number of iterations don’t reach the maximum predefined, repeat step (5)–(7) for each particle.

5. For the particle, updating its velocity and position respectively using Eqs. (21) and (22), and calculating its fitness. Where υ_i,d and p_i,d are representing the velocity and the position of ith particle in dth dimension. lb_i,d is the local best position for ith particle in dth dimension. gb_d isthe global best position in dth dimension. ω is the inertia weight of particles. We exploit linearly decreasing inertia weight in this paper, due to its simplicity and good performance (Han et al., 2010). a₁ and a₂ are the acceleration coefficients, which push the particle toward local and global best positions, respectively. r₁ and r₂ are two random values in the range of [0, 1]. To rationalize the updated position in dth dimension, we perform rounding operation and modulo $p_i^{max}$ plus 1 on it. (21)${\displaystyle {\upsilon }_{i,d}=\omega \cdot {\upsilon }_{i,d}+a_1\cdot r_1\cdot \left(l{b}_{i,d}-{\upsilon }_{i,d}\right)+a_2\cdot r_2\cdot \left(g{b}_d-{\upsilon }_{i,d}\right),}$ (22)${\displaystyle p_{i,d}=\lceil p_{i,d}+{\upsilon }_{i,d}\rceil mod{p}_i^{max}+1.}$ The inertia weight update strategy and the values of various parameters (e.g., a₁ and a₂) have influences on the performance of PSO, which is one of our future works. One is advised to read related latest works, e.g., (Houssein et al., 2021a; Nabi & Ahmed, 2021), if interested to follow the details.

6. For the particle, comparing its current fitness and local best fitness, and updating the local best fitness and position respectively as the greater one and the corresponding position.

7. Comparing the local best fitness with the global best fitness, and updating the global best fitness and position respectively as the greater one and the corresponding position.

 
____________________________________________________________________________________________________________ 
Algorithm 3 IPSO 
____________________________________________________________________________________________________________ 
Input: the parameters of the IPSO. 
Output:  The global best particle position. 
  1:  generating the position and the velocity of each particle randomly; 
  2:  calculating the fitness of each particle by Algorithm 2; 
  3:  initializing the local best solution as the current position and the fitness for each particle; 
  4:  initializing the global best solution as the local best solution of the particle providing the best 
      fitness; 
  5:  while the iterative number don’t reach the maximum do 
  6:     for each particle do 
  7:         updating the position using Eq. (21) and (22); 
  8:         calculating the fitness of each particle by Algorithm 2; 
  9:         updating the local best solution; 
10:         updating the global best solution; 
11:  return  the global best solution; 
___________________________________________________________________________________________________________    

For updating particle positions, we only discretize them and limit them to reasonable space, which is helpful for preserving the diversity of particles. Existing discrete PSO methods limit both positions and velocity for particles, and exploit the interception operator for the limiting, which sets a value as the minimum and the maximum when it is less than the minimum and greater than the maximum, respectively. This makes the possibilities of the minimum and the maximum for particle positions are much greater than that of other possible values, and thus reduces the particle diversity, which can reduce the performance of PSO.

Complexity analysis

As shown in Algorithm 3, there are two layers loop, which has O(ITR⋅NP) time complexity, where ITR and NP are the numbers of the iteration and particles, respectively. Within the loop, the most complicated part is calling Algorithm 2 which is O(NC⋅(T/NC)²) = O(T²/NC) in time complexity on average, as shown in its lines 2–3, where NC is the number of cores in the DE3C system. T/NC is the average number of tasks assigned to each core, and O((T/NC)²) is the time complexity of EDF for each core on average. Thus, the time complexity of our IPSO based method is O(ITR⋅NP⋅T²/NC) on average, which is quadratically increased with the number of tasks.

For PSO or GA with binary encoding method, they have similar procedures to IPSO, and thus their time complexities are also O(ITR⋅NP⋅T²/NC). Referring to Bays (1977); B.V. & Guddeti (2018); Benoit, Elghazi & Robert (2021); Liu et al. (2019); Meng et al. (2020); Mahmud et al. (2020), time complexity of First Fit (FF) is O(T∗NC), and that of First Fit Decreasing (FFD), Earliest Deadline First (EDF), Earliest Finish Time First (EFTF), Least Average Completion Time (LACT), and Least Slack Time First (LSTF) are O(T²∗NC). In general, the numbers of the iteration and particles are constants, and all of above methods except FF exhibit quadratic complexity with the number of tasks.

SLA satisfaction

Figure 3 shows the performance of various task scheduling methods in maximizing the accumulated number, computing length, and processed data size of finished tasks. As shown in the figure, our method has about 36%, 46%, and 55% better performance than these heuristic methods, FF, FFD, EDF, EFTF, LACT, and LSTF, in these three SLA satisfaction metrics, respectively. This illustrates that meta-heuristic methods can achieve a much better performance than heuristic methods, due to their randomness for global searching ability. While, the performance of GA, PSO_srv, and BPSO are much worse than that of these heuristic methods, such as, our method achieves 953%, 115%, and 322% than GA, PSO_srv, and BPSO, respectively, more completed task number. This suggests us that meta-heuristic approaches must be carefully designed for a good performance.

Of these heuristic methods, EDF has the best performance in SLA satisfaction, as shown in Fig. 3, due to its aware of the task deadline, which is the reason why we exploit it for task ordering in each core.

Compared with BPSO, IPSO has 322%, 523%, and 313% better performance in three SLA satisfaction metrics, respectively. This provides experimental evidence that our integer coding method significantly improves the performance of PSO for task scheduling in DE3C. The main reason is that the searching space BPSO is much larger than IPSO due to their different represents to the same problem. For example, if there are 6 candidate cores, e.g., two device cores, four edge server cores, and one cloud VM type, for processing every task in a DE3C, then considering there are 10 tasks, the search space includes 6¹⁰ solutions for IPSO, while 2⁶⁰ for BPSO. Thus, in this case, the search space of BPSO is more than 330 million times larger than that of IPSO, and this multiple exponentially increases with the numbers of tasks and candidate cores of each task. Therefore, for an optimization problem, IPSO has much probability of searching a local or global best solution than BPSO. This is also the main reason why GA has much worse performance than IPSO, as shown in Fig. 3.

PSO_srv has smaller search space while worse performance than IPSO. As shown in Fig. 3, IPSO has 115%, 166%, and 108% better performance than PSO_srv in three SLA satisfaction metrics, respectively. This is mainly because the coding of the task assignment to a coarse-grained resource cannot take full advantage of the global searching ability of PSO. Google’s previous work has verified that fine-grained resource allocation helps to improve the resource efficiency (Tirmazi et al., 2020), thus our IPSO uses the core as the granularity of resources during the searching process, which results in a better performance in SLA satisfaction optimization compared with other methods.

Resource efficiency

Figures 4A and 4B respectively show the overall resource utilization and the cost efficiency when using various task scheduling methods in the simulated DE3C environment. As shown in the figure, our method has the best performance in optimizing both resource efficiency metric values, where our method has 36.9%–964% higher resource utilization and 5.6%–143% greater cost efficiency, compared with other methods (GA has zero cost efficiency as its solution does not offload any task to the cloud). This is mainly because the resource utilization is our second optimization objective (see Eqs. (17) or (19)), which results in that the solution having a higher utilization has a greater fitness in all of the solution with same number of finished tasks.

EDF has a worse cost efficiency than other heuristic methods. This may be because EDF offloads more tasks to the cloud, which leads to a greater ratio of the data transfer time and the computing time in the cloud, and thus results in a poor cost efficiency. The idea of offloading tasks with small input data size to the cloud helps to improve the cost efficiency, which is one of our consideration for designing heuristics or hybrid heuristics with high effectiveness. This is the main reason why EFTF has the best cost efficiency in all of these heuristics, because EFTF iteratively assigns the task with minimal finish time, which usually having small input data size, when making the offloading and assignment decisions in the cloud.

Processing efficiency

Figure 5 respectively show the values of the two processing efficiency metrics when applying various task scheduling methods. As shown in the figure, these two processing efficiency metric values respectively have a similar relative performance to the corresponding SLA satisfaction metric values for these scheduling methods, as shown in Figs. 3B and 3C. This is because all of these methods have comparable performance in the makespan. Thus, our method also has the best performance in processing efficiency.