Hybrid approaches in Network Optical Routing with QoS based on Genetic Algorithms and Particle Swarm Optimization

Hybrid approaches in Network Optical Routing with QoS based on Genetic Algorithms and Particle Swarm Optimization

• 1.
  ACEEE Int. J.on Network Security , Vol. 02, No. 04, Oct 2011 Hybrid approaches in Network Optical Routing with QoS based on Genetic Algorithms and Particle Swarm Optimization Guillen. Edward1, Camargo.Yeison2, and Estupiñán.Paola3 1 Military University Nueva Granada/ Telecommunications Engineering Department, Bogotá, Colombia. Email: Edward.guillen@unimilitar.edu.co 2,3 Military University Nueva Granada/Telecommunications Engineering Department, Bogotá, Colombia. Email: {gissic, edith.estupinan}@unimilitar.edu.co Abstract—Hybrid heuristics have been proposed by many networks [18]. T researches as a method to overcome problems in pure heuristic he method relies on genes, chromosomes and their implementation for multi-constrained QoS routing problems. interaction. In order to exchange information between In this paper we present some hybrid approaches based on chromosomes, GA (Genetic Algorithms) uses some genetic Genetic Algorithms and Particle Swarm Optimization as well operators called: Crossover, Mutation and Selection. A set of as their performance to solve NP-complete routing problem. . genes make up a chromosome which represents possible Index Terms—PSO, GA, Routing, Multicast, Anycast, solution to a problem. The interactions between chromosomes Optimization. are called Crossover. Selection is used to filter individuals (chromosomes). It bases on a “fitness” value witch allow to I. INTRODUCTION select the stronger ones. Many selection approaches has been proposed such as: proportionate selection scheme [19] Today’s networks are rapidly increasing the amount and where the fitness function uses the average fitness value type of transported traffic. Every service has different within the whole population and divides it with chromosome restrictions based on the state of the network, such as: fitness value. This method allows selecting only the bandwidth, delay, jitter, loss packet rate. Therefore, routing chromosomes which have a higher fitness value than mechanism relying on those constrains are necessary. But, population average fitness as in (1). finding multiple paths with multi-constrained QoS requirements has been proven to be NP-complete [1]. Hence, multiple heuristic has been proposed to solve the problem such as Ant Colony Optimization (ACO), Simulated Annealing (SA), Genetic Algorithms (GA), Particle Swarm Optimization (PSO) [2]. Nevertheless, pure heuristic implementation has shown some lacks and then hybrid models are presented. In the same way, different routing approaches has been introduced to make easier the routing problem such as multicast and anycast routing [3,4] and some kind of In roulette wheel selection [19] a roulette wheel is adopted algorithms for each one of the routing approaches. The actual for the chromosomes, each of them, has a part of the angle work presents some hybrid approaches based on Genetic fi 2π algorithms and Particle Swarm Optimization and different within, a number is randomly generated from 0 to  and f mixing ways to solve multi-constrained routing problem. Furthermore, performance and simulation results are if it falls in the chromosome space it is elected. Other ap- presented comparing pure heuristic and hybrid approaches. proaches have been proposed [20]. Mutation operator relies on a mutation rate, which allows changing information from II. BIO-INSPIRED MODELS the chromosomes randomly and sporadically. It is used to escape from local optimal. Selection GA parameters has been A. Genetic Algorithms. studied by different researchers (De Jong, Grefenstette, Bäck, The heuristic proposed by Holand in 1970 [5] based on Gao) as explained in the section selecting GA parameters in the Darwinian evolution theory, has been used to solve [21]. Finally, due to the complex computational resources used optimization problems, although, it has been applied to by GA, Parallel Genetic Algorithm has appeared as a possible different fields such as trust models in MANET’s [6], solution for this issue [22, 23, 24]. The GA process is showed Bandwidth calculation [7], Gas-lift Allocation [8], Differential Fig.1 part (a). calculus [9], Robotics [10], Mobiles [11], Smart Antenna Systems [12], Networks design [13], IDS [14], Load Balancing B. Particle Swarm Optimization. [15], Vehicle routing [16], Signal processing [17], Neuronal Social behavior is the base of PSO (Particle Swarm © 2011 ACEEE 15 DOI: 01.IJNS.02.04. 31
• 2.
  ACEEE Int. J.on Network Security , Vol. 02, No. 04, Oct 2011 Optimization) heuristic. Based on bird flocking, fish schooling QoS routing problem. and particularly swarming theory, James Kenedy and Rusell Eberhart proposed PSO in 1995 [25] simulating bird flocks looking for corn. The approach is similar to Genetic Algorithms. In PSO the individuals are called particles. Unlike to GA, PSO does not rely on genetic operators; In order to find the best solution the particles follow the best particle found so far and evaluate which particle is placed in a better position (solution) in the problem space (closer to the global optimal function value).The evaluation bases on three vectors attached to each one of the particles: current position ( xi ),  previous best position ( pbest ) and velocity ( vi ). When a i better position is found, the value (coordinates) is stored in  the ( pbest ) vector (fitness). The vector (vi) describes the i next movement of the particles and it is achieved by adding the ( vi ) coordinates to ( xi ) vector, the equations for ( vi ) vector and the ( xi ) update position are described in (2). The best position found by the heuristic is stored in a previous best vector .The interaction among the particles is the main factor in the heuristic successful. Thus c1 is a cognitive constant, which means every particle tends going  to its better known position ( pbest ) , and C2 is a social i constant, which means every particle tends going to the better know position within the whole particle population [26]. In [27] the authors improved PSO and included a inertia weight  ,which means a energy loss while Figure 1. Bioinspired Cycles moving, “can be interpreted as the fluidity of the medium in A. PSO - GA chromosome. which a particle moves [27]”, researches have found a The hybrid proposed in [36] for multicast routing with relation: when applying   0.9 the exploration is higher, , QoS, bases on the fact, GA initial chromosomes are randomly due to the easy particles movement, and lower exploration generated. Hence, the algorithm convergence becomes slower. with   0.4 , due to high viscosity medium [28].PSO has In order to overcome the shortcoming a hybrid based on GA- PSO is presented. The new algorithm performs PSO in the many applications in different fields such as: antennas, route generation from source node to each destination node, biomedical, networking, control, as described in [29]. Finally, which means PSO, is used in the initial GA chromosome some test functions are proposed in chapter 4 “Benchmark generation. In order to select the routes which will be included Set” in [30]. The initial PSO pseudo-code is presented in the chromosomes a probability matrix is proposed. Therefore, Fig.1 part (b). initial population is elite for GA and convergence can be achieved in less iterations. After chromosomes based on PSO III. HYBRID APROACHES are generated, the GA heuristic tries to find the minimum cost Based on GA and PSO features, many researches have multicast tree. Simulation is implemented in NS2 and performed comparison studies. Results show the integration comparison between pure GA and hybrid approach as shown of this heuristics is a good approach [31,32,33 ]. PSO has an in Fig.2 parts (a-b). easy implementation, low computational cost, memory and B. PSO - elite group chromosome. rapid convergence [34], while GA are slow to convergence, require a higher computational cost and every generation Another approach proposed by Changbing Li, Changxiu the memory is erased, but its genetic operator achieve better Cao1, Yinguo Li and Yibin Yu’ in [37] for multicast routing fitness value, helping to escape from local optimal. Different with QoS problem, relies on the GA improvement, the hybrid implementation approaches have been proposed, this section is performed by initial GA heuristic, when the chromosomes is intended to show some of them and generally describe the are created, the upper-half of the best fitness chromosomes way researches mix the heuristics to solve multi-constrained is selected and called elite group, in this phase PSO heuristic © 2011 ACEEE 16 DOI: 01.IJNS.02.04. 31
