噴泉碼及其在無線視頻組播環(huán)境中的應(yīng)用

閆慧慧，宋建新

（南京郵電大學(xué) 圖像處理與圖像通信實驗室，江蘇 南京 210003）

0 引言

無線信道存在嚴重的干擾、衰落以及噪聲，這種高誤碼率、高突發(fā)誤幀的特點造成了視頻通信的困難。數(shù)字噴泉碼[1]解決了無線網(wǎng)絡(luò)中的丟包以及組播信道的異步接收問題?；跀?shù)字噴泉碼的組播解決方案具有良好的性能。

本文針對無線組播多跳環(huán)境提出兩種噴泉碼數(shù)據(jù)分發(fā)調(diào)度方案：1）非組播用戶的中間節(jié)點僅進行簡單的轉(zhuǎn)發(fā)，此方法實現(xiàn)簡單但不適應(yīng)復(fù)雜的多跳多播環(huán)境。2）中間節(jié)點解碼恢復(fù)出原始數(shù)據(jù)包后進行再次噴泉編碼，生成新的編碼包轉(zhuǎn)發(fā)給其下行節(jié)點，這種方法減少了數(shù)據(jù)調(diào)度的復(fù)雜性并能適應(yīng)節(jié)點的動態(tài)離開性，但增加了中間節(jié)點的負擔(dān)。

無線視頻多播主要的挑戰(zhàn)是如何為不同信道特征的多個接收端提供服務(wù)。如果想要保證所有用戶都能接收到足夠多的數(shù)據(jù)包并成功解碼，需要保證信道質(zhì)量最差的用戶也能收到足夠多的數(shù)據(jù)包，可能會對信道質(zhì)量好的用戶造成資源浪費。因此，提出一種基于不同碼長的混合噴泉編碼方案，發(fā)送端根據(jù)組播用戶信道質(zhì)量的差異選取不同碼長的噴泉編碼方案。實驗證明，對丟包率高、信道質(zhì)量差的接收端而言，短碼長的噴泉編碼方案提高了接收端的譯碼成功概率。

1 噴泉碼及其在組播環(huán)境下的分發(fā)調(diào)度

1.1 噴泉碼介紹

噴泉碼的基本原理是：編碼端將原始數(shù)據(jù)分割成K個原始數(shù)據(jù)數(shù)組，將這K個原始數(shù)據(jù)分組編碼生成任意數(shù)量的編碼分組，接收端只要收到其中任意N個編碼分組，即可通過譯碼以高概率成功恢復(fù)原始分組。一般情況下，N略大于K，引起的譯碼開銷定義為ε=N/K。上述編碼過程可被形象地看作源源不斷產(chǎn)生水滴的噴泉，只要用杯子接收足夠多的水滴即可，正因如此，這種編碼被稱為噴泉碼。

噴泉碼是一種無碼率編碼[2]，在基于包通信的系統(tǒng)中有接近理想的糾刪性能。接收端為了成功解碼，并不關(guān)注接收到哪個分組，不關(guān)注包到來的順序，只需要關(guān)注接收到一定量的編碼包即可。數(shù)字噴泉碼可以用多種編碼方式實現(xiàn)，例如Reed-Solomon碼，Tornado碼以及比較典型的LT碼和Raptor碼等。

LT碼[3]是一類通用刪除碼，具有簡便的譯碼算法。LT碼在繼承噴泉碼優(yōu)點的基礎(chǔ)上，大大降低了編解碼的復(fù)雜度，本文中采用了LT碼。

1.2 噴泉碼在組播環(huán)境下的分發(fā)調(diào)度

采用噴泉編碼機制，接收端不需要考慮收到編碼包的先后順序和接收數(shù)據(jù)段的區(qū)別，并且不會因為網(wǎng)絡(luò)帶寬條件導(dǎo)致部分數(shù)據(jù)包丟失。本節(jié)只要考慮噴泉碼在無線組播多跳環(huán)境下的數(shù)據(jù)分發(fā)調(diào)度方案。

假定Ad Hoc網(wǎng)絡(luò)中一個兩跳的多播組。源S對原始數(shù)據(jù)包進行噴泉編碼后，以一定速率分發(fā)多媒體數(shù)據(jù)流到組播用戶中。組播組用戶為節(jié)點T3，T4和T5。假設(shè)原始數(shù)據(jù)包有K=4個，譯碼開銷為1.25，即多播組用戶只要接收到N=5個數(shù)據(jù)包即可完全解碼。

采取以下兩種方案進行數(shù)據(jù)的分發(fā)，這兩種方案的差別在于中間節(jié)點的功能不同。

1.2.1 方案一

