基于遗传算法的qos组播路由算法研究

《基于遗传算法的qos组播路由算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、山东大学硕士学位论文基于遗传算法的QoS组播路由算法研究姓名：孙玲玲申请学位级别：硕士专业：计算机系统结构指导教师：贾智平20080405山东大学硕士学位论文摘要随着Internet和宽带网络技术的日益发展，传统的以文字和图片为主的服务已不能满足用户的需要，具有视频和音频的多媒体服务成为主流。近几年嵌入式网络数字视频监控系统正在得到广泛应用。由于嵌入式网络数字视频监控系统传输的数据量大而系统资源有限，采用点对点的传输方式会增加服务器的负担，造成网络拥塞。而组播技术可以将相同的数据从嵌入式网络视频服务器同时并行地发送到接收者，大大节省了网络

2、带宽，减少了数据冗余，即使用户数量成倍增加，主干网络带宽也不会随之增加。同时视频监控系统对信息传送的时延和时延抖动有严格的要求，要求传输的数据必须在一定的时延限制内到达所有的接收者，并且接收者之间的延迟差别也需在一定的范围内，即满足一定服务质量(OoS)的要求。因此在嵌入式网络数字视频监控系统中我们需要解决OoS组播路由问题。该问题的目标是寻找一棵满足OoS要求的组播树，使该树覆盖所有的组成员，同时使网络费用达到最小。遗传算法是近几年提出的一种模拟生物界自然选择和遗传机制，具有高度并行，群体寻优的新型最优化搜索算法，近年来已有一些学者采用

3、遗传算法来求解OoS组播路由问题。本文在分析现有遗传算法的基础上，提出了两种改进的遗传算法。第一个改进算法针对遗传算法运行初期易陷入早熟，运行后期收敛缓慢的问题进行了改进，采用初始群体均衡生成法和自适应变异操作可以很好地抑制早熟现象，引入排序对适应度进行拉伸，从而加快了算法的收敛速度。仿真实验结果表明改进后的遗传算法收敛速度快，性能好，可以满足系统资源有限和实时性的要求。第二种改进算法是在分析了遗传算法和蚁群算法各自优缺点的基础上，将两种算法进行融合来求解OoS组播路由问题，算法的前一阶段利用遗传算法的快速性、随机性、全局收敛性产生后一阶

4、段蚁群算法所需要的初始信息素，加快了蚁群算法利用正反馈特性进行搜索的速度。经融合后的算法，在时间效率上优于蚁群算法，在求解效率上优于遗传算法，形成了一种时间效率和求解效率都比较好的启发式算法。山东大学硕十学位论文本文最后针对现有视频监控系统单播传输存在的问题，将组播技术应用到网络视频监控系统中，可以有效地节省网络资源，降低时延，减少网络堵塞的几率，较好地保证了数字视频传输的实时性和服务质量。关键词：QoS；组播路由；遗传算法；蚁群算法II山东大学硕士学位论文ABSTRACTWiththedevelopmentofInternetandbr

5、oadbandtechnology，traditionalservicesforwordandpicturecannotsatisfytheneedofusers，mediaserviceswithvideoandaudiobecomemainstream．Inrecentyears，embeddednetworkdigitalvideomonitorsystemiswidelyused．Becauseoflargedataandlimitsystemresource，unicastwillenhancetheburdenofserver

6、andleadtocongestion．ButmulticastcantransmitthesamedatafromembeddednetworkvideoservertothereceiversparallellySOthatitcansavebroadbandandreducedataredundancy．Atthesametime，videomonitorsystemhasthestrictrequestfordelayanddelay-jitter．Thetransmitteddatamustreachallreceiversin

7、limitedtime，andthedelaydifferencebetweenreceiversalsoneedstobeinalimitedrange，thatistosay，satisfythedemandofQoS．ThereforeweneedtosolveQoSmulticastroutingquestioninembeddednetworkdigitalvideomonitorsystem．ThegoalofthequestionistofindamulticasttreesatisfyingthedemandofQoSth

8、atoverlayallgroupnumbersandmakethecostminimum．Geneticalgorithmisanewglobaloptimalalgorithmsimula