基于冗余避免的高效网络编码广播重传方法

姚玉坤， 陈　曦， 任　智， 易建琼， 雷宏江

(重庆邮电大学移动通信技术重庆市重点实验室， 重庆 400065)



基于冗余避免的高效网络编码广播重传方法

姚玉坤， 陈曦， 任智， 易建琼， 雷宏江

(重庆邮电大学移动通信技术重庆市重点实验室， 重庆 400065)

摘要：为了提高无线网络中基于网络编码的广播重传方法的编码效率，从而有效地减少重传次数和数据包传输时延，提出一种主动避免编码冗余的高效网络编码广播重传方法(network coding broadcasting retransmission approach based on redundancy avoiding，NCRA)。NCRA编码时主动避免不能解码的编码组合被重复编码重传，同时优先编码重传对接收节点已缓存的未解码编码包的解码贡献较大的丢失数据包以充分利用编码机会，在对解码贡献相同的条件下优先编码较早丢失的数据包以减小数据包传输时延。理论分析和仿真结果表明，NCRA算法相比于现有算法能有效减小重传次数和降低数据包传输时延，减少网络开销，进一步提高了编码重传的效率。

关键词：无线网络; 广播重传; 网络编码; 编码组合; 冗余避免

0引言

在无线网络广播传输中，由于无线链路的不可靠特点，极易造成数据包的丢失或者传输错误，重传是改善传输可靠性的有效方法[1]。网络编码(network coding, NC)的提出为提高无线网络广播重传效率提供了新的解决思路[2]。

网络编码允许网络中间节点对接收到的数据信息采用线性或者非线性的方式进行编码处理后转发以提高数据的传输效率[3-5]。将网络编码技术应用于广播重传，源节点在对接收节点丢失的数据包进行重传时，不是重传单一的某个丢失数据包，而是将多个接收节点丢失的不同数据包进行编码组合后再重传，实现通过一次发送就可以同时恢复多个接收节点的丢失数据包的效果，从而达到减少重传发送次数、提高重传效率的目的。

文献[6]使用网络编码技术提出了在无线网络中优化吞吐量的方法。文献[7]在无线Mesh网络中提出了机会式网络编码，可以提高网络吞吐量。文献[8-9]将机会式网络编码思想应用于无线网络广播重传，可以改善重传的性能。文献[10]针对每个丢失数据包赋一个效用值，提出了基于Sort-By-Utility(SBU)的网络编码广播重传算法。但是其要求生成的编码包必须能被所有接收节点解码，因此参与编码的原始数据包的个数受到限制，没有充分利用每次编码机会。文献[11]在SBU算法的基础上，提出了Benefit算法，接收节点从多个重传包中恢复出丢失数据包，有效地提高了网络吞吐量，但是其算法判断条件较为复杂，不易实现。文献[12]提出按照数据包的发送顺序依次编码丢失数据包的广播重传算法。但是当丢包率较大，编码包不能被解码的概率较大的情况下，性能不佳。文献[13]提出了基于机会式网络编码多组合分组广播传输算法(opportunistic network coding based multiple combination packets broadcast transmission，ONCMB)，该算法将不能解码的编码包进行缓存，通过后续成功恢复的丢失数据包来机会性地解码缓存中的编码包，从而减少重传次数。但是该算法存在不能被解码的丢失数据包组合被重复编码重传的情况，导致接收节点虽然能够多次成功接收但均无法解码这些编码包的问题，且需要单独重传丢失数据包来解码缓存编码包，因此降低了网络重传效率。

本文以上述研究工作为基础，提出了主动避免编码冗余的网络编码广播重传方法(network coding broadcasting retransmission approach based on redundancy avoiding，NCRA)。NCRA算法的基本思想是：接收节点将不能解码的编码包进行缓存，源节点在对丢失数据包进行编码重传时，通过主动避免已经重传过的不能解码的编码组合的冗余发送，同时优先选择能够最有助于解码接收节点已缓存编码包和降低数据包传输时延的丢失数据包进行编码，并确保每个重传编码包都至少包含每个接收节点的一个丢失数据包，以提高每次编码的有效性，达到进一步改善重传性能的目的。

1网络模型及问题描述

