无线通信中的网络编码技术*

王亨友，彭木根，王文博，邬贺铨

（北京邮电大学 北京 100876）

无线通信中的网络编码技术*

王亨友，彭木根，王文博，邬贺铨

（北京邮电大学 北京 100876）

网络编码是一种提高网络吞吐量和性能的新技术，预计将成为未来网络的一项关键技术。本文概述了无线网络中的网络编码技术，无线网络被认为是网络编码最可能得到应用的领域之一，网络编码技术使无线媒质的广播属性可以得到充分利用，无线网络和传感器网络为网络编码的应用提供了巨大的机会。本文结合不同无线场景介绍了网络编码的各种编码方法，包括传统的网络编码、物理层网络编码、模拟网络编码以及复数域网络编码，并对未来发展给出了展望。

无线网络编码；数字网络编码；物理层网络编码；有限域网络编码；复数域网络编码

[1]首次引入了网络编码概念，用于卫星通信网络，在参考文献[2]中得到完善的发展，并首次阐述了网络编码相对于传统的存储转发方式的优势，这就驳斥了之前的观点，即在中间节点只需作数据复制而没有必要进行数据处理，参考文献[3,4]证明了网络编码的构造可以分别通过线性组合和有限域来实现。

参考文献[2]和[3]研究了多播网络的网络容量以及涉及割集的容量，描述了多播网络的可容许编码速率区，证明了网络的最大吞吐量可以通过使用编码来实现。参考文献[2]发展的卷积码属于非线性网络编码，适用于多源情况，但是这种非线性码的复杂度太大。针对单源的多播网络，Li等人在参考文献[3]深入研究了线性网络编码。线性编码是所有最简单的编码方案之一，在线性编码中，节点的编码是采用传入数据的线性组合，即，线性编码将一组数据看作某一特定基本域上的一个向量，且允许一个节点在将一个向量传递之前对向量应用线性变换，证明了每一接收机的最大流（上限）可以实现。作者严谨地阐述了这种多播问题并证明了线性编码足以实现最优的多播容量，即从源节点到每一接收节点的最大流。

参考文献[4]中，Koetter等人深入研究了网络容量问题，指出网络编码是实现网络容量的重要组成部分，以Li等人对于多播网络容量的研究为基础，Koetter等人利用代数方法，将一个给定的网络信息流问题和一个有限域闭包上的代数变量之间建立起直接的连接，来研究网络及其容量，将网络编码扩展到任意网络和鲁棒性组网问题。对于限定为使用线性网络编码的网络，发现了一个给定网络上的任意连接的可行性之必要和充分条件，还研究了非各态历经链路失败的网络恢复问题，针对多播问题，证明了存在能够提供最大鲁棒性网络的编码方法，且无需先于所讨论的失败模式调整网络，推导出的结果既适用于无时延网络，也适用于有时延网络。

由于参考文献[2]和[3]的工作包含代数的成分，其中前者是卷积码，后者是线性编码，因此这种与代数几何建立起连接的概念，就为直接利用已经发展良好的数学学科之强大理论打开了大门。对于那些限定在使用线性码的网络，参考文献[4]找到了在一个给定网络上实现任意给定的连接，所需要的必要和充分的条件。使用该构架证明了一个网络上的多播连接情形呈现出一种非常特殊的结构，使得以多项式时间的验证成为可行，而且，类似于参考文献[3]和[4]的结果都表明，线性编码足以实现任意可行的多播连接。Jaggi等人在参考文献[5]证明了编码和解码能够以多项式时间实现，参考文献[6]中，Ho等人提出了随机网络码，其编码系数的选择是随机的。

当网络编码用于信息传输，其物理实现将引起信道上的传输时延和节点上的处理时延，而目前节点处理是网络上信息传送总时延的决定因素，这就要求网络编码的编码机制应以简单和快速的电路来实现，因此，采用线性映射的网络编码方案特别受到关注。

以上这些最初的网络编码的研究主要针对于无损耗的有线网络中多播通信的路由问题，而且基本是抽象出无时延的网络模型，但是，这些基础性的工作，却为后来的其他应用的研究奠定了坚实的理论基础。

鉴于其普遍适用性和巨大应用潜力，网络编码理论已经被引入多个研究领域，诸如信息和编码理论、网络、网络恢复、网络监控、内容分发、分布式存储、组合数学、交换、无线通信、ad hoc网、复杂度理论、安全及密码学和矩阵理论（见参考文献[3]和[7]），且网络编码新的应用仍在继续出现。本文主要面向网络编码在无线通信中的应用，介绍其理论和技术发展。

将网络编码的思想应用到无线网络环境已经引起了大量的研究兴趣，无线网络编码已经成为发展最快的研究领域之一，此处简要概述一些最初的标志性的结论。将网络编码与无线通信环境的广播特性结合在一起以利用后者的优势，进行这一工作的代表性人物如Wu等人[8]和 Fragouli等人[9]；参考文献[10]中，Lun等人提出了能量最小化的LP方程；参考文献[11]中，Eryilmaz等人研究了无线网络的合理性和时延问题；参考文献[12]中Zhang等人提出了物理层网络编码；参考文献[13]中Katti等人设计了COPE协议；Dimakis等人在参考文献 [14]中和Fragouli等人在参考文献[15]中都做了将网络编码应用于传感器网络的研究；在参考文献[16]中Petrovic等人将网络编码应用于传感器网络中研究非调谐网络，类似的思想近期已经被应用于传送网（transportation network）。将无线网络编码用作信息论工具的研究工作也得到了发展，例如，在参考文献[17]中Gowaikar等人研究了无线擦除网络（wireless erasure network）的容量，Ratnakar等人在参考文献[18]中研究了确定性信道上的广播特性，而Avestimehr等人在参考文献[19，20]中研究了普通确定性信道网络中广播和干扰的问题，在参考文献 [21]中，Sagduyu和Ephremides研究了跨层设计情况下的网络编码问题。

