基于网络编码的III型HARQ无线广播跨层设计

吕振兴 许 魁 徐友云

(解放军理工大学通信工程学院 南京 210007)

1 引言

无线通信系统中，多种数据业务传输方案都要求具有低误码率和高吞吐量的性能。常用的混合自动重传请求(HARQ)技术有效地结合前向纠错(Forward Error Correction FEC)和自动重传请求(Automatic Repeat reQuest ARQ)这两种基本的差错控制机制，为传输提供了更高的可靠性和系统吞吐量[1]。根据重传内容的不同，HARQ技术可分为3种类型[2,3]。I型HARQ是一种信息序列及其校验位全部重传并单独译码的机制。Ⅱ型和Ⅲ型HARQ系统属于增量冗余机制。不同之处在于II型HARQ机制，重传的只是数据信息或只是FEC冗余信息，只能与先前的错误版本并译码，而III型HARQ机制中，重传数据均包含数据信息和冗余信息，接收端可单独译码，也可与缓存的出错版本进行合并译码。III型HARQ机制可以克服快速变化的信道以及信道条件瞬时恶化对系统性能的影响，尤其适用于时变衰落信道。

无线广播场景中大量用户丢失不同的数据包，传统的 HARQ技术每次只能重传一个出错的数据包，造成了重传效率的低下。因此，如何提高广播中的重传效率成为研究热点之一，而具有显著优势的网络编码[4]技术为研究者提供了一种新的途径。基于无线信道的不可靠性和广播特性，网络编码在无线通信领域得到了灵活有效的应用，Katti 等人[5]设计了实用的网络层编码协议 COPE，其在重负载时吞吐量性能较传统路由有 40%的提高；Gollakota 等人[6]设计了灵活的物理层编码协议ZigZag, 14个节点的仿真表明其相比传统的802.11协议平均吞吐率提高25%，平均丢包率从15.8%减小至0.2%。大量研究表明，无线通信中的网络编码技术不仅可以改善误码性能，增强网络的容错性和鲁棒性，还能够减少数据包重传次数[7,8]，显著提升网络吞吐量。

无线广播模型中常用的网络编码重传策略有两种。一种策略是基站首次广播数据包后，根据ARQ反馈，将所有需重传数据包重复进行随机网络编码(RNC)后发送，用户只要接收到足够多的编码包，就能根据求解逆矩阵的思想得到所需的数据包[7,9]。但这种策略有两个明显的缺点：一是译码过程复杂，二是重传包延时过大。另一种策略是基站广播发送数据包的同时，根据实时接收的ARQ反馈进行异或型(XORing)网络编码[5,10-12]。这种策略的网络译码过程简单，且在广播的同时就能穿插编码重传过程，延时较低。由于文献[10]中提出的数据包组合策略可能会导致该用户不可译码，本文将对其进行改进，提出了新的异或型网络编码联合(XORing Network Coding Combined, XNCC)策略。

文献[11]研究了认知网络中联合网络编码和传统ARQ技术的NC-ARQ广播方案，基本思想是在ARQ重传阶段对丢失包进行网络编码联合，以减少传输次数。文献[12,13]分别研究广播中继和双向中继模型下，联合网络编码和HARQ技术所带来的吞吐量增益。文献[14]研究了无线下行链路中基于传统 HARQ的网络编码技术 NC-HARQ，理论分析了网络编码在重传效率和传输时延方面的性能增益。本文进一步将网络编码技术和III型HARQ机制相结合，提出一种基于网络编码的NC-HARQ III型广播系统。其主要思想是在重传阶段，利用所提XNCC策略联合需重传数据包，一方面使每次编码包的重传能服务于多个用户，减少重传次数；另一方面通过联合网络-信道译码(Joint Network and Channel Decoding, JNCD)设计，降低译码错误性能，减少再次重传次数。仿真表明该方案，较网络层或链路层的分层设计方案，能有效减少重传次数，获得显著的时延增益。

2 NC-HARQ Ⅲ型广播系统

NC-HARQ III型广播系统传输结构如图1所示。基站通过侦听来自各用户的控制信号，获取信道状态信息(CSI)来实施自适应编码调制(AMC)控制，以获得最大的频谱利用率。本文不对AMC技术做重点讨论，简单起见，调制方式采用BPSK调制，信道编码采用递归系统卷积码(RSC)编码，这主要是考虑到重传数据可以与先前缓存数据联合构成分布式Turbo码，降低误包率。整个传输过程可分为两个阶段：数据包的首次发送称为广播阶段，错误数据包的再次发送称为重传阶段。为了满足系统的QoS要求，两阶段可穿插进行，保证数据业务的实时性和流畅度。

