GWOCSA Based Algorithm for Allocating Resources to the Tasks in the Cloud

In the area of optimization, many heuristic and meta-heuristic theories have been proposed in the recent past. Cloud computing has adopted some of the optimization techniques which combine or improvise one or more meta-heuristic algorithms. To enhance the efficiency of scheduling algorithms, researchers are using swarm intelligence algorithms. To quote a few, "Ant colony optimization, Particle swarm optimization, Genetic Algorithm, Differential evolution algorithm, Simulated annealing, Whale optimization, Grey wolf optimization, Crow search algorithm, Eagle strategy, Moth search algorithm, Artificial bee colony algorithm, Spider Monkey algorithm, Jaya algorithm, Teaching learning based optimization" [1], and so on.

2.1 Ant colony optimization

Tawfeek et al. [7] applied an ant colony optimization algorithm in scheduling and compares ACO with FCFS and proves that ACO shows better results. Li et al. [8] applied ant colony optimization to solve load balancing problems in the cloud environment. They propose an improvised algorithm LBACO.

Dai et al. [9] took into account the effect of strong positive feedback of ACO on the algorithm's convergence rate. The initial pheromone chosen has a significant effect on the convergence rate. The algorithm uses a GA's global search capability to find the best solution and then transforms it into the ACO's initial pheromone.

Azad and Navimipour [10] combined the ACO algorithm with the Cultural algorithm. Makespan and energy consumption are considered as objectives. Particle swarm optimization and ant colony optimization are combined in Ref. [11]. To maintain the population's diversity and the fitness of the particles increased, the authors demonstrate improved working efficiency in fitness, expense, and running time through their approach. They present a more accurate and effective understanding of task scheduling.

However, ACO is strongly reliant on its two constants $\alpha$ and β as a probabilistic algorithm. For combinatorial kinds of problems, it is highly desired to retain the standard values of these parameters. The ACO algorithm's stagnation phase could not be recovered without modifying the values of $\alpha$. Even if standard values of $\alpha$ and β are preserved, the convergence speed of the solution drastically varies for the same problem and the same number of ants.

2.2 Particle swarm optimization

In the recent past, researchers proposed many algorithms to solve optimization problems. Though individually, they showed their efficiency, either they suffered from lack of exploration or exploitation. The limitation of exploration and exploitation of the algorithms led the researchers to hybridize the algorithms to enhance efficiency. GA and PSO were added to solve the optimization problems [12]. Individuals are generated along with crossover, mutation, and operators of local and global search of PSO. As suggested by Pandey et al. [13], (PSO)-based heuristic for scheduling cloud applications to consider both computing and data transmission costs as the main objectives. The authors compare their proposed algorithm with the "Best resource selection" heuristic. They claim that their algorithm is better than the heuristic algorithm.

Awad et al. [14] proposed a numerical model by considering reliability, execution time, transmission time, and load balancing between tasks and virtual machines using Load Balancing Mutation (balancing) a particle swarm optimization (LBMPSO) based schedule and allocation. They compare their method with standard PSO, random algorithm, and Longest Cloudlet to Fastest Processor (LCFP) algorithm to show an improvement.

Verma and Kaushal [15] proposed a multi-objective optimization-based algorithm by hybridizing particle swarm optimization (HPSO). Under deadline and budget constraints, the HPSO heuristic attempts to optimize two competing goals, namely, makespan and expense. Along with these two opposing goals, the number of resources used to build the workflow schedule is also reduced. The algorithm generates a set of Pareto Optimal solutions from which the consumer can choose the most appropriate one.

Gill et al. [16] suggested BULLET, a PSO-based resource scheduling strategy for scheduling workloads in the cloud to reduce execution expense, time, and energy consumption. BULLET is efficient in reducing the execution time, expense, and energy usage of cloud workloads, as well as other QoS parameters, including availability, efficiency, latency, and resource utilization, according to experimental findings.

The particle swarm optimization (PSO) algorithm has the disadvantages of being easy to fall into a local optimum in high-dimensional space and having a slow convergence rate in the repeated process [17].

2.3 Genetic algorithm

Zhao et al. [18] suggested an efficient genetic algorithm for scheduling independent and divisible tasks that can respond to various computing. They activate the algorithm in heterogeneous environments, where computing and communication capabilities (including CPUs) are heterogeneous. The use of dynamic scheduling is also being considered.

