Browsing by Author "Chen, Ming-Tsung"

Now showing 1 - 2 of 2

Ant colony optimization for dynamic routing and wavelength assignment in WDM networks with sparse wavelength conversion
(2011-03-01)
Chen, Ming-Tsung
;
Lin, Bertrand M. T.
;
Tseng, Shian-Shyong
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
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.
Multicast routing and wavelength assignment with delay constraints in WDM networks with heterogeneous capabilities
(2008-01-01)
Chen, Ming-Tsung
;
Lin, B. M. T.
;
Tseng, Shian-Shyong
;
資訊工程學系
;
資訊管理與財務金融系註：原資管所+財金所
Because optical wavelength division multiplexing (WDM) networks are expected to be realized for building up backbone in the near future, multicasting in WDM networks needs to be addressed for various network applications. This paper studies an extended multicast routing and wavelength assignment (RWA) problem called multicast routing and wavelength assignment with delay constraint (MRWA-DC) that incorporates delay constraints in WDM networks having heterogeneous light splitting capabilities. The objective is to find a light-forest whose multicast cost, defined as a weighted combination of communication cost and wavelength consumption, is minimum. An integer linear programming (ILP) model is proposed to formulate and solve the problem. Experimental results show that using CPLEX to solve the ILP formulation can optimally deal with small-scale networks. Therefore, we develop a heuristic, near-k-shortest-path heuristic (NKSPH), to solve the problem in large-scale networks. Numerical results indicate that the proposed heuristic algorithm can produce approximate solutions of good quality in an acceptable time. (C) 2006 Elsevier Ltd. All rights reserved.