An efficient multicast routing algorithm based on simulated annealing for multimedia communications

To support various quality-of-service performance requirements of multimedia communications, more real-time applications need to transmit information in manner of multicasting. In this paper, an efficient multicast routing algorithm based on simulated annealing named SAMRA is proposed to solve delay- and delay variation-bounded Steiner tree problem. This problem is known to be NP-complete. To avoid enlargement of search area and increase of computing time, the proposed heuristic algorithm uses ´paths-switching´ strategy to construct neighbors in the range of feasible solutions according to the relationship between delay and delay variation. Simulations demonstrates that the algorithm has characteristics of feasibility, stability and rapid convergence, and it can effectively construct multicast tree with lower cost according to QoS request, and has better real-time property.