非线性网络编码及网络编码在文件分发中的应用研究

摘要

在当前网络中，节点采用存储转发的方式传输信息，而在网络编码所研究的模型中，网络节点能够对信息进行编码。Ahlswede等人证明了通过网络编码方式能够使最大信息流量达到多播网络的容量上界。 本论文研究了网络编码领域中的以下问题：网络编码的非线性编码方案、仿真平台上支持网络编码功能的扩展以及文件分发系统中的网络编码应用。 由于存在线性编码不可解的网络，寻找并研究非线性编码有可能是网络编码中一个有意义的新方向。 第二章给出了非线性编码的多项式描述(称为多项式编码)，并与线性编码进行了比较。通过对编码函数可解码性质的研究，得到以下结论：(1)证明了在一般的情况下，多项式编码至少具有与线性码相当的编码能力。(2)给出了从线性编码构造多项式编码的一种方法。(3)利用编码函数和拉丁矩阵之间的联系证明了更复杂的多项式编码的存在性。 研究网络具有可行网络编码的充分和必要条件是理论上的重要问题。 第三章给出了网络具有可行非线性网络编码的必要条件：若网络存在一个可行的非线性编码，则该网络可拟阵化为一个代数可表示拟阵。论文将可行非线性编码所具有的函数独立性归结到拟阵的代数可表示性问题，得到了这一必要条件。基于这一必要条件，结合拟阵理论中的相关工具得到结论：(1)存在线性编码不可解，但非线性编码可解的网络。(2)存在线性编码和非线性编码都不可解的网络。相对已有工作，论文使用的方法更系统简洁地回答了网络编码在非多播网络应用上的两个基本问题：(1)线性编码是否足以实现所有非多播网络上的传输?(2)网络编码(包括线性编码和非线性编码)是否足以实现所有非多播网络上的传输? 使用网络编码技术将对网络上现存的其它应用产生怎样的影响?这需要进行仿真研究。现有网络仿真平台不支持网络编码模式，从而限制了这类研究。 第四章给出了网络仿真平台NS(NetworkSimulator)上支持网络编码功能的扩展方案。论文在研究NS架构的基础上，对其节点架构进行了调整，利用伽罗瓦数学函数库实现了网络编码功能，并在经典网络拓扑下验证了该方案的可行性。下一步，可基于这一扩展研究网络编码对现存网络应用的影响。 网络编码在文件分发协议中的应用是当前一个存在争议的研究热点，存在两个主要问题：(1)网络编码方案是否具有比稀缺优先算法更好的效率，从而提高P2P文件分发系统的性能?(2)如果网络编码方案较稀缺优先算法更优，它能在多大程度上提高现有系统的性能?而不是在新的系统上对网络编码方案和稀缺优先算法进行比较。 第五章解决了上述两个问题。对第一个问题，论文首次对使用网络编码后的系统进行了建模分析。该方法有效地避免了基于实验模拟方法的缺点：不同实验设置及网络编码的特殊实现机制可能影响实验结果，导致结论的模糊性。论文将文件分发效率的计算问题归结到求两向量子空间相交的概率，进而利用高斯多项式系数求解，给出了改进系统的效率下界。另外，首次指出系统效率与编码域大小的关系。 论文通过实验仿真的方法回答了第二个问题。论文以流行的BitTorrent系统作为对比系统，并尽可能地保证了对比的公平性：参与对比的系统在其它机制上尽可能保持一致，保留了文件分发领域的基本假设，在一系列常见的分发场景中进行了对比实验。最后，模拟实验的结果很好地吻合了论文模型分析的结果。 第六章对本文进行了总结，并给出了几个有待进一步研究的问题。

目录

文摘

英文文摘

论文说明：符号说明

声明

第一章绪论

1.1网络编码简介

1.2基本术语和模型

1.3 问题起源：多播容量的上确界与网络编码

1.4网络编码的发展

1.5本文的主要工作

第二章非线性编码的一些研究

2.1 引言

2.2模型

2.3主要结论

小结

第三章非线性编码可解的必要条件

3.1 引言

3.2拟阵，线性可表示拟阵及代数可表示拟阵

3.3线性编码与线性可表示拟阵

3.4构造可拟阵化的网络

3.5非线性编码与代数可表示拟阵

3.6 小 结

第四章NS仿真器上的网络编码扩展

4.1 引言

4.2模型和系统分析

4.3系统设计

4.4实验演示

第五章 网络编码在文件分发中的应用

5.1 引言

5.2背景

5.3模型分析

5.4实验系统设计与实现

5.5实验模拟

5.6 小结

第六章总结与展望

6.1主要研究成果

6.2研究展望

参考文献

攻读博士学位期间已录用和投稿的论文

致谢