范在山1，张祖凡1，吴爱爱1，蒋劲松

(1.重庆邮电大学 通信与信息工程学院，重庆 400065；2.四川省鼎讯科技有限公司，成都 610041)

1 引 言

网络编码的核心思想是网络中参与传输的节点上输出的数据，可以通过该节点多条输入上传输的数据的某种线性或非线性变换而得到，且参与传输的所有节点对数据变换可以保证最终所有接收节点正确恢复出信源所发送的信息。在一定程度上也可以认为它是一种融合了编码和路由的交换传输技术。

在实际应用网络中，人们为了信息分析、信息安全以及交换的目的，总是要在中间节点进行某种形式的数据处理，而传统的路由方案并不支持这一需求。2000年，香港中文大学蔡宁、李硕彦和杨伟豪教授首次提出了网络编码[1]，推翻了原有路由机制单一复制转发的传输方式，并从理论上分析和验证了它对通信系统的影响。特别是在无线通信网络中，基于无线信道的广播特性，利用相邻节点间的协作对传输数据进行网络编码操作，可以在一定程度上节约无线资源[2]；当网络部分节点或链路失效时采用随机线性网络编码[3]，可以在目的节点仍能恢复原始数据，增强网络的容错性和鲁棒性等。

在下一代移动通信网中，IMT-Advanced系统设计的峰值传输速率高达100 Mbit/s～1 Gbit/s，小区平均频谱效率下行高于3 bit/s·Hz-1,上行高于2 bit/s·Hz-1,小区边缘频谱效率不小于1 bit/s·Hz-1,其用户数量也将比以往的系统高一个数量级。网络编码作为下一代移动通信的关键技术之一，在一定程度上可节省网络的资源消耗，提高频谱资源利用率，并在有限的频谱资源中尽可能多地传输数据，可以增加信道的传输容量，完全满足LTE-A中的技术要求。与此同时，网络编码作为未来无线网络的“绿色技术”之一，在差错控制[4]、节能[5]、干扰消除、提高网络安全[6]等方面起着至关重要的作用。

综上所述，网络编码的应用给现有的网络带来了革命性的变革，它可以改善网络性能，改变网络结构和协议。目前，国内外很多学者和科研机构都致力于网络编码的研究工作，从网络信息流的研究一直到与MIMO技术以及协同技术的结合，不断地促进了网络信息论的发展。本文跟踪了网络编码的发展历程，并根据未来通信网复杂的无线环境评述了今后该领域的研究方向。

2 网络编码基本原理及构造方案

网络编码的基本特征是在网络层对传输的信息进行智能化处理，包括采用各种编码策略。因此，当给定一个组播网络时，如何设计网络编码方案实现最大流传输是一个很重要的问题[2-4]。目前最常用的是随机线性网络编码策略。

2.1 网络编码基本原理

本文将以“蝶型网络[7]”模型为例，具体阐述网络编码的基本原理。如图1所示，设每一个有向链路的容量为1 bit。根据“最大流最小切割定理[1]”，网络传输的最大流为2。图1(a)表示的是传统的路由传输方案，节点c只有存储和转发功能，只能在2 s内依次把信息b1和b2转发给汇点。图1(b)表示的是网络编码方法，节点c收到b1和b2后进行异或编码[8]，将b=b1⊕b2传送到汇点，在接受节点通过异或的加减法定理译出b1和b2。图1(a)中从源s到接收节点的最大信息传输速率为1.5 bit/s；图1(b)中,接收节点可以同时恢复出信息b1和b2，其信息流速率为2 bit/s，带宽利用率提高了33%。网络编码使信息在传输过程中均匀分布于整个网络，有效解决了网络拥塞和传输瓶颈问题，从而使网络负载得到均衡。此外，网络编码可以实现基于接收者的组播链路失效恢复，从而预防网络链接失效对网络链接的影响，提高网络的鲁棒性[9]。而网络编码的吞吐量是传统编码的Ωlg|V|倍，其中Ω是信源符号的全空间，|V|表示通信网络中节点个数[9-10]。由此可知，中间节点c所采用的编码策略属于线性网络编码方案。另外，在c点还可以采用非线性网络编码和随机线性网络编码等方案。

(a)传统路由传输方案

(b)网络编码方法

2.2 (非)线性网络编码

