资源描述：
《基于遗传算法的流媒体组播路由选择方法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、2004年4月北京邮电大学学报Apr.2004第27卷第2期JournalofBeijingUniversityofPostsandTelecommunicationsVol.27No.2文章编号:1007-5321(2004)02-0039-05基于遗传算法的流媒体组播路由选择方法121姜圳,张宏科,张礼勇(1.哈尔滨理工大学测控技术与通信工程学院,黑龙江哈尔滨150040;2.北京交通大学电子信息工程学院,北京100044)摘要:在满足一定时延限制情况下,找出包括特定源、目的节点的最小费用树是NP-Complete问题.针对
2、该问题对遗传算法进行理论分析,提出了较其它的遗传算法和启发式算法而言具有编码方式简单、收敛速度快的遗传算法,给出了组播路由的模型,并利用遗传算法对该模型进行计算机仿真分析.关键词:组播;路由;遗传算法中图分类号:TM393文献标识码:ATheApplicationofGeneticAlgorithminMulticastRoutingofMultimediaStream121JIANGZhen,ZHANGHong-ke,ZHANGLi-yong(1.CollegeofMeasure-controlTechnologyandCom
3、municationEngineering,HarbinUniversityofScience&Technology,Harbin150040,China;2.SchoolofElectronicsandInformationEngineering,BeijingJiaotongUniversity,Beijing100044,China)Abstract:Findingaminimalcosttreewhichcontainsaspecialsourceanddestina-tionnodesinacertainconstra
4、intsisaNP-Completeproblem.Amodelofmulticastrouteispresentedandtheresultofsimulationisshown.Comparedwiththeothergeneticalgorithmsandheuristicalgorithms,thegeneticalgorithmproposedinthisarticleissimpleandcanobtainoptimalresultantinashorttime.Theresultindi-catesthattheg
5、eneticalgorithmhascharacteristicsuchashigh-efficientinmulti-castrouting.Keywords:multicast;routing;geneticalgorithm目前随着高速网络的日益普及,流媒体业务也得到了迅猛发展.组播作为一点对多点的通信,是节省网络带宽的有效方法之一.组播路由器需要依据路由算法计算到所有组成员的最短路径.寻求组播通信路由树是基于一些优化目标的,一个频繁被考虑的优化目标是最小化树的收稿日期:2003-01-27基金项目:国家自然科学基金资助项
6、目(60272012);国家“863计划”资助项目(2001AA121014)作者简介:姜圳(1973—),男,博士生.E-mail:wangxl@dq.njtu.edu.cn40北京邮电大学学报第27卷[1]整个费用,这就是求解斯坦利最小树问题,目前已证明该问题是NP-Complete问题.针对该[2]问题大都采用启发式算法来解决.如Zhu算法,Zhu等人提出了一种构造受限Steiner树的[3]信源路由启发式算法.Sun-Langendoerfer算法是通过Dijkstra算法求解受限Steiner树的近似解.但是启发式搜索
7、算法需要找到一种能产生可行解的启发式规则,以找到一个最优解或近似最优解.该算法求解效率比较高,但对每一个需求解的问题都必须找出其特有的启发式规[4]则.Kompella算法采用信源路由方式构造受限树.首先构造全连通图,然后采用Floyd最短路由算法,但该算法必须解决延迟受限最短路d(d-1)/2次,d是源节点和目的节点的个数.[5,6]近年来遗传算法得到了广泛的应用,文献[7]采用的是遗传算法,但其以Nn×Nn位一维二进制编码作为遗传算法的编码机制,Nn为网络节点数.这样,当网络节点增加时,将导致编码N×N长度巨增,Nnnn×N
8、n位的编码长度会产生2的搜索空间,搜索空间过于庞大将导致搜索效率降低.本文提出的模型采用改进的二进制编码方法,码长为lbT,T为组播树的个数,该方法有效地降低了编码长度,从而缩小搜索空间,提高搜索效率.近几年也出现了一些改进的遗[8,9]传算法,如混乱遗传算法M
