一种基于网络编码的重传算法研究*

吴阳阳，魏辰, 王久鹏

（重庆邮电大学，重庆 400065）

网络编码理论最早是由香港中文大学的Ahlswede[1]教授等人在2000年首先提出的，其核心思想是允许网络的中间节点对各条信道上收到的信息进行线性或者非线性的处理，而传统网络中的中间节点只对收到的数据进行存储转发。通过允许中间节点处理数据，网络编码可以达到由最大流最小割定理得到的网络最大传输容量，由于无线网络的广播特性非常适合网络编码的思想，因此将网络编码用于无线网络中已经成为当前的一个研究热点。

目前，网络编码在无线网络中的应用研究主要侧重在几个方面改善系统吞吐量，提高能量利用效率、保证无线链路传输的可靠性和安全性。由于无线网络的传输信道受噪声，多径衰落等影响较大，节点发送的数据分组，可能要经过多次重传才能实现可靠传输，而多次重传会导致节点的能耗增加，带宽利用率降低。将网络编码与ARQ结合的重传机制能够在一个时隙能广播发送由多个丢失数据分组编码得到的编码分组，而丢分组节点可以通过接收编码分组来解码得到丢失的数据分组。也就是说一个时隙内传输一个编码分组可以得到多个丢失的数据分组，因此传输效率可以得到极大提升。

1 相关工作

我们以经典的蝴蝶网络为模型，说明网络编码应用于无线网络中时，网络性能的提升。在图1所示的蝴蝶网络中，S是源节点，R1和R2是两个目的节点，假设各条链路都无时延和差错，每条边的容量都为1。在图1（a）中，由最大流最小割定理知，信源节点S到目的节点R1和R2的最大传播速率不可能超过2。然而,如果允许网络中的中间节点对进入节点的数据分组进行编码,如图1（b）所示,则可以同时将数据分组P1和数据分组P2发送到目的节点R1和R2。因为当目的节点R1接收到数据分组P1和编码分组P1P2时,可以将P1与P1P2进行异或运算恢复出P2。同理,在目的节点R2可以恢复出P1。我们可以看到，在蝴蝶网络中利用网络编码，可以使网络的传输效率得到明显提升。

图1 采用编码的具有两个目的节点的蝴蝶网

