Review Paper on Optimized Utilization of Resources Using Various Task Scheduling Algorithms in Cloud Computing

Review Paper on Optimized Utilization of Resources Using Various Task Scheduling Algorithms in Cloud Computing

Gunvir Kaur

1. ech. (Department of computer science) CGC Gharaun, Punjab (India)

   Er. Sugandha Sharma

   Assistant Professor Department of computer science CGC Gharaun Punjab (India)

   Abstract Cloud computing is a new topic in the field of information technology, which is developing drastically. Cloud computing delivers an elastic execution environment of resources over the internet. Task scheduling is a challenging issue to gain maximum profit and to efficiently increase working of cloud computing. In this paper we are studying task scheduling algorithms and various issues related to them i.e. how to allocate resources and maximize the profit while guaranteeing quality of service (QoS). This paper surveys Particle Swarm Optimization (PSO), Particle Swarm-simulated Annealing (P-S) algorithm and improved PSO. To get maximum benefit from resources, optimized utilization of resources is important and for this scheduling plays an important role.

   Index Terms Cloud Computing, Particle Swarm Optimization, Simulated Annealing, Resource allocation.

   1. INTRODUCTION

      Cloud computing is a model which provides dynamic services and enables applications by providing virtualized resources over the internet from large scale data centers i.e. cloud. In cloud computing everything is provided as a service i.e. shared resources, software , information etc. So end user can directly access the services but they are not aware about from where these services come from and where these services are stored over the network.

      Fig. 1: Cloud Computing [1]

      From a systematic viewpoint, cloud computing relies on only one thing i.e. internet to deliver its services to its paying customers (see Fig. 1). Task scheduling is a challenging issue

      to gain maximum profit and to efficiently increase working of cloud computing. Task scheduling plays a vital role to improve reliable and flexible systems. The main purpose of task scheduling is to finding out a sequence in which tasks can be executed under some transaction logic constraints [2]. Cloud computing provides many services such as . shared resources, software , information to customers at relatively low cost. When number of customers increases, fulfilling their requirements becomes an important issue. Resource allocation is the major issue because more than one resources may be needed at the same time.

      Traditional task scheduling algorithms only considers that how QoS is maintained but do not consider. how to allocate resources and maximize the profit .To overcome such problems many task scheduling algorithms have been proposed. These algorithms are:

      1. Genetic Algorithm

      2. Particle Swarm Optimization (PSO) Algorithm

      3. Particle Swarm-Simulated Annealing (P-S) Algorithm

      4. Improved Particle Swarm Optimization (IPSO) Algorithm

   2. RELATED WORK

      Task scheduling plays similar role in both cloud and grid computing environment. To get maximum benefit from resources, optimized utilization of resources is important and for this scheduling plays an important role. Many scheduling algorithms were designed so that proper utilization of resouces and guareenting the QoS.

      [Arash Ghorbannia Delavar, Yalda Aryan,2011] adopted genetic algorithm to solve the NP-hard problem by considering many objectives like total makespan,resource load balancing as well as Qos and finds an idealsolution for task scheduling in cloud environment[3]. [Pinal Salot,2013] analyze various task scheduling algorithms and issues related to them and conclude that disk space management is a critical issue in virtual environment. This paper also conclude that Batch mode heuristic scheduling algorithms(BMHA) and Online mode heuristic scheduling algorithms gives high throughput and cost effective but do not consider reliability and availability[4]. [Suraj Pandey, Linlin Wu, Siddeswara Mayura Guru, Rajkumar ,2009] presents a scheduling heuristic method based on particle swarm optimization(PSO) to minimize total cost of execution . This paper compares PSO

      and Best Resource Selection(BRS) algorithm and results show that PSO is better because it achieves three times cost saving as compared to BRS and better distribution of workload on resources[5].

      [Mingyue Feng, Xiao Wang, Yongjin Zhang, Jianshi Li,2012] concerns with problem of resource allocation. So a particle swarm optimization algorithm is designed to overcome this problem by introducing Pareto-dominate theory to the algorithm. This theory search for optimal schedulers in the multi-objective optimizing matter on resources based on total task executing time, resource reservation, and QoS of each task[6]. [Xingquan Zuo, Guoxiang zhang, Wei Tan,2013] proposes a self-adaptive learning PSO(SLPSO)-based scheduling approach which is used to effectively schedule inter-cloud resources. When resources are not sufficient, Iaas provider outsources its workload to the external clouds. This paper also compares SLPSO with cloud federation and results that this approach finds optimal and sub-optimal allocation scheme of internal and external resources which improves the quality and maximize the profit of IaaS provider[7].

      [ Simsy Xavier, S. P. Jeno Lovesum,2013] surveys various scheduling algorithms and compare their parameters. Existing workflow algorithms i.e. PSO based heuristic, Heterogeneous Earliest Finish Time Algorithm (HEFT) etc. does not consider the execution time so there is need of new scheduling algorithm that minimize the execution time[8]. [Prof. Dr. Jayat. S. Umale, Priyanka A. Chaudhari,2013] presents revised discrete particle swarm optimization to optimize the schedules of workflow application in cloud computing environment. This method is used to improve the performance of algorithm and also reduces search space [9].

      [Shaobin Zhan, Hongying Huo, 2012] proposes improved particle swarm optimization which shortens the average operation time, increases utilization ratio of resources and supplies proper resources to user task efficiently. PSO does not solve large scale optimization then simulated annealing algorithm is added into the PSO algorithm which avoids sinking into the local optima and also increases the convergence speed of PSO . The results shows that the proposed method redues the task average running time and the rate of availability of resources is raised [10]. [Yi Cai, Zhutian Chen, Huaqing Min,2013] proposes a swarm intelligence based algorithm which reduces searching time. Traditional PSO algorithm is modified with a random factor to tackle with the premature convergence problem. Results show that proposed system is more feasible, robust and scalable than previous methods. Proposed method gives better performance when compared with traditional PSO-based algorithm. Total time taken to complete the task is shorter and stable than traditional PSO-based method which results in low power consumption [11].

   3. PARTICLE SWARM OPTIMIZATION(PSO)

      Particle swarm optimization (PSO) is a group based searching algorithm. PSO is similar to Genetic algorithm (GA) which is based on population but in PSO re-combination of individuals of the population is not direct. PSO is a self-adaptive global search based optimization technique introduced by Kennedy

      and Eberhart [12]. In wide range of applications PSO is simple

      is the reason PSO becomes popular but it has low convergence accuracy.

      START

      Initialize particle with random position and velocity vectors

      Calculate fitness value for each particle position(p)

      If fitness(p) better than fitness(pbest) than pbest=p

      Assign best particle pbest value to gbest

      Calculate velocity for each particle

      Update particle velocity and position

      Target reached

      End

      Fig.2-Flow diagram of PSO

      As shown in Fig.2, group of particles are used to represent the solution . Every particle uses two vectors i.e. velocity and position. Firstly, initialize particle with random position and velocity vectors in the search space. Every particle will have fitness value then calculate fitness value for each particle(p) will be evaluated according to its present position. Every particle knows its best position (pbest),which stores the best solution. If fitness(p) is better than fitness(pbest) than pbest=p. After this ,for all particles, select the best particle as gbest. At last, calculate and update the velocity and position of each particle using equations (1) and (2).

      vt 1 v t c r ( pbest xt ) c r (gbest xt )

      i

      and effective with low computational cost and fast speed that

      i 1 1

      i i 2 2

      d i

      (1)

      xt 1 xt vt 1

      (2)

      increased. IPSO based cloud computing server cluster fastly

      i i i

      Where:

      v

      i

      t velocity of ith particle at iteration t.

      i

      vt 1 velocity of ith particle at iteration t+1.

      pbesti = best position of ith particle.

      x

      i

      i

      gbest = position of best particle in a population. t current position of ith particle at iteration t. xt 1 = position of ith particle at iteration t+1.

      c1 and c2= acceleration constants.

      r1 and r2= random values. = inertia weight.

      Overall performance of PSO is increased by the inertia weight. If the value of inertia weight is large it encourage global exploration but if it is small than it tends to promote local exploration. To provide balance between global and local exploration and to reduce number of iterations to find the optimum solution suitable selection of inertia weight is necessary. When value of inertia weight is decreased than performance is increased. Many combinational optimization problems are successfully solved by PSO. Some applications that used PSO are: chemical engineering [13], pattern recognition [14], reactive voltage control problem [15] etc.

      PARTICLE SWARM-SIMULATED ANNEALING (P-S)

      ALGORITHM

      PSO algorithm has many advantages like easy to realize, high flexibility, strong robustness, scalability etc. because of these merits PSO solves many combinational problems. But there are some disadvantages in PSO, convergence rate of PSO is low when solving large scale optimization problems and PSO easily sink into defects of local optima due its strong randomicity. PSO is good during intial phase but while going through iterations convergence rate becomes low, particles lose variety. To overcome these problems there is need of some other algorithm then PSO is combined with Simulated annealing and mixed algorithm is designed i.e. P-S algorithm. This algorithm provides better results by combining the properties of both algorithms i.e. PSO has fast searching ability to search better swarm and SA has jumping ability to partly optimize a better individual so, by advantages of both PSO and SA, probability and speed of convergence to the optimum solution is improved. SA algorithm takes optimal individuals as initial solutions which advances scheduling efficiency.

   4. IMPROVED PARTICLE SWARM OPTIMIZATION (IPSO) ALGORITHM

      i

      i

      i

      Firstly, select N initial solutions randomly , initialize , c1, c2 and inertia weight decreases coefficient , set annealing coefficient and intial temperature, the minimum sampled length Umin and maximum sampled length Umax. Then at the end of iteration, update x t and calculate fitness. If particle fitness is better than pbesti set pbesti= x t. If particle fitness is better than gbesti set gbesti = x t. Generate new state from gbesti and set new state by accepting rules. This strategy avoids sinking into local optima and population diversity is

      discover resources, task execution resource matching. Information flows in one direction in global PSO system, gbestt transfer information to other particles further other particles search for the near gbestt i.e. whole group of particles evolve to the optima with gbestt. PSO algorithm is premature because it has poor searching ability for gbestt . PSO has fast searching ability to search better swarm and SA has jumping ability to partly optimize a better individual. Advantages of both PSO and SA are combined and this combined algorithm is known as improved particle swarm optimization algorithm.

   5. CONCLUSION

