喷泉码多路并行转发中继系统传输时间分析

吴丹，田亚飞，杨晨阳

（北京航空航天大学 电子信息工程学院， 北京 100191）

1 引言

中继技术可以有效地扩展无线通信系统的覆盖范围或者提升用户的吞吐量[1]。在能量受限的系统中，如超宽带通信系统，使用多中继并行转发可以大大扩展其传输距离。如果中继节点之间可以联合同步，并且每个节点传输的数据率相同，则多中继可以形成虚拟天线阵，进行波束形成以得到能量增益。但是，在实际的系统中中继之间往往难以进行联合同步，而且中继节点的位置往往不同，导致传输数据率不同，此时进行多路数据流并行转发是更有效的方式[2,3]。

本文考虑多级多路并行转发宽带中继系统。多路不同的码流可以通过时分、频分或码分来区分，中继系统可以服务一个用户也可以服务多个用户。

为了保证传输的可靠性，通信网络在数据链路层一般会采用差错控制，如自动重传请求（ARQ）协议。但是，基于多跳通信的ARQ方案[4]难以直接应用于多路并行传输的中继网络中。多级传输的时序非常复杂，当某一级的某一路信号出现传输错误时，信源很难判断何时重新发射信号。如果层层向上反馈，则会给网络带来大量额外的开销。

为了降低多级多路中继系统中反馈和重传的负担，本文考虑采用喷泉码进行开环差错控制。

喷泉码是在删除信道上设计的编码[5]，在加性白高斯噪声信道和衰落信道下也能达到很好的性能[6,7]。采用喷泉码编码的传输过程不需要经常反馈重传信息，只需接收端在接收到足够的数据并正确解调信息后给信源发送一个终止信号，从而可以避免建立大量的反馈链路。喷泉码已被考虑应用于各类无线通信场景中，如由无线局域网构成的ad hoc网络[8]、广播、多址网络[9]，单中继协作网络[10]和窄带协作中继网络[3,11]。文献[3]首次研究了喷泉码在两级多中继协作网络中的应用，并给出了中继同步和异步时的传输方案及性能。在文献[3,11]研究的窄带协作网络中，信源向各中继节点广播同样的数据，而中继节点只有在收到足够多的数据并完整解出原始信息后才会进行转发，在多级中继系统中，这会造成过长的传输延迟。

本文考虑宽带多中继协作网络。利用喷泉码的性质和多路并行传输的特点，中继端都不进行喷泉码译码，而是对每一个收到的数据分组进行循环冗余校验（CRC），如果正确接收就进行转发，如果错误则直接丢弃，完整译码只在目的接收端进行。通过分析和仿真，比较这种传输方案和基于 ARQ方案的传输时间。结果表明，基于喷泉码的方案优于 ARQ传输方案，并且随着系统误包率和网络中继数的增加，喷泉码方案的优势越来越明显。

本文安排如下：第2节给出多级多路协作中继系统模型，并简要介绍喷泉码；第3节对喷泉码和ARQ传输方案下的系统传输时间进行理论分析与比较；第4节通过数值分析和仿真对这2种方案的性能进行比较；最后是结束语。

2 系统模型

喷泉码的基本编译码思想为：发射端对原始K个分组做随机线性编码，接收端只需接收到N = K ( 1 + ε )个分组后（N略大于K），就能以很大的概率正确恢复原始分组，这里ε表示接收端正确译码所需要接收的冗余度。Raptor码的编译码复杂度与数据分组数K呈线性关系，并且当K很大时，冗余度很小[15]。3GPP组织的多媒体广播和多播业务标准中采用的系统Raptor码[16]，在分组数较小的情况下也有较好的冗余性能。由于接收端对数据分组的接收顺序没有要求，采用喷泉码传输的网络可以直接丢弃接收错误的分组，无需反馈重传信息，

考虑如图1所示的多级中继协作网络，包含一个信源节点，一个或多个目的接收节点以及多级中继转发节点。这个网络由广播和多址2个基本阶段构成。其中，由一个节点向多个节点发送数据的过程为广播阶段，由多个节点向一个节点发送数据的过程为多址阶段。

以单用户一级多中继系统为例，在多路并行传输模式下，信源可以向M个中继节点发送不同的数据，多中继也可以同时向信宿传输。考虑实际系统的可实现性，这里中继采用时分双工模式[12]。

