面向数据分发的网络编码研究

论文摘要

大规模的数据分发有着广泛的应用背景。在现有网络条件下,如何更有效利用网络资源并实现高质量的数据分发,已成为网络信息流研究领域的重要课题之一。近些年来提出的网络编码为实现这一目标提供了新的解决方案。网络编码的核心思想是允许通信网络中的节点对传输的信息进行处理和操作（如有限域中的运算等）,而不再限于存储和转发。网络编码革命性地拓展了现有的基于存储和转发的数据分发模式,被认为是进入21世纪后信息处理和信息传输理论研究领域上的重大突破,具有重要的理论价值和广泛的应用前景。国内外许多知名大学、科研机构和公司等都积极投入对网络编码的研究,并取得了一些重要的研究成果。已经证明,网络编码能显著改善数据分发系统的性能,如提升网络吞吐量,节约传输带宽和均衡网络负载等。然而,与基于存储和转发操作的路由传输机制相比,网络编码系统中的节点需要执行频繁的编码和译码操作,这必将消耗额外的计算资源（如I/O和CPU等）,从而增加了在实际网络中部署和实施网络编码的成本和代价。因此,对面向数据分发的网络编码传输过程进行优化,减少网络编码操作所需的额外计算消耗,以此来实现低代价网络编码数据分发,对进一步提升数据分发系统的性能并促进网络编码的大规模应用有重要的指导意义。本文以降低网络编码操作所需的额外计算消耗为出发点,研究能实现更高效的基于网络编码的数据分发模式。研究主要从以下几个方面展开:（1）基于信息流向量的网络编码传输模型的研究;（2）基于关键链路的低代价网络编码实现算法的研究;（3）基于分簇网络编码的传输策略与相关算法的研究。本文的研究工作得到了国家自然科学基金“无线Mesh网络流媒体分发研究”（No. 60773193）,华为公司高科技基金“面向P2P的网络编码研究”（No. HW200606301254）,湖北省智能互联网技术重点实验室开放基金（No. HSIT-200605）和华中科技大学电信系基础理论研究基金（2008）的资助。本文的研究成果包含以下几个方面:1)基于信息流向量的网络编码传输模型:将数据分发系统中传输的信息建模为网络信息流,提出了一种具有线性复杂性的描述网络信息流的方法:信息流向量。结合信息流向量,分析了网络编码系统中存在的信息流向量约束,提出了反映网络编码操作数的指标:代价函数,并构建了最小代价的网络编码传输模型。该模型将网络编码数据分发系统的优化问题转化为数学规划问题,因此能够利用数学规划的相关理论求解并确定出最小代价的网络编码数据分发模式。此外,为考虑一些特殊网络中网络编码操作执行效率的问题,提出了一种基于效用折中的网络编码传输模型。该模型对在实际网络中,构建具有最小代价的,基于网络编码的数据分发系统具有重要的理论指导意义。2)低代价网络编码实现算法的研究:通过分析网络编码的本质特性,将网络编码区分于传统的基于存储和转发的数据分发模式并显著提升数据分发系统性能的根本原因归结为构建的传输路径上存在“关键”链路。为实现给定网络中数据分发系统的理论吞吐量,关键链路必须传输编码信息。编码信息能够在信宿节点通过合适的译码操作加以“区分”。因此,在构建网络编码数据分发系统的传输路径时,如果能够保证形成较少的关键链路,就能在一定程度上减少系统中网络编码操作的执行次数,从而降低网络编码所需的额外计算消耗,进而降低网络编码的实施成本和代价,并构建低代价的基于网络编码的数据分发模式。基于该思想,提出了一种基于关键链路的低代价网络编码实现算法,并对该算法进行了分布式实现。3)基于分簇网络编码的传输策略与相关算法研究。虽然网络编码源于IP组播,并被证明能提升组播网络中的数据分发性能,但由于技术和非技术上的挑战,IP组播并没有在现有互联网上得到大规模的部署和应用。作为一种替代的解决方案,基于对等网的协作式数据分发模型及其系统近年来得到了长足的发展,并被广泛应用。网络编码与基于对等网的协作式数据分发模型相结合,是网络编码应用研究领域的热点。然而,由于网络编码固有的特点,即节点需要执行编码和译码操作,一些学者对网络编码究竟能在多大程度上提升协作式数据分发系统的性能表示怀疑。以此为研究背景,以降低节点执行编码和译码操作的复杂性为目标,提出了分簇网络编码的思想。基于分簇网络编码,提出了随机性选择和相关性检测等机制来保证在降低网络编码复杂性的前提下,进一步提升数据分发系统的性能。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 选题背景与意义
• 1.2 研究内容与本文组织
• 2 面向数据分发的网络编码概述
• 2.1 网络编码的理论基础
• 2.2 问题的提出和研究动机
• 2.3 典型的解决方案及其分析
• 2.4 本文提出的解决方案及其创新点
• 2.5 本章小结
• 3 效用折中的网络编码传输模型
• 3.1 网络信息流与信息流向量
• 3.2 基于信息流向量的网络编码模型
• 3.3 效用折中的最优化网络编码传输模型
• 3.4 仿真与结果
• 3.5 本章小结
• 4 低代价网络编码实现算法
• 4.1 网络编码的本质分析
• 4.2 基于关键链路的低代价网络编码实现算法
• 4.3 低代价网络编码传输的分布式实现
• 4.4 仿真与结果
• 4.5 本章小结
• 5 基于分簇网络编码的数据分发策略与算法
• 5.1 问题描述和研究动机
• 5.2 分簇网络编码
• 5.3 改进的网络编码数据分发模型
• 5.4 仿真与结果
• 5.5 本章小结
• 6 总结与展望
• 6.1 本文总结
• 6.2 后续研究的展望
• 致谢
• 参考文献
• 附录1：攻读博士期间相关专利与论文