作　　者： ; ; ;

机构地区： 深圳大学信息工程学院

出　　处： 《深圳大学学报（理工版）》 2001年第2期10-18,共9页

摘　　要： 提出了一种性能可以调节的组播树生成算法 .这种算法提供了一个调节参数κ ,即每次随机选择的端节点的个数 .通过改变参数κ ,可在组播树的费用和运行时间之间进行权衡选择 ,以适应不同应用场合的需要 .为了仿真 ,还提出了一种使节点平均点度非常精确的随机网络产生方法 .分析和仿真结果表明 ,只用较小的κ值就可得到较为理想的组播树费用 ,同时算法能保持较高的计算效率 .与算法SCTF (SelectiveClosestTerminalFirst)相比 ,在计算效率相同时 ,本算法费用值更低 . A fast algorithm for multicast tree is presented and a generating method for random networks is given. In our algorithm, a parameter κ, the random selective terminal number is provided. Using parameter κ, trade off selection between the cost of multicast tree and the running time of the algorithm can be made for different situations. The analysis and simulating results show that using a lowκ gives nearly best possible expected tree cost while maintaining acceptable run time efficiency. Comparing with SCTF(Selective Closest Terminal First), our heuristic algorithm gains more run time efficiency with the same tree cost. Our algorithm can compute faster with relatively smaller cost compared with SCTF.

关 键 词： 组播路由 近似算法 计算机网络 树 广域网

领　　域： [自动化与计算机技术] [自动化与计算机技术] [电子电信] [电子电信]