中間節(jié)點僅進行簡單的轉(zhuǎn)發(fā)功能，將接收到的數(shù)據(jù)包直接轉(zhuǎn)發(fā)給下行節(jié)點，如圖1所示。

源端S1使用噴泉編碼，媒體數(shù)據(jù)源S對原始數(shù)據(jù)塊｛1，2，3，4｝進行噴泉編碼，產(chǎn)生了無限數(shù)量的編碼數(shù)據(jù)包｛1’，2’，3’，4’，5’，…｝，S分別以一定速率向其下行節(jié)點T1和T2發(fā)送編碼數(shù)據(jù)塊｛1’，2’，3’，4’，5’，…｝和｛2’，3’，5’，6’，7’，…｝。

節(jié)點T1和節(jié)點T2收到子節(jié)點的請求時，對從上行節(jié)點收到的編碼數(shù)據(jù)包并不進行任何處理，直接轉(zhuǎn)發(fā)給其下行節(jié)點。T1以一定速率向其下行子節(jié)點T3和T4發(fā)送編碼數(shù)據(jù)塊｛1’，2’，3’，4’，6’｝，｛1’，3’，5’，6’，7’｝。T2向其子節(jié)點T5發(fā)送編碼數(shù)據(jù)塊｛3’，5’，6’，7’，9’｝。

組播用戶T3，T4，T5收到足夠的數(shù)據(jù)包后，分別向其上行節(jié)點T2，T3發(fā)送反饋消息，節(jié)點T2，T3停止發(fā)送數(shù)據(jù)。

此時節(jié)點T2，T3在收到下行節(jié)點的反饋消息后，立即發(fā)送反饋消息給其上行節(jié)點S，源節(jié)點S收到其所有下行節(jié)點的反饋消息后停止發(fā)送數(shù)據(jù)包。

這種方法的好處是非多播組用戶的中間節(jié)點不需進行解碼、再編碼，直接轉(zhuǎn)發(fā)數(shù)據(jù)包，減輕了不屬于多播組用戶的中間節(jié)點的負擔(dān)。帶來的問題是：這種方案只適用于簡單的多播網(wǎng)絡(luò)，對于復(fù)雜的多跳多播網(wǎng)絡(luò)不利于分發(fā)控制，且數(shù)據(jù)在多跳環(huán)境下需要進行多級控制，增加了網(wǎng)絡(luò)的負擔(dān)。

因此，提出在中間節(jié)點進行成功解碼后再次采用噴泉編碼的方案，即方案二。

1.2.2 方案二

中間節(jié)點進行解碼、再次編碼后，將再次編碼后的數(shù)據(jù)包轉(zhuǎn)發(fā)給下行節(jié)點，如圖2所示。

源端采用噴泉編碼，媒體數(shù)據(jù)源S對原始數(shù)據(jù)塊｛1，2，3，4｝進行噴泉編碼，產(chǎn)生了無限數(shù)量的編碼數(shù)據(jù)包｛1’，2’，3’，4’，5’，…｝，S分別以一定速率向其下行節(jié)點T1和T2發(fā)送編碼數(shù)據(jù)塊｛1’，2’，3’，4’，5’｝和｛5’，6’，7’，8’，9’｝。

節(jié)點T1和節(jié)點T2收到足夠多的數(shù)據(jù)包時發(fā)送反饋信息給其上行節(jié)點S，節(jié)點S停止發(fā)送數(shù)據(jù)包。然后T1和T2對從上行節(jié)點收到的編碼數(shù)據(jù)包進行解碼，恢復(fù)出原編碼數(shù)據(jù)包｛1，2，3，4｝。最后節(jié)點T1和T2分別對原始數(shù)據(jù)塊進行噴泉編碼，產(chǎn)生無限量數(shù)據(jù)包｛1”，2”，3”，4”，5”，…｝和｛1(3)，2(3)，3(3)，4(3)，5(3)，…｝并發(fā)送給其下行節(jié)點。

T1以一定速率向其下行子節(jié)點T3和T4發(fā)送編碼數(shù)據(jù)塊｛1”，2”，3”，4”，6”｝，｛1”，3”，5”，6”，7”｝。T3和T4收到足夠多數(shù)據(jù)包時向T1發(fā)送反饋消息，T1停止發(fā)送。T2向其子節(jié)點T5發(fā)送編碼數(shù)據(jù)塊｛2(3)，3(3)，4(3)，7(3)，8(3)｝。T5收到足夠多數(shù)據(jù)包后向T2發(fā)送反饋消息，T2停止發(fā)送。

