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

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