资源描述：
《一种有效的时延约束组播路由算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、一种有效的时延约束组播路由算法黄勇(国防科大人文与管理学院，湖南长沙410073)摘要:在多媒休通信网络中，组播问题提出了新的要求，除了最小化组播通信的代价，同时要求保证每一个目的的节点在固定的延时之内接收信息。在这篇论文中，我们提出了一个链路选择函数用于解决时延约束组播问题。我们的实验结果揭示了该函数能提供满足时延约束且代价较小的组播路由问题近似解。关键词:组播路由;时延约束;链路选择函数Abstract:Inmultimediacommunicationnetworks，theproblemofmulticastingassumesanewdimension.Apartfrommin
2、imizingthecostofmulticastcommunication，itisalsonecessarytoensurethateachofthedestinationnodesreceivesthemessagewithinaboundeddelay.Inthispaper，wepresentanedgeselectionfunctionforsolvingthedelay一boundedmulticastproblem.Ourexperimentalresultsrevelalthatthealgorithmprovidesfastandsuperiorqualitysolu
3、tionstothedelay一boundedmulticastproblem.Keywords:MulticastRouting;Delay一bounded;edgeselectionfunctionQoS组播路由技术。0引言1网络模型及问题的描述随着视频会议/点播、多媒体播放以及远程教学等应用的兴起，对成员是的交互通信在多媒体实时业务的QoS传输中，基于提出了高的服务质量QoS的要求。在网络各时延约束的代价优化路由模型可表示为无向中继系统中实现对QoS需求的流进行带赋权图G=(V,E)，其中V是网络中所有交QoS需求约束的路由选择机制，被称为QoS换节点组成的集合，E是图G中任意两相
4、邻路由选择问题(QoSrouting)，所用算法的路节点i,j的边(i,j)的集合。对于G中的每一由计算约束条件包括各种QoS需求，如时条边(G,j)EE，均对应两个正实数加权值延、时延抖动、带宽等约束。QoS路由实现的cost(i,j).delay(i,j)ecost(i,j)定义了边(i,j)困难是路径计算的复杂性，选择有单一QoS的代价，其值与该边的资源使用情况有关。约束的可行路径可由任何最短路径算法实delay(i,j)定义了边(i,j)的信息传送延时，该现，但是许多服务类别需要多个QoS约束，延时包括排队延时、传输延时和交换延时等。这通常是一个NP完全问题[l]。组播路由问题可
5、描述为在图G中寻找一棵本文将通过对这一课题的研究，提出一包含发送源及所有接收节点的树T=(VT,种基于链路选择函数的性能较优的网络ET)，(TgG)，收稿日期:2002一03一27;修改B期:2002一11一26作者简介:黄勇(1975-)，男，湖南长沙人，硕士研究生，主要方向为计算机网络，智能计算。·16。《电脑与信息技术》2002年第6期并满足:min艺cost(i,j))(1)行其他的选择，这大大丰富了f的行为，具体U.j)EE,的规律如下:当k较小时，分母的比重较小，f约束条件:艺delay(i,j)<,A,U.j)任P"(x.v)更加偏重于代价的优化，当k较大时，分母的VVEM
6、(2)比重较大，f更加偏重于延迟的优化，事实其中△为时延上限(或称时延约束)，该上，当k足够大时(一般为20以上)，可以得参量定义了实时业务的传送延时要求。PT(s,到与Dijkstra最短路径算法同样的延迟限，v)为树T中从发送源s到接收点v的路径，而且同时所得到的总代价一般较小。但当kM为接收点的集合。比较大时，不但增加运算的时间，同时也有可能会溢出，于是对链路函数f进行了一些小2链路选择函数的变化，使之成为:本文中的链路选择函数是在需要满足f(v,w)=logc(v,w)一k‘log(A一QoS请求的多播路由中，用于平衡代价与延P(v)一D(v,w))迟的一种路由选择策略。当前的链
7、路选择函P(v)+D(v,w)<,6数多采用文献[z7中提出的以下两种:否则，f(v,w)二0f(v,w)=c(v,w)同时链路函数的搜索过程直接在网络上P(v)+D(v,w)
