无线自组织网络的网络编码技术

摘要：网络编码作为一种新的技术在宽带无线自组织网络中有很好的应用，通过网络编码，中间节点可以将接收信息进行编码并发送出去，提高了网络吞吐量和健壮性。为不对现有网络的软硬件设备和相应的协议做很大的修改，可以选择在高层实现网络编码。无线传感器网络、无线格状网(Mesh)等无线自组织网络都可以使用网络编码技术显著提高多跳链路的传输性能。目前网络编码的研究热点集中在网络编码节点选取方案、网络编码算法的设计、网络编码复杂度分析、网络编码的性能分析、网络编码与系统安全性分析、网络编码在无线分布式网络中的应用等方面。

关键词：无线自组织网络；协同；网络编码

Abstract:The network coding, as a novel technology, will have a good application in the broadband wireless self-organized network. The relay node will decode and forward the relaying message via the network coding technology, which will improve the network throughput and enhance the robustness. In order to decrease the modification on the software, hardware and corresponding protocols in the current network, the network coding technique shall be adopted at the upper layer. Actually, the network coding is utilized to improve transmission performances of the multi-hop link in both the wireless sensor and the Mesh network. The current research interest related to the network coding technique focuses on the node selection, coding algorithm design, coding complexity evaluation, coding performance analysis, coding safety mechanism, and the application in the wireless distributed network.

Key words:wireless self-organized network; cooperative; network coding

基金项目：国家“863”计划项目(2006AA01Z257)；国家自然科学基金项目(60602058)

宽带无线多跳通信系统的设计目标是在充分利用有限的无线网络资源的前提下，使各接收节点能快速收到完整信息。如何提高多跳自组织无线网络的性能，一直是业界研究和关注的重点[1]。

1 网络编码技术原理

网络编码(Network coding)从广义上来讲，是网络中的节点将接收到的信息进行编码后再转发出去的多点传送(Multicast)技术。多点传送(也称组播)是网络中的一种重要的通信方式。当一个或几个节点同时向若干个其他节点发送数据时，往往要借助其他节点的传递。

在传统的网络中，作为中继的节点只能对接收到的信号进行复制、放大和转发，这对于网络资源有时候是一种浪费。网络编码技术打破了这种限制，它允许中继节点对接收到的信息进行编码，并将接收到的多个数据包按照某种特定算法重新组合再发送出去。

图1所示为一无线通信领域3节点拓扑的实例：节点A、节点B相互传递信息a、b。图1中的箭头代表有向链路，假设每条链路的容量为“1”。图1(a)采用传统的通信方式，A首先向S发送信息a，然后B向S发送信息b，S然后依次把信息a和b分别广播给节点A和节点B。这样经过4条链路的传输节点B可以获得信息a，而节点A可以获得信息b 。但是当信息a和b准备通过节点S进行转发时，如果应用网络编码技术，将a和b作模2和运算后直接转发出去，则在节点B处，根据接收到的信息可恢复出a来；同理，在节点A处也可以恢复出信息b来，从而可以译码得到信息b。采用了网络编码技术后(见图1(b))，只需要使用3条链路就可以实现传统方式的所有通信要求。

从实例可以看出，网络编码技术可以显著地提高多点传送的数据率。在一个网络中传递的信息，可以形象的称之为“流”。网络的最大流量即为从源点到收点的最大传输数据率。而广播的最大流量是指源点同时向所有收点发送同样数据时，每个收点能接收到的最大数据传输速率。理论上讲，最大流取决于网络的拓扑结构，即各节点的连接关系和带宽。利用图论中著名的最大流最小割定理可以得到给定网络中某个源点到收点的最大流[2]。

最大流最小割定理：任何带发点和收点的网络中都存在最大流和最小割，并且最大流的流值等于最小割的容量。

从图1还可以看出，一个容许的网络编码方案，必须使得收点能够从接收到的数据中恢复出原始信息，也就是说，根据接收到的数据，和已知的编码方案，可以唯一地解出原始的数据。如果把整个网络看作一个系统，源点发送的数据可以视为系统的输入，收点接收到的数据作为输出，中间每个编码节点的操作作为系统函数，则要求从源点到每个收点之间的信息传输矩阵满秩，才能够满足广播的要求。