本文结构如下：第二部分通过一个简单的双向无线通信环境，引入网络编码的模型，第三部分介绍各种无线网络环境主流无线网络编码技术的编码方案及其应用，最后，给出一个结论性的总结和提出面临的挑战。

2 系统模型举例

考虑一个简单的3节点的无线双向信息交换的例子，如图 1所示，Alice（A）和 Bob（B）之间希望互传信息，其中的传输距离超出了发射机的覆盖范围，所以不能直接通信，而需要通过一个中继器（或者称之为路由器（R））。在传统的设计中，A传送包到R，R转发给B，B传送包到R，R转发给A，整个过程需要4个时隙，如图1（a）所示。

而利用网络编码的方法，如参考文献[13]中所做的那样，A和B可以分别传送各自的包给R，R将其做XOR运算，然后以广播的形式将此编码过的包A茌B同时发送给A和B，A利用自己的包与编码的包进行XOR运算，可以恢复出B的包，即A茌B茌A=B；B也以同样的方式恢复出A发来的包，这个过程利用了网络中的冗余来压缩信息，在一个时隙中传送两个包，总共以3个时隙完成通信过程，节省了一个时隙，提高了吞吐量，如图1（b）所示。

Katti等人在参考文献[13]进一步发展了机会网络编码的思想，提高了网络吞吐量，然而这类传统网络编码的编码运算是在数字比特流级别完成的，为了进一步减少时隙和提高吞吐量，充分利用无线媒质的广播属性，参考文献[12]和参考文献[22]分别提出了物理层网络编码和模拟网络编码的概念仍以双向通信的情景为例，如图1（c）所示，A和B同时传送信号到R，R接收到的将是A和B的混合信号，由于R不能提取出A和B的单独信息，所以不能像传统网络编码那样对其进行比特级编码，因此R仅仅是起到一个中继的作用，将混合信号转发给A和B。在物理层网络编码方法中，针对节点处具体的调制方式，可以建立某种映射机制，其编码运算发生在信号级，利用这种映射机制以及节点A和B处各自的信息，在节点A和B解出对方节点发来的信息。而在模拟网络编码中，A和B同时向R传输信号，R放大接收到的受到互相干扰的混合信号，并广播的形式发射出去，A接收到信号以后，从中减去已知的自己的信号，从而恢复出B传输来的信号，B对接收到的信号做类似的处理，整个过程只需要两个时隙，从而获得了更高的吞吐量。具体的过程下面的部分将做更详细的说明。

图1的双向3节点简单模型可以推广到各种其他复杂的情形。参考文献[23]研究了4节点双向中继网络，如何能够最优地中继信息的协议和算法，提出了一种有效地中继信息的中继协议。

图1 3节点的无线双向信息交换的例子

3 技术发展和应用

无线网络遭受一系列特有的问题，诸如低吞吐量、盲点以及对于移动性支持的不充分等；但是，其另外一些特征诸如媒质的广播属性、空间分集以及大量的数据冗余等，又为解决以上问题提出新的设计思想提供了机会。将网络编码应用于无线网络，就是基于这样的想法。参考文献[24]对于将网络编码用于无线网络之统一设计范例进行了探讨，尝试通过描述如何处理吞吐量、可靠性、移动性等问题，还讨论了将这样一种设计整合到网络协议栈的实际挑战。

在无线网络中，当来自不同发射机的信号自动地在无线信道中合成，无线信道为物理层网络编码提供了完美的媒质。

无线网络区别于有线网络的主要特征是传输媒质的共享和传输信道的时变特性。对于某一节点来说，通过提高发射功率，将最终可以得到足够大的信号噪声比，使得信号可以传送到网络中的其他每一节点，但是与此同时又会对其他节点产生很明显的干扰，而且，由于诸如衰落或者节点移动性的原因，信道状况将随时间而改变，最后，无线网络的资源诸如计算功率或者电池寿命往往是有限的（见参考文献[25]）。

现有的多数网络协议利用无线媒质建立起点对点的连接，但是并没有利用无线传输的广播特性，网络设计已经主要致力于运行的简单性和可扩展性；另一方面，近期的信息论诸如中继网络的研究表明，通过使用适合的编码方案进行广播，物理资源可以获得显著的节省，然而，所提出的编码方案诸如随机散列法（random hashing）等的编码复杂度太高，而通常这些方案不能够很好地根据网络规模进行扩展（见参考文献[25]）。

从无线系统的当前技术水平面向实际的基于信息论解决方法的研究过程中，将网络编码概念与无线媒质的广播特性相结合，是一个富有意义的技术步骤。实际上，运用代数的方法叠加信号就是散列法的一种变形，这种方法能够利用无线媒质的广播属性优势，而且在实际实现中也足够简单可行。某种意义上说，无线网络编码与网络信息理论和网络算法具有很大的重叠。从实际应用的角度，无线ad hoc和无线传感器网络深受期待而成为首批应用网络编码技术的领域之一，原因是两者的网络环境下其协议严格性要求较为宽松。