本文研究所使用的网络模型与文献[12-13]相同，是由一个广播源节点和M(M≥2)个接收节点组成。广播传输过程分为2个阶段：原始数据包发送阶段和丢失数据包编码重传阶段。在原始数据包发送阶段，假设广播源节点以固定的时间间隔Δt广播发送N个原始数据包，各接收节点通过同步发送控制包(acknowledgement/negative acknowledgment，ACK/NACK)到源节点来反馈数据包的接收状态，并假设ACK/NACK控制包不存在丢失，且各接收节点的丢包率相互独立。在丢失数据包编码重传阶段，源节点对所有接收节点丢失的数据包进行编码重传。源节点将不同接收节点的丢失数据包进行异或运算编码后重传，这样不同的接收节点可以从一个编码包中恢复各自的丢失数据包，能够提高网络重传性能。

定义 1数据包接收状态矩阵T。是指广播源节点根据各接收节点对所有原始数据包的接收情况的反馈而生成的矩阵。假设网络中有M个接收节点(R1,R2,…,RM-1, RM)，源节点在原始数据包发送阶段发送了N个数据包(P1,P2,…,PN-1, PN)，则T则为M行N列的0/1矩阵。矩阵中的元素为“0”表示对应行的接收节点成功接收到了对应列的数据包，为“1”则表示丢失了该数据包。

定理 1如果编码包中包含了某个接收节点的2个及以上丢失数据包，则该接收节点将不能解码编码包。

证明假设编码包A(P1⊕P2…Pi-1⊕Pi…Pj⊕Pj+1…Ps)，包含了接收节点R1的任意2个丢失数据包Pi和Pj，根据异或运算解码可得。

(1)

从式(1)可知，R1不能解码编码包A，因此不能恢复出丢失数据包Pi和Pj。同理可知，当编码包A包含了R1的2个以上丢失数据包时也不能被解码，从而定理1成立。

证毕

文献[13]提出的机会式网络编码多组合分组广播传输算法ONCMB，在对丢失数据包进行编码重传时包含以下2个阶段。

阶段1：源节点依次选取接收状态矩阵中每行对应的第1个丢失数据包组成重传编码包，而后接收节点反馈ACK/NACK控制包说明其是否收到传输的编码数据包。如果收到，则将接收状态矩阵中所选取编码的丢失数据包位置置为“0”。接收节点将不能解码的编码包进行缓存。依次类推，直到所有编码包成功发送。

阶段2：源节点根据发送的所有编码包的信息，查找接收节点没有成功恢复的ε(ε≥2)个丢失数据包，重传ε-1个不可恢复的丢失数据包，接收节点再通过解码缓存的编码包获取最后一个丢失数据包。

ONCMB算法有效地提高了重传性能，但仍存在以下不足。

(1)ONCMB算法编码时存在已经重传过的不能解码的丢失数据包编码组合被冗余发送的情况。这样会导致已经缓存有该编码组合的接收节点一定不能解码该编码包，且占用了其他丢失数据包参与编码的机会。当接收状态矩阵中所有为“1”位置的丢失数据包都参与了编码后，存在接收节点仍有缓存编码包没有被解码，相应的丢失数据包没有被恢复，源节点需要再重传丢失数据包来解码，从而导致重传次数增加，数据包传输时延增大等问题。

(2)ONCMB算法中接收节点将不能解码的编码包进行缓存。该算法没有考虑到源节点如何主动利用这些已经缓存的编码包信息来优化源节点的编码方法，以较少的发送次数通过后续的重传使接收节点可以较快的将缓存中的编码包解码出来。

2NCRA方法的编码原理

2.1NCRA基本思想与方法描述

在对丢失数据包进行编码重传时，如果要求生成的编码包必须能被所有接收节点可解，参与编码的丢失数据包受到限制，影响重传效率。因此NCRA算法同ONCMB算法一样，允许接收节点对编码包不能立即解码的情况存在，且仍将不能解码的编码包进行缓存。

NCRA算法的主要创新思想如下：

(1) 编码重传时，避免已经重传过的不能解码的丢失数据包编码组合的重复发送，去除编码冗余，提高编码效率。

(2) 源节点利用接收节点的缓存编码包信息来实现优先对解码缓存编码包贡献较大的丢失数据包进行编码，提高缓存编码包解码效率。

(3) 优先编码较早丢失的数据包以降低数据包传输时延。

