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

Abstract: 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.

Key words: Steiner tree, Minimum cost Paths Heuristic (MPH) algorithm, optimum of shortest path algorithm devised by Floyd, heuristic algorithm, multicast communication