通信网络可以看作一种删除信道[5]。喷泉码是删除信道中的一种稀疏图编码[5]，由 Luby等人在1998年第一次提出[13]，但是并没有给出明确的实现方法和结构。LT码是喷泉码的第一次实现[14]，Raptor码是LT码和一个线性预编码的级联[15]，可以降低编译码复杂度，同时提高性能。从而开环控制网络，减少网络信令开销，降低网络复杂度。

图1 中继协作网络

3 传输方案与传输时间分析

下面将喷泉码应用于多路并行中继协作网络，给出一种网络传输方案，并分析所需传输时间。作为比较，也将给出在上述网络中应用 ARQ协议的传输方案。

3.1 喷泉码方案与传输时间

考虑传输一份大小为K个数据分组的源文件，信源端使用喷泉码对原始分组编码，对每组喷泉码数据再进行 CRC编码。编码后一个分组内的比特数为l，持续时间为pT。各分组通过不同的中继进行传输，出现传输错误的分组被中继和目的端直接丢弃，目的端只需收到一定冗余量的分组即可正确恢复数据，数据分组到达的顺序不影响最终译码性能。假设所有发射接收设备的处理都是理想的，没有延迟。

如图2所示，信源在广播阶段向中继广播不同数据，之后开始监听。中继对接收到的数据进行CRC校验后，向目的节点转发校验正确的数据分组，即为多址阶段，完成后也转入监听状态lT。当目的节点接收到足够多正确的数据分组，可以成功译码时，在1T时间内发出终止信号。当信源和中继监听到终止信号时，文件传输结束；若未监听到终止信号，则转入下一个广播状态，继续发射后续数据分组。

图 2 喷泉码传输方案帧结构

一组数据由信源发出，经中继i转发，正确到达目的节点的概率为其中，为广播阶段各链路的误包率，为多址阶段各链路的误包率。因此，信源向每个中继发射的数据分组数sN满足下式：

当中继位置相近时，广播和多址阶段各中继链路的误包率可认为近似相等，分别为e,BCp 和e,MAp ，从而采用喷泉码传输方案时系统传输时间约为

3.2 ARQ方案与传输时间

图3给出了采用停发等候ARQ协议[17]时的帧结构。同样采用分组传输和 CRC校验，系统的延迟可以忽略，数据发送完成之后，发送方等待接收方的 CRC校验信息，如显示成功，则发送后续数据，否则重传。

图3 ARQ传输协议帧结构

在广播阶段，信源向中继广播不同数据，发射完成后进入长度为TW的时隙等待中继反馈校验信息；信源重发没有接收到 ACK信息的数据分组，直至接收到所有 ACK信息后，发出通知信号（发射完成信号），信源节点切换为监听状态。

假设对于没有接收到 ACK确认的数据分组只需重传一次即可保证正确接收，则广播阶段正确传输所需的平均时间为

信源节点切换为监听状态时，系统进入多址阶段，所有中继开始转发数据，等待目的节点的反馈。中继接收到 ACK信号后，向信源发送转发完成信号，并转入接收状态。当信源监听到所有中继的转发完成信号后，系统切回广播状态，完成一次传输。不难得到，多址阶段正确传输所需的平均时间为

只有所有中继（或目的节点）正确接收到各自的数据（或所有转发数据）时，传输才算完成。因此ARQ方案下一次完整传输所需时间为

事实上，在 ARQ传输协议中，随着中继数的增加，信源需要等待的通知信号（包括广播阶段ACK信号和多址阶段转发完成信号）越多，等待时间 TW越长。对于ARQ协议，一个时隙的平均持续时间为

3.3 2种传输方案的性能比较

由式(2)和式(5)可以得到采用喷泉码方案和重发一次即正确的ARQ方案时系统传输时间的比值：

式(6)中(1)ε+是喷泉码的冗余性能对传输性能的影响。

tFC/tARQ反映了传输协议的复杂度对传输时间的影响。根据3.1节和3.2节的传输方案，有 tARQ＞tFC。

式(6)中第2行的第2个因子反映的是传输方案对传输时间的影响，2种协议的主要差别在于当网络中某条链路传输出错时，喷泉码协议可以继续传输，而ARQ协议必须等待同级的所有链路传输均正确后才能转入下一级，这是影响系统传输时间的主要因素。当 pe,BC和 pe,MA较小时，这一项因子可以用Taylor展开进一步化简得到