为了说明无线网络当应用网络编码技术所带来的优势，可以首先考虑共享无线媒质的广播属性所能提供的带宽、传输功率、时延，以及对于环境动态改变的适应性。基于诸如此类的优势，下面的部分将讨论一系列业务模式和网络配置示例。MIT的COPE结论表明，即使当编码运算限定在遵循一些额外限制的简单二进制加法，仍然会在吞吐量和MAC层协议的效率等方面获得增益。

传统的网络编码将接收机端的干扰视为对于系统性能的有害因子，而依靠合适的调度广播传输来减低干扰，这种机制将会在可实现速率方面引起显著的损耗。参考文献[12]所提出的物理层网络编码是第一次试图解决这一问题的工作，后来，出现了一种捕捉无线网络中的信号间交互作用的线性确定性模型，研究表明对于这样一种模型，能够实现信息论最大流最小割。

3.1 无线ad hoc网络的能量问题

无线ad hoc和传感器网络为网络编码的应用提供了大量的机会，同时它也面临大量的问题。

在一个网络中，传输一个信息比特所需的最小能量可用以描述最经济的通信方式，参考文献[8]中的研究证明了在一个分层无线网络模型下，一个移动ad hoc网络多播的最小每比特能量能够通过解线性规划问题来解决，最小每比特能量能够通过利用网络编码的方法来得到，与传统的路由求解方法相比，网络编码不仅潜在地可实现更低的每比特能量，还能够在多项式时间级别发现最优解，这明显优于构建最小能量多播树方法求解最优路由解，后者是一种NP hard问题。研究还表明，最小能量多播问题等价于线性的基于边定价的最小成本问题，这里的价格是对应的物理层广播链路之每比特能量，该参考文献还研究了使用路由方法的最小能量多播问题。由于定价方案的线性特征，路由选择之最小每比特能量的实现是通过使用一个单树，研究给出了利用一个单树选路的可容许速率区域的表征，而多播路由选择之最小每比特能量是通过求解一个整数线性规划来得到。而根据更早期的文献中Steiner树的研究结果证明，该整数线性规划问题的条件放松，能够理解为使用网络编码对于最小能量多播的优化。总之，该文给出了应用网络编码和路由进行最小能量多播的一种统一研究。

参考文献[9]研究了无线ad hoc网络中利用网络编码解决能量效率的问题，研究的情形是网络中的每一节点都试图作为向其他节点传输信息的源节点。能量效率直接影响电池寿命，它是无线网络的一个关键设计参数。他们提出了一种针对这种情形应用网络编码的可实现方法，进行了详细的理论分析，并籍此提出了一种实际的完全分布式的方法应用于实际的无线ad hoc网络环境，解决了一些实际问题诸如如何设置转发因子、如何管理网络编码的生成以及传输距离的影响，研究中使用了理论分析和包级仿真（packet level simulation）。

3.2 无线传感器网络

参考文献[15]将网络编码应用于传感器网络的研究，研究表明在网络拓扑动态变化的无线网络环境下，网络编码具有明显的增益，其研究限于分布式算法且没有利用关于网络环境的反馈信息。作者考虑了动态拓扑的几种情形，包括广播信息到网络的所有节点和收集传感器测试数据，研究表明在很多此类的情形下，在某些简化假设下，该问题理论上等价于息票托管问题 （coupon collector problem）的简单变种，因此，通过应用网络编码获得的增益因子是lg(n)，这里n是节点数，该增益在该作者的另外一篇文章中称作能量效率。此项研究给出了实际条件下的仿真结果来支持上述结论。

无线传感器网络的实现和布网要求超低成本和低功率节点，尽管节点的数字子系统仍然遵循摩尔定律，但是有关模拟组件的性能则没有这种趋势。参考文献[16]提出了一种将数字和模拟组件（包括本地振荡器）完全集成的架构，能够显著地降低节点的成本、尺寸和总功耗。尽管这样的一个基本架构不能提供可靠的标准设计的调整，但是已经证明通过使用随机网络编码，这类节点的一个密集网络能够实现吞吐量线性于通信系统中可用信道的数量；而且可以证明，非调谐网络（这里非调谐网络是指每一个传感器从一个有限的频率集合中，随机选择一个频率用以发射）与一个完全协调的可调网络的可实现吞吐量之比近似于1/e。他们的研究利用网络编码来改变这样一个事实即吞吐量等于一个图的最大流是可实现的，即使是在无法事先知道网络拓扑的情况下，然而，此处的挑战在于如何发现对应于该网络的随机图的最大流。

3.3 机会网络编码

3.3.1 COPE