PSO algorithm has many defects such as convergence rate of PSO is low while solving large scale optimization problems and PSO easily sink into defects of local optima due its strong randomicity. PSO algorithm is good during intial phase but while going through iteration particles lose variety. Then simulated annealing algorithm is combined with PSO algorithm to solve the problems of PSO which increases convergence rate and not sink into local optima. Performance of cloud environment is directly affected by the efficiency of scheduling algorithms. Improved particle swarm optimization (IPSO) algorithm improves average operation time required to complete a task, provides proper resources to the user efficiently.

REFERENCES

1. M.-E. BEGIN, An egee comparative study: Grids and clouds evolution or revolution. EGEE III project Report, vol. 30 (2008).

2. XIAO Zhi-Jiao, CHANG Hui-You,YI Yang An Optimization M ethod of W orkflow Dynamic Scheduling Based on Heuristic GA, Computer Science, Vo1.34 No.2 2007.

3. Arash Ghorbannia Delavar, Yalda Aryan. A Synthetic Heuristic Algorithm for Independent Task Scheduling in Cloud Systems. IJCSI International Journal of Computer Science Issues, Vol. 8, No 2, 2011, pp.289-295.

4. Pinal Salot, A Survey of Various Scheduling Algorithms in Cloud Computing Enviornment IJRET, Vol.2, Issue.2,2013.

