彭木根等：无线自组织网络的网络编码技术
ＺＴＥＣＯＭＭＵＮＩＣＡＴＩＯＮＳ
无线自组织网络的网络编码技术
ＮｅｔｗｏｒｋＣｏｄｉｎｇＴｅｃｈｎｏｌｏｇｙｉｎｔｈｅＷｉｒｅｌｅｓｓＳｅｌｆ－ｏｒｇａｎｉｚｅｄＮｅｔｗｏｒｋ
彭木根／ＰＥＮＧＭｕ－ｇｅｎ，王月新／ＷＡＮＧＹｕｅ－ｘｉｎ，王文博／ＷＡＮＧＷｅｎ－ｂｏ
（北京邮电大学电信工程学院，北京１００８７６）
（ＴｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎＥｎｇｉｎｅｅｒｉｎｇＳｃｈｏｏｌ，ＢｅｉｊｉｎｇＵｎｉｖｅｒｓｉｔｙｏｆＰｏｓｔｓａｎｄＴｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ，Ｂｅｉｊｉｎｇ１００８７６，Ｃｈｉｎａ）
中图分类号：ＴＮ９２９．５文献标识码：Ａ文章编号：１００９－６８６８（２００７）０４－００５６－０５
摘要：网络编码作为一种新的技术在宽带无线自组织网络中有很好的应用，通过网络编码，中间节点可以将接收信息进行编码并发送出去，提高了网络吞吐量和健壮性。为不对现有网络的软硬件设备和相应的协议做很大的修改，可以选择在高层实现网络编码。无线传感器网络、无线格状网（Ｍｅｓｈ）等无线自组织网络都可以使用网络编码技术显著提高多跳链路的传输性能。目前网络编码的研究热点集中在网络编码节点选取方案、网络编码算法的设计、网络编码复杂度分析、网络编码的性能分析、网络编码与系统安全性分析、网络编码在无线分布式网络中的应用等方面。关键词：无线自组织网络；协同；网络编码
Ａｂｓｔｒａｃｔ：Ｔｈｅｎｅｔｗｏｒｋｃｏｄｉｎｇ，ａｓａｎｏｖｅｌｔｅｃｈｎｏｌｏｇｙ，ｗｉｌｌｈａｖｅａｇｏｏｄａｐｐｌｉｃａｔｉｏｎｉｎｔｈｅ
ｂｒｏａｄｂａｎｄｗｉｒｅｌｅｓｓｓｅｌｆ－ｏｒｇａｎｉｚｅｄｎｅｔｗｏｒｋ．Ｔｈｅｒｅｌａｙｎｏｄｅｗｉｌｌｄｅｃｏｄｅａｎｄｆｏｒｗａｒｄｔｈｅｒｅｌａｙｉｎｇｍｅｓｓａｇｅｖｉａｔｈｅｎｅｔｗｏｒｋｃｏｄｉｎｇｔｅｃｈｎｏｌｏｇｙ，ｗｈｉｃｈｗｉｌｌｉｍｐｒｏｖｅｔｈｅｎｅｔｗｏｒｋｔｈｒｏｕｇｈｐｕｔａｎｄｅｎｈａｎｃｅｔｈｅｒｏｂｕｓｔｎｅｓｓ．Ｉｎｏｒｄｅｒｔｏｄｅｃｒｅａｓｅｔｈｅｍｏｄｉｆｉｃａｔｉｏｎｏｎｔｈｅｓｏｆｔｗａｒｅ，ｈａｒｄｗａｒｅａｎｄｃｏｒｒｅｓｐｏｎｄｉｎｇｐｒｏｔｏｃｏｌｓｉｎｔｈｅｃｕｒｒｅｎｔｎｅｔｗｏｒｋ，ｔｈｅｎｅｔｗｏｒｋｃｏｄｉｎｇｔｅｃｈｎｉｑｕｅｓｈａｌｌｂｅａｄｏｐｔｅｄａｔｔｈｅｕｐｐｅｒｌａｙｅｒ．Ａｃｔｕａｌｌｙ，ｔｈｅｎｅｔｗｏｒｋｃｏｄｉｎｇｉｓｕｔｉｌｉｚｅｄｔｏｉｍｐｒｏｖｅｔｒａｎｓｍｉｓｓｉｏｎｐｅｒｆｏｒｍａｎｃｅｓｏｆｔｈｅｍｕｌｔｉ－ｈｏｐｌｉｎｋｉｎｂｏｔｈｔｈｅｗｉｒｅｌｅｓｓｓｅｎｓｏｒａｎｄｔｈｅＭｅｓｈｎｅｔｗｏｒｋ．Ｔｈｅｃｕｒｒｅｎｔｒｅｓｅａｒｃｈｉｎｔｅｒｅｓｔｒｅｌａｔｅｄｔｏｔｈｅｎｅｔｗｏｒｋｃｏｄｉｎｇｔｅｃｈｎｉｑｕｅｆｏｃｕｓｅｓｏｎｔｈｅｎｏｄｅｓｅｌｅｃｔｉｏｎ，ｃｏｄｉｎｇａｌｇｏｒｉｔｈｍｄｅｓｉｇｎ，ｃｏｄｉｎｇ
ｃｏｍｐｌｅｘｉｔｙｅｖａｌｕａｔｉｏｎ，ｃｏｄｉｎｇｐｅｒｆｏｒｍａｎｃｅａｎａｌｙｓｉｓ，ｃｏｄｉｎｇｓａｆｅｔｙｍｅｃｈａｎｉｓｍ，ａｎｄｔｈｅａｐｐｌｉｃａｔｉｏｎｉｎｔｈｅｗｉｒｅｌｅｓｓｄｉｓｔｒｉｂｕｔｅｄｎｅｔｗｏｒｋ．
Ｋｅｙｗｏｒｄｓ：ｗｉｒｅｌｅｓｓｓｅｌｆ－ｏｒｇａｎｉｚｅｄｎｅｔｗｏｒｋ；ｃｏｏｐｅｒａｔｉｖｅ；ｎｅｔｗｏｒｋｃｏｄｉｎｇ
宽
带无线多跳通信系统的设计目织无线网络的性能，一直是业界研究标是在充分利用有限的无线网
和关注的重点［１］。
络资源的前提下，使各接收节点能快速收到完整信息。如何提高多跳自组
１网络编码技术原理
网络编码（Ｎｅｔｗｏｒｋｃｏｄｉｎｇ）从广义基金项目：
国家“８６３”计划项目
（２００６ＡＡ０１Ｚ２５７）；国家自然科学基金项目上来讲，是网络中的节点将接收到的（６０６０２０５８）
信息进行编码后再转发出去的多点
５６
中兴通讯技术
２００７年８月第１３卷第４期Ａｕｇ．２００７Ｖｏｌ．１３Ｎｏ．４
传送（Ｍｕｌｔｉｃａｓｔ）技术。多点传送（也称
组播）是网络中的一种重要的通信方式。当一个或几个节点同时向若干个其他节点发送数据时，往往要借助其他节点的传递。
在传统的网络中，作为中继的节点只能对接收到的信号进行复制、放大和转发，这对于网络资源有时候是一种浪费。网络编码技术打破了这种限制，它允许中继节点对接收到的信息进行编码，并将接收到的多个数据包按照某种特定算法重新组合再发送出去。
图１所示为一无线通信领域３节点拓扑的实例：节点Ａ、
节点Ｂ相互传递信息ａ、ｂ。图１中的箭头代表有向链路，假设每条链路的容量为“１”。
图１（ａ）采用传统的通信方式，Ａ首先向Ｓ
发送信息ａ，然后Ｂ向Ｓ发送信息ｂ，Ｓ然后依次把信息ａ和ｂ分别广播给节点Ａ和节点Ｂ。这样经过４条链路的传输节点Ｂ可以获得信息ａ，而节点Ａ可以获得信息ｂ。但是当信息ａ和ｂ准备通过节点Ｓ进行转发时，如果应用网络编码技术，将ａ和ｂ作模２和运算后直接转发出去，则在节点Ｂ处，根据接收到的信息可恢复出ａ来；同理，在节点Ａ处也可以恢复出信息ｂ来，从而可以译码得到信息ｂ。采用了网络编码技术后（见图１（ｂ）），只需要使用３条链路就可以实现传统方式的所有通信要求。
从实例可以看出，网络编码技术可以显著地提高多点传送的数据率。在一个网络中传递的信息，可以形象的称之为“流”。网络的最大流量即为从源点到收点的最大传输数据率。而广播的最大流量是指源点同时向所有收点发送同样数据时，每个收点
能接收到的最大数据传输速率。理论上讲，最大流取决于网络的拓扑结构，即各节点的连接关系和带宽。利用图论中著名的最大流最小割定理可以得到给定网络中某个源点到收点的最大流［２］。
最大流最小割定理：任何带发点
彭木根等：无线自组织网络的网络编码技术
ＺＴＥＣＯＭＭＵＮＩＣＡＴＩＯＮＳ
和收点的网络中都存在最大流和最小割，并且最大流的流值等于最小割的容量。
从图１还可以看出，一个容许的网络编码方案，必须使得收点能够从接收到的数据中恢复出原始信息，也就是说，根据接收到的数据，和已知的编码方案，可以唯一地解出原始的数据。如果把整个网络看作一个系统，源点发送的数据可以视为系统的输入，收点接收到的数据作为输出，中间每个编码节点的操作作为系统函数，则要求从源点到每个收点之间的信息传输矩阵满秩，才能够满足广播的要求。
一串数据在经过中间网络时，可能经过多次编码。一个节点如果自身不是源点，那么它发出的信息只能来源于收到的信息。因此无论怎样编码，它发出的信息量必然小于等于收到的信息量。从信息论的角度讲，数据在传输过程中每经过一个节点，其信息熵都是非增的。所以，为了保证最后传到收点处的信息熵不降低，就要求每一个中间节点在编码时，系统的传输矩阵不降秩，即无损编码。而该节点为了判断当前的编码方案是否会造成系统传输矩阵降秩，还要知道其他节点处的编码情况。这就需要整个网络的通力协作，这是迥异于传统网络的新概念。在传统的网络通信中，每个节点只知道自己和临近节点的状态，并致力于满足自身的最优化目标。但网络编码技术要求各个节点之间的合作，以保证整个通信系统的最优化。如何让各节点协同工作，并不降低编码效率和网络其他方面的性能，是网络编码算法设计的重大挑战之一。
网络编码方案可分为线性和非线性两种，其中线性方法的编码和解码都相对简单，因此，一般都倾向于采用线性方法。Ｌｉ［３］指出在有向网络中，如果一个网络编码问题有解，则一定有线性解。从理论上保证了线性算法的有效性。线性组合要求网络节
点具有更高的计算能力，然而根据摩尔定律，随着处理成本的降低，网络的“瓶颈”逐渐转向业务所需的更高的带宽支持和服务质量（ＱｏＳ）保证。网络编码实际上是用节点处理能力换取更高的网络效率。
ＡＡＡＡ
ａｂａ
ＳＳＳＳ（ａ）
ａ、ｂ：信息
Ａ、Ｂ、Ｓ：节点
ｂａｂ
ＢＢＢＢ
ＡＡＡ
ａ
ＳＳ
ａ! ｂ
Ｓ（ｂ）
ｂａ! ｂ
ＢＢＢ
▲图１无线单播系统传统传输方式与网络编码技术比较
节点中重复操作。
２．２解码过程
假设节点接收集合为（ｇ１，Ｘ１）……
（ｇｍ，Ｘｍ），为了恢复原始信息，需要求
ｉ
解｛Ｘｊ＝∑ｉ＝１ｇｉｊＭｋ｝的ｍ个等式中的ｎ个
ｎ
未知数Ｍｉ，恢复所有数据要求Ｍ≥ｎ，
２线性网络编码处理过程
线性网络编码是将节点传送信息线性映射到一个有限域内，利用线性关系实现编译码过程［４］。假设每个信息数据包为Ｌ比特，当它与要组合的数据包长度不同时，较短的信息附加额外一串“０”，将包中的ｓ个连续比特组成域上的一个符号，则一个包中包含Ｌ／ｓ个符号。在线性编码下，运用乘法和加法运算，使从节点发送出去的数据为该节点接收到信息的线性组合。
也就是说接收包的个数至少为原信息的个数。而有些线性组合可能是线性相关的，Ｍ≥ｎ并不是充分条件，但却是网络编码的重要条件。
解码需要求解一组线性方程。实际中，可以应用高斯消去的方法：节点存贮编码向量以及编码之后的结果，以行向量的形式，存储在所谓解码矩阵中。最初，解码矩阵中只包含未经该节点编码的包以及与之相对应的编码向量（如果有的话），否则为空。当接收到一个已编码包后，会从中抽取它的编码向量以及编码结果，放入到解码矩阵中。解码矩阵会经过等价变换变成行阶梯型，最终变成行最简型。所收到的某一个包如果可以增加矩阵的秩，则称之为更新包，如果所收到的包是非更新的，它可以通过等价变换变为全零，从而可以忽略。当解码矩阵变换成最简型后，方程组得解。这种情况发生在当接收到
２．１编码过程
假设一个源或多个源产生的原始数据包信息为Ｍ１……Ｍｎ，则在线性网络编码中传输的数据可表示为为
Ｘ＝∑ｇＭｉ（其中ｇ１……ｇｎ表示相应的
编码系数），对每个符号有：Ｘｋ＝∑ｇＭｋ，ｉ
ｎ
ｉ＝１ｉ
ｎ
ｉ＝１ｉ
Ｍｉｋ和Ｘｋ分别为Ｍｉ和Ｘ的第ｋ个符号。
传输的数据包中既包括编码向量，又包括信息向量，编码向量用于接收端的解码。
编码过程采用迭代的方法，若一个节点已经接收和存储的包信息集合为（ｇ１，Ｘ１）……（ｇｍ，Ｘｍ），则这个节点可以通过选定编码系数ｈ１……ｈｍ和运用算式Ｘ＇∑ｉ＝１ｈｊＸｊ得到新的信息包
ｍ
ｎ个线性独立的编码向量之后。２．３线性组合方案
设计网络编码的问题在于每个节点如何进行编码组合，目前在算法设计上，可以分为确定性编码和随机编码两种方案。
（ｇ＇，Ｘ＇），编码向量ｇ＇可以通过直接的
代数计算得到，该过程可以在若干个
（１）确定的编码方案
Ｙｅｕｎｇ［３］提出了线性网络编码的
中兴通讯技术
５７
Ａｕｇ．２００７Ｖｏｌ．１３Ｎｏ．４２００７年８月第１３卷第４期
彭木根等：无线自组织网络的网络编码技术
ＺＴＥＣＯＭＭＵＮＩＣＡＴＩＯＮＳ
叠代实现方法，通过分析网络结构，网络有着显著的差别，这主要是由无根据节点的输入输出个数设计相应线自组织网络的结构特征和无线传的局部编码向量，用迭代的方式得到输信道的时变衰落特性决定的。与通全局编码向量，从而实现网络编码；
过电缆或者光纤等可靠媒介形成固Ｋｏｅｔｔｏｒ［５］则提出了较为完备的线性网
定而独立连接的有线网络不同，无线络编码的代数实现。但他们的方法运自组织网络的节点在分布上具有多算量太高。于是Ｊａｇｇｉ［６］等人又提出了维空间上的随机特性，节点之间的连一种确定多项式－时间的编码设计算接因受节点移动或节点分布地域的法，可以为特定的广播网络找到可行限制，不但具有时间域上的时变特性的网络编码，目前已有对此算法的各而且在空间域上具有相互制约的相种改进。
关性，在信号传输上受到时变衰落信确定性的编码方案由于每个节道的影响具有时间域上的随机性和点应用的都是固定的编码向量，因此不可靠性。所以把网络编码从有线网网络中传递的数据中只需要包含信络推广到无线自组织网络，用来提高息向量，节省带宽，并且所需的符号无线网络传输的有效性和可靠性，一集比较小；但确定性的网络编码需要个首要的问题就是对承载传输业务了解全网的情况，复杂度比较高，难的无线自组织网络的结构特性和传于分布式地实现。一旦网络拓扑结构输特性进行深入透彻的认识，即加强发生了变化，就必须对整个编码方案对网络模型的提取和对网络无线传进行修改，鲁棒性比较差。
输容量的细致研究。这一研究不但在（２）随机编码方案
确立无线网络传输性能极限上具有由于确定性网络编码的以上缺重要的理论意义，而且对如何把网络点，Ｈｏ和Ｍｅｄａｒｄ等人［７］提出了随机编编码应用于无线网络中有着根本的码的概念，随机编码是让网络中的节指导作用。
点以完全独立的分布式方式，随机选目前，网络编码是国际信息论和取编码系数，对输入信息编码，并把网络理论领域所关注的热点，相关的这组随机向量作为报头的一部分发研究人员如Ｍｅｄａｒｄ、Ｅｆｆｒｏ和Ｙｅｕｎｇ等人送给收点，以便于解码。已经证明，当已经在建立网络编码的数学描述方符号集为无穷大时，采用随机编码，法等方面作了大量的工作，得到了有系统传输矩阵满秩的概率为“１”。
线网络中利用网络编码实现最大流随机编码可以分布式地实现，并传输的若干判定定理。然而，他们的可增加保密性。文献［５］提出的代数实工作主要是集中在具有固定拓扑结现的框架指出，线性网络编码可以通构和容量的有线网络上，对网络编码过随机编码有效地构建。Ｃｈｏｕ［８］应用在无线网络中的应用涉及得较少。由随机编码，提出了第一个实用的网络于有线网络中的带宽资源相对丰富，编码方案。为了保证随机编码成功概并且超高速传输对于处理的复杂度率，编码向量的符号集必须足够大，限制较低。而对于无线自组织网络，这可能会增加数据包头部的负担，因原有的关于有线网络的固定特性也此符号集的大小必须仔细选择。
不适于在任意端到端之间构造相应的网络编码，难于适合网络拓扑的变３网络编码研究现状
化。因此网络编码在无线网络中的应前期网络编码研究的背景主要用还面临着很多独特的问题。
是基于有线网络的，逐步深入的研究关于网络编码的复杂度，Ｋｏｅｔｔｏｒ展示了网络编码扩展到无线网络中在文献［５］中证明，应用他们的算法，的广阔前景。但是在网络编码的理论所用编码系数的符号集大大小于ｌｏｇ２
和应用方面，无线自组织网络与有线
（ｍｈ＋１）。其中ｈ是广播的流量，ｍ是收
５８
中兴通讯技术
２００７年８月第１３卷第４期Ａｕｇ．２００７Ｖｏｌ．１３Ｎｏ．４
点的数目。
Ｆｒａｇｏｕｌｉ［９］将其缩小到。
在文献［１０］中，作者系统地研究了网络编码的线性可解性和符号集大小的关系，并指出在某个符号集上有解的广播网络编码，在更大的符号集上未必可解。
在一个广播会话中，不是所有的中继节点都要对输入信息进行编码处理，只需在必须编码的节点处进行即可。这些必须编码的节点叫
做编码节点，在编码节点处编码后的信息输出的链路叫做编码边。在文献［１１］中，
Ｌａｎｇｂｅｒｇ等人给出了一个广播网络中
编码边数的上界和下界。不幸的是，他们还证明了确定编码边数的最小值是个非线性编程－硬（ＮＰ－ｈａｒｄ）问题。这表明，在目前任何寻找编码节点和编码边的有效算法都只能是近似的。尽管如此，选择性的编码比在所有节点都进行编码的方法系统开销还是要小得多。Ｆｒａｇｏｕｌｉ［９］提出了一种子树分解算法来寻找编码节点。
在算法设计上，
形成了两个极
端。一种是完全确定的编码方案。
Ｋｏｅｔｔｏｒ［５］提出了较为完备的线性网络
编码的代数实现。但是他们的方法运算量太高。确定性的编码方案能够保证容许性，并且所需的符号集比较小。但是确定性的网络编码需要了解全网的情况，复杂度比较高，难于分布式的实现。一旦网络拓扑结构发生了变化，就必须对整个编码方案进行修改，所以鲁棒性比较差。
由于确定性网络编码的以上缺点，后来提出了随机编码的概念。随机编码是指每个节点随机地选取一组编码向量，对输入信息进行编码，并把这组随机向量作为报头的一部分发送给收点，以便于解码。随机编码可以分布式地实现，并且可以增加保密性。随机编码可以解决分布式实现的问题，但是可能造成系统传输矩阵奇异，导致在收点无法恢复出原始数据。可以证明，当符号集为无穷大时，采用随机编码，系统传输矩阵满
彭木根等：无线自组织网络的网络编码技术
ＺＴＥＣＯＭＭＵＮＩＣＡＴＩＯＮＳ
秩的概率为“１”。
其余的算法基本上都是以上两个极端的折衷，例如可以采用半随机的编码方案。整个网络被化分成若干区域，各区域都采用随机编码，但为了保证传输矩阵满秩，区域间要相互传递信息，以使每个区域在选择编码向量时尽量不选可能导致解码失败的那些向量。为了保证随机编码成功概率，编码向量的符号集必须足够大，这可能增加数据包头部的负担，因此符号集的大小必须仔细选择。
此外，还有一些研究人员利用网络编码的思想提出了一些方案，以达到与最大流类似的最小费用、最低能量传输等网络优化目标。
对等网络（Ｐ２Ｐ）网络中，网络编码策略可以降低下载时间，在大规模的分配式Ｐ２Ｐ网络中，全局的调度非常复杂，而应用网络编码后，可以采用很简单的机制来构造随机的网络架构，提高系统性能，同时由于已编码文件块的密集性，基于网络编码的解决方案健壮性更强，例如当某种子节点过早离开时，编码机制的应用使网络信息块平等，从而可以降低信息丢失的情况。
在增大流量上，利用网络编码可以达到理论上限，可以应用于带宽有限的无线网络，利用其节点信息可以被周围邻居检测接收的特点。如图１所示，无线网络中当两个无线节点需要通过一个共同的基站来进行通信时，网络编码可以提高双向业务的网络流量，将结论推广到无线网络中的多跳路由中，两个终端节点的业务是双向的，且拥有相同的包要交换，在相邻路由器间应用轮询的时间调度，通过最初几步后，所有的中间节点都存储了要向两个方向传送的数据，当有传送机会时，路由器将要向两个方向传送的数据编码，传送出去，从而充分利用无线传输的特点；而对于接收节点，可以通过相应译码得到所需信息，信道的流量增加了一倍。网络编码还可以在组播、广播场景中应
用，于是可以用于无线格状网（Ｍｅｓｈ）、自组织（ＡｄＨｏｃ）网络及无线传感器等多跳网络中。
网络编码机制使信息更加分散，等同于将信息进行了隐藏，更难窃听，提高了信息安全性。节点需要具有译码功能，同时要求得到足够的数据才能正确解码，信息很难被窃听，同时网络编码还可以防止拥塞方面的侵害，因此，将网络编码技术应用于军事等领域，其保密性和鲁棒性方面的潜力很大。
为了不对现有网络的软硬件设备和相应的协议做很大的修改，可以选择在更高层实现网络编码。基于组播覆盖网络节点功能更强、拓扑结构易构建的特点，应用简单的编码策略就可以提高网络容量和降低信息传输时延。基于这种思想，可以考虑在无线传感器网络，无线Ｍｅｓｈ网络中应用网络编码，有效降低成本。
码节点就不太适合。因此，无线网络中主要考虑节点能量及稳定性的影响，选择编码节点或设计网络拓扑时应尽可能将节点能量较高、具有较强的运算速度和较大的缓存空间的节点，以提高网络的鲁棒性。
４．２网络编码算法的设计
目前网络编码主要有确定性和随机性两种编码方案，分别用于不同的网络应用与构架上，这些方案主要是基于理论上的分析和实现，因此在实际网络上需要针对不同的应用设计相应的编码方式：如对于结构较小的网络，可以选择比较简单的确定性算法，编码过程中甚至可以通过转换为对数，将乘法运算转换成加法运算，降低总的编码复杂度；而对于无线网络，则应用随机编码机制是主要的研究趋势，即令中间节点随机生成编码系数，对节点所有的可用信息应用线性编码，并随时更新编码系数，文献［５］已经证明，当符号集为无穷大时，采用随机编码，系数传输矩阵满秩的概率是“１”，即编码成功的概率很大，但同时会增大数据报头的负担，因此符号集的大小需要权衡各种因素。
４网络编码的研究热点
作为一种新型的网络传输技术，网络编码的优点不言而喻。但到目前为止，对这一领域的研究还主要集中在理论方面以及应用中局限性的分析方面。
４．１网络编码节点选取方案
在确定的网络结构中，并不是所有的节点都需要进行网络编码，而是选取其中需要编译码的节点，给予编译码功能，对于不需要编译码的节点，只要具有传统的存储转发功能即可。这样不仅可以降低编码算法的复杂度，也减小了对硬件的要求，从而使得网络编码的应用更为广泛。文献
４．３网络编码复杂度的分析
网络节点编码过程中会涉及到大量的乘法与加法运算，需要较大的计算复杂度，而接收节点译码过程若应用高斯消除方法，也是较大的运算过程。接收节点个数和节点信息块大小共同决定了编码符号集的最低门限。对于确定性编码而言，所需的符号集可以较小，编码的复杂度较低，但这种机制需要有中心节点集中控制网络信息，对于网络编码的很多应用场景以及网络构架都不适用，但可以通过对其相应的复杂度分析，来设计合适的编码算法从而降低网络的复杂度；对于随机网络编码而言，所需的符号集较大，而且节点在传送信息的同时传送系数向量，虽然系数向
［１２］根据网络拓扑结构，利用一种子
树分解算法来寻找编码节点。将该算法应用于有线网络中并使用确定的网络编码机制，效果较好；但对于无线网络，节点之间的连接关系更为复杂，并且节点传输覆盖范围内的节点都可能接收到网络信息，导致拓扑结构更为紧密，则应用上述方法选择编
中兴通讯技术
５９
Ａｕｇ．２００７Ｖｏｌ．１３Ｎｏ．４２００７年８月第１３卷第４
期
彭木根等：无线自组织网络的网络编码技术
ＺＴＥＣＯＭＭＵＮＩＣＡＴＩＯＮＳ
量相对于信息而言较小，但同样会占安全性的影响，从而针对不同的系统用较大的带宽，因此需要设计合适的应用选用合适的编码算法，以提高网算法，保证在提高编码增益的同时降络安全性能，这对于无线通信具有重低复杂度。网络编码复杂度要受到符要意义。
号集大小、节点计算复杂度、网络编码方案等诸多因素的影响，需要全面４．６网络编码在无线分布式网络中
分析得出。
的应用
对网络编码技术的研究需要在４．４网络编码的性能分析和应用
加深理论研究的同时，考虑实际的应网络编码机制可以提高网络容用场景，侧重解决实际应用中遇到的量。已经证明应用网络编码，可以达问题，比如需要降低编码复杂度，需到香农极限。网络编码通过编码节点要考虑系统本身的延时以及网络编对输入信息线性或非线性的编码处码带来的延时影响等。网络编码在无理，可以在不提高消耗带宽的情况线通信网络当中的应用是一片亟待下，使不同的信息同时通过有限的链开发的热土，一方面无线网络的广播路，从而提高网络流量。对于无线网特性非常利于网络编码的应用；另一络中的网络编码性能进行分析则需方面，相对于有线网络而言，无线网要应用网络信息论的知识，建立合适络中的节点不可能同时监听来自多的网络容量模型来进行容量分析。
个源的信息，对网络编码的应用造成网络编码导致编解码的过程中了一定的阻碍。如何结合无线分布式可能会产生编译码错误，这将增大网网络的特点扬长避短，找到能够最大络数据传输的误码率。而就网络编码程度发挥网络编码优势的结合点，是本身而言，对误码率有着相当苛刻的需要考虑的主要问题。
要求，只有较小的误码率才能保证网络编码的有效性和可靠性，否则使用５结束语
网络编码可能还会带来系统整体性网络编码作为一种新型的信息能的降低。因此，如何设计可靠的网处理技术已经得到广泛的研究，本文络编码方案以保证数据传输较低的在综合介绍了线性网络编码的产生误码率，并尽可能地采用相应技术减背景和原理及编译码方案后，讨论了少误码率对网络编码方案的影响是网络编码的优点和应用场景，并介绍网络编码研究所必需的。
了网络编码的研究热点，随着更多学者对该领域的深入研究，网络编码技４．５网络编码与系统安全性分析
术在未来通信中必将得到广泛应用。
网络编码不仅可以提高节点间传输效率和网络吞吐量，还会对网络６参考文献
的安全性能产生影响。一方面，由网［１］ＡｈｌｓｗｅｄｅＲ，ＣａｉＮ，ＬｉＳＹＲ，ＹｅｕｎｇＲＷ．络编码导致的信息的分散性和编译Ｎｅｔｗｏｒｋｉｎｆｏｒｍａｔｉｏｎｆｌｏｗ［Ｊ］．ＩＥＥＥ
ＴｒａｎｓａｃｔｉｏｎｓｏｎＩｎｆｏｒｍａｔｉｏｎＴｈｅｏｒｙ，２０００，４６：码特性增加了信息破译难度，对安全１０１６－１０２４．
性而言是一种改善［２］谢政，李建平．网络算法与复杂性理论［Ｍ］．国
；另一方面，对确防科技大学出版社，１９９５（５）．
定性编码算法而言，由于传输过程中［３］ＬｉＳＹＲ，ＹｅｕｎｇＲＷ，ＣａｉＮ．Ｌｉｎｅａｒｎｅｔｗｏｒｋｃｏｄｉｎｇ［Ｊ］．ＩＥＥＥＴｒａｎｓａｃｔｉｏｎｓｏｎＩｎｆｏｒｍａｔｉｏｎ将涉及较多的节点数目，以及编码算Ｔｈｅｏｒｙ，２００３，４９：３７１－３７９．
法方案的确定性，会导致系统的安全［４］ＣｈｒｉｓｔｉｎａＦｒａｇｏｕｌｉ，Ｊｅａｎ－ＹｖｅｓＬｅＢｏｕｄｅｃ，ＪｏｒｇＷｉｄｍｅｒ．Ｎｅｔｗｏｒｋｃｏｄｉｎｇ：ａｎｉｎｓｔａｎｔ性能的降低。因此编码算法的设计中Ｐｒｉｍｅｒ［Ｊ］．ＩＥＥＥＴｒａｎｓａｃｔｉｏｎｓｏｎＩｎｆｏｒｍａｔｉｏｎ也需要考虑系统的安全性能Ｔｈｅｏｒｙ，２００２，４８：２７１－２７７．
，通过对［５］ＫｏｅｔｔｅｒＲ，ＭｅｄａｒｄＭ．Ａｎａｌｇｅｂｒａｉｃａｐｐｒｏａｃｈ不同的编码算法进行恰当的安全性ｔｏｎｅｔｗｏｒｋｃｏｄｉｎｇ［Ｊ］．ＩＥＥＥ／ＡＣＭ
ＴｒａｎｓａｃｔｉｏｎｓｏｎＮｅｔｗｏｒｋｉｎｇ，２００３（１０）：能分析，来确定不同网络算法对系统
１０３１－１０４２．
６０
中兴通讯技术
２００７年８月第１３卷第４期Ａｕｇ．２００７Ｖｏｌ．１３Ｎｏ．４
［６］ＪａｇｇｉＳ，ＳａｎｄｅｒｓＰ，ＣｈｏｕＰＡ，ＥｆｆｒｏｓＭ，ＥｇｎｅｒＳ，ＪａｉｎＫ，ＴｏｌｈｕｉｚｅｎＬ．Ｐｏｌｙｎｏｍｉａｌｔｉｍｅａｌｇｏｒｉｔｈｍｓｆｏｒｍｕｌｔｉｃａｓｔｎｅｔｗｏｒｋｃｏｄｅｃｏｎｓｔｒｕｃｔｉｏｎ［Ｊ］．ＩＥＥＥＴｒａｎｓａｃｔｉｏｎｓｏｎＩｎｆｏｒｍａｔｉｏｎＴｈｅｏｒｙ，２００３，４９：８３１－８３６．
［７］ＨｏＴ，ＫｏｅｔｔｅｒＲ，ＭｅｄａｒｄＭ，ＥｆｆｒｏｓＭ，ＳｈｉＪ，ＫａｒｇｅｒＤ．Ｔｏｗａｒｄａｒａｎｄｏｍｏｐｅｒａｔｉｏｎｏｆｎｅｔｗｏｒｋｓ［Ｊ］．ＩＥＥＥＴｒａｎｓａｃｔｉｏｎｓｏｎ
ＩｎｆｏｒｍａｔｉｏｎＴｈｅｏｒｙ，２００４，５０：５３２－５３７．［８］ＣｈｏｕＰＡ，ＷｕＹ，ＪａｉｎＫ．Ｐｒａｃｔｉｃａｌｎｅｔｗｏｒｋｃｏｄｉｎｇ［Ｊ］．ＡｌｌｅｒｔｏｎＣｏｎｆｅｒｅｎｃｅｏｎ
Ｃｏｍｍｕｎｉｃａｔｉｏｎ，Ｃｏｎｔｒｏｌ，ａｎｄＣｏｍｐｕｔｉｎｇ，Ｍｏｎｔｉｃｅｌｌｏ，ＩＬ，２０００，（１０）．
［９］ＦｒａｇｏｕｌｉＣ，ＳｏｌｊａｎｉｎＥ．Ｉｎｆｏｒｍａｔｉｏｎｆｌｏｗ
ｄｅｃｏｍｐｏｓｉｔｉｏｎｆｏｒｎｅｔｗｏｒｋｃｏｄｉｎｇ［Ｊ］．ＩＥＥＥＴｒａｎｓａｃｔｉｏｎｓｏｎＩｎｆｏｒｍａｔｉｏｎＴｈｅｏｒｙ，２００４，５０：６３３－６３８．
［１０］ＤｏｕｇｈｅｒｔｙＲ，ＦｒｅｉｌｉｎｇＣ，ＺｅｇｅｒＫ．Ｌｉｎｅａｒｉｔｙ
ａｎｄｓｏｌｖａｂｉｌｉｔｙｉｎｍｕｌｔｉｃａｓｔｎｅｔｗｏｒｋｓ［Ｊ］．ＩＥＥＥＴｒａｎｓａｃｔｉｏｎｓｏｎＩｎｆｏｒｍａｔｉｏｎＴｈｅｏｒｙ，２００４，５０：５３８－５４９．
［１１］ＬａｎｇｂｅｒｇＭ，ＳｐｒｉｎｔｓｏｎＡ，ＢｒｕｃｋＪ．Ｔｈｅ
ｅｎｃｏｄｉｎｇｃｏｍｐｌｅｘｉｔｙｏｆｎｅｔｗｏｒｋｃｏｄｉｎｇ［Ｊ］．ＥＴＲ０６３，ＣａｌｉｆｏｒｎｉａＩｎｓｔｉｔｕｔｅｏｆＴｅｃｈｎｏｌｏｇｙ，２００５，１２０：８８－９６．
［１２］ＣｈｒｉｓｔｉｎａＦｒａｇｏｕｌｉ，ＥｍｉｎａＳｏｌｊａｎｉｎ．Ａ
ｃｏｎｎｅｃｔｉｏｎｂｅｔｗｅｅｎｎｅｔｗｏｒｋｃｏｄｉｎｇａｎｄｃｏｎｖｏｌｕｔｉｏｎａｌｃｏｄｅｓ［Ｊ］．ＩＥＥＥ
ＣｏｍｍｕｎｉｃａｔｉｏｎｓＳｏｃｉｅｔｙ，２００４，７０：１５６－１６７．
收稿日期：２００７－０４－０９
彭木根，北京邮电大学电信
工程学院博士毕业，毕业后留校任教。目前正负责和承
担国家“８６３”计划项目、
国家自然科学基金项目以及国际／国内著名设备制造商和运营商的多个科研项目。研究兴趣包括无线网络协同信息论、下一代无线宽带通信系统无线资源管理算
法和协议设计、多跳无线中继和网络编码等。已出版著作４本、译著２本，发表论文６０余篇，其中２０余篇被ＳＣＩ和ＥＩ收录。
王月新，北京邮电大学电信工程学院无线信号处理与网络实验室在读硕士研究生。研究方向为无线Ｍｅｓｈ网络关键技术和网络编码技术研究。
王文博，北京邮电大学电信工程学院院长、教授、博士生导师。长期从事移动通信无线传输理论和技术研究、无线通信网络理论研究以及数字信号处理与软件无线电理论研究。已在国内外学术期刊和国际学术会议上发表论文１００余篇，出版专著和教材５部。
彭木根等：无线自组织网络的网络编码技术
ＺＴＥＣＯＭＭＵＮＩＣＡＴＩＯＮＳ
无线自组织网络的网络编码技术
ＮｅｔｗｏｒｋＣｏｄｉｎｇＴｅｃｈｎｏｌｏｇｙｉｎｔｈｅＷｉｒｅｌｅｓｓＳｅｌｆ－ｏｒｇａｎｉｚｅｄＮｅｔｗｏｒｋ
彭木根／ＰＥＮＧＭｕ－ｇｅｎ，王月新／ＷＡＮＧＹｕｅ－ｘｉｎ，王文博／ＷＡＮＧＷｅｎ－ｂｏ
（北京邮电大学电信工程学院，北京１００８７６）
（ＴｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎＥｎｇｉｎｅｅｒｉｎｇＳｃｈｏｏｌ，ＢｅｉｊｉｎｇＵｎｉｖｅｒｓｉｔｙｏｆＰｏｓｔｓａｎｄＴｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ，Ｂｅｉｊｉｎｇ１００８７６，Ｃｈｉｎａ）
中图分类号：ＴＮ９２９．５文献标识码：Ａ文章编号：１００９－６８６８（２００７）０４－００５６－０５
摘要：网络编码作为一种新的技术在宽带无线自组织网络中有很好的应用，通过网络编码，中间节点可以将接收信息进行编码并发送出去，提高了网络吞吐量和健壮性。为不对现有网络的软硬件设备和相应的协议做很大的修改，可以选择在高层实现网络编码。无线传感器网络、无线格状网（Ｍｅｓｈ）等无线自组织网络都可以使用网络编码技术显著提高多跳链路的传输性能。目前网络编码的研究热点集中在网络编码节点选取方案、网络编码算法的设计、网络编码复杂度分析、网络编码的性能分析、网络编码与系统安全性分析、网络编码在无线分布式网络中的应用等方面。关键词：无线自组织网络；协同；网络编码
Ａｂｓｔｒａｃｔ：Ｔｈｅｎｅｔｗｏｒｋｃｏｄｉｎｇ，ａｓａｎｏｖｅｌｔｅｃｈｎｏｌｏｇｙ，ｗｉｌｌｈａｖｅａｇｏｏｄａｐｐｌｉｃａｔｉｏｎｉｎｔｈｅ
ｂｒｏａｄｂａｎｄｗｉｒｅｌｅｓｓｓｅｌｆ－ｏｒｇａｎｉｚｅｄｎｅｔｗｏｒｋ．Ｔｈｅｒｅｌａｙｎｏｄｅｗｉｌｌｄｅｃｏｄｅａｎｄｆｏｒｗａｒｄｔｈｅｒｅｌａｙｉｎｇｍｅｓｓａｇｅｖｉａｔｈｅｎｅｔｗｏｒｋｃｏｄｉｎｇｔｅｃｈｎｏｌｏｇｙ，ｗｈｉｃｈｗｉｌｌｉｍｐｒｏｖｅｔｈｅｎｅｔｗｏｒｋｔｈｒｏｕｇｈｐｕｔａｎｄｅｎｈａｎｃｅｔｈｅｒｏｂｕｓｔｎｅｓｓ．Ｉｎｏｒｄｅｒｔｏｄｅｃｒｅａｓｅｔｈｅｍｏｄｉｆｉｃａｔｉｏｎｏｎｔｈｅｓｏｆｔｗａｒｅ，ｈａｒｄｗａｒｅａｎｄｃｏｒｒｅｓｐｏｎｄｉｎｇｐｒｏｔｏｃｏｌｓｉｎｔｈｅｃｕｒｒｅｎｔｎｅｔｗｏｒｋ，ｔｈｅｎｅｔｗｏｒｋｃｏｄｉｎｇｔｅｃｈｎｉｑｕｅｓｈａｌｌｂｅａｄｏｐｔｅｄａｔｔｈｅｕｐｐｅｒｌａｙｅｒ．Ａｃｔｕａｌｌｙ，ｔｈｅｎｅｔｗｏｒｋｃｏｄｉｎｇｉｓｕｔｉｌｉｚｅｄｔｏｉｍｐｒｏｖｅｔｒａｎｓｍｉｓｓｉｏｎｐｅｒｆｏｒｍａｎｃｅｓｏｆｔｈｅｍｕｌｔｉ－ｈｏｐｌｉｎｋｉｎｂｏｔｈｔｈｅｗｉｒｅｌｅｓｓｓｅｎｓｏｒａｎｄｔｈｅＭｅｓｈｎｅｔｗｏｒｋ．Ｔｈｅｃｕｒｒｅｎｔｒｅｓｅａｒｃｈｉｎｔｅｒｅｓｔｒｅｌａｔｅｄｔｏｔｈｅｎｅｔｗｏｒｋｃｏｄｉｎｇｔｅｃｈｎｉｑｕｅｆｏｃｕｓｅｓｏｎｔｈｅｎｏｄｅｓｅｌｅｃｔｉｏｎ，ｃｏｄｉｎｇａｌｇｏｒｉｔｈｍｄｅｓｉｇｎ，ｃｏｄｉｎｇ
ｃｏｍｐｌｅｘｉｔｙｅｖａｌｕａｔｉｏｎ，ｃｏｄｉｎｇｐｅｒｆｏｒｍａｎｃｅａｎａｌｙｓｉｓ，ｃｏｄｉｎｇｓａｆｅｔｙｍｅｃｈａｎｉｓｍ，ａｎｄｔｈｅａｐｐｌｉｃａｔｉｏｎｉｎｔｈｅｗｉｒｅｌｅｓｓｄｉｓｔｒｉｂｕｔｅｄｎｅｔｗｏｒｋ．
Ｋｅｙｗｏｒｄｓ：ｗｉｒｅｌｅｓｓｓｅｌｆ－ｏｒｇａｎｉｚｅｄｎｅｔｗｏｒｋ；ｃｏｏｐｅｒａｔｉｖｅ；ｎｅｔｗｏｒｋｃｏｄｉｎｇ
宽
带无线多跳通信系统的设计目织无线网络的性能，一直是业界研究标是在充分利用有限的无线网
和关注的重点［１］。
络资源的前提下，使各接收节点能快速收到完整信息。如何提高多跳自组
１网络编码技术原理
网络编码（Ｎｅｔｗｏｒｋｃｏｄｉｎｇ）从广义基金项目：
国家“８６３”计划项目
（２００６ＡＡ０１Ｚ２５７）；国家自然科学基金项目上来讲，是网络中的节点将接收到的（６０６０２０５８）
信息进行编码后再转发出去的多点
５６
中兴通讯技术
２００７年８月第１３卷第４期Ａｕｇ．２００７Ｖｏｌ．１３Ｎｏ．４
传送（Ｍｕｌｔｉｃａｓｔ）技术。多点传送（也称
组播）是网络中的一种重要的通信方式。当一个或几个节点同时向若干个其他节点发送数据时，往往要借助其他节点的传递。
在传统的网络中，作为中继的节点只能对接收到的信号进行复制、放大和转发，这对于网络资源有时候是一种浪费。网络编码技术打破了这种限制，它允许中继节点对接收到的信息进行编码，并将接收到的多个数据包按照某种特定算法重新组合再发送出去。
图１所示为一无线通信领域３节点拓扑的实例：节点Ａ、
节点Ｂ相互传递信息ａ、ｂ。图１中的箭头代表有向链路，假设每条链路的容量为“１”。
图１（ａ）采用传统的通信方式，Ａ首先向Ｓ
发送信息ａ，然后Ｂ向Ｓ发送信息ｂ，Ｓ然后依次把信息ａ和ｂ分别广播给节点Ａ和节点Ｂ。这样经过４条链路的传输节点Ｂ可以获得信息ａ，而节点Ａ可以获得信息ｂ。但是当信息ａ和ｂ准备通过节点Ｓ进行转发时，如果应用网络编码技术，将ａ和ｂ作模２和运算后直接转发出去，则在节点Ｂ处，根据接收到的信息可恢复出ａ来；同理，在节点Ａ处也可以恢复出信息ｂ来，从而可以译码得到信息ｂ。采用了网络编码技术后（见图１（ｂ）），只需要使用３条链路就可以实现传统方式的所有通信要求。
从实例可以看出，网络编码技术可以显著地提高多点传送的数据率。在一个网络中传递的信息，可以形象的称之为“流”。网络的最大流量即为从源点到收点的最大传输数据率。而广播的最大流量是指源点同时向所有收点发送同样数据时，每个收点
能接收到的最大数据传输速率。理论上讲，最大流取决于网络的拓扑结构，即各节点的连接关系和带宽。利用图论中著名的最大流最小割定理可以得到给定网络中某个源点到收点的最大流［２］。
最大流最小割定理：任何带发点
彭木根等：无线自组织网络的网络编码技术
ＺＴＥＣＯＭＭＵＮＩＣＡＴＩＯＮＳ
和收点的网络中都存在最大流和最小割，并且最大流的流值等于最小割的容量。
从图１还可以看出，一个容许的网络编码方案，必须使得收点能够从接收到的数据中恢复出原始信息，也就是说，根据接收到的数据，和已知的编码方案，可以唯一地解出原始的数据。如果把整个网络看作一个系统，源点发送的数据可以视为系统的输入，收点接收到的数据作为输出，中间每个编码节点的操作作为系统函数，则要求从源点到每个收点之间的信息传输矩阵满秩，才能够满足广播的要求。
一串数据在经过中间网络时，可能经过多次编码。一个节点如果自身不是源点，那么它发出的信息只能来源于收到的信息。因此无论怎样编码，它发出的信息量必然小于等于收到的信息量。从信息论的角度讲，数据在传输过程中每经过一个节点，其信息熵都是非增的。所以，为了保证最后传到收点处的信息熵不降低，就要求每一个中间节点在编码时，系统的传输矩阵不降秩，即无损编码。而该节点为了判断当前的编码方案是否会造成系统传输矩阵降秩，还要知道其他节点处的编码情况。这就需要整个网络的通力协作，这是迥异于传统网络的新概念。在传统的网络通信中，每个节点只知道自己和临近节点的状态，并致力于满足自身的最优化目标。但网络编码技术要求各个节点之间的合作，以保证整个通信系统的最优化。如何让各节点协同工作，并不降低编码效率和网络其他方面的性能，是网络编码算法设计的重大挑战之一。
网络编码方案可分为线性和非线性两种，其中线性方法的编码和解码都相对简单，因此，一般都倾向于采用线性方法。Ｌｉ［３］指出在有向网络中，如果一个网络编码问题有解，则一定有线性解。从理论上保证了线性算法的有效性。线性组合要求网络节
点具有更高的计算能力，然而根据摩尔定律，随着处理成本的降低，网络的“瓶颈”逐渐转向业务所需的更高的带宽支持和服务质量（ＱｏＳ）保证。网络编码实际上是用节点处理能力换取更高的网络效率。
ＡＡＡＡ
ａｂａ
ＳＳＳＳ（ａ）
ａ、ｂ：信息
Ａ、Ｂ、Ｓ：节点
ｂａｂ
ＢＢＢＢ
ＡＡＡ
ａ
ＳＳ
ａ! ｂ
Ｓ（ｂ）
ｂａ! ｂ
ＢＢＢ
▲图１无线单播系统传统传输方式与网络编码技术比较
节点中重复操作。
２．２解码过程
假设节点接收集合为（ｇ１，Ｘ１）……
（ｇｍ，Ｘｍ），为了恢复原始信息，需要求
ｉ
解｛Ｘｊ＝∑ｉ＝１ｇｉｊＭｋ｝的ｍ个等式中的ｎ个
ｎ
未知数Ｍｉ，恢复所有数据要求Ｍ≥ｎ，
２线性网络编码处理过程
线性网络编码是将节点传送信息线性映射到一个有限域内，利用线性关系实现编译码过程［４］。假设每个信息数据包为Ｌ比特，当它与要组合的数据包长度不同时，较短的信息附加额外一串“０”，将包中的ｓ个连续比特组成域上的一个符号，则一个包中包含Ｌ／ｓ个符号。在线性编码下，运用乘法和加法运算，使从节点发送出去的数据为该节点接收到信息的线性组合。
也就是说接收包的个数至少为原信息的个数。而有些线性组合可能是线性相关的，Ｍ≥ｎ并不是充分条件，但却是网络编码的重要条件。
解码需要求解一组线性方程。实际中，可以应用高斯消去的方法：节点存贮编码向量以及编码之后的结果，以行向量的形式，存储在所谓解码矩阵中。最初，解码矩阵中只包含未经该节点编码的包以及与之相对应的编码向量（如果有的话），否则为空。当接收到一个已编码包后，会从中抽取它的编码向量以及编码结果，放入到解码矩阵中。解码矩阵会经过等价变换变成行阶梯型，最终变成行最简型。所收到的某一个包如果可以增加矩阵的秩，则称之为更新包，如果所收到的包是非更新的，它可以通过等价变换变为全零，从而可以忽略。当解码矩阵变换成最简型后，方程组得解。这种情况发生在当接收到
２．１编码过程
假设一个源或多个源产生的原始数据包信息为Ｍ１……Ｍｎ，则在线性网络编码中传输的数据可表示为为
Ｘ＝∑ｇＭｉ（其中ｇ１……ｇｎ表示相应的
编码系数），对每个符号有：Ｘｋ＝∑ｇＭｋ，ｉ
ｎ
ｉ＝１ｉ
ｎ
ｉ＝１ｉ
Ｍｉｋ和Ｘｋ分别为Ｍｉ和Ｘ的第ｋ个符号。
传输的数据包中既包括编码向量，又包括信息向量，编码向量用于接收端的解码。
编码过程采用迭代的方法，若一个节点已经接收和存储的包信息集合为（ｇ１，Ｘ１）……（ｇｍ，Ｘｍ），则这个节点可以通过选定编码系数ｈ１……ｈｍ和运用算式Ｘ＇∑ｉ＝１ｈｊＸｊ得到新的信息包
ｍ
ｎ个线性独立的编码向量之后。２．３线性组合方案
设计网络编码的问题在于每个节点如何进行编码组合，目前在算法设计上，可以分为确定性编码和随机编码两种方案。
（ｇ＇，Ｘ＇），编码向量ｇ＇可以通过直接的
代数计算得到，该过程可以在若干个
（１）确定的编码方案
Ｙｅｕｎｇ［３］提出了线性网络编码的
中兴通讯技术
５７
Ａｕｇ．２００７Ｖｏｌ．１３Ｎｏ．４２００７年８月第１３卷第４期
彭木根等：无线自组织网络的网络编码技术
ＺＴＥＣＯＭＭＵＮＩＣＡＴＩＯＮＳ
叠代实现方法，通过分析网络结构，网络有着显著的差别，这主要是由无根据节点的输入输出个数设计相应线自组织网络的结构特征和无线传的局部编码向量，用迭代的方式得到输信道的时变衰落特性决定的。与通全局编码向量，从而实现网络编码；
过电缆或者光纤等可靠媒介形成固Ｋｏｅｔｔｏｒ［５］则提出了较为完备的线性网
定而独立连接的有线网络不同，无线络编码的代数实现。但他们的方法运自组织网络的节点在分布上具有多算量太高。于是Ｊａｇｇｉ［６］等人又提出了维空间上的随机特性，节点之间的连一种确定多项式－时间的编码设计算接因受节点移动或节点分布地域的法，可以为特定的广播网络找到可行限制，不但具有时间域上的时变特性的网络编码，目前已有对此算法的各而且在空间域上具有相互制约的相种改进。
关性，在信号传输上受到时变衰落信确定性的编码方案由于每个节道的影响具有时间域上的随机性和点应用的都是固定的编码向量，因此不可靠性。所以把网络编码从有线网网络中传递的数据中只需要包含信络推广到无线自组织网络，用来提高息向量，节省带宽，并且所需的符号无线网络传输的有效性和可靠性，一集比较小；但确定性的网络编码需要个首要的问题就是对承载传输业务了解全网的情况，复杂度比较高，难的无线自组织网络的结构特性和传于分布式地实现。一旦网络拓扑结构输特性进行深入透彻的认识，即加强发生了变化，就必须对整个编码方案对网络模型的提取和对网络无线传进行修改，鲁棒性比较差。
输容量的细致研究。这一研究不但在（２）随机编码方案
确立无线网络传输性能极限上具有由于确定性网络编码的以上缺重要的理论意义，而且对如何把网络点，Ｈｏ和Ｍｅｄａｒｄ等人［７］提出了随机编编码应用于无线网络中有着根本的码的概念，随机编码是让网络中的节指导作用。
点以完全独立的分布式方式，随机选目前，网络编码是国际信息论和取编码系数，对输入信息编码，并把网络理论领域所关注的热点，相关的这组随机向量作为报头的一部分发研究人员如Ｍｅｄａｒｄ、Ｅｆｆｒｏ和Ｙｅｕｎｇ等人送给收点，以便于解码。已经证明，当已经在建立网络编码的数学描述方符号集为无穷大时，采用随机编码，法等方面作了大量的工作，得到了有系统传输矩阵满秩的概率为“１”。
线网络中利用网络编码实现最大流随机编码可以分布式地实现，并传输的若干判定定理。然而，他们的可增加保密性。文献［５］提出的代数实工作主要是集中在具有固定拓扑结现的框架指出，线性网络编码可以通构和容量的有线网络上，对网络编码过随机编码有效地构建。Ｃｈｏｕ［８］应用在无线网络中的应用涉及得较少。由随机编码，提出了第一个实用的网络于有线网络中的带宽资源相对丰富，编码方案。为了保证随机编码成功概并且超高速传输对于处理的复杂度率，编码向量的符号集必须足够大，限制较低。而对于无线自组织网络，这可能会增加数据包头部的负担，因原有的关于有线网络的固定特性也此符号集的大小必须仔细选择。
不适于在任意端到端之间构造相应的网络编码，难于适合网络拓扑的变３网络编码研究现状
化。因此网络编码在无线网络中的应前期网络编码研究的背景主要用还面临着很多独特的问题。
是基于有线网络的，逐步深入的研究关于网络编码的复杂度，Ｋｏｅｔｔｏｒ展示了网络编码扩展到无线网络中在文献［５］中证明，应用他们的算法，的广阔前景。但是在网络编码的理论所用编码系数的符号集大大小于ｌｏｇ２
和应用方面，无线自组织网络与有线
（ｍｈ＋１）。其中ｈ是广播的流量，ｍ是收
５８
中兴通讯技术
２００７年８月第１３卷第４期Ａｕｇ．２００７Ｖｏｌ．１３Ｎｏ．４
点的数目。
Ｆｒａｇｏｕｌｉ［９］将其缩小到。
在文献［１０］中，作者系统地研究了网络编码的线性可解性和符号集大小的关系，并指出在某个符号集上有解的广播网络编码，在更大的符号集上未必可解。
在一个广播会话中，不是所有的中继节点都要对输入信息进行编码处理，只需在必须编码的节点处进行即可。这些必须编码的节点叫
做编码节点，在编码节点处编码后的信息输出的链路叫做编码边。在文献［１１］中，
Ｌａｎｇｂｅｒｇ等人给出了一个广播网络中
编码边数的上界和下界。不幸的是，他们还证明了确定编码边数的最小值是个非线性编程－硬（ＮＰ－ｈａｒｄ）问题。这表明，在目前任何寻找编码节点和编码边的有效算法都只能是近似的。尽管如此，选择性的编码比在所有节点都进行编码的方法系统开销还是要小得多。Ｆｒａｇｏｕｌｉ［９］提出了一种子树分解算法来寻找编码节点。
在算法设计上，
形成了两个极
端。一种是完全确定的编码方案。
Ｋｏｅｔｔｏｒ［５］提出了较为完备的线性网络
编码的代数实现。但是他们的方法运算量太高。确定性的编码方案能够保证容许性，并且所需的符号集比较小。但是确定性的网络编码需要了解全网的情况，复杂度比较高，难于分布式的实现。一旦网络拓扑结构发生了变化，就必须对整个编码方案进行修改，所以鲁棒性比较差。
由于确定性网络编码的以上缺点，后来提出了随机编码的概念。随机编码是指每个节点随机地选取一组编码向量，对输入信息进行编码，并把这组随机向量作为报头的一部分发送给收点，以便于解码。随机编码可以分布式地实现，并且可以增加保密性。随机编码可以解决分布式实现的问题，但是可能造成系统传输矩阵奇异，导致在收点无法恢复出原始数据。可以证明，当符号集为无穷大时，采用随机编码，系统传输矩阵满
彭木根等：无线自组织网络的网络编码技术
ＺＴＥＣＯＭＭＵＮＩＣＡＴＩＯＮＳ
秩的概率为“１”。
其余的算法基本上都是以上两个极端的折衷，例如可以采用半随机的编码方案。整个网络被化分成若干区域，各区域都采用随机编码，但为了保证传输矩阵满秩，区域间要相互传递信息，以使每个区域在选择编码向量时尽量不选可能导致解码失败的那些向量。为了保证随机编码成功概率，编码向量的符号集必须足够大，这可能增加数据包头部的负担，因此符号集的大小必须仔细选择。
此外，还有一些研究人员利用网络编码的思想提出了一些方案，以达到与最大流类似的最小费用、最低能量传输等网络优化目标。
对等网络（Ｐ２Ｐ）网络中，网络编码策略可以降低下载时间，在大规模的分配式Ｐ２Ｐ网络中，全局的调度非常复杂，而应用网络编码后，可以采用很简单的机制来构造随机的网络架构，提高系统性能，同时由于已编码文件块的密集性，基于网络编码的解决方案健壮性更强，例如当某种子节点过早离开时，编码机制的应用使网络信息块平等，从而可以降低信息丢失的情况。
在增大流量上，利用网络编码可以达到理论上限，可以应用于带宽有限的无线网络，利用其节点信息可以被周围邻居检测接收的特点。如图１所示，无线网络中当两个无线节点需要通过一个共同的基站来进行通信时，网络编码可以提高双向业务的网络流量，将结论推广到无线网络中的多跳路由中，两个终端节点的业务是双向的，且拥有相同的包要交换，在相邻路由器间应用轮询的时间调度，通过最初几步后，所有的中间节点都存储了要向两个方向传送的数据，当有传送机会时，路由器将要向两个方向传送的数据编码，传送出去，从而充分利用无线传输的特点；而对于接收节点，可以通过相应译码得到所需信息，信道的流量增加了一倍。网络编码还可以在组播、广播场景中应
用，于是可以用于无线格状网（Ｍｅｓｈ）、自组织（ＡｄＨｏｃ）网络及无线传感器等多跳网络中。
网络编码机制使信息更加分散，等同于将信息进行了隐藏，更难窃听，提高了信息安全性。节点需要具有译码功能，同时要求得到足够的数据才能正确解码，信息很难被窃听，同时网络编码还可以防止拥塞方面的侵害，因此，将网络编码技术应用于军事等领域，其保密性和鲁棒性方面的潜力很大。
为了不对现有网络的软硬件设备和相应的协议做很大的修改，可以选择在更高层实现网络编码。基于组播覆盖网络节点功能更强、拓扑结构易构建的特点，应用简单的编码策略就可以提高网络容量和降低信息传输时延。基于这种思想，可以考虑在无线传感器网络，无线Ｍｅｓｈ网络中应用网络编码，有效降低成本。
码节点就不太适合。因此，无线网络中主要考虑节点能量及稳定性的影响，选择编码节点或设计网络拓扑时应尽可能将节点能量较高、具有较强的运算速度和较大的缓存空间的节点，以提高网络的鲁棒性。
４．２网络编码算法的设计
目前网络编码主要有确定性和随机性两种编码方案，分别用于不同的网络应用与构架上，这些方案主要是基于理论上的分析和实现，因此在实际网络上需要针对不同的应用设计相应的编码方式：如对于结构较小的网络，可以选择比较简单的确定性算法，编码过程中甚至可以通过转换为对数，将乘法运算转换成加法运算，降低总的编码复杂度；而对于无线网络，则应用随机编码机制是主要的研究趋势，即令中间节点随机生成编码系数，对节点所有的可用信息应用线性编码，并随时更新编码系数，文献［５］已经证明，当符号集为无穷大时，采用随机编码，系数传输矩阵满秩的概率是“１”，即编码成功的概率很大，但同时会增大数据报头的负担，因此符号集的大小需要权衡各种因素。
４网络编码的研究热点
作为一种新型的网络传输技术，网络编码的优点不言而喻。但到目前为止，对这一领域的研究还主要集中在理论方面以及应用中局限性的分析方面。
４．１网络编码节点选取方案
在确定的网络结构中，并不是所有的节点都需要进行网络编码，而是选取其中需要编译码的节点，给予编译码功能，对于不需要编译码的节点，只要具有传统的存储转发功能即可。这样不仅可以降低编码算法的复杂度，也减小了对硬件的要求，从而使得网络编码的应用更为广泛。文献
４．３网络编码复杂度的分析
网络节点编码过程中会涉及到大量的乘法与加法运算，需要较大的计算复杂度，而接收节点译码过程若应用高斯消除方法，也是较大的运算过程。接收节点个数和节点信息块大小共同决定了编码符号集的最低门限。对于确定性编码而言，所需的符号集可以较小，编码的复杂度较低，但这种机制需要有中心节点集中控制网络信息，对于网络编码的很多应用场景以及网络构架都不适用，但可以通过对其相应的复杂度分析，来设计合适的编码算法从而降低网络的复杂度；对于随机网络编码而言，所需的符号集较大，而且节点在传送信息的同时传送系数向量，虽然系数向
［１２］根据网络拓扑结构，利用一种子
树分解算法来寻找编码节点。将该算法应用于有线网络中并使用确定的网络编码机制，效果较好；但对于无线网络，节点之间的连接关系更为复杂，并且节点传输覆盖范围内的节点都可能接收到网络信息，导致拓扑结构更为紧密，则应用上述方法选择编
中兴通讯技术
５９
Ａｕｇ．２００７Ｖｏｌ．１３Ｎｏ．４２００７年８月第１３卷第４
期
彭木根等：无线自组织网络的网络编码技术
ＺＴＥＣＯＭＭＵＮＩＣＡＴＩＯＮＳ
量相对于信息而言较小，但同样会占安全性的影响，从而针对不同的系统用较大的带宽，因此需要设计合适的应用选用合适的编码算法，以提高网算法，保证在提高编码增益的同时降络安全性能，这对于无线通信具有重低复杂度。网络编码复杂度要受到符要意义。
号集大小、节点计算复杂度、网络编码方案等诸多因素的影响，需要全面４．６网络编码在无线分布式网络中
分析得出。
的应用
对网络编码技术的研究需要在４．４网络编码的性能分析和应用
加深理论研究的同时，考虑实际的应网络编码机制可以提高网络容用场景，侧重解决实际应用中遇到的量。已经证明应用网络编码，可以达问题，比如需要降低编码复杂度，需到香农极限。网络编码通过编码节点要考虑系统本身的延时以及网络编对输入信息线性或非线性的编码处码带来的延时影响等。网络编码在无理，可以在不提高消耗带宽的情况线通信网络当中的应用是一片亟待下，使不同的信息同时通过有限的链开发的热土，一方面无线网络的广播路，从而提高网络流量。对于无线网特性非常利于网络编码的应用；另一络中的网络编码性能进行分析则需方面，相对于有线网络而言，无线网要应用网络信息论的知识，建立合适络中的节点不可能同时监听来自多的网络容量模型来进行容量分析。
个源的信息，对网络编码的应用造成网络编码导致编解码的过程中了一定的阻碍。如何结合无线分布式可能会产生编译码错误，这将增大网网络的特点扬长避短，找到能够最大络数据传输的误码率。而就网络编码程度发挥网络编码优势的结合点，是本身而言，对误码率有着相当苛刻的需要考虑的主要问题。
要求，只有较小的误码率才能保证网络编码的有效性和可靠性，否则使用５结束语
网络编码可能还会带来系统整体性网络编码作为一种新型的信息能的降低。因此，如何设计可靠的网处理技术已经得到广泛的研究，本文络编码方案以保证数据传输较低的在综合介绍了线性网络编码的产生误码率，并尽可能地采用相应技术减背景和原理及编译码方案后，讨论了少误码率对网络编码方案的影响是网络编码的优点和应用场景，并介绍网络编码研究所必需的。
了网络编码的研究热点，随着更多学者对该领域的深入研究，网络编码技４．５网络编码与系统安全性分析
术在未来通信中必将得到广泛应用。
网络编码不仅可以提高节点间传输效率和网络吞吐量，还会对网络６参考文献
的安全性能产生影响。一方面，由网［１］ＡｈｌｓｗｅｄｅＲ，ＣａｉＮ，ＬｉＳＹＲ，ＹｅｕｎｇＲＷ．络编码导致的信息的分散性和编译Ｎｅｔｗｏｒｋｉｎｆｏｒｍａｔｉｏｎｆｌｏｗ［Ｊ］．ＩＥＥＥ
ＴｒａｎｓａｃｔｉｏｎｓｏｎＩｎｆｏｒｍａｔｉｏｎＴｈｅｏｒｙ，２０００，４６：码特性增加了信息破译难度，对安全１０１６－１０２４．
性而言是一种改善［２］谢政，李建平．网络算法与复杂性理论［Ｍ］．国
；另一方面，对确防科技大学出版社，１９９５（５）．
定性编码算法而言，由于传输过程中［３］ＬｉＳＹＲ，ＹｅｕｎｇＲＷ，ＣａｉＮ．Ｌｉｎｅａｒｎｅｔｗｏｒｋｃｏｄｉｎｇ［Ｊ］．ＩＥＥＥＴｒａｎｓａｃｔｉｏｎｓｏｎＩｎｆｏｒｍａｔｉｏｎ将涉及较多的节点数目，以及编码算Ｔｈｅｏｒｙ，２００３，４９：３７１－３７９．
法方案的确定性，会导致系统的安全［４］ＣｈｒｉｓｔｉｎａＦｒａｇｏｕｌｉ，Ｊｅａｎ－ＹｖｅｓＬｅＢｏｕｄｅｃ，ＪｏｒｇＷｉｄｍｅｒ．Ｎｅｔｗｏｒｋｃｏｄｉｎｇ：ａｎｉｎｓｔａｎｔ性能的降低。因此编码算法的设计中Ｐｒｉｍｅｒ［Ｊ］．ＩＥＥＥＴｒａｎｓａｃｔｉｏｎｓｏｎＩｎｆｏｒｍａｔｉｏｎ也需要考虑系统的安全性能Ｔｈｅｏｒｙ，２００２，４８：２７１－２７７．
，通过对［５］ＫｏｅｔｔｅｒＲ，ＭｅｄａｒｄＭ．Ａｎａｌｇｅｂｒａｉｃａｐｐｒｏａｃｈ不同的编码算法进行恰当的安全性ｔｏｎｅｔｗｏｒｋｃｏｄｉｎｇ［Ｊ］．ＩＥＥＥ／ＡＣＭ
ＴｒａｎｓａｃｔｉｏｎｓｏｎＮｅｔｗｏｒｋｉｎｇ，２００３（１０）：能分析，来确定不同网络算法对系统
１０３１－１０４２．
６０
中兴通讯技术
２００７年８月第１３卷第４期Ａｕｇ．２００７Ｖｏｌ．１３Ｎｏ．４
［６］ＪａｇｇｉＳ，ＳａｎｄｅｒｓＰ，ＣｈｏｕＰＡ，ＥｆｆｒｏｓＭ，ＥｇｎｅｒＳ，ＪａｉｎＫ，ＴｏｌｈｕｉｚｅｎＬ．Ｐｏｌｙｎｏｍｉａｌｔｉｍｅａｌｇｏｒｉｔｈｍｓｆｏｒｍｕｌｔｉｃａｓｔｎｅｔｗｏｒｋｃｏｄｅｃｏｎｓｔｒｕｃｔｉｏｎ［Ｊ］．ＩＥＥＥＴｒａｎｓａｃｔｉｏｎｓｏｎＩｎｆｏｒｍａｔｉｏｎＴｈｅｏｒｙ，２００３，４９：８３１－８３６．
［７］ＨｏＴ，ＫｏｅｔｔｅｒＲ，ＭｅｄａｒｄＭ，ＥｆｆｒｏｓＭ，ＳｈｉＪ，ＫａｒｇｅｒＤ．Ｔｏｗａｒｄａｒａｎｄｏｍｏｐｅｒａｔｉｏｎｏｆｎｅｔｗｏｒｋｓ［Ｊ］．ＩＥＥＥＴｒａｎｓａｃｔｉｏｎｓｏｎ
ＩｎｆｏｒｍａｔｉｏｎＴｈｅｏｒｙ，２００４，５０：５３２－５３７．［８］ＣｈｏｕＰＡ，ＷｕＹ，ＪａｉｎＫ．Ｐｒａｃｔｉｃａｌｎｅｔｗｏｒｋｃｏｄｉｎｇ［Ｊ］．ＡｌｌｅｒｔｏｎＣｏｎｆｅｒｅｎｃｅｏｎ
Ｃｏｍｍｕｎｉｃａｔｉｏｎ，Ｃｏｎｔｒｏｌ，ａｎｄＣｏｍｐｕｔｉｎｇ，Ｍｏｎｔｉｃｅｌｌｏ，ＩＬ，２０００，（１０）．
［９］ＦｒａｇｏｕｌｉＣ，ＳｏｌｊａｎｉｎＥ．Ｉｎｆｏｒｍａｔｉｏｎｆｌｏｗ
ｄｅｃｏｍｐｏｓｉｔｉｏｎｆｏｒｎｅｔｗｏｒｋｃｏｄｉｎｇ［Ｊ］．ＩＥＥＥＴｒａｎｓａｃｔｉｏｎｓｏｎＩｎｆｏｒｍａｔｉｏｎＴｈｅｏｒｙ，２００４，５０：６３３－６３８．
［１０］ＤｏｕｇｈｅｒｔｙＲ，ＦｒｅｉｌｉｎｇＣ，ＺｅｇｅｒＫ．Ｌｉｎｅａｒｉｔｙ
ａｎｄｓｏｌｖａｂｉｌｉｔｙｉｎｍｕｌｔｉｃａｓｔｎｅｔｗｏｒｋｓ［Ｊ］．ＩＥＥＥＴｒａｎｓａｃｔｉｏｎｓｏｎＩｎｆｏｒｍａｔｉｏｎＴｈｅｏｒｙ，２００４，５０：５３８－５４９．
［１１］ＬａｎｇｂｅｒｇＭ，ＳｐｒｉｎｔｓｏｎＡ，ＢｒｕｃｋＪ．Ｔｈｅ
ｅｎｃｏｄｉｎｇｃｏｍｐｌｅｘｉｔｙｏｆｎｅｔｗｏｒｋｃｏｄｉｎｇ［Ｊ］．ＥＴＲ０６３，ＣａｌｉｆｏｒｎｉａＩｎｓｔｉｔｕｔｅｏｆＴｅｃｈｎｏｌｏｇｙ，２００５，１２０：８８－９６．
［１２］ＣｈｒｉｓｔｉｎａＦｒａｇｏｕｌｉ，ＥｍｉｎａＳｏｌｊａｎｉｎ．Ａ
ｃｏｎｎｅｃｔｉｏｎｂｅｔｗｅｅｎｎｅｔｗｏｒｋｃｏｄｉｎｇａｎｄｃｏｎｖｏｌｕｔｉｏｎａｌｃｏｄｅｓ［Ｊ］．ＩＥＥＥ
ＣｏｍｍｕｎｉｃａｔｉｏｎｓＳｏｃｉｅｔｙ，２００４，７０：１５６－１６７．
收稿日期：２００７－０４－０９
彭木根，北京邮电大学电信
工程学院博士毕业，毕业后留校任教。目前正负责和承
担国家“８６３”计划项目、
国家自然科学基金项目以及国际／国内著名设备制造商和运营商的多个科研项目。研究兴趣包括无线网络协同信息论、下一代无线宽带通信系统无线资源管理算
法和协议设计、多跳无线中继和网络编码等。已出版著作４本、译著２本，发表论文６０余篇，其中２０余篇被ＳＣＩ和ＥＩ收录。
王月新，北京邮电大学电信工程学院无线信号处理与网络实验室在读硕士研究生。研究方向为无线Ｍｅｓｈ网络关键技术和网络编码技术研究。
王文博，北京邮电大学电信工程学院院长、教授、博士生导师。长期从事移动通信无线传输理论和技术研究、无线通信网络理论研究以及数字信号处理与软件无线电理论研究。已在国内外学术期刊和国际学术会议上发表论文１００余篇，出版专著和教材５部。