网络编码算法研究综述

网络编码算法研究综述

1. 引言

目前通信网络在各行各业已经显示出越来越重要的作用。但是与此同时由于网络使用者数量的骤增和网络服务需求和网络传输质量的多样化使得如何对网络进行优化从而最大限度地利用网络的现有资源成为当前研究者们所关注的重要问题。

网络编码起源于网络中的多播(组播,multicast) 问题。2000年Ahlswede 等根据网络信息流的概念在文献[1]中指出通过节点对数据包对来自不同链路的数据包进行组合发送(编码) 能够使得网络多播的容量确定性地达到最大流理论的极限(该极限被称作网络多播的最大流限) ，由于这一极限很难通过传统的多播路由机制来达到，因此网络编码的优点非常明显，同时它也有相应的缺点。

其主要优点[2]是提升多播网络吞吐量、改善网络负载均衡、节省网络带宽消耗、节省无线网络节点能量消耗、提高网络链路鲁棒性；主要缺点是因引入编/解码而复杂性高、因中间节点可以编/解码而存在安全问题。

2. 网络编码的基本概念与原理

2.1网络编码的基本概念

下面通过文献[1]中给出的蝶形网络为例来阐述网络编码能够达到网络多播的最大流限来描述网络编码的基本概念，如图1所示。图中所示的网络是一个无差错的传输系统，不考虑时延和传输差错。其中源节点S 准备将信息a 和b 发送到目的节点t 1和t 2，其余中间节点r 1到r 2均为路由节点。此外网络中的每一条边的容量为1，即每次只能传输一个信息。图1(a)中显示了传统的网络多播传输过程。由最大流最小割定理[3]很容易得出源节点S 到两个目的节点t 1和t 2的最大流分别为2。但是由于在链路r 3→r 4每次只能传输一个信息，因此待转发的信息

a 和b 中的一个必须在r 3处等待，从而目的节点t 1和t 2同时获得信息a 和b 的需求无法被满足。显然在该网络中传统的多播方式无法达到多播的最大流限。而由于使用网络编码的多播方案允许节点进行编码，r 3对a 和b 进行异或操作(编码) 并将编码结果a ⊕b 进行转发。这样目的节点t 1和t 2能够通过将各自接收到的信息进行异或操作(解码) 从而同时获得a 和b 。显而易见这种处理方式达到了网络

多播的最大流限。

(a) 传统的网络多播方式 (b) 使用网络编码的多播方式

图1 “蝴蝶网络”模型示意图

网络编码是从信息论的角度出发提出来的概念，它本质上打破了通信网络中传统的信息处理方式，已经成为通信网络研究领域中的一个研究热点。当前对网络网络编码的研究从形式上来划分可以分为下面的两大类[4]。

1. “数据流内”编码

进一步地来讨论图1(b)所示的示例。该例通过在中间节点r 3对信息a 和b 进行“混合”(编码) 从而达到了网络多播吞吐量的上限。由于参与编码的信息a 和b 同属于一条多播数据流，因此将这种编码类型称为“数据流内”(intra-session)的编码，即参与编码的信息属于同一的数据流的编码机制。“数据流内”编码起源于文献[1]所研究的多播网络编码，目前已经得到了迅速发展。

2. “数据流间”的编码

与“数据流内”编码相对应，“数据流间”(inter-session)的编码指参与编码的信息属于不同的数据流的编码机制。早期的“数据流间”的编码主要是针对非多播网络的编码机制，如本章的下一部分阐述的非线性编码。文献[4]引发了在无线网络上对“数据流间”编码的研究，即面向单播(unicast)传输的无线网络编码机制，目前其已经成为无线网络编码研究的主流。

需要说明的是上述对网络编码的划分仅基于编码所针对的网络需求(多播/非多播) 而言，并不针对某种特定的编码机制。比如所有多播网络中的线性编码方案为“数据流内”编码，而某些非多播网络中的线性编码方案为“数据流间”编码。

2.2网络编码的基本原理

1. 线性编码

在网络编码理论被提出之后，在一个网络中对信息进行怎样的操作才能够使得网络多播达到上限成为首先被考虑的问题。Li 、Yeung 和Cai 三人首次在文献

[5-6]中提出网络编码的线性编码方案(linear network coding)，证明了在运算所选取的有限域F q 足够大的前提下，只需要对传输的信息进行线性操作即可确定性地

使得多播传输达到上限值。但是如何进行线性编码仍然是一个需要考虑的问题。R.Koetter 和M.Medard 首先给出了一种可应用于任意网络拓扑的线性编码代数构造方式[7-8]。这种构造方式是已知整个网络的拓扑结构信息的情况下，使用一个关系矩阵M 来描述源节点的输入信息和接收节点所接收的信息之间的关系：M =A (I -F ) -1B T 。其中矩阵A 为源节点输入与边之间的关系矩阵，矩阵F 为网络中边与边之间的关系矩阵，矩阵B 为边与目的节点输出之间的关系矩阵。在这种方法中只要构造系统转移矩阵能够符合要求(矩阵满秩) 则该矩阵所表示的编码方案即可行。

