《多播路由算法的理论分析和证明方法论述》——MPH论文资料库.doc
《《多播路由算法的理论分析和证明方法论述》——MPH论文资料库.doc》由会员分享,可在线阅读,更多相关《《多播路由算法的理论分析和证明方法论述》——MPH论文资料库.doc(5页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、【精品文档】如有侵权,请联系网站删除,仅供学习与交流多播路由算法的理论分析和证明方法论述MPH论文资料库.精品文档.多播路由算法的理论分析和证明方法论述MPH论文资料库摘要:多播通信是从一个源点同时向网络中的多个成员发送分组的通信服务,一个最小代价的多播路由算法是NP完全的,在时间敏感的应用中其运行时间是一个关键问题.MPH(Minimum Path Cost Heuristic)算法是一个著名的启发式最小代价多播路由算法,本文对该算法进行了理论分析和证明,并做了广泛的仿真实验,结果表明其时间复杂度是O(m2n)而不是过去文献中所给出的O(m2n+e).关键词:多播路由 最小成本 时间复杂度A
2、bstract: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(Min
3、imum 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 an
4、d 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提出
5、了改进的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),
6、边标记为vi,vj,(1i 定义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是最小成本多
7、播树.MPH算法是一个启发式最小成本多播树算法,其基本思想如下:(1)部分多播树T开始只包括源节点s.(2)从余下的端节点中选取到树T的最短路径(如有多个则随机选择一个),端节点及路径上的所有节点并入Vt,路径上的边并入Et. (3)重复步骤(2),(3)直到Z中所有的节点包含到Vt中,此时的T即为近似最小成本多播树.3算法时间复杂度分析文13认为MPH算法中,对每一个即将加入到部分多播生成树的端节点的选择,最多需进行mn次最短路径的比较,m个端节点一个一个地加入,共需进行m2n次比较.另外,将选定的端节点到树T的最短路径上的节点和边加入到多播生成树的次数最多是e.因而,MPH算法的时间复杂度
8、为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).作为对算法复杂性
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 多播路由算法的理论分析和证明方法论述 路由 算法 理论 分析 证明 方法 论述 MPH 论文 资料库
限制150内