关键词: 多播树, 时延约束, Steiner树

Abstract: In order to optimize cost and decrease complexity with a delay upper bound, the delay-constrained Steiner tree problem was studied. Based on the Delay-Constrained Minimum Path Heuristic (DCMPH) algorithm and through improvement on the search path, a new MPH-based delay-constrained Steiner tree algorithm was presented in this paper. With the new algorithm, a destination node could join the existing multicast tree by selecting the path whose cost was the least; if the path's delay destroyed the delay upper bound, the least-delay path computed by shortest path tree algorithm was used to take the place of the least-cost path to join the current multicast tree. By the way, a low-cost multicast spanning tree could be constructed and the delay upper bound would not be destroyed. The simulation results show that the new algorithm is superior to DCMPH algorithm in the performance of spanning tree and space complexity.

Key words: multicast tree, delay-constrained, Steiner tree