线性网络编码[11]的中心思想是在中间节点对来自不同链路的信息流进行线性组合后再转发，将节点传送信息线性映射到一个有限域内，实现最大流的信息传输[12]。在无环网络中，通过线性编码组播传输原始数据包的线性组合向量，并在目的节点提取更新编码系数译出原始信息。对于有环网络[13]，引入时间延迟指标，将有环网络转化成等价的无环网络进行编码。典型的编码算法有贪婪算法[11]、指数时间算法[14]、多项式时间算法[15]等。相对而言，非线性网络编码可以在某些信道或网络中弥补线性网络编码的不足[16]，如在有噪信道中可以有效降低失真，提供更好的网络性能[17]。

2.3 随机网络编码

随机网络编码[12]就是每个网络节点独立地随机选取一种映射方式将自己接收到的输入信息映射到相应的输出链路上。通常情况下，该映射方式选取线性映射，即在一个有限域Fq内每个输入信息流选取相应的加权系数。用此方案进行组播数据时，目的节点可以成功译码的概率至少为(1-d/q)η，特别是网络规模较大时，其中d为接收节点数，η是转接输入信号的随机组合的链路数。目前它已被广泛用于多播[18]、中继[19]等网络中，用来提高网络的传输容量、系统吞吐量等性能。此外，还有几种实用性相对较差的编码策略，比如代数法[14]、信息流法[20]以及确定性网络编码[21]，由于其可扩展性差、运算复杂度高等因素，在网络编码中很少被用到。

传统的网络编码中，使用机会调度策略，充分利用延迟时间传输数据实现信息流的“匹配”，从而提高网络吞吐量[12,22]，但是它并不能实现节点的最大吞吐量。在无线网络中，由于信道的衰落、噪声、干扰等特性，传统的编码方案在分集增益、误码率以及系统吞吐量等方面显示出了它的不足。

3 联合网络编码

本节将从物理层的角度对网络编码进行分析，并将其与信道的编译码技术[23-29]、纠错技术[30-31]以及各种传输技术相结合，更好地提高系统的吞吐量、数据传输速率，并有效地降低误码率以及编译码的复杂度和时延。

3.1 网络编码与信道编译码的联合设计特性

网络编码同信道编译码结合的基本思想就是利用网络编码的冗余支持信道编码从而获得好的抗噪声性能和误码率，达到最大信道容量，并充分利用中继传输的额外冗余度获得分集增益[26]。基于Turbo[28]码和低密度奇偶校验码(LDPC)[32]的联合编码被广泛研究，并在多址中继信道[26]、时分复用双向中继信道[27]以及BSC和加性高斯白噪声信道(AWGN)[25]中与传统的网络编码方案进行了比较，显示了联合编码在能量消耗、判决检测以及信道容量和误码率方面的优势，有效降低了编码的复杂度和由信道噪声带来的失真。

与分离编码方案相比，它在中间节点对接收信号分别进行软检测估计后再进行软网络编码和软维特比译码，能够在高速编码的情况下减少信息损失以保证网络的信道容量和误比特率性能。如在AWGN信道[25]中信息流在信道译码前进行了组合使得错误概率增加，信道容量减小，随着信噪比的增加而不断改善，最终近似于传统的网络编码，但是联合编译码的计算复杂度降低了50%。为了降低错误概率，在信道编码阶段可以采用卷积码与H-ARQ[31]结合，在中间节点进行软结合和检测，对所接收数据的估计值进行网络编码，并广播到两个接收节点进行迭代译码[27]。

3.2 物理层网络编码与信道译码的联合设计

物理层网络编码(PNC)[23]主要是针对无线通信系统提出的，它能充分利用无线传播的信息广播特性来提高无线网路中的信道容量。无线通信的信息传输载体(电磁波)在传输过程中会产生干扰而导致信号间的混乱，基于EM信号的相加特性，物理层网络编码可以将电磁波信号映射为数据比特流，则干扰就变成了网络编码中的算术问题。

在双向中继信道中[24]，采用PNC方案并把双向信道分为多址接入信道和广播信道。通过多址信道中的映射和线性信道编码可以分别达到信道容量上限和下限，在信噪比高于5 dB时上下限会重合，与传统网络编码和简单网络编码方案相比物理层网络编码的信道容量增益分别为3/2和2。在多跳网络中，物理层网络编码可以分别实现100%和50%的吞吐量增加[23]。

在多址信道中[29]物理层网络编码与信道译码相结合，利用电磁波的相加特性和Turbo码与网络编码的线性特性直接对网络编码的码字进行估计。如图2所示，在节点1和3分别进行Turbo编码和调制，然后再进行相加；而在中间节点进行软判决检测得到检测信号的最大似然比L(*)，再通过Turbo译码器得出网络编码的估计码字。与传统的编码方案相比，此方案不仅降低了计算的复杂度而且还改善了误比特率、信道容量和信噪比。此外，在目的节点还可以获得额外的分集增益，而由于电磁波的相加特性系统的吞吐量也得到了进一步提高。

