ISSN 1000-1239 CN 11-1777/TP

• 论文 •

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

1. 1(南京理工大学计算机科学与技术学院 南京 210094) 2(佛山科学技术学院计算机系 佛山 528000) (cszhouling@sohu.com)
• 出版日期: 2008-05-15

### A DelayConstrained Steiner Tree Algorithm Using MPH

Zhou Ling1, 2 and Sun Yamin1

1. 1(School of Computer Science and Technology, Nanjing University of Science and Technology, Nanjing 210094) 2(Department of Computer Science, Foshan University, Foshan 528000)
• Online: 2008-05-15

Abstract: 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 delayconstrained 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 path’s 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.