A tree-growth based ant colony algorithm for QpS multicast routing problem

摘要

QoS multicast routing is a non-linear combinatorial optimization problem. It tries to find a multicast routing tree with minimal cost that can satisfy constraints such as bandwidth, delay, and delay jitter. This problem is NP-complete. The solution to such problems is often to search first for paths from the source node to each destination node and then integrate these paths into a multicast tree. Such a method, however, is slow and complex. To overcome these shortcomings, we propose a new method for tree-based optimization. Our algorithm optimizes the multicast tree directly, unlike the conventional solutions to rinding paths and integrating them to generate a multicast tree. It applies ant colony optimization to control the tree growth in order to generate a multicast tree. Via orthogonal experiments, the most efficient combination of various parameters is selected so that the quality of optimization is improved. We then evaluate the performance and efficiency of the proposed algorithm in comparison with other existing algorithms. Simulation results show that our algorithm performs well in searching, converging speed and adaptability scale.