与R.Koetter 和M.Medard 提出的线性编码的代数框架结构相对应，P.Sanders 等人基于图论提出了一种实现网络编码的多项式时间算法[9-10]。该方法同样需要己知网络拓扑的情况下对网络进行编码，通过最大流最小割算法寻找完成网络组播所需的路径来依次确定路径上各个路由节点的编码操作。这种方法有效地避免了冗余边上的编码过程，不但将编码的构造进一步简化而且大大降低了编码运算中基于的有限域的大小。

2. 随机编码

上面所提到的编码构造算法都是基于已知网络拓扑信息的确定性算法，在应用中具有一定的局限性。针对这个问题研究者们又提出了不需网络拓扑信息的随机网络编码算法[11-12]。在该算法中节点只需对来自不同链路的数据包进行随机的线性组合处理即可(即节点输出是输入的随机线性组合，组合的系数从一个有限域内随机选取) 。研究表明随着接收节点数量与编码运算基于的有限域大小的比值趋近于0时，该算法中接收节点能够成功解码的概率将趋近于1。

总的来看，集中式的网络编码算法[7-10]需要根据全局拓扑状况来给每个节点

分配线性编码系数。虽然这些方法使得编码运算所需的有限域不会太大，但是网络拓扑的变化将导致全部编码系数重新分配，因此可扩展性较差。虽然随机网络编码算法具有良好的拓扑适应性，但是这种方法实现正确无误的传输具有一定的概率性。

3. 非线性编码

线性编码已被证明可以确定性地达到任何一个多播网络的最大流限。但是线性编码在非多播网络中的性能将会是怎样，并没有一个确切的答案。文献[13]首先关注这一问题，证明了当编码运算基于的有限域为二元域时，存在着没有线性编码方案的多播网络。文献[13]通过一个实例证明了同样限定编码域为二元域时存在没有线性编码方案但有非线性编码方案的非多播网络，并首次探讨了使用非线性函数进行编码的可能性。文献[14]进一步地指出即使编码域的增加不足以使得所有非多播网络都存在线性编码方案。文献[15]将非线性编码分成两类，证明了存在着一类与线性编码等价的非线性编码。由于在非多播网络中构造达到其容量上限的编码方案非常复杂，因此对非线性编码的研究目前还处于起步阶段。

上面介绍的三种编码方法是进行网络编码的三种基本方式和原理，所有的网络编码实现都是以这三种编码方法来实现的。网络编码在应用研究方面主要分为在大型网络和无线网络中研究模拟实现。

3．网络编码的构造算法

网络编码构造算法主要是解决如何有效求得每条链路对应的编码向量，并运用该编码向量进行线性操作计算出链路上传输的信息向量，编码算法的发杂性是衡量网络编码能否有效实现的重要依据。总的来说，典型的集中式算法主要包括指数时间算法、多项式时间算法、贪婪算法等，其中因多项式时间有较低的复杂性，因此具有重要的理论和应用价值。同时还有基于分布式实现的随机算法RNC 。上述的典型算法都是网络编码应用的算法基础。

1. 指数时间算法

设M1,M2, „,M|T|表示LCM 种各个信宿节点对应的系统转移矩阵, 如果

det(M1)×det(M2)×⋯×det(M|T|)=p≠0, 则M1,M2, „,M|T|均满秩, 即所有的信宿节点均能成功译码。基于这种思想, Koeter R[16]等人给出线性网络编码代数框架的同时，提出了一种指数时间的网络编码构造算法: 设ξ1, ξ2，„ξn ，

n=|E|表示所有编码链路对应的编码向量，则必定存在函数关系：p=f(ξ1, ξ2，„ξn), 并称使p=0的点(ξ1, ξ2，„ξn) 的集合称为被“函数p 分割出来的代数簇”，因而算法的目标就是求得一个不位于“函数p 分割出来的代数簇”上的点。对于“单信源n 信宿”的无环有向网络，若LCM 的最大理论传输容量为h ，则在有限域Fq(q=2m ，m ≥log 2(nh+1))中，通过上述指数时间算法求得各链路对应的编码向量，

从而使信宿节点能成功译码。然而该算法参变量的校验次数随着网络规模成指数增加。因此, 该算法对于大规模的网络不够实用。

2. 多项式时间算法

P.Sander 等人提出另一个能够保证转移矩阵Mt= A(I-F)-1B T 满秩的集中式算法: 多项式时间算法[17]。该算法是线性网络编码的快速实现, 其目标是在尽可能小的有限域Fq 上快速地寻找编码向量。该算法首次将计算复杂性局限在多项式时间范围内, 极大提高了网络编码的实用性。

如果LCM 的最大理论传输容量为h, 将信源S 和信宿t ∈T 之间建立的h 条无重合链路构成的路径簇(S,t)记为f t , 对f t 上的链路按照拓扑排序, 排序后的链路可表示为e1,e2, „,en ,然后依次求解各链路对应的线性操作系数向量g e ，即全局编

码向量。在求解系数向量时, 必须保证对任意接收节点t ∈T 存在一个包含h 条链路的集合C t , 即是f t 中h 条路径上的最新构造出全局编码向量的h 条链路, 一条路径上

