一种改进的网络编码广播重传算法

王　骁

(中国电子科技集团公司第20研究所 通信事业部， 陕西 西安 710068)

一种改进的网络编码广播重传算法

王骁

(中国电子科技集团公司第20研究所 通信事业部， 陕西 西安 710068)

摘要在无线网络广播传输中，为了提升效率提出改进的基于冗余避免的网络编码广播重传算法(INCBRRA)。对接收状态矩阵进行重排列后，再主动避免重传不可解码的编码组合，从而优先编码有助于接收节点解码的丢失数据包组合。分析结果表明，INCBRRA算法相比于现有算法能有效减少重传次数，提升了传输效率。

关键词无线网络；网络编码；冗余避免；广播重传

网络编码[1]使得网络中间节点能够对转发信息进行编码，在接收节点进行解码，从而提高网络吞吐率，并带来安全方面的优势。基于网络编码在提升无线传输效率方面的优点[2]，近年来出现了多种网络编码应用于无线广播重传[3-5]的相关研究。

无线网络广播可使多个终端同时收到数据，是一种广泛应用的数据传输技术，尤其在卫星通信中应用普遍。然而，由于无线链路容易受到各种干扰，影响了无线广播的可靠性，重传则是提高可靠性的重要手段。现有的无线广播重传有两类：自动重传请求和基于网络编码的重传方法。2006年，Nguyen[3]等将网络编码技术应用于重传策略中，提出了两个接收节点情况下的编码重传策略，减少了平均传输次数，提高了重传效率。文献[5～6]利用反馈丢包的信息，节点对多个需要重传的数据包进行编码组合，再广播重传，称为NCWBR方法。文献[7]针对编码包不可译且接收节点较多的情况，提出改进的基于网络编码的广播重传策略，称为INCBR方法。文献[8]提出主动避免编码冗余的高效网络编码广播重传策略，优先编码重传对解码贡献较大的丢失数据包，称为NCRA方法。文献[9]提出一种基于并行机会式网络编码重传方案，利用并行机制降低算法复杂度。文献[10]实现了基于机会式网络编码的单组合分组广播传输算法和多组合分组广播传输算法，有效降低了广播传输所需的传输带宽。

本文提出改进的基于冗余避免网络编码的广播重传方法，接收节点将不能解码的编码包进行缓存，并且每次重传前对接收状态矩阵进行重新排列，优先发送传输中损耗率较高的数据包同时避免不能解码的编码组合被重复编码，从而提升广播重传的性能。

1系统模型

假设有一个卫星作为信源节点S，并有N(N≥2)个在S广播范围内的用户作为接收节点，构成一个卫星广播网络。

卫星广播重传阶段如下:

阶段1 源节点S向N个接收节点广播M个原始数据包，且各接收节点的丢包率相互独立。

阶段2 固定间隔Δt后，每个接收节点通过发送ACK/NACK反馈数据包的丢失情况，并且ACK/NACK不存在丢失情况，丢失情况包括数据包是否丢失，丢失数据包序列号和丢失节点序列号。

阶段3 根据ACK/NACK生成广播接收状态矩阵R。

阶段4 源节点S根据广播接收状态矩阵R进行数据包编码重传。

阶段3中的数据包广播接收状态矩阵R定义如下：

定义1 数据包广播接收状态矩阵R是每个接收节点对M个原始数据包的接收情况反馈生成的N×M矩阵。矩阵的元素为0或1，其中R(i,j)=0表示第i个接收节点接收到了第j个原始数据包，R(i,j)=1则表示第i个接收节点未能接收到第j个原始数据包。

文献[7]的NCRA算法基本思想是接收节点将不能解码的编码包进行缓存，源节点 在对丢失数据包进行编码重传时，主动避免已经重传过的不能解码的编码组合，同时优先选择最有助于解码接收节点已缓存编码包的丢失数据包进行异或编码，并确保每个重传编码包都至少包含每个接收节点的一个丢失数据包。

引理1 根据本文的系统模型，当n(n≤N)个接收节点丢失某个原始数据包，而另外N-n个接收节点丢失另一个原始数据包，那么应用网络编码技术对这个两个原始数据包进行组合，则可以在重传后使得编码包在接收节点具有可解性。

