[1]杨明,谢希仁.一种快速的近似最小代价多播路由算法MCTH[J].东南大学学报(自然科学版),1999,29(3):95-100.[doi:10.3969/j.issn.1001-0505.1999.03.018]
 Yang Ming,Xie Xiren.A Fast Algorithm for Near-Minimum Cost Multicast Routing MCTH[J].Journal of Southeast University (Natural Science Edition),1999,29(3):95-100.[doi:10.3969/j.issn.1001-0505.1999.03.018]
点击复制

一种快速的近似最小代价多播路由算法MCTH()
分享到:

《东南大学学报(自然科学版)》[ISSN:1001-0505/CN:32-1178/N]

卷:
29
期数:
1999年第3期
页码:
95-100
栏目:
计算机科学与工程
出版日期:
1999-05-20

文章信息/Info

Title:
A Fast Algorithm for Near-Minimum Cost Multicast Routing MCTH
作者:
杨明 谢希仁
通信工程学院, 南京 210016
Author(s):
Yang Ming Xie Xiren
Institute of Communications Engineering,Nanjing 210016
关键词:
多播通信 路由算法 Steiner树
Keywords:
multicast communication routing algorithm Steiner tree
分类号:
TP393
DOI:
10.3969/j.issn.1001-0505.1999.03.018
摘要:
提出一种快速近似最小代价多播路由算法. 算法通过动态调整结点与当前路由树的代价值,依次选择和当前路由树有最小代价的结点来逐步生成总体代价小的多播路由树. Minimum Cost Path Heuristic (MPH)是一个性能很好的Steiner树近似算法,通过算法分析和实验比较得出,本文的算法与MPH有相同的性能,但复杂性更低,并且建立路由时仅需了解相邻结点间链路的代价信息.
Abstract:
The article presents a fast algorithm for near-minimum cost multicast routing. The algorithm adjusts the nodes’ minimum cost to the current multicast tree dynamically, and gradually gets multicast tree with low total cost by selecting the node with minimum cost to current multicast tree in turn. The algorithm has as the same performance as Minimum Cost Path Heuristic (MPH) algorithm, which is a very fine Steiner tree heuristic algorithm, but lower complexity than MPH by algorithm analyses and simulation. Moreover, the algorithm builds multicast tree by querying only incident links for cost information.

参考文献/References:

[1] Takahashi H,Matsuyama A.An approximate solution for the Steiner tree problem in graphs.Mathematica Japonica,1980,24(6):573~577
[2] Winter P.Steiner problem in networks:a survey.Networks,1987,17:129~167
[3] Kou L,Markowsky G,Berman L.A fast algorithm for Steiner trees in graphs.Acta Informatica,1981,15:141~145
[4] Shaikh A,Shin K.Destination-driven routing for low-cost multicast.IEEE J S A C,1997,15(3):373~381
[5] Bauer F,Varma A.Distributed algorithms for multicast path setup in data networks.IEEE/ACM Trans Networking,1996,4(2):181~191
[6] Waxman B M.Routing of multipoint connections.IEEE J Selected Area Comm,1988,6(9):1617~1622

相似文献/References:

[1]陶军,肖鹏,刘莹,等.基于拓扑连通概率的车载自组织网络路由算法[J].东南大学学报(自然科学版),2013,43(2):286.[doi:10.3969/j.issn.1001-0505.2013.02.011]
 Tao Jun,Xiao Peng,Liu Ying,et al.Routing algorithm based on probability of topology connectivity in vehicular ad hoc networks[J].Journal of Southeast University (Natural Science Edition),2013,43(3):286.[doi:10.3969/j.issn.1001-0505.2013.02.011]

备注/Memo

备注/Memo:
第一作者:男,1968年生,博士研究生,讲师.
更新日期/Last Update: 1999-05-20