Research On A Genetic Algorithm For The QoS Multi-Multicast Routing

The development of internet has given rise to many new communication services such as video broadcasting, multimedia conference, and remote education; this application develops the multi-multicast communication. The multiple-multicast routing problem can be formulated as finding a minimal-cost routes set from many sources to many destinations and satisfied with bandwidth and delay constraints in a given networks. This is a more complex problem than the problem from one source to multiple destinations. It is a typical NP-hard problem.The current approaches for multi-multicast routing problem include heuristic algorithm and genetic algorithm. In this thesis, the application of genetic algorithm in the QoS multi-multicast routing 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 problem. Therefore, genetic algorithm provides us some new method to solve QoS multi-multicast routing problem.This paper proposed a genetic algorithm to solve the problem based on the idea of decomposing the complex problem into two objections. According to the objections of finding multiple excellent multicast trees of a source to its destinations satisfied the delay constraint and the optimal combination of multicast trees of each origins, an algorithm with two genetic modules are represented. In the module of finding multicast tree the coding with tree-structured chromosome by connected nodes, and crossover and mutation operators are designed. The numerical simulation shows that it is efficient to search high quality solutions for the multiple-multicast routing problem.