资源描述：
《低代价最短路径树的快速算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、1000-9825/2004/15(05)0660©2004JournalofSoftware软件学报Vol.15,No.5∗低代价最短路径树的快速算法+王涛,李伟生(北京交通大学计算机与信息技术学院,北京100044)AFastLow-CostShortestPathTreeAlgorithm+WANGTao,LIWei-Sheng(SchoolofComputerandInformationTechnology,BeijingJiaotongUniversity,Beijing100044,China)+Correspondin
2、gauthor:E-mail:wtzyb4446@163.com,http://www.njtu.edu.cnReceived2003-06-09;Accepted2003-09-05WangT,LiWS.Afastlow-costshortestpathtreealgorithm.JournalofSoftware,2004,15(5):660~665.http://www.jos.org.cn/1000-9825/15/660.htmAbstract:Low-CostShortestPathTreeisacommonly-use
3、dmulticasttreetype,whichcanminimizetheend-to-enddelayandatthesametimereducethebandwidthrequirementifpossible.Basedonthelow-costshortestpathtreealgorithmDDSP(destination-drivenshortestpath)andthroughimprovingonthesearchprocedure,aFastLow-costShortestPathTree(FLSPT)algor
4、ithmispresentedinthispaper.TheShortestPathTreeconstructedbytheFLSPTalgorithmisthesameasthatconstructedbytheDDSPalgorithm,butitscomputationcomplexityislowerthanthatoftheDDSPalgorithm.ThesimulationresultswithrandomnetworkmodelsshowthatFLSPTalgorithmismoreeffective.Keywor
5、ds:multicast;SPT(shortestpathtree);steinertree;MST(minimumspanningtree)摘要:低代价最短路径树是一种广泛使用的多播树.它能够在保证传送时延最小的同时尽量降低带宽消耗.在DDSP(destination-drivenshortestpath)算法的基础上,通过改进节点的搜索过程,提出了快速低代价最短路径树算法FLSPT(fastlow-costshortestpathtree).该算法构造的最短路径树与DDSP算法构造的树具有相同的性能,但其时间复杂度低于DDSP算
6、法.随机网络模型的仿真结果表明,FLSPT算法效率更高.关键词:多播;最短路径树;Steiner树;最小生成树中图法分类号:TP301文献标识码:A多播是一种群组通信的手段,要求将信息从一个数据源同时传送到多个目的地.为了有效地支持实时的大数据量数据传送的应用,一个好的多播路由算法应该能够控制数据传送的延时和带宽消耗.构造多播树是解决[1]多播路由问题的常用方法.有3种不同类型的多播树:基于数据源的树、Steiner树和基于中心的树.这些不同类型的树中具有代表性的是基于源的最短路径树(shortestpathtree,简称SPT)和
7、Steiner树.SPT最主要的优点就是它使得源节点到每个目的节点的时延最小;而Steiner树则使得所有连接的消耗总和最小,最大限度地共享带宽,如果网络中除源节点外的每个节点都是目的节点,这棵树就是最小生成树(minimumspanningtree,简称∗作者简介:王涛(1980－),男,广西桂林人,硕士生,主要研究领域为计算机网络技术,图论算法设计于分析;李伟生(1945－),男,教授,主要研究领域为算法的设计与分析(并行算法、图论算法、最优化算法),网络数据库技术.王涛等:低代价最短路径树的快速算法661MST).在给定的网络
8、中,构造从源节点到其他目的节点的多播树,几乎不可能使它同时达到最小延时和最小总消[2~4]耗,因此,一些学者研究构造满足指定时延限制的Steiner树.当网络变得足够大时,从源节点到一些目的节点的最短路径常常不只一条,而由此构成的SP
