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

论文摘要

网络编码技术与传统的存储转发路由不同,允许中间节点对数据进行编码操作。利用网络编码技术可以明显改善分层组播的吞吐量,成为当前的研究热点。论文研究基于网络编码的多速率组播问题,利用网络编码来提高多速率组播接收节点的接收速率。通过对现有的基于网络编码的分层多速率组播问题进行综述,分析了现有算法的优缺点,针对各分层层速率不确定的情况提出了一种启发式的子图划分分层组播算法,并对提出的方案进行了实验和性能分析。论文的主要工作如下：首先对组播和网络编码技术进行了概述,总结了几种主要的多速率组播技术,并对组播网络中的网络流和网络编码理论进行归纳和描述,重点概述了线性网络编码技术的原理和分类。对基于网络编码的分层多速率组播问题进行研究,概述了分层组播问题的原理和基本模型,并对目前存在的问题进行了描述。根据层速率是否固定将基于网络编码的分层组播问题划分为两类,对这两类问题分别进行介绍,并总结了目前针对两类问题的基于网络编码的分层组播解决方案,比较分析了各方案的优势和不足。在分层层速率可变时,分层组播优化问题是非线性的整数规划问题,求解十分复杂,不适合大规模网络。针对该问题,论文基于最小编码网络的思想,提出了一种多项式时间的启发式子图划分算法。考虑到分层内使用网络编码算法使得同层内各接收节点不会竞争链路带宽,而不同分层之间的数据传输仍会竞争链路带宽的特点,在该算法中,为了最大化接收节点总的接收速率,通过增加同层内链路的重用程度并且最小化每层子图传输的链路进行子图划分,使得更多的剩余链路可以传输下层子图数据。模拟测试结果表明,该算法能够获得较好的总接收速率和带宽利用率,并且大大缩短了计算时间。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景及现状
• 1.1.1 多速率组播
• 1.1.2 网络编码研究现状
• 1.1.3 基于网络编码的多速率组播
• 1.2 研究意义和主要研究内容
• 1.3 论文的组织
• 第二章 相关理论与技术
• 2.1 组播技术
• 2.1.1 单速率组播技术
• 2.1.2 多速率组播技术
• 2.2 网络编码简介
• 2.2.1 网络流理论
• 2.2.2 网络编码基本理论
• 2.2.3 线性网络编码
• 2.3 本章小结
• 第三章 基于网络编码的分层多速率组播问题研究
• 3.1 概述
• 3.1.1 分层组播原理和模型
• 3.1.2 基于网络编码的分层组播问题描述
• 3.2 DCM-rate问题
• 3.2.1 网络编码
• 3.2.2 集中式方案
• 3.2.3 分布式方案
• 3.3 DVM-rate问题
• 3.4 本章小结
• 第四章 基于最小编码网络的子图划分分层组播算法
• 4.1 概述
• 4.2 最小编码网络
• 4.2.1 最小编码网络定义
• 4.2.2 最小编码网络算法描述
• 4.3 基于最小编码网络的子图划分分层组播算法SPLM-MCN
• 4.3.1 SPLM-MCN基本思想
• 4.3.2 SPLM-MCN过程描述
• 4.4 仿真实验与分析
• 4.4.1 网络节点数对性能的影响
• 4.4.2 接收节点数对性能的影响
• 4.5 本章小结
• 第五章 总结与展望
• 5.1 工作总结
• 5.2 下一步工作
• 参考文献
• 致谢
• 攻读硕士学位期间主要的研究成果