共享路径优先组播路由算法  

Research on Shared Path First Heuristic Algorithm

作　　者：杨帆[1] 邱智亮[1] 李志冰[1] 刘增基[1] 常月娥 

机构地区：[1]西安电子科技大学综合业务网国家重点实验室,西安710071 [2]陕西华经微电子有限公司,西安710065

出　　处：《电子与信息学报》2007年第3期716-718,共3页Journal of Electronics & Information Technology

基　　金：国家"863"计划项目(2002AA103062)资助课题

摘　　要：求解开销最小组播树在数学上归结为Steiner树问题,但由于寻找最优的Steiner树问题是NP-Complete问题,因此在组播应用中,采用启发式算法获得次优的组播树是常见的方法。该文提出了一种新的的启发式组播路由算法(Shared Path First Heuristic,SPFH)该算法在选择目的节点加入组播树时,既考虑到目的节点到树上的距离,又考虑到先加入的节点对后续加入节点的影响。算法从距离当前组播树近的目的节点中挑选节点加入组播树,选择的规则是,把能够减小其它目的节点加入组播树开销的节点先加入树。仿真结果表明,SPFH算法能找到开销接近于最优解的组播树。The minimum cost multicast tree may boil down to Steiner tree problem which is NP-Complete. In multicast applications, heuristic algorithms are commonly used to calculate the suboptimal tree. In this paper, a new heuristic algorithm named Shared Path First Heuristic （SPFH） is proposed. In this algorithm, when destination nodes are joined into the multicast tree, two factors are considered. One is the distance between the destination nodes and the multicast tree, the other is the influence of earlier joined nodes to the later joined nodes. Among the nearest nodes to the constructing multicast tree, the node which can reduce the joining cost of other nodes are first chosen to join the tree. The simulation result shows that SPFH achieves the preferable performance.

关 键 词：组播 组播路由算法 STEINER树 路由器内部交换网络 

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