广播阶段，基站将信源数据包添加循环冗余校验(CRC)后进行RSC编码、调制发送；用户对接收到的解调数据进行RSC译码，通过CRC校验判断是否正确译码，同时将HARQ反馈通过控制信道发送到基站。译码正确的数据包将被送入数据包缓存，以便重传阶段进行网络译码；译码错误时，软解调数据将被送入软信息缓存，以便与重传阶段接收数据联合进行信道译码。

图1 NC-HARQ III型广播系统传输结构

重传阶段，基站根据HARQ反馈，采用XNCC策略，在源数据包缓存中选择合适的数据包进行XORing网络编码，生成的编码包经CRC校验、交织、RSC编码后发送。接收端从软解调数据中网络译码出丢失数据包的重传信息，将其与广播阶段的解调数据联合进行信道译码，以此获得较低的误包率。译码结果的处理模式同广播阶段一样：译码正确时，数据包将被送入数据包缓存；译码错误时，软解调数据将被送入软信息缓存。

需要注意的是，数据包的 CRC校验编码与RSC信道编码都具有良好的线性性质，网络编码中的XOR操作不影响其发挥作用。以等数据长度的数据包i1和i2为例，CRC(*)和RSC(*)分别表示具有相同生成多项式的 CRC校验编码和具有相同生成矩阵的 RSC信道编码。若C1=CRC(i1),C2=CRC(i2)，则等式C1⊕C2=CRC(i1⊕i2)仍然成立；若R1=RSC(i1),R2=RSC(i2)，则等式R1⊕R2=RSC(i1⊕i2)仍然成立。限于篇幅，不作证明。

2.1 XNCC策略

基站根据接收到的HARQ反馈，获得数据包的丢失情况，其包括：(1)数据包是否丢失；(2)丢失数据包的序列号和丢失节点序列号[10]。假定反馈信道不存在损耗。基站将丢失情况记录在矩阵T中，如图2所示，该矩阵中行表示用户接收情况，列表示数据包被接收情况。若某个数据包在某个接收节点被成功接收，相应位置赋值为“0”；若丢失，相应位置赋值为“1”。

图2 数据包传输错误标志矩阵T

为了使每次重传过程中，尽量多的用户节点通过简单的XOR操作，就能获得丢失数据包的重传信息，有以下两个选择编码准则：(1)针对任一用户只能有一个丢失包参与网络编码；(2)每次生成的编码包能服务于尽量多的用户。参照选择准则，我们设计了在数据包传输错误标志矩阵T中寻找编码组合的XNCC策略，具体步骤为：

步骤 1 将被全部用户正确接收的数据包序列去除，比如图 2中的ID:8数据包，清空编码列表CodingList，清空服务用户列表UserList；

步骤 2 从第1列开始，将该列中错误标志为“1”的所有用户ID设为向量UserList_temp；

(1)若UserList_temp与UserList有交集，则该列不能添加进编码列表，丢弃。

(2)若UserList_temp与UserList无交集，则将该列ID添加进编码列表CodingList，该列中所有的错误标志置为“0”，更新服务用户列表：UserList=UserList+UserList_temp。

若服务用户列表UserList遍及所有用户或达到限制重传次数，则可退出循环。

步骤 3 将编码列表 CodingList指示的所有数据包进行XOR操作。

实用过程中，XNCC策略的详细编码算法如表1所示，其中N表示用户数目，l表示待重传包数目。

表1 XNCC策略编码算法

根据XNCC策略，可得到表1的网络编码方式为：1⊕2⊕6, 3⊕5, 4⊕9, 7⊕10，则重传次数从传统的9次减少到4次，大幅降低了重传次数。每次组合对应的编码列表 CodingList可通过控制信道发送给各用户，以便其进行网络译码。同时，通过观察可知：当广播数据包足够多时，根据XNCC策略得到的网络编码包数等于所有用户丢包个数的最大值。用户数目为2时，结论显然成立，当用户数目增加时也是如此。因针对任一用户，每次编码组合只能重传一个数据包，则所需的重传次数取决于丢包率最大的用户[14]，故网络编码组合次数等于最大丢包数，这为第4节的性能分析提供了依据。

2.2 联合网络-信道译码

用户端重传阶段的联合网络-信道译码结构如图3所示，用户从控制信号获取参与网络编码的数据包 ID，从数据包缓存中取出对应的数据包进行XOR操作、添加CRC校验、交织后进行RSC信道编码。这里的CRC校验、交织方式、RSC方式均与基站发送端的相同，目的是重构基站数据包(除丢失信息外)的编码过程，使用户能从本地解调数据中根据得到的编码信息，软判决出丢失包的重传信息。通过网络译码得到丢失包的重传信息后，首先进行单独的 RSC译码，若不成功，则联合先前软信息缓存中的校验位进行Turbo译码。既然广播阶段的数据译码错误，表明其已经历严重的衰落，故不能利用其信息位进行分集合并，只能利用校验位进行码字合并译码。然而Turbo译码必需的是每个解调数据的对数似然比(LLR)，怎样从网络编码包中提取重传数据每个比特的 LLR值是一个不可避免的问题。