数据在经过中间网络时，可能经过多次编码。一个节点如果自身不是源点，那么它发出的信息只能来源于收到的信息。因此无论怎样编码，它发出的信息量必然小于等于收到的信息量。从信息论的角度讲，数据在传输过程中每经过一个节点，其信息熵都是非增的。所以，为了保证最后传到收点处的信息熵不降低，就要求每一个中间节点在编码时，系统的传输矩阵不降秩，即无损编码。而该节点为了判断当前的编码方案是否会造成系统传输矩阵降秩，还要知道其他节点处的编码情况。这就需要整个网络的通力协作，这是迥异于传统网络的新概念。在传统的网络通信中，每个节点只知道自己和临近节点的状态，并致力于满足自身的最优化目标。但网络编码技术要求各个节点之间的合作，以保证整个通信系统的最优化。如何让各节点协同工作，并不降低编码效率和网络其他方面的性能，是网络编码算法设计的重大挑战之一。

网络编码方案可分为线性和非线性两种，其中线性方法的编码和解码都相对简单，因此，一般都倾向于采用线性方法。Li[3]指出在有向网络中，如果一个网络编码问题有解，则一定有线性解。从理论上保证了线性算法的有效性。线性组合要求网络节点具有更高的计算能力，然而根据摩尔定律，随着处理成本的降低，网络的“瓶颈”逐渐转向业务所需的更高的带宽支持和服务质量(QoS)保证。网络编码实际上是用节点处理能力换取更高的网络效率。

2 线性网络编码处理过程

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

2.1 编码过程

假设一个源或多个源产生的原始数据包信息为M 1……M n，则在线性网络编码中传输的数据可表示为为(其中g1……gn表示相应的编码系数)，对每个符号有：，

M ik和Xk分别为M i和X的第k个符号。传输的数据包中既包括编码向量，又包括信息向量，编码向量用于接收端的解码。

编码过程采用迭代的方法，若一个节点已经接收和存储的包信息集合为(g 1,X 1)……(g m,X m)，则这个节点可以通过选定编码系数h1……hm和运用算式得到新的信息包

(g ',X ')，编码向量g '可以通过直接的代数计算得到，该过程可以在若干个节点中重复操作。

2.2 解码过程

假设节点接收集合为(g 1,X 1)……(g m,X m)，为了恢复原始信息，需要求解｛｝的m个等式中的n个未知数M i，恢复所有数据要求M≥n，也就是说接收包的个数至少为原信息的个数。而有些线性组合可能是线性相关的，M≥n并不是充分条件，但却是网络编码的重要条件。

解码需要求解一组线性方程。实际中，可以应用高斯消去的方法：节点存贮编码向量以及编码之后的结果，以行向量的形式，存储在所谓解码矩阵中。最初，解码矩阵中只包含未经该节点编码的包以及与之相对应的编码向量(如果有的话)，否则为空。当接收到一个已编码包后，会从中抽取它的编码向量以及编码结果，放入到解码矩阵中。解码矩阵会经过等价变换变成行阶梯型，最终变成行最简型。所收到的某一个包如果可以增加矩阵的秩，则称之为更新包，如果所收到的包是非更新的，它可以通过等价变换变为全零，从而可以忽略。当解码矩阵变换成最简型后，方程组得解。这种情况发生在当接收到n 个线性独立的编码向量之后。

2.3 线性组合方案

设计网络编码的问题在于每个节点如何进行编码组合，目前在算法设计上，可以分为确定性编码和随机编码两种方案。

(1)确定的编码方案

Yeung[3]提出了线性网络编码的叠代实现方法，通过分析网络结构，根据节点的输入输出个数设计相应的局部编码向量，用迭代的方式得到全局编码向量，从而实现网络编码；Koettor[5]则提出了较为完备的线性网络编码的代数实现。但他们的方法运算量太高。于是Jaggi[6]等人又提出了一种确定多项式-时间的编码设计算法，可以为特定的广播网络找到可行的网络编码，目前已有对此算法的各种改进。

