网络编码在P2P网络中的应用

基金项目：国家自然科学基金资助项目(60872005)；华中科技大学校基金(2008)；华中科技大学电信系基础研究基金(2008)

    网络编码(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个分块时，分代技术的计算开销将会比代间编码技术高的多，体现了代间网络编码技术的优越性。

3 网络编码在P2P流媒体中主要技术

3.1 一种基于网络编码的P2P流媒体的节点架构
    基于网络编码的P2P流媒体把数据流分为若干个数据段，每个数据段再进一步划分为大小均为k 的n 个数据块，如图5所示
对等节点的系统构架[7]如图6所示，对等节点从上流节点接收数据块后按照其所属数据段的优先级进行收集，经由解码器送入播放缓存；编码器对解码后数据进行重新编码，发送给下行对等节点。

    编码器：对每一数据段中的数据块进行随机网络编码。邻居节点随机的选取编码系数[c 1,c 2……cm](m≤n)，对当前数据段中拥有的数据块进行编码。当m /n =1时表明该节点已拥有这个数据段中的所有n个数据块。

    解码器：节点收到数据块后，用Gauss-Jordan消元法进行逐步解码。解码过程中若发现线性相关的数据段则及时剔除。当一个数据段收到n 个线性独立的数据块之后，则可以完全解码。

    播放缓存：如图7所示分为3部分，首先下载紧急模式中的分块。同时对等节点对自己拥有的数据块进行重新编码，发送给下行节点。

3.2 基于网络编码技术的P2P流媒体的数据调度

3.2.1 分层网络编码
    基于网络编码技术的P2P流媒体较P2P下载在数据调度上需要重点考虑数据中一些紧急重要的数据。文献[8]提出了分层网络编码(HNC)，可以解决P2P流媒体因实时性造成的优先级问题。HNC编码方案使得那些紧急重要的数据包可以优先被解码。

    HNC编码举例如下：假设一个信息流被分为多个数据包，每个数据包属于A、B、C三类中的一类。其中A类数据包最重要，B类次之，C类最不重要。假设这个信息流仅6个数据包，分别为a1、a2、b1、b2、c1和c2，则HNC的编码构造方案如下：
N 1=f 11a1+f 21a2；
N 2=f 12a1+f 22a2+f 32b1+f 42b2；
N 3=f 13a1+f 23a2+f 33b1+f 43b2+f 53c1+f 63c2；

    这样，当接收到6个线性独立的编码过的数据包后，a1、a2一定能被解码，b1、b2仅在接收到6个为N 2或N 3类的数据包时才能被解码，c1、c2仅在接收到6个N 3类数据包时才能被解码。这样A、B、C三类包被优先解码的概率为A>B>C。这种方法从编码角度对具有优先级的数据调度提供了一种思路。

3.2.2 网络编码在P2P直播中的应用
    (1)Pull调度方法：
    目前，Pull调度方法在P2P流媒体技术中广泛运用，引入网络编码后，对该数据调度方法提出了新的要求：即需要决定对等节点应该从哪些邻居节点获取哪些数据块,以便每个数据块在播放之前都能被解码。如果不能被全部及时解码,则使不能被及时解码的数据块个数最少；与此同时还需考虑到节点间可用带宽的约束。

    文献[9]提出了一种数据调度算法,其主要思想:首先，随机选取n 个上行节点作为邻居节点。其次，对等节点按每个数据段播放的先后顺序对段内数据块发出请求；对每个数据段，如果未能收到n 个相互独立的数据块，则从n 个源节点以外的邻居节点请求数据块，直到收到n 个相互独立的数据块或邻居节点轮询完为止。

    此外，为优化传输效果，在当前节点随机选取完邻居节点后，会向这n 个邻居节点以外的待选邻居节点发送探测包。若探测结果显示待测对等节点与当前节点间的带宽和时延优于目前大部分的邻居节点，则剔除原邻居节点中性能最差的那个节点，把这个探测到的待测节点加入到邻居节点列表中去。

    (2)Push调度方法：
    经网络编码组合后可使数据段内的数据块具有无序性，所以Push调度方法可以更好地体现网络编码给P2P流媒体带来的好处，文献[10]中提出了一种基于网络编码的Push调度机制。

    Push调度方法中，邻居节点随机选取某一数据段编码后的数据块Push给下行节。Push时要优先考虑到马上就要播放的数据段。如图8，设选取当前播放点t 秒后的区域作为优先区域，邻居节点采用均匀分布的方式优先发送Push优先区域内数据段的相关数据块。当优先区域中的某数据段仍缺失一些数据块时，则紧急方案启动，在其带宽允许的情况下，其所有的邻居节点向其发送该数据段的数据块。即要保证优先区域内的所有数据段都需完整。当优先区域内的数据段都完成接收后，对其后的数据段采用特定的概率分布函数进行Push。该概率分布函数只要能达到Push后越接近优先区域的数据段越先收到n个数据块的总效果即可，如图9(a)。

    Push存在的问题：邻居节点Push时并不知道其Push当前数据块时，接收节点是否已经收到了n 个相互独立的数据块。所以Push机制需要一种预刹车方案[10]，当接收节点快接收到n 个数据块时，向其邻居节点发送一信息，表明其将要接收到n 个数据块，逐步减少向其Push的邻居节点的个数，从而减少不必要的数据传输。

    (3)Push调度方法与Pull调度方法(如图9(b))的比较：
    Push调度较Pull调度的优点：

• 缩短播放缓存的初始化时间：
  采用Pull的方法必须先交换媒体内容的数据信息，发送数据请求才能开始传输数据，这将导致一定程度的播放延时积累。Push调度方法采用同步播放机制，通过Push调度方法，新节点可以很快地获取所需的数据段。
• 提高带宽利用率：
  Pull调度方法中，缓存映射(BM)需要周期性的在节点间交换。Push数据调度方法只在播放了一个数据段，或完成某一数据段的下载时才将BM嵌入到编码后的数据块中。

3.2.3 网络编码在P2P点播中的应用
    P2P点播系统相对于直播系统而言具有更强的异步时序性。其核心问题是如何对用户异步播放操作进行快速响应。网络编码的引入使得对等节点可以更好的利用其邻居节点的资源从而缩短信息获取时间，并缓解节点对服务器的压力。

    举例说明如下：设服务器提供的信息流被分为A、B、C、D、E、F共6个数据包，X、Y、Z互为邻居节点。初始情况下，X拥有数据包A、B，Y拥有数据包A，Z没有任何数据包。

    (1)基于网络编码(NC)的数据调度算法
    如图10(a)，T0时间片内：节点X、Y、Z分别从服务器请求得到随机编码后数据包C-F，B-F和A-F；Y从X请求得到数据包B；Z从X请求得到编码后数据包A、B，并从Y请求得到数据包A。

    如图10(b)，T1时间片内：节点X从服务器请求得到与T0 时间片中编码系数不同的编码数据包C-F，从Y，Z分别得到编码后数据包B-F，A-F；Y从服务器请求得到编码后数据包B-F，从X，Z分别得到编码后数据包B-F，A-F；Z从服务器得到编码后数据包A-F，从X、Y分别请求得到编码后数据包A-F。（以上编码后数据包均要求编码系数线性无关，包括与T0时间片的编码系数线性无关。）

    如图10(c)所示，T1时间片结束后，X、Y、Z各拥有6个线性无关的数据包，到T2时间片便可解码得到所有消息。

    综上，NC算法仅花费2个时间片用于下载，从服务器请求6次数据，充分利用对等节点的资源，缩短了响应时间，有效地减轻了对等节点对服务器的压力。但是，NC算法也存在问题，即对等节点需接收到6个数据包后，才能被解码，当遇到一些立即就要播放的数据包时，NC算法反而会造成播放延时。

    (2)基于具有截止时间意识的网络编码的数据调度算法
    具有截止时间意识的网络编码(DNC)[11]是对NC的一种改进算法，可有效解决由NC算法造成的播放延时问题。DNC提出了编码窗(CW)的概念，CW大小即参与编码的数据包个数，其值由“有效邻居节点”个数与距当前播放点的时间片数目的乘积决定。“有效邻居节点”指拥有其所需数据包的节点。

    如图11(a)，T0时间片：设节点X、Y当前播放点分别为B、A。节点X的“有效邻居节点”个数为1(即仅能从服务器获取所需的数据包)，距当前播放点的时间片为1，即CW=1×1=1，由服务器处得到数据包C。节点Y的“有效邻居节点”个数为2(服务器和节点X)，CW=2×1=2，分别由服务器和节点X处获得数据包B-C和B。T0时间片结束后，节点X拥有数据包A、B、C，Y拥有数据包A、B，并可立即解码得到C。

    如图11(b)，T1时间片：X节点的当前播放点变为C，同理CW=1，从服务器获得数据包D。Y节点的当前播放点位B，由于T0时间片结束后，Y拥有数据包A、B、C，所需的数据包为D，“有效邻居节点”的个数为1(仅服务器)，距当前播放点B的时间片为2，CW=1×2=2,从服务器获得数据包D-E。

    如图11(c)，T2时间片中对等节点可以相互交换数据包而无需向服务器请求数据，最终得到图11(d)。

    综上，DNC算法花费3个时间片用于下载，从服务器处请求6次数据。尽管比NC算法多了一个时间片，但该算法解决了对等节点需接收到6个数据包后才能解码而造成的一些紧急片段的播放延时问题。

5 结束语
    本文综述网络编码在非实时P2P文件下载和实时P2P流媒体中的主要应用技术方法，尤其阐述网络编码在具有优先级要求的P2P流媒体中的应用。最后讨论研究方向。

• 网络编码在P2P QoS/QoE中的应用，利用网络编码来辅助提升QoS/QoE。
• 基于最小代价网络编码的P2P应用，以降低网络编码引入的编解码复杂性。
• 基于网络编码的P2P应用中的安全问题是P2P可持续发展的关键问题之一。
• 基于网络编码的P2P软件原型系统开发和基于Plantlab等实际网络上的仿真研究。例如，网络编码实现中的同步问题；

    具有拓扑意识的网络编码在P2P中应用，将拓扑意识加入到基于网络编码的P2P应用中，提升P2P传输效率；P2P流媒体中基于网络编码的Pull和Push相互结合的调度机制等。

6 参考文献
[1] YEUNG R W. Information theory and network coding[J]. New York, NY, USA: Springer. 2008.
[2] 黄佳庆，陶少国，熊志强，等. 网络编码关键理论问题研究[J]. 计算机应用研究. 2008, 25(8):2260-2264.
[3] 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.   
[4] CHOU P A, WU Y, JAIN K. Practical network coding [C] // Proceedings of 41st Annual Allerton Conference on Communication, Control, and Computing ,Oct 1-3,2003,Monticello, IL,JSA. Oct. 2003.
[5] GKANTSIDIS C, RODRIGUEZ P R. Network coding for large scale content distribution [C] // Proceedings of 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM’05): Vol 4, Mar 13-17, Miami, FL, USA. Piscataway, NJ, USA:IEEE, 2005: 2235-2245. 
[6] HALLOUSH M ,RADHA H. Network coding with multi-generation mixing [C] //Proceedings of, 42nd Annual Conference on Information Science and System (CISS’08), Mar 19-21, 2008, Princeton, NJ, USA. 2008:515-520.
[7] WANG M, LI B. Lava: A Reality Check of Network Coding in Peer-to-Peer Live Streaming [C] //Proceedings of 27th IEEE International Conference on Computer Communications (INFOCOM’07),Mar 6-12,2007, Anchorage, AK,USA., Piscataway, NJ,USA:IEEE,2007: 1082-1090.
[8] NGUYEN K, NGUYEN T, CHEUNG S. Peer-To-Peer Streaming with Hierarchical Network Coding [C] //Proceedings of IEEE International Conference on Multmedia and Expo(ICME’07) , Jul 2-5, 2007 Beijing,China.2007:396 - 399.
[9] 刘亚杰,窦文华. 基于网络编码的P2P 流媒体[J]. 计算机工程与科学, 2006, 28(19): 33-34, 38.
[10] WANG M, LI B. R2: Random push with random network coding in live peer-to-peer streaming[J]. IEEE Journal on Selected Areas in Communications, 2007, 25(9):1655-1666.
[11] CHI H, ZHANG Q. Deadline-aware network coding for video on demand service over P2P networks[J]. Journal of Zhejiang University: Science A, 2006, 7(5):755-763.

收稿日期：2008-11-07

[摘要] 网络编码是信息论领域的一个重要突破，它不同于信源编码和信道编码，将网络编码应用到P2P网络中是当前研究热点之一，其中具有分布式特点的随机网络编码可广泛应用于P2P网络。对具有非实时性的P2P文件下载应用，为降低随机网络编码引入的复杂性，可对文件分块进行分代，然后采用代内或代间网络编码技术。对具有实时性的P2P流媒体直播和点播，则需要采用具有优先级意识的网络编码技术，包括分层网络编码，或与推拉技术相结合来实现高效率的P2P流媒体分发。

[关键词] 网络编码；对等网；对等节点；P2P文件下载；P2P流媒体

[Abstract] Network coding, which differs from source coding and channel coding, is of great breakthrough on the area of information theory. One of the hot topics is to apply network coding for P2P networks. Random network coding which is distributed has been widely used in P2P networks. As for non-real-time P2P file downloading, in order to decrease the complexity induced by random network coding, generation technique that blocks of a file are grouped into generation is adopted and then intra- or inter-generation network coding is applied. As to real-time P2P live streaming and Video-on-demand, priority-aware network coding techniques, including hierarchical network coding or combination with pull-push methods, are taken to achieve high efficient P2P media streaming distribution.

[Keywords] network coding; peer-to-peer network; peer; P2P file downloading; P2P streaming