5. Suraj Pandey, Linlin Wu, Siddeswara Mayura Guru, Rajkumar Buyya,

   A Particle Swarm Optimization-based Heuristic for Scheduling Workflow Applications in Cloud Computing Enviornments technical reports, University of Melbourne,2009.

6. Mingyue Feng, Xiao Wang, Yongjin Zhang, Jianshi Li, Multi- Objective Particle Swarm Optimization For Resource Allocation In Cloud Computing IEEE,2012.

7. Xingquan Zuo, Guoxiang zhang, Wei Tan, Self-Adaptive Learning PSO-Based Deadline Constrained Task Scheduling for Hybrid IaaS Cloud IEEE Transaction on Automation Science and Engineering,2013.

8. Simsy Xavier, S. P. Jeno Lovesum, A Survey of Various Workflow Scheduling Algorithms in Cloud Environment International Journal of Scientific and Research Publication (IJSRP), vol. 3, Issue 2, 2013.

9. Prof. Dr. Jayat. S. Umale, Priyanka A. Chaudhari, Survey on Job Scheduling Algorithms of Cloud Computing International Journal of Computer Science and Management Research(IJCSMR), ISSN 2278- 733X, 2013.

10. Shaobin Zhan, Hongying Huo, Improved PSO-based Task Scheduling Algorithm in Cloud Computing Journal of Information and Computational Science(JOICS) 9:13(2012) 3821-3829 .

11. Yi Cai, Zhutian Chen, Huaqing Min, Improving Particle Swarm Optimization Algorithm for Distributed Sensing and Search International Conference on P2P, Parallel, Grid, Cloud and Internet Computing, IEEE,2013.

12. J. Kennedy and R. Eberhart, Particle Swarm Optimization. In IEEE International Conference on Neural Networks, Vol. 4, pages 1942- 1948,1995.

13. C . u. O. Ourique, E. C. J. Biscaia, and J. C. Pinto. The use of particle swarm optimization for dynamical analysis in chemical processes. Computers andChemical Engineering,26(12):1782-1793, 2002.

14. J. Louchet, M. Guyon, M. J. Lesot, and A. Boumaza. Dynamic files: a new pattern recognition tool applied to stereo sequence processing. Pattern Recognization Letters, 23(1-3):335-345,2002.

15. H. yoshida, K. Kawata, Y. Fukuyama, and Y. Nakanishi. A particle swarm optimization for reactive power and voltage control considering voltage stability. In the International Conference on Intelligent System application to Power System, pages 117-121,1999.