Study On QoS Multicast Routing Optimization Based On Genetic Algorithm

With the development of Internet, the recent emergence of multimedia communications and cooperative works in distributed environments provides an incentive to system designers to include multicast communication support for these applications. A fundamental issue in multicast communication is how to determine an efficient multicast routing, namely in search of simple, effective and robust multicast routing algorithms. Multicast routing algorithms are used to compute multicast trees that satisfy quality of service requirement. The problem in search of multicast routing with QoS constrained is a NP-complete problem, so the problem can not be solved using the classical shortest path first algorithms such as Bellman-Ford and Dijkstra. Thus, most previous researchers have focused on developing heuristic algorithms to solve unconstrained and delay-constrained multicast routing problem. However, these heuristic algorithms have high computation complexity so they are not fit in practicality. In the paper, Genetic Algorithm is used to the QoS multicast routing problem and four typical respects of research have been put forward. First of all, candidate routing tables are designed based on the characteristic of multicast routing problem and the encoding method of nodes string with equal length is used. Due to the disadvantage of standard Genetic Algorithm, Simulated Annealing is introduced to genetic operators. The proposed algorithm enhances not only global search ability but also convergence speed. Secondly, in allusion to the limitation of single constraint or unconstrained multicast routing problem, a common multiconstrained multicast routing based on Genetic Algorithm is realized. The routing encoding method is used, so the genetic operators can be operated comparatively easily. The algorithm manifests better search ability of Genetic Algorithm. Moreover, analyzing the characteristic of multicast routing and Genetic Algorithm, a dual-populations Genetic Algorithm is designed. In the process of evolution, the grafted population instructs the evolution direction of the evolutive population. To a great extent, the convergence speed of the algorithm is improved. Finally, the Genetic Algorithm based on two chromosomes solves bandwidth-delay-constrained least-cost multicast routing problem. When the initial population is produced, the traditional heuristic algorithm is introduced to the improved Genetic Algorithm. Dual mutation operator is used, and crossover operator is operated between two chromosomes. Simulation results show this algorithm is effective.