可以看出，這種方案中，數(shù)據(jù)只需在相鄰跳間進行分發(fā)控制即可，減少了分發(fā)控制的復(fù)雜度。特別是當(dāng)有用戶臨時加入多播組時，只需請求它的上行節(jié)點進行數(shù)據(jù)分發(fā)，適應(yīng)了無線環(huán)境下節(jié)點的動態(tài)離開性。

2 無線組播環(huán)境中不同碼長的混合噴泉編碼

無線視頻多播面臨的主要挑戰(zhàn)是如何保證為不同信道特征的多個接收端提供服務(wù)，希望看到的理想狀態(tài)是：源廣播發(fā)送一條單視頻流給所有的接收端，每個接收端獲得的視頻分辨力可以和自己的信道質(zhì)量相匹配。這種理想狀態(tài)在目前的網(wǎng)絡(luò)設(shè)計方案中不可能實現(xiàn)，而且可能會造成視頻的“懸崖效應(yīng)”。因此，如果想要保證所有接收端都能接收到數(shù)據(jù)包，就必須按照所有接收端中支持的最低碼率來傳輸，這對于信道質(zhì)量好的用戶形成了資源上的浪費。

針對上述問題，目前的方法有兩種，但都不令人滿意。第一種方法應(yīng)用較為普遍，發(fā)送端給每個客戶端都采用單播發(fā)送一條獨立的數(shù)據(jù)流[4]。另一種方法是多分辨力編碼（MRC），它將每個視頻流分成一個基本層和多個增強層?；緦影l(fā)送速率最低，采用IEEE 802.11的比特率，保證每個接收端都能對基本層解碼[5]。增強層發(fā)送速率比基本層高，因此只有信道質(zhì)量好的客戶端才能對增強層解碼。多分辨力編碼適用于有線多播，這時，鏈路發(fā)生擁塞的接收端會避免下載增強層，而是僅下載基本層。但在無線環(huán)境中，所有層共享無線媒介，增強層的存在影響了基本層的傳輸帶寬，并與基本層形成競爭，這樣會導(dǎo)致質(zhì)量差的接收端可能連基本層都接收不到，性能也就進一步下降。

如何給組播用戶提供與其信道質(zhì)量相匹配的服務(wù)。文獻[6]提出基于疊加編碼與數(shù)字噴泉碼相結(jié)和的多播分析，但提出的方案過于繁瑣亦缺乏有效的仿真和實驗驗證。因此提出一種適應(yīng)多播環(huán)境的基于不同碼長的噴泉編碼方案。

鑒于Socket當(dāng)中timer發(fā)送機制是通過在一段時間內(nèi)取一定數(shù)量的數(shù)據(jù)包進行發(fā)送來達到速率控制的目的，那么只要單獨1個數(shù)據(jù)包的大小不超過其所進行傳輸?shù)男诺缼捈纯芍辽俦ＷC某時間段內(nèi)1個數(shù)據(jù)包的發(fā)送。

從噴泉碼的編碼碼長上入手，設(shè)想兩個信道，一個速率快，一個慢，丟包率差不多；或者速率相仿，但丟包率相差較大。這兩個信道可統(tǒng)一地在接收端表現(xiàn)為，同一段時間內(nèi)，信道質(zhì)量好的一方接收到更多有效數(shù)據(jù)包。

假定噴泉碼碼長500，譯碼開銷為1.16，則接收端接收到580個數(shù)據(jù)包即可完全解碼。假定每個發(fā)送的數(shù)據(jù)包大小為4 kbyte，設(shè)一傳輸時間段為10 s；信道質(zhì)量較好的信道傳輸速率為2 Mbit/s，丟包率為5%；信道質(zhì)量差者傳輸速率為1 Mbit/s，丟包率為10%。那么做一個統(tǒng)計學(xué)上的計算：質(zhì)量較好的接收端實際收到有效數(shù)據(jù)包為2 Mbit·s-1/（4 kbyte）×10 s×0.95=608個，可以完全解碼；而信道質(zhì)量差的接收端僅接收到1 Mbit·s-1/（4 kbyte）×10 s×0.9=288個數(shù)據(jù)包，無法完成解碼。

觀察噴泉碼的特性可以發(fā)現(xiàn)，碼長的改變決定的只是每個初始分段的大小，對生成矩陣和其產(chǎn)生的最終發(fā)送包大小影響很小。假定忽略編碼數(shù)據(jù)包大小和生成矩陣大小對傳輸?shù)挠绊?，又回到上面的假設(shè)。如果針對信道質(zhì)量較差者，將其噴泉碼碼長降低為200，此時譯碼開銷為1.3，接收端收到260個數(shù)據(jù)包即可完全解碼。雖然同樣只有288個有效包，但對于降低后的碼長也足以實現(xiàn)完全解碼。