可以看出，当中继数 M ≥ 2 时，式(7)小于或等于1，当喷泉码的冗余度较小时，有即采用喷泉码方案的系统传输时间较小；当中继数M= 1时，式(7)略大于 1，但是由于这表明在点对点单跳链路中，2种方案的传输时间基本相同。可见，喷泉码可以降低多中继系统的反馈量，减少传输时间，提高吞吐量。

3.4 多级中继传输

考虑由(n-1)级转发中继( 2n≥ )构成的n级传输系统。采用喷泉码方案，每个转发节点以2个帧时隙（一个时隙用于接收上一级节点的数据，一个时隙用于向下一个节点转发数据）为周期，进行级联转发。为了终止传输，接收端可以发射一个足够强的终止信号，使各级节点均可监听到；也可通过各级中继进行逐级回传，但这会牺牲一些传输时间。

假设各级传输的误包率相等，均为pe；每级转发的中继数也相等，均为M。则采用喷泉码传输时系统的传输时间为

其中， M(1-pe)n为经过n级传输并正确到达接收端的平均数据分组数；系统需要等待(n-2)个时隙，才能接收到第一个时隙发出的数据，随后，每隔 2个时隙接收一次数据。当n=2时，式(8)退化为式(2)。

ARQ方案在重传一次即正确的假设下，也可以进行级联转发，但是反馈量随级数的增加也增加，协议较为复杂。ARQ传输方案的传输时间为

因此，对于n级传输系统，2种传输协议下系统的传输时间比值为

随着级数n的增加，式(10)中 TFC/TARQ也增大，这是由于喷泉码方案中每级成功传输的数据分组递减。但是只要M＞n，喷泉码方案就优于ARQ方案。

4 数值与仿真分析

本节给出采用喷泉码传输协议、一般 ARQ传输协议和重传一次即正确ARQ传输协议这3种协议时一级中继系统的性能。对每个中继节点发射105分组进行蒙特卡洛仿真实验。假设ARQ反馈信号可以保证无误传输，且不考虑同步等处理时间。

仿真中采用3GPP多媒体广播和组播业务标准中的系统Raptor码[16]。表1给出 100次Raptor编译码实验中接收端成功译码的次数。可以看出，当分组数K在1 000~3 000之间时，接收端在多收10个分组后即能以很大的概率正确译码，即冗余度ε＜ 1 %。

表1 Raptor码译码性能

式(6)中 tFC/ tARQ因子的影响在实际系统中不能忽略，与信令设计有关，但由于本文不涉及具体的物理层包头设计，因此仅仿真第2项因子的影响，故仿真结果为时分双工系统中实际值的上界。

图4给出了喷泉码方案和ARQ方案（重发一次即正确ARQ与重发直至正确的一般ARQ方案）传输时间比值的数值和仿真结果。其中，中继数M=4，数值结果由式(6)给出。可以看出，重发一次即正确ARQ方案的仿真结果与数值结果吻合；当2个阶段误包率均较小时，如小于 0.04，一般 ARQ的仿真结果也与数值结果基本吻合。图中比值均小于 1，说明采用喷泉码传输方案时系统的传输时间小于ARQ传输方案，前者可以获得更高的吞吐量。

从图中还可以看出，多址阶段误包率 pe,MA越高，相对于一般 ARQ方案，采用喷泉码方案时系统的传输时间越短，喷泉码方案越有优势。根据传输协议设计，可知广播阶段误包率 pe,BC对系统传输时间的影响也是如此。当 pe,BC分别为0.01和0.1时，喷泉码在后者条件下优势更为明显。

随着pe,MA的增加，喷泉码方案与重传一次即正确 ARQ方案的时间比值先下降再上升。这是由于在误包率较大时，ARQ方案使数据分组在每个阶段的传输时间控制在2个时隙内，人为地缩短了传输时间。而在实际系统中要满足重传一次即成功的假设，需要增大发射机信号功率，或采用纠错性能更好的编码进行重发，或者选择信道条件更好的中继进行转发，是一种混合ARQ控制和中继选择问题，不在本文的讨论范围内。

图4 TFC/TARQ的数值和仿真结果

图5给出了在给定广播阶段误包率 pe,BC=0.01的情况下， TFC/TARQ与中继数M的关系。

