一种基于蚁群算法的分布式多播路由算法  

A novel distributed multicast routing algorithm based on ant colony algorithm

作　　者：刘彦鹏[1,2] 吴明光[1] 钱积新[1] 

机构地区：[1]浙江大学信息科学与工程学院系统工程研究所,浙江杭州310027 [2]安徽省电力科学研究院,安徽合肥230022

出　　处：《电路与系统学报》2008年第5期112-116,144,共6页Journal of Circuits and Systems

摘　　要：随着计算机网络的不断发展,大量多媒体应用要求网络具有满足QoS约束的多播功能。应用多播的关键是确定有效的多播路由,即求解最优Steiner树。目前提出的大部分都是集中式的或本质上是集中式的启发式算法,关于分布式算法的研究还比较少。本文提出了一种基于蚁群算法的分布式多播路由算法。该算法在源节点不掌握整个网络信息的情况下,利用网络的局部启发式信息和蚂蚁留下的信息素建立最优的多播路由。结合多播路由问题的特点,对算法进行了改进,使算法的收敛速度和解的质量都得到了较大的提高。仿真实验结果验证了该算法的有效性。With the rapid development of the commercial application in Internet, multimedia multicast application that satisfies the QoS constraints attracts more and more research attention, In order to support multicast, efficient multicast routing is crucial, which is a process of establishing a tree rooted from the source node and containing all multicast destinations. In nature, it is to construct a minimum-cost tree, namely Steiner tree. Delay-constrained multicast routing has been proven to be an NP-Complete problem. Currently many heuristic algorithms have been proposed, which are centralize, or centralized in nature. The research on distributed algorithm is relatively less. A novel distributed multicast routing algorithm based on ant colony algorithm is proposed. The algorithm tries to construct the minimum-cost tree by taking advantage of the local information and the pheromone left by previous ants in the case that the source node does not possess the whole network information. Combined the characteristic of multicast routing, the algorithm is improved, which accelerate the convergence speed and obtained better results. Simulation results show its effectiveness.

关 键 词：多播路由 蚁群算法 STEINER树 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]