加权的基于多播节点的多播路由算法  

A weighted destination-driven multicast routing algorithm

作　　者：余燕平[1] 仇佩亮[1] 

机构地区：[1]浙江大学信息与电子工程学系,浙江杭州310027

出　　处：《电路与系统学报》2006年第3期110-114,共5页Journal of Circuits and Systems

摘　　要：在许多多播应用中,降低多播树网络费用非常重要。本文提出了加权的基于多播节点的多播路由算法(WDDMC算法)。由于改变了DDMC(Destination-Drivenrouting for low-cost Multicast)算法中的指示函数,适当降低了多播节点作为中间节点的优先级,提高非多播节点作为中间节点的优先级,从而使得多播树更接近最小Steiner树。在随机网络上的仿真结果表明,WDDMC算法的多播树网络费用优于DDMC算法。该算法的复杂度与DDMC算法完全相同。It is very important to reduce the cost of multicast trees in a lot of multicast applications. Minimum Steiner Tree Problem is NP complete problem. There are theoretic and realistic significance to research heuristic for Steiner problem. In this paper, a new algorithm WDDMC, in which the cost of the multicast trees is reduced by changing the indication function in which the priority of Steiner nodes is increased while that of intermediate nodes is reduced, is presented. The simulation results on random networks show that in almost all cases the cost of DDMC trees is lower than that of DDMC algorithm without any increase in time complexity. The complexity of WDDMC is O（elog n）. e is the number of edge, n is the number of vertex in network.

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

分 类 号：TN915[电子电信—通信与信息系统]