Katti等人在参考文献[13]提出了一种称作COPE的架构，这是用于无线mesh网的一种新架构。除了转发包以外，路由器将来自不同源节点的包进行混合（例如进行编码），用以每一次传输的信息内容。这种在中间节点的处理提高了网络吞吐量，而设计就是基于网络编码理论的。之前的网络编码研究主要偏于理论且多集中于研究多播业务，COPE的目标是在理论和实际应用之间架起一座桥梁，研究了更普遍的单播业务、动态和突发流，以及在当前网络协议栈下融合加入网络编码的实际问题，设计了一个20节点的无线网络，对无线网络编码的首次测试床测试结果进行了讨论和性能评估，结果显示COPE显著地提高了网络吞吐量，一个3节点测试床的初步的试验结果表明，802.11 mesh网络中，相对于传统存储转发方案，COPE获得的是几乎3倍的吞吐量；而由于业务模式、拥塞控制水平和传输协议的不同，吞吐量的增益从几个百分点到几十个百分点不等。

COPE将机会算法（opportunistic algorithm）运用到网络编码中，每一节点监听无线媒质，借以获取其邻近各节点的状态，检测编码机会，一旦其接收者能够解码，则该节点进行编码。COPE所处理的情形是，需要提供多个单播业务的无线mesh网，而且没有网络拓扑或者业务模式的中央控制信息。COPE的基本思想就是网络编码处理能够带来增益的同时，网络节点仍然可以识别和利用机会。

3.3.2 MORE

COPE解决的是单播问题，而单播问题是WMN的首要和重要业务；但是由于COPE是一种流间（inter-flow）网络编码协议，不能适用于全向业务，不能解决盲点（dead spot）问题。相反，另外一种方案MORE是参考文献[26]提出的一种流内（intra-flow）网络编码协议，其作者将机会路由和网络编码融合为一个整体的协议，获得了显著的性能增益。

COPE称作流间网络编码是因为编码过程作用在其上的各个包在它们的下一跳是不同的，所以也就来自不同的流；而MORE称之为流内网络编码是因为路由器所结合的包都流向相同的目标节点参考。MORE应用了3种技术来产生足够的编码，以保证路由器能够很容易地支持高速率，这3种技术是：只对新包编码；对码向量编码；预编码。详细的描述见参考文献[26]。

机会路由（opportunistic routing）技术是为了在有损无线链路环境下实现高吞吐量而提出的，之前的机会路由协议ExOR，将和路由和MAC层联系在一起，使得路由器跟媒质的接入必须要有严格的调度机制。尽管调度机制可以分配机会增益 （opportunistic gain），但它将丢失掉802.11 MAC层的一些内在的特征，例如，它抑制了空间重用，从而不能充分利用无线媒质的特征；它还消除了分层抽象，使得协议不易于扩展诸如像多播一类的可选业务类型。

MORE是一种独立于MAC的机会路由协议，其在将包转发之前随机地混合包，这种随机性操作保证了监听到相同传输的路由器不必转发同样的包，因此MORE不需要专门的调度机器来协调路由器，从而可以直接运行于801.11的顶端。一个20节点的无线测试床上的实验结果显示，MORE的平均单播吞吐量高于ExOR 22%，而当具有空间重用机会时，增益更是增大到了45%；对于多播传输的情况，MORE的增益随目标节点数量的增加而增加，将高于ExOR协议35%～200%。

3.3.3 noCoCo

Scheuermann等人在参考文献[27]的工作比COPE又跨出了一步，研究了如何以一种更确定的方式构造编码机会，而同时仍然保留实际意义。他们提出一种跨层方案称作 noCoCo（near-optimal coordinated coding，近最优协作编码）方案，该方案将每一跳包调度、网络编码和拥塞控制整合为一。noCoCo的主要想法是，在COPE中当有自然出现的编码机会时进行编码处理，而传输的等级能够显著地影响编码机会的获取，从而影响编码增益。利用无线传输的路径分集和广播特性，作者提出一种有效的多径路由协议，称之为 MC2（multipath code casting，多径编码传播），这种设计是基于网络编码，无需像先前的机会路由协议那样需要节点间的协作；而且，这种协议提供了一种统一的架构来处理多径和非可靠性传播路径情形下的数据传输。

3.3.4 AdpNC

在参考文献[28]中，Karande等人研究了当包因遭到破坏而导致的比特错误情形下应用网络编码的问题。其基本思想是，某些预先设计一定的交换规则，通过这些规则，中继节点能够确定在某些特定的时刻，是否应用网络编码。针对双向中继网络的信息交换问题，作者提出了一种系统化优化方法来设计一种自适应网络编码（AptNC）方案，以更有效地交换互相独立的信息。其中研究了在中间节点上应用最少量的处理网络模型，此时网络编码函数的效率将依赖于包中观察到的误比特率（BER），因此在时变信道条件下，网络编码需要进行调整以符合与包所关联的信道状态。在该方案下，中间节点对于包的中继是否应用网络编码依赖于接收到的包的受破坏程度，而应用相对应的预先设计的交换规则。对于从802.11b和802.15.4演绎出来的信道模型所做的性能评价显示，AptNC具有比传统的转发和网络编码方案非常显著的性能提高。

3.4 干扰利用的网络编码

3.4.1 物理层网络编码

