閆慧慧，宋建新

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

0 引言

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

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

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

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

1.1 噴泉碼介紹

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

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

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

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

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

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

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

1.2.1 方案一

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

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

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

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

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

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

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

1.2.2 方案二

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)數(shù)據(jù)與分析

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

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

測(cè)試環(huán)境采用C語(yǔ)言開(kāi)發(fā)，而且因?yàn)闂l件限制，在局域網(wǎng)環(huán)境中設(shè)置測(cè)試環(huán)境進(jìn)行測(cè)試，表1給出本文涉及模塊的開(kāi)發(fā)及測(cè)試環(huán)境。

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

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

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

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

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

4 小結(jié)

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

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

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