摘  要： 通过对网络编码理论和现有P2P文件共享系统的深入研究，设计了一种基于线性网络编码的P2P文件共享系统。该系统的优点是解决了现有P2P文件共享系统中存在的不能充分利用网络资源、“种子”节点突然退出造成文件下载不完等问题。实验结果表明，该系统克服了现有系统中存在的问题，同时也提高了整个系统的吞吐量并增强了系统的稳定性。
关键词： 对等网络；网络编码；比特洪流

　对等网络P2P（Peer-to-Peer Network）是分布式系统与计算机结合的产物，是采用对等模式工作的计算机网络，它开发了网络中每个节点的网络能力。基于P2P的文件共享系统摆脱了原有基于客户/服务器（C/S）体系结构集中式访问模式的束缚，通过汇集网络边缘可用资源提供服务，现已成为Internet上下载大文件的主流模型。但是现有的P2P文件共享系统也存在一些问题：
　（1）如果“种子”节点突然离开P2P网络，可能造成网络中其余计算机不能完整地下载源文件。
　（2）一个好的数据块调度算法时间复杂度高，执行效率低，这将影响到客户端的下载时间。
　（3）在现有的P2P通信网络中，信息的传输都是从源节点出发，经过中间节点的存储转发到目的节点。在这个过程中，中间节点起着中继作用，其并未对收到的信息做任何处理，这种传统的通信模式很难达到网络的最大吞吐量。
　本文在对网络编码和现有的P2P文件共享系统工作原理研究的基础上，提出了一种基于线性网络编码的文件共享系统实现方案。利用网络编码的优势，来解决现有P2P文件共享系统中存在的问题，完善和增强系统的性能。

1.3 线性网络编译码器实现算法说明及性能分析
　在实际工作中，P2P网络的拓扑结构经常会随着节点的加入或退出发生变化，所以网络编码采用随机线性网络编码[4]，即网络节点对编码系数是随机选取的，并且对输入数据包进行线性操作，其具有良好的拓扑适应性。但从网络编码原理分析可知，网络编码算法时间复杂度较高，因此，本文在编译码器的实现程序中采取了一些优化策略，以尽可能降低计算量，提高编译码的速度。策略如下：
　（1）有限域运算。编译码过程中需要有大量的有限域乘除运算，本程序采用离散对数方法来减少运算量。利用有限域中特殊元素生成元，将有限域中任何非零元素唯一的表示为生成元的指数形式，因此有限域元素相乘除的运算都可转化为指数运算。
　（2）对源文件采用“代”（Generation）划分[3]。P2P网络中等待下载的文件通常都在百兆以上，数量庞大的源文件分组使相应的编码矩阵和解码矩阵维数很大，加剧了编译码运算过程中的运算量。本文对源文件采用“代”划分的方法，以达到有效降低编译码矩阵维数、简化运算量的目的。
　（3）稀疏矩阵。网络编码的编码系数是随机选择的，随机选择的编码系数是均匀分布的，编码系数中零的个数很少，所以程序的编码矩阵选择使用稀疏矩阵[5]，这样可以有效降低编译码计算量。
　基于随机线性网络编码的原理和上述算法优化策略，本文采用C++在Linux环境下实现了传统的线性网络编码编译码器和随机线性网络编码编译码器（采用上述优化策略）。用100 MB的文件在两种编译码器上分别测试了分组大小从64 KB到2 MB的编译码运行速率。通过分析图2的编译码器性能图可以得到，经过优化策略的编译码器性能明显优于传统网络编码的编译码器。实验结果证明，将上述策略应用于网络编码的编译码器是有效的，所以选择合适大小的分组可以充分发挥编译码器的性能。

2 线性网络编码在P2P文件共享系统中的应用
　当前，BitTorrent是使用最为广泛的P2P文件共享系统之一[6]。通过对BitTorrent系统工作原理、线性网络编码理论的研究和分析，将本文提出的线性网络编译码器应用到BitTorrent客户端系统中，实现基于线性网络编码的P2P文件共享系统。图3是基于线性网络编码的BitTorrent系统框架图。该系统主要由5个模块组成：（1）传输机制模块：提供Socket的通信，收发消息。（2）编码器模块：对数据进行编码。如果当前的节点是种子节点，就对原始数据进行编码；如果是非种子节点，就对当前收到的同一“代”的编码过的数据进行再次编码。（3）线性检测模块：对收到数据包的编码向量进行线性相关性的检测。如果线性无关，将该数据包存放在临时文件中；如果线性相关，将该数据包抛弃；如果临时文件存放的线性无关的数据包达到一定数量，就可以进行译码。（4）译码器模块：对收到编码过的数据包进行译码，恢复源文件。（5）成员管理模块：让当前客户端能够与系统中一定数目的其他客户端建立连接，并在运行过程中实现对与其连接的其他客户端进行淘汰和更新。

　将基于线性网络编码的BitTorrent文件共享系统运行在实验室实际的网络环境中（12台PC）。在实验过程中，将种子节点中途退出。实验最终结果表明，其余客户端都可以正确地下载完源文件。通过对实验结果进一步分析得到一些结论：（1）该系统可以解决P2P网络中“种子”突然退出可能造成的文件下载不完的问题；（2）基于网络编码的BitTorrent并没有比普通的BitTorrent性能快很多，这是由于编码和译码时间复杂度比较高，从而影响系统的整体性能。
　P2P文件共享系统已经成为了Internet的主要应用之一。本文实现了一种基于线性网络编码的P2P文件共享系统。该系统可以提高网络的吞吐量、增强系统的可靠性并提高下载成功率。由于网络编码存在着计算复杂度高的问题，虽然在编译码器的实现方法中结合了一些有效策略，可以降低部分计算量，但是编译码器的计算量开销依然很大，因此研究降低网络编码的复杂性，实现最小代价的网络编码，具有重要的理论意义和使用应用价值。
参考文献
[1] AHLSWEDE R， CAI N， LI S Y R， et al. Network information flow[J]. IEEE Transactions on Information Theory， 2000， 46（4）：1204-1216.
[2] LI S Y R， YEUNG R W， Ning Cai. Linear network coding[J]. IEEE Transactions on Information Theory， 2003，49（2）：371-381.
[3] CHOU P A， WU Y N， JAIN K. Practical network coding[C]. The 41st Allerton Conference on Communication， Control and Computing Monticello， Kluwer，2003.
[4] HO T， MEDARD M， KOETTER R， et al. A random linear network coding approach to multicast[J]. IEEE Transactions on Information Theory， 2006，52（10）：4413-4430.
[5] MA G， XU Y， LIN M， et al. A content distribution system based on sparse linear network coding[C]. Proceedings of the 3rd Workshop on Network Coding， Theory， and Applications （NETCOD 2007）， 2007.
[6] GKANTSIDIS C， RODRIGOUE Z. Network coding for large scale content distribution[C]. INFOCOM 2005， 2005（4）：2235-2245.