GA-based heuristic algorithms for bandwidth-delay-constrained least-cost multicast routing

被引:47
作者
Haghighat, AT [1 ]
Faez, K
Dehghan, M
Mowlaei, A
Ghahremani, Y
机构
[1] Amirkabir Univ Technol, Dept Elect Engn, Tehran 15914, Iran
[2] Iran Telecommun Res Ctr, Tehran, Iran
[3] Atom Energy Org Iran, Tehran, Iran
[4] Iran Univ Sci & Technol, Dept Comp Engn, Tehran, Iran
关键词
quality of service; multicast routing; multiconstrained Steiner tree; genetic algorithm;
D O I
10.1016/S0140-3664(03)00185-3
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 [计算机科学与技术];
摘要
The bandwidth-delay-constrained least-cost multicast routing is a challenging problem in high-speed multimedia networks. Computing such a constrained Steiner tree is an NP-complete problem. In this paper, we propose several novel solutions to this problem based on genetic algorithms (GA). The proposed solutions consist of six different schemes for genotype representation, and also several new heuristic algorithms for mutation, crossover, and creation of random individuals. We evaluate the performance and efficiency of the proposed algorithms in comparison with other existing heuristic and GA-based algorithms using simulation results. The most efficient combination of various proposed alternative algorithms is selected as our final solution by the simulation results. This proposed GA-based algorithm has overcome the existing algorithms considering average tree cost and running time. (C) 2003 Elsevier B.V. All rights reserved.
引用
收藏
页码:111 / 127
页数:17
相关论文
共 39 条
[1]
[Anonymous], IEEE T EVOL COMPUT
[2]
Genetic framework for the high level optimisation of low power VLSI DSP systems [J].
Bright, MS ;
Arslan, T .
ELECTRONICS LETTERS, 1996, 32 (13) :1150-1151
[3]
CHOTIPAT P, 1995, INT C NETW PROT IEEE, P332
[4]
Coello C.A.C., 2000, INT J SMART ENG SYST, V2, P299
[5]
COMPUTING NEAR-OPTIMAL SOLUTIONS TO THE STEINER PROBLEM IN A GRAPH USING A GENETIC ALGORITHM [J].
ESBENSEN, H .
NETWORKS, 1995, 26 (04) :173-185
[6]
Improved neural heuristics for multicast routing [J].
Gelenbe, E ;
Ghanwani, A ;
Srinivasan, V .
IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, 1997, 15 (02) :147-155
[7]
Gen M., 2000, Genetic Algorithms and Engineering Optimization
[8]
GUO L, 1999, P 5 IEEE REAL TIM TE
[9]
GUOLIANG C, 1996, GENETIC ALGORITHMS I
[10]
HAGHIGHAT AT, 2002, ICCC 2002 C IND, P243