确定性的编码方案由于每个节点应用的都是固定的编码向量，因此网络中传递的数据中只需要包含信息向量，节省带宽，并且所需的符号集比较小；但确定性的网络编码需要了解全网的情况，复杂度比较高，难于分布式地实现。一旦网络拓扑结构发生了变化，就必须对整个编码方案进行修改，鲁棒性比较差。

(2)随机编码方案

由于确定性网络编码的以上缺点，Ho和Medard等人[7]提出了随机编码的概念，随机编码是让网络中的节点以完全独立的分布式方式，随机选取编码系数，对输入信息编码，并把这组随机向量作为报头的一部分发送给收点，以便于解码。已经证明，当符号集为无穷大时，采用随机编码，系统传输矩阵满秩的概率为“1”。

随机编码可以分布式地实现，并可增加保密性。文献[5]提出的代数实现的框架指出，线性网络编码可以通过随机编码有效地构建。Chou[8]应用随机编码，提出了第一个实用的网络编码方案。为了保证随机编码成功概率，编码向量的符号集必须足够大，这可能会增加数据包头部的负担，因此符号集的大小必须仔细选择。

3 网络编码研究现状

前期网络编码研究的背景主要是基于有线网络的，逐步深入的研究展示了网络编码扩展到无线网络中的广阔前景。但是在网络编码的理论和应用方面，无线自组织网络与有线网络有着显著的差别，这主要是由无线自组织网络的结构特征和无线传输信道的时变衰落特性决定的。与通过电缆或者光纤等可靠媒介形成固定而独立连接的有线网络不同，无线自组织网络的节点在分布上具有多维空间上的随机特性，节点之间的连接因受节点移动或节点分布地域的限制，不但具有时间域上的时变特性而且在空间域上具有相互制约的相关性，在信号传输上受到时变衰落信道的影响具有时间域上的随机性和不可靠性。所以把网络编码从有线网络推广到无线自组织网络，用来提高无线网络传输的有效性和可靠性，一个首要的问题就是对承载传输业务的无线自组织网络的结构特性和传输特性进行深入透彻的认识，即加强对网络模型的提取和对网络无线传输容量的细致研究。这一研究不但在确立无线网络传输性能极限上具有重要的理论意义，而且对如何把网络编码应用于无线网络中有着根本的指导作用。

目前，网络编码是国际信息论和网络理论领域所关注的热点，相关的研究人员如Medard、Effro和Yeung等人已经在建立网络编码的数学描述方法等方面作了大量的工作，得到了有线网络中利用网络编码实现最大流传输的若干判定定理。然而，他们的工作主要是集中在具有固定拓扑结构和容量的有线网络上，对网络编码在无线网络中的应用涉及得较少。由于有线网络中的带宽资源相对丰富，并且超高速传输对于处理的复杂度限制较低。而对于无线自组织网络，原有的关于有线网络的固定特性也不适于在任意端到端之间构造相应的网络编码，难于适合网络拓扑的变化。因此网络编码在无线网络中的应用还面临着很多独特的问题。

关于网络编码的复杂度，Koettor在文献[5]中证明，应用他们的算法，所用编码系数的符号集大大小于log2(mh +1)。其中h 是广播的流量，m是收点的数目。

Fragouli[9]将其缩小到 2m-7/4+1/2。在文献[10]中，作者系统地研究了网络编码的线性可解性和符号集大小的关系，并指出在某个符号集上有解的广播网络编码，在更大的符号集上未必可解。

在一个广播会话中，不是所有的中继节点都要对输入信息进行编码处理，只需在必须编码的节点处进行即可。这些必须编码的节点叫做编码节点，在编码节点处编码后的信息输出的链路叫做编码边。在文献[11]中，Langberg等人给出了一个广播网络中编码边数的上界和下界。不幸的是，他们还证明了确定编码边数的最小值是个非线性编程-硬(NP－hard)问题。这表明，在目前任何寻找编码节点和编码边的有效算法都只能是近似的。尽管如此，选择性的编码比在所有节点都进行编码的方法系统开销还是要小得多。Fragouli[9]提出了一种子树分解算法来寻找编码节点。