(4) 保证每个编码包都包含所有存在丢包情况的接收节点的至少一个丢失数据包，以尽快恢复所有接收节点的丢失数据包。

设计缓存集合C和缓存队列Q，分别用以记录接收节点缓存的编码组合信息和存储丢失数据包对解码缓存编码包的贡献优先级。

定义 2缓存集合C，用来记录所有接收节点成功接收但不能解码的编码组合的集合。源节点根据接收状态矩阵，将参与编码重传的丢失数据包组合中所有接收节点不能解码的编码组合进行记录。初始化C=∅。

定义 3缓存队列Q，用来标记出现在缓存集合C中的丢失数据包对于解码缓存中所有编码包的贡献程度。某丢失数据包出现在集合C中的频率越大，说明恢复该丢失该数据包能够解码出较多的编码包，因此该丢失数据包对于解码缓存中的所有编码包越重要，即贡献程度越大，编码优先级越高。如果频率一样，为了降低数据包恢复时延，将包序号越小的数据包设优先级越高。将出现在缓存集合C中的丢失数据包按照优先级从低到高组成缓存队列Q。初始化队列Q=∅。

NCRA算法具体步骤如下：

步骤 1在丢失数据包编码重传阶段，源节点根据所建立的数据包接收状态矩阵，依次选取每行第一个为“1”的丢失数据包组成初始编码序列S。

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

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

步骤 4接收节点通过ACK向源节点反馈该编码包是否成功接收。

步骤 5根据各接收节点的反馈，如果成功接收该编码包，源节点依据编码序列SF和接收状态矩阵，更新集合C和队列Q。随后将接收状态矩阵中参与编码的对应位置置为“0”。

缓存集合C和缓存队列Q的具体更新方法如下：

首先根据接收状态矩阵，查找出SF中包含的接收节点丢失数据包组成的不能解码的编码组合，然后查找出SF中已经在原缓存集合C中该节点对应的编码组合的丢失数据包，得到当前接收节点在SF中不能解码的组合。如果没有找到这样的组合，表示该节点能够解码SF组成的编码包，再根据解码出的丢失数据包对该节点在C中的组合进行更新。

更新完缓存集合C后，将缓存队列Q清零。然后统计C中各丢失数据包在C中出现的频率，然后按照频率升序排列，如果频率一样，则将数据包序号大的排在前面，组成新的缓存队列Q。

对上述方法举例说明如下。假设Sf={Pr,Pt,Pu,Pv}，接收节点R1在原缓存集合C中的不可解码的组合为{(Px,Pr)}，且在接收状态矩阵中，R1对Sf中的对应数据包的接收状态是{0,1,1,0}。首先依据接收状态矩阵，查找出SF中R1不能解码的组合{Pt,Pu}。然后查找出SF中的数据包出现在R1对应的原缓存集合C中的组合的丢失数据包。

(2)

此时可得Sf中R1不能解码的编码组合为(Pr,Pt,Pu)。根据R1节点更新C为{(Px,Pr), (Pr ,Pt,Pu)}。

2.2NCRA算法的应用分析

下面以图1为例对NCRA与ONCMB算法进行应用分析。图1表示源节点根据5个接收节点对10个原始数据包的反馈信息生成的接收状态矩阵。为了便于分析，假设编码包不存在丢失。在图1中，不同的几何符号(即三角形、圆形、长方形、正六边形)分别用来标记第1、2、3、4次参与编码重传的丢失数据包。

用图1(a)来具体阐述ONCMB重传方法的应用结果。在阶段一中，源节点依次发送4个编码包(P1⊕P2⊕P3)，(P2⊕P3⊕P6⊕P7)，(P4⊕P5⊕P6⊕P8⊕P10)，(P7⊕P8⊕P9)。将矩阵中所有为“1”位置的丢失数据包编码重传后，源节点需要通过发送的所有编码包信息来计算是否有接收节点还有数据包未被恢复，即是否存在接收节点有缓存编码包没有被解码。通过计算得出R1有数据包P2和P3未被恢复(具体计算方法见参考文献[13])。进入阶段2，重传丢失数据包P2(图1(a)中用虚线标出)，并通过解码缓存中的编码包可恢复出丢失数据包P3，从而恢复所有丢包。从图1(a)可知，编码包P1⊕P2⊕P3和P2⊕P3⊕P6⊕P7均同时包含了R1节点的丢包P2和P3，R1不能对这2个编码包解码，进行缓存。P2⊕P3⊕P6⊕P7再次包含了R1不能解码的编码组合P2⊕P3，因此这个组合的发送对于R1来讲是冗余的，而且也占用了R1其他丢失数据包参与编码的机会。针对图1而言，应用ONCMB算法一共需要5次重传才能恢复所有节点丢失的数据包。

