改进的时延约束Steiner树算法

An Advanced Algorithm for Delay-Constrained Steiner Tree

针对现有时延约束Steiner树算法时间复杂度较高以及生成的组播树代价较高的问题,提出了一种改进的时延约束Steiner树算法。该算法采用Dijkstra算法路径递增的基本思想和链路共享的方法,在快速搜索阶段,依次搜索到当前树有最小可行代价的节点,将目的节点通过最小可行代价路径加入组播树;在异常处理阶段,将遗漏的目的节点通过最小时延路径加入组播树,进而生成满足时延约束的Steiner树。理论分析和实验结果表明,与同类算法相比,该算法能够以较低的时间复杂度,取得较好的组播树代价。

An advanced algorithm for delayconstrained Steiner tree is proposed to focus on the problem that the existing delayconstrained Steiner tree algorithms usually lead to high multicast cost and high time complexity. The proposed algorithm adopts the idea of path increasing in Dijkstra algorithm and the method of link sharing. It iteratively searches the node with the least feasible cost to the current tree and adds the destination node to the current tree through its feasible least cost path in the fast search stage. The missing destination nodes are added to the current tree through its least delay path in the exception handling stage of the algorithm. The delayconstrained Steiner tree is constructed through these two stages of the algorithm. Theoretical analysis, experimental results and comparisons with similar algorithms show that the proposed algorithm can construct multicast tree in lower cost and time complexity.