An Efficient And Reliable Algorithm For The Rwa Problem In Optical Wdm Networks

An Efficient And Reliable Algorithm For The Rwa Problem In Optical Wdm Networks

G.Rajesh

M.Tech 2ndyear, E.C.E Department, V.R.Siddhartha Engineering College, A.P, India,

S.Chitti Babu

Associate Professor, E.C.E Department, V.R.Siddhartha Engineering College, A.P, India,

Abstract

The Routing and Wavelength Assignment (RWA) in Dense Wavelength Division Multiplexing (DWDM) optical networks is a complicated problem. Artificial Bee Colony (ABC) algorithm is an optimization algorithm based on the intelligent behaviour of honey bee swarm. ABC algorithm provides an attractive approach for solving RWA problem for large scale networks. In this paper ABC algorithm is used for solving RWA problem with better convergence speeds and to maximize the utilization of network resources. The simulation results show the efficiency of ABC based algorithm in making efficient use of resources.

Keywords: Routing and Wavelength Assignment, Artificial Bee colony algorithm, Large scale optical networks, convergence speed.

1. Introduction

   RWA algorithms in optical communication was initially presented by Mukharjee [1] and validated by Rama murthy & Mukharjee [2].RWA problem can be split into two independent parts.

   1. Find a root from source to destination.

   2. Assign a wavelength to selected route.

   Routing can be subdivided into static routing and dynamic routing. On analyzing various routing algorithms. It has seen shown that dynamic routing schemes [3] achieving better performance in reducing blocking probability and better utilization of bandwidth and resources. Assigning wavelengths to the routes subject to the following constraints [4]. If no wavelength convertors are available, the same wavelength must be assigned along the entire route. This is called wavelength continuity constraint. In addition, light paths that share a common physical link cannot be assigned the same wavelength. This is called the

   wavelength clash constraint. The objective of the

   RWA problem [5-6] is often to minimize the number of wavelengths used, or to maximize the number of light paths successfully set up subjected to limited number of wavelengths. Recent literature shows that there are many bio- inspired algorithms proposed to solve RWA problems in WDM networks.ABC algorithm is one of the most recently introduced optimization algorithms [7] based on the intelligent behavior of honey bee swarm. The objective of this paper is to introduce an algorithm based on ABC model to solve dynamic RWA problem in Optical WDM networks [8].

2. Artificial Bee Colony Model

   In the ABC algorithm, the colony of artificial bees contains three groups of bees: employed bees, onlookers and scouts. The first half of the colony consists of the employed artificial bees and the second half includes the onlookers. For every food source, there is only one employed bee. In other words, the number of employed bees is equal to the number of food sources around the hive. The employed bee whose food source has been exhausted by the bees becomes a scout.

   1. ABC Procedure

      In this algorithm each food source is a possible solution for the problem under consideration and the nectar amount of a food source represents the quality of solution which is given by fitness Value. This value can be defined for a path (p) as

      fitness (p) = +w (1) Where , and are weighing factors, Length

      (p) is the length of path p, Fw is number of free wave lengths on path p, H is the hop count of path

      p. This means that for any arriving connection

      request, this algorithm chooses the path with best possible combinations of all these parameters.

      In the first step, randomly generated food source positions are considered as initial solutions. An onlooker bee chooses a food source depends on probability value associated with that food source

      ,pi can be calculated with the following equation

      Pi= (2)

      Where fi is the fitness value of the ith solution evaluated by its employed bee,

      And N is the number of food sources which is equal to the number of employed bees(BN).In order to produce a new food position from the old one , This algorithm uses the following expression

      Vij= Zij+Øij (Zij Zkj) (3)

      Where k and j are randomly chosen indexes and ki. Øij is a random number between [-1, 1].

      After the evaluation of each new position its performance is compared with old one. If it is better the old one is replaced by new food position. Otherwise old one is retained.If a position cannot be improved in a predetermined number o cycles called limit, the food source is assumed to be abandoned. The abandoned position will b replaced by a new food source found by scout.

      Zij= ) (4)

      Where zmin and zmax are lower and upper limits on zij.Thus the ABC algorithm has three control parameters. The number of food sources which is equal to number of employed or onlooker bees, value of limit, the maximum cycle number (MCN).

   2. ABC algorithm:

