The Distributed Multicast Routing Scheme with Delay Constraint Using Ant Colony Optimization

摘要

The delay-constrained minimum-cost multicast routing problem is known to be NP-complete. Currently many heuristic algorithms have been proposed, most of which are centralized, or centralized in nature. A completely distributed scheme based on ant colony optimization is proposed. In this scheme, no core node with the whole network topology information exists and the ants only use the local information of their current nodes to find the destinations. Combined the characteristics of multicast routing, the algorithm was improved, which accelerated the convergence speed and enhanced the quality of solution. The proposed scheme is easy to realize by three types of ants with simple structures. The scheme is loop-free and has small overhead compared with the flooding method. Simulation results show that the scheme is an effective distributed approach to multicast routing decision with delay constraint.