引理2 根据本文的系统模型，当n(n≤N)个接收节点丢失某个原始数据包，而另外N-n个接收节点丢失另外多个原始数据包，且这些原始数据包在广播状态矩阵中每行当且仅有一个原始数据包丢失。那么将所有丢失的原始数据包进行网络编码组合后，所有的接收节点都可以解码。

2INCBRRA方法

2.1INCBRRA基本原理

本文提出一种改进的冗余避免网络编码广播重传方法(Improved Network Coding Broadcasting Retransmission Algorithm Based Redundancy Avoiding, INCBRRA)，在NCRA算法的基础上提高原始数据包的编码效率。

首先，在ACK/NACK反馈原始数据包丢失情况的基础上对其进行编码重传，编码时避免重传不能解码的丢失原始数据包的编码组合。

其次，在对原始数据包进行编码组合时，通过调整广播接收状态矩阵的列向量，实现优先发送损耗率较高的原始数据包。

最后，在广播接收状态矩阵调整后的基础上基于NCRA算法设计缓存集合C和缓存队列Q。其中，缓存集合C记录所有接收节点成功接收但不能解码的编码组合的集合，初始化C=Φ。缓存队列Q，用来标记出现在缓存集合 中的丢失数据包对于解码缓存中所有编码包的贡献程度，当贡献程度一样时，将序号越小的数据包优先级设置越高，丢失数据包按照优先级从低到高组成缓存队列Q，初始化队列Q=Φ。

2.2INCBRRA算法步骤

步骤1 源节点S依据ACK/NACK生成广播接收状态矩阵R。

步骤2 源节点S对R按照每一列元素“1”的多少进行从大到小前后调整。

步骤3 源节点S在R的每一行寻找第一个“1”数据的位置且该数据包满足可解性条件，并将其组成初始编码序列I。

步骤4S检查缓存集合C，如果C为空，进入步骤 6。否则，判断I中是否包含有C中的组合，如果没有，则进入步骤5。如果I中包含有C中的组合，则对这些组合进行删除，按照缓存队列Q中的顺序依次删除组合中的丢失数据包，直到I中不再包含C中的组合，不将这个组合包含的所有丢失数据包都删除。

步骤5S检查I是否至少包含了每个接收节点的一个丢失数据包。如果是，则将数据包编码后广播发送；如果不是，选取该接收节点对应行的第一个还未参与过编码的丢失数据包加入I，组成重传编码序列IF，将IF中的数据包编码后广播发送。

步骤6 源节点S根据ACK判断编码包是否被各接收节点成功接收。如果编码包被成功接收，S依据重传编码序列IF和接收状态矩阵R，更新缓存集合C和缓存队列Q。随后将R中参与编码的对应位置元素置为“0”。

在步骤6中需要更新缓存集合C和缓存队列Q。缓存集合C和缓存队列Q的具体更新方法如下：首先根据接收状态矩阵，查找出IF中包含的接收节点丢失数据包组成的不能解码的编码组合，然后查找出IF中已经在原缓存集合C中该节点对应的编码组合的丢失数据包，得到当前接收节点在IF中不能解码的组合。如果没有找到这样的组合，表示该节点能够解码IF组成的编码包，再根据解码出的丢失数据包对该节点在C中的组合进行更新。更新完缓存集合C后，将缓存队列Q清零。然后统计C中各丢失数据包在C中出现的频率，再按照频率升序排列，如果频率一样，则将数据包序号大的排在前面，组成新的缓存队列Q。

3应用分析

在一个由单个信源节点和5个接收节点组成无线广播网络中，信源节点向接收节点R1,R2,R3,R4,R5广播10个数据包M1,M2,M3,M4,M5,M6,M7,M8,M9,M10，用图1表示接收节点的初始接收状态矩阵。

M1M2M3M4M5M6M7M8M9M10R10110011000R20010010100R31101000100R41010100010R50010001001

图1初始接收状态矩阵

3.1NCRA算法应用