一条链路, 且这h 条链路的全局编码向量G t ={g(e)|e∈C t }是F h 的一个基。因此, 当

计算完成时,C t ∈T I (t),形成的G t 就是转移矩阵M t , 则信宿t 通过M t 就可以译出信源

发出的信息向量。

多项式时间算法的主要步骤包括:

(1) 构造信源S 至各个信宿节点t 的路径簇(S,t)；

(2) 将路径簇上的链路按照拓扑排序；

(3) 依次寻找各个链路的全局编码向量, 使得各路径簇。

(S,t)上最新链路的编码向量能够形成一个基，以此确保最终形成的转移矩阵满秩。此步为多项式时间算法的核心和重点。多项式时间网络编码算法的时间复杂度为O(|E|·|T|h2), 最坏情况下为O(|E|·|T|h(h+|T|2)) 。

3. 随机网络编码算法（RNC ）

虽然多项式时间算法能够有效地构造编码向量，确保信宿节点成功译码，但

由于它是集中式算法，需对网络拓扑结构有全面的了解。因此，从实用的角度来看，多项式时间算法对拓扑结构动态变化或规模很大的网络，实用性并不强。 为此M.Medard 提出了一种更一般的分布式网络编码的实现方法: 随机网络编码(Random Network Coding, 简称RNC) [18]，该方法基于一种随机选择编码向量的策略：对于除了信宿节点外的所有中间节点，只要在一个足够大的有限域F q 上随机选择它们输入链路到输出链路的映射，而且各节点映射关系的选取是相互独立的, 就能以较高概率使各个信宿节点对应的系统转移矩阵M t 满秩，即各信宿节点

能以较高的概率成功译码。图2表示的是随机网络编码, 各个链路上的系数向量(全局编码向量) 和信源发送的信息进行同步传输，各个系数向量ξ1, ξ2，„ξn 在有限域F q 中随机选取，在通过编码节点时，系数向量根据随机选取的映射关系

进行更新，最终的各信宿节点收到的输入信流。

图2 随机网络编码

在采用RNC 的线性编码多播中，多个信源可以是独立的，也可以是线性相关的。对于线性相关的信源，RNC 可以起到信息压缩的作用。此外，RNC 是网络编码的分布式实现，无需事先获知整个网络的拓扑信息，尤其适用于拓扑结构动态变化或者大规模的网络。对于存在网络节点和链路失效的网络，RNC 可以利用整个网络的剩余容量来获得网络的最佳容量，从而提高多播传输的鲁棒性。与时间多项式算法总能保证成功译码不同，在RNC 中，虽然不能确保最终形成的系统转移矩阵M t 满秩，但由于是随机选择编码向量，其复杂性与确定性算法相比要低得多，

更易于实现，而且99%以上的译码成功率在一般情况也足以满足需求。因此， 随机网络编码具有重要的理论价值和应用价值，得到了广泛的关注和应用。

4. 网络编码的应用

网络编码虽起源于多播传输, 主要是为解决多播传输中的最大流问题, 但是随着不断的深入研究, 网络编码与其它技术的结合也越来越受到人们的关注。下面将以无线网络、应用层多播和P2P 文件共享为例，介绍网络编码的几种典型应用以及它们的关键算法。

4.1 无线网络

由于无线链路的不可靠性和物理层广播特性，应用网络编码，可以解决多播吞吐量、减少数据包的传播次数从而降低无线发送能耗、增强网络的容错性和鲁棒性、提高网络的安全性等问题。网络编码主要应用在无线自组织网络、无线传感器网络和无线网状网中，下面将对这三个网络的编码算法进行分析介绍

4.1.1 无线自组织网络

无线自组织网络编码方案，以Ad-Hoc 网络为例，可分为线性和非线性两种, 其中线性方法的编码和解码都相对简单, 因此, 在应用中一般都倾向于采用线性方法。Li [19]指出在有向网络中, 如果一个网络编码问题有解, 则一定有线性解。从理论上保证了线性算法的有效性。

在Ad-Hoc 网络中，线性网络编码是将节点传送信息线性映射到一个有限域内, 利用线性关系实现编译码过程[20]。主要的思想是：假设每个信息数据包为L 比特, 当它与要组合的数据包长度不同时, 较短的信息附加额外一串“ 0”, 将包中的s 个连续比特组成域上的一个符号, 则一个包中包含L /s个符号。在线性编码下, 运用乘法和加法运算, 使从节点发送出去的数据为该节点接收到信息的线性组合。

