网络编码(NC)[1]理论是21世纪初在信息论领域中的一个重要突破，其划时代意义在于：推翻了独立的比特不能再被压缩的经典结论，指出网络信息流可以被压缩，从而可进一步提升网络吞吐量，因此该理论也被称为网络信息流理论。
至今网络编码理论已经应用于众多领域，如P2P、应用层多播、无线Ad hoc网络、无线传感器网络和无线Mesh网络等。网络编码的主要优缺点和关键理论问题研究可参见文献[2]，限于篇幅不再赘述。
本文主要阐述网络编码在P2P中的应用，包括P2P文件下载和P2P流媒体中的应用，它们的主要区别在于对P2P流媒体中的应用有实时性的要求。因此网络编码应用于P2P流媒体中需额外考虑优先级的问题。下面首先介绍随机网络编码，具有分布式特性，目前应用非常广泛。
1随机网络编码
Ho等在文献[3]中提出了分布式网络编码的构造方法——随机网络编码(RNC)，该方法基于一种随机选择编码向量的策略：对于除了信宿节点外的所有中间节点，只要在一个足够大的有限域上随机选择它们输入链路到输出链路的映射，且各节点映射关系的选取是相互独立的，从而保证各信宿能以较高概率成功译码。
如图1所示，源节点S向目的节点R1和R2发送消息X1和X2。各链路上的系数向量(全局编码向量)和信源发送的信息进行同步传输，各个系数向量ξ1,ξ2……ξn 在有限域中随机选取，在通过编码节点时，系数向量根据随机选取的映射关系进行更新，最终目的节点R1和R2收到的输入信息将包含输入链路对应的全局编码向量和信源发送的信息流，例如R1收到ξ1X1+
ξ2X2和ξ5(ξ1X1+ξ2X2)+ξ6(ξ3X1+ξ4X2)，同时R2收到ξ5(ξ1X1+ξ2X2)+ξ6(ξ3X1+ξ4X2)和ξ3X1+ξ4X2，然后采用高斯消元法(即解线性方程组)正确译码获得X1和X2。
文献[3]中给出了解码概率的定理，当信源相互独立或线性相关，所有节点的全局编码向量都在有限域Fq上独立均匀选取，则接收节点能以最小概率(1-d /q)η译出信源发送的消息，其中d 是信宿节点的数目，q(>d )为编码符号域的大小，η是随机选取编码系数的链路数目。该定理说明只要当编码符号域q足够大，总可保证接收节点以较高概率成功译出信源发送的信息。文献[4]指出当有限域大小|Fq |=216和链路数|E |=28时解码成功率可达0.996，而且指出|F |=28就足够实际使用了。
RNC具有分布式特性，无需事先获知整个网络的拓扑信息，尤其适用于拓扑结构动态变化或者大规模的网络。微软提出的P2P文件下载系统Avalanche[5]便是首先采用RNC的典型P2P应用。
2网络编码在P2P文件下载中主要技术
P2P文件下载中主要有以下3种网络编码技术。
2.1无分代随机网络编码技术
典型代表是微软公司开发的基于随机网络编码(RNC)的P2P文件下载系统Avalanche[5]，其原理(如图2)是：假设服务器需要传输文件给对等节点A，则首先将服务器上的文件分解成n 个文件块，即B1,B2……Bn，然后应用随机网络编码，随机选择系数c 1，c 2……cn，将线性网络编码后的组合块E1=c 1B1+c 2B2……cn Bn传送给对等节点A，假设对等节点A又收到另外一个编码后的组合块E2=c 1'B1+c 2'B2……cn' Bn，该组合块来自其它对等节点或者服务器。然后对等节点A再随机选择编码系数c 1″、c 2″，对E1和E2进行线性操作，将操作的结果E3=c 1″E1+c 2″E2发送给对等节点B，如此则对等节点 B又传送给其它的对等节点。只要每一个对等节点收到足够多的线性无关组合，就可以通过解线性方程组译出原始文件块。
P2P文件下载中采用网络编码的优势是：分块随机组合后，整个网络的分块分布均衡化，而且能够适应P2P系统的动态变化。例如，某节点动态离开后，相应的分块也随之带走，对BitTorrent而言，节点离开可能带走稀有分块，从而造成“死档”；而对Avalanche系统，由于网络中存在所有分块的组合，只要收到足够多的线性无关组合，就可以通过解方程组得到所需的分块，因而可使下载“死档”的概率大大降低。
2.2分代网络编码技术
当将网络编码应用于P2P网络中时，编码的策略将会对网络的性能产生至关重要的影响。原始的编码策略是将一个文件分成多个分块，然后在所有分块之间进行编码传输，该方法虽然可以提高网络的传输效率，但也存在两点不足：第一，由于编解码的过程是在一个文件的所有分块之间进行的，导致系统的计算开销过大；第二，解码出文件的前提是收到的编码过的分块组合数目等于或大于文件原始分块数目，因此当没有达到这样的数目之前，得到的编码过的分块组合是无法解码出文件的原始分块的，这种编码方式对文件的传输很不利，尤其是对于流媒体而言。因此可以考虑使用分代技术。
分代技术[6]是指将需要传输的文件分成多个代，每代拥有固定数目的分块，编解码的过程发生在代内的分块之间，图3所示是一个拥有m 代的网络编码示意图，对每一代内的分块进行编码，产生多个经过编码的分块组合 E(gi)，各代之间编码产生的分块组合是相互独立的。分代网络编码技术也存在一个问题，即有时由于节点的退出，网络中已经不存在足够线性无关的编码分块组合来解码出某一代的原始分块，导致无法解码出完整的文件。为了解决该问题，可以引入代间编码技术。
2.3代间网络编码技术
代间编码技术集合相邻的多代组成一个代集，图4中所示是一个拥有m 代、每代拥有k 个分块的代集，代集内每一代的编码包括了代集内这一代以及之前所有代的分块的信息，例如考虑某代gi(i≤m -1)的编码分块，它是由代g 0、g 1……gi中的所有分块编码而来，代集之间编码产生的分块是相互独立的。同样，要解码代gi，总共需要获得代g 0、g 1……gi之中共(i+1)k个独立的编码分块组合，同时解码出代g 0、g 1……gi。这样的编码技术决定了它无法单独解码出某一代，但是同样它也有一个好处，即当代集中的某一代无法得到解码所需要的足够多的编码分块时，缺少的部分可以由其序号之后的代来弥补，例如当gi -1代无法解出的可由后一代gi代弥补。虽然说在代的规模都是k个分块的情况下，代间网络编码技术需要的计算开销将大于分代技术，但是当分代技术中代的规模是mk个分块时，分代技术的计算开销将会比代间编码技术高的多，体现了代间网络编码技术的优越性。
