求解度约束组播路由的新型蚁群算法  

New Ant Heuristic Algorithm for Degree-Constrained Multicast Routing

作　　者：葛连升[1,2] 王华[1] 王海洋[1] 

机构地区：[1]山东大学计算机科学与技术学院,山东济南250061 [2]山东大学网络与信息中心,山东济南250100

出　　处：《电子学报》2009年第7期1447-1451,共5页Acta Electronica Sinica

基　　金：国家自然科学基金(No.60773101);山东省自然基金(No.Y2007G42)

摘　　要：基于蚁群算法的正反馈机制提出了一种基于树的蚁群算法,并用它来求解度约束组播路由问题.在该算法中,蚂蚁按照一定的概率选择一条链路加入组播子树,然后检查加入点的度约束情况,如果该点的度约束情况达到饱和,则蚂蚁以后不再选取与该点连接的链路.通过计算模拟分析方法证明了该算法的有效性,计算机仿真结果显示,在解决度约束组播路由问题时,该新型蚁群算法的收敛速度大大快于已有的蚁群算法,找到的最优解性能稍好于已有的算法,算法的空间复杂度也得到降低.This paper proposes a Tree-Based Ant Colony Optimization based on the positive feedback mechanism and uses it to resolve the Degree-Constrained Multicast Routing. The ant in the new algorithm chooses some link according to the possibility distribution and adds it into the multieast sub-tree,while it checks the node where the new link is added.If the node has reached its degree constraint, the ant will never choose the adjacent links of the node. Computational simulation and analysis show validity of the new algorithm.The simulation result shows that the convergence of the new algorithm is much faster than the old one,the performance of the resolution is better, and it also has a lower space complexity when used m resolve the degree-constrained multicast routing.

关 键 词：度约束 组播路由 蚁群启发式算法 

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