Chinese Journal of Computers   Full Text
Title	Solving QoS Multicast Routing Problem Based on Heuristic Genetic Algorithm
Authors	WANG Zheng-Ying SHI Bing-Xin
Address	(Department of Electronics & Information Engineering, Huazhong University of Science and Technology, Wuhan 430074)
Year	2001
Issue	No.1(55-61)
Abstract &   Background	In this paper, we study the bandwidth, delay, delay jitter, and packet loss-constrained least-cost multicast routing problem which is known to be NP-complete, and present a heuristic genetic algorithm to solve the problem. Firstly, the links with a bandwidth less than the bandwidth requirement are removed, thus the remained links in the refined graph must satisfy the bandwidth constraint. Then the heuristic genetic algorithm is adopted to solve the minimal multicast tree with delay constraint. The proposed genetic algorithm has the following characteristics: (1) Tree structure coding scheme, by which we can use any data structure of the tree to describe the chromosome structure, and omits the coding and decoding process. (2) Elitist selection model, by which we first select the optimal individuals and directly copy them to the next generation and then select the rest individuals by the proportional model. (3) Heuristic crossover operation, which first selects links with same parent and copy them to the children directly, and then connects the separate sub-trees to form a multicast tree using the least-delay paths if neither parent satisfies the delay constraint, or the least-cost ones if either parent satisfies the delay constraint. (4) Instructional mutation operations, by which the mutation procedure first randomly selects a subset of nodes according to the mutation probability, and then breaks the multicast tree into some separate sub-trees by removing all the links that are incident to the selected nodes. Finally it re-connects those separate sub-trees into a new multicast tree by randomly selecting the least-delay or the least-cost paths between them. Simulations have verified that this algorithm is efficient and effective. keywords quality of service, multicast routing, heuristic, genetic algorithm