Zhang等人[12]提出了一种物理层网络编码（physical layer network coding，PNC），研究了白高斯噪声（AWGN）双向中继信道下，将叠加的电磁信号映射为简单的有限域（2n）上的数字比特流的加性运算。Zhang等人研究了双向中继信道中两个节点间的双向传输，两节点中间有一个中继节点。传统的网络编码设法避免在同一时间进行多个传输以防止干扰，与传统网络编码方案将干扰作为负面因素处理而刻意避免所不同的是，Zhang等人的工作尝试将干扰加以利用，以提高吞吐量性能，他们将网络编码概念应用于物理层，从而使得无线自组织网（wireless ad hoc）中无线传输的广播特性真正成为了提高容量的一个优势。通常在传统的网络编码中，编码运算只发生在比特级别，应用于那些已经正确接收的比特；与之相反，PNC将干扰变为编码运算的一个组成部分，它是通过在节点间协调传输，并将电磁信号的叠加映射为GF(2n)域上的数字比特流的加法。参考文献[12]中的结果显示，与传统的转发机制和直接的网络编码相比，当应用PNC，一个双向中继信道的容量分别增加100%和50%。

3.4.2 模拟网络编码

之前的多数网络编码研究工作，其编码的线性组合都是作用在有限域上，参考文献[12]所做的工作是第一次将网络编码应用于物理层，而Katti等人则在参考文献[22]引入了模拟网络编码（analog network coding，AlgNC）的概念，之所以称作模拟网络编码是因为混合的是信号而不是比特。AlgNC同样把干扰作为有益因素，设法有选择地让某些发送方互相干扰，路由器转发的是受到干扰的信号而不是包，目标节点接收机首先校正信道畸变，然后能够将对应于已知包的信号消除，前提是接收机知道它所需要的包所收到的干扰包的内容。

在理论上，AlgNC方案也能够使一个双向中继网络的容量吞吐量加倍，原因是所需的时隙减半。软件无线电（software radio）测试床的结果表明，相对于传统的无线路由和数字网络编码，吞吐量分别增加了70%和30%；而且，AlgNC有助于解决链路拓扑中的隐藏终端（hidden terminal）问题，无论是对单向链路还是双向链路。但是，没有进行同步的假设，也没有通过导频（pilot）做同步处理，甚至没有利用包之间的不完整重叠进行同步，甚至它还能够处理不同的信道之间所引入的相移。

PNC和AlgNC方案中存在的一个问题就是两者都依赖于调制方式，目前为止两者都没有构造出一种独立于调制方式的方案，而且PNC对于同步还非常敏感。但是，有关物理层网络编码的这些工作有助于激发对于将无线广播特性融入网络编码的更深入的研究。

3.4.3 复数域网络编码

先前的网络编码研究主要应用于有限域，因此编码主要是在比特级的运算，而将网络编码应用于其他域的研究已经引起了广泛的兴趣。2008年初，Wang和Giannakis在参考文献 [29]中引入了复数域网络编码 （complex field network coding，CFNC），研究了衰落信道的性能。CFNC概念的引入，使得在物理层的符号级运算成为必要，而与有限域网络编码（Galois field network coding，GFNC）相比，在无线网络环境条件下，CFNC是一种更好的选择。CFNC的动机是，通过利用多用户检测，基于中继的多源协作通信能够实现空间分集增益，并提高覆盖和有效的最大似然比解调。Wang等人采用预编码的方法来对抗多径衰落，为网络编码的应用提供保障。参考文献[29]指出，对于一个具有源个数为NS、中继个数为NR和一个目标节点的中继协同网络，CFNC总是能够提供每源每时隙1/2符号的吞吐量，而GFNC的吞吐量仅仅是1/(NS+NR)，传统中继的吞吐量则仅仅是1/(NS+(NR+1))。如所期望，不论SNR和星座尺寸如何，CFNC都能够实现完全分集。

3.5 网络编码概念与其他技术的融合

在参考文献[30]中，Fasolo等人将MIMO技术与网络编码技术结合，利用空间增益和网络编码增益，针对衰落信道和包丢失问题，获得了比单纯应用传统网络编码技术鲁棒性更好的系统。参考文献[31]同样研究了MIMO网络编码，基于的是Alamouti开环空时块码（STBC），针对的是一个3节点中继网络。与目前多数的研究工作关注于3节点中继模型所不同，参考文献[23]研究了4节点双向中继信道模型，这种模型下多增加了一跳（hop），因此两个中继扮演了中间编码节点的角色。作者设计了一个预消除协议，并使用了模拟网络编码技术，但是使用的是无噪声信道模型假设。在参考文献[32]的工作中，Khirallah等人将扩频（spread spectrum）和物理层网络编码融合在一起，提出了网络扩频编码（network spread coding，NSC）以改进传统标准扩频码的性能。作者使用了完全补码（complete complementary code，CC码）作为扩频码，原因是 CC码的理想相关特性使得与标准扩频码相比，NSC显示出显著的竞争力。通过所设计的NSC编码方案，在AWGN和衰落信道中，均获得了更低的复杂度和更低的干扰等级，节省了大量的带宽。

将网络编码的概念与其他的无线技术结合起来，可以根据某一方面的需要，优化无线网络的性能，近期的诸如此类研究工作包括与多天线技术的结合、与扩展频谱技术的结合等，详见参考文献[23，30～33]。

3.5.1 与多天线技术的结合

在参考文献[30]中，将MIMO技术应用于网络编码，以利用包合成过程所内在的空间分集特性。实际上，网络编码和MIMO解决的是类似的问题，即根据给定的一个接收样本向量，解码传输符号（symbol）向量。根据这一观察结果，提出一种新的NC编解码方法，其基本思想是将网络编码功能移向物理层以便联合进行NC解码和MIMO检测，从而获得两种方法的优势。理论分析和仿真结果证明，在克服衰落和包丢失性能方面，这种MIMO_NC系统比传统的网络编码具有更好的鲁棒性。