1. Start

2. Load the samples that are used for training

3. Generate the initial population. i= 1, 2

   .. N.

4. Evaluate the fitness of the population using (1) .

5. Initialize a variable called cycle to 1.

6. REPEAT

7. For i=1 ..N

{For each Employed bee} Calculate fitness value.

Produce a new solution using (3)

Apply greedy selection process.

1. Calculate the probability values Pi for the solutions using (2)

2. For i=1 . BN

   {For each onlooker bee}

   Select a solution based on values of pi Produce a new solution

   Calculate Fitness value.

   Apply Greedy selection process.

3. This randomly produced new solution replaces the abandoned solution for the scout (if exists) by using (4)

4. Memorize the best solution so far.

5. Increase the value of cycle by 1.

6. Until cycle= MCN.

7. END.

1. Problem statement

   Figure 1. Network topology

   The network shown in fig1 is modeled as an undirected graph. For a given set of connection requests the aim to establish a connection between source(s) and destination (d), so that the utilized wavelengths must be minimum.

   The objective is to minimize the number of wavelengths used by lightpaths to serve a given set of connection requests. The amount of utilizing capacity(number of wavelengths required) allocated to working(spare) light paths is denoted by ) for link l which is in the range from l to M.The minimization of wavelengths utilized by working and spare lightpaths to service a give n demand matrix may be written as

   fc=min +)}

   This is subjected to the following conditions.

   1. Each wave length can be utilized by only one light path.

   2. A connection request from source to destination must satisfy demand in terms of wavelength on each link between that node pair.

   3.1 Simulation results and discussions

   The simulation results are obtained from the network topology shown in Fig.1and the simulation environment is based on MatlabR2011a. The number of wavelengths on each link is taken as 10.A set of connection requests are generated, and the link state variables after routing and wavelength assignment are presented in Fig.3. From Fig.2.Iit is concluded that bigger populations have better speeds of convergence.

   4 different population sizes

   10

   3

   population=10 population=50

   0 population=100

   2

   10

   fitness

   1

   10

   0

   10

   -1

   10

   -2

   10

   -100 0 100 200 300 400 500 600 700 800 900 1000

   iterations

   Fig 2 Effect of population on convergence speeds

   Fig 3 Link state variables after Routing wavelength assignment

2. Conclusion:

   This paper demonstrates the performance of ABC algorithm for solving RWA problem in large scale optical WDM networks. The simulation results shows that bigger population sizes have better convergence speeds.

   It is an intelligent approach in utilizing the network resources such as wavelengths available on each link. There are several issues which remain as the scope for future studies such as effect of control parameters on the performance of ABC algorithm and link state variables.

3. References

1. H. Zang, J.P. He, B. Mukherjee, A review of routing and wavelength assignment approaches for wavelength-routed optical WDM networks, Optical Network Magazine 1 (1) (2000) 4760.

2. R.Ramamurthy, B.Mukherjee, and Fixed- alternate routing and length conversion in wavelength-routed optical networks, IEEE/ACM Transactions on networking (2002).

3. H. Zang, J.P. Jue, and B. Mukherjee, A review of routing and wavelength assignment approaches for wavelength-routed optical WDM networks, Optical Networks Magazine, vol. 1, no. 1, pp. 47- 60, 2000.

4. N. Skorin-Kapov, Routing and wavelength assignment in optical networks using bin packing based algorithms, European Journal of Operational Research, vol. 177, pp. 1167-1179, 2007.

5. Y.S. Kavian, W. Ren, M. Naderi, M.S. Leeson, and E.L. Hines, Survivable wavelength-routed optical network design using genetic algorithms, European Transactions on Telecommunications, vol. 19, no. 3, pp. 247-255, 2008.

6. J. Vesterstrøm, J. Riget, Particle Swarms Extensions for improved local, multi-modal, and dynamic search in numerical optimization,

   MSc.Thesis, May 2002

7. D. Karaboga, An idea based on honey bee swarm for numerical optimization, Technical Report-TR06,Erciyes University, Engineering Faculty, Computer Engineering Department, 2005.

8. D. Karaboga, and B. Basturk, On the performance of artificial bee colony (ABC) algorithm, Applied Soft Computing, vol.8, no. 3, pp. 687-697, 2008.