噴泉碼及其在無線視頻組播環境中的應用

閆慧慧，宋建新

（南京郵電大學 圖像處理與圖像通信實驗室，江蘇 南京 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.