Research On Quantum-Inspired Evolutionary For Multicast Routing Algorithm

With the rapid development of Internet, a variety of multimedia applications, such as audio conferencing, online games, online trading, are increasing rapidly, leading to much more intensive bandwidth consumption and network congestion. Multicast technology, which transmits the same data from a source to a large number of destination nodes simultaneously, save a great deal of bandwidth and reduce network congestion. The paper centers on the algorithms which can construct delay-constrained and low-cost multicast routing trees. The main research work is summarized as follows:1. Quantum-inspired evaluation algorithm (QEA) based multicast routing algorithm is proposed, in which the multicast routing problem is transformed into the combinatorial optimization problem of the side in the network. The individuals in a population are represented by quantum encoding based on the side in the network to replace the coding of network candidate path set. The quantum rotation gate strategy is improved to accelerate convergence speed of the algorithm. Theoretical analysis and computer simulation show that the complexity of the proposed algorithm greatly reduced, and the results are stable. The algorithm converges fast and easy to operate.2. For dynamic multicast problem, combined with the advantage of coding and the construction processing of the multicast tree in the QEA for static multicast routing problem, QEA based dynamic multicast algorithm is proposed. We discussed the dynamics of two cases that the model of multicast group membership changes and the model of network topology changes. The population update operator and individual repair operator are introduced into the algorithm to compensate and repair the multicast tree after the dynamic changes. Simulations prove, the proposed algorithm is validity and reliability for dynamic multicast routing problems.3. For larger scale network multicast routing problem, learning from small-scale multicast problem solving and considering both the minimum cost of multicast tree and the complexity of the algorithm, we proposed the delay-constrained multicast routing algorithm for large scale network based on QEA, in which the individuals in a population are represented by multistate gene quantum bits coding based the path. In the individual’s updating, the quantum rotation gate strategy is applied to accelerate convergence. Simulation results show that, the algorithm can achieve a balance between the performance of multicast tree and the complexity of the algorithm, and the algorithm has the property of simple realization and flexible control.