应用网络编码的动态连续协作重传改进算法

姚玉坤，张云霞，宋威威，濮 浩，李 威

(重庆邮电大学通信与信息工程学院，重庆400065)

E-mail:332459950@qq.com

1 引言

多跳无线网络中，由于无线链路的不可靠传输，总是存在数据包发生丢失或出错，而重传方法作为一种有效途径用于解决上述问题.2003年提出的网络编码［1］(Network Coding，NC)，允许中间节点对多个原始包进行编码后传输，目的节点再解码，进一步提高了无线网络的性能、网络吞吐量.文献［2］提出了机会网络编码(Opportunity Network Coding，ONC)，且给出了具体的编解码方式.由于ONC简单且易于实现，因此成为近些年重传策略研究的重点，且取得了许多研究成果［3，4］.

文献［5，6］中将ONC与ARQ相结合的重传策略在重传速率及重传次数上明显优于传统的ARQ机制.肖潇［7］等人提出了能相对减少平均传输次数的网络编码广播重传策略(Network coding wireless broadcasting retransmission，NCWBR)，但该算法存在有些编码包无法完全解码的问题.针对NCWBR不可解码问题，孙伟，张更新［8］等人提出一种改进的编码重传策略(Improved network coding based broadcasting retransmission，INCBR).文献［9］提出了加权广播重传算法(Weighted opportunistic network coding retransm-ission，WONCR)，该算法将减少重传次数的问题转化为了链路质量加权的最大增益问题.文献［10，11］提出应用汉明重量的丢包选择的重传方法.文献［12-16］中，通过结合协作通信和网络编码技术以快速恢复丢包.上述重传算法均是分批进行数据传输，且在不同批间无法进行丢包的编码重传，因此可称为块内编码重传(Intra-Buffer Network Coding based ARQ，INCARQ).对此，文献［17］提出了一种基于哈希搜索和网络编码的连续重传算法(Hash Searching and Network Coding Based Continuous Retransmission，HSNCR)，该算法将固定大小的原始包传输替换为逐包的连续传输，且优先重传最优丢包组合以最大化每一次重传的效率，充分利用了块间编码机会，最大化每次的重传增益，减少了重传次数.但该算法存在着重传性能并非最优和发送缓存浪费的问题，且该算法并未考虑链路丢失率不同的情况.

在各接收节点处链路丢失率不同的情况下，为了更有效的减少重传次数，并保证每次重传编码包增益最大，在上述理论成果的基础上提出了一种改进的应用网络编码的动态连续协作重传(Improved Dynamic Continuous Cooperative Retransmission，IDCCR)算法.该算法的基本思想是在完成首次数据发送缓存区的包传输之后，动态选择一个最佳协作节点，由该节点恢复目的节点的丢包，且在第一次重传完成后，源节点更新数据发送缓存区，并采用不固定大小的连续策略传输原始包.在重传过程中，优先重传编码增益最大的编码包.

2 系统模型

如图1所示，该网络模型为单源多目的的多跳无线网络模型，源节点S发送原始数据包P={P1，P2，…，PM}给N个目的节点R={R1，R2，…，RN}，在该原始数据发送的过程中由中继节点F1转发数据包给多个目的节点.

图1 网络模型图Fig.1 Wireless network model

在初始传输时，源节点S广播发送数据包，中继节点将接收到的包转发给目的节点.目的节点接收到数据包后反馈发送ACK/NACK(接收/丢失)确认消息.假设反馈信道是可靠的，反馈确认消息不会发生丢失.源节点根据接收到的确认消息创建数据包加权接收状态矩阵Φ，该矩阵为一个N×M的矩阵，N为目的节点数，M为原始包数，矩阵元素用ωij表示，ωij=0表示目的节点Ri成功接收到数据包Pj;0＜ωij＜1表示目的节点Ri未成功接收到数据包Pj，且在目的节点Ri处数据包传输成功率为1－pi，pi为目的节点Ri处的包丢失率.如表1所示，加权接收状态矩阵Φ中有3个目的节点丢失10个数据包.

表1 加权接收状态矩阵ΦTable 1 Packet receiving state matrix

在丢包重传阶段，采用哈希汉明搜索选择多个丢包生成编码包，并重传以恢复目的节点丢包.重复上述过程，直到所有的数据包被全部目的节点正确接收.

