Ant colony optimization for dynamic routing and wavelength assignment in WDM networks with sparse wavelength conversion

被引:11
作者
Chen, Ming-Tsung [2 ,3 ]
Lin, Bertrand M. T. [1 ]
Tseng, Shian-Shyong [3 ,4 ]
机构
[1] Natl Chiao Tung Univ, Inst Informat Management, Dept Informat & Finance Management, Hsinchu, Taiwan
[2] Chunghwa Telcom Co Ltd, Telecommun Strategy & Mkt Res Dept, Telecommun Lab, Taipei, Taiwan
[3] Natl Chiao Tung Univ, Dept Comp & Informat Sci, Hsinchu, Taiwan
[4] Asia Univ, Dept Informat Sci & Applicat, Taichung, Taiwan
关键词
Routing and wavelength assignment; Communication cost; Delay bound; Approximate solution; Ant colony optimization; ALGORITHMS;
D O I
10.1016/j.engappai.2010.05.010
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
Since optical WDM networks are becoming one of the alternatives for building up backbones, dynamic routing, and wavelength assignment with delay constraints (DRWA-DC) in WDM networks with sparse wavelength conversions is important for a communication model to route requests subject to delay bounds. Since the NP-hard minimum Steiner tree problem can be reduced to the DRWA-DC problem, it is very unlikely to derive optimal solutions in a reasonable time for the DRWA-DC problem. In this paper, we circumvent to apply a meta-heuristic based upon the ant colony optimization (ACO) approach to produce approximate solutions in a timely manner. In the literature, the ACO approach has been successfully applied to several well-known combinatorial optimization problems whose solutions might be in the form of paths on the associated graphs. The ACO algorithm proposed in this paper incorporates several new features so as to select wavelength links for which the communication cost and the transmission delay of routing the request can be minimized as much as possible subject to the specified delay bound. Computational experiments are designed and conducted to study the performance of the proposed algorithm. Comparing with the optimal solutions found by an ILP formulation, numerical results evince that the ACO algorithm is effective and robust in providing quality approximate solutions to the DRWA-DC problem. (C) 2010 Elsevier Ltd. All rights reserved.
引用
收藏
页码:295 / 305
页数:11
相关论文
共 29 条
[1]  
CHEN MT, 2003, P INT S COMM ISCOM T
[2]   LIGHTPATH COMMUNICATIONS - AN APPROACH TO HIGH BANDWIDTH OPTICAL WANS [J].
CHLAMTAC, I ;
GANZ, A ;
KARMI, G .
IEEE TRANSACTIONS ON COMMUNICATIONS, 1992, 40 (07) :1171-1182
[3]  
Dijkstra E. W., 1959, NUMER MATH, V1, P269
[4]   Ant colonies for the travelling salesman problem [J].
Dorigo, M ;
Gambardella, LM .
BIOSYSTEMS, 1997, 43 (02) :73-81
[5]  
DORIGO M, 1991, 91016 IT POL MIL
[6]  
GARLICK RM, 2002, P ANTS 2002 BRUSS BE, P250
[7]  
GREEN PE, 1992, FIBER OPTIC NETWORKS
[8]   Performance of WDM transport networks [J].
Karasan, E ;
Ayanoglu, E .
IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, 1998, 16 (07) :1081-1096
[9]   RWA problem for designing DWDM networks-delay against capacity optimisation [J].
Kavian, Y. S. ;
Rashvand, H. F. ;
Ren, W. ;
Leeson, M. S. ;
Hines, E. L. ;
Naderi, M. .
ELECTRONICS LETTERS, 2007, 43 (16) :892-893
[10]   Algorithms for routing and wavelength assignment based on solutions of LP-relaxations [J].
Krishnaswamy, RM ;
Sivarajan, KN .
IEEE COMMUNICATIONS LETTERS, 2001, 5 (10) :435-437