FEC在高波动性网络中的应用研究

段 涛，孙 军

(1.上海交通大学电子工程系图像通信与信息处理研究所，上海200240;2.上海市数字媒体处理与传输重点实验室，上海200240)

1 FEC在UDP传输中的应用

在网络传输过程中，不可避免地会出现数据损伤，主要分为错误和丢失两种类型。错误是数据比特位发生了变化，丢失是数据包没有收到。在TCP协议和UDP协议中，接收到的数据包要接受校验，发生错误的数据包被自动丢弃。所以在TCP/UDP传输中，所有的数据损伤都会反映为丢包。因此，可以认为在UDP传输中不存在误码，将UDP传输线路等价为二进制删除信道(BEC)。传输中的数据损失位置即是丢包的位置，在解码过程中不需重新判断错误位置。

TCP协议对传输中出错的包会自动重传，所以对于损伤有较强的抵抗力。但另一方面丢包率较高的情况下，TCP传输过程中会出现大量的重传包占用资源，进一步降低传输效率。因此在能够承受少量数据损失但要求传输速度较快的场合，往往采用单向传输的UDP协议，如电视会议、视频广播、网络电话等。为了控制UDP传输中的丢包问题，常见的方法就是前向纠错编码(Forward Error Correction ，FEC)。

在FEC中，发送端在要发送的数据后加上一段冗余的数据，只要传输过程中数据损失量小于其纠错能力，接收端就可以根据这些冗余数据计算数据中的误码位置和误差值，从而自动修正错误。这种机制不同于自动重传(Automatic Repeat-reQuest，ARQ)，不存在接收端到发送端的反馈信息，所以不会阻塞网络，在丢包率较高的情况下性能更加优秀。

FEC编码将k个数据源信号(source symbols)编码为n个编码信号(encoding symbols)，编码率r=k/n，译码开销(overhead)记为ε，则

可以看出，在k固定的情况下，n和ε越大，传输的可靠性也越高，相应的数据冗余量和延迟也越大。在实际应用中，需要在可靠性和延迟中取得平衡，根据能够承受的数据损失量合理设置译码开销。

2 RS码和Raptor码

2.1 RS码原理和仿真设计

Reed-Solomon码(RS码)，是一类纠错能力较强的多进制循环码。RS码能较好地纠正突发错误和随机错误，在数据存储和视频广播等多个领域有着很好的表现。在DVB-H 标准中［1］，采用了 RS(204，188)码，即数据源为188 byte，编码冗余数据为16 byte，纠错能力为8 byte。RS码是一类循环码，以生成多项式G(x)为基础，通过计算校验位，其中M(x)是信息码多项式，Q(x)为校验多项式。最终编码结果为 C(x)=xn-kM(x)+xn-k·M(x)modQ(x)。

对于出错位置未知的RS编码，如果出错的数量大于(n-k)/2，则超出了RS码的纠错能力，解码失败［2］。在UDP传输中，错误位置就是丢包位置，可以通过同步数据进行记录，因此最大纠错数量提高为(n-k)。

通过RS编码，可以有效地恢复单个比特的传输损伤。但在UDP协议传输中，数据损伤是以整个数据包为单位的。如果编码后的数据按照原顺序发送，丢包时会损失大量的连续数据，造成解码失败。为了将丢包的数据损伤进行分散，提高解码成功率，可以以数据包为单位进行RS编码。但这种方法造成的延迟较大，且需要较大的缓存空间，因此实用性较低。另一种方式就是通过卷积交织码，将每次编码后的数据分散到不同的UDP包中，从而降低实际发送数据的序列相关性，提高解码成功率。

仿真实验中，外码采用RS(204，188)编码，在UDP传输中最大纠错能力为16个信号。内码则采用B=204个支路的卷积交织码，最大限度分散丢包的影响。因此，只要在连续发送的204个UDP数据包中，丢包的数量不超过16个，即可正确恢复数据。数据经过RS编码和卷积交织后，在包头部加入了4 byte的数据作为包序号。接收端通过比较连续收到的UDP包序号，可以判断传输过程中是否出现了丢包和乱序。对于丢包，在对应位置填入空白数据，并记录下无效数据的位置。使用RS码进行UDP传输的示意图见图1。

图1 RS码+卷积交织流程

2.2 喷泉码原理和仿真设计

数字喷泉码(Digital Fountain)是指由k个信源信号生成任意数量的编码符号，接收端只要收到任意n个编码符号，即可以较高概率成功译码。通常情况下，n略大于k。喷泉码就像一个不断涌出编码信号的喷泉，译码器就像收集编码信号的容器，只要收集到了足够数量的信号，就能达到解码的目的，而不取决于收到的是哪些编码信号。正因为这个特点，这种编码方式被称为喷泉码。喷泉码最初用于删除信道，但随后的研究发现，喷泉码在二进制对称信道(BSC)和加性高斯白噪声信道(AWGN)中也具有优秀的性能。