图3 重传阶段的联合网络-信道译码结构

3 中继广播模型及方案扩展

实施机会中继的具体方法是每个基站/中继站采用最小信道增益h的倒数当作倒计时器的初始值，选择计时器最先归零的基站/中继站进行重传。当选定某一中继站重传时，其内部的NC-HARQ III型编码广播方案与基站处的相同。采用中继站进行重传的目的是，进一步降低重传阶段的误包率，以减少重传次数。需要注意的是：当用户数目增多时，机会中继带来的误包率性能增益逐渐减小。

4 性能分析

图4 中继站的编码重传结构

时分复用系统中，因系统的传输延时取决于数据的传输次数，所以本文衡量的性能指标是平均每一源数据包传输至所有用户终端所需要的传输次数。传统的HARQ I型重传机制下，基站对数据添加 FEC编码后广播发送，用户根据本次接收数据进行译码。链路层采用网络编码的HARQ I型方案(NC-HARQ I)中，基站根据XNCC策略选择合适的重传包，网络编码后添加 FEC编码，用户也只是根据本次接收数据信道译码，再通过网络译码得到重传数据。选取上述两种方案与本文所提NC-HARQ III型广播方案进行对比，是要分别验证网络编码技术和联合网络-信道译码设计带来的时延增益。

基站要发送K个数据包至N个用户终端。设采用RSC信道编译码进行首次广播的误包率为Pb，则 HARQ I型重传模式的误包率也始终为Pb。设HARQ III型冗余重传模式下第i次重传的误包率为Pri，由于采取联合译码，显然误包率会逐次降低，即Pb＞Pr1＞Pr2＞Pr3…。为分析方便，这里取Pr1为HARQ III型冗余重传模式下的误包率，并假设每个用户终端的误包率相同。

HARQ I型方案中，一个数据包的平均传输次数L1为[7]

网络编码方案中，定义平均传输次数为L(Pb,Pr) ，其中Pr为重传阶段的误包率。广播阶段，每一用户的错误包数为KPb，由第2.1节的分析可知：需要重传的网络编码包数即为KPb。因XNCC策略根据HARQ反馈实时进行动态编码，且每次编码都能服务一次指定用户，故此时网络编码包的重传次数相当于基站发送KPb个数据包到单一指定用户的传输次数，重传次数Lr为

所需平均传输次数L(Pb,Pr)为

故NC-HARQ I型方案的平均传输次数为L(Pb,Pb) ,NC-HARQ III型方案的平均传输次数为L(Pb,Pr1)。

5 仿真验证

基站广播104个数据包至10个用户终端，每数据包长度为200 bit(含CRC校验)，信道编码采用码率为1/2的(37, 21)RSC编码，BPSK调制发送，Turbo译码采用MAP算法，且均为8次迭代。仿真环境为叠加高斯白噪声的瑞利慢衰落信道，广播或重传阶段经过RSC编码的400 bit经历相同的信道衰落。假设基站/中继站针对每一用户具有相同的发送信噪比SNR。

图5反映了在广播阶段RSC译码错误的情况下，3种HARQ机制首次重传的误包率。其中HARQ II型经过两次重传发送了 RSC编码的全部信息位和校验位，这样保证其重传数据也为400 bit，其中信息位与缓存数据的信息位进行等增益分集合并，校验位采用码字合并进行联合Turbo译码。为方便下文引用，对应的误包率曲线在图示中用P1,P3,P1r,P3r来标志。由图 5可以看出：在低信噪比(SNR ＜4 dB)时，HARQ II型重传机制由于采用合并译码技术，误包率要好于HARQ I型机制；当信噪比增加时，若广播阶段仍译码错误，表示其首次广播数据衰落较严重，即使增加冗余信息也难以争取译码；HARQ III型重传数据包的误包率始终好于其它两种HARQ机制。针对存在6个中继节点的情况，仿真表明机会中继策略能显著降低重传数据包的误包率。

图6反映了传统的HARQ I型方案，融合网络编码的NC-HARQ I型方案以及NC-HARQ III型方案，在图6所示误包率的基础上，平均每一源数据包传输至所有用户终端所需要的传输次数，图示中的P1,P3,P1r,P3r分别对应图5中的误包率。NC-HARQ I型方案与HARQ I型方案相比，传输次数的减少得益于网络编码机制(XNCC策略)在减少重传次数方面的潜在优势。NC-HARQ III型方案与NC-HARQ I型方案相比，传输次数的减少应归功于JNCD设计带来的更低的误包性能。存在6个中继站时，两方案下平均传输次数套用式(5)可得：L(P1 ,P1r),L(P1 ,P3r)，仿真表明机会中继策略能有效降低重传次数。