图1　NCRA与ONCMB算法的应用

下面结合图1(b)详细阐述NCRA重传算法的应用结果。Si(i=1,2,3…)表示每次编码重传NCRA算法选择的初始编码序列，SFi表示每次重传最终发送的编码序列。

NCRA算法首先初始化缓存集合C、缓存队列Q为空集，并根据接收状态矩阵选取每行第1个丢包的序号组成第1次初始编码序列S1={P1, P2, P3}。由于C、Q为空集，因此第1次最终编码序列SF1=S1，源节点第1次发送的编码包是P1⊕P2⊕P3。根据图1，SF1包含了R1的丢包P2和P3，R3的丢包P1和P2，R4的丢包P1和P3，这3个接收节点将不能对该编码包进行解码，会进行缓存，所以更新缓存集合C为{( P2,P3),( P1,P2),( P1,P3)}，队列Q为{P3, P2, P1}。

源节点第2次选择初始编码序列S2={P2, P3, P6, P7}。对比集合C，可知S2中包含了C中的(P2, P3)组合。于是按照队列Q中的丢失数据包顺序应删除数据包P3，则编码序列变为(P2, P6, P7)。由于(P2, P6, P7)仅包含了R1，R2，R3，R5的丢包，未包含R4的丢包。故选择矩阵的第4行中未在已经重传过的编码包中出现的第1个数据丢包“P5”加入编码序列，组成SF2为{P2, P5, P6,P7}。源节点第2次发送的编码包是P2⊕P5⊕P6⊕P7。这个编码包发送以后，除了R1，其他节点都能对其解码。根据缓存集合C的更新方法，更新C为{(P2, P3),(P1,P3),(P2, P6, P7)}，更新Q为{P7, P6, P1, P3, P2}。

源节点第3次选择编码序列S3={P3,P4,P8,P10}，未包含集合C中的组合。因此SF3=S3={P3,P4,P8,P10}。随后更新C为{(P6,P7)}，Q为{P7,P6}。

源节点第4次选择编码组合序列S4={P7,P8,P9}，没有包含集合C中的组合，故取SF4=S4为{P7,P8,P9}。至此，所有接收节点可以通过解码缓存中的编码包成功恢复出之前的所有丢包。由此可见，对图1而言，应用NCRA算法一共只需4次编码重传，达到了理论下限值。相比ONCMB，NCRA减少了编码包的重传次数，提高了重传性能。

定理 2当同一接收节点的多个丢失数据包被编码在全部编码包中的编码组合信息都一样时，该接收节点将不能解码这多个丢包的编码组合。

证明假设Px和Py是同一接收节点的2个丢包，并假设在全部编码包中的编码组合信息都一样，即 Px和Py要么同时被编码在某个编码包中，要么同时不被编码在编码包中。根据异或运算解码，解码的结果是Px⊕Py或者0，不能解码出Px或者Py。同理可知，大于2个丢包的编码组合也是如此。

证毕

令Ei(n)=1(1≤i≤k, 1≤n≤N,)表示数据包Pn编码于SFi，反之Ei(n)=0表示Pn 未编码于SFi。其中，k表示重传阶段生成的重传编码包的总数。Ei(n)=1(1≤i≤k)组成编码矩阵E，表示数据包参与重传编码包中的信息。

根据上图1(a)和1(b)中，得出ONCMB与NCRA算法的编码矩阵Ea和Eb，如图2所示。

图2　NCRA与ONCMB算法的应用

从图2(a)中可以看出，丢失数据包P2和P3,在全部编码包中的编码信息都一样。同理还有P4和P5，P8和P9。但是只有P2和P3同时是R1节点的丢包。因此R1节点接收到所有编码包以后也不能解码出P2和P3。

图2(b)表明的是，由于NCRA算法在编码时，不能解码的丢失数据包编码组合不会重复出现在其他编码包中，所以同一接收节点的多个丢包的编码信息一定会不一样。当编码阶段结束，所有的编码包都将会被解码。NCRA算法不需要ONCMB算法第2阶段的重传发送，减少了重传发送次数，有效地提高了重传性能。

