摘  要: 介绍了网络编码的概念，分析了网络编码的原理及其特点。着重关注了网络编码的具体应用，包括文件下载、无线环境、分布式存储等方面。评述了网络编码的最新研究进展，并对其发展趋势进行了展望。
关键词: 网络编码； P2P下载； 分布式存储； 无线网络

    根据最大流最小割定理，通信网中端到端的最大信息流是由网络有向图的最小切割决定的。但目前网络中无法达到这一理论的上界，这是因为在网络中信息以“流”的方式来处理，原则上一个通信“管道”一次只允许传输一个“流”。传统的观念中，认为在中间节点对信息进行处理于信息传输本身没有任何好处。然而，Ahlswede等人于2000年提出了网络编码的概念[1]，推翻了上述结论。所谓网络编码，是指中间节点不仅仅是简单的存储转发，还可以对信息进行一定的处理融合，增加单次传输的信息量，提高网络的性能。网络编码融合了编码和路由的概念，给现有的网络带来了革命性的变化，给网络结构、路由的设计带来了新的设计思路。
1 网络编码的概念
    最初提出网络编码是用来解决网络中组播的最大流问题，即给定一个通信网络，以G(V，E)来表示，G是一个有向无环图。在组播通信中，需要一个信源S∈V和一组信宿T∈V。要实现组播通信，传统的路由方式是建立一个或多个组播树,即建立一棵以发送者为根节点、连接所有接收者的多播分发树，所要传输的信息就在这些事先选好的路径上传输。所以建立组播树是实现组播的关键，但是一般认为组播树的建立是一个NP问题。通常只是求出其近似解，先采用最大流算法找到信源S与一个信宿T1的最大流路径，然后再依次寻找与下个信宿T2之间的最大流路径，这时通常会在原通信网络中去掉与T1之间已经用过的链路的容量。这样处理是因为传统路由认为网络中传输的信息是不能叠加的，只能存储转发。这样的组播树的建立方式就会导致信源S与信宿T2后面的信宿建立的路径都不是以它们之间的最大流进行传输的。而网络编码的提出就是为了解决这个问题，以实现由最大流最小割定理给定的一个通信网络的容量上限。为了进一步说明网络编码的原理，下面给出一个经典的例子。如图1所示，在这个蝶式网络中，每个边代表一个直接链路，每次可以可靠地传输一个包。源端S有2个包b1和b2，想要都发送给t1和t2。在如图1(a)所示的传统路由模式中，中间节点只能对接收到的数据包复制和转发，即3到4的链路每次只能传输b1或者b2，这条链路不得不使用2次才能达到目的，节点t1和t2最后一共收到3个包,平均速率为1.5个包/单位时间；图1(b)中采用了网络编码，节点3对数据报进行了异或处理，将处理后的数据包转发出去，这样一次传输就可以将b1⊕b2传到节点4，由于t1和t2已经接收到了b1和b2,所以再次进行异或操作便可以得到b2和b1。这样所能达到的平均速率为2个包/单位时间。从这个例子可以清楚地看到，网络编码能够提高网络吞吐量，保证负载均衡，减少传输次数，缩短网络延时。

    网络编码主要分为以下几种类型[2]：如果网络中所有节点对其输入信息进行线性操作，则称之为线性网络编码，反之为非线性编码；同样如果网络节点对信息进行操作的系数是随机选取的，则为随机网络编码，否则为确定网络编码。
2 网络编码的优缺点
    网络编码最初是用来解决网络中组播的最大流问题，从而提高组播的吞吐量。随着研究的深入，其他方面的优点也逐渐体现出来。
    (1) 提升网络吞吐量。吞吐量的提升是网络编码的主要优点，可以在一条链路上同时传送多个信息流，提高了链路的利用率。无论是多播还是单播，均匀链路还是非均匀链路，都能提升其吞吐量。
    (2) 减小传输能耗。在无线网络中,应用网络编码可以减小节点的能耗。以广播代替单播，减少发送的次数，这在无线传感器网络中有重要的应用。
    (3) 均衡网络负载。网络编码可以有效地利用空闲路径，将网络流量分布到更广泛的网络上，进行均衡网络负载。这有助于解决网络拥塞等问题。
    网络编码还具有鲁棒性、自适应性、增加传输的安全性等优点。但是，由于网络编码增加了中间节点的计算复杂性，且信息的恢复需要收到足够的包，因此网络编码增加了传输时延、节点的额外资源消耗以及信息的同步问题。这对网络编码的应用提出了挑战。