图7反映了信噪比设定为2 dB的情况下，3种传输方案中平均传输次数随用户终端数目增加的变化情况。传统的HARQ I型重传方案中，当用户终端数目增加，所需平均传输次数快速增加；采用网络编码后，平均传输次数与终端数目无关。可见采用网络编码的重传方案更适用于用户密集的场景。中继广播模型下，随着用户终端数目的增加，所需平均传输次数趋近于无中继模型，这主要是因为随着用户终端数目的增加，机会中继带来的误包率性能增益越来越小。

6 结论

图5 针对某一用户广播阶段的丢失包不同HARQ机制首次重传的误包率

图6 不同重传方案下的平均传输次数

图7 不同重传方案下的平均传 输次数随用户数目的变化情况

本文提出了联合网络编码的III型HARQ广播系统跨层设计方法，其主要思想是在重传阶段，利用XNCC策略XOR重传数据包，一方面使每次编码包的重传能服务于多个用户，减少重传次数；另一方面通过联合网络-信道译码设计，降低误包率。本文进一步利用机会中继的思想，将提出的 NCHARQ III机制扩展到中继广播系统。在不同HARQ类型丢包率的仿真基础上，论文推导出联合网络编码设计时广播系统的所需平均传输次数，并通过仿真对比了采用网络编码和不同 HARQ类型进行联合设计时的延时性能。数值分析和仿真表明：所提NC-HARQ III型广播方案，较传统的HARQ I型或NC-HARQ I型广播方案，能有效减少重传次数，获得显著的时延增益。

[1]Cheng J. Coding performance of hybrid ARQ schemes [J].IEEE Transactions on Communications, 2006, 54(6):1017-1029.

[2]Garg D, Kimura R, and Adachi F. RCPT hybrid ARQ with limited number of retransmissions in DS-CDMA[J].Electronic Letters, 2003, 39(2): 241-242.

[3]刘锋, 黄生叶, 冯穗力, 等. 新型的基于信道状况的自适应HARQ方案[J]. 计算机工程与应用, 2010, 46(8): 99-102.

Liu Feng, Huang Sheng-ye, Feng Hui-li,et al.. Novel adaptive HARQ system based on channel condition [J].Computer Engineering and Applications, 2010, 46(8): 99-102.

[4]Ahlswede R, Cai N, Robert Li S Y,et al.. Network information flow [J].IEEE Transactions on Information Theory, 2000, 46(4): 1204-1216.

[5]Katti S, Rahul H, Hu W,et al.. XORs in the air: practical wireless network coding [J].IEEE/ACM Transactions on Networking, 2008, 16(3): 497-510.

[6]Gollakota S and Katabi D. ZigZag decoding: combating hidden terminals in wireless networks[C]. SIGCOMM’08,Washington, USA, Aug. 2008: 159-170.

[7]Ahmed E, Eryilmaz A, Medard M,et al.. On the scaling law of network coding gains in wireless networks[C]. IEEE MILCOM 2007, Orlando, USA, Oct. 2007: 1-7.

[8]Ding Z, Zheng M, and Leung K K. Impact of network coding on system delay for multisource-multidestination scenarios[J].IEEE Transactions on Vehicular Technology, 2010, 59(2):831-841.

[9]Dong N, Tran T, Nguyen T,et al.. Hybrid ARQ-random network coding for wireless media streaming [C].International Conference on Communications and Electronics (ICCE) 2008, Hoi an Vietnam, Jun. 2008:115-120.

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

Xiao Xiao, Wang Wei-ping, Yang Lu-ming,et al.. Wireless broadcasting retransmission approach based on network coding [J].Journal on Communications, 2009, 30(9): 69-75.

[11]Liu Y, Feng Z, and Zhang P. A novel ARQ scheme based on network coding theory in cognitive radio networks [C]. IEEE International Conference on Wireless Information Technology and Systems (ICWITS) 2010, Honolulu, USA,Aug. 2010: 1-4.

[12]Hong S K and Chung J M. Network-coding-based hybrid ARQ scheme for mobile relay networks [J].Electronics Letters, 2010, 46(7): 539-540.

[13]Vien Q T, Tran L N, and Nguyen H X. Network coding-based ARQ retransmission strategies for two-way wireless relay networks [C]. Softcom 2010, Split Jugoslavia,Sept. 2010: 180-184.

[14]Peng Q, Zhang T, and Cuthbert L. Research on network coding based hybrid-ARQ scheme for wireless networks [C].IEEE International Conference on Communication Systems(ICCS) 2010, Singapore, Nov. 2010: 218-222.

[15]Bletsas A, Khisti A, Reed D P,et al.. A simple cooperative diversity method based on network path selection [J].IEEE Journal on Selected Areas in Communications, 2006, 24(3):659-672.