参考文献[31]中研究了一个中继配备多个天线的双向通信系统，证明了当中继不知道下行信道状态信息的情况下，通过在中继上增加天线所获得的优势，只能通过使用解码转发（decode and forward，DF）来得到，而不能通过放大转发（amplify and forward，AF）得到；当同时应用发射分集和无线网络编码时，得到了很显著的增益，此外还证明了如何在中继进行天线选择才能够提高这种系统的性能，研究结果显示如果中继知道下行信道状态信息，则相对于简单的天线选择方案，网络编码可能不会提供额外的增益。

3.5.2 与扩频技术的结合

参考文献[32]将网络编码与扩展频谱技术相结合。无线ad hoc和P2P网络上的数据流面对的是诸如干扰级别、衰落、噪声等问题，这些问题限制了实时多媒体应用，降低这些影响的一种典型方法是应用扩展频谱技术，该技术通常会导致难以接受的对于带宽的需求增长；另一方面，网络编码是作为一种降低带宽需求的有效方法而提出来的。基于这种思想提出了一种基于完全补码（CC码）的方案，称之为NSC，将扩频技术和网络编码技术结合起来。NSC具有对于噪声和干扰的鲁棒性，同时又降低了对于带宽的需求。与传统的扩频方案相比，不管是AWGN还是衰落信道，所提出的两种实际的NSC设计表现出了富于竞争力的更好性能，具有更低的复杂度，同时节省了大量的带宽。

3.5.3 多载波信道与多址信道的协同

在参考文献[33]中，Zhang和Li将网络编码的应用延伸到多信道无线系统，研究了基于OFDMA的802.16无线城域网（WMAN），其方法是应用了他们提出的编码已知的子载波分配机制 （coding aware subcarrier assignment mechanism）。多信道网络编码是通过将具有相似大小信噪比SNR的子载波进行编码，利用了下行链路子载波之间的信道增益的分集，结果显示吞吐量能够真正得到提高。

正交频分多址已经应用于宽带接入技术如802.16无线城域网，由于下行子载波间信道增益的分集性，从之前的研究已经知道，子载波的动态分配能够显著地提高OFDMA系统的整体性能，表现在功率效率和链路吞吐量等方面。之前大量的研究工作关注于OFDMA下行链路的联合子载波分配和资源（比特和功率）分配，在参考文献[33]中，对于基于OFDMA的无线网络的上行和下行链路，采用跨层设计的方法，提出一种结合网络编码方法的子载波分配算法。其中，将最大速率分配问题构造为一种混合整数线性规划，推导出一种多项式时间探索式方法来近似求解。通过将具有相似大小信噪比SNR的子载波进行编码，利用了下行链路子载波之间的信道增益的分集，结果显示吞吐量能够真正得到提高。利用网络编码，将可以分配相同的子载波到不同的下行链路，而又不致引起任何的干扰。因此，结合网络编码的分配方案可观地提高了带宽效率，增加了网络层吞吐量。研究显示，这种探索式方法得到的总的网络吞吐量可与最优解相比拟，而仅仅在公平性方面有轻微的损失；而且，结合网络编码的子载波分配机制同样可以应用于其他的多信道无线系统。

近来，协同分集（cooperative diversity）受到大量的关注，作为一种低成本技术用以克服多径衰落和提高传输可靠性，但是，由于中继传输要消耗额外的带宽资源，之前的很多协同协议遭受各态历经容量的损失，为此在参考文献[34]中，Ding提出了一种上行链路中将网络编码技术与协调分集结合在一起，以利用网络编码技术能够提高系统吞吐量的能力。通过应用一种分布式的中继选择策略，有效地利用了多径传播的动态属性。同样的，使用了两种信息论度量耗损和多径容量来支持所提传输方案的性能评价，分析结果显示出与蒙特卡罗仿真很一致的结论，这表明，与其他对应的方案相比，所提出的协议能够同时实现更好的系统鲁棒性和更大的系统吞吐量。

Ding在参考文献[35]研究了应用物理层网络编码的情况下，如何保持分集的问题。PNC证明了能够显著提高AWGN信道无线网络的吞吐量，但是当PNC应用到多径信道时将会带来很多问题，因为多径信道的情形要求每一发射机端的振幅和相位补偿，而相位补偿需要准确的分布式相位跟踪，振幅补偿则更为复杂，因为会引起系统的效率降低，从而导致分集的消失，即使是在完美的信道估计实现的情况下也可能会如此。Ding等人提出的一种系统来避免这些问题，通过在网络体系更高一级——物理层对PNC技术的认定，进行分布式中继选择。由于这样得到的方案能够实现一种分集选择，所以称之为分集网络编码（network coding with diversity，NUD）。为便于性能评价，研究了两种信息论量度，即耗损 （outage）和各态历经容量（ergodic capacity）。理论分析和仿真结果表明，与对应的方案相比，所提出的协议能够实现更鲁棒的性能和更好的系统吞吐量。最后，将所提出的网络编码延伸到协同多址信道，得到一种新的协同协议，获得比已经存在的传输方案更好的耗损参数和更大的各态历经容量。