当全部目的节点均正确接收到数据包Pi时，认为数据包Pi正确接收.当存在至少一个目的节点没有接收到数据包Pi时，则认为数据包Pi未被正确接收.根据加权接收状态矩阵Φ，协作节点对丢包进行编码操作并发送给目的节点.编解码操作采用异或(XOR)编码.

3 IDCCR算法

3.1 最佳协作节点选择机制

在选择最佳协作节点的过程中综合考虑节点与下一跳节点之间的链路质量和与上一跳节点之间的链路质量，能够减小传输时延且使传输成功率更高.假设协作节点为 Ci，D(F1)表示节点F1的邻居节点集;L(n)表示节点F1的上一跳节点的邻居节点集;N(n)表示节点F1的下一跳节点的邻居节点集;PS，Ci表示源节点与节点Ci之间的链路丢包率;PCi，Ri表示节点Ci与目的节点Ri之间的链路丢包率.则节点Ci为最佳协作节点的条件如下所示:

1)Ci∈L(n)且 Ci∈N(n)，且有 Ci∈D(F1)，即该节点既在上一跳节点的一跳范围内，又在下一跳节点的一跳范围内;

2)Ci=arg min(PS，Ci)且 Ci=arg min(PCi，Ri)，即该节点与源节点之间和目的节点之间的链路质量均是最佳的.

证明:假定上述条件1)和条件2)均成立.即节点Ci既是源节点的邻居又是目的节点的邻居，且节点Ci与S以及Ri之间的链路丢失率均为最小，则节点Ci可以侦听到越多的信息，从而有利于充当协作节点，充分性得证.

假设节点Ci为协作节点，则该节点既是源节点S的邻居又是目的节点Ri的邻居，满足条件1).且Ci接收到最多的原始包和确认信息，即该节点与S和Ri的链路质量均为最好，链路丢失率最小，从而满足条件2)，必要性得证.

当存在唯一节点满足上述条件时，选择该节点作为协作节点;当存在两个及以上节点满足上述条件时，选择多个邻居节点中拥有最多目的节点丢包的节点作为协作节点.

3.2 动态连续NC-ARQ策略

定义1.最优重传组合(Optimized Retransmission Combination，ORC)，可以使得所有目的节点至少恢复一个丢包的编码包.

定义2.最大重传组合(Maximum Retransmission Combination，MRC)，可以使得最多目的节点至少恢复一个丢包的编码包.

本文提出了动态连续NC-ARQ策略，其基本思想是在首次完成前M个原始包的初始传输后，包传输采用数目动态的连续传输方式来代替数目固定的块传输方式.如图2所示为动态连续NC-ARQ策略描述图，假设原始数据发送缓存空间为M，首先，源节点发送数据发送缓存中的原始包给目的节点，目的节点接收数据包并反馈发送ACK/NACK;其次，协作节点搜索并重传ORC或者满足特定条件的MRC组合，目的节点接收编码包后解码并反馈发送ACK/NACK;然后，源节点更新数据发送缓存，并计算第1次数据传输过程中发送缓存中目的成功接受到的原始包数Li;最后，源节点继续发送Li个原始数据包，目的反馈确认信息，然后重复上述过程直到所有原始数据包被全部目的节点成功接收.

3.3 丢失数据包选择调度算法

在IDCCR中，原始丢失数据包的选择调度采用哈希汉明搜索.用表示丢失数据包Pj的汉明重量，该值为加权接收状态矩阵Φ中对应Pj所在列的元素取整之和，该值越大，Pj发生丢失越多，需要该包的目的节点越多，则该包对编码的影响越大.记加权接收状态矩阵Φ的列向量为WP1，WP2，…，WPM，若数据包 P1，P2，…Pn同时满足下述两式:

式中＆表示元素进行“与”运算，则数据包P1，P2，…Pn是一组可解的编码组合.公式(1)为编码包的解码条件，即允许目的节点在该编码组合中没有或仅有一个丢包;公式(2)为编码性能判断条件，值越大则越多的目的节点需要该编码组合，编码效率越高.

图2 动态连续NC-ARQ策略Fig.2 Illustration of dynamic continuous NC-ARQ strategy

定义3.若数据包P1，P2，…，Pn的汉明重量分别为 W1，W2，…，Wn，则 W1，W2，…，Wn的汉明邻域可用集合 Uw表示:

根据汉明思想的定义，哈希汉明搜索的操作步骤如下所示:

步骤

1.计算加权接收状态矩阵Φ中所有丢包的汉明重量;

