喷泉码及其在无线视频组播环境中的应用

闫慧慧，宋建新

（南京邮电大学 图像处理与图像通信实验室，江苏 南京 210003）

0 引言

无线信道存在严重的干扰、衰落以及噪声，这种高误码率、高突发误帧的特点造成了视频通信的困难。数字喷泉码[1]解决了无线网络中的丢包以及组播信道的异步接收问题。基于数字喷泉码的组播解决方案具有良好的性能。

本文针对无线组播多跳环境提出两种喷泉码数据分发调度方案：1）非组播用户的中间节点仅进行简单的转发，此方法实现简单但不适应复杂的多跳多播环境。2）中间节点解码恢复出原始数据包后进行再次喷泉编码，生成新的编码包转发给其下行节点，这种方法减少了数据调度的复杂性并能适应节点的动态离开性，但增加了中间节点的负担。

无线视频多播主要的挑战是如何为不同信道特征的多个接收端提供服务。如果想要保证所有用户都能接收到足够多的数据包并成功解码，需要保证信道质量最差的用户也能收到足够多的数据包，可能会对信道质量好的用户造成资源浪费。因此，提出一种基于不同码长的混合喷泉编码方案，发送端根据组播用户信道质量的差异选取不同码长的喷泉编码方案。实验证明，对丢包率高、信道质量差的接收端而言，短码长的喷泉编码方案提高了接收端的译码成功概率。

1 喷泉码及其在组播环境下的分发调度

1.1 喷泉码介绍

喷泉码的基本原理是：编码端将原始数据分割成K个原始数据数组，将这K个原始数据分组编码生成任意数量的编码分组，接收端只要收到其中任意N个编码分组，即可通过译码以高概率成功恢复原始分组。一般情况下，N略大于K，引起的译码开销定义为ε=N/K。上述编码过程可被形象地看作源源不断产生水滴的喷泉，只要用杯子接收足够多的水滴即可，正因如此，这种编码被称为喷泉码。

喷泉码是一种无码率编码[2]，在基于包通信的系统中有接近理想的纠删性能。接收端为了成功解码，并不关注接收到哪个分组，不关注包到来的顺序，只需要关注接收到一定量的编码包即可。数字喷泉码可以用多种编码方式实现，例如Reed-Solomon码，Tornado码以及比较典型的LT码和Raptor码等。

LT码[3]是一类通用删除码，具有简便的译码算法。LT码在继承喷泉码优点的基础上，大大降低了编解码的复杂度，本文中采用了LT码。

1.2 喷泉码在组播环境下的分发调度

采用喷泉编码机制，接收端不需要考虑收到编码包的先后顺序和接收数据段的区别，并且不会因为网络带宽条件导致部分数据包丢失。本节只要考虑喷泉码在无线组播多跳环境下的数据分发调度方案。

假定Ad Hoc网络中一个两跳的多播组。源S对原始数据包进行喷泉编码后，以一定速率分发多媒体数据流到组播用户中。组播组用户为节点T3，T4和T5。假设原始数据包有K=4个，译码开销为1.25，即多播组用户只要接收到N=5个数据包即可完全解码。

采取以下两种方案进行数据的分发，这两种方案的差别在于中间节点的功能不同。

1.2.1 方案一

中间节点仅进行简单的转发功能，将接收到的数据包直接转发给下行节点，如图1所示。

源端S1使用喷泉编码，媒体数据源S对原始数据块｛1，2，3，4｝进行喷泉编码，产生了无限数量的编码数据包｛1’，2’，3’，4’，5’，…｝，S分别以一定速率向其下行节点T1和T2发送编码数据块｛1’，2’，3’，4’，5’，…｝和｛2’，3’，5’，6’，7’，…｝。

节点T1和节点T2收到子节点的请求时，对从上行节点收到的编码数据包并不进行任何处理，直接转发给其下行节点。T1以一定速率向其下行子节点T3和T4发送编码数据块｛1’，2’，3’，4’，6’｝，｛1’，3’，5’，6’，7’｝。T2向其子节点T5发送编码数据块｛3’，5’，6’，7’，9’｝。

组播用户T3，T4，T5收到足够的数据包后，分别向其上行节点T2，T3发送反馈消息，节点T2，T3停止发送数据。

此时节点T2，T3在收到下行节点的反馈消息后，立即发送反馈消息给其上行节点S，源节点S收到其所有下行节点的反馈消息后停止发送数据包。

这种方法的好处是非多播组用户的中间节点不需进行解码、再编码，直接转发数据包，减轻了不属于多播组用户的中间节点的负担。带来的问题是：这种方案只适用于简单的多播网络，对于复杂的多跳多播网络不利于分发控制，且数据在多跳环境下需要进行多级控制，增加了网络的负担。