• 3.
  ACEEE Int. J.on Network Security , Vol. 02, No. 04, Oct 2011 is performed, then, elite group will be tread as a swarm, each one of the elites in the group will be particles as in PSO, the elites are enhanced by PSO, finally reproduced and selected as parents for crossover in GA. The proposed method is in accordance of the authors as the growing up and adaptation to the medium that individuals perform before reproduction. In normal GA heuristic the chromosomes are immediately reproduced without this approach. The proposed algorithm is called HGAPSO. As described in the paper, better results are achieved by the hybrid approach optimizing cost of the tree, max end-to-end delay, average delay and max link utilization as presented in Fig2 part (c-e) and table I. C. GA Genetic Operator - PSO The method proposed by LI Taoshen, XIONG Qin and GE Zhihui in [38] for anycast Routing with multi-constrained QoS restrictions problem is based on the integration to genetic operator from GA to PSO, as described before PSO has a rapid convergence but it is easy to fall in local optimal, then, genetic operator are used to solve the shortcoming. Figure 2. Hybrid Performance The method initially performs PSO in the routing algorithm TABLE I. . COMPARISON OF PROPOSED ALGORITHM AND CONVENTIONAL ALGORITHM with a group of random particles which search for an optimal WITH THE MEAN PERCENTAGE DEVIATIONS [37]. fitness, the update operator in PSO is improved in order the particles to learn about sub-routes within other particles, in this way the particles learn about better sub-routes and they become better, when PSO gets in a local optima crossover and mutation operators are performed. Thus, PSO can escape from local optimal and achieve better solutions. Simulations presented in the paper showed better fitness values for hybrid approach and less iterations for convergence than pure heuristic approaches as described in Fig. 2 part (f). IV. BIOINSPIRED MODELS IN OPTICAL NETWORKS The implementation of routing approaches described before try to address the multi-constrained QoS problem in CONCLUSIONS the network layer. In the other hand, it could be useful to extend QoS constrains to physical layer. Bio-inspired models Different kind of heuristics have been used by researches have been also proposed to solve WDM (Wavelength to solve routing problem, the paper described different Division Multiplexing) problems, where the use of optical approaches in hybrid application models based on Genetic fiber bandwidth is intended to be optimized by using non- Algorithms and Particle Swarm Optimization. The simulation interferencing channels with multiple carriers at different results have proven hybrid heuristics to achieve better frequencies. GA is applied to improve routing with optical performance than single heuristic implementation, due to networks [39], where a lightpath could be created based on implementation of heuristics features to overcome lacks in the connection request of a specific service. This approach heuristics such as slow convergence time or local optimal. allow to improve QoS constrains, due to its implementation Furthermore, different mixed forms have been shown for same not only in network layer but also in physical layer. hybrid approach. REFERENCES [1] Bin Wang and J.C. Hou. Multicast routing and its qos extension: problems, algorithms, and protocols. Network, IEEE, 14(1):22 – 36, jan/feb 2000 [2] Rafael Páez  Edward  Paul  Guillen Pinto,  Yeison Julian Camargo.  Routing  with  QoS  using  bioinspired  models:  An overview. 2011 [3] R.F. Abdel-Kader. An improved discrete PSO with GA operators for efficient QoS-multicast routing. 2011. [4] Li Taoshen,  Xiong  Qin,  and  Ge Zhihui.  Genetic  and  particle © 2011 ACEEE 17 DOI: 01.IJNS.02.04. 31
