Multicast routing for delay variation bound using a modified ant colony algorithm

The delay and delay variation-bounded Steiner tree problem is an important multicast routing problem in real-time multimedia networks. Such a constrained Steiner tree problem is known to be NP-complete. This paper proposes an ant colony algorithm with orientation factor and applies it to multicast routing problem with the constraints of delay variation bound. The orientation factor enables the ant to get rid of the initial blindness when searching paths, makes use of the search results and reduces the misguiding effect of pheromone on irrelevant paths, thus overcoming the drawbacks of slow convergence existing in the basic ant colony algorithm, increasing the speed of convergence and speeding up the finding of feasible solution to the problem. The simulation results show that the modified algorithm makes it possible to find a feasible solution to the multicast routing problem with delay variation bound. Compared with the conventional ant colony algorithm, the convergence speed of the modified algorithm is improved.