3 网络编码的应用
    网络编码的理论提出来已经有一段时间了，随着研究的不断深入,从有线到无线已经有了一些具体的应用，下面对网络编码的几种典型应用进行介绍。
3.1 P2P下载
  

　　还有其他应用如Coded Multicast和LION等方案[3-4]，Coded Multicast通过构建多播组,每个接收者建立2条不相交的路径到发送者，形成一个冗余的Overlay结构，利用网络编码在这个Overlay上传送数据，从而提高了多播组的吞吐率。LION考虑了P2P网络中不同节点的带宽不同，在节点中建立多个Overlay的mesh结构，发送者将分层的数据发送到对应的节点，每个节点根据自己的可用带宽加入不同数量的mesh，从而提高吞吐率。
3.2 分布式存储
    网络编码也可以用到分布式存储上。Acedanski[5]等人研究了一个网络分布式系统中在受限的存储资源上存储一个或多个大文件的问题。每个存储位置选择一个文件的一部分，而不关心这个文件存放在哪里，希望文件下载器能够尽可能少地链接存储器而取得整个文件。对比无编码存储和基于传统纠删编码的存储和基于随机线性编码的存储三种策略,其仿真结果表明基于随机线性码的分布式存储策略在无需全局文件服务器参与时,其性能接近集中式全局调度算法。而传统的基于纠删编码则需要中心服务器占据大量的附加存储空间才能完成参数的恰当选择。
3.3 无线网络
    网络编码更加适合于无线网络，在无线网络中物理信道的广播特性更能发挥网络编码的优势。下面介绍当前流行的几种无线网络中应用网络编码的方法。
3.3.1 无线网状网
    Katti等提出的基于机会的网络编码方法(COPE)首次研究了网络编码在无线环境中的协议层面上具体实现的问题[6]。在COPE 中, 每个节点编码组合数据后, 进行基于机会的路由。COPE的主要思想是节点首先对传输信道进行侦听,获取其邻居的相关信息，决定进行编码的机会，并在本地的先入先出FIFO(First Input First Output)缓存结构内进行编码，然后进行基于机会的路由。COPE协议要求每个节点利用本地信息各自决定哪些数据包需要进行编码以及如何进行编码。若节点Vi的发送队列中的k个数据分组p1,p2,…,pk能一起编码，构造一个能被下一跳节点正确解码的数据分组，则必须满足以下解码条件：每个参与编码的数据分组pj的下一跳节点Vj都获得除pj之外的其他参与编码的数据分组。
    覃团发等由此提出了一种基于网络编码的无线Mesh路由协议，应用马尔科夫链模型，定义了网络编码感知的路由判据[7]。代替了传统的期望传输次数(ETX)、期望传输时间(ETT)等判据，引入了COPE中的期望资源消耗(ERC)判据，每个节点都维护着一个链路缓存用来存储链路的ERC信息。一旦链路的ERC信息发生变化，节点重新计算到达其他节点的最优路径。网络中的节点根据这一判据作出路由选择，能增加网络编码机会，降低网络资源消耗，最大化网络编码效率。
3.3.2 无线自组织网络
    无线自组网(Ad-Hoc)是近年来研究较多的一种无线网络，节点采用对等的、自配置的方式快速组网，具有灵活性高、成本低等特点。但是也有终端受限、带宽不足等问题。为了解决Ad-Hoc中的网络吞吐量问题，J.Yuan提出了一种利用网络编码优化的流路由方法，以此来提升Ad-Hoc网络的多播吞吐量[8]。该方法基于一种在网络层和物理层平衡链路带宽供需的跨层优化策略。J.Yuan等把该问题分解为2个子问题：(1)优化网络层的多跳路由；(2)优化物理层能量分配。他们提出的是一种跨层优化的策略，该策略分别在网络层和物理层平衡链路带宽的供需，在这种平衡状态上，提供了利用网络编码优化吞吐量的流路由方法。运用网络编码可以在很大程度上提高网络吞吐量，但是不可避免地会增加网络的复杂性。