根據(jù)以上理論，提出基于不同碼長的混合噴泉編碼方案：對于信道質(zhì)量差的一方，采用碼長較小的噴泉碼編碼方案，讓每個發(fā)送數(shù)據(jù)包中所包含的原始數(shù)據(jù)分組多一些，使之在進行解碼時對相同大小的原始數(shù)據(jù)需要更少的包就可以進行解碼。而對于信道質(zhì)量較好的一方，可以采用碼長更大的噴泉編碼方案，使之達到更加細致的編碼劃分和解碼效果。

當(dāng)然，采用短碼長編碼也存在一定弊端。簡單地舉例說明：K=8時，可能至少需要10個包才能完成解碼，但如果所有原始包不能解碼，看到的降質(zhì)畫面序列可能為“1345678”，“2”被丟掉了，損失相當(dāng)于12.5%的質(zhì)量；而K=4，可能只要5～6個包即可完成解碼，但一旦解碼不完全，降質(zhì)序列可能為“145678”，“23”被丟掉了，損失相當(dāng)于25%的質(zhì)量。因此，針對信道質(zhì)量差的組播用戶采用短碼長噴泉編碼，雖然成功地采用較少的有效數(shù)據(jù)包需求來緩解信道質(zhì)量低下的問題，但卻是以增加譯碼開銷、降低視頻質(zhì)量為代價。

3 實驗數(shù)據(jù)與分析

圖3是進行實驗的簡單系統(tǒng)模型示意圖。在該模型中，包括兩類節(jié)點：組播服務(wù)器和組播用戶。主要驗證對于信道質(zhì)量差，丟包率高的組播用戶，在短碼長情況下可以實現(xiàn)更高的譯碼成功概率。

服務(wù)器向組播用戶A和B發(fā)送視頻流，服務(wù)器采用噴泉碼LT碼進行編碼。

測試環(huán)境采用C語言開發(fā)，而且因為條件限制，在局域網(wǎng)環(huán)境中設(shè)置測試環(huán)境進行測試，表1給出本文涉及模塊的開發(fā)及測試環(huán)境。

表1 開發(fā)及測試環(huán)境

服務(wù)器主要負責(zé)監(jiān)聽組播用戶請求，讀取原始視頻文件，對其分塊處理后進行噴泉編碼發(fā)送。其中監(jiān)聽組播用戶請求使用TCP連接，編碼數(shù)據(jù)的發(fā)送使用UDP連接。組播用戶接收數(shù)據(jù)并進行解碼。

取兩種情況進行測試：碼長K=500、冗余E=150和碼長K=200、冗余E=200。觀察這兩種情況下隨著丟包率的上升接收端的譯碼成功概率。丟包率間隔為0.02，每種丟包率情況下進行循環(huán)測試200次。實驗結(jié)果如圖4所示。

從圖4可以看出，當(dāng)碼長K=500時，丟包率超過10%后譯碼成功概率就開始迅速下降。而碼長K=200時，即便丟包率達到35%，依然可以維持95%的譯碼成功概率。可以看到，短碼長情況下，以增加冗余為代價，換取了在高丟包率情況下的高譯碼成功概率。

對于信道質(zhì)量差的接收端，采用碼長較短的噴泉碼編碼方案，進行解碼時對相同大小的原始數(shù)據(jù)只需要更少的包就可以進行解碼，因此在丟包率高的情況下可以實現(xiàn)更高的譯碼成功概率。而對于信道質(zhì)量較好的一方，可以采用碼長更長的噴泉編碼方案，實現(xiàn)更好的噴泉碼性能。

4 小結(jié)

提出了兩種無線多播環(huán)境下的數(shù)據(jù)分發(fā)調(diào)度方案，一種是中間節(jié)點對接收到的數(shù)據(jù)包不進行處理直接轉(zhuǎn)發(fā)給其下行節(jié)點。另一種是中間節(jié)點對接收到的數(shù)據(jù)包進行解碼、再次噴泉編碼后再將新的編碼包發(fā)送給下行節(jié)點。隨后針對無線視頻多播的主要問題——如何保證為不同信道的多個接收端提供服務(wù)，提出了一種基于不同碼長編碼的混合噴泉編碼方案。實驗證明，對丟包率高、信道質(zhì)量差的接收端而言，短碼長的噴泉編碼方案提高了接收端的譯碼成功概率。

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

[2]鄧善征，杜興民，楊軍，等.LT碼在移動多媒體廣播系統(tǒng)中的應(yīng)用[J].電視技術(shù)，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]張揚帆.無線多播中的數(shù)字噴泉碼技術(shù)研究[D].武漢：華中科技大學(xué)，2008.