喷泉码最大的特点就是码率无关性(Rateless)，即不存在码长的定义，编码结果可以是大于信源长度的任意长度。与其他FEC编码不同，在喷泉码中n不表示码长，而是指解码所需的信号数量，译码开销码率无关性使得喷泉码特别适合用于无线通信中的广播、多播业务。

目前的喷泉码有LT码和Raptor码两种。LT码是第一种实用的喷泉码，但LT编码中由少量具有较高度的节点来确保解码成功率，这不但使LT码的解码成功率较为不稳定，而且在编码和解码过程中都带来了较大的计算量。为了解决这些问题，在LT码的基础上发展出了Raptor码［4-5］。Raptor码在LT码的基础上嵌套了预编码，一般采用低密度校验矩阵(LDPC)码［3］，进一步提高了解码成功率。在运算复杂度方面，由于减小了LT编码对于度很高的节点的依赖，提高了运算速度。而额外加入的预编码计算复杂度较小，对整体性能影响不大。Raptor码编码结构如图2所示。

3 性能分析

为了反映UDP传输中的数据损伤，采用网络损伤仪来模拟数据损伤。网络损伤仪两端相当于高损伤率的网络环境，可以设置通过其传输的数据的延迟、丢包、乱序和带宽抖动等损伤参数。在FEC编码的测试中，主要调整丢包率(Loss)参数。

RS码采用k=188，n=204的码长，译码开销为ε=9.6%。Raptor码的两组对照实验，译码开销分别设为9.6%和20%。RS译码先计算伴随多项式 s(x)=，再根据已知的错误位置构造错误位置多项式Λ(x)=∏(1+xXi)，则误差多项式E(x)为。最后根据C(x)=R(x)+E(x)得到解码数据。

Raptor码的解码过程由LDPC解码和LT解码串联组成，其中LT解码采取置信传播算法(Belief Propagation Algorithm)［6］。在每一个循环周期，不断在编码中寻找度为1的信号，并记录到译码集合。此后将每一个译出信号与跟它相关的所有编码信号进行模2和运算，去除编码信号与译出信号的关系，以产生新的度为1的编码信号。以上循环不断重复，直至全部信源信号被译出则解码成功。如果在某次循环中，编码信号的度全部大于1则解码失败。

图3给出了采取以上译码算法，3组实验在不同丢包率下的解码成功率，测试中的编码单元为8 bit。实验结果表明，RS码随着丢包率的提高，解码成功率降低较快，丢包率超过10%时已基本不具备稳定传输的能力。而Raptor码在高丢包率的条件下仍保有良好的性能，在丢包率上升至20%时仍能保持80%左右的解码成功率。

图3 FEC码在不同丢包率下的解码成功率

为了进一步衡量Raptor码的译码开销和丢包率的关系，测试在不同丢包率下能够99%成功解码所需的译码开销，实验结果如图4所示。可以看出，随着丢包率的上升，Raptor码仍能以近似线性关系的代价提升获得稳定的解码成功率，非常适合在恶劣的网络环境中进行数据传输。

图4 不同丢包率下Raptor码达到99%解码所需的译码开销

4 ARQ-Raptor多路数据传输方案

针对Internet传输环境，从发送端到接收端可能存在多条传输通路。为了能够充分利用多路传输资源，将数据流分摊到多路进行传输是一个必然的选择。在多路传输中，由于每一条传输线路都有自身的性能特性，因此其纠删策略难以简单地应用ARQ或者FEC。如果采用ARQTCP方式，每一条传输线路都将独立产生较大延迟，且互相之间严重不同步，对数据包的整合将变得十分复杂和不可靠。如果采用UDP-FEC方式，由于每条传输线路的丢包率和延时各不相同，导致接收端数据包发生乱序的几率大大上升，其传输可靠性和效率将低于FEC在单一传输线路上的表现［7］。

为了充分利用多路带宽对流媒体进行传输，可以采用少量重传请求结合Raptor码的传输方案。以流媒体多路传输为例，ARQ-Raptor多路数据传输由5部分组成，结构如图5所示。

图5 ARQ-Raptor多路传输示意图

1)编码器:接收流媒体数据包并进行Raptor编码，将编码结果推入转发器。

2)转发器:选择一条线路将收到的编码包送出。同时给每一个编码包赋予一个包序号(递增整数)，存入本地缓存。当收到确认信号之后，将已经正确接收的数据包从本地缓存中删除。缓存中的数据包如果经过一定时间还没有被正确接收(超时)，则选择一条线路将其重新发送。