因此，提出在中间节点进行成功解码后再次采用喷泉编码的方案，即方案二。

1.2.2 方案二

中间节点进行解码、再次编码后，将再次编码后的数据包转发给下行节点，如图2所示。

源端采用喷泉编码，媒体数据源S对原始数据块｛1，2，3，4｝进行喷泉编码，产生了无限数量的编码数据包｛1’，2’，3’，4’，5’，…｝，S分别以一定速率向其下行节点T1和T2发送编码数据块｛1’，2’，3’，4’，5’｝和｛5’，6’，7’，8’，9’｝。

节点T1和节点T2收到足够多的数据包时发送反馈信息给其上行节点S，节点S停止发送数据包。然后T1和T2对从上行节点收到的编码数据包进行解码，恢复出原编码数据包｛1，2，3，4｝。最后节点T1和T2分别对原始数据块进行喷泉编码，产生无限量数据包｛1”，2”，3”，4”，5”，…｝和｛1(3)，2(3)，3(3)，4(3)，5(3)，…｝并发送给其下行节点。

T1以一定速率向其下行子节点T3和T4发送编码数据块｛1”，2”，3”，4”，6”｝，｛1”，3”，5”，6”，7”｝。T3和T4收到足够多数据包时向T1发送反馈消息，T1停止发送。T2向其子节点T5发送编码数据块｛2(3)，3(3)，4(3)，7(3)，8(3)｝。T5收到足够多数据包后向T2发送反馈消息，T2停止发送。

可以看出，这种方案中，数据只需在相邻跳间进行分发控制即可，减少了分发控制的复杂度。特别是当有用户临时加入多播组时，只需请求它的上行节点进行数据分发，适应了无线环境下节点的动态离开性。

2 无线组播环境中不同码长的混合喷泉编码

无线视频多播面临的主要挑战是如何保证为不同信道特征的多个接收端提供服务，希望看到的理想状态是：源广播发送一条单视频流给所有的接收端，每个接收端获得的视频分辨力可以和自己的信道质量相匹配。这种理想状态在目前的网络设计方案中不可能实现，而且可能会造成视频的“悬崖效应”。因此，如果想要保证所有接收端都能接收到数据包，就必须按照所有接收端中支持的最低码率来传输，这对于信道质量好的用户形成了资源上的浪费。

针对上述问题，目前的方法有两种，但都不令人满意。第一种方法应用较为普遍，发送端给每个客户端都采用单播发送一条独立的数据流[4]。另一种方法是多分辨力编码（MRC），它将每个视频流分成一个基本层和多个增强层。基本层发送速率最低，采用IEEE 802.11的比特率，保证每个接收端都能对基本层解码[5]。增强层发送速率比基本层高，因此只有信道质量好的客户端才能对增强层解码。多分辨力编码适用于有线多播，这时，链路发生拥塞的接收端会避免下载增强层，而是仅下载基本层。但在无线环境中，所有层共享无线媒介，增强层的存在影响了基本层的传输带宽，并与基本层形成竞争，这样会导致质量差的接收端可能连基本层都接收不到，性能也就进一步下降。

如何给组播用户提供与其信道质量相匹配的服务。文献[6]提出基于叠加编码与数字喷泉码相结和的多播分析，但提出的方案过于繁琐亦缺乏有效的仿真和实验验证。因此提出一种适应多播环境的基于不同码长的喷泉编码方案。

鉴于Socket当中timer发送机制是通过在一段时间内取一定数量的数据包进行发送来达到速率控制的目的，那么只要单独1个数据包的大小不超过其所进行传输的信道带宽即可至少保证某时间段内1个数据包的发送。

从喷泉码的编码码长上入手，设想两个信道，一个速率快，一个慢，丢包率差不多；或者速率相仿，但丢包率相差较大。这两个信道可统一地在接收端表现为，同一段时间内，信道质量好的一方接收到更多有效数据包。

假定喷泉码码长500，译码开销为1.16，则接收端接收到580个数据包即可完全解码。假定每个发送的数据包大小为4 kbyte，设一传输时间段为10 s；信道质量较好的信道传输速率为2 Mbit/s，丢包率为5%；信道质量差者传输速率为1 Mbit/s，丢包率为10%。那么做一个统计学上的计算：质量较好的接收端实际收到有效数据包为2 Mbit·s-1/（4 kbyte）×10 s×0.95=608个，可以完全解码；而信道质量差的接收端仅接收到1 Mbit·s-1/（4 kbyte）×10 s×0.9=288个数据包，无法完成解码。