Aziza and Krichen [19] devised a fitness mechanism that aids in the reduction of mission execution costs and minimization of makespan. The extension of GA to two existing scheduling rules, time-shared and space-shared, resulted in two additional policies, TSGA and SSGA. The makespan and overall cost of execution are two metrics used to measure performance.

Ibrahim et al. [20] proposed an Integer Linear Programming (ILP) model that minimizes energy consumption in a Cloud data center to create a dynamic task scheduling algorithm. In addition, an Adaptive Genetic Algorithm (GA) is proposed to reflect the complex nature of the Cloud world and to provide a near-optimal scheduling solution that saves resources.

Zhou et al. [21] suggested MGGS (modified genetic algorithm (GA) combined with greedy strategy) as a new algorithm in this article. To maximize the efficiency of scheduling, the proposed algorithm uses a revamped GA algorithm paired with a greedy approach. MGGS, unlike other algorithms, can find an optimal solution with a lower number of iterations.

2.4 Grey wolf optimization

The grey wolf, also known as the timber wolf [5], is the world's largest wild dog. Wolves exist in clans led by an alpha wolf, with the rest of the pack adhering to a dominance hierarchy. The actions like hunting and finding the location of stay are taken by the alpha wolf. The second level of the wolf pack is beta and is considered subordinate to the alpha. The following levels of the wolves are delta and omega.

The phases of hunting can be considered as follows.

1) Tracking, pursuing, and closing in on the prey. 2) Pursue, encircle, and annoy the prey until it comes to a halt. 3) Attack on the prey.

Grey wolf optimizer is one of the metaheuristic algorithms. It was suggested by Mirjalili et al. [5] who proposed an intriguing meta-heuristic algorithm that mimicked the behavior of grey wolves.

(1) Hierarchical structure

GWO has been mathematically modeled by taking into account the social hierarchy. The best location of the search agent in the solution space is considered as α wolf, β as the second best, and δ as the third. The remaining are known as omega wolves [5].

(2) Encircling

During the hunting wolves encircle the prey. The equation for encircling the prey is denoted by in Eq. (1) and Eq. (2) [4, 5]. Here, the position of the wolves and the prey is represented by a vector. In the equation 'Dist' indicates the distance between prey and the wolf. GW and X_p correspond to the location of the wolf and the placement of prey respectively.

$\vec{D}=\overrightarrow{\mid C *} \vec{X}_{\text {prey }}(t)-\overrightarrow{G W}(t) \mid$                (1)

$\overrightarrow{G W}(t+1)=\vec{X}_{\text {prey }}(t)-\vec{A} \cdot \vec{D}$                (2)

$\vec{A}=2 \vec{a} \vec{r}_{1}-\vec{a}$        (3)

$\vec{C}=2 \cdot \vec{r}_{2}$        (4)

Eq. (3) & Eq. (4) are vectors of coefficients.

r1 and r2 represent random values between [0,1].

(3) Prey hunting

Grey wolves' encircling the prey is modeled by Eq. (5) and Eq. (6). Guided byα, β, and δ wolves, all the remaining wolves update their position by Eq. (7).

$\vec{D}_{\alpha}=\left|\vec{C} * \vec{X}_{\alpha}(t)-\overrightarrow{G W}(t)\right|$

$\vec{D}_{\beta}=\left|\vec{C} * \vec{X}_{\beta}(t)-\overrightarrow{G W}(t)\right|$

$\vec{D}_{\delta}=\left|\vec{C} * \vec{X}_{\delta}(t)-\overrightarrow{G W}(t)\right|$          (5)

$\overrightarrow{G W}_{1}(t+1)=\vec{X}_{\alpha}(t)-\vec{A} \cdot \overrightarrow{D \imath s t}_{\alpha}$

$\overrightarrow{G W_{2}}(t+1)=\vec{X}_{\beta}(t)-\vec{A} \cdot \overrightarrow{D i s t}_{\beta}$

$\overrightarrow{G W}_{3}(t+1)=\vec{X}_{\delta}(t)-\vec{A} \cdot \overrightarrow{D i s t}_{\delta}$         (6)

$G W(t+1)=\frac{\sum_{i=1}^{3} \overrightarrow{G W}_{i}(t+1)}{3}$       (7)

(4) Searching & attacking the prey

