网络编码若干问题的研究

论文摘要

2000年,Ahlswede等首先提出了网络信息流(network information flow)的模型,在此模型下,可以假定节点间的连接是点到点的,链路上是无噪声的。在此基础上Ahlswede等研究了组播网络通信的容量问题,并提出了网络编码(network coding)的概念。通常的网络通信中,中间节点只担当数据转发的作用,而不对数据进行处理。在网络编码的模型下,中间节点对接收到的数据流进行编码处理,然后再发送,在接收端对接收到的已编码数据流进行解码处理。采用网络编码可以有效地利用网络资源,并且要实现达到网络容量的通信,采用网络编码是必要的。网络编码理论是近年网络信息论领域的重大突破,引发了广泛的研究兴趣。本文对网络编码若干相关的问题进行了研究。在介绍了网络编码的背景,基本概念和理论后,主要研究了如下几个方面的内容。网络编码的安全性。安全性是现代网络研究和设计需要考虑的一个重要方面。本文第3章首先引入若干辅助数学结果,建立了应用线性网络编码时,线性独立性和统计独立性的等价性,在此基础上提出了实现信息论意义上安全的充分必要条件。为保证信源信息的安全性,引入随机密钥信息与信源信息进行编码是必要的。本文研究了在一种应用网络编码特殊的组播通信情况下,需要引入密钥信息率的一个下边界。网络编码的弱安全性。为了保证系统的安全性,通常不得不引入密钥信息,这就必然会降低通信的有效性。在某些情况下,信息论意义下的安全标准可以适当的放松以换取传输率的提升。在第4章中研究了网络编码的弱安全性,提出了两种弱安全标准的定义,并对其进行了初步的讨论。网络编码与网络流控。在现代通信网络中,流控(flow control)是保证网络高效和可靠运行不可或缺的重要组件。特别是在基于分组的网络中,流控机制可以消除拥塞,提高吞吐,减小时延,以及确保不同数据流间的公正性(fairness)等等。在本文第5章研究了基于网络编码组播的流控设计问题。首先由Kelly等提出的用效用函数(utility function)描述设计目标和用优化分解获得分布式算法的方式为研究网络相关问题提供了新的理论工具,更进一步Chiang等提出用优化分解的方式架构网络为网络研究提供了严格的数学语言。我们把上述网络效用最大化的研究方式引入到基于网络编码组播通信的流控设计中,采用阶梯分解的方式(hierarchical decomposition),提出了一种架构方案,并给出了分布式的流控算法。本文的第6章总结了本文的工作和不足,指出了仍需进一步深入研究的地方。网络编码理论为理解网络,设计网络,以及解决网络相关的问题提供了新的思路,已有的研究成果证明其重要的理论和实际价值。本文在此背景下对网络编码的若干问题做了初步的研究。本文的工作得到973项目和国家重点科技攻关项目的支持。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 网络编码的背景
• 1.2 网络编码的概念
• 1.3 网络编码的现状
• 1.4 本文的组织结构
• 1.5 参考文献
• 第2章 网络编码的基本概念
• 2.1 引言
• 2.2 网络编码的起源
• 2.3 图论相关概念和术语
• 2.4 网络编码和组播网络的容量
• 2.5 线性网络编码
• 2.5.1 线性网络编码的模型
• 2.5.2 线性网络编码的编码方式
• 2.5.3 线性网络编码的边界
• 2.6 随机网络编码
• 2.7 纠错网络编码
• 2.8 网络编码的实际问题
• 2.9 小结
• 2.10 参考文献
• 第3章 网络编码的安全性
• 3.1 引言
• 3.2 网络编码安全性的数学描述
• 3.2.1 一般描述
• 3.2.2 代数描述
• 3.2.3 信息测度的代数描述
• 3.2.4 线性编码安全性的充分必要条件
• 3.3 安全网络编码的一个必要条件
• 3.3.1 一种特殊情况网络编码条件下的安全性
• 3.3.2 Shannon保密系统
• 3.3.3 Shamir的秘密共享机制
• 3.3.4 安全网络编码的一个必要条件
• 3.3.5 例子和分析
• 3.4 小结
• 3.5 参考文献
• 第4章 网络编码的弱安全性
• 4.1 引言
• 4.2 一种弱安全性的定义
• 4.3 另一种弱安全性的定义
• 4.4 小结
• 4.5 参考文献
• 第5章 网络编码与网络流控
• 5.1 引言
• 5.2 网络流控基本问题
• 5.2.1 实现网络流控的意义
• 5.2.2 网络流控的模型
• 5.2.3 拥塞控制
• 5.2.4 时延控制
• 5.2.5 网络资源分配的公正性控制
• 5.3 TCP流控
• 5.3.1 TCP的端到端（end-to-end）流控
• 5.3.2 接收端的流控
• 5.3.3 TCP的拥塞控制
• 5.4 基于优化的网络流控设计
• 5.4.1 优化理论的数学准备
• 5.4.2 基于优化理论流控的基本原理
• 5.4.3 优化分解与网络架构
• 5.4.4 用优化理论理解TCP流控
• 5.5 基于网络编码的组播通信中的流控
• 5.5.1 流控问题的数学描述
• 5.5.2 阶梯分解方式
• 5.5.3 其它阶梯分解方式
• 5.6 网络流控设计与实现的再思考
• 5.6.1 网络研究的方法
• 5.6.2 网络研究的微观和宏观视角
• 5.6.3 数学理论的工程化
• 5.6.4 网络的构建原则
• 5.6.5 网络复杂度的分配
• 5.7 小结
• 5.8 参考文献
• 第6章 总结和展望
• 6.1 本文工作的总结
• 6.2 本文不足及进一步工作
• 符号对照表
• 攻读学位期间获得的研究成果
• 致谢