观察喷泉码的特性可以发现，码长的改变决定的只是每个初始分段的大小，对生成矩阵和其产生的最终发送包大小影响很小。假定忽略编码数据包大小和生成矩阵大小对传输的影响，又回到上面的假设。如果针对信道质量较差者，将其喷泉码码长降低为200，此时译码开销为1.3，接收端收到260个数据包即可完全解码。虽然同样只有288个有效包，但对于降低后的码长也足以实现完全解码。

根据以上理论，提出基于不同码长的混合喷泉编码方案：对于信道质量差的一方，采用码长较小的喷泉码编码方案，让每个发送数据包中所包含的原始数据分组多一些，使之在进行解码时对相同大小的原始数据需要更少的包就可以进行解码。而对于信道质量较好的一方，可以采用码长更大的喷泉编码方案，使之达到更加细致的编码划分和解码效果。

当然，采用短码长编码也存在一定弊端。简单地举例说明：K=8时，可能至少需要10个包才能完成解码，但如果所有原始包不能解码，看到的降质画面序列可能为“1345678”，“2”被丢掉了，损失相当于12.5%的质量；而K=4，可能只要5～6个包即可完成解码，但一旦解码不完全，降质序列可能为“145678”，“23”被丢掉了，损失相当于25%的质量。因此，针对信道质量差的组播用户采用短码长喷泉编码，虽然成功地采用较少的有效数据包需求来缓解信道质量低下的问题，但却是以增加译码开销、降低视频质量为代价。

3 实验数据与分析

图3是进行实验的简单系统模型示意图。在该模型中，包括两类节点：组播服务器和组播用户。主要验证对于信道质量差，丢包率高的组播用户，在短码长情况下可以实现更高的译码成功概率。

服务器向组播用户A和B发送视频流，服务器采用喷泉码LT码进行编码。

测试环境采用C语言开发，而且因为条件限制，在局域网环境中设置测试环境进行测试，表1给出本文涉及模块的开发及测试环境。

表1 开发及测试环境

服务器主要负责监听组播用户请求，读取原始视频文件，对其分块处理后进行喷泉编码发送。其中监听组播用户请求使用TCP连接，编码数据的发送使用UDP连接。组播用户接收数据并进行解码。

取两种情况进行测试：码长K=500、冗余E=150和码长K=200、冗余E=200。观察这两种情况下随着丢包率的上升接收端的译码成功概率。丢包率间隔为0.02，每种丢包率情况下进行循环测试200次。实验结果如图4所示。

从图4可以看出，当码长K=500时，丢包率超过10%后译码成功概率就开始迅速下降。而码长K=200时，即便丢包率达到35%，依然可以维持95%的译码成功概率。可以看到，短码长情况下，以增加冗余为代价，换取了在高丢包率情况下的高译码成功概率。

对于信道质量差的接收端，采用码长较短的喷泉码编码方案，进行解码时对相同大小的原始数据只需要更少的包就可以进行解码，因此在丢包率高的情况下可以实现更高的译码成功概率。而对于信道质量较好的一方，可以采用码长更长的喷泉编码方案，实现更好的喷泉码性能。

4 小结

提出了两种无线多播环境下的数据分发调度方案，一种是中间节点对接收到的数据包不进行处理直接转发给其下行节点。另一种是中间节点对接收到的数据包进行解码、再次喷泉编码后再将新的编码包发送给下行节点。随后针对无线视频多播的主要问题——如何保证为不同信道的多个接收端提供服务，提出了一种基于不同码长编码的混合喷泉编码方案。实验证明，对丢包率高、信道质量差的接收端而言，短码长的喷泉编码方案提高了接收端的译码成功概率。

[1]MACKAY D J C.Fountain codes[J].IEEE Proceedings of Communications，2005，152（6）：1062-1068.

[2]邓善征，杜兴民，杨军，等.LT码在移动多媒体广播系统中的应用[J].电视技术，2007，31（3）：37-39.

[3]LUBY M.LT Codes[C]//Proc.43rd Annual IEEE Symposium on Foundations of Computer Science.[S.l.]：IEEE Press，2002：271-280.

[4]ELLEITHY K，SOBH T，MAHMOOD A，et al.Efficient support of wireless video multicast services in 3G and beyond[J].Advances in Computer，Information,and Systems Sciences,and Engineering，2005，1：205-210.

[5]WU D，HOU Y，ZHANG Y Q，et al.Scalable video coding and transport over broadband wireless networks[J].Proceedings of the IEEE，2001，89（1）：6-20.

[6]张扬帆.无线多播中的数字喷泉码技术研究[D].武汉：华中科技大学，2008.