基于最小生成树的动态贪婪多播路由算法研究.doc

基于最小生成树的动态贪婪多播路由算法研究[摘要]提出了基于最小生成树的动态贪婪算法,由于在所有节点都是多播节点时,最小生成树是最佳的,因此通过该算法产生的多播树的性能在合理的范围之内。仿真结果表明DPG算法在多播节点密度较大时显示了优越性,同时它还具有复杂度低的特点。本文来源于网络,本站发布的论文均是优质论文,供学习和研究使用,文中立场与本网站无关,版权和著作权归原作者所有,如有不愿意被转载的情况,请通知我们删除已转载的信息,如果需要分享,请保留本段说明。[关键词]计算机网络多播路由动态多播路由算法多播路由协议中图分类号:TP3文献标识码:A文章编号:1671-7597(2009)0420055-01 许多多播应用都要求支持动态多播,即多播组中的成员经常性变化,参与的组成员可以随时加入或离开,使得通信成员具有动态性。支持这样的应用需要网络能够随着多播成员的加入或离开而改变现有的多播树,这时的多播路由问题就是动态多播路由问题。在极端情况下,可以在每次组成员变化后用静态启发式算法来重新运算多播树,但是这样做的代价是运行时间太长、多播树的变化太大,多播树的重构会造成正在传送的分组的丢失。因此一个理想的算法应该是能够使得每次加入或离开事件后多播树的变化最小、多播树的费用最小、而且每次更新事件的时间复杂度较低。动态性使得动态多播路由算法问题比静态路由优化问题要难解决,这是因为动态路由优化是在通信过程中进行的,无法预知哪些成员将会加入或离开通信组。另外,动态路由优化是在通信过程中进行的,要求路由调整对其它成员不造成影响或影响的程度最小。因此往往只能在路由性能与组或网络的动态性之间取折中。一、算法描述对动态steiner多播路由问题的主要要求是节点的加入或离开过程中不需要重组多播路由树、树的网络费用低、复杂度低。贪婪算法或加权贪婪算法是较符合这些要求的算法。因此我们的仿真模型中将对这两种算法进行仿真比较。贪婪算法和加权贪婪算法虽然是复杂度较低的不重组算法,但树的网络费用却随着节点更新时间的递增而可能变得很坏,其主要原因是当节点离开时,若它不是树上的叶节点,则不会被剪除,而是仍然保留在多播树上,若这样的节点增多时,则树的网络费用可能会高于最佳树的网络费用值许多,因此贪婪算法和加权贪婪算法的无效度会较大。ARIES算法、EBA算法、vTDM算法和GsDM算法的无效度都低于贪婪算法的无效度,遗憾的是除了VTDM算法以外,都需要多播树在节点更新过程中重组,而且复杂度都太高。根据不重组、降低无效度、复杂度低的要求,我们提出了一种基于最小生成树和贪婪算法基本思想的一种动态多播路由算法,它是解决动态Steiner问题的算法,称之为DPG(DynamiePrim-basedGreedymulticastroutingalgorithm)算法。该算法的基本思想是每次源节点发起一次多播通信时,首先利用Prim算法对网络计算一棵最小生成树,并保留这些路径,每次新的多播节点要加入时,就按最小生成树的路径连到已有的多播树。该算法在最坏情况下加入一个节点时需要重新计算路径,算法的复杂度为。若路由表没有改变,则该算法中也不需重新计算路径,其时间复杂度仅与添加的路径上的节点数有关,最差情况下为O(n)。当删除一个节点时,其时间复杂度即贪婪算法的时间复杂度,最差情况下也是O(n)。二、动态多播路由