步骤2.根据汉明重量从大到小的顺序建立丢包的哈希汉明列表，列表中第二行为相同汉明重量的丢包个数;

步骤3.在每次搜索中总是搜索汉明重量最大的丢包.首先从哈希汉明列表中选择汉明重量最大的丢包，然后计算该值的汉明邻域，并按大小顺序从中找到下一个可组合的丢包;再根据这两个丢包的汉明重量和计算其汉明邻域，并按从大到小从中找到下一个可组合的丢包.不断重复该过程，直至当前搜索到的丢包组合的汉明重量和已经达到N或哈希表已被搜索完毕，最后把本次搜索的结果进行编码重传;

步骤4.根据目的节点的重传反馈信息，源节点即时更新加权状态矩阵，同时更新丢包哈希汉明列表;

步骤5.重复执行步骤3和步骤4，直至全部目的节点成功接收到所有原始数据包.

IDCCR采用哈希汉明搜索方式选择ORC和MRC组合，如果哈希汉明列表已被全部遍历但所选的丢包组合汉明重量和没达到N，那么本次搜索到编码组合为MRC组合;否则是ORC组合.如表2所示为表1中矩阵Φ对应的哈希汉明列表，编码包 P1P3、P4P5、P2P6和 P7P10均可恢复所有目的的其中一个丢包，则这些丢包组合为ORC组合.

表2 哈希汉明列表Table 2 Hash hamming list

3.4 IDCCR算法的工作流程

IDCCR算法采用不固定大小的动态重传策略代替固定大小的重传机制，不仅能够在块内进行编码操作，而且与现有基于网络编码的重传策略相比传输效率更优.此外，为了更加快速有效的搜索原始丢失数据包组合，采用哈希汉明搜索方式搜索原始丢包.IDCCR算法流程图如图3所示.

图3 IDCCR算法流程图Fig.3 Flow chart of IDCCR algorithm

4 性能分析

在HSNCR算法中，除初次的M个原始数据传输外，每发送一个原始包且该包在目的节点处存在丢失时，将立刻进入重传过程，且仅重传符合条件的最优分组组合或最大分组组合.因此，在HSNCR中，总的重传包数(T2)为:

当采用INC-ARQ机制时，重传中编码包的个数等于某接收节点处的最大丢包数.假定源节点处原始数据发送缓存大小为M，需要传输的原始数据包总数为TN，Nij表示目的节点Ri在第j个缓存数据传输过程中的丢包数，则总的重传包数(T1)为:

采用IDCCR机制时，除首次固定发送M个原始数据包外，每传送Li(1≤Li≤M)个原始包时即开始重传，且只重传ORC或满足条件的MRC.当目的节点Ri有ni个原始丢包时，接收到ni个重传编码包时就可以恢复其全部ni个丢包.因此，重传包数等于某个目的节点处的最大丢包数.则总的重传包数(T3)为:

由公式(4)、公式(5)和公式(6)可以看出，T1总是大于等于T2和T3，因此与传统的NC-ARQ机制相比，IDCCR算法与HSNCR算法的总重传次数相对较少，且从公式(7)可以看出，IDCCR算法的总重传次数相比HSNCR算法更少，则IDCCR算法性能更优.

在实际中，接收节点处的链路丢包率决定了原始丢包的平均数量.因此，当原始数据包数足够多时，丢包率最大的节点决定了网络的重传性能.目的节点数为N，总的原始包数为TN，目的节点Ri处的丢包率为pi.则总的数据包传输次数(记为TTN)可表示为:

则TN个原始包的总重传次数为:

假设目的节点处的丢包率均相同，即p1=p2，…，=p.则每一个原始数据包的平均重传次数(记为ANR):

5 仿真验证及结果分析

5.1 仿真环境及参数设置

本文利用OPNET Modeler 14.5的仿真工具对IDCCR算法进行仿真实验，网络模型设计为设计400m×400m的平面区域内，无线网络模型包括一个源节点、一个中继节点和N各目的节点.MAC层协议采用IEEE 802.11.b标准，数据传输速率最高为11Mb/s.原始数据包初始传输阶段和丢包编码重传阶段，原始数据包发送间隔为1s，发送的原始数据包总数用TN表示.

5.2 仿真结果分析

5.2.1 平均重传次数的仿真及分析

为了验证IDCCR算法的有效性，本节对未编码的ARQ、EONCR、HSNCR和IDCCR四种算法的平均重传次数分别在链路丢失率、目的节点数不同取值的情况下进行仿真实验，固定原始数据包总数TN为5×105个.