Zhang等人在参考文献[36]研究了两个源节点S1和S2，通过一个中继节点R进行信息交换的双向中继信道（TWRC），其中R在同一个时隙接收来自S1和S2的叠加信号，然后在下一个时隙放大并转发给S1和S2，应用模拟网络编码，S1和S2从接收到的信号中消除所谓的自干扰信号，然后解出所需的信息。假设S1和S2都配备有单天线，R配备有多天线，分析了基于模拟网络编码，在中继R采用线性处理（波束赋形）的TWRC信道的容量区，容量区包含了当S1、S2和R为给定发射功率时，S1和S2的所有可实现双向速率对，给出了最优中继波束赋形结构以及一种基于凸优化技术的有效算法来计算最优波束赋形矩阵，同时也给出了一种低复杂度的次优中继波束赋形方案，比较了其可实现速率与最优方案下的容量。

4 无线网络编码研究面临的挑战

网络编码的部署需要用到各种资源，诸如同步和可靠性机制，需要网络节点的功能平衡，诸如有限域运算或其他域的运算以及存储能力。

或许更为重要的是，需要设计新的协议和架构，或者为无线网络调整已有的基础网络，以便使得网络编码功能得以实现。在哪一层实现网络编码功能，网络编码能够支持什么类型的链接，应该布置什么样的编码机制，构成了目前网络协议和架构设计中的研究课题。

其他挑战包括如何支持某些特殊应用的需求。例如，实时应用，诸如音频和视频，可能在吞吐量和时延方面对于QoS有严格的需求。通常这些因素是互相冲突的，要通过网络编码实现最优的吞吐量，对于包的个数n值很大的情况，可能需要网络节点混合n个包；另一方面，为了解码源信息，一个节点可能需要收集n个包，这将导致难以承受的时延。如何很好地平衡这些需求，可能必须需要跨层设计的方法。

另外，一些功能上的问题，诸如调度和路由，也需要考虑周到。例如，对于支持多个单播任务的一个网络，目前还没有搞清楚跨越不同任务的信息能够混合到怎样的程度，以及在何等级别上广播传输能够进行调度。

目前为止，无线网络编码的研究基本停留在理论模型上，而缺乏一般性的和实用模型的编码方法。具体地说，网络编码应用于实际的无线环境面临的挑战分两方面：一是大多数现有的无线网络编码需要很多的不切实际的假设，例如，物理层网络编码需要完全的相位/时间同步、功率控制和发射机与接收机两端都必须是信道状态信息可知，特别地，完全的相位同步假设是最困难的，因为由信道和收发机硬件引起的相位漂移是随机的，这就要求必须有一个闭环的控制方案；另外一个挑战是，无线网络编码的实际编码方法和解码方法的研究还没有引起足够多的注意，例如，接收信息的线性组合是线性网络编码的主要思想，然而，如何应用线性网络编码到无线网络，且做到性能的鲁棒性和保证好的解码时延性能，是一个有待解决的问题。

参考文献

1 Yeung R W,Zhang Z.Distributed source coding for satellite communications.IEEE Transactions on Information Theory,1999(IT-45):1111～1120

2 Ahlswede R,Cai N,Yeung R W.Network information flow.IEEE Transactions on Information Theory,2000 (IT-46):1204～1216

3 Li S Y R,Yeung R W,Cai N.Linear network coding.IEEE Transactions on Information Theory,2003,49(2):371～381

4 Koetter R,Medard M.An algebraic approach to network coding.IEEE-Acm Transactions on Networking,2003,11(5):782～795

5 Jaggi S,Sandrs P,Chou P A,et al.Polynomial time algorithms for multicast network code construction.IEEE Transactions on Information Theory,2005,51(6):1973～1982

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

7 Fragouli C, Soljanin E. Network coding fundamentals.Foundations and Trends in Networking,2007,2(1):1～133

8 Wu Y N,Chou P A,Kung S Y.Minimum-energy multicast in mobile ad hoc networks using network coding. IEEE Transactions on Communications,2005,53(11):1906～1918

9 Fragouli C,Widmer J,Le Boudec J Y.A network coding approach to energy efficient broadcasting:from theory to practice.In:25th IEEE International Conference on Computer Communications,April 2006

10 Lun D S.Efficient operation OD coded packet networks.PhD thesis,Massachusetts Institute of Technology,June 2006

11 Eryilmaz A,Ozdaglar A,Medard M.On delay performance gains from network coding.In:Proc 40th Annual Conference on Information Sciences and Systems,Princeton,NJ,March 2006

12 Zhang S,Liew S,Lam P.Physical layer network coding.In:ACM MobiCom 2006,Los Angeles,Sept 2006

13 Katti S,Rahul H,Hu W,et al.XORs in the air:practical wirelessnetwork coding.Computer Communication Review,2006,36(4):243～254

