基于网络编码的子图划分多速率组播算法研究

《基于网络编码的子图划分多速率组播算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、ResearchOfSubgraphPartitionMultirateMulticastAlgorithmBasedOnNetworkCodingSpecialty：．——SystemAnalysisandIntegration．——MasterDegreeCandidate：DaiLongquan一‘。。__’’‘。_-_-。。__-●一——————一●r———————________--___一Supervisor：里!Q￡翌亟蛰直g里选i：旦i堕gSchoolofInformationScience&EngineeringCentral

2、SouthUniversityChangShaHunanP．R．C㈣6眦3帅8㈣8㈣9咖眦—●m2吼Y原创性声明本人声明，所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。作者签名：氲墨是日期：兰年羔月旦日学位论文版权使用授权书本人了解中南大学有关保留、使用学位论文的规定，即：学校有权保留学位论文并根据国家或湖南省

3、有关部门规定送交学位论文，允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科学技术信息研究所将本学位论文收录到《中国学位论文全文数据库》，并通过网络向社会公众提供信息服务。作者签名：趣导师签名摘要网络编码技术与传统的存储转发路由不同，允许中间节点对数据进行编码操作。利用网络编码技术可以明显改善分层组播的吞吐量，成为当前的研究热点。论文研究基于网络编码的多速率组播问题，利用网络编码来提高多速率组播接收节点的接收速率。通过对现有的基于网络编码的分层多速率组播问题进行综述，分析了现

4、有算法的优缺点，针对各分层层速率不确定的情况提出了一种启发式的子图划分分层组播算法，并对提出的方案进行了实验和性能分析。论文的主要工作如下：首先对组播和网络编码技术进行了概述，总结了几种主要的多速率组播技术，并对组播网络中的网络流和网络编码理论进行归纳和描述，重点概述了线性网络编码技术的原理和分类。对基于网络编码的分层多速率组播问题进行研究，概述了分层组播问题的原理和基本模型，并对目前存在的问题进行了描述。根据层速率是否固定将基于网络编码的分层组播问题划分为两类，对这两类问题分别进行介绍，并总结了目前针对两类问题的基于网络编码的分层组播解决方案

5、，比较分析了各方案的优势和不足。在分层层速率可变时，分层组播优化问题是非线性的整数规划问题，求解十分复杂，不适合大规模网络。针对该问题，论文基于最小编码网络的思想，提出了一种多项式时间的启发式子图划分算法。考虑到分层内使用网络编码算法使得同层内各接收节点不会竞争链路带宽，而不同分层之间的数据传输仍会竞争链路带宽的特点，在该算法中，为了最大化接收节点总的接收速率，通过增加同层内链路的重用程度并且最小化每层子图传输的链路进行子图划分，使得更多的剩余链路可以传输下层子图数据。模拟测试结果表明，该算法能够获得较好的总接收速率和带宽利用率，并且大大缩短了

6、计算时间。关键词：分层多速率组播，网络编码，吞吐量，子图划分ABSTRACTNetworkcodinghaschangedtraditionalroutingwithonlystore．and．forward，anditallowsrelaynodestocodethedatatheyhavereceived．Networkcodinghasbeenahotsubjectoftheresearchfieldasaresultofitsthroughputimprovementonlayeredmulticastnetwork．Thispaper

7、focusesonthemultiratemulticastbasedonnetworkcodingandmakestheadvantageofnetworkcodingtoimprovethethroughputofmultiratemulticast，namelytotalreceivingrateofreceivers．Afterreviewingexistinglayeredmulticastproblemsbasedonnetworkcoding，thispaperanalyzestheadvantagesanddisadvantag

8、esofexistingalgorithms．Furthermore，aheuristicalgorithmofsubgraphpartition1a