QoS Multicast Routing Based On Immune Genetic Algorithm

With fast development of network technologies, increase of network bandwidth and processing power makes the network provide more multimedia applications, and also makes the multicast communication that supports "one-to-many" or "many-to-many" become a necessary mode of- multimedia services. 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 and genetic algorithm to solve unconstrained and delay-constrained multicast routing problem. However, these heuristic algorithms have high computation complexity so they are not fit in practicality and these genetic algorithms have two flows: premature convergence and easily stick to local optimum so they can't find a global optimal solution.Aiming at the demerit of Genetic algorithms, concentration adjustment mechanism of immune system was introduced to the genetic algorithm, thus immune genetic algorithm was formed. Based on the improved immune genetic algorithm with elitism (IIGAE) , this paper proposed a novel routing selection approach to solve QoS multicast routing problem with minimum cost and constrains of bandwidth, delay and delay jitter. Firstly, it used the preprocessing mechanism to get rid of the links that didn't satisfy bandwidth constraint in network structure. And the TV shortest paths' Dijkstra algorithm was utilized to establish the alternative path set of the algorithm coding space. Secondly, it generated the initial population of IIGAE, using the tree structure coding based on the path. So each individual of the population represented a candidate solution to the multicast routing problem. Finally, IIGAE algorithm was used to optimize the population. It ultimately obtained the multicast routing meeting QoS requirements. The simulation results show that this proposed algorithm is highly efficiency and it can find a multicast tree at the lowest cost and at fast convergence speed.