改进的时延约束Steiner树算法

徐剑　倪宏　邓浩江　刘磊

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

关键词：Steiner树；代价；时延约束；路径递增；链路共享