3.3.3 无线传感器网络
    由于无线传感器网络以数据为中心，非常适合采用网络编码来发挥其优势。MIT 的Petrovic等人提出了一种结合网络编码的、对无线信号不进行调制的策略[9]。运用随机分布式网络编码，无线信号可以不经过调制直接进行传输且可以达到经过调制后的吞吐量。这样就能节省大量因为调制而消耗的能量，且可以降低节点的成本。不足之处在于为了防止未经调制的无线窄带信号可能使节点之间出现不能互相通信的情况，所以要求传感器网络保证一定的节点密度。
    采用网络编码能获得网络组播的最大流限，特别是在带宽受限的WSNs中，网络编码对于增大数据流可以达到理论上限。在WSNs中,数据是通过一跳或者多跳传输到目的(sink)节点，网络编码充分利用了无线信道传输的特性,极大地提高了网络的吞吐量。网络编码还可以提高数据的正确率，在一定数据包受损的情况下，能够通过解码还原，因此减小了重传的次数，从而降低了能耗,提高了系统的容错性和鲁棒性。
3.4 其他应用
    网络编码还可以应用到其他网络环境中，如应用层多播、网络安全等。应用层多播是指把多播服务从网络层转移到应用层作为应用层服务实现。网络层的多播信息流由路由器转发，而在应用层多播中则由端主机转发，端主机具有一定的计算能力，这为网络编码提供了良好的环境。网络编码还可以应用到信息加密中，由于信息本身就是经过编码转换的，因此可以节省额外的加密操作，攻击者在没有得到所有编码信息的前提下，无法还原出原始信息,这为设计新的加密算法提供了新的方法。
    网络编码是一个较新的研究领域，它的提出，颠覆了人们对网络传输流认识上的禁锢。越来越多的研究者已经被吸引到这一领域来，理论上的完善和实际应用的探究都取得了一定的进展，线性编码和非线性编码已经在数学上得到了证明，编码时域大小的确定，编码方案的选择也被广泛关注。在无线Mesh网络中，已经有了具体的应用网络编码的算法COPE，并且在此基础上不断地被改进。在P2P文件传输中也不断地涌现出新的网络编码的应用方案，此外，在网络安全中，网络编码也有用武之地，可以利用信息本身来进行加密，可以有效地提高加密的效率。总之，网络编码必将对未来网络的设计产生深远的影响。
    本文主要介绍了网络编码的理论背景以及网络编码的应用方式。总结了网络编码的优缺点，对当前的一些网络编码在应用方案作了介绍和探讨。网络编码在以下几个方面将有进一步研究：网络编码在多径、多源环境下的应用，与其他领域的技术相结合(如编码与分布式压缩等)以及如何降低编码复杂度、提高编码效率等。
参考文献
[1]     AHLSWEDE R, CAI N, LI S R, et al. Network information flow[J].IEEE Transactions on Information Theory,2000.
[2]     黄佳庆, 王帅, 陈文清.网络编码在P2P网络中的应用[J].中兴通讯技术,2009,15(1):37-39.
[3]    ZHU Ying, LI Bao Chun, GUO Jiang. Multicast with network coding in application layer overlay networks[J]. IEEE    Journal of Selected Arears in Communications. 2004, 22(1):107-119.
[4]     ZHAO Jin, YANG Fan, ZHANG Qian, et al.LION:layered overlay multicast with network coding[C]. IEEE Transactions on Multimedia. 2006,8(5):1021-1025.
[5]     ACEDANSKI S, DEB S, MEDARD M, et al. How good  is random linear coding based distributed network storage[C]. The 1st Workshop on Network Coding, Theoryand Applications. 2005.
[6]    KATTI S, KATABI D, WENDJUN H, et al. The importance of being opportunistic: Practical network coding for  wireless environments[C]. 43rd Annual Allert on Conference on Communication, Control and Computing. Monticello: University of Illinois, 2005:134-144.
[7]     覃团发， 廖素芸，罗会平.支持网络编码的无线Mesh网络路由协议[J].北京邮电大学学报，2009，32(1)：16-18.
[8]     YUAN Jun, LI Zong Peng, YU Wei, et al. A cross-layer  optimization framework for multicast in multi-hop wireless networks[C]. Proc. of First International Conference of  Wireless Internet(WICON),Budapest,Hungary,2005:47-54.
[9] PETROVIC D, RAMCHANDRAN K, RABAEY J. Coding  for sensor networks using untuned radios[C]. IEEE 6th Workshop on Signal Processing Advances in Wireless  Communications, 2005:1093-1097.