14 Dimakis A G,Prabhakaran V,Ramchandran K.Ubiquitous accessto distributed datain large-scalenet works through decentralized erasurecodes.In:Symposium on Information Processing in Sensor Networks (IPSN'05),Los Angeles,California,USA,April 2005

15 Fragouli C,Widmer J,Le Boudec J Y.On the benefits of network coding for wireless applications.In:4th International Symposium on Modeling and Optimization in Mobile,Ad Hoc and Wireless Networks,April 2006

16 Petrovic D,Ramchandran K,Rabaey J.Overcoming untuned radios in wireless networks with network coding.IEEE Transactions on Information Theory,2006,52(6):2649～2657

17 Gowaikar R,Dana A F,Boudec J-Y L.On the capacity of wireless erasure networks.In:Proceeding of the 2007 IEEE International Symposium on Information Theory, Chicago,Illinois,June-July 2004

18 Ratnakar N,Kramer G.The multicast capacity of acyclic,deterministic,relaynetworkswith nointerference.Network Coding Workshop,Italy,April 2005

19 Avestimehr S,Diggavi S,Tse D H C,A deterministic model for wireless relay networks and its capacity.Information Theory Workshop,Lake Tahoe,September 2007

20 Avestimehr S,Diggavi S,Tse D H C.Wirelessnet work information flow.In:Proceedings of Allert on Conference on Communication,Control,and Computing,Illinois,September 2007

21 Sagduyu Y E,Ephremides A.Joint scheduling and wireless network coding.In:Proc First Workshop on Network Coding,Theory,and Applications,Riva del Garda,Italy,April,2005

22 Katti S,Gollakota S,Katabi D.Embracing wireless interference:analog network coding.Computer Communication Review,2007,37(4):397～408

23 Kuek S K,Yuen C,Chin W H.Four-node relay network with bi-directional traffic employing wireless network coding with precancellation.In:IEEE 67th Vehicular Technology Conference-Spring,Singapore,May 2008

24 Fragouli C,Katabi D,Markopoulou A,et al.Wireless network coding: opportunities & challenges. In: IEEE Military Communications Conference,Orlando,Florida,USA,Oct 2007

25 FragouliC,Soljanin E.Network coding applications.In:Foundations and Trends in Networking,2007,2(2)

26 Chachulski S,Jennings M,Katti S,et al.Trading structure for randomness in wireless opportunistic routing. Computer Communication Review,2007,37(4):169～180

27 Scheuermann B,Hu W,Crowcroft J.Near-optimal coordinated coding in wireless multihop networks.In:CoNext'07,New York,USA,2007

28 Karande S S,Misra K,Ilyas M U,et al.Adaptive network coding with noisy packets.In:41st Annual Conference on Information Sciences and Systems,Baltimore,MD,March 2007

29 Wang T R,Giannakis G B.Complex field network coding for multiuser cooperative communications.IEEE Journal on Selected Areas in Communications,2008,26(3):561～571

30 Fasolo E,Rossetto F,Zorzi M.Network coding meets MIMO.In:Fourth Workshop on Network Coding,Theory,and Applications,Hong Kong,China,January 2008

31 Yuen C,Chin W H,Guan Y L,et al.Bi-directional multi-antenna relay communications with wireless network coding.In:IEEE 67th Vehicular Technology Conference-Spring,Singapore,May 2008

32 Khirallah C,et al.Network spread coding.In:Fourth Workshop on Network Coding,Theory,and Applications,Hong Kong,China,January 2008

33 Zhang X Y,Li B C.Joint network coding and subcarrier assignmentin OFDMA-based wirelessnet works.In:Fourth Workshop on Network Coding,Theory,and Applications,Hong Kong,China,January 2008

34 Ding Z G,Leung K K,Goeckel D L,et al.A new form of network coded cooperative transmission for multiple access channels.In:IEEE Military Communications Conference,San Diego,California,November 2008

35 Ding Z G,Leung K K,Goeckel D L,et al.On the study of network coding with diversity.IEEE Transactions on Wireless Communications,2009,8(3):1247～1259

36 Zhang R,Liang Y C,Chai C C,et al.Optimal beam forming for two-way multi-antenna relay channel with analogue network coding.IEEE Journal on Selected Areas in Communications,2009,27(5):699～712

Network Coding Technology in Wireless Network

Wang Hengyou,Pen Mugen,Wang Wenbo,Wu Hequan
(BUPT,Beijing 100876,China)

Network coding is a novel technique to improve network throughput and performance.It is expected to be a key technology for networks of future.This paper gives a survey on the network coding applicated in wireless networks which is considerd to be one of the most likely applications of network coding.Network coding allows to take advantage of the broadcasting nature of the shared wireless medium.Wireless networks and sensor networks provide opportunities for the application of network coding.In this paper,we introduce several network coding and corresponding encoding strategies under different scenarios.These include traditional network coding,physical layer network coding,analogue network coding and complex field network coding as well.We also give remarks on wireless network coding in the future.

wireless network coding,digital network coding,physical layer network coding,finite field network coding,complex field network coding

2010-07-09）

* 国家自然科学基金资助项目（No.61072058），国家科技重大专项资助项目（No.2010ZX03003-003-01）

1 引言

传统的通信网络中，信息流从源节点发出，各级中间节点进行存储转发，最后到达目标节点。网络编码概念的提出改变了这一观念，赋予了中间节点信息处理和运算的功能，理论上显著提高了网络的吞吐量。

王亨友，北京邮电大学在读博士生，师从邬贺铨院士，研究方向为下一代宽带移动通信系统的网络编码技术；彭木根，北京邮电大学副教授，硕士生导师，博士，研究方向为无线信号处理及宽带无线网络技术；王文博，北京邮电大学教授，博士生导师，博士，研究方向为无线通信技术及无线宽带网络；邬贺铨，中国工程院院士，中国工程院副院长，国家科委“863”计划通信技术主题专家组组长，工业和信息化部电信科学技术研究院副院长兼总工程师。