根据上面的算法思想，线性网络编码的编码过程主要是：首先，假设一个源或多个源产生的原始数据包信息为M 1„M n ，则在线性网络编码中传输的数据可表示为(其中g1„gn 表示相应的编码系数) ，对每个符号有:Xk =∑i=1n g i M i k 。M k i 和X k 分别为M i 和X 的第k 个符号。传输的数据包中既包括编码向量, 又包括信息向量, 编码向量用于接收端的解码。在定义了一系列的信息后，在进行编码过程采用迭代的方法, 若一个节点已经接收和存储的包信息集合为(g1,X 1) …(gm ,X m ) ，则这个节点可以通过选定编码系数h 1… hm 和运用算式得到新的信息包(g',X),编码向量

g' 可以通过直接的代数计算得到，并且该过程可以在若干个节点中重复操作。

完成了编码的过程后，在节点处，还需要有解码的算法才可以使网络编码工

作起来。首先，假设节点接收集合为(g1,X 1) „(gm ,X m ) ，为了恢复原始信息, 需要求解{Xj =∑i=1n g i j M i k }的m 个等式中的n 个未知数M i ，恢复所有数据要求M ≥n, 也就是

说接收包的个数至少为原信息的个数。然后就可以进行解码，这需要求解一组线性方程。在实际应用中, 可以应用高斯消去的方法:当接收到一个已编码包后, 会从中抽取它的编码向量以及编码结果, 放入到解码矩阵中。解码矩阵会经过等价变换变成行阶梯型, 最终变成行最简型。当解码矩阵变换成最简型后, 方程组得解，这种情况发生在当接收到n 个线性独立的编码向量之后。

在得到编解码的算法后，还需要对编码进行组合，目前主要的方法主要可以分为确定性编码和随机编码。正如上面提到的网络编码构造算法，就是通过确定性编码和随机编码进行对编好的码进行网络编码的构造。

确定性的方法是基于整个无线Ad-Hoc 网络的拓扑结构，通过分析网络结构, 根据节点的输入输出个数设计相应的局部编码向量, 用迭代的方式得到全局编码向量, 从而实现网络编码Jaggi [21]等人提出了一种确定多项式- 时间的编码设计算法, 可以为特定的广播网络找到可行的网络编码, 目前已有对此算法的各种改进。确定性的编码方案由于每个节点应用的都是固定的编码向量, 因此网络中传递的数据中只需要包含信息向量, 节省带宽, 并且所需的符号集比较小; 但确定性的网络编码需要了解全网的情况, 复杂度比较高, 难于分布式地实现。一旦网络拓扑结构发生了变化, 就必须对整个编码方案进行修改, 鲁棒性比较差。

而随机编码则不需要基于已知的网络拓扑的基础上，它以完全独立的分布式方式随机选取编码系数, 对输入信息编码, 并把这组随机向量作为报头的一部分发送给收点, 以便于解码。已经证明, 当符号集为无穷大时, 采用随机编码, 系统传输矩阵满秩的概率为“1”。在实际工作中，Chou [22]应用随机编码, 提出了第一个实用的网络编码方案。为了保证随机编码成功概率, 编码向量的符号集必须足够大, 这可能会增加数据包头部的负担, 因此符号集的大小必须仔细选择。

4.1.2 无线传感器网络

相对于Ad-Hoc 网络，无线传感器网络密度较大，移动性不强，通常运行在无人值守的恶劣甚至危险的远程环境中，能源无法替代，设计有效的策略延长网络的生命周期成为无线传感器网络的核心问题。

为了解决上述的问题，无线传感器网络可以采用多路径的方式来保证数据传输的可靠性，并通过网络编码与多路径方式的结合，来实现高效的、安全的传输。要实现多路径传输的网络编码，首先要先引入多路径传输的概念，即在多路径数据传输中, 数据源节点根据应用的期望可靠性以及信道的状况选择将数据传输到所需的路径数。期望可靠性就是数据源产生的包被成功传输到采集点的概率；而到Sink 的路径数是这样定义的：平均跳步数为k ，信道失效率为e, 为达到期望可靠性r ，每份数据至少需要的路径数为N, 则有N=㏒(1-r)/ ㏒(1-(1-e)k ) （公式1）。

根据上面的多路径传输模型，就可以对这个网络进行网络编码。首先给出实用网络编码的基本思想[23]，它是将分组数据编码成多份相互无关的数据, 接收端只要能够收到其中的一部分, 就可以恢复出原始数据，具体产生的编码数据数量与应用的需求相关假定一组含有h 份报文，当节点要发送这些报文时，首先产生h 个随机数并组成h 维向量r 1，r 2，„，r h ，随后, 按向量(r1，r 2，„，r h ) 以及数据

块B 1，B 2，„，B h 的内容生成一个新的数据块E, 并且也按向量(r1，r 2，„，r h ) 及该组中的系数向量e 1,e 2, „,e h 生成一个新的系数向量α，α和E 的定义分别如

下：

E= r1 B1+ r2 B2+„+rh Bh （公式2）

α=r1 e1+ r2 e2+„+rh eh （公式3）

每次传输都需产生一组新的随机数除了数据源以外, 中间节点如果收到多份数据, 还可以再次编码。在Sink 中，假定收到的h 份数据分别是E 1，E 2，„，E h ，则进一步判断相应的h 个系数向量α1，α2，„，αh 是否线性无关, 即α1，α2，„，αh 所组成的h*h维矩阵是否为满秩的，如果是，则原始数据可按图3所示方式恢

复。

图3 原始数据恢复

有了上面的前期工作，下面就可以进行多路径中结合网络编码进行算法实现：

(1)对于源节点, 首先计算所需的路径数m, 并产生m 组随机数再用每组随机

数对组内原始数据和随机数按照公式2、公式3方式进行编码, 如图4所示, 分别产生m 份编码数据, 然后将编码数据沿m 条路径传输。

图4 源节点将数据编码成m 份新数据

(2)对于中间节点, 在给定的时间t 内检查所收到的编码数据, 假定数量为c ，则产生c 组随机数, 并按照公式2、公式3方式对编码数据进行再次编码, 进一步减少数据的相关性。

(3)对于sink 节点, 根据收到的报文数量Recvcnt 进行判断：

如果Recvcnt ≥h, 判断公式1对应的系数向量矩阵是否线性无关，或者公式2系数向量线性相关但满足秩大于或等于h, 如果是, 则按图3的方法恢复原始报文；

如果Recvcnt ≤h 或者Recvcnt ≥h 但对应的系数向量的秩小于h ，判断当前事件的数据是否满足期望可靠性r ，如果满足, 则丢弃这些报文；如果不满足，则sink 沿路径相反方向请求再次发送新的编码数据，要求新编码数据的系数向量和已有数据的系数向量线性无关。

这种网络编码的方式实现多路径传输，比传统的FEC(前向纠错编码) 更加灵活，而且鲁棒性更高。FEC 只允许在源节点编码，目标节点解码，而网络编码在中间节点也可以再编码和解码，这样，不仅提高了可靠性和灵活性，就算在中途丢包了，也能保证解出正确包的概率。此外网络编码采用了线性编码，编码数据只与产生的随机数有关，计算量很小，非常适合传感器资源受限的特点。

4.1.3 无线网状网

无线网络编码方案COPE 是一种提高无线网络单播传输吞吐量的有效方式，并且并不需要对当前无线网络路由设备的硬件进行改动，因此应用代价非常小。在

无线网状网，即无线mesh 网络中，十分关注网络的吞吐量，因此，COPE 对无线mesh 网络来说尤为适用。

COPE 对网络编码的基本思想进行了扩充，充分利用了无线网络的“广播”特性，要求节点独立地选取自己接口队列中的若干个数据包进行编码：异或操作，然后将编码包广播给参与编码数据包的下一跳节点。

在COPE 中，每个节点对传输媒体进行侦听来接收任何经过它的数据包，并通过它的邻居节点的状态信息来决定进行编码的机会。节点在自己的接口队列(即节点的数据包缓存队列) 中进行编码，然后进行路由。这种灵活的设计有效地减少了数据包缓存队列的长度，使得整个网络在网络流量剧增、或发送/接收节点动态变化而导致拥塞的情况下，仍然能够比较良好地工作。可以通过下图5中的典型实例来说明COPE 的原理。

(a) 初始情况 (b) 没有编码机会的路由选择 (c) 具有编码机会的路由选择

图5 COPE的典型实例

COPE 算法的本质是一种基于“机会”的方法，它要求节点自主地发现编码机会对数据包进行编码发送来来尝试减少包发送次数以达到提高网络吞吐量的目的，因此编码机会的数量与COPE 对网络吞吐量的提高直接相关。倘若无线网络的所有路由节点都没有编码机会，则COPE 的应用对网络吞吐量不会有任何的提高。因此，网络中COPE 的有效应用必须要有感知编码的无线路由协议对其支持。

由上面的原理可以知道，在无线网络编码方案COPE 中，最为关键的问题在于网络中的每个节点如何自主地判断自己接口队列中的哪些数据包能够进行编码，这里的能够编码暗含了编码包的每个接收节点能够正确解码。该问题可以转化为下面两个子问题：

(1) 节点如何判断自己接口队列中的任意两个数据包能否一起编码。

(2) 节点在获得发送机会时如何尽可能多地在自己的接口队列中寻找能够编码的数据包进行编码。

1. 编码判断

n 个数据包在节点v i 能够一起进行编码的充要条件：每个数据包p j 的下一跳节点nexthop (p j ) 都已经拥有和p j 一起进行编码的其余n -1个数据包。因此节点v i 判断它当前转发的任意两个数据包p j 和p k 能否一起进行编码的问题转化为v i 如何判断p j 的下一跳nexthop (p j ) 是否已经拥有数据包p k 的问题。

通常使用的是基于猜测的方法，即通过查看节点的位置和当前的状态来进行判断节点是否已经拥有某个数据包。在无线网络中节点nexthop (p j ) 获得数据包p k 一般分为两种方式：nexthop (p j ) 转发过p k 或者nexthop (p j ) 侦听到某个节点转发p k 的过程。因此在猜测法中只要能够确定满足上面的两个判断条件之一就认为节点已经获得了数据包。所以在进行编码判断时基本的做法是：

Step1：首先查看nexthop (p j ) 发送的接收报告中是否含有p k 的信息，如果有则返回成功；否则继续Step2。

Step2：采用猜测法来进行进一步判断。

2. 编码数据包的选择

首先将节点接口队列中的数据包对应到一个无向图(G, E)上：

(1) 每个数据包p i 对应图中的点v i ；

(2) 若两个数据包p i 和p j 的下一跳节点都已经分别拥有p j 和p i ，则存在一

条无向边e i j =(v i , v j ) ∈E 。

通过这种对应关系，寻找最多的参与编码数据包就被转化为寻找图(G,E)的最大团问题上。算法的思想是首先寻找与队首数据包p 对应的点v 相邻的点构成的图Neighbor 。之后选出图Neighbor 中邻居节点数目最多的点v max 将其加入到集合

GoodClique 中，并删掉图Neighbor 中与v max 不相邻的点以及相应的边，重复选择

v max 直到图Neighbor 为空为止。集合GoodClique 中点对应的数据包就是就得到的

参与编码的数据包。当节点接口队列中有n 个数据包时，该算法的复杂度为O(n) 。

上述算法是一种典型的“贪心”方法。由于节点接口队列中任意两个数据包之间的关系特性(构造出的图为稀疏图) ，因此该算法能够很好地适用于参与编码数据包的选择。

在解码组件中，有与编码算法相对应的从编码包中恢复出数据包的解码算法。该算法要求节点利用自己已经获得的数据包尝试对编码包解码来恢复自己所3

需要的那个数据包。若节点当前拥有m 个数据包，且接收到的编码包由n 个数据包编码而成，则该算法的复杂度为O(n*m)。

4.2 应用层多播

虽然网络层多播(Network Layer Multicast)被认为是提供一到多或者多对多服务的最佳方式，但是由于技术上和非技术上的原因导致网络层多播并没有在目前的Internet 上得到广泛的实现。但由于应用层多播利用的覆盖网络的拓扑不如物理层那样固定，可以按需变化，这也恰好可以利用网络编码对动态网络适应性强的优势，为此，在应用层的多播上面，网络编码也有着深层的应用意义。

Y.Zhu 给出了一个基于网络编码的应用层LCM 的完整实现[24]，其算法实现过程主要包含两个步骤:

(1)首先构造包含所有覆盖节点的“基本图”, 然后在“基本图”的基础上构造“基本树”, 最后通过基础树构造“2 冗余网络多播图”。拓扑结构符合“2 冗余网络多播图”的覆盖网络, 其所有覆盖节点的入度或出度均不超过2。

(2)由于“2 冗余网络多播图”拓扑结构较为简单, 可以方面的使用线性网络编码。

通过对网络层多播, 普通应用层多播和应用层LCM 的各种传输性能进行了对比测试, 结果表明应用层LCM 在网络吞吐量、资源利用率等方面的性能要优于网络层多播和普通应用层多播。但是在传输迟延和信息冗余等方面不够理想。大多数情况下，应用层LCM 较普通应用层多播，其吞吐量可以提升一倍。

4.3 P2P网络文件共享

随着网络技术的发展，P2P 应用占据了互联网上70%以上的网络流量[25]。特别是BT(Bit Torrent 的简称) 的出现，使得P2P 应用越来越广泛。但是由于人们对信息共享效率与下载速度的无止境追求，使得现有P2P 越来越难以满足人们的需求，特别是由于BT 容易造成带宽吞噬，使得网络环境变得拥塞不堪，而且由于存在“死档”，导致传输质量的下降。网络编码的出现，有助于从内部机制上改善P2P 的传输效率，提升其性能。

P2P 应用的典型代表是微软公司开发的基于随机网络编码(RNC)的P2P 文件下载系统Avalanche [26]，其原理(如图6) 是：假设服务器需要传输文件给对等节点A ，则首先将服务器上的文件分解成n 个文件块，即B 1,B 2„B n ，然后应用随机网络编

码，随机选择系数c 1，c 2„c n ，将线性网络编码后的组合块E1=c1B 1+c2B 2„c n B n 传送给对等节点A ，假设对等节点A 又收到另外一个已经过编码的组合块

E2=c1'B 1+c2'B 2„c n 'B n ，该组合块来自其它对等节点或者服务器。然后对等节点A

再随机选择编码系数c 1″、c 2″，对E 1和E 2进行线性操作，将操作的结果E3=c1″E 1+c2″E 2发送给对等节点B ，如此则对等节点B 又传送给其它的对等节点。只要每

一个对等节点收到足够多的线性无关组合，就可以通过解线性方程组译出原始文件块。

图6 Avalanche的工作原理

Avalanche 是第一次将网络编码应用于P2P 的原型系统，开创了将网络编码与P2P 应用相结合的先河，具有很高的参考价值。

4.4 安全网络编码

网络安全问题是现代网络一个新兴的热点问题，由于网络编码能对网络的安全性进行提高，因此网络编码在安全方面的应用也吸引了一些敏锐研究者的目光, 可以预见, 对无线网络编码在安全方面的研究会是将来的一个研究热点。

网络通信中，按照攻击者的攻击方式，攻击主要分为以下两种：搭线窃听(被动攻击) 和Byzantine 攻击(主动攻击) 。传统的密码学方法存在一定的局限性，如计算复杂度较大，数据传输速率较低，消息冗余较大等，因此需要寻找一些安全、高效的数据传输方式，基于网络编码的网络安全防御方式诞生了。

在近来的研究中，抗搭线窃听的安全网络编码是研究的热点，蔡宁和杨伟豪首先在文献[27]中论述了网络编码在安全方面的应用，最先研究了单源无圈网络中数据的安全多播问题，给出了搭线窃听的网络通信模型（CSWN ）。并且构造了窃听者无论窃听给定的窃听集集合中的哪个窃听集都无法恢复出原始信息，在信

息论意义下安全的网络编码。

搭线窃听网络(CSWN)的模型包含5个组成部分：

(1)有限有向无圈图G =(V,E ) ，其中V 是节点集，E 是边集，两节点间可以有多条有向边。

(2)信源节点集S ：每个信源节点s 以一定的速率随机生成取值于字母表M 的随机信息m s 。

(3)信宿节点集T ：每个信宿节点t 是可以无差错地恢复出某些信源发出的随机信息ms 的合法用户。

(4)搭线窃听集的集合Λ，Λ为边集E 的子集的集合：Λ中每个元素称为搭线窃听集合，每个搭线窃听的集合中的边可以被窃听者窃取到所传输的所有信息，但是窃听者所能窃听的所有边不能同时在多于一个窃听集合中。

(5)边的容量R =[R(a,b)：(a,b)∈E]，R (a,b)表示(a,b)边上可传输最大平均速率。

五元组(G、S 、T 、Λ、R ) 为一个搭线窃听网络(CSWN)。对于一个CSWN ，通信者知道窃听者的窃听集合Λ，但不知道Λ中的哪一个元素是搭线窃听集合。通信者的目的是以尽可能大的速率将信息从信源节点集S 传输到信宿节点集T ，而且使得窃听者从搭线窃听集Λ中得不到任何信息m s ，s ∈S 。在一个CSWN 中，我们一

般还假设窃听者知道通信者的编码策略，而且还可以尽可能地根据自己的知识和经验来选择搭线窃听集。要想达到上面的安全传输信息的目的，一般而言，通信者必须将要传输的信息m s 随机化。令W 为独立随机变量集，其中的随机变量在指

标集w 中一致分布。

根据上面搭线窃听网络(CSWN)模型的建立和网络通信的一些规定假设，我们可构造出抗搭线窃听的安全网络编码：

(1)选择合适的正整数n 和r ，其中r

q 中随机选取(不一定是

均匀分布) ，独立的随机密钥K 在域F q 上均匀分布，多播的信息是(m,k)，其中m

是要保密的信息，k ∈K 是密钥，m 和k 都在源节点处生成，且令X=(M,K)。

(2)选择域F n

q 上合适的n 维线性网络编码。

(3)在每条信道e 上将传输的信息X 编码为Xf e ，其中f e 是信道e 上全局编码核。

通过上述的过程，就可以根据CSWN 网络的模型，建立出一种抗搭线窃听的安全网络编码，它是一种充分的可容许码，在任一信道都被搭线窃听的情形下都是r

安全的，更重要的是它同时达到了网络的最大容量。

5. 网路编码未来研究方向

经过几年的快速发展，基于网络编码的新理论和新应用不断涌现，可以说， 网络编码正给现有网络带来革命性的变化。但从研究的深度来看，仍处于探索阶段，还存在一些尚未解决的问题或者尚未探索的领域。

5.1 多源网络编码研究

目前网络编码的研究基本上局限于单源多播(Single 2Source Multicast) , 对于多源多播(Multi 2Source Multicast) , 特别是对于信源数目大于2的网络编码多播，研究不够充分。多源多播是普遍存在的，如多方会议、网络游戏、协同工作等都是多源多播技术在实际生活和工作中的体现，因此研究多源网络编码有重要的实际意义。

5.2 非线性网络编码研究

虽然线性网络编码能够实现多播传输的理论最大流，并提出了几种实现LCM 的有效方法，如时间多项式算法和随机网络编码，但非线性网络编码的性能特征究竟如何，目前在这方面的研究还没有起步。一般而言，非线性编码无论是从系统建模，还是算法求解等方面，均表现出较高的要求和难度。非线性网络编码以及其延伸的应用也必然是未来的研究方向之一。

5.3 网络编码的具体实现

现在已经提出了很多网络编码方法，有集中式线性网络编码、分布式随机网络编码, 但是要在实际网络环境中实现网络编码，需要考虑诸如同步、线性独立的编码系数选择、开销控制等问题。网络编码在实际网络环境(包括有线和无线) 中如何实现是一个很迫切的问题，也是网络编码研究的最终目的和归宿. 因此, 网络编码的具体实现也是很有意义的研究方向。

5.4 降低网络编码的复杂性

采用网络编码可以在很大程度上提高网络性能，但设计和实现上的复杂性也随之增加，如何在不显著增加网络开销的情况下，综合考虑效率和性能，如何实现最小代价的网络编码等问题是将来需要进行深入研究的方向。研究降低网络编码的复杂性，实现最小的代价的网络编码，具有重要的理论意义和实用价值。

参考文献

[1]Ahlswede R, Cai N, Li S,etal. Network information flow. IEEE Transactions on Information Theory,2000,vol.46(4):1204-1216.

[2]康巧燕, 孟相如, 王建峰. 网络编码对组播通信的性能改善[J].计算机工程与应用, 2007, 43(3):1502152,163.

[3]Ford L R, Fulkerson D R. Maximal flow through a network. Canadian Journal of Mathematics, 1956, vol.8: 399-404.

[4]Katti S, Rahul H, Hu W, et al. XORs in the air: practical wireless network coding. IEEE/ACM Transactions on Networking, 2008, Vol.16: 497-510.

[5]Li S.Y.R, Yeung R.W, Cai N. Linear network coding. IEEE Transactions on Information Theory, 2003, vol.49 (2): 371-381.

[6]Li S.Y.R, Cai N and Yeung R.W. On theory of linear network coding [C]. International Symposium on Information Theory (ISIT 2005), 2005, 273-277.

[7]Koetter R, Medard M. Beyond routing: an algebraic approach to network coding [C].

st The 21 IEEE Conference on Computer Communications (INFOCOM 2002), 2002.

[8]Koetter R, Medard M. An algebraic approach to network coding. IEEE/ACM Transactions on Networking, 2003, vol.11(5): 782-795.

[9]Snaders P, Egner S, Tolhuizen L. Polynomial time algorithms of network

th information flow [C]. The 15 ACM symposium on parallel Algorithms and Architecture,

2003, 286-293.

[10]Jaggi S, Sander P, Chou P, et al. Polynomial time algorithms of network code construction. IEEE Transactions on Information Theory, 2005, vol.51(6): 1973- 1982.

[11]Ho T, Koetter R, Medard M, et al. The benefits of coding over routing in a randomized setting [C]. The IEEE International Symposium on Information Theory (ISIT 2003), 2003.

[12]Ho T, Koetter R, Medard M, et al. A random linear network coding approach to multicast. IEEE Transactions on Information Theory, 2006, vol.52 (10): 4413-4430.

[13]Dougherty R, Freiling C, Zeger K. Linearity and solvability inmulticast networks. IEEE Transactions on Information Theory, 2004, vol. 50(10): 2243-2256.

[14]Dougherty R, Freiling C, Zeger K. Insufficiency of linear coding in network information flow. IEEE Transactions on Information Theory, 2005, 51(8): 2745-2759.

[15]Li L X, Fan K, Long D Y. Nonlinear network coding: a case study [C]. The IAENG International Conference on Communication Systems and Applications (IMECS 2008).2008, 1105-1108

[16]Koeter R, M edardM. A n algebraic app roach to netwo rk coding[J]. IEEEöA CM T rans. N etwo rk ing, 2003, 11 (5) : 7822795

[17]Sanders P, Egner S, To lhuizen L. Po lynom ial time algo rithm s

fo r netwo rk info rmation flow [C]. In: P roc. 15th ACM Sympo2

sium on Parallel A lgo rithm s and A rch itectures, 2003.

[18]Ho T, KargerD, M edardM , et al. The benefits of coding overrouting in a random ized setting[C]. IEEE International Sympo2sium on Info rmation Theo ry, Yokohama, J apanp. 442, June,2003.

[19]Li S Y R, Yeung R W, Cai N. Linear networkcoding [J]. IEEE Transactions on InformationTheory, 2003, 49: 371- 379.

[20]Chris tina Fragouli, Jean- Yves Le Boudec,Jorg Widmer. Network coding: an ins tantPrimer [J]. IEEE Transactions on InformationTheory, 2002, 48: 271- 277.

[21]Jaggi S, Sanders P, Chou P A, Effros M,Egner S, Jain K, Tolhuizen L. Polynomial timealgorithms for multicas t network codecons truction [J]. IEEE Transactions onInformation Theory, 2003, 49: 831- 836.

[22]Chou P A, Wu Y, Jain K. Practical networkcoding [J]. Allerton Conference onCommunication, Control, and Computing,Monticello, IL, 2000,(10).

[23]Chou PA,Wu YN,Jain K.Practical network coding.In:Proc.of the 41st Annual Allerton Conf.on Communication Control and Computing.2003.

[24]Zhu Ying, L i Bao2chun, Guo J iang. M ulticast w ith netwo rk

coding in app lication2layer overlay netwo rk s[J]. Selected A reas

in Communications, IEEE Journal, J an. 2004, 22 (1) : 1072120.

[25]Cohen B. Incentives build robustness in bitto rrent [Z]. In P2P

Econo rnicsWo rk shop, Berkeley, CA. 2003.

[26]GKANTSIDIS C, RODRIGUEZ P R. Networkcoding for large scale content distribution

[C]//Proceedings of 24th Annual Joint Conference ofthe IEEE Computer and

CommunicationsSocieties (INFOCOM’05): Vol 4, Mar13-17,Miami, FL, USA. Piscataway, NJ, USA:IEEE,2005: 2235-2245.

[27]CAI N, YEUNG R W. Secure network coding[C]//Proceedings of 2002 IEEE InternationalSymposium on Information Theory (ISIT2002), Jun 30-Jul 5, 2002, Lausanne,Switzerland. Los Alamitis, CA,USA: IEEE