3NCRA算法性能的理论分析

假定网络中有M个接收节点，各接收节点的丢包率服从伯努利分布且互不相关。令li表示接收节点 Ri(1≤i≤M)的丢包率，lmax=Max(li)，并假设源节点在广播原始数据包阶段一共发送了N个原始数据包。

3.1平均传输次数

定义 4数据包平均传输次数UA，是指为了使所有接收节点最终成功接收N个原始数据包，源节点所需的对原始数据包的平均传输次数，其大小为

(3)

式中，H表示重传阶段的总的传输次数，H/N是原始数据包的平均重传次数的大小，记为Ha。

(4)

(5)

由式(5)可知，数据包平均重传次数为

(6)

代入式(3)可得

(7)

由于ONCMB在将所有丢失数据包编码重传后，有接收节点缓存的编码包不能被解码，源节点需要再重传丢失数据包来解码缓存编码。所以ONCMB的平均传输次数UB为

(8)

式中，η表示ONCMB通过发送丢失数据包来解码缓存编码包的平均传输次数。对比式(7)和式(8)可知，NCRA算法的平均传输次数小于ONCMB算法。

3.2数据包平均传输时延

定义 5数据包平均传输时延D(n)，表示所有接收节点成功接收到第n(1≤n≤N)个数据包Pn的平均传输时延。用dx表示接收节点Ri(1≤i≤M)成功收到数据包Pn的传输时延，di(n)表示该传输时延均值。

如果数据包Pn在Ri节点没有出现丢失，Pn的传输时延dx为

(9)

式中，Δt表示源节点发送数据包的时间间隔大小。

若Pn在Ri出现丢失，当N个数据包发送完以后，则需要通过重传恢复Pn的时延dx为

(10)

式中，Ha表示原始数据包的平均重传次数(见式(6))；n×Ha为n个数据包的重传次数。

由于Ri节点的丢包率为li，故，Ri成功收到数据包Pn的平均时延di(n)为

(11)

NCRA在所有接收节点成功接收Pn的平均传输时延为

(12)

使用ONCMB算法时，有一部分丢失数据包是在编码重传阶段结束后，源节点通过单独重传这些丢失数据包来恢复的，这些丢失数据包的传输时延较大，为Δt×(N+N×Ha)，因此这一部分丢失数据包的平均传输时延为

(13)

对比式(11)和式(13)可知ONCMB的数据包平均传输时延大于NCRA算法。

另外，NCRA算法在对丢失数据包进行编码重传时，除了考虑优先重传能够使得接收节点缓存中的编码包解码的丢失数据包以后，还考虑优先传输数据包序号较小的丢失数据包。丢失数据包的序号越小，表明该数据包越早被丢失，所以优先传输数据包序号较小的丢失数据包，能够降低数据包传输时延。

3.3算法复杂度

NCRA算法主要包括编码和更新2部分。在编码部分中，由于数据包接收状态矩阵为M×N矩阵，选取初始编码序列的时间复杂度为o(M×N)。缓存队列Q的可能最大长度为N，根据缓存优先级来组成重传编码序列的时间复杂度为o(N)。在集合C和队列Q的更新部分中，由于初始编码序列的可能最大长度为M，且需要判断的次数即是接收节点的个数为M，所以更新集合C的时间复杂度为o(M2)。依据集合C更新队列Q的时间复杂度为o(N)。NCRA算法的时间复杂度为o(M×N+M2)。

4仿真实验及分析

4.1仿真环境及参数设置

本文使用的仿真工具是OPNET14.5。采用的网络模型是在400m×400m的平面区域内，由1个广播源节点和M(M=5,10,15)个接收节点组成的无线单跳广播网络。节点MAC层采用IEEE802.11b标准，最高速率为11Mb/s。在原始数据包广播阶段和丢失数据包编码重传阶段，发送数据包的时间间隔为1s，发送的原始数据包的个数用N表示。仿真实验中对比了以下算法：文献[]提出的NCWBR算法、文献[]提出的ONCMB算法、本文提出的NCRA算法。

4.2仿真结果及分析

(1) 重传次数

重传次数是源节点在重传阶段为了恢复所有丢失数据包发送的数据包的总次数。