3)传输线路:由多条单向传输线路和一条单向反馈线路组成，每条线路的丢包率和延迟互相独立。

4)接收器:本地缓存中将接收到的数据包按照包序号排列为一个有序表(Ordered List)。每当接收一个新数据包时，将其插入表中相应位置，并将表中序号最小的编码包发给解码器，然后从缓存中删除。每接收一定数量的包后，向转发器发送确认信号。

5)解码器:Raptor解码，解码出原始数据。

该方案依靠单一反馈线路，采用最小规模的重传请求对所有传输线路的丢包进行重传。包序号的加入，一方面是为了区分编码包，便于将确认信号与发送端缓存中的数据进行对应;另一方面，由于多路传输中的包乱序现象十分明显，接收器可以使用包序号对数据包进行排序，在进入解码器之前消除乱序。ARQ重传失败的数据由Raptor码进行恢复。

可以看出，整个方案的传输性能主要取决于合理的选择参数。首先在传输线路选择上，简单地采用轮询策略(Polling Strategy)，交替地从每一条线路发送编码包。在发送器和接收器缓存方面，较大的缓存可以更好地利用重传系统，减少传输过程中的损失;但另一方面，较大的缓存会大大提高整个系统的延时，在即时性要求较高的场合可能不适用。在仿真实验中，每个数据包容量为1 314 byte，发送器缓存设置为164 kbyte，接收器缓存为41 kbyte。在重传策略方面，给发送器缓存中的每一个编码包设置一个生存时限，在超过一定时间未收到确认信号的情况下将该编码包重新发送。设发送器缓存容量为c个数据包，生存时限为t，每一个编码包的最大重传次数。时限设置较小，可以提高编码包的重传次数，有助于提高编码包最终被正确接收的几率。但对于延迟较大的传输线路，较小的时限可能导致尚在传输过程中的编码包被大量重发，严重挤占传输资源，降低传输效率。仿真中设置生存时限为32，表示生存时间为发送器发送出32个编码包的时间。因此，每一个编码包最多有4次重发机会。

仿真实验设置RaptorQ冗余度为9.6%，使用5路传输流媒体视频文件，测试丢包率和解码成功率的关系，与单路RaptorQ编码对比如图6所示。在冗余度为9.6%的情况下，编码器输出编码包的速率为96.6 package/s，接收器缓存会先接收32个编码包才有输出，所以理论上传输系统带来的额外延迟为0.33 s。可以看出，在丢包率较高的情况下，采用了小规模重传可以明显提高传输可靠性。

在实验过程中，发现即使在丢包率较高的情况下，本方案也能以很高的几率成功解码。经过多路传输的视频流，也能在播放器中比较流畅地播放。但在30%丢包率下，虽然最终数据损伤极小，但在视频播放中还是偶尔可以看到明显卡顿现象。这是由于RaptorQ在解码失败的情况下会产生多个相邻的无效数据包，导致实际的数据损失都集中在较小的范围内，影响了播放效果。

5 结论

本文介绍了在UDP传输中应用FEC编码的仿真环境，并结合网络损伤仪对RS编码和Raptor编码的解码性能。实验表明，RS编码和Raptor编码在丢包率较低的情况下(＜5%)都能够很好地恢复数据。但随着丢包率的提高，RS码的纠错性能下降比较明显;而Raptor码仍能够以较小的开销保持优秀的解码成功率，因而更适于运用到复杂的网络环境中。本文还提出了结合ARQ和Raptor码的多路传输方案，实验结果表明，该方案能有效地利用多条传输线路对数据流进行高效可靠的传输。

［1］刘琪.DVB-H中RS码的算法研究和ASIC设计［D］.上海:上海交通大学，2008.

［2］余亚芳，张勇，王化深.RS码的译码算法及软件实现［J］.现代电子技术，2003，26(22):99-101.

［3］YANG M，LI Y，RYAN W.Design of efficiently encodable moderatelength high-rate irregular LDPC codes［J］.IEEE Trans.Communication，2004，52(4):564-571.

［4］LUBY M，SHOKROLLAHI A，WATSON M，et al.RFC 5053:Raptor forward error correction scheme for object delivery［S］.2007.

［5］SHOKROLLAHI A.Raptor codes［J］.IEEE Trans.Information Theory，2006，52(6):2551-2567.

［6］余国华.删除信道中的喷泉码译码技术研究［D］.上海:上海交通大学，2009.

［7］吴丹，田亚飞，杨晨阳.喷泉码多路并行转发中继系统传输时间分析［J］.通信学报，2010，31(8):121-126.