当M=50，N=5，链路丢包率p以步长0.05的规律从0.2递增到0.7，由图4可知，当p逐渐增大的时候，四种算法的重传性能均有所提升.其主要原因是当丢包率逐渐增大的时候，目的节点接收数据成功率均有所降低.从图4中可看出IDCCR算法的重传次数相比HSNCR算法略好一点.其主要原因是IDCCR算法的连续重传机制优于HSNCR算法的连续重传机制，IDCCR算法在完成原始数据包的首次传输后，用动态数目的原始包传输来替代固定数目的原始包传输源，且在重传时优先重传ORC和满足条件的MRC，从而提升了重传性能.

图4 重传次数VS链路丢失率Fig.4 Retransmission efficiency against PER

当M=50，链路丢包率p=0.2，目的节点数N从2递增到10.如图5所示，当目的节点数逐渐增多的时候，IDCCR算法、EONCR算法和HSNCR算法的ANR相对比较平稳，且IDCCR算法的ANR优于HSNCR和EONCR算法，而未编码的ARQ机制ANR趋于急速上升的趋势.其主要原因是IDCCR算法中原始数据传输阶段结束时将立刻进入重传阶段，降低了目的节点数目增多对重传次数的影响.另外从图5中可以看出，目的节点数越多，未采用网络编码的ARQ机制的重传次数增速极快，而其他三种算法的上升相对比较慢，说明后三种算法性能优于未编码的ARQ机制.

图5 目的节点数VS重传性能Fig.5 Retransmission efficiency against number of receivers

5.2.2 发送缓存及原始包数对重传性能影响的仿真及分析

本节将对编码的ARQ、EONCR、HSNCR和IDCCR四种算法的发送缓存大小和原始数据包总数对平均重传次数的影响进行仿真实验.

当 N=4，p=0.2，TN=5 ×105，数据发送缓存 M 从 10 增大到400，三种算法的平均重传次数仿真对比如图6所示.由图6可知，在M逐渐增大的过程中，相比其他三种算法，块内编码的ARQ机制的ANR明显较低，但是块内编码的ARQ机制的ANR逐渐的贴近其他三种算法.当M增大到100的时候，M值对IDCCR算法的影响已经很小，其ANR值已无线逼近理论值.对于上述四种算法，发送缓存越大，则重传效率越高.IDCCR算法中，由于每次仅重传 ORC或 MRC，M越大，则MRC重传机会越小，ORC重传机会越大，从而单次重传效率均会提升，重传次数减少;且由于其采用了动态连续重传策略，新的丢包不断的进入下一次重传中，当M足够大的时候，ORC的搜索要求已能够完全满足，即每次重传基本都能找到ORC组合，从而使得重传性能无线逼近理论值.明显低于其他三种算法.这是因为相对于其他几种机制，IDCCR具有可利用的编码机会更多，且单次重传效率更优.EONCR算法和应用编码的ARQ机制仅在块内执行重传过程，因此重传效率的影响因素仅仅是每批原始数据包的数量，而不是原始数据包总数.在IDCCR和HSNCR算法中，在发送缓存空间的数据首次传输完成之后，分别进入单个包传输方式和动态传输方式，从而其平均传输次数并不会受到原始包数的影响.

当 N=4，p=0.2，M=100，原始数据包总数 TN 从 105个增长为106个，如图7所示，IDCCR算法的ANR指标总体上

图6 重传性能VS发送数据缓存大小Fig.6 Retransmission efficiency against the size of transfer buffer

图7 重传性能VS原始包总数Fig.7 Retransmission efficiency against number of original packets

6 结论

本文通过分析及研究现有协作重传算法，提出了一种改进的协作重传算法，以提高传输效率，优化网络性能.IDCCR算法避免了INC-ARQ方案的块隔离问题，且解决了HSNCR算法的缓存空间浪费问题并考虑了链路丢失率不同的情况，从而为丢失数据包提供了更多的编码可能性.IDCCR算法是基于哈希汉明搜索的快速丢包选择调度算法.此外，该新算法通过仅重传ORC或MRC来最大程度地提高每一次的重传增益.通过对不同条件下重传性能的仿真实验结果表明，IDCCR方案在减少重传次数上确实优于以往方案.在今后的工作中，我们将对多节点协作的这一方案做一些研究.