网络编码应用于数据分组的丢失重传是无线网络的发展趋势。在文献[2]中，作者提出了一些网络编码的应用方案，应用于一个发送方多个接收方单跳无线网络中，可以有效减少广播重传的次数，主要思想是允许发送方以特定的方法编码和重传丢失的数据分组，以使多个接收方能够在一次重传中恢复丢失的数据分组。文献[3]中，H.WU等提出了一种基于广播重传的网络编码机制 (CoRET，Coding-based RE Transmission），应用于移动通信网络的广播服务，以提高重传效率和重传的可靠性。在文献[3]中，肖潇提出了一种基于网络编码的无线广播重方法NCWBR (Network Coding Wireless Broadcasting Retransmission)，NCWBR的基本思想是节点利用反馈的分组丢失信息,对需要重传的多个数据分组进行编码组合，然后把编码分组广播重传，该重传策略可以有效减少重传次数，提高重传效率。

现有的研究中，在重传中应用网络编码，都是基于一个发送方多个接收方的网络情景，而在多个发送方多个接收方的单跳网络中应用网络编码却还没有得到充分研究，本文提出一种应用于多个发送方多个接收方无线网络中的重传算法RMBNC（Retransmission Mechanism Based on Network Coding）。

2 网络编码在MSMR单跳无线网络中的应用

我们通过图2来说明在多个发送方多个接收方的单跳无线网络中，网络编码应用于数据分组的重传时，网络性能的提升。图中所示网络模型为随机网络拓扑，含有6个节点，每个节点既可以是发送方也可以是接收方，网络中的每个节点公平竞争传输信道，每个节点发送的数据分组可以直接传输到目的节点，因此网络中不存在中继节点。从图中可以看出，节点1发送给目的节点3的数据分组P1传输失败，节点2发送给目的节点4的数据分组P2也传输失败，但是目的节点3侦听到了节点2发送的数据分组P2，目的节点4侦听到了节点1发送的数据分组P1，因此当节点2在重传时发送一个编码分组P1P2时，目的节点3和目的节点4分别可以通过解码编码分组恢复丢失的数据分组P1和P2。简而言之，在一个时隙内，通过重传一个编码度为2的编码包，得到了两个数据分组，因此，在重传中使用了网络编码的重传机制，与传统的ARQ机制相比有明显的效率提升。

图2 网络编码在无线网络中的应用

显然，在重传中使用网络编码可以提升网络性能，但是节点在重传中传输的编码分组应该使用多大的编码度N，即编码分组由多少个丢失的数据分组编码组合而成，我们还需要进行分析。编码度N越大，目的节点通过解码编码分组恢复丢失数据分组的概率就越小，因为目的节点需要存储更多的副本分组，才能解码。为此我们在所提出的RMBNC算法中研究了编码度N对重传效率的影响。另外，网络中的节点个数对网络性能也有明显的影响，节点个数越多，数据分组的碰撞概率就越多，节点传输数据分组时丢失的概率也就会越大，因此我们需要研究节点个数对所提出算法的影响。

3 RMBNC算法在MSMR单跳无线网络中的应用

3.1 RMBNC算法的具体实现

在由多个发送方多个接收方组成的单跳无线网络中，由于所有的数据分组都能由发送方直接传输给接收方，所以不存在中继节点，网络编码不能用在直传中，但是可以应用于重传中。RMBNC算法的基本思想是，源节点发送的数据分组直传失败后，在第一次重传中，源节点继续发送该数据分组，当该数据分组又一次传输失败后，在第二次重传中，源节点发送一个编码度为N的编码分组。编码分组由源节点在直传和第一次重传中都传输失败的那个数据分组和网络中其它N-1个节点丢失的N-1个数据分组编码组合而成。如果相应的目的节点还不能通过解码这个编码分组得到该数据分组，则源节点不在重传该数据分组，该丢失的数据分组可以通过网络中其它节点发送到该目的节点的编码分组来恢复，但是该丢失的数据分组在编码分组中的最大传输次数不超过M次。下面我们给出RMBNC算法的具体实现过程。

S1源节点侦听到信道空闲时，发送一个RTS，等待目的节点回复CTS。

S2收到目的节点发来的CTS，发送数据分组到目的节点。

S3当源节点收到目的节点发送的ACK时，传输结束，当收到NACK时，执行第一次重传。

S4第一次重传时，当源节点收到目的节点发送的ACK时，传输结束，当收到NACK时，执行第二次重传。

S5第二次重传时，节点发送一个编码度为N的编码分组。源节点收到ACK，传输结束，收到NACK，传输结束，不在执行重传。

为了在第二次重传中使用网络编码发送编码分组，每个节点必须保存一个表用来存储网络中丢失的数据分组，这个表用来记录丢失数据分组的源地址，目的地址和数据分组的IP号，我们可以把这个表叫做NCTable。节点根据收到的ACK和NACK，更新NCTable表，当某一个丢失的数据分组通过节点解码编码分组得到时，其它节点根据其发送的ACK，移除表中关于该数据分组的信息。

3.2 RMBNC算法的性能评估

我们通过饱和吞吐量和分组丢失率来评估RMBNC算法的性能，并与IEEE 802.11标准对比。

3.2.1 RMBNC算法的饱和吞吐量分析

与IEEE 802.11标准相比，RMBNC算法在第二次重传中发送一个编码度为N的编码分组，网络中的其它节点可以通过解码编码分组得到丢失的数据分组。这样使得N个节点最多能通过一次传输得到N个丢失数据分组，系统吞吐量会得到明显提升，我们使用下面的公式来计算RMBNC算法的饱和吞吐量：

其中，ps表示数据分组成功传输的概率，L表示数据分组的长度，p0表示节点具有N-1个用于解码的副本分组的概率，pe表示传输出错的概率。K表示发送数据分组时允许的最大冲突次数。PI，PS，PC，PE分别信道空闲的概率，传输成功的概率，碰撞概率，传输失败概率，TI，TS，TC，TE分别表示信道空闲的时间，传输成功的时间，碰撞的时间，传输失败的时间。

3.2.2 RMBNC算法的分组丢失率分析

与IEEE 802.11相比，本文所提出的RMBNC算法在分组丢失率性能上面的优势体现在节点发送的数据分组在直传，第一次重传，第二次重传都失败后，仍然可以通过网络中其它节点在第二次重传时发送的编码分组来解码得到丢失的数据分组。因此，RMBNC算法的分组丢失率会明显的小于IEEE 802.11。我们通过下面的公式来计算RMBNC算法分组丢失率。

其中， 表示节点发送数据分组时，达到最大冲突次数而丢分组， 表示节点因冲突次数达到K-1次，只有一次数据分组传输且传输失败， 表示节点因冲突次数达到K-2次，只有二次数据分组传输，且两次传输都失败， 表示节点有3次传输机会，但3次传输都失败。M表示节点丢失的数据分组在编码分组中的最大重传次数。

4 仿真分析

为验证RMBNC算法的优越性能，我们使用饱和吞吐量和分组丢失率来评估网络性能，并使用IEEE 802.11 MAC协议作为对比来分析RMBNC算法的性能。仿真中使用的参数如下所示pe=0.1，K=10，M=5，L=1 000 byte。

在图3中，我们选择50个节点作为仿真中网络节点的个数，通过仿真分析了编码度N对网络吞吐量的影响。从图中可以看出，RMBNC算法的吞吐量远远超过IEEE 802.11标准，在N=2时，RMBNC算法的吞吐量达到最大值。但是随着N的增加，网络吞吐量会逐渐的降低，因此RMBNC算法的编码度N的选择不能过大。

在图4中，我们分析了编码度对分组丢失率的影响。从图中可以看出，RMBNC算法的分组丢失率明显小于IEEE 802.11标准，但随着编码度N的增加，分组丢失率会逐渐的增大。仿真结果表明，RMBNC算法中，编码度N的选择要适中。

图3 编码度N为变量时，网络吞吐量对比

图4 编码度N为变量时，分组丢失率对比

图5中，我们选取的编码度N为3，通过仿真分析节点个数对网络吞吐量的影响。从图中可以看出，RMBNC算法的饱和吞吐量远远高于IEEE 802.11。网络中节点的个数n对RMBNC算法饱和吞吐量有重要的影响，随着n的增加，网络吞吐量会逐渐的降低。

图6中，我们可以看到，节点个数n对分组丢失率有很大的影响。随着n的增加，分组丢失率迅速增大，但从图中我们可以看到RMBNC算法在分组丢失率性能上依然优于IEEE 802.11标准。

图5 节点个数n为变量时，网络吞吐量对比

图6 节点个数为变量时，分组丢失率性能对比

5 总结和展望

本文提出了将网络编码应用于多个发送方多个接收方单跳无线网络中的算法RMBNC,并对算法进行了理论推导和仿真分析。通过饱和吞吐量和分组丢失率这两个性能指标与IEEE 802.11标准进行分析对比，仿真结果表明本文所提出算法的有效性。在接下来的工作中，我们将对影响RMBNC算法的其它因素进行分析，并推导出该算法与IEEE 802.11标准在开销，时延方面的性能对比。

[1] Ahlswede R, Cai N, Li S-Y, Yeung R. network information flow[J]. IEEE Transactions on Information Theory, vol. 46, no. 4,pp.1204-1216, July 2000.

[2] Nguyen D, Tran T, Nguyen T, Bose B. Wireless broadcast using network coding[J]. IEEE Transactions on Vehicular Technology,2009,58(4):914-925.

[3] Wu1 H, Zheng J. Efficient network coding-based multicast retransmission mechanism for mobile communication networks[J]. IET Communications, 2012(6):187-193.

[4] Xiao X, Yang L-M, Wang Wi-P, Zhang S. A wireless broadcasting,retransmission approach based on network coding”.IEEE International Conference on Circuits and Systems for Communications[C].2008,782-786,DOI:10.1109/ICCSC.2008.171,Published by: IEEE Communication Society.

[5] 肖潇, 杨路明, 蒲保兴. 基于网络编码的多节点无线广播重传策略研究[J]. 计算机应用, 2008,28(4):849-852.

[6] 熊志强, 黄佳庆, 刘威, 杨宗凯. 无线网络编码综述[J]. 计算机科学, 2007,34(3),6-10.

[7] IEEE Standard for Information Technology-Telecommunications and Information Exchange between Systems-Local and Metropolitan area Networks-Specific Requirements Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications[S]. IEEE Computer Society, 12 June 2007.

[8] Bianchi G. Performance analysis of the IEEE 802.11 distributed coordination function[J]. IEEE Journal on Selected Areas in Communications, 2000,18(3):535-547.