时延受限组播路由的最短路径加速算法求解  

Delay-constrained multicast routing algorithm based on optimized Floyd shortest path algorithm

作　　者：李元臣[1] 刘维群[1] 

机构地区：[1]洛阳师范学院信息技术学院,河南洛阳471022

出　　处：《计算机应用》2010年第5期1176-1178,1182,共4页journal of Computer Applications

基　　金：河南省自然科学基金资助项目(2008B520027);河南省高等学校青年骨干教师资助计划项目(2006104)

摘　　要：分析了时延受限的Steiner树问题,总结了在构建组播树过程中的代价和计算复杂度变化规律,并根据实际网络环境,从优化最短路径出发,提出了一种基于优化最短路径的时延受限组播路由算法AOSPMPH。该算法以MPH算法为基础,利用Floyd最短路径优化算法求出节点对之间的最短路径,选择满足时延要求的最小代价路径加入组播树,进而产生一棵满足时延约束的最小代价组播树。仿真结果表明,AOSPMPH不但能正确地构造时延约束组播树,而且其代价和计算复杂度与其他同类算法相比得到了优化。An important issue in multicast communication is how to create an efficient and robust Steiner tree through using multicast routing algorithm.Based on the analysis of delay-constrained Steiner tree,the cost and computational complexity when constructing a multicast tree,starting from the practical requirements and optimizing shortest paths,a new algorithm named Algorithm of Optimizing Shortest Path based on MPH （AOSPMPH） was proposed.On the basis of Minimum cost Paths Heuristic （MPH）,the proposed algorithm found the shortest path between nodes using optimized Floyd shortest path algorithm and selected the minimum cost path to meet the requirements of delay constraint to add into the multicast tree.By this way,a low cost multicast tree could be constructed.The simulation results show that AOSPMPH not only can construct delay-constrained multicast tree correctly,but also is of less cost and lower computational complexity than those of many other multicast algorithms.

关 键 词：STEINER树 MPH算法 Floyd最短路径优化 启发式算法 组播通信 

分 类 号：TP393.02[自动化与计算机技术—计算机应用技术]