Ant Colony Optimization And Its Research On QoS Multicast Routing Problem

With the development of Internet and related technologies, a lot of real-time network business services are appearing continually, it calls new requirement for quality of service (QoS). As the integration of QoS and multicast routing, which are important research topics, QoS multicast routing problem is an urgent problem to be solved of current and next-generation Internet.QoS multicast routing problem generally comes down to the Steiner Tree problem in mathematics, that is, to find a multicast tree which covers all the source and destination nodes, meets certain QoS constraints and has the minimum total cost in network topology, and it's has been proved a NP-Complete problem. Ant Colony Optimization (ACO) is a new intelligent optimization algorithm, it's applied to solve QoS multicast routing problem in this article. Firstly, this article describes the relevant knowledge of QoS and multicast routing from many aspects and introduces a variety of QoS multicast routing algorithms.Secondly, this article commences with researching the Traveling Salesman Problem (TSP), and describes the theory of ACO detailedly. Aim at overcoming the shortcomings of ACO that it has a long searching time and easily gets in local optimum, this article puts forward a new improved ACO called MACA, it combine with the model of MAX-MIN Ant System (MMAS) and Ant Colony System (ACS), and a dynamic parameter adjustment strategy of r and Q is introduced in it. Meanwhile, oliver30 is used as the applied example to test the performance of MACA and it's compared with MMAS and ACS.Finally, with the inspiration from solving TSP, this article put forward another improved ACO called BEMACA, this algorithm bases on MACA and a Branch-Exchange Strategy is introduced in it. Network topologies generated by Salama random model are used as the research objects, and an adaptive function is used to evaluate the fitness of multicast tree. The performance testing on the algorithm shows that BEMACA, with the introduction of Branch-Exchange Strategy, improves the performance on quality of the optimal solution and convergence speed, it's an available algorithm to solve QoS multicast routing problem.