233 Original scientific paper  MIDEM Society A Meta-Heuristic Approach for Wavelength Assignment in Long-Haul Optical System R. Hemalatha, R. Mahalakshmi Department of EEE, Kumaraguru College of Technology, Coimbatore, India Abstract: Routing and Wavelength Assignment (RWA) problem is one of the optimization problems in optical networks. The aim is to minimize the blocking probability and the number of wavelengths used. The RWA problem can be solved by number of algorithms like Genetic Algorithm (GA), Ant Colony Optimization (ACO), etc. In the proposed research, Shuffled Frog Leaping Algorithm (SFLA) has been implemented in optical networks to solve the RWA problem. The optimization parameters considered are cost, number of wavelengths, hop count and blocking probability. The problem is analyzed for different wavelength assignment methods such as first fit, random, round robin, wavelength ordering and Four Wave Mixing (FWM) priority based wavelength assignment. Fitness function devised includes cost, number of wavelengths, hop count and setup time. The proposed SFLA algorithm has been compared with GA and is found to minimize the blocking probability, cost and computational complexity. Keywords: GA; RWA; SFLA; WDM Metahevrističen pristop določitve valovne dolžine optičnega sistema Long-Haul Izvleček: Osnoven problem optičnih omrežjih je njihova pot in določitev valovne dolžine (RWA). Namen je minimizacija verjetnosti združevanja in števila uporabljenih valovnih dolžin. RWA problem se lahko reši s številnimi algoritmi, kot so generičen algoritem (GA), Ant Colony optimizacija (ACO) in drugi. V predstavljeni raziskavi je bil uporabljen Shuffled Frog Leaping Algoritem (SFLA). Parametri optimizacije so bili strošek, število valovnih dolžin ter število poskokov in verjetnost združevanja. Problem je bil analiziran za različne določitve valovnih dolžin, kot so prvi približek, naključnost, sistem vsak s vsakim, urejanje valovnih dolžin ter Four Wave Mixing (FWM) prednostna določitev valovne dolžine. Predlagan SFLA algoritem je bil primerjan z GA algoritmom. Izkazalo se je, da SFLA zmanjšuje verjetnost združevanja, strošek in kompleksnost računanja. Ključne besede: GA; RWA; SFLA; WDM * Corresponding Author’s e-mail: hemalatha.r.ece@kct.ac.in Journal of Microelectronics, Electronic Components and Materials Vol. 47, No. 4(2017), 233 – 240 1 Introduction In high capacity telecommunication networks, Optical networks play a major role. Routing, grooming and res- toration are the wavelength based services provided by optical networks. Fiber optics is to transmit data in the form of light. Electrically powered switching equip- ment such as a router or a switch aggregator is used in active optical system. It is used to regulate signal distri- bution and to direct the signals to different users. The switch controls the incoming and outgoing signals. Optical splitters are used to isolate and collect optical signals. The aim of optical communication systems is to transfer large amount of information with simple equipments (Batagelj 2014).Optical fiber communica- tion performs better in terms of transmission capacity and communication range (Vidmar 2001). An optical Wavelength Division Multiplexing (WDM) network is a network with fiber optic transmission links designed to utilize the features of fibers and WDM. Wavelength-division multiplexing meets the high bandwidth demand. Several routing and wavelength assignment problems that exist in optical wavelength division multiplexing are traffic grooming , optimal routing and wavelength assignment, survivability, Quality of service(QoS) routing and physical layer im- pairment aware (PLI aware) problems (Bhanjaa and Mahapatra 2013). A lightpath is an optical connection 234 between two nodes. Depending on the wavelength of the lightpaths, data are optically routed at intermedi- ate nodes (Le et al 2005 and Bisbal et al 2004). Con- ventional methods to solve these complex problems consume more computational time (Wang et al 2014 and Triay et al 2010). Multi-objective evolutionary algo- rithms based on swarm intelligence are used to solve the RWA problem, which are in real- world optical net- works (Kavian et al 2013 and Largo et al 2012). In the proposed method Shuffled Frog Leaping Algorithm is used to solve this problem. Similar algorithms available are either simple leading to poor performance or too complex to be used. The aim is to use computationally feasible algorithm for better network performance. In this research paper, routing and wavelength assign- ment problem model is described with two optimiza- tion algorithms, genetic algorithm and shuffled frog leaping algorithm. Genetic Algorithm is used to solve many problems in variety of fields and hence compari- son of SFLA is done with this algorithm. The discussions include simulation results, analysis, conclusions of the study and possible future work. 2 Routing and wavelength assignment problem 2.1 Problem Definition In dynamic routing and wavelength assignment, the lightpath requests arrive dynamically. A lightpath in a network is the path that satisfies the wavelength con- tinuity constraint (that is, same wavelength should be used by the l ightpath on all the links i n its path). For each lightpath request, source node, destina- tion node and holding time are defined. Holding time is the time during which a lightpath and the associated resources remain occupied. The resources become free, when the holding time elapses and can support other lightpath requests. Fig.1 shows the model to solve the RWA problem (Bhanjaa et al 2013). Figure1: Block diagram of optimization method 2.2 Network Model A network with N nodes can be modeled as a graph G(V,E), where V is the set of nodes denoting the routers or switches and E is the set of edges denoting connec- tivity between the nodes. The links between the nodes are assumed to be bidirectional. In dynamic routing and wavelength assignment problem, V is the set of nodes denoting routers or wireless routing networks and E is the set of fiber links denoting physical connec- tivity between the nodes. 2.3 Routing Model Routing and Wavelength Assignment (RWA) is one of the major problems in optical networking. The goal is to maximize the number of optical connection. A route and wavelength must be assigned for each connection request. Throughout the path, wavelength must be the same, unless the usage of wavelength converters is as- sumed. Two connections requests can share the same optical link, if different wavelength is provided (Bhan- jaa et al 2012). Fitness function to be maximized is given by 1 , ( ), ( 1) ( , ) 1 x x x x x k x i j x gx j gx j i j E j W W Wf H TC − + ∈ = = + + ∑∑ (1) Wx is free wavelength factor and takes the value of one, if same wavelength is available in all the links of path x or otherwise, zero. Summation in the first term de- fines the total link cost of the path and summation in the second term represents the total number of hops in the path. The variable Hxi,j is one, if link (i, j) is a part of path x and is zero otherwise. Variable Tx represents the set up time of path x. Variable Kx represents the length of the x-th chromosome or number of memeplexes. The route is optimal when the objective function maxi- mizes with the following constraints being satisfied. ( , ) ( , ) 1, if i=S, lp LPlp lpij ij i j E j i E I I ∈ ∈ − = ∈∑ ∑ (2) ( , ) ( , ) 1, if i=D, lp LPlp lpij ij i j E j i E I I ∈ ∈ − = − ∈∑ ∑ (3) ( , ) ( , ) 0, if i S, i D, lp LPlp lpij ij i j E j i E I I ∈ ∈ − = ≠ ≠ ∈∑ ∑ (4) ( , ) 1, if i D, lp LPlpij i j i j E I ≠ ∈ ≤ ≠ ∈∑ (5) ( , ) 0, if i=D, lp LPlpij i j i j E I ≠ ∈ = ∈∑ (6) R. Hemalatha et al; Informacije Midem, Vol. 47, No. 4(2017), 233 – 240 235 0 ( , ) , for t Tlpij i j E I h ∈ ≤ ≤∑ (7) 0 ( , ) ( 1), for t Tlpij i j E h I N ∈ < ≤ − >∑ (8) Equations (2) to (6) represent the flow conservation constraint. Equations (7) and (8) represent the hop count constraint. 2.4 Wavelength Assignment Model First fit and Random fit are the wavelength assignment techniques that are used generally. First Fit method de- cides the available wavelength with the lowest index while random fit method identifies the available wave- lengths and chooses randomly amongst them. O(w) is the complexity of both algorithms, where w is the number of wavelengths. First Fit outperforms Random Fit. Other wavelength assignment techniques used here are round robin technique, wavelength ordering technique and Four Wave Mixing aware wavelength as- signment technique. In FWM aware wavelength assign- ment technique, since the FWM crosstalk power will be more over the center of transmission window, priority is given to the wavelengths towards the edges of the transmission window. O(N3log2N) is the complexity of this method, where N is the number of nodes in the network. In the proposed fitness function, Wx the free wavelength factor is updated after the wavelength as- signment phase. In the wavelength assignment model, if the link (i, j) is used by the lightpath lp, the variable Iij lp assumes one else it assumes zero. Variable Iijw lp is the lightpath wavelength indicator. It shows whether the lightpath lp uses wavelength ‘W’ on link (i, j). Variable Iijw lp(x,y) is the lightpath wavelength link indicator and is one when the lightpath uses wavelength ‘W’ on link (i, j) between the nodes x and y. l(x,y) equals one if a physical link exists between the nodes x and y (Bhanjaa et al 2010). The wavelength continuity constraints are 1 0 , (i,j) W lp lp ij ijw w I I − = = ∀∑ (9) ( , ) , (i,j), (x,y), wlp x y lpijw ijwI I≤ ∀ ∀ ∀ , (10) ( , ) , 1, (x,y), wlp x yijw i j I ≤ ∀ ∀∑ (11) 1 1 ( , ) ( , ) ( , ) ( , ) 0 0 , y=j W W lp x y x y lp y x y x lp ijw ijw ij w x w x I l I l I − − = = − =∑∑ ∑∑ (12) 1 1 ( , ) ( , ) ( , ) ( , ) 0 0 , y=I W W lp x y x y lp y x y x lp ijw ijw ij w x w x I l I l I − − = = − = −∑∑ ∑∑ (13) 1 1 ( , ) ( , ) ( , ) ( , ) 0 0 0, y i, y j W W lp x y x y lp y x y x ijw ijw w x w x I l I l − − = = − = ≠ ≠∑∑ ∑∑ (14) 3 Optimization algorithms 3.1 Genetic Algorithm The methodology of Genetic Algorithm is shown in Fig.2. This method works iteratively on an initial solu- tion set which is referred to as population and con- verges to arrive on best solution (Kavian et al 2009). Figure 2: Flow diagram of GA 3.2 Representation of chromosome and Initialization of population Route or path encoded from source to destination is represented by a chromosome. A sequence of nodes creates each chromosome and is generated randomly satisfying the topology of particular network. The chro- mosomes are of variable length, each of which is the encoding of a path from the source node S to the des- tination node D. Random selection of solutions create R. Hemalatha et al; Informacije Midem, Vol. 47, No. 4(2017), 233 – 240 236 initial population. The initial population has only one chromosome. 3.3 Crossover and Mutation Crossover does not depend on the position of nodes in routing paths. One pair is randomly taken and the crossing site of each chromosome is identified by the locus of each node. The crossing points of two chromo- somes may be different from each other (Ahn and Ram- akrishna 2002). During mutation, the mutation site of the parent chromosome is chosen randomly. From the mutation site to the destination, different path chosen is based on the topology database. 3.4 Calculation of fitness function The fitness function is formulated as in equation (1) and is to evaluate the quality of the chromosomes. 3.5 Shuffled Frog Leaping Algorithm Shuffled Frog Leaping Algorithm (SFLA) is a natural inspired metaheuristic algorithm. Novelty of this al- gorithm is its fast convergence speed. It combines the advantages of the both the genetic-based memetic algorithm and the behavior-based Particle Swarm Op- timization (PSO) algorithm. In the SFLA, possible solu- tions are defined by a group of frogs which is referred to as population. These groups of frog are partitioned into several communities referred to as memeplexes. Each frog in the memeplexes perform local search. The behavior of individual frog is influenced by behaviors of other frogs within each memeplex and it develops through a process of memetic evolution. After a cer- tain number of memetic evolutions, the memeplexes are forced to mix together and through shuffling pro- cess, new memeplexes are formed. Until convergence criteria are satisfied, the local search and the shuffling processes continue. The flowchart of Shuffled frog leaping algorithm is illustrated in Fig.3 (Roshni et al 2016). The various steps are as follows: a) SFLA involves a population ‘P’ of possible solu- tion, defined by a group of virtual frogs(n). b) Frogs are sorted in descending order based on their fitness and partitioned into subsets called as memeplexes (m). c) Frog i is expressed as Xi = (Xi1, Xi2, …..Xin) where X represents number of variables. d) Frogs with worst and best fitness are identified as Xw and Xb within each memeplex. e) Frog with global best fitness is identified as Xg. f ) The frog with worst fitness is improved based on the following equation. Di=rand() (Xb -Xw) (15) Xneww=X oldw+ Di (16) Rand() is a random number in the range of [0,1] (Muzaf- far 2006). Figure 3: Flow diagram of SFLA R. Hemalatha et al; Informacije Midem, Vol. 47, No. 4(2017), 233 – 240 237 Di is the step size of i-th leaping frog and Dmax is the maximum step size allowed. If the fitness value of new Xw is better than the current one, Xw will be accepted. Otherwise, the calculated step size of leaping frog Di and new fitness Xneww are recomputed with Xb replaced by Xg. Further if no improvement is achieved, a new Xw is generated randomly. The update operation is repeat- ed for specific number of iterations. After a predefined number of memetic evolutionary steps within each memeplex, the solutions of evolved memeplexes are replaced into new population. This is called shuffling process. Global information exchange among the frogs is promoted by the shuffling process. The population is then sorted in order of decreasing performance values and updates the population based on best frog’s posi- tion, repartition the frog group into memeplexes and progress the evolution within each memeplex until the convergence criteria are satisfied (Samuel and Rajan 2014). 4 Simulation results The optimization algorithms have been carried out in MATLAB R2012b. Simulations are carried out for a 14 node network similar to NSFNET network topology with 21 bidirectional links. Fig.4 depicts the fitness of the genetic algorithm and shuffled frog leaping algo- rithm against the execution time. The fitness function involves cost, number of hops and holding time. Better fitness is achieved for a smaller execution time. Figure 4: Fitness function of GA and SFLA Fig.5 and 6 shows the variation in the blocking proba- bility assuming different values of adjacent wavelength rejection ratios for GA and SFLA respectively. In each case by executing the program several times and then by computing the average, mean blocking probability is estimated. In FWM aware priority based wavelength assignment, the mean blocking probability decreases for a reduction in each of the adjacent wavelength re- jection ratio. To reduce the FWM crosstalk equal and unequal channel spacing is also used which is said to be spectrum separation technique. The comlexity is lower in this technique. But the mean blocking prob- ability is lesser and fitness score is better in the dynam- ic wavelength allocation based on FWM aware based priority assignment that makes it advantageous to be used. Figure 5: Mean blocking probability for a fixed net- work load using GA Figure 6: Mean blocking probability for a fixed net- work load using SFLA Fig.7 shows the rate of convergence of genetic algo- rithm and shuffled frog leaping algorithm for first fit, random, round robin, wavelength ordering and FWM aware priority based wavelength assignment tech- niques. By randomly selecting an individual and fix- ing the best fitness value, the curves are plotted. The average fitness score decreases with increase in gen- erations. Average fitness score for GA and SFLA using different wavelength assignment techniques are ap- proximately the same. FWM priority based assignment has higher average fitness score. R. Hemalatha et al; Informacije Midem, Vol. 47, No. 4(2017), 233 – 240 238 Figure 7: Average fitness score for GA and SFLA The mean execution time of the five wavelength as- signment techniques for different network load in Er- lang using GA and SFLA are in Table 1. FWM aware pri- ority based wavelength assignment technique has the least mean execution time for different network loads in both the algorithms. However, the mean execution time is minimum using SFLA compared to GA. The experimental results in Table 2 show that wave- length ordering and round robin exhibits less mean blocking probability with respect to channel rejection ratio and number of generations respectively. Average fitness score is higher and the mean execution time is minimum in FWM aware priority based wavelength assignment technique. Comparing Genetic Algorithm and Shuffled Frog Leap Algorithm, Shuffled Frog Leap Algorithm achieves least mean blocking probability and a mean execution time for different wavelength as- signment techniques such as First Fit, Random, Round Robin, Wavelength Ordering and FWM aware priority based wavelength assignment though the average fit- ness score is approximately same for both the algo- rithms. 5 Conclusions Routing and Wavelength Assignment (RWA) problem is one of the most complex optimization problems in optical networks. In the proposed work, Genetic Algo- Table 1: Mean Execution Time of different wavelength assignment techniques using GA and SFLA Wavelength As- signment Tech- niques Mean Execution Time (w.r.to network load(Erlang)) using GA Mean Execution Time (w.r.to network load(Erlang)) using SFLA 0 1.4 2.7 3.6 4.4 0 1.4 2.7 3.6 4.4 First Fit 0.1200 0.0432 0.0689 0.1038 0.1019 0.1191 0.0423 0.0654 0.1018 0.1003 Random 0.3000 0.2372 0.2328 0.3155 0.3762 0.2987 0.2372 0.2328 0.3155 0.3762 Round Robin 0.1200 0.1736 0.1613 0.2004 0.2251 0.1198 0.1703 0.1610 0.2001 0.2248 Wavelength Ordering 0.0500 0.0062 0.0123 0.0302 0.0415 0.0490 0.0059 0.00117 0.0295 0.0409 FWM priority based Assignment 0.0050 4.275e-11 8.509e-11 2.1167e-10 2.94e-10 0.038 4.257e-11 8.503e-11 2.1068e-10 2.85e-10 Table 2: Comparison of GA and SFLA for different wavelength assignment techniques Wavelength Assignment Techniques GA SFLA Mean Blocking Probabil- ity (w.r.to channel rejection ratio) Average fitness score Mean Block- ing Probabil- ity (w.r.to no. of genera- tions) Mean Execution Time Mean Blocking Probability (w.r.to chan- nel rejection ratio) Average fitness score Mean Block- ing Probabil- ity (w.r.to no. of genera- tions) Mean Execution Time First Fit 0.8910 2.1184 0.5176 0.0829 0.8899 2.1184 0.4508 0.008025 Random 0.7875 0.6087 0.6035 0.2711 0.7802 0.6087 0.5805 0.2709 Round Robin 0.5225 1.023 0.2018 0.1619 0.1009 1.023 0.0010 0.1618 Wavelength Ordering 0.0959 0.08175 - 0.0266 0.0947 0.08175 - 0.0256 FWM based Assignment - 12.481 - 0.00070 - 12.481 - 0.00067 R. Hemalatha et al; Informacije Midem, Vol. 47, No. 4(2017), 233 – 240 239 rithm and Shuffled Frog Leaping Algorithm are used to solve this problem. The fitness function minimizes the cost, number of hops and blocking probability. Five different wavelength assignment techniques such as first fit, random, round robin, wavelength ordering and FWM aware priority based wavelength assignment are used while evaluating the performance of GA and SFLA. In SFLA, better fitness value is achieved compared to GA. Among different wavelength assignment tech- niques, FWM aware priority based wavelength as- signment technique gives maximum average fitness score and least mean execution time. Comparing these optimization algorithms, SFLA is better than GA with minimum mean blocking probability, less mean execu- tion time and better fitness value. SFLA approach has a lower time complexity compared to Genetic Algorithm and hence the proposed scheme may provide certain degree of flexibility in the network design. 6 References 1. A. Adhya and D. Datta, 2009. Design methodol- ogy for WDM backbone networks using FWM- aware heuristic algorithm. Optical Switching and Networking, 6: 10–19. 2. C. W. Ahn and R. S. Ramakrishna, 2002. A genetic algorithm for shortest path routing problem and the sizing of populations. IEEE Transactions on Evolutionary Computation, 6: 566–579. 3. A´ lvaro Rubio-Largo, Miguel A. Vega- Rodriguez, Juan A. Gomez-Pulido and Juan M. Sanchez- Pe´rez, 2012. A Comparative Study on Multi ob- jective Swarm Intelligence for the Routing and Wavelength Assignment Problem. IEEE Transac- tions on systems, man, and cybernetics , 4: 1644– 1655. 4. David Bisbal, Ignacio de Miguel and Fernando Gonzalez, 2004. Dynamic Routing and Wave- length Assignment in Optical Networks by Means of Genetic Algorithm. Photonic Network Commu- nications, pp: 43-58. 5. G. Giftson Samuel and C. Christober Asir Rajan, 2014. A Modified Shuffled Frog Leaping Algo- rithm for Long-Term Generation Maintenance Scheduling. Springer, 258: 11-24. 6. Joan Triay and Cristina Cervello-Pastor, 2010. An Ant-Based Algorithm for Distributed Routing and Wavelength Assignment in Dynamic Optical Net- works. IEEE journal on selected areas in communi- cations , 28: 542-552. 7. V. T. Le, X. Jiang, S. H. Ngo and S. Horiguchi, 2005. Dynamic RWA Based on the Combination of Mo- bile Agents Technique and Genetic Algorithms in WDM Networks with Sparse Wavelength Conver- sion. IEICE Transactions on Information and Sys- tems, 9: 2067-2078. 8. Muzaffar, Kevin and Fayzul Pasha, 2006. Shuffled frog-leaping algorithm: a memetic meta-heuristic for discrete optimization. Engineering Optimiza- tion, 38, 2: 129–154. 9. R. Ramaswami and K.N. Sivarajan, 2000. Optical Networks: A Practical Perspective. Morgan Kauf- mann Publishers, San Francisco. 10. D. Srinath and J. Janet, 2013. Secured Ant Colony Optimization Routing for Wireless Network. Asian Journal of Information Technology, 12: 83-90. 11. Urmila Bhanjaa, Sudipta Mahapatra and Rajar- shi Roy, 2010. A novel solution to the dynamic routing and wavelength assignment problem in transparent optical networks. International Jour- nal of Computer Networks and Communications, 2: 119-130. 12. Urmila Bhanjaa, Sudipta Mahapatra and Rajarshi Roy, 2012. FWM aware evolutionary program- ming algorithm for transparent optical networks. Photonic Network Communications, 3: 285-299. 13. Urmila Bhanjaa and Sudipta Mahapatra, 2013. A metaheuristic approach for optical network op- timization problems. Elsevier-Applied Soft Com- puting, 13: 981–997. 14. Urmila Bhanjaa, Sudipta Mahapatra and Rajarshi Roy, 2013. An evolutionary programming algo- rithm for survivable routing and wavelength as- signment in transparent optical networks. Elsevi- er-Information Sciences, 222: 634–647. 15. X. Wang, M. Brandt-Pearce, and S. Subramaniam, 2014. Distributed Grooming, Routing, and Wave- length Assignment for Dynamic Optical Networks Using Ant Colony Optimization. IEEE/OSA Journal of Optical Communications and Networks, 6: 578- 589. 16. Y. S. Kavian ,W. Ren , H. F. Rashvand, M. S. Leeson , M. Naderi and E. L. Hines, 2009. Genetic Algorithm for Designing DWDM Optical Networks under De- mand Uncertainty. Proceedings of ICTON Medi- terranean Winter Conference, December 10-12, 2009, Angers, pp: 1-4. 17. Yousef S. Kavian, Arash Rashedi, Ali Mahani and Zabih Ghassemlooy, 2013. Routing and wave- length assignment in optical networks using Ar- tificial Bee Colony algorithm. Elsevier-Optik, 124: 1243-1249. 18. Roshni. V. V, R. Hemalatha and R. Mahalakshmi, 2016. Optimization of Routing and Wavelength assignment in passive optical networks. Pak. J. of Biotechnology, Special issue on innovations in information embedded and communication sys- R. Hemalatha et al; Informacije Midem, Vol. 47, No. 4(2017), 233 – 240 240 tems, Vol. 13: 247-251. 19. B. Batagelj, V. Janyani and S. Tomazic, 2014. Re- search Challenges in optical communications to- wards 2020 and beyond. Informacije MIDEM, Vol. 44:177-184. 20. M. Vidmar, 2001. Optical-fiber communications: components and systems. Informacije MIDEM, Vol. 31:246-251. Arrived: 04. 07. 2017 Accepted: 03. 10. 2017 R. Hemalatha et al; Informacije Midem, Vol. 47, No. 4(2017), 233 – 240