针对图1的初始接收状态矩阵，NCRA算法首先初始化缓存集合C和缓存队列Q为空集，并根据接收状态矩阵选取每行第1个丢包的序号组成第1次编码序列I1={M1,M2,M3}。第1次最终编码序列IF1=I1，第1次发送的编码包为M1⊕M2⊕M3，通过与表1对比可知，IF1包含了R1的丢包M2和M3，R3的丢包M1和M2，以及R4的丢包M1和M3。这3个接收节点不能对该编码包进行解码，从而根据算法更新缓存后，C={(M2,M3),(M1,M2),(M1,M3)}，Q={M3,M2,M1}。

源节点第2次选择初始编码序列I2={M2,M6,M1,M7}，I2中包含了C中的(M1,M2)组合，按照Q中数据包的顺序，删除I2中的M2后得到第2次最终编码序列IF2={M6,M1,M7}，第2次发送的编码包为M6⊕M1⊕M7。此时的IF2包含了R1的丢包M6和M7，据此更新缓存后，C={(M2,M3),(M6,M7)}，Q={M7,M6,M2,M3}。

源节点第3次选择初始编码序列I3={M2,M8,M3.M10}，I3中包含C中的(M2,M3)组合，从而根据Q中数据包顺序删除I3中的M2后得到第3次最终编码序列IF3={M8,M3,M10}，发送的编码包为M8⊕M3⊕M10。此时，每个接收节点都可以解码，因此C和Q更新为空集。

源节点第4次选择初始编码序列I4={M2,M5}，IF4=I4，发送的编码包为M2⊕M5。此时，每个接收节点都可以解码，因此C和Q更新为空集。

源节点第5次选择初始编码序列I5={M6,M4,M9}，IF5=I5，发送的编码包为M6⊕M4⊕M9。此时，每个接收节点都可以解码，因此C和Q更新为空集。

源节点第6次选择初始编码序列I6={M7}，IF6=I6，发送的编码包为M7，至此5个接收节点均收到10个原始数据包。

3.2INCBRRA算法应用

首先按照算法步骤对图1所示的初始接收状态矩阵进行重新排序后，得到如表2所示的接收状态矩阵。

M3M2M6M8M7M1M4M5M9M10R11110100000R21011010000R30101011000R41000000110R51000100001

图2第1次重排序的接收状态矩阵

源节点针对图2所示，第1次选择初始编码序列I1={M3，M4}。在R3所处的行选择数据包时，考虑到令I1不包含R1和R2两个丢失数据包，因此不选择M2，M8，M1，最终选择数据包M4。此时，第1次发送的编码包为M3⊕M4，所有接收节点均能解码，那么C和Q为空集。

编码包被接收节点解码后，接收状态矩阵会有相应的变化，针对其变化按照算法对其进行重新排序后得到如图3所示的接收状态矩阵。

M6M2M8M7M1M5M9M10M4M3R11101000000R21010100000R30110100000R40000011000R50001000100

图3第2次重排序的接收状态矩阵

源节点针对表3，第2次选择编码序列I2={M6,M2,M5,M10}，在R3所处的行选择数据包时，所有可选择的数据包M2,M8,M1均会令I2包含R1和R2两个丢失数据包，因此按照算法，仍旧选择第一个数据包M2；在R5所处的行选择数据包时，考虑到选择M7会令I2包含R1的两个丢失数据包，因此选择M10；最终发送的编码包为M6⊕M2⊕M5⊕M10；此时I2包含R1的两个丢失数据包M6和M2，更新缓存后C={(M6,M2)}，Q={M6,M2}。

编码包被接收节点解码后，接收状态矩阵会有相应的变化，针对其变化按照算法对其进行重新排序后得到如图4所示的接收状态矩阵。

M7M8M1M6M2M9M10M4M3M5R11001100000R20110000000R30110000000R40000010000R51001000000

图4第3次重排序的接收状态矩阵

源节点针对图4所示，第3次选择编码序列I3={M7,M8,M9}，发送的编码包为M7⊕M8⊕M9，所有接收节点均能解码，那么C和Q更新为空集。

