다수의 QoS 제약 조건을 고려한 GA 기반의 멀티캐스트 라우팅 알고리즘
A GA-based Multicast Routing Algorithm with Multi-QoS Constraints
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
본 논문에서는 다수의 Quality of Service (QoS) 제약조건 (bandwidth, 경로지연시간)을 만족하는 유전자 알고리즘 기반의 멀티캐스트 라우팅 기법을 제안한다. 제안 알고리즘의 목적은 다수의 QoS 제약조건을 만족하면서, 하나의 출발지로부터 다수의 목적지들까지 최적 경로를 구성하는 것이다. 이를 위해 제안 알고리즘에서는 출발지로부터 목적지들까지의 경로들을 트리 구조의 염색체로 부호화(encoding) 하였다. 또한, 주어진 QoS 제약 조건을 반영한 형태의 적합도 함수를 고려하였다. 그리고, 제안 트리 구조의 염색체 부호화 방법에 적합한 교배(crossover)와 돌연변이(mutation) 연산을 설계하였다. 제안 교배 연산은 유전자의 위치에 무관하게 두 염색체들 간의 부분 경로(sub-path)를 상호 교환하여 해-표면(solution- surface)을 효과적으로 탐색할 수 있도록 한다. 제안 돌연변이 연산은 부분 경로를 새로운 부분 경로로 대처함으로써 준최적해(local optimum)로의 수렴을 방지한다. 한편, 교배 연산을 통하여 발생 가능한 (진화) 부적합 염색체를 효과적으로 치료할 수 있는 복구 함수(repair function)를 설계하였다. 실험 결과를 통하여 제안 기법은 기존 접근방식보다 멀티캐스트 라우팅에 대해 최적성 및 수렴 성능에서 더 우수한 성능 보였다.
Abstract
This paper presents a genetic-inspired multicast routing algorithm guaranteeing Quality of Service (i.e., bandwidth and delay variant). The aim is to transplant the principle of state-of-the-art genetic-based optimization into multicast communication system, for discovering a minimal spanning tree (MST) from a source to multiple destinations. To this end, variable-length chromosomes are employed. They are encoded by positive integers which represent nodes’ IDs. Each chromosome is formed as a tree structure, a representation from genetic programming (GP). New variation operators (i.e., crossover and mutation) have been designed for the purpose. Crossover exchanges partial chromosomes (i.e., sub-trees) in a positionally independent manner. It maximally increases the exploratory power of the proposed algorithm. Mutation introduces (in part) a new sub-tree with low probability. It maintains a fair measure of genetic diversity (of population) so as to escape from local optima. Moreover, all the infeasible chromosomes are treated with a simple repair function. The synergy achieved by combing new ingredients (i.e., encoding, crossover, mutation, and repair function) offers an effective search capability that results in improved quality of solution and enhanced rate of convergence. Experimental results show that the proposed GA outperforms other heuristic algorithms.
참고문헌 (18)
- Chang Wook Ahn, "A Genetic Algorithm for Shortest Path Routing Problem and the Sizing of Populations", IEEE Transactions on Evolutionary Computation, 6(6), pp.566~579 (2002)
- Yee Leung, "A Genetic Algorithm for the Multiple Destination Routing Problems", IEEE Transactions on Evolutionary Computation, 2(4), pp.150~161 (1998)
- Leonard Barolli, "A QoS Routing Method for Ad-Hoc Networks Based on Genetic Algorithm", Proceedings of the 14th International Workshop on Database and Expert Systems Applications (DEXA'03). (2003)
- Fei Xiang, "QoS Routing based on genetic algorithm", Computer Communications, 22, pp.1392~1399 (1999)
- REN-HUNG HWANG, "Multicast Routing Based on Genetic Algorithms", Joural of Information Science and Engineering, 16, pp.885~901 (2000)
- Abolfazl Toroghi Haghighat, "-based heuristic algorithms for bandwidth-delay constrained least-cost multicast routing", Computer Communications, 27, pp.111~127 (2004)
- Zhou Xianwei, "A Genetic Algorithm for Multicasting Routing Problem", Proc. Int. Conf. Communication Technology (WCCICCT-2000), pp.1248~1253 (2000)
- David Beasley, "An Overview of Genetic Algorithms: Part 1, Fundamentals", University Computing, 15(2), pp.58~69 (1993)
- Lin Chen, "A Degree-Delay-Constrained Genetic algorithm for Multicast Routing Tree", Proceedings of the Fourth International Conference on Computer and Information Technology (CIT'04). (2004)
- Jorge Crichigno, "A Multicast Routing Algorithm Using Multiobjective Optimization", ICT 2004, LNCS 3124, pp.1107~1113 (2004)
- Moussa Hamdan, "Multicast Routing with Delay and Delay Variation Constraint Using Genetic Algorithm", CCECE 2004-CCGEI 2004, Niagara Falls (2004)
- Hua Chen, "Multicast Routing Optimization Algorithm with Bandwidth and Delay Constraints Based on GA", of Communication and Computer, 2(5) (2005)
- Xunxue Cui, "A Multiobjective Model for QoS Multicast Routing Based on Genetic Algorithm", Proceedings of the 2003 International Conference on Computer Networks and Mobile Computing (ICCNMC'03). (2003)
- Abdullah M.S. Alkahtani, "An Overview of Quality of Service (QoS) and QoS Routing in Communication Networks", PGnet, 2003 (2003)
- Mohamed F. Mokbel, "An Efficient Algorithm for Shortest Path Multicast Routing under Delay and Delay Variation Constraints", Proceedings of the Symposium on Performance Evaluation of Computer and Telecomm. Systems, SPECTS 2000, Vancouver, Canada (2000)
- Vachaspathi P. Kompella, "Multicast Routing for Multimedia Communication", IEEE, 1993, pp.1(3), ~
- Xiaola Lin, "Multicast Communication in Multicomputer Networks", IEEE Transaction on Parallel and Distributed Systems, 4(10) (1993)
- C.P. Ravikumar, "Sources-based delay-bounded multicasting in multimedia networks", Computer Communications, 21, pp.126~132 (1998)