The prey gets attacked by grey wolves only when it stops progress. It is described mathematically with a vector 'A' employed in Eq. (3). 'A' is a random vector and contains the values in [-a, a] [4, 5], with 'a' decreasing from 2 to 0 during the iterations using Eq. (8).

|A| < 1 will lead the wolf to assault the prey with movement towards it and |A| > 1 lead the wolf to move away from the prey [1]. The position of α, β and δ wolves decide the direction of search for the prey. Global (exploration) and local (exploitation) searches rely on A and C vectors.

$a=2-\left(2 \times t / \operatorname{Max}_{\text {iter }}\right)$                (8)

The range of random values for the C vector is [0, 2], which is critical for preventing local optima stagnation. The values of the C vector show random behavior, in turn this helps to explore globally.

The GWO suffers from poor local search and slow convergence rate [22].

2.5 Crow search algorithms

Crows are intelligent creatures. They have the biggest brain in proportion to their body size. Experiments proved that they show self awareness ingenuity. Crows may use tools to interact in complex ways, and remember the location of their food for many months. Crows watch other birds, observing the place of food storage, and then stealing it after actual bird leaves. If a crow was a victim of theft before, it will take special care including changing hiding areas to prevent being a victim again. This behavior of cleverness is mimicked in finding the optimal solution using a natural-inspired algorithm by Askarzadeh [6]. CSA's operation is based on four important principles: herd living, recall the place of secret food, pursue another individual of their genus, and ultimately protect their accumulation from arbitrary plundering.

(1) Mathematical model for CSA

The position of each crow is represented by an M dimensional vector. Searching for the optimal solution starts from an initial population. Initialize the upper bound of iterations, count of crows, flight length and awareness probability. The fitness will be calculated.

The notation CPop_k represents the initial population of the crow and [CPop_j1, CPop_j2, CPop_j3, ...,CPop_jM] indicates the position of crow 'j'.

Cpop^i,t indicates the initial location of 'i^th' crow at time 't'. Whereas 'r_i,' and 'fl' indicate a random number, and flight length respectively. The secret place is 'sp'.

If j^th crow wants to visit the secret place where the food is hidden, i^th crow plans to find the secret place of the crow j. This leads to either of the following. First awareness probability is compared with a random number. The crow updates its position by Eq. (9) [3, 6] if the awareness probability is larger. Otherwise it updates its position with a random crow's position.

$\operatorname{Cpop}^{(i+1, t+1)}=\mathrm{Cpop}^{i, t}+r_{i} \times f l^{i, t} \times\left(s p^{i, t}-\mathrm{Cpop}^{i, t}\right)$

if $A P>r_{i}$             (9)

Algorithm 2 shows the pseudo code for CSA.

The Crow search algorithm also suffers from slow convergence speed and can be trapped into local optima.

The proposed algorithm is checked in MATALB R2020A software for its efficiency on Intel core™i7 CPU@1.80-GHz with 8 GB of RAM using synthetic data. As it is an NP-Complete problem, the algorithm gives various outputs based on the random numbers. In this setup five jobs and five heterogeneous virtual machines are considered. Table 1 presents the initial population. Table 2 represents the execution time of each job on every VM. Table 3 shows the final allocation of the algorithm.

Table 1. Initial population

Table 2. Execution times of jobs on VMS

Table 3. Final allocation-GWOCSA

The best makespan of the given problem after 10 iterations calculated by GWOCSA=124, with GWO=122 and with CSA=128. After iteration 120, the best makespan is 89. GWOCSA algorithm converges quickly. GWO and CSA suffer from slow convergence. Based on the values obtained from results it can be concluded that the proposed algorithm competes with GWO and CSA algorithms. It has proven that at times its efficiency is better than the other two algorithms.

Figure 1 shows the comparison of the GWOCSA with GWO and CSA. From the figure, it can be observed that at the initial stages GWO shows a better solution. CSA algorithm does not converge quickly. However, the proposed algorithm balances the exploration and exploitation and reaches an optimal solution. The makespan after 20 iterations was 123 with GWO,130 with CSA, and 120 with GWOCSA. GWOCSA converges to the optimal solution after 120 iterations. The convergence of the GWO algorithms takes after 160 iterations, and with CSA algorithm happens after 180 iterations.

1.png

Figure 1. Comparison of makespan