在原始数据包发送阶段，设置接收节点丢包率l=0.2，网络中接收节点的个数M=5，发送原始数据包的个数为[100～500]。仿真结果图3展示了当源节点发送不同原始数据包个数时，各种算法的重传次数。从图中可以看出随着原始数据包的个数不断增加，接收节点丢失的数据包越多，需要重传的次数越大。由于NCRA算法在编码重传时避免不能解码的编码组合冗余发送，且优先重传了有利于解码缓存中编码包的丢失数据包，所以在重传次数方面优于其他两种算法。

图3　不同原始数据包发送个数下的重传次数

仿真结果图4得出了在不同丢包率下，源节点发送500个原始数据包时的重传次数。接收节点的个数M=5，丢包率l设置为[0.1～0.4]，步长为0.1。随着丢包率的增加，接收节点丢失的原始数据包越多，且重传的编码包不能被解码的概率增大。NCWBR算法没有利用不能解码的编码包，导致重传次数的大幅增大。ONCMB算法与NCRA算法都将不能解码的编码包进行了缓存，从而比NCWBR需要的重传次数要少。NCRA算法编码方法相比ONCMB更优化，更有效地利用了编码机会，从而减少了更多的重传次数。

图4　不同丢包率下的重传次数

仿真结果图5是网络重传次数在接收节点个数不同的网络场景下的仿真结果。丢包率为0.2，源节点发送的原始数据包的个数为300，接收节点的个数M分别为5,10,15的场景。当网络节点数增大时，虽然发送的原始数据包的个数没有发生变化，但是由于接收节点的个数增多，原始数据包中出现丢失的概率增大。每次参与编码的丢失数据包增多，导致编码包长度增大，从而不被解码的概率增大。从图中可以看出，当接收节点的个数增多时，NCRA算法通过接收节点的缓存包信息来调整参与编码的丢失数据包，有效地提高了编码效率，从而降低了网络重传次数。

图5　不同接收节点个数下的重传次数

(2)数据包平均传输时延

数据包传输时延是指从源节点发送原始数据包开始，到所有接收节点成功收到所有原始数据包所用的平均时间。

图6得出了在源节点发送200个原始数据包，接收节点的个数M=5，丢包率为[0.1～0.4]的情况下，数据包平均传输时延。从图中可以看出，NCRA算法的平均传输时延要比其他算法低，因为NCRA算法不仅降低了网络重传次数，而且优先恢复了较早丢失的数据包，所以降低了数据包平均传输时延。

图6　数据包平均恢复时延

(3)重传阶段网络开销

重传网络开销包括重传阶段发送的编码包，用以解码缓存编码包的丢失数据包，以及控制包的总比特数。

图7展示了重传阶段的网络开销统计结果。仿真场景为接收节点的个数M=5，接收节点的丢包率为0.2，源节点发送的原始数据包的个数为[100～400]。由于NCRA算法相比其他算法，能够有效地降低重传次数，从而减少了编码包和ACK控制包的发送，因此降低了重传阶段的网络开销。

图7　网络重传开销

5结束语

针对现有ONCMB存在的问题，本文提出了NCRA算法。NCRA在编码时避免了不能解码的组合的重复发送，同时根据接收节点的缓存编码包信息优化了源节点的编码方法，能够有效地提升广播重传效率，理论分析和仿真实验说明：NCRA与NCWBR和ONCMB算法相比，能够有效减少重传次数，降低数据包的平均传输时延。在下一步的工作中，我们将深入探究如何在原始数据包广播阶段同时对丢失的数据包进行编码重传，以达到进一步降低丢失数据包平均传输时延的目的。

参考文献：

[1] Dianati M, Ling X H, Naik K, et al. A node cooperative ARQ scheme for wireless ad hoc networks[J].IEEETrans.onVehicularTechnology, 2006, 55(3):1927-1938.

[2] Ahlswede R, Cai N, Li S Y R, et al. Network information flow[J].IEEETrans.onInformTheory, 2000, 46(4):1204-1216.

[3] Mansouri H S, Pakravan M R. Network coding based reliable broadcasting in wireless ad hoc network[C]∥Proc.oftheIEEEInternationalConferenceonNetworks, 2007:525-530.

