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

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

分析了时延受限的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.