在算法设计上，形成了两个极端。一种是完全确定的编码方案。Koettor[5]提出了较为完备的线性网络编码的代数实现。但是他们的方法运算量太高。确定性的编码方案能够保证容许性，并且所需的符号集比较小。但是确定性的网络编码需要了解全网的情况，复杂度比较高，难于分布式的实现。一旦网络拓扑结构发生了变化，就必须对整个编码方案进行修改，所以鲁棒性比较差。

由于确定性网络编码的以上缺点，后来提出了随机编码的概念。随机编码是指每个节点随机地选取一组编码向量，对输入信息进行编码，并把这组随机向量作为报头的一部分发送给收点，以便于解码。随机编码可以分布式地实现，并且可以增加保密性。随机编码可以解决分布式实现的问题，但是可能造成系统传输矩阵奇异，导致在收点无法恢复出原始数据。可以证明，当符号集为无穷大时，采用随机编码，系统传输矩阵满秩的概率为“1”。

其余的算法基本上都是以上两个极端的折衷，例如可以采用半随机的编码方案。整个网络被化分成若干区域，各区域都采用随机编码，但为了保证传输矩阵满秩，区域间要相互传递信息，以使每个区域在选择编码向量时尽量不选可能导致解码失败的那些向量。为了保证随机编码成功概率，编码向量的符号集必须足够大，这可能增加数据包头部的负担，因此符号集的大小必须仔细选择。

此外，还有一些研究人员利用网络编码的思想提出了一些方案，以达到与最大流类似的最小费用、最低能量传输等网络优化目标。

对等网络(P2P)网络中，网络编码策略可以降低下载时间，在大规模的分配式P2P网络中，全局的调度非常复杂，而应用网络编码后，可以采用很简单的机制来构造随机的网络架构，提高系统性能，同时由于已编码文件块的密集性，基于网络编码的解决方案健壮性更强，例如当某种子节点过早离开时，编码机制的应用使网络信息块平等，从而可以降低信息丢失的情况。

在增大流量上，利用网络编码可以达到理论上限，可以应用于带宽有限的无线网络，利用其节点信息可以被周围邻居检测接收的特点。如图1所示，无线网络中当两个无线节点需要通过一个共同的基站来进行通信时，网络编码可以提高双向业务的网络流量，将结论推广到无线网络中的多跳路由中，两个终端节点的业务是双向的，且拥有相同的包要交换，在相邻路由器间应用轮询的时间调度，通过最初几步后，所有的中间节点都存储了要向两个方向传送的数据，当有传送机会时，路由器将要向两个方向传送的数据编码，传送出去，从而充分利用无线传输的特点；而对于接收节点，可以通过相应译码得到所需信息，信道的流量增加了一倍。网络编码还可以在组播、广播场景中应用，于是可以用于无线格状网(Mesh)、自组织(Ad Hoc)网络及无线传感器等多跳网络中。

网络编码机制使信息更加分散，等同于将信息进行了隐藏，更难窃听，提高了信息安全性。节点需要具有译码功能，同时要求得到足够的数据才能正确解码，信息很难被窃听，同时网络编码还可以防止拥塞方面的侵害，因此，将网络编码技术应用于军事等领域，其保密性和鲁棒性方面的潜力很大。

为了不对现有网络的软硬件设备和相应的协议做很大的修改，可以选择在更高层实现网络编码。基于组播覆盖网络节点功能更强、拓扑结构易构建的特点，应用简单的编码策略就可以提高网络容量和降低信息传输时延。基于这种思想，可以考虑在无线传感器网络，无线Mesh网络中应用网络编码，有效降低成本。

4 网络编码的研究热点

作为一种新型的网络传输技术，网络编码的优点不言而喻。但到目前为止，对这一领域的研究还主要集中在理论方面以及应用中局限性的分析方面。

4.1 网络编码节点选取方案