图2 物理层网络编码与信道编码联合设计方案

4 基于MIMO和协作分集技术的网络编码

在新一代无线移动通信系统中，面对复杂的无线场景和信道的衰落特性，网络编码与无线协作分集技术、MIMO技术相结合，在提高系统吞吐量、信道容量和分集增益等方面具有广阔的前景。

4.1 基于协作分集技术的网络编码

协作分集技术是通过节点间的协作，获得较大的分集增益，克服无线信道衰落，实现了所谓“虚拟天线阵列”的功能，极大地改善了无线通信系统抗衰落性能，提高了资源效率和系统容量[33]。另外，在协作分集的基础上进行网络编码可以同时获得分集增益和网络编码增益。在考虑只有源节点A和B和目的节点C的模型中，节点A和B互相协作中并将数据包传输到目的节点C。发送节点A和B将接收到来自协作节点的信息(中继信息)，经检测译码后与本地信息相结合(网络编码和)。接收节点则根据来自节点A和B中的网络码字以及信息的先验概率进行检测译码，恢复出所需信息[34]。此方案充分利用了网络资源和分集技术，可获得相对较低的错误概率中断概率，以及较高的编码增益，使得数据可以在衰落信道中能够更好地传输。

4.2 基于MIMO的网络编码

MIMO技术是利用多个发送和接收天线获得分集增益，改善信道的多径衰落特性，提高系统的容量、频谱利用率以及数据传输速率。而网络编码(NC)在多径信道下由于信道的衰落和电磁干扰等，丢包率会很大，这就会导致译码器的错误译码。基于这两种技术的共同目的和系统的相似性，将网络编码和MIMO技术(MIMO-NC)在物理层相结合，通过在不同的包内编码相同的信息，并利用获得的冗余度将接收到的能量传递给译码器，更好地完成检测译码过程，获得大的信噪比增益，增强系统的鲁棒性，降低丢包率和误比特率。

MIMO-NC方案[35]包括两个阶段：

(1)编码过程：每个节点将缓存器中的信息单元进行网络编码，产生编码包。这些编码包是Galois符号序列，通过转换调制进行发送；

(2)译码过程：在接收端将收到的矢量(数据包)存入缓存器并更新和提取相应的编码系数，最终通过软译码方案恢复出原始信息。

其编译码流程如图3所示，其中x1，x2，x3，…，xp是由源节点传输到网络中的信息单元(IUs)，gnp为编码系数，{bn,1，bn,2，…，bn,8}是一个Galois符号dn所对应的一个调制后的矢量sn，y1,y2,…,yN是在不同的时间接收端所接收的来自不同信源的编码包。

图3 MIMO-NC编译码流程图

为了获得高于网络编码的分集和编码增益，在编码阶段可以采用两个网络编码器，有两个生成系数矩阵G1和G2，它们编码相同的信息，编码包的头部存储编码系数，且这些编码包是Galois符号序列，通过转换和QPSK调制，两个编码器产生的符号序列分别作为实部和虚部再通过调制发送出去。高分集增益的获得是以传输速率的降低为代价的。译码阶段采用自适应MIMO-NC技术，就是为了降低错误概率，改善传输速率[36]，但复杂度有所增加。

MIMO技术与网络编码的结合是一种新型技术，在各种无线传播环境下，它充分利用网络编码提供的冗余度和MIMO技术的高分集增益提高系统性能，为未来的网络编码和基于网络编码的数据传输方面的研究铺平了道路。

5 网络编码的进一步发展方向

网络编码作为通信网络中的信息处理和传输理论研究的重大突破，具有重要的理论价值和广阔的应用前景，已被认为是LTE-A的关键技术之一。新一代宽带无线移动通信网的网络架构是一个复杂、多元化的架构，这一方面体现在网络层次/基本构架方面，另一方面也体现在包括复杂的无线场景/传播环境和混合的无线小区结构等。如何在新的环境下提高系统吞吐量和信道容量，降低传输误码率等，是目前的研究热点问题。LTE-A中采用MIMO分集技术，改善信道的特性，抑制衰落，并在物理层通过与网络编码的结合改善了系统的传输性能。为此，可以在MIMO-NC的基础上从以下几个方面进一步研究适合于新一代宽带无线移动通信网的网络编码技术：

(1)结合多输入多输出天线，研究不同无线场景/传播环境研究网络编码。充分研究无线场景/传播环境对网络中数据流传输的影响，研究有效的译码算法，特别是研究网络编码中最小代价函数问题，从而反演研究低复杂度、低时延的网络编码；