• 4.
  ACEEE Int. J.on Network Security , Vol. 02, No. 04, Oct 2011 swarm hybrid QoS anycast routing algorithm. 1:313 –317, nov. [21] R.L. Haupt, S.E. Haupt, and S.E. Haupt. Practical genetic 2009 algorithms. Wiley Online Library, 1998. [5] JH Holland.  Adaptation  in  natural  and  artificial  system:  an [22] A.A.B. Junior and A.L. Freitas. Algoritmos genéticos paralelos. introduction with application to biology, control and artificial Departamento de Ciências da Computação–Universidade Federal intelligence. Ann Arbor, University of Michigan Press, 1975. da Bahia. Disponvel: http://twiki. dcc.ufba.br/pub/MAT054/ [6] Marcela Mejia, Néstor Peña, Jose L. Muñoz, Oscar Esparza, S emest reA rti g o s2 0 0 61 / A lg o rit m o sG en et i cosPa ra l elo s- and Marco A. Alzate. A game theoretic trust model for on-line AmadeuLage. pdf. Acesso em, 27(12):2007, 2006. distributed evolution of cooperation inmanets. Journal of Network [23] E. Cantú-Paz.  A  survey  of  parallel  genetic  algorithms. and Computer Applications, 34(1):39 – 51, 2011 Calculateurs paralleles, reseaux et systems repartis, 10(2):141– [7] R. Gunasekaran,  S. Siddharth,  R. Muthuregunathan, 171, 1998. R. Srivathsan,  and  V.R.  Uthariaraj. An  improved  parallel  genetic [24] R. Shonkwiler.  Parallel  genetic  algorithms.  pages  199–205, algorithm for path bandwidth calculation in tdma-based mobile ad 1993 hoc networks. In Advances in Computing, Control, [25] J. Kennedy  and  R. Eberhart.  Particle  swarm  optimization.  In Telecommunication Technologies, 2009. ACT ’09. International Neural Networks, 1995. Proceedings., IEEE International Conference on, pages 220 –226, dec. 2009. Conference on, volume 4, pages 1942 –1948 vol.4, 1995. [8] M.M. Zerafat, S. Ayatollahi, and A.A. Roosta. Genetic [26] DIEGO ALEJANDRO MUÑOZ CARPINTERO. Diseño y algorithms and ant colony approach for gas-lift allocation evaluación de algoritmos evolutivos para estrategias de control optimization. Journal of the Japan Petroleum Institute, 52(3):102– predictivo híbrido no lineal. 2010. 107102, 2009 [27] Y. Shi  and R. Eberhart. A modified  particle  swarm  optimizer. [9] N.J. Amador. Algoritmos genéticos en el cálculo diferencial. In Evolutionary Computation Proceedings, 1998. IEEE World [10] R.P. CARLOS and A.T.P. CARLOS. Algoritmo genético para Congress on Computational Intelligence., The 1998 IEEE la ubicación optima de sensores en un robot seguidor de línea. International Conference on, pages 69 –73, may 1998. [11] H.E. Carranza, L. Chávez, M.L. Fosfore, and S.B. Simón. Un [28] Riccardo Poli, James Kennedy, and Tim Blackwell. Particle enfoque multiobjetivo para la asignación de canales en sistemas swarm optimization. Swarm Intelligence, 1:33–57, 2007. 10.1007/ celulares. Información tecnológica, 19(1):87–96. s11721-007-0002-0. [12] H. Awan,  K. Abdullah,  and  M. Faryad.  Implementing  smart [29] R. Poli.  An  analysis  of  publications  on  particle  swarm antenna system using genetic algorithm and artificial immune system. optimization applications. Essex, UK: Department of Computer In Microwaves, Radar and Wireless Communications, 2008. MIKON Science, University of Essex, 2007 2008. 17th International Conference on, pages 1 –4, may 2008. [30] M. Clerc.  Particle swarm optimization. Wiley-ISTE, 2006. [13] King-Tim Ko, Kit-Sang Tang, Cheung-Yau Chan, Kim-Fung [31] P. Angeline.  Evolutionary  optimization versus  particle  swarm Man, and Sam Kwong. Using genetic algorithms to design mesh optimization: Philosophy and performance differences. In networks. Computer, 30(8):56 –61, aug 1997. Evolutionary Programming VII, pages 601–610. Springer, 1998. [14] W. Li. Using genetic algorithm for network intrusion detection. [32] R. Eberhart and Y. Shi. Comparison between genetic algorithms In Proceedings of the United States Department of Energy Cyber and particle swarm optimization. In Evolutionary Programming Security Group 2004 Training Conference, Kansas City, Kansas, VII, pages 611–616. Springer, 1998. pages 24–27. Citeseer, 2004. [33] K.O. Jones. Comparison of genetic algorithm and particle [15] Xinhua Jiang, Lina Zhang, and Heru Xue. An application of swarm optimization. In Proceedings of the International Conference immune genetic algorithm for load balancing in vod cluster. In on Computer Systems and Technologies, 2005. Information Science and Engineering (ICISE), 2009 1st International [34] J. Kennedy  and  R. Eberhart.  Particle  swarm  optimization.  In Conference on, pages 109 –112, dec. 2009. Neural Networks, 1995. Proceedings., IEEE International [16] Keivan Ghoseiri and Seyed Farid Ghannadpour. Multi- Conference on, volume 4, pages 1942 –1948 vol.4, 1995. objective vehicle routing problem with time windows using goal [35] PSO. http://www.swarmintelligence.org/. programming and genetic algorithm. Applied Soft Computing, [36] Junwei Wang, Xingwei Wang, and Min Huang. A hybrid 10(4):1096 – 1107, 2010. Optimisation Methods & Applications intelligent QoS multicast routing algorithm in ngi. pages 723 – 727, in Decision-Making Processes. dec. 2005. [17] H. Takahashi,  N. Shaaban,  Q.W.  Wang,  J.Y.  Yeom,  and [37] Changbing Li, Changxiu Cao, Yinguo Li, and Yibin Yu.Hybrid M. Nakazawa. Adaptive  signal  processing  with  genetic  algorithm of genetic algorithm and particle swarm optimization for multicast optimum filter for fast digitizer asic. In Nuclear Science Symposium qos routing. In Control and Automation, 2007. ICCA 2007. IEEE Conference Record, 2003 IEEE, volume 5, pages 3441 – 3443 Vol.5, International Conference on, pages 2355 –2359, 30 2007-june 1 oct. 2003 2007 [18] A. Imada and K. Araki. Genetic algorithm enlarges the capacity [38] Li Taoshen,  Xiong  Qin,  and  Ge Zhihui.  Genetic  and  particle of associative memory. In Proceedings of 6th International swarm hybrid qos anycast routing algorithm. 1:313 –317, nov. Conference on Genetic Algorithms, volume 413. Citeseer, 1995. 2009 [19] M. Srinivas and L.M. Patnaik. Genetic algorithms: a survey. [39] Ravi Sankar, Ashok Kumar. Genetic Algorithm techniques to Computer, 27(6):17 –26, June 1994. solve Routing and Wavelength Assignment problem in Wavelength [20] T. Blickle  and  L. Thiele.  A  comparison  of  selection  schemes Division Multiplexing all-optical networks. 2011- IEEE. used in genetic algorithms. Evolutionary Computation, 4(4):311– 347, 1997. [31]P. Angeline. Evolutionary optimization versus particle swarm optimization: Philosophy and performance differences. In Evolutionary Programming VII, pages 601–610. Springer, 1998. © 2011 ACEEE 18 DOI: 01.IJNS.02.04.31