Research Of Multi-constrained Qos Multicast Algrotihm Based On Hybrid Cenetic Algorithm

In recent years, with staggering development of network technologies andincreasing of both network bandwidth and processing power which make thenetwork provide various operations of multimedia, At the same times, it alsomakes the multicast communication that supports"one-to-many"or"many-tomany"become a necessary mode of multimedia services. As the core technique ofhigh-speed network, routing has many research fields, for example, routingprotocols, routing policy and routing algorithms etc. A fundamental problem inmulticast communication is how to determine an efficient multicast routing,however, still, finding simple but effective and robust multicast routing algorithmshas been regarded as an unsolved problem in network fields.Many distributed multimedia applications have various demands on delay,delay variation, bandwidth and packet loss. The problem of searching multicastrouting with many QoS constraints is a NP-complete problem. Thus, most previousresearchers have been focusing on developing heuristic algorithms to solveunconstrained and multi-constrained multicast routing problem. However, theseheuristic algorithms have high computation complexity or easily stick to localoptimum so they are not fit in practicality. Therefore, the research on multicastrouting algorithms based on multi-constrained QoS becomes an important andhotspot part of network research fields.As a new global optimization search method, genetic algorithm that hasmany characteristics like simple and universal, robust, parallelism etc, and it hasbeen applied in many fields. However, it has two flows: premature convergenceand easily stick to local optimum so it can not find a global optimal solution.Simulated annealing algorithm also is a global optimization search method withstrong local search ability. Its disadvantage is the contradiction between quality ofsolution and the time that be spending. In this dissertation, a new hybrid geneticalgorithm is proposed based on these two algorithms. Fist of all, in the algorithm,integral sequence encoding method based on the preparative paths set is adoptedand a heuristic crossover and mutation strategy is applied. Secondly, the offspringof genetic operation is optimized by using simulated annealing algorithm, andconvergence speed is mended. Finally, we design three special operators includinghamming operator, invasion operator and re-warming operator to maintain robustof populations and improve the global search ability. This dissertation designs a kind of effective network simulation enviromentthat is referred to the Salama model by adding K-means operator, which is used toconfirm performance of the algorithms. Simulations has demonstrated that thealgorithm has characteristics of feasibility, stability and rapid convergence, and itcan effectively construct multicast tree with lower cost according to QoS request,in addition , it has better real-time property.