TY - JOUR

T1 - Solving the converter placement problem in WDM ring networks using genetic algorithms

AU - CHAN, Tak-Ming

AU - KWONG, Sam

AU - MAN, K. F.

PY - 2003

Y1 - 2003

N2 - In this paper, we study the converter placement problem with static traffic in wavelength division multiplexing ring networks using sparse wavelength conversion. Three heuristic techniques, genetic algorithms (GA), simulated annealing (SA) and tabu search (TS), are utilized to solve this combinatorial optimization problem. Also, an alternative method, integer programming based heuristic (Lagrangian heuristic), is utilized to compare with the results of the three heuristic techniques. In order to investigate how effective the wavelength conversion is, we employ three approaches: (i) without wavelength conversion (i.e. no converter is allowed to be placed in the network); (ii) with wavelength conversion and each of the nodes has a converter placed, to compare with the approach of the converter placement problem; and (iii) with wavelength conversion and some nodes have a converter placed. We have considered three different scenarios in the simulation: (a) 10-node network; (b) 15-node network; and (c) 20-node network. The simulation results show that GA is able to find better solutions than SA, TS and Lagrangian heuristic in three different scenarios. Also, it is found that placing some wavelength converters in the network can minimize the total number of used wavelengths effectively and placing converters on only some nodes can reach the same performance as that when placing converters on all nodes.

AB - In this paper, we study the converter placement problem with static traffic in wavelength division multiplexing ring networks using sparse wavelength conversion. Three heuristic techniques, genetic algorithms (GA), simulated annealing (SA) and tabu search (TS), are utilized to solve this combinatorial optimization problem. Also, an alternative method, integer programming based heuristic (Lagrangian heuristic), is utilized to compare with the results of the three heuristic techniques. In order to investigate how effective the wavelength conversion is, we employ three approaches: (i) without wavelength conversion (i.e. no converter is allowed to be placed in the network); (ii) with wavelength conversion and each of the nodes has a converter placed, to compare with the approach of the converter placement problem; and (iii) with wavelength conversion and some nodes have a converter placed. We have considered three different scenarios in the simulation: (a) 10-node network; (b) 15-node network; and (c) 20-node network. The simulation results show that GA is able to find better solutions than SA, TS and Lagrangian heuristic in three different scenarios. Also, it is found that placing some wavelength converters in the network can minimize the total number of used wavelengths effectively and placing converters on only some nodes can reach the same performance as that when placing converters on all nodes.

UR - http://www.scopus.com/inward/record.url?scp=0037666897&partnerID=8YFLogxK

U2 - 10.1093/comjnl/46.4.427

DO - 10.1093/comjnl/46.4.427

M3 - Journal Article (refereed)

SN - 0010-4620

VL - 46

SP - 427

EP - 448

JO - Computer Journal

JF - Computer Journal

IS - 4

ER -