| 一个改进的多播路由算法 |
| |
| 引用本文： | 蒋廷耀,李庆华.一个改进的多播路由算法[J].上海大学学报(英文版),2004,8(3):317-321. |
| |
| 作者姓名： | 蒋廷耀 李庆华 |
| |
| 作者单位： | [1]ColleeofElectricalEngineeringandInformationTechnology,ChinaThreeGorgesUniversity,Yichang443002,P.R.China [2]CollegeofComputerScienceandTechnology,HuazhongUniversityofScienceandTechnology,Wuhan430074,P.R.China |
| |
| 基金项目： | ProjectsupportedbytheNationalNaturalScienceFoundationofChina (GrantNo .60 2 73 0 75 ) |
| |
| 摘 要： | Multicasting is a communication service that allows an application to efficiently transmit copies of data packets to a set of destination nodes. The problem of finding a minimum cost multicast tree can be formulated as a minimum Steiner tree problem in networks, which is NP-completeness. MPH (minimum path cost heuristic) algorithm is a famous solution to this problem. In this paper,we present a novel solution TPMPH (two phase minimum path cost heuristic) to improve the MPH by generating the nodes and the edges of multicast tree separately. The cost of multicast tree generated by the proposed algorithm with the same time as MPH is no more than that of MPH in the worst case. Extensive simulation results show that TPMPH can effectively improve the performance on MPH, and performs better in large-scale networks and wireless networks.
|
| 关 键 词： | 多址通信路径 斯泰纳树问题 最小路径成本 数据包 NP完全 |
| 收稿时间： | 24 January 2003 |
An improved multicast routing algorithm |
| |
| Jiang?Ting-yao,Li?Qing-hua.An improved multicast routing algorithm[J].Journal of Shanghai University(English Edition),2004,8(3):317-321. |
| |
| Authors: | Jiang Ting-yao Li Qing-hua |
| |
| Institution: | 1. Collee of Electrical Engineering and Information Technology, China Three Gorges University, Yichang 443002, P. R. China;College of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074, P.R. China
2. College of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074, P.R. China |
| |
| Abstract: | Multicasting is a communication service that allows an application to efficiently transmit copies of data packets to a set of destination nodes. The problem of finding a minimum cost multicast tree can be formulated as a minimum Steiner tree problem in networks, which is NP-completeness. MPH (minimum path cost heuristic) algorithm is a famous solution to this problem. In this paper, we present a novel solution TPMPH (two phase minimum path cost heuristic) to improve the MPH by generating the nodes and the edges of multicast tree separately. The cost of multicast tree generated by the proposed algorithm with the same time as MPH is no more than that of MPH in the worst case. Extensive simulation results show that TPMPH can effectively improve the performance on MPH, and performs better in large-scale networks and wireless networks. |
| |
| Keywords: | multicast routing Steiner tree problem minimum cost |
| 本文献已被 CNKI 维普 万方数据 SpringerLink 等数据库收录！ |
