|
1.INTRODUCTIONCloud computing resource allocation can be explained as a process of reasonably allocating resources for different customers in a characteristic cloud environment, following some resource allocation rules1. With the increasing maturity of cloud computing technology, the allocation of cloud computing resources has become the focus of attention. At present, the related research on resource allocation strategy has achieved good results. For example, Reference2 optimized the task scheduling and evaluated each task, but the results deviated greatly due to the different adaptation functions of genetic algorithms. The algorithm proposed in Reference3 will cause search stagnation due to the lack of initial paths. In this paper, the two algorithms are fused together to give full play to their respective advantages. The experimental results show that the genetic ant colony fusion algorithm is very effective for resource allocation. 2.GENETIC ALGORITHMGenetic algorithm originated in the early 1960s. It is a computational model based on the genetic and evolutionary mechanism of nature4. It searches for the optimal solution in real engineering problems by simulating the crossover and mutation of chromosomes in the evolution of natural organisms5. It has three elements: parameter coding, initial population setting and genetic operator. However, the traditional genetic algorithm has some defects, such as premature convergence, decreasing population diversity and weak local search ability. 3.ANT COLONY OPTIMIZATIONAnt colony optimization is a simulation and optimization algorithm that simulates the swarm intelligence behavior of ants foraging6. Ants release a certain amount of pheromones on the path they pass to release information to other ants. Ant Tong ant colony algorithm is only suitable for a certain scale of calculation. In the initial stage of the implementation process, it is prone to stagnation due to the small number of paths recorded in the tabu table. After a long period of time, the pheromone on the better path can be significantly higher than that on other paths7. With the passage of time, the difference becomes more and more obvious, and finally converge. By perceiving the strength of pheromones to choose the path to go next, groups cooperate with each other to better adapt to the environment. 4.DESIGN OF GENETIC ANT COLONY FUSION ALGORITHM4.1.Fusion point designBy analysing the characteristics of genetic algorithm and ant colony algorithm, the fusion point design of these two algorithms is shown in Figure 1: In Figure 1, in the start time period T0, Ta, genetic algorithm maintains a high evolution rate, but in Tb. After time, because genetic algorithm cannot effectively use heuristic information, its individual evolution rate begins to decrease gradually. On the contrary, the ant colony algorithm performs the following tasks in the time period T0, Ta Due to the lack of early pheromones, the individual evolution rate is low, but in Tb After time, the individual evolution rate of ant colony algorithm is improved. Therefore, Ta is the best time point for the end and start of these two algorithms. The algorithm steps are as follows:
4.2.Transformation of initial pheromoneAfter the fusion point design is completed, the local optimal solution of the first algorithm needs to be converted into the initial pheromone of the second algorithm. The method adopted in this paper is: after the first algorithm runs the harness, the chromosome individuals with the highest fitness function value are screened out according to the set proportion (the set value here is 25%), the screened chromosomes are converted into the number of each resource point of cloud computing, and each resource point is converted into the pheromone path (m, n) of ants. The formula is as follows: In equations (1) and (2), xj represents the number of ants retained in resource point I by the individual with the jth genetic chromosome. θ represents pheromone conversion factor. The algorithm flow design in this paper is shown in Figure 2: 4.3.Design of resource schedulingThe resource allocation of cloud computing is based on the reasonable allocation of N pending tasks uploaded by users to m computing resource nodes in the system under certain constraints. The design of resource allocation model requires that the task can be completed in a short time, and the power consumption of the system can also be kept at a low level. This paper designs a resource allocation model, which is specifically defined as follows: Definition 1: task set X = {x1, x2, …, xi, … xn} is the task to be processed, n refers to the number of tasks, xiis the ith task to be processed. Definition 2: the calculation node set Y = {y1, y2, …, yj, … yт} is the calculation node included in the system, m refers to the number of calculation nodes, yj refers to the jth allocable computing node. Definition 3: Texe(i, j) represents the expected time to complete task I on node j, using Xl(i) represents the data length of task I, Yc(j) represents the execution rate of the computing node j. Then Texe(i, j) can be expressed as: Definition 4: Td(i, j) represents the expected time required to transfer task I to computing node j. Xs(i) represents the amount of data that task I needs to transmit, Yd(j) represents the data transmission rate of computing node j, then Td(i, j) can be expressed as: Definition 5: Ttime(i, j) represents the expected time required to transfer the task I to the computing node j, and its value can be expressed as: Since the resource allocation of cloud computing is parallel, each computing node completes its own work alone, then the expected time cost of the system to complete all tasks is Tc can be expressed as: Power cost of completing resource allocation Cc can be expressed as: In equation (7), Ce and Cd represents the power consumption of computing nodes in completing computing and transmission in unit time. 4.4Improvement of ant colony algorithm4.4.1Improve Pheromone.In order to reduce the ant colony algorithm falling into local optimization, we set the pheromone Volatilization Coefficient to achieve the adaptability of the ant colony algorithm. The adaptive pheromone coefficient volatilization formula is: In formula (8), ρ(t) is the pheromone coefficient at time t. And ρmin is the minimum value of the pheromone coefficient. The minimum value is set to avoid the algorithm convergence speed from falling too fast. 4.4.2Design Load Balancing Adjustment Factor.In order to avoid that too many tasks are assigned to the same node, resulting in overload of the node, a load balancing adjustment factor F is introduced here, as shown in equation (9): The value of F in equation (9) can be calculated according to equations (3) and (4). When the task Xi is assigned to the computing resource Yj for execution, the pheromone of the computing resource Yj is updated by the method of formula (10) here, and the other computing resources that are not assigned tasks are updated by the method of formula (11). 4.5Design of genetic algorithmUsing genetic algorithm in resource allocation of cloud computing requires the design of fitness function in combination with the actual resource allocation. The larger the fitness function value, the more likely the genetic chromosome will be retained to the next generation. In order to achieve the premise of shorter task execution and completion time, we also need to ensure low power consumption of the system. The fitness function of completion time is designed Time and power cost fitness function Fitnesstime and Fitnesspower. In order to find a balance between completion time and power cost, the fitness function of genetic algorithm is: In equation (14), a represents the completion time weight value, and B represents the power consumption cost weight value. Between a and b, a + b=1, a & b ∈ 0, 1 is required. 5.SIMULATION EXPERIMENT5.1.Experimental environment and parameter settingThe specific parameter settings of datacenter, virtual machine and cloudlet in cloud sim3.0 are shown in Table 1. Table 1.Experimental environment settings.
The parameter settings of fusion algorithm are shown in Table 2: Table 2.Parameter settings of this algorithm.
5.2Experimental environment and parameter settingThis fusion algorithm is compared with the algorithms proposed in References8-10. The comparison results of the three algorithms in terms of iteration times, time cost, power consumption cost, node load rate and so on are as follows:
6.CONCLUDING REMARKSBased on the research of resource scheduling in cloud computing, this paper proposes a genetic ant colony algorithm with load balancing, iteration times, time cost and power consumption cost as the research objectives. This algorithm has certain advantages in time cost, power consumption cost and load balancing. It provides a reference for resource scheduling in cloud computing. REFERENCESXiao, Y. T.,
“Cloud Computing resource scheduling based on improved ant colony optimization algorithm,”
Microcomputer Applications,
(2), 160
–164
(2022). Google Scholar
Ye, C., Yuan, X. P. and Cang, X. H.,
“Two hypotheses and test assumptions based on Quantum-behaved Particle Swarm Optimization (QPSO),”
Cluster Computing,
(6), 88
–96
(2019). Google Scholar
Jain R. E.,
“An enhanced ant colony optimization algorithm for task scheduling in cloud computing,”
Int. J. Secur. Appl, 13
(4), 91
–100
(2020). Google Scholar
Liu, F., Li, B. and Yang, J.,
“An improved genetic algorithm for cloud computing resource scheduling,”
Computer Measurement & Control,
(5), 202
–206
(2016). Google Scholar
Liu, K. and Jin, H.,
“A compromised-time-cost scheduling algorithm for cost-constrained workflows on cloud computing platform,”
in International Conference System Modeling,
303
–308
(2014). Google Scholar
Zheng, Y., Cai, L. and Huang, S.,
“Cloud testing scheduling based on improved,”
ACO International Symposium on Compuers & Informatics,
(3), 569
–578
(2015). Google Scholar
Wei, S. W. and Deng, W.,
“Cloud resource scheduling based on multi-elite coevolutionary genetic algorithm,”
Computer Applications and Software,
(5), 274
–280
(2021). Google Scholar
Gao, R. and Juebo, W.,
“Dynamic load balancing strategy for cloud computing with ant colony optimization,”
Future Internet,
(4), 465
–483
(2015). https://doi.org/10.3390/fi7040465 Google Scholar
Binsack, Y. and Ralf, W.,
“The intelligent task scheduling algorithm in cloud computing with multistage optimization,”
International Journal of Grid and Distributed Computing, 9
(4), 313
–323
(2016). https://doi.org/10.14257/ijgdc Google Scholar
Ren, J. and Liu, M.,
“Task scheduling strategy for cloud computing based on improved GA,”
Journal of Shenyang University of Technology,
(5), 320
–325
(2019). Google Scholar
|