基于最小生成树的动态多播路由算法

摘要：

提出了基于最小生成树的动态多播路由算法,称之为DPG(dynamic prim-based greedy multicast algorithm)算法,该算法属于不重组的动态多播路由算法.由于在所有节点都是多播节点时,最小生成树是最佳的,因此期望通过该算法产生的多播树的性能在合理的范围之内.结果表明DPG算法是一种平均无效度和最大无效度都在可接受的范围内的一种动态路由算法,尤其在多播节点密度较高时,它的平均无效度和最大无效度都较低.同时DPG算法的平均无效度对网络大小和网络平均节点度数不敏感.DPG算法的另一优点是时间复杂度低,它比贪婪算法和加权贪婪算法都快速.

关键词：动态多播路由算法、Steiner树、最小生成树

所属期刊栏目：37

分类号：TP393.02(计算技术、计算机技术)

在线出版日期：2004-01-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：162-166