图5 不同ARQ协议下，TFC/TARQ与中继数的关系

可以看出，在2种ARQ传输方案下，随着M的增多，TFC/TARQ均减小。在多路并行传输模式下，尽管可以采用时分、频分和码分等方式传输多个数据流，但是由于时间、频率同步、衰落信道等各种实际因素的影响，多路数据的正交性无法完全保证。这意味着随着中继数的增加，每个中继节点受到其他节点的总干扰一般会增大，系统误包率也会增大。此时，喷泉码的优势更加明显。另外，网络中继数越多，ARQ方案中一个帧时隙持续时间越长，反馈链路越复杂；而喷泉码传输方案在大规模网络中具有十分优越的性能。

5 结束语

本文将喷泉码应用于多路并行传输中继网络中，给出了基于喷泉码传输的中继协作网络的传输方案和帧格式，分析了系统的传输时间。

本文针对一级和多级中继协作网络，理论分析了采用喷泉码与采用重发一次即正确的 ARQ时系统的传输时间之比，并通过仿真验证了理论分析的正确性。分析的结果表明，喷泉码方案的传输时间小于ARQ方案；随着中继数和系统误包率的增加，喷泉码方案的优势更加明显；在多级中继系统中，只要转发中继数大于转发级数，采用喷泉码方案的系统就会具有很大的性能优势。可见，采用喷泉码的传输方案无需复杂的协议设计，无需引入反馈链路，即可以在保证系统传输可靠性的前提下减小传输时间，提高系统的吞吐量。

[1] FITZEKF H P, KATZM D. Cooperation in Wireless Networks: Principles and Applications[M]. Netherlands: Springer, 2006.

[2] TIAN Y F, YANG C Y. Space-time focusing transmission in ultra-wideband cooperative relay networks[A]. ICUWB[C]. 2009. 353-358.

[3] MOLISCH A F, MEHTA N B, YEDIDIA J S, et al. Performance of fountain codes in collaborative relay networks[J]. IEEE Transactions on Wireless Communications, 2007, 6(11): 4108-4119.

[4] JEON S Y, CHO D H. Modeling and analysis of ARQ mechanisms for wireless multi-hop relay system[A]. VTC Spring[C]. 2008. 2436-2440.

[5] MACKAY D J C. Fountain codes[J]. IEEE Proceedings on Communications, 2005, 152(6): 1062-1068.

[6] CASTURA J, MAO Y. Rateless coding for wireless relay channels[J].IEEE Transactions on Wireless Communications, 2007, 6(5): 1638-1642.

[7] CASTURA J, MAO Y. Rateless coding over fading channels[J]. IEEE Communication Letters, 2006, 10(1): 46-48.

[8] KSENTINI A, CHAHED T. Extending the ad hoc horizon in dense 802.11 networks using fountain codes[A]. ICSNC[C]. 2009.63-67.

[9] JANKAC H, STOCKHAMMER T. Asynchronous media streaming over wireless broadcast channels[A]. IEEE International Conference on Multimedia Expo[C]. 2005. 1318-1321

[10] LIU X, LIM T J. Fountain codes over fading relay channels[J]. IEEE Transactions on Wireless Communications, 2009, 6(6): 3278-3287.

[11] LEI W J, LI X M, LI G J. Wireless cooperative relay system using digital fountain codes[A]. ICCCAS[C]. 2009. 123-127.

[12] PETERS S W, PANAH A Y, TRUONG K T, et al. Relay architectures for 3GPP LTE-advanced[J]. EURASIP Journal on Wireless Communications and Networking, 2009, Article ID 618787: 1-14.

[13] BYERS J, LUBY M. A digital fountain approach to reliable distribution of bulk data[A]. ACM SIGCOMM[C]. 1998. 56-67.

[14] LUBY M. LT codes[A]. FOCS[C]. 2002. 271-282.

[15] SHOKROLLAHI A. Raptor codes[J]. IEEE Transactions on Information Theory, 2006, 52(6): 2551-2567.

[16] 3rdGeneration Partnership Project (3GPP). Technical Specification Group Services and System Aspects; Multi-media Broadcast/Multicast Services (MBMS); Protocols and Codecs (Release6)[R]. Tech Rep 3GPP TS 26.346 V6.3.0, 3GPP, 2005.