基于最小生成树的动态多播路由算法 |
| |
引用本文: | 余燕平,仇佩亮. 基于最小生成树的动态多播路由算法[J]. 浙江大学学报(工学版), 2003, 37(2): 162-166 |
| |
作者姓名: | 余燕平 仇佩亮 |
| |
作者单位: | 浙江大学信息与电子工程学系,浙江大学信息与电子工程学系 浙江杭州310027,浙江杭州310027 |
| |
摘 要: | 提出了基于最小生成树的动态多播路由算法,称之为DPG(dynamic prim-based greedy multicast algorithm)算法,该算法属于不重组的动态多播路由算法。由于在所有节点都是多播节点时,最小生成树是最佳的,因此期望通过该算法产生的多播树的性能在合理的范围之内。结果表明DPG算法是一种平均无效率和最大无效度都在可接受的范围内的一种动态路由算法,尤其在多播节点密度较高时,它的平均无效率和最大无效度都较低。同时DPG算法的平均无效度对网络大小和网络平均节点度数不敏感,DPG算法的另一优点是时间复杂度低,它比贪婪算法和加权贪婪算法都快速。
|
关 键 词: | 动态多播路由算法 Steiner树 最小生成树 |
文章编号: | 1008-973X(2003)02-0162-05 |
修稿时间: | 2002-06-11 |
Minimum span tree based dynamic multicast routing algorithm |
| |
Abstract: | |
| |
Keywords: | dynamic multicast routing Steiner tree minimum spannin g tree |
本文献已被 CNKI 维普 等数据库收录! |