Title: A genetic algorithm for Multicast Routing under Delay Constraint in WDM network with different light splitting
Authors: Chen, MT
Tseng, SS
資訊工程學系
Department of Computer Science
Keywords: genetic algorithm;multicast routing;WDM network;delay constraint;splitting degree;NP-hard
Issue Date: 1-Jan-2005
Abstract: Because optical WDM networks will become a realistic choice for buildings backbones, multicasting in the WDM network should be supported for various network applications. In this paper, a new multicast problem, Multicast Routing under Delay Constraint Problem (MRDCP), routing a request with delay bound to all destinations in a WDM network with different light splitting is solved by genetic algorithms (GAs), where different light splitting means that nodes in the network can transmit one copy or multiple copies to other nodes by using the same wavelength. The MRDCP can be reduced to the Minimal Steiner Tree Problem (MSTP) which has been shown to be NP-Complete. We propose a destination-oriented representation to represent chromosomes, three general genetic operators (selection, crossover, and mutation), four types of operators (Chromosome Crossover, Individual Crossover, Chromosome Mutation, and Individual Mutation). Four mutation heuristics (Random Mutation (RM), Cost First Mutation (CFM), Delay First Mutation (DFM), and Hybrid Mutation (HM)) are employed in the GA method. Finally, experimental results show that our solution model call obtain a near optimal solution.
URI: http://hdl.handle.net/11536/25399
ISSN: 1016-2364
Journal: JOURNAL OF INFORMATION SCIENCE AND ENGINEERING
Volume: 21
Issue: 1
Begin Page: 85
End Page: 108
Appears in Collections:Articles