在确定的网络结构中，并不是所有的节点都需要进行网络编码，而是选取其中需要编译码的节点，给予编译码功能，对于不需要编译码的节点，只要具有传统的存储转发功能即可。这样不仅可以降低编码算法的复杂度，也减小了对硬件的要求，从而使得网络编码的应用更为广泛。文献[12]根据网络拓扑结构，利用一种子树分解算法来寻找编码节点。将该算法应用于有线网络中并使用确定的网络编码机制，效果较好；但对于无线网络，节点之间的连接关系更为复杂，并且节点传输覆盖范围内的节点都可能接收到网络信息，导致拓扑结构更为紧密，则应用上述方法选择编码节点就不太适合。因此，无线网络中主要考虑节点能量及稳定性的影响，选择编码节点或设计网络拓扑时应尽可能将节点能量较高、具有较强的运算速度和较大的缓存空间的节点，以提高网络的鲁棒性。

4.2 网络编码算法的设计

目前网络编码主要有确定性和随机性两种编码方案，分别用于不同的网络应用与构架上，这些方案主要是基于理论上的分析和实现，因此在实际网络上需要针对不同的应用设计相应的编码方式：如对于结构较小的网络，可以选择比较简单的确定性算法，编码过程中甚至可以通过转换为对数，将乘法运算转换成加法运算，降低总的编码复杂度；而对于无线网络，则应用随机编码机制是主要的研究趋势，即令中间节点随机生成编码系数，对节点所有的可用信息应用线性编码，并随时更新编码系数，文献[5]已经证明，当符号集为无穷大时，采用随机编码，系数传输矩阵满秩的概率是“1”，即编码成功的概率很大，但同时会增大数据报头的负担，因此符号集的大小需要权衡各种因素。

4.3 网络编码复杂度的分析

网络节点编码过程中会涉及到大量的乘法与加法运算，需要较大的计算复杂度，而接收节点译码过程若应用高斯消除方法，也是较大的运算过程。接收节点个数和节点信息块大小共同决定了编码符号集的最低门限。对于确定性编码而言，所需的符号集可以较小，编码的复杂度较低，但这种机制需要有中心节点集中控制网络信息，对于网络编码的很多应用场景以及网络构架都不适用，但可以通过对其相应的复杂度分析，来设计合适的编码算法从而降低网络的复杂度；对于随机网络编码而言，所需的符号集较大，而且节点在传送信息的同时传送系数向量，虽然系数向量相对于信息而言较小，但同样会占用较大的带宽，因此需要设计合适的算法，保证在提高编码增益的同时降低复杂度。网络编码复杂度要受到符号集大小、节点计算复杂度、网络编码方案等诸多因素的影响，需要全面分析得出。

4.4 网络编码的性能分析和应用

网络编码机制可以提高网络容量。已经证明应用网络编码，可以达到香农极限。网络编码通过编码节点对输入信息线性或非线性的编码处理，可以在不提高消耗带宽的情况下，使不同的信息同时通过有限的链路，从而提高网络流量。对于无线网络中的网络编码性能进行分析则需要应用网络信息论的知识，建立合适的网络容量模型来进行容量分析。

网络编码导致编解码的过程中可能会产生编译码错误，这将增大网络数据传输的误码率。而就网络编码本身而言，对误码率有着相当苛刻的要求，只有较小的误码率才能保证网络编码的有效性和可靠性，否则使用网络编码可能还会带来系统整体性能的降低。因此，如何设计可靠的网络编码方案以保证数据传输较低的误码率，并尽可能地采用相应技术减少误码率对网络编码方案的影响是网络编码研究所必需的。

4.5 网络编码与系统安全性分析

网络编码不仅可以提高节点间传输效率和网络吞吐量，还会对网络的安全性能产生影响。一方面，由网络编码导致的信息的分散性和编译码特性增加了信息破译难度，对安全性而言是一种改善；另一方面，对确定性编码算法而言，由于传输过程中将涉及较多的节点数目，以及编码算法方案的确定性，会导致系统的安全性能的降低。因此编码算法的设计中也需要考虑系统的安全性能，通过对不同的编码算法进行恰当的安全性能分析，来确定不同网络算法对系统安全性的影响，从而针对不同的系统应用选用合适的编码算法，以提高网络安全性能，这对于无线通信具有重要意义。

