A QoS Multicast Routing Based On Genetic Algorithm

The development of internet has given rise to many new communication services such as video broadcasting, multimedia conference, remote education, these applications develop the multicast communication. Data packet is transmitted from source node to multiple destination nodes in multicast communication. A fundamental issue in multicast is how to determine an efficient route.Tree construction is a commonly used approach in solving the multicast routing problem. So, Multicast routing algorithms are used to compute multicast trees that satisfy different QoS requirements. The current approaches for multicast routing problem include heuristic algorithms and genetic algorithm. In this thesis, the application of genetic algorithm in the QoS multicast problem is studied. The genetic algorithm is a global random optimization method, which has so many advantages, such as concurrent searching and colony optimize, and has been applied successfully in many fields of NP complete problems. Therefore, genetic algorithm provides us some new methods to solve the QoS multicast routing problems. The simulated annealing/genetic algorithm is proposed for Delay-Contrained Multicast Routing problem (DCMR). The proposed algorithm introduces simulated annealing to genetic operators so that it can enhance the ability of the global search and the convergence speed. The routing encoding method is used, so the genetic operators can be operated comparatively easily.And the algorithm analyse and solve the loop problem in course of operation. Simulations show the proposed algorithm can get low cost multicast tree without violating the delay constraint in fewer generations. With beter cost and convergence performance, the proposed algorithm can meet the demands of the practical applications. A multiobjective genetic algorithm is presented to solve the multicast routing problem with multiple QoS constraints, which bases on the analysis of the drawback of the single-objective algorithm in the field, such as multiple Qos constraints are combined to form a scalar single-objective so the solution becomes highly sensitive to the weight vector and uniqueness. The proposed algorithm also bases on the routing encoding method, and utilize the concept of Pareto Dominance to optimizes the multiple QoS parameters simultaneously and is capable of discovering a set of nondominate routes, so it can overcome the shortage of the single-objective optimization of routing. The niche technology is introduced to the algorithm to keep the population diversity in order to avoid the premature convergence and the unique solution. Finally, the simulation show this algorithm is effective.