基于MPH的时延约束Steiner树算法

A Delay-Constrained Steiner Tree Algorithm Using MPH

为了在时延约束条件下进一步优化组播树代价,并降低算法计算复杂度,研究了时延受限的Steiner树问题.分析了MPH(minimum path heuristic)算法的计算复杂度;在此基础上设计了一个时延约束Steiner树算法DCMPH(delay-constrained MPH)用于构造时延约束最小代价组播树.该算法中每个目的结点通过与当前组播树有最小代价的路径加入组播树;若时延不满足要求,则通过合并最小时延SPT(shortest path tree)树进而产生一个满足时延约束的最小代价组播树.仿真实验表明,DCMPH算法生成的组播树在保证时延要求的情况下,与同类算法相比取得了很好的代价性能和较低的计算复杂度.

Multicast routing algorithm has received considerable attention from researchers in computer communication. In most conditions, it is NP-complete and defined as a Steiner tree problem. In order to optimize cost and decrease time complexity with a delay upper bound, the delayconstrained Steiner tree problem is addressed. Time complexity of minimum path heuristic （MPH） algorithm is analyzed firstly, and then a delay-constrained least-cost （DCLC） multicast routing algorithm called DCMPH is presented to construct DCLC multicast tree. With DCMPH a computing member node can join the multicast tree by selecting the path whose cost is the least to the existing multicast tree; if the pathos delay destroys the delay upper bound, the least-delay path computed by shortest path tree （SPT） algorithm is used to take the place of the least-cost path to join the current multicast tree. By this way, a low-cost multicast routing tree can be constructed and the delay upper bound isn＇t destroyed. The correctness of DCMPH is proved by mathematical induction and the time complexity is analyzed in theory. Simulation results show that DCMPH is high-performance in constructing DCLC multicast routing tree and has a lower time complexity than many other DCLC multicast routing algorithms.