编码包被接收节点解码后，接收状态矩阵会有相应的变化，针对其变化按照算法对其进行重新排序后得到如表5所示的接收状态矩阵。

M1M6M2M10M4M3M5M7M8M9R10110000000R21000000000R31000000000R40000000000R50000000000

图5第4次重排序的接收状态矩阵

源节点针对图5所示，第4次选择编码序列I4={M6,M1}，发送的编码包为M6⊕M1，所有接收节点均能解码，C和Q仍为空集。编码包被接收节点解码后，接收状态矩阵会有相应的变化，针对其变化按照算法对其进行重新排序后得到如图6所示的接收状态矩阵。

M2M10M4M3M5M7M8M9M6M1R11000000000R20000000000R30000000000R40000000000R50000000000

图6第5次重排序的接收状态矩阵

源节点针对图6所示，第5次选择编码序列I5={M2}，发送的编码包为M2。

至此，所有5个接收节点均收到10个原始数据包。从算法应用分析可以看出，INCBRRA算法相比于NCRA算法，减少了重传次数，提高了广播重传效率。

4结束语

本文利用网络编码在无线网络传输中的应用，提出一种改进的基于冗余避免网络编码广播重传方法，根据接收节点反馈的缓存编码包信息，同时考虑传送损耗率较高的丢失数据包和避免传送不能被解码的丢失数据包组合，达到了减少广播重传次数和提升传输效率的目的。

参考文献

[1]Ahlswede R,Cai N, SYR L, et al. Network information flow [J]. IEEE Transactions on Information Theory,2000 (46): 1204-1206.

[2]Katti S, Rahul H, Hu W, et al. Xors in the air: practical wireless network coding[C].Shanghai: SIGCOMM,2006.

[3]Neguyen D,Nguyen T,Bose B,Wireless broadcasting using network coding [R].Oregan: Technical Report: OSU-TR-2006-06, Oregon State University,2006.

[4]Wu Y, Chou P A, Kung S Y. Information exchange in wireless networks with network coding and physical-layer broadcast [R].CA,USA: Technical Report MSR-TR -2004-78, Microsoft Research,2004.

[5]肖潇,王伟平,杨路明,等.基于网络编码的无线网络广播重传方法[J]. 通信学报,2009,30(9):69-75.

[6]肖潇,杨路明,王伟平.高损耗无线网络中基于网络编码的广播重传策略[J].中南大学学报:自然科学版,2008,39(6):1291-1295.

[7]孙伟,张更新,边东明,等.卫星通信中基于网络编码改进的广播重传策略[J]. 宇航学报,2013,34(2):231-236.

[8]姚玉坤,陈曦,任智,等.基于冗余避免的高效网络编码广播重传方法[J].系统工程与电子技术,2015,37(5):1170-1176.

[9]王斌,王文鼐.一种基于并行网络编码的无线广播重传方案[J]. 南京邮电大学学报:自然科学版,2014,34(6):9-14.

[10]卢冀,吴成柯,肖嵩,等.基于机会式网络编码的高效广播传输算法[J].通信学报,2012,33(1):64-70.

An Improved Broadcast Retransmission Algorithm Based on Network Coding

WANG Xiao

(Communications Division，China Electronics Technology Group Corporation No.20 Institute, Xi’an 710068, China)

AbstractFor the purpose of improving the transmission efficiency of the network coding broadcasting retransmission method, thus reducing the retransmission times, an improved network coding broadcasting retransmission algorithms based on redundancy avoiding(INCBRRA) is proposed. After rearrange the receive matrix, it voluntarily avoids redundant transmission of the combination which can not decoded by the receiving nodes, and preferentially codes the lost packets which are conducive to decoding. The analysis results shows that compared to existing algorithms, INCBRRA can reduce the number of retransmission times and improve the transmission efficiency.

Keywordswireless network; network coding; redundancy avoiding; broadcasting retransmission

收稿日期:2015-04-29

作者简介:王骁(1984-)，男，博士，工程师。研究方向：网络编码，数据通信。

doi:10.16180/j.cnki.issn1007-7820.2016.06.018

中图分类号TN926

文献标识码A

文章编号1007-7820(2016)06-061-04