QoS Multicast Routing Optimization Algorithm Based On Quantum-behaved Particle Swarm Optimization Algorithms

QoS (Quality-of-Service) multicast routing in networks is a very important research issues in the areas of networks. It has been demonstrated that it is NP-Complete to find a feasible multicast tree with two independent additive path constraints. The QoS requirements can be classified into link constraints (e.g., bandwidth), path constraints (e.g., end to end delay) and tree constraints (e.g., delay-jitter). Generally, heuristics are employed to solve this NP-complete problem. Some GAs has been used to solve the problem form different aspects.As References [2, 3], a quantum-behaved particle swarm optimization algorithm (QPSO) was originally proposed by Sun. It has been proved to be an efficient method for many global optimization problems and in some cases it does not suffer the difficulties encountered by GA. QPSO was originally proposed to solve the continuous functions optimization. So far, it has rarely been used to discrete Combinatory Optimization Problems (COP). The goal of this paper is to solving QoS multicast routing problem via QPSO.Firstly, the knowledge of QoS, especially of QoS routing algorithm problem is studied. The theories and application strategies of several optimization algorithms that solved QoS multicast routing algorithm are analyzed. And the specialties of these algorithms are compared. As QoS constrains character, multi-objective optimization problems with multiple constraints are also studied.Secondly, the network model of QoS multicast routing is constructed. And constrained terms in the problem are processed by the penalty function. The processes of using GA and GA-TS to solve the QoS multicast routing problem are introduced. The courses of using PSO, especially QPSO to solve the QoS multicast routing problem are also described. The QoS multicast routing optimization problem is changed into an integer-programming problem by designing a new integer coding method that can use PSO and QPSO to solve the QoS multicast routing problem successfully.Finally, the simulation of solving QoS multicast routing problem based on QPSO is tested, which using a network model of QoS multicast routing. For contrast, PSO, GA and GA-TS are also tested in the same condition. This proposed algorithm is applied to illustrate its higher searching efficiency in comparison with PSO, GA and GA-TS for this routing optimization problem what computer simulations have verified. QPSO is more efficient and effective which the test results are proved.