《多播路由算法的理论分析和证明方法论述》——MPH论文资料库.doc

【精品文档】如有侵权，请联系网站删除，仅供学习与交流多播路由算法的理论分析和证明方法论述MPH论文资料库.精品文档.多播路由算法的理论分析和证明方法论述MPH论文资料库摘要:多播通信是从一个源点同时向网络中的多个成员发送分组的通信服务,一个最小代价的多播路由算法是NP完全的,在时间敏感的应用中其运行时间是一个关键问题.MPH(Minimum Path Cost Heuristic)算法是一个著名的启发式最小代价多播路由算法,本文对该算法进行了理论分析和证明,并做了广泛的仿真实验,结果表明其时间复杂度是O(m2n)而不是过去文献中所给出的O(m2n+e).关键词:多播路由 最小成本 时间复杂度Abstract:Multicasting is a communication service that allows a source to efficiently transmit copies of data packet to a set ofdestination nodes.The run time of multicast routing algorithm is a key problem in real time applications since finding a minimum costmulticast tree is NP-completeness.MPH(Minimum Path CostHeuristic)algorithm is a famous heuristic solution to multicast routing.Inthis paper,we show that theO(nm2+e)time complexity of MPH in previous literatures is not correct by theory analysis and exten-sive simulation,where n is number of network nodes,m is number of destination nodes and e is number of network edges.Furthermore,a precise time boundO(nm2)is proposed.Key words:multicast routing;minimum cost;time complexity1引言多播通信(multicast)技术是网络中的一个源点同时向网络中的多个成员节点(端节点)发送分组的通信服务.它有利于节省网络资源,在现代计算机通信中有着重大的应用价值.多播路由(又叫多播树)是从源点到各端节点的路径,最小成本的多播路由的确定是NP完全的.MPH是一个出色的启发式算法,在文献16中都有描述,文献2,3提出了改进的MPH算法以减少多播树的构造时间.文1在将MPH算法与其它算法进行性能比较时,认为MPH算法的时间复杂度在端节点到其它节点的最短路径已知的条件下(后文都是基于这个条件)是O(m2n+e),n是网络节点数,m是端节点数,e是网络中的边数.文2,3运用文1的分析方法和结论也进行了有关算法的性能分析和比较.本文认为文13对MPH算法和有关算法的时间复杂性度量是不正确的,理论分析和仿真结果表明MPH的时间复杂度应该是O(m2n).2MPH算法通信网络可模型为一个带权无向图G=(V,E,c),V是节点集合,E是边的集合,边代表节点间的通信链路.G中节点个数为n,节点标记为vi(i=1,2,n),边标记为vi,vj,(1i< P> 定义1节点vi,vj之间的最短路径是连通vi,vj的路径中各边成本之和最小的一条路径.节点到树的最短路径是指该节点到树中各节点的最短路径中成本最小的那一条路径.定义2最小成本多播树.给定一个无向图G=(V,E,c),源节点s,一个端节点集合Z V,寻找G的一个子图(树)T=(Vt,Et,ct),若满足源节点到其它任一端节点存在一条路径,Steiner节点(源节点和端节点以外的节点)的度大于或等于2,T G,Vt V,Et E,Z Vt,则T是关于s和Z的一棵多播树.若T的成本ct=vi,vjEtcost(vi,vj)是所有关于s和Z的多播树中最小的,则T是最小成本多播树.MPH算法是一个启发式最小成本多播树算法,其基本思想如下:(1)部分多播树T开始只包括源节点s.(2)从余下的端节点中选取到树T的最短路径(如有多个则随机选择一个),端节点及路径上的所有节点并入Vt,路径上的边并入Et. (3)重复步骤(2),(3)直到Z中所有的节点包含到Vt中,此时的T即为近似最小成本多播树.3算法时间复杂度分析文13认为MPH算法中,对每一个即将加入到部分多播生成树的端节点的选择,最多需进行mn次最短路径的比较,m个端节点一个一个地加入,共需进行m2n次比较.另外,将选定的端节点到树T的最短路径上的节点和边加入到多播生成树的次数最多是e.因而,MPH算法的时间复杂度为O(m2n+e).我们把MPH算法的操作分为三部分:端节点的加入所需的最短路径的比较次数;最短路径上的边的加入次数;最短路径上的节点的加入次数.(1)最短路径的比较次数MPH算法中,端节点到部分多播生成树的最短的最短路径的确定需进行的最大比较次数为:O(mi=0(n-m+i)(m-i)=O(3m2n+2m3-3m2+3mn-m6)=O(m2n)文3基于MPH算法介绍了一种改进的算法FMPH,有利于减少最短路径的比较次数.但文3关于比较次数为O(m2k),k为多播生成树中任意一个端节点的路径节点个数的结论是值得商榷的.因为根据原文定义2,k可能是0,最坏情况下也可能是O(n).作为对算法复杂性的度量,任意的k是不妥当的.(2)边的加入次数当从余下的端节点确定了到部分多播生成树的最短路径后,还需将该路径上的边并入部分多播生成树. 论文格式为了确立这部分操作所需考察的边的数目,我们先证明下面的定理.定理1设T=(V,E)是网络图G=(V,E)的一棵子树(可扩展为子图),节点vmV,vm V,vm到树T的最短路径path(vm,T)=(V,E),则EE=.证明用反证法.由定义1,设vm到树T的最短路径是vm、vt节点间的最短路径,vtV.如果EE,则至少有一条边vi,vjE,vi,vjE,即有viV,vjV,则vi,vj两个节点至少有一个节点不是vt,不妨设该节点是vj.由于vj是vm到vt的最短路径上的节点,则vm到vj的距离小于vm到vt的距离,这说明vm到树T的最短路径是vm、vj节点间的最短路径,这同vm到树T的最短路径是vm、vt节点间的最短路径的假设是矛盾的,所以定理1成立.由定理1,MPH算法中向部分多播生成树加入选定的最短路径上的边时所需处理的边的最大数目应是n-1.因为最终生成的多播树最大是包括n个节点的一棵生成树,且该树在构造时所处理的边是没有重复的.而文13认为处理的边的最大数目是O(e),对稀松图,这部分计算量对算法总的时间复杂性的影响不是太大,但是对稠密图却可能使对算法的性能分析得到错误的结论,因为边的总数e是O(n2)条.例如,稠密图中当m n时边的加入的计算量成为算法的主要部分,O(m2n+e)=O(e)=O(n2),是实际计算时间的O(n)倍.另外,文2在对LSMPH算法、文3在对FMPH算法的时间复杂度的分析上对边的度量存在同样的问题,这里不再赘述.(3)最短路径上的节点的加入次数多播生成树的节点数最多是n,故节点的加入所需的最大次数是O(n).综上所述,MPH算法的时间复杂度应是O(m2n+n+n)=O(m2n),而O(m2n+e)的结论是不正确的.4仿真实验为了更好的说明文13的结论O(m2n+e)中的e相对于n的偏差程度,我们进行了仿真实验.实验中采用Wax-man在文献7中介绍的方法生成随机网络图.n个节点中任意一对节点u,v之间是否存在一条边由连通概率p(u,v)确定,p(u,v)=e-d(u,v)/L,(0,1).边长即成本d(u,v)随机分布在(0,L)中,L表示边长的变动期间.,是调整网络特性的参数,增加,长边相对短边的比增加;增加,节点的度增加,即边越稠密.共进行了3组对照实验,n=300,L=100,=0·2,分别为0·9,0·6,0·3.每一组参数生成300个随机网络图.对每一个网络图,记录网络图的总边数, 图1(a).O(e)相对实际处理边数的偏差程度;(b).O(n)相对实际处理边数的偏差程度300次实验的平均值记为e;随机选择指定数目的端节点,记录MPH算法构造多播生成树时所实际处理的边数,平均值记为real.比值e/real、n/real分别示于图1.从图1(a)可以看出用e来作为MPH算法的边的处理次数是实际处理次数的102倍数,而且边越稠密,偏差越大;端节点数越少,偏差越大.而从图1( b)可以看出以n来作为MPH算法的边的处理次数是合理的,并且几乎不受边的稠密程度的影响. 5结论理论分析和仿真结果表明多播路由算法MPH的时间复杂度应该是O(m2n),而文13对MPH算法和有关算法的时间复杂性度量是不正确的.参考文献: 1 S Ramanathan.Multicast tree generation in networks with asymmetriclinksJ.IEEE ACMTrans.On Networking,1996,4(4):558-568. 2 李汉兵,喻建平,谢维信.局部搜索最小路径费用算法J.电子学报,2000,28(5):92-95. 3 胡光岷,李乐民,安红岩.最小代价多播生成树的快速算法J.电子学报,2002,30(6):880-882. 4 Pawel Winter.Steiner problem in networks:a surneyJ.Networks,1987,17(2):129-167. 5 F KHwang.Steiner tree problems J.Networks,1992,22(1):55-89. 6 HF Salama,D S Reeves.Evaluation of multicast routing algorithms forreal-time communication on high speed networksJ.IEEE Journal onselected areas in communication,1997,15(3):332-349. 7 Mwaxman.Routing of multipoint connectionsJ.IEEE Journal on Se-lected Areas in communication,1988,6(9):1617-1621.本文由无忧论文网硕士（博士、职称、毕业）论文下载与发表中心独家提供资源，如有雷同，纯属盗版。欢迎各位光临获取更多有用资料。硕士论文网：博士论文网：英语论文网：http:/www.51lunwen.org会计论文发表网：http:/www.ukessay.org教育论文发表网:医学论文发表网：第一论文发表网：英国论文网http:/www.ukthesis.org留学作业网http:/www.ukassignment.org留学论文网留学生论文网留学论文公司http:/www.ukessay.org毕业论文网英语毕业论文网：http:/www.51lunwen.org/englishpaper.html留学生论文网：http:/www.51lunwen.org核心论文发表网：http:/www.51fabiao.org古玩网http:/www.china-中国元素网http:/www.china-蜂朝网蜂朝商务网蜂朝百科蜂朝教育导航收集一些比较经典的论文发表网站供大家多多交流哦。英语论文网：139-1720-6902 QQ：949925041Email： yingyulunwen