无线网络编码技术的探讨
俞智敏 汪莉君 华信邮电咨询设计研究院有限公司
池凯凯 浙江工业大学
【摘 要】文章介绍了网络编码这一新技术在不同类型无线网络中的潜在应用，分析了网络编码在不同应用中所能带来的性能提升以及存在的问题，并对这些问题提出了可能的解决思路，为网络编码技术在无线网络中的实用提供了参考。
【关键词】网络编码 无线网络 无线局域网 无线中继网络 无线多跳网络收稿
1 引言
在2000年，网络编码技术最初被提出来用于提高有线网络中的多播（单点到多点）传输速率，使其达到多播的最大流限[1]。在传统的数据包传送方式中，中间节点仅仅扮演着转发器角色，它们对接收到的数据进行复制和转发而不对数据内容做任何处理。而网络编码技术拓展了传统的包传送技术。简单来说，网络编码是一种融合了编码和转发的信息交换技术。使用网络编码技术，中间节点扮演了编码器的角色，来完成编码和转发双重功能。自提出以后，网络编码技术便引起了国内外学术界、工业界的广泛关住。
最初几年，关于网络编码技术应用的研究主要集中于有线通信网络。已有的研究成果表明：网络编码可以在有线网络中不同的通信场景中带来好处。跟传统的包转发技术相比，网络编码技术能有效地提高多播传输速率[1]，或者有效地降低多播带宽消耗[2]。Gkansidis等人研究了网络编码在大数据分发中的应用问题[3]，不仅节约了下载时间，还增强了P2P通信系统的鲁棒性。此外，网络编码还在纠错、链路失败下的数据恢复等方面有着潜在的应用。最近几年，网络编码技术在无线通信网络里的应用也开始受到广泛关注。研究成果表明，由于无线链路的不可靠性和物理层广播特性非常适合采用网络编码，网络编码技术可以在无线局域网、无线中继网络、分布式无线多跳网络等无线网络中带来非常可观的性能改善。
网络编码在无线网络中所能带来的好处可以用图1中的简单例子来说明。图中，节点A要发送数据包P1到节点B，节点B要发送同样大小的数据包P2到节点A。A和B不在相互的通信范围内，必须借助于节点R来转发。如果用传统的发送方式，总共需要4次发送来完成P1和P2的传送。如果采用网络编码技术，可以先让节点A把P1发送到R和B把P2发送到R，然后R把P1和P2逐个比特异或后得到编码包P1 P2并且发送（物理层广播）出去。A接收到P1 P2后，通过把P1 P2和P1异或得到P2，同理B也得到P1。
因此总共只需要3次发送就完成P1和P2的传送，从而提高传送效率。接下来讨论网络编码技术如何在无线局域网、无线中继网络、分布式无线多跳网络等无线网络中带来性能提高，指出存在的一些问题，并讨论可能的解决方法。
2 网络编码在无线局域网的应用
无线局域网已经被广泛部署在各种地方，比如说办公楼、大学校园、机场等等。由于无线局域网中无线链路内在的高丢包性，获得高传输效率是一个很大的挑战，网络编码技术可以用于无线局域网中以显著提高传输效率。无线局域网中的网络编码主要思想是：在无线接入点，不像传统的协议里那样不同的丢包被分开重传，几个（有着不同接收节点的）丢包可以组合在一起来实现一次发送就恢复多个丢包。以图2里的无线局域网为例来说明该思想。在这个例子中，接入点要分别发送P1和P2到节点A和B。当发送P1时，A没有正确接收到此包，而B却正确接收到此包；当发送P2时，B没有正确接收到此包，而A却正确接收到此包。
在这种情况下，接入节点可以发送编码包P1 P2。
如果A收到该编码包，则可以通过把P1 P2和P2异或来恢复出P1。同样，如果B收到该编码包，则可以通过把P1 P2和P1异或来恢复出P2。这样一来，一次发送就能成功传输2个丢包，从而将重传效率提高了一倍。为了设计出实际可行的基于网络编码的无线局域网接入点发送协议，有两个重要的方面需要进一步考虑：（1）媒体接入控制（MAC）协议的设计目前的无线局域网工作模式下，当无线接入点要给某个用户发数据包时，通过基于点到点连接的MAC协议来获取发送机会。当采用网络编码后，由于一个编码包有好几个接收节点，基于点到点连接的MAC协议已经不能再用于此种场合。因此有必要设计新的MAC协议。
一种简单的方案是接入节点采用广播的方式来发送数据，从而让每个接收节点都接收编码包。
这种方案的缺点是那些不需要此编码包的接收节点会由于接收此包而浪费能量。更合理的方案是设计能够建立从接入节点到多个接收节点连接的MAC协议，来保证仅仅有必要的接收节点来接收编码包。
（2）高效编码算法的设计当有很多个接收节点时，不同的编码包（即有不同接收节点集合）会有不同的性能提高。因此，有必要明确编码包好坏的合理衡量方法以及设计高效编码算法来找出较好的编码包。
合理的编码包好坏衡量方法应该综合考虑到各个接收节点处已经接收的包，各个接收节点处的丢包率和各个流的包大小。而高效的编码算法可以从最优化理论的角度来研究，设计查找最优编码的低复杂度算法，或者设计低复杂度启发式算法来查找较好（但不一定最优）的编码。
3 网络编码在无线中继网络的应用
下一代移动通信系统对频谱效率提出了更高的要求，在现有的蜂窝网结构中引入中继的协作式通信是实现高速率高覆盖的非常可行的方案之一。无线中继的基本思想是使用中继节点将基站发送的信号处理后再发送给用户，或者将用户发送的信号处理后再发给基站，从而扩展覆盖范围和获取分集增益。传统的无线中继技术里，无线中继对不同的信号（数据包）进行分开的处理和转发。具有网络编码的无线中继可以将多个信号进行编码后通过一次发送来实现多个信号的中继，从而进一步提高频谱效率[4]。
以图3中的无线中继为例，说明网络编码所能带来的性能提高。当用户A发送信号P1时，一方面基站直接接收该信号，另一方面中继把接收到的信号转发给基站。同理，当用户B发送信号P2时，中继也接收此信号并进行转发。在传统的中继技术中，中继点对接收的P1和P2分别进行转发，总共需要2次转发。因此网络吞吐量为1/2符号/时隙。由于目的节点两次接收到信息P1和P2，该中继传输方案获得了2阶分集增益。如果具有网络编码功能，通过转发编码包P1 P2中继节点可以同时帮助A和B中继信号。在这种情况下，基于网络编码的吞吐量为2/3符号/时隙且同样也获得了2阶分集增益，从而获得更高的频谱效率。在基于网络编码的无线中继中，有几个重要问题需要进一步研究。首先，目前为止已经提出来许多可行的中继方案（有着不同的中继节点信号处理方式、发送功率确定规则等），如何将这些具体的中继方案与网络编码技术结合起来需要进行大量的研究。其次，由于中继节点发送的是编码的包，目前已有的中继节点最佳发送速率和发送功率确定方法已经不再适用，因此需要重新设计。还有，由于用户的移动而发生中继或者基站的切换时，如何快速有效地更新网络信息也需要进一步的考虑。
4 网络编码在无线多跳网络的应用
无线多跳网络由于其低带宽、多跳、拓扑变化、高丢包率等特性，采用基于单纯转发的传统包传送技术时所能达到的网络吞吐量非常有限。因此，采用网络编码技术来显著提高无线多跳网络吞吐量是一个非常有意义的研究方向。在无线多跳网络中，网络编码可以在单播、多播、广播、P2P等方面带来性能提高。由于单播数据流占到网络总流量的主要部分，采用网络编码来有效地支持单播通信有着非常重要的意义。在2005年，Wu[5]等人指出在简单的双向单播中通过同时利用网络编码技术和无线链路物理层广播特性，可以大大提高频谱效率。受此思想的启发，针对多路单播流，MIT的Katti等人[6]提出了一个基于网络编码、实际可行的包传送架构（COPE）。该架构巧妙地利用了由双向信息流和无线通信中的包监听特性这两方面所制造的可观网络编码机会，并结合无线物理层广播特性来实现单个发送就将多个数据包传递到各自的下一跳。他们所搭建的测试平台显示COPE架构具有显著提升（能高达二倍以上）无线多跳网络吞吐量的潜力。紧接着此开创性工作，一方面，一些研究工作对COPE架构进行了不同方面的性能分析：文献[7]从理论上分析了COPE架构下的编码机会，而Liu等人[8]则分析了利用网络编码和物理层广播特性所能带来的网络吞吐量提高的理论上界值。
另一方面，一些研究者从制造更多编码机会和更有效利用编码机会这两个方向来探索更加合理的包传送架构设计。Ni等人[9]提出了基于网络编码意识（coding-aware）的路由思想，通过合适的路由选择来制造更多的双向信息流和有效的包监听，从而制造更多的潜在网络编码机会。目前基于网络编码的无线多跳网络包传送技术存在几个关键问题，以下将对其及其解决方案进行讨论。
4.1 网络编码机会制造的问题及解决方案
虽然网络层上采用基于网络编码机会的路由算法能够为网络节点制造更加可观的潜在编码机会，但是这些潜在编码机会必须转换为数据链路层上真实的编码机会才能最终带来编码增益。现有的MAC协议由于是无意识地制造数据链路层真实编码机会，使得数据链路层以非常低的效率利用潜在的编码机会。
因此，有必要设计基于网络编码的MAC协议，从而把潜在编码机会在数据链路层充分地体现出来。目前为止，已经有一小部分研究工作对该问题进行了初步探讨。但是这些工作中提出的MAC协议存在着以下严重不足：在做接入调度时仅考虑由双向信息流产生的潜在编码机会，并没有考虑到由包监听所产生的可观的潜在编码机会；没有考虑和评估所设计的MAC协议的节点接入公平性。因此，有必要对基于网络编码的MAC协议设计进行更加深入的研究。无线多跳网络MAC协议采用退避计数器及相应的退避机制来有效地减少发送碰撞的概率，并保证公平性。
为了设计能主动地制造编码机会的MAC协议，可以设计能主动地制造编码机会且保证接入公平性的退避机制。主要思路是：（1）设计合理的规则，基于当前节点待发送包的信息来判断在节点获得接入机会的时刻是否具有编码机会。如果没有编码机会，则判断推迟接入无线媒质（即增大退避计数器当前值）是否能带来编码机会。（2）设计合理的规则，基于邻居节点待发送包的信息来判断邻居节点是否需要接收当前节点的某个包以获取编码机会，从而决定当前节点是否提前接入无线媒质（即减小退避计数器当前值）。（3）基于各个竞争流已经获得的包发送机会统计数据来动态调整竞争窗口值，以保证接入公平性。
4.2 网络编码机会利用的问题及解决方案
在数据链路层，Katti等人在文献[6]中提出的采用面向数据包大小的队列结构，把有着相同下一跳且在同一大小范围内的所有不同数据流的包都缓存在同一个队列。为了减少乱序，只有每个队列的最前面那个包可能参与编码。但是，理论上讲，每一个流的最早到达的包都有可能符合参与编码的条件。因此，该队列结构过于简单，抹去了部分数据包所具有的潜在编码机会。合适的队列结构既要有能接受的复杂度（如队列数），又能在不引入包乱序的前提下保证尽可能多的不同数据流的最早到达包具有参与编码的机会（即保留尽可能多的编码机会）。如果采用面向流的队列结构（即为每个流维护一个队列），所有最早到达包都具有参与编码的机会，然而此结构需维护较多的队列。可以根据不同类型网络的具体特性来设计相应的（在复杂度和编码机会间取得良好平衡的）队列结构。在编码子层，目前的编码算法要么有低复杂度但经常找不出最优编码，要么能经常找出最优编码但复杂度偏高。高效编码算法的设计可以从最优化理论和算法的角度来研究。针对每类网络的队列结构，首先分析最优编码问题的难度（是否NP-complete），然后根据问题难度来决定是设计具有多项式复杂度的查找最优编码的算法，还是设计有效的启发式算法或近似算法。
5 结束语
通过上面对不同类型无线网络中的网络编码应用的探讨，可以清晰地了解网络编码在无线通信网络里有着广泛的应用前景。然而，目前关于无线网络编码的研究大多停留在理论阶段，仅有少数的研究者在测试网络里进行性能测试。因此，尚有大量的问题需要进一步的深入考虑和研究，以最终实现网络编码在无线网络里的实际应用。