[4] Ho T, Medard M, Shi J, et al. On randomized network coding[C]∥Proc.ofthe41stAnnualAllertonConferenceonCommunicationControlandComputing,2003:1354-1357.

[5] Koetter R, Medard M. An algebraic approach to network coding[J].IEEE/ACMTrans.onNetworking, 2003, 11(5):782-795.

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

[7] Katti S, Rahul H, Hu W, et al. Xors in the air:practical wireless network coding[J].IEEE/ACMTrans.onNetworking, 2008, 16(3):497-510.

[8] Nguyen D, Nguyen T, Bose B.Wireless broadcasting using network coding[R].Oregon State University,OSU-TR-2006-06.

[9] Nguyen D, Tran T, Nguyen T, et al. Wireless broadcast using network coding[J].IEEETrans.onVehicularTechnology, 2009, 58(2):914-925.

[10] Rozner E, Padmanabha A, Mehta Y, et al. ER:efficient retransmission scheme for wireless LANs[C]∥Proc.oftheACMCoNEXT, 2007:613-625.

[11] Qureshi J, Foh C H, Cai J. An efficient network coding based retransmission algorithm for wireless multicast[C]∥Proc.oftheInternationalSymposiumonPersonal,Indoor,andMobileRadioCommunications, 2009:691-695.

[12] Xiao X, Wang W P, Yang L M, et al. Wireless broadcasting retransmission approach based on network coding[J].JournalonCommunications,2009, 30(9):69-75.(肖潇, 王伟平, 杨路明,等. 基于网络编码的无线网络广播重传方法[J]. 通信学报, 2009, 30(9):69-75.)

[13] Lu J, Wu C K, Xiao S, et al. Efficient broadcast transmission algorithms based on opportunistic network coding[J].JournalonCommunications, 2012,33(1):64-70.(卢冀, 吴成柯, 肖嵩等. 基于机会式网络编码的高效广播传输算法[J]. 通信学报, 2012,33(1):64-70. )

姚玉坤(1964-)，女，教授，主要研究方向为宽带无线移动通信网络及网络编码。

E-mail:yaoyk@cqupt.edu.cn

陈曦(1989-)，女，硕士研究生，主要研究方向为无线网络编码。

E-mail:xiflycn@sina.cn

任智(1971-)，男，教授，博士，主要研究方向为宽带无线移动通信网络。

E-mail:renzhi@cqupt.edu.cn

易建琼(1986-)，女，硕士，主要研究方向为无线网络编码。

E-mail:464257824@qq.com

雷宏江(1976-)，男，副教授，博士，主要研究方向为无线自组织网络。

E-mail:191792320@qq.com

网络优先出版地址：http://www.cnki.net/kcms/detail/11.2422.TN.20141110.0944.001.html

Efficient network coding broadcasting retransmission

approach based on redundancy avoiding

YAO Yu-kun， CHEN Xi， REN Zhi， YI Jian-qiong， LEI Hong-jiang

(ChongqingKeyLaboratoryofMobileCommunicationTechnology,ChongqingUniversity

ofPostsandTelecommunications,Chongqing400065,China)

Abstract:For the purpose of improving the coding efficiency of the network coding broadcasting retransmission method in wireless network, thus reducing the retransmission times and the packets transmission delay, an efficient network coding broadcasting retransmission approach based on redundancy avoiding (NCRA) is proposed. According to NCRA, when the source node codes the lost packets together, it voluntarily avoids redundant transmission of the combination which cannot be decoded by the receiving node. At the same time, NCRA preferentially codes the lost packets which are conducive to decoding more cached coded packets. Under the condition that multiple lost packets have the same effect on decoding cached coded packets, the source node preferentially encodes the earliest lost packet to reduce the packet transmission delay. The theoretical analysis and simulation results reveal that compared to the existing algorithms, NCRA can significantly reduce the number of retransmission times and the average packets transmission delay.

Keywords:wireless networks; broadcasting retransmission; network coding; coded combination; redundancy avoiding

作者简介：

中图分类号：TP393

文献标志码：ADOI:10.3969/j.issn.1001-506X.2015.05.30

基金项目：重庆市自然科学基金项目(CSTC2012jjA40040)；长江学者和创新团队发展计划资助(IRT1299)；重庆市科委重点实验室专项经费(D2011-24)

收稿日期：2014-03-18；修回日期：2014-08-26；网络优先出版日期：2014-11-10。