4.6 网络编码在无线分布式网络中的应用

对网络编码技术的研究需要在加深理论研究的同时，考虑实际的应用场景，侧重解决实际应用中遇到的问题，比如需要降低编码复杂度，需要考虑系统本身的延时以及网络编码带来的延时影响等。网络编码在无线通信网络当中的应用是一片亟待开发的热土，一方面无线网络的广播特性非常利于网络编码的应用；另一方面，相对于有线网络而言，无线网络中的节点不可能同时监听来自多个源的信息，对网络编码的应用造成了一定的阻碍。如何结合无线分布式网络的特点扬长避短，找到能够最大程度发挥网络编码优势的结合点，是需要考虑的主要问题。

5 结束语

网络编码作为一种新型的信息处理技术已经得到广泛的研究，本文在综合介绍了线性网络编码的产生背景和原理及编译码方案后，讨论了网络编码的优点和应用场景，并介绍了网络编码的研究热点，随着更多学者对该领域的深入研究，网络编码技术在未来通信中必将得到广泛应用。

6 参考文献

[1] Ahlswede R, Cai N, Li S Y R, Yeung R W. Network information flow [J]. IEEE Transactions on Information Theory, 2000, 46: 1016-1024.

[2] 谢政, 李建平. 网络算法与复杂性理论 [M]. 国防科技大学出版社, 1995(5).

[3] Li S Y R, Yeung R W, Cai N. Linear network coding [J]. IEEE Transactions on Information Theory, 2003, 49: 371-379.

[4] Christina Fragouli, Jean-Yves Le Boudec, Jorg Widmer. Network coding: an instant Primer [J]. IEEE Transactions on Information Theory, 2002, 48: 271-277.

[5] Koetter R, Medard M. An algebraic approach to network coding [J]. IEEE/ACM Transactions on Networking, 2003 (10): 1031-1042.

[6] Jaggi S, Sanders P, Chou P A, Effros M, Egner S, Jain K, Tolhuizen L. Polynomial time algorithms for multicast network code construction [J]. IEEE Transactions on Information Theory, 2003, 49: 831-836.

[7] Ho T, Koetter R, Medard M, Effros M, Shi J, Karger D. Toward a random operation of networks [J]. IEEE Transactions on Information Theory, 2004, 50: 532-537.

[8] Chou P A, Wu Y, Jain K. Practical network coding [J]. Allerton Conference on Communication, Control, and Computing, Monticello, IL, 2000,(10).

[9] Fragouli C, Soljanin E. Information flow decomposition for network coding [J]. IEEE Transactions on Information Theory, 2004, 50: 633-638.

[10] Dougherty R, Freiling C, Zeger K. Linearity and solvability in multicast networks [J]. IEEE Transactions on Information Theory, 2004, 50: 538-549.

[11] Langberg M, Sprintson A, Bruck J. The encoding complexity of network coding [J]. ETR063, California Institute of Technology, 2005, 120: 88-96.

[12] Christina Fragouli, Emina Soljanin. A connection between network coding and convolutional codes [J]. IEEE Communications Society, 2004, 70: 156-167.

作者简介：

彭木根，北京邮电大学电信工程学院博士毕业，毕业后留校任教。目前正负责和承担国家“863”计划项目、国家自然科学基金项目以及国际/国内著名设备制造商和运营商的多个科研项目。研究兴趣包括无线网络协同信息论、下一代无线宽带通信系统无线资源管理算法和协议设计、多跳无线中继和网络编码等。已出版著作4本、译著2本，发表论文60余篇，其中20余篇被SCI和EI收录。 王月新，北京邮电大学电信工程学院无线信号处理与网络实验室在读硕士研究生。研究方向为无线Mesh网络关键技术和网络编码技术研究。 王文博，北京邮电大学电信工程学院院长、教授、博士生导师。长期从事移动通信无线传输理论和技术研究、无线通信网络理论研究以及数字信号处理与软件无线电理论研究。已在国内外学术期刊和国际学术会议上发表论文100余篇，出版专著和教材5部。