(2)研究基于不同无线场景/传播环境和协作技术的网络编码。研究基于MIMO或协作技术的物理层网络编码和信道编码的联合设计算法和方案，寻求低复杂度、更小代价函数的网络编码算法。为了节省传输能量的消耗需要对编码节点以及传输路径选择，采用最短路径进行传输；

(3)结合无线传播特性，尤其是考虑无线传播过程的遮挡物而引起的信道特性的变化，从而导致网络容量的变化。考虑将无线信道中的障碍物等作为无线传输中的一个节点，利用网络最大流定理，进行网络编码研究，特别是研究这些“节点”对传输过程中的数据速率的影响，同时引入分布式编码技术，研究网络信道容量最大化问题，从而有效利用网络带宽，提高系统吞吐量等。

6 结束语

网络编码作为一项新兴技术，从理论到实际应用都还处在不断完善和丰富的阶段。本文重点讨论了网络编码的优缺点和发展现状。随着更多学者对该领域的深入研究，网络编码技术在新一代无线移动通信网中将起到关键性的作用。上述问题的深入研究必将促进网络编码理论和应用的发展，从而推动网络信息论乃至整个通信网络的发展。

参考文献：

[1] Ahlswede R, Cai N, Li S-Y, et al. Network information flow [J]. IEEE Transactions on Information Theory, 2000, 46(4):1024-1216.

[2] Widmer J,Fragouli C, Le Boudec,et al. Low-complexity energy-efficient broadcasting in wireless ad-hoc networks using network coding[C]//Proceedings of Workshop on Network Coding,Theory,and Application(NetCod 2005). Riva del Garda,Itlay:[s.n.],2005.

[3] Ho Tracy, Medard M,Ralf K,et al. A Random Linear Network Coding Approach to Multicast [J]. IEEE Transactions on Information Theory, 2006, 52(10):4413-4430.

[4] Cai Ning, Yeung R W. Network Coding and Error Correction[C]//Proceedings of Workshop on Information Theory.[S.l.]:IEEE,2002: 119-122.

[5] Wang Suyu, Gao Xuejuan,Zhuo Li. Survey of network coding and its benefits in energy saving over wireless sensor networks [C] //Proceedings of 7th International Conference on Information, Communications and Signal Processing(ICICS 2009).[S.l.]:IEEE,2009:1-5.

[6] Cai Ning, Yeung R W. Secure Network Coding[C]//Proceedings of IEEE International Symposium on Information Theory(ISIT2002).Lausanne,Switzerland:IEEE,2002:323.

[7] Yang Min,Yang Yuanyuan. A Linear Inter-Session Network Coding Scheme for Multicast [C] //Proceedings of the 7th IEEE International Symposium on Network Computing and Applications.[S.l.]:IEEE,2008:117-184.

[8] Sachin Katti, Hariharan Rahul, Wenjun Hu, et al. XORs in The Air: Practical Wireless Network Coding [J]. IEEE/ACM Transactions on Networking,2008,16(3):497-510.

[9] Ho T,Karger D,Medard M,et a1. The benefits of coding over routing in a randomized setting[C]//Proceedings of IEEE International Symposium on Information Theory (ISIT '04). Chicago, IL:IEEE,2003:442-447.

[10] Keshavarz-Haddadt A,Riedi R.Bounds on the Benefit of Network Coding:Throughput and Energy Saving in Wireless Networks[C]//Proceedings of the 27th Conference on Computer Communications.Phoenix,AZ:IEEE,2008:376-384.

[11] Li S-Y R, Yeung R W,Cai N. Linear Network Coding [J]. IEEE Transactions on Information Theory,2003,49(2):371-381.

[12] 樊平毅. 网络信息论 [M]. 北京：清华大学出版社，2009:109-146.

FAN Ping-yi.Network Information Theory[M].Beijing:Tsinghua University Press,2009: 109-146.(in Chinese)

[13] Wang Liang, Huang Jiaqing,Li Hui. Applying Network Coding to Cyclic Networks [C]// Proceedings of the 28th IEEE International Conference on Computer Communications Workshops. NJ, USA:IEEE,2009:321-322.

[14] Koeter R,Medard M. An Algebraic Approach to Network Coding [J].IEEE/ACM Transactions on Networking,2003,11(5):782-795.

[15] Sanders P,Egner S,Tolhuizen L. Polynomial time algorithms for network information flow[C]//Proceedings of 15th Annual ACM Symposium on Parallel Algorithms and Architectures.San Diego,California,USA:ACM,2003:286-294.

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

