원문정보
초록
영어
QoS multicast routing is a non-linear combinatorial optimization problem that arises in many multimedia applications. Providing QoS support is crucial to guarantee effective transportation of multimedia service in multicast communication. Computing the band-widthdelay constrained least cost multicast routing tree is an NP-complete problem. In this paper, a novel heuristic QoS multicast routing algorithm with bandwidth and delay constraints is proposed. The algorithm applies the discrete particle swarm optimization (PSO) algorithm to optimally search the solution space for the optimal multicast tree which satisfies the QoS requirement. New PSO operators have been introduced to modify the original PSO velocity and position update rules to adapt to the discrete solution space of the multicast routing problem. A new adjustable PSO-GA hybrid multicast routing algorithm which combines PSO with genetic operators was proposed. The proposed hybrid technique combines the strengths of PSO and GA to realize the balance between natural selection and good knowledge sharing to provide robust and efficient search of the solution space. Two driving parameters are utilized in the adjustable hybrid model to optimize the performance of the PSO-GA hybrid by giving preference to either PSO or GA. Simulation results show that with the correct combination of GA and PSO the hybrid algorithm outperforms both the standard PSO and GA models. The flexibility in the choice of parameters in the hybrid algorithm improves the ability of the evolutionary operators to generate strong-developing individuals that can achieve faster convergence and avoids premature convergence to local optima.
목차
1. Introduction
2. Particle Swarm Optimization
3. Multicast Routing Problem Formulation
4. Proposed Multicast Routing Algorithm
4.1. Particle Encoding
4.2. Fitness Function
4.3. Simple PSO Multicasting Algorithm
5. Hybrid PSO-GA Multicast Routing Algorithm
5.1. Crossover Operator
5.2. Mutation Operator
5.3. Discard Duplicate Particles
6. Experimental Results
7. Conclusions
References