[17] Joda R， Lahouti F. Nonlinear network code design for the multiple access relay channel [C]//Proceedings of the 24th Biennial Symposium on Communications.Kingston,Ontario,Canada:IEEE,2008:13-16.

[18] Dong Nguyen,Tuan Tran, Thinh Nguyen,et al. Wireless Broadcasting Using Network Coding [J]. IEEE Transactions on Vehicular Technology, 2009,58(2):914-925.

[19] Pu Wei,Lu Chong,Li Shi-peng, et al. Continuous Network Coding in Wireless Relay Networks [C]//Proceedings of the 27th Conference on Computer Communications(IEEE INFOCOM). Phoenix, AZ:IEEE,2008:1526-1534.

[20] Fragouli C,Soljanin E. Information flow decomposition for network coding [J].IEEE Transactions on Information Theory,2006,52(3):829-848.

[21] Fragouli C,Soljanin E. Decentralized network coding [C]//Proceedings of IEEE Information Theory Workshop.[S.l.]:IEEE,2004: 310-314.

[22] Fasolo E,Rossi M,Widmer J,et al. On MAC Scheduling and Packet Combination Strategies for Practical Random Network Coding [C]//Proceedings of IEEE International Conference on Communications. Glasgow, UK:IEEE,2007:3582-3589.

[23] Zhang S, Liew S, Lam P. Physical layer network coding[C]//Proceedings of ACM International Conference on Mobile Computing and Networking(MobiCom’06).Los Angeles,CA,USA:ACM,2006: 358-365.

[24] Popovski P,Yomo H. Physical Network Coding in Two-Way Wireless Relay Channels[C]//Proceedings of IEEE International Conference on Communications.[S.l.]:IEEE,2007: 707-712.

[25] Zhang Shengli,Zhu Yu，Liew Soung-Chang，et al. Joint Design of Network Coding and Channel Decoding for Wireless Network[C]//Proceedings of IEEE Wireless Communications and Networking Conference.[S.l.]:IEEE,2007: 779-784.

[26] Hausl C， Dupraz P. Joint Network-Channel Coding for the Multiple-Access Relay Channel[C]//Proceedings of the 3rd Annual IEEE Communications Society on Sensor and Ad Hoc Communication and Networks.[S.l.]:IEEE,2006: 817-822.

[27] Hausl C,Hagenauer J. Iterative Network and Channel Decoding for the Two-Way Relay Channel[C]//Proceedings of IEEE International Conference on Communications. [S.l.]:IEEE,2006: 1568-1573.

[28] Zhao B,Valenti M C. Distributed turbo coded diversity for the relay channel [J]. Electronic Letters, 2003, 39(10):786-787.

[29] Ao Zhan,Chen He. Joint Design of Channel Coding and Physical Network Coding for Wireless Networks[C]//Proceedings of International Conference on Neural Networks and Signal Processing. [S.l.]:IEEE,2008:512-516.

[30] Silva D,Kschischang F R.Adversarial Error Correction for Network Coding:Models and Metrics[C]// Proceedings of the 46th Annual Allerton Conference on Communication,Control,and Computing.[S.l.]:IEEE,2008:1246-1253.

[31] Dong Nguyen, Tuan Tran, Bose B, et al. Hybrid ARQ-Random Network Coding for Wireless Media Streaming[C]// Proceedings of the 2th International Conference on Communications and Electronics (ICCE). [S.l.]:IEEE,2008:115-120.

[32] Razaghi P, Yu W Bilayer. Low-Density Parity-Check Codes for Decode-and-Forward in Relay Channels [J] . IEEE Transaction on Information Theory, 2007,53(10):3723-3739.

[33] Hunter T E,Nosratinia A. Diversity through Coded Cooperation [J].IEEE Transactions on Wireless Communications,2006,5(2):283-289.

[34] Lei Xiao,Fuja T,Kliewer J,et al. A Network Coding Approach to Cooperative Diversity[J]. IEEE Transaction on Information Theory, 2007,53(10):3714-3722.

[35] Fasolo E,Rossetto F,Zorzi M. Network Coding meets MIMO[C]//Proceedings of the Fourth Workshop on Network Coding,Theory and Applications.[S.l.]:IEEE,2008:1-6.

[36] Fasolo E， Rossetto F, Zorzi M. On encoding and rate adaptation for MIMO-NC [C]// Proceedings of the 3rd International Symposium on Communications, Control, and Signal Processing. [S.l.]:IEEE,2008: 741-746.