段 濤，孫 軍

(1.上海交通大學(xué)電子工程系圖像通信與信息處理研究所，上海200240;2.上海市數(shù)字媒體處理與傳輸重點(diǎn)實(shí)驗(yàn)室，上海200240)

1 FEC在UDP傳輸中的應(yīng)用

在網(wǎng)絡(luò)傳輸過程中，不可避免地會出現(xiàn)數(shù)據(jù)損傷，主要分為錯(cuò)誤和丟失兩種類型。錯(cuò)誤是數(shù)據(jù)比特位發(fā)生了變化，丟失是數(shù)據(jù)包沒有收到。在TCP協(xié)議和UDP協(xié)議中，接收到的數(shù)據(jù)包要接受校驗(yàn)，發(fā)生錯(cuò)誤的數(shù)據(jù)包被自動(dòng)丟棄。所以在TCP/UDP傳輸中，所有的數(shù)據(jù)損傷都會反映為丟包。因此，可以認(rèn)為在UDP傳輸中不存在誤碼，將UDP傳輸線路等價(jià)為二進(jìn)制刪除信道(BEC)。傳輸中的數(shù)據(jù)損失位置即是丟包的位置，在解碼過程中不需重新判斷錯(cuò)誤位置。

TCP協(xié)議對傳輸中出錯(cuò)的包會自動(dòng)重傳，所以對于損傷有較強(qiáng)的抵抗力。但另一方面丟包率較高的情況下，TCP傳輸過程中會出現(xiàn)大量的重傳包占用資源，進(jìn)一步降低傳輸效率。因此在能夠承受少量數(shù)據(jù)損失但要求傳輸速度較快的場合，往往采用單向傳輸?shù)腢DP協(xié)議，如電視會議、視頻廣播、網(wǎng)絡(luò)電話等。為了控制UDP傳輸中的丟包問題，常見的方法就是前向糾錯(cuò)編碼(Forward Error Correction ，F(xiàn)EC)。

在FEC中，發(fā)送端在要發(fā)送的數(shù)據(jù)后加上一段冗余的數(shù)據(jù)，只要傳輸過程中數(shù)據(jù)損失量小于其糾錯(cuò)能力，接收端就可以根據(jù)這些冗余數(shù)據(jù)計(jì)算數(shù)據(jù)中的誤碼位置和誤差值，從而自動(dòng)修正錯(cuò)誤。這種機(jī)制不同于自動(dòng)重傳(Automatic Repeat-reQuest，ARQ)，不存在接收端到發(fā)送端的反饋信息，所以不會阻塞網(wǎng)絡(luò)，在丟包率較高的情況下性能更加優(yōu)秀。

FEC編碼將k個(gè)數(shù)據(jù)源信號(source symbols)編碼為n個(gè)編碼信號(encoding symbols)，編碼率r=k/n，譯碼開銷(overhead)記為ε，則

可以看出，在k固定的情況下，n和ε越大，傳輸?shù)目煽啃砸苍礁撸鄳?yīng)的數(shù)據(jù)冗余量和延遲也越大。在實(shí)際應(yīng)用中，需要在可靠性和延遲中取得平衡，根據(jù)能夠承受的數(shù)據(jù)損失量合理設(shè)置譯碼開銷。

2 RS碼和Raptor碼

2.1 RS碼原理和仿真設(shè)計(jì)

Reed-Solomon碼(RS碼)，是一類糾錯(cuò)能力較強(qiáng)的多進(jìn)制循環(huán)碼。RS碼能較好地糾正突發(fā)錯(cuò)誤和隨機(jī)錯(cuò)誤，在數(shù)據(jù)存儲和視頻廣播等多個(gè)領(lǐng)域有著很好的表現(xiàn)。在DVB-H 標(biāo)準(zhǔn)中［1］，采用了 RS(204，188)碼，即數(shù)據(jù)源為188 byte，編碼冗余數(shù)據(jù)為16 byte，糾錯(cuò)能力為8 byte。RS碼是一類循環(huán)碼，以生成多項(xiàng)式G(x)為基礎(chǔ)，通過計(jì)算校驗(yàn)位，其中M(x)是信息碼多項(xiàng)式，Q(x)為校驗(yàn)多項(xiàng)式。最終編碼結(jié)果為 C(x)=xn-kM(x)+xn-k·M(x)modQ(x)。

對于出錯(cuò)位置未知的RS編碼，如果出錯(cuò)的數(shù)量大于(n-k)/2，則超出了RS碼的糾錯(cuò)能力，解碼失?。?］。在UDP傳輸中，錯(cuò)誤位置就是丟包位置，可以通過同步數(shù)據(jù)進(jìn)行記錄，因此最大糾錯(cuò)數(shù)量提高為(n-k)。

通過RS編碼，可以有效地恢復(fù)單個(gè)比特的傳輸損傷。但在UDP協(xié)議傳輸中，數(shù)據(jù)損傷是以整個(gè)數(shù)據(jù)包為單位的。如果編碼后的數(shù)據(jù)按照原順序發(fā)送，丟包時(shí)會損失大量的連續(xù)數(shù)據(jù)，造成解碼失敗。為了將丟包的數(shù)據(jù)損傷進(jìn)行分散，提高解碼成功率，可以以數(shù)據(jù)包為單位進(jìn)行RS編碼。但這種方法造成的延遲較大，且需要較大的緩存空間，因此實(shí)用性較低。另一種方式就是通過卷積交織碼，將每次編碼后的數(shù)據(jù)分散到不同的UDP包中，從而降低實(shí)際發(fā)送數(shù)據(jù)的序列相關(guān)性，提高解碼成功率。

仿真實(shí)驗(yàn)中，外碼采用RS(204，188)編碼，在UDP傳輸中最大糾錯(cuò)能力為16個(gè)信號。內(nèi)碼則采用B=204個(gè)支路的卷積交織碼，最大限度分散丟包的影響。因此，只要在連續(xù)發(fā)送的204個(gè)UDP數(shù)據(jù)包中，丟包的數(shù)量不超過16個(gè)，即可正確恢復(fù)數(shù)據(jù)。數(shù)據(jù)經(jīng)過RS編碼和卷積交織后，在包頭部加入了4 byte的數(shù)據(jù)作為包序號。接收端通過比較連續(xù)收到的UDP包序號，可以判斷傳輸過程中是否出現(xiàn)了丟包和亂序。對于丟包，在對應(yīng)位置填入空白數(shù)據(jù)，并記錄下無效數(shù)據(jù)的位置。使用RS碼進(jìn)行UDP傳輸?shù)氖疽鈭D見圖1。

圖1 RS碼+卷積交織流程

2.2 噴泉碼原理和仿真設(shè)計(jì)

數(shù)字噴泉碼(Digital Fountain)是指由k個(gè)信源信號生成任意數(shù)量的編碼符號，接收端只要收到任意n個(gè)編碼符號，即可以較高概率成功譯碼。通常情況下，n略大于k。噴泉碼就像一個(gè)不斷涌出編碼信號的噴泉，譯碼器就像收集編碼信號的容器，只要收集到了足夠數(shù)量的信號，就能達(dá)到解碼的目的，而不取決于收到的是哪些編碼信號。正因?yàn)檫@個(gè)特點(diǎn)，這種編碼方式被稱為噴泉碼。噴泉碼最初用于刪除信道，但隨后的研究發(fā)現(xiàn)，噴泉碼在二進(jìn)制對稱信道(BSC)和加性高斯白噪聲信道(AWGN)中也具有優(yōu)秀的性能。

噴泉碼最大的特點(diǎn)就是碼率無關(guān)性(Rateless)，即不存在碼長的定義，編碼結(jié)果可以是大于信源長度的任意長度。與其他FEC編碼不同，在噴泉碼中n不表示碼長，而是指解碼所需的信號數(shù)量，譯碼開銷碼率無關(guān)性使得噴泉碼特別適合用于無線通信中的廣播、多播業(yè)務(wù)。

目前的噴泉碼有LT碼和Raptor碼兩種。LT碼是第一種實(shí)用的噴泉碼，但LT編碼中由少量具有較高度的節(jié)點(diǎn)來確保解碼成功率，這不但使LT碼的解碼成功率較為不穩(wěn)定，而且在編碼和解碼過程中都帶來了較大的計(jì)算量。為了解決這些問題，在LT碼的基礎(chǔ)上發(fā)展出了Raptor碼［4-5］。Raptor碼在LT碼的基礎(chǔ)上嵌套了預(yù)編碼，一般采用低密度校驗(yàn)矩陣(LDPC)碼［3］，進(jìn)一步提高了解碼成功率。在運(yùn)算復(fù)雜度方面，由于減小了LT編碼對于度很高的節(jié)點(diǎn)的依賴，提高了運(yùn)算速度。而額外加入的預(yù)編碼計(jì)算復(fù)雜度較小，對整體性能影響不大。Raptor碼編碼結(jié)構(gòu)如圖2所示。

3 性能分析

為了反映UDP傳輸中的數(shù)據(jù)損傷，采用網(wǎng)絡(luò)損傷儀來模擬數(shù)據(jù)損傷。網(wǎng)絡(luò)損傷儀兩端相當(dāng)于高損傷率的網(wǎng)絡(luò)環(huán)境，可以設(shè)置通過其傳輸?shù)臄?shù)據(jù)的延遲、丟包、亂序和帶寬抖動(dòng)等損傷參數(shù)。在FEC編碼的測試中，主要調(diào)整丟包率(Loss)參數(shù)。

RS碼采用k=188，n=204的碼長，譯碼開銷為ε=9.6%。Raptor碼的兩組對照實(shí)驗(yàn)，譯碼開銷分別設(shè)為9.6%和20%。RS譯碼先計(jì)算伴隨多項(xiàng)式 s(x)=，再根據(jù)已知的錯(cuò)誤位置構(gòu)造錯(cuò)誤位置多項(xiàng)式Λ(x)=∏(1+xXi)，則誤差多項(xiàng)式E(x)為。最后根據(jù)C(x)=R(x)+E(x)得到解碼數(shù)據(jù)。

Raptor碼的解碼過程由LDPC解碼和LT解碼串聯(lián)組成，其中LT解碼采取置信傳播算法(Belief Propagation Algorithm)［6］。在每一個(gè)循環(huán)周期，不斷在編碼中尋找度為1的信號，并記錄到譯碼集合。此后將每一個(gè)譯出信號與跟它相關(guān)的所有編碼信號進(jìn)行模2和運(yùn)算，去除編碼信號與譯出信號的關(guān)系，以產(chǎn)生新的度為1的編碼信號。以上循環(huán)不斷重復(fù)，直至全部信源信號被譯出則解碼成功。如果在某次循環(huán)中，編碼信號的度全部大于1則解碼失敗。

圖3給出了采取以上譯碼算法，3組實(shí)驗(yàn)在不同丟包率下的解碼成功率，測試中的編碼單元為8 bit。實(shí)驗(yàn)結(jié)果表明，RS碼隨著丟包率的提高，解碼成功率降低較快，丟包率超過10%時(shí)已基本不具備穩(wěn)定傳輸?shù)哪芰?。而Raptor碼在高丟包率的條件下仍保有良好的性能，在丟包率上升至20%時(shí)仍能保持80%左右的解碼成功率。

圖3 FEC碼在不同丟包率下的解碼成功率

為了進(jìn)一步衡量Raptor碼的譯碼開銷和丟包率的關(guān)系，測試在不同丟包率下能夠99%成功解碼所需的譯碼開銷，實(shí)驗(yàn)結(jié)果如圖4所示?？梢钥闯?，隨著丟包率的上升，Raptor碼仍能以近似線性關(guān)系的代價(jià)提升獲得穩(wěn)定的解碼成功率，非常適合在惡劣的網(wǎng)絡(luò)環(huán)境中進(jìn)行數(shù)據(jù)傳輸。

圖4 不同丟包率下Raptor碼達(dá)到99%解碼所需的譯碼開銷

4 ARQ-Raptor多路數(shù)據(jù)傳輸方案

針對Internet傳輸環(huán)境，從發(fā)送端到接收端可能存在多條傳輸通路。為了能夠充分利用多路傳輸資源，將數(shù)據(jù)流分?jǐn)偟蕉嗦愤M(jìn)行傳輸是一個(gè)必然的選擇。在多路傳輸中，由于每一條傳輸線路都有自身的性能特性，因此其糾刪策略難以簡單地應(yīng)用ARQ或者FEC。如果采用ARQTCP方式，每一條傳輸線路都將獨(dú)立產(chǎn)生較大延遲，且互相之間嚴(yán)重不同步，對數(shù)據(jù)包的整合將變得十分復(fù)雜和不可靠。如果采用UDP-FEC方式，由于每條傳輸線路的丟包率和延時(shí)各不相同，導(dǎo)致接收端數(shù)據(jù)包發(fā)生亂序的幾率大大上升，其傳輸可靠性和效率將低于FEC在單一傳輸線路上的表現(xiàn)［7］。

為了充分利用多路帶寬對流媒體進(jìn)行傳輸，可以采用少量重傳請求結(jié)合Raptor碼的傳輸方案。以流媒體多路傳輸為例，ARQ-Raptor多路數(shù)據(jù)傳輸由5部分組成，結(jié)構(gòu)如圖5所示。

圖5 ARQ-Raptor多路傳輸示意圖

1)編碼器:接收流媒體數(shù)據(jù)包并進(jìn)行Raptor編碼，將編碼結(jié)果推入轉(zhuǎn)發(fā)器。

2)轉(zhuǎn)發(fā)器:選擇一條線路將收到的編碼包送出。同時(shí)給每一個(gè)編碼包賦予一個(gè)包序號(遞增整數(shù))，存入本地緩存。當(dāng)收到確認(rèn)信號之后，將已經(jīng)正確接收的數(shù)據(jù)包從本地緩存中刪除。緩存中的數(shù)據(jù)包如果經(jīng)過一定時(shí)間還沒有被正確接收(超時(shí))，則選擇一條線路將其重新發(fā)送。

3)傳輸線路:由多條單向傳輸線路和一條單向反饋線路組成，每條線路的丟包率和延遲互相獨(dú)立。

4)接收器:本地緩存中將接收到的數(shù)據(jù)包按照包序號排列為一個(gè)有序表(Ordered List)。每當(dāng)接收一個(gè)新數(shù)據(jù)包時(shí)，將其插入表中相應(yīng)位置，并將表中序號最小的編碼包發(fā)給解碼器，然后從緩存中刪除。每接收一定數(shù)量的包后，向轉(zhuǎn)發(fā)器發(fā)送確認(rèn)信號。

5)解碼器:Raptor解碼，解碼出原始數(shù)據(jù)。

該方案依靠單一反饋線路，采用最小規(guī)模的重傳請求對所有傳輸線路的丟包進(jìn)行重傳。包序號的加入，一方面是為了區(qū)分編碼包，便于將確認(rèn)信號與發(fā)送端緩存中的數(shù)據(jù)進(jìn)行對應(yīng);另一方面，由于多路傳輸中的包亂序現(xiàn)象十分明顯，接收器可以使用包序號對數(shù)據(jù)包進(jìn)行排序，在進(jìn)入解碼器之前消除亂序。ARQ重傳失敗的數(shù)據(jù)由Raptor碼進(jìn)行恢復(fù)。

可以看出，整個(gè)方案的傳輸性能主要取決于合理的選擇參數(shù)。首先在傳輸線路選擇上，簡單地采用輪詢策略(Polling Strategy)，交替地從每一條線路發(fā)送編碼包。在發(fā)送器和接收器緩存方面，較大的緩存可以更好地利用重傳系統(tǒng)，減少傳輸過程中的損失;但另一方面，較大的緩存會大大提高整個(gè)系統(tǒng)的延時(shí)，在即時(shí)性要求較高的場合可能不適用。在仿真實(shí)驗(yàn)中，每個(gè)數(shù)據(jù)包容量為1 314 byte，發(fā)送器緩存設(shè)置為164 kbyte，接收器緩存為41 kbyte。在重傳策略方面，給發(fā)送器緩存中的每一個(gè)編碼包設(shè)置一個(gè)生存時(shí)限，在超過一定時(shí)間未收到確認(rèn)信號的情況下將該編碼包重新發(fā)送。設(shè)發(fā)送器緩存容量為c個(gè)數(shù)據(jù)包，生存時(shí)限為t，每一個(gè)編碼包的最大重傳次數(shù)。時(shí)限設(shè)置較小，可以提高編碼包的重傳次數(shù)，有助于提高編碼包最終被正確接收的幾率。但對于延遲較大的傳輸線路，較小的時(shí)限可能導(dǎo)致尚在傳輸過程中的編碼包被大量重發(fā)，嚴(yán)重?cái)D占傳輸資源，降低傳輸效率。仿真中設(shè)置生存時(shí)限為32，表示生存時(shí)間為發(fā)送器發(fā)送出32個(gè)編碼包的時(shí)間。因此，每一個(gè)編碼包最多有4次重發(fā)機(jī)會。

仿真實(shí)驗(yàn)設(shè)置RaptorQ冗余度為9.6%，使用5路傳輸流媒體視頻文件，測試丟包率和解碼成功率的關(guān)系，與單路RaptorQ編碼對比如圖6所示。在冗余度為9.6%的情況下，編碼器輸出編碼包的速率為96.6 package/s，接收器緩存會先接收32個(gè)編碼包才有輸出，所以理論上傳輸系統(tǒng)帶來的額外延遲為0.33 s?？梢钥闯?，在丟包率較高的情況下，采用了小規(guī)模重傳可以明顯提高傳輸可靠性。

在實(shí)驗(yàn)過程中，發(fā)現(xiàn)即使在丟包率較高的情況下，本方案也能以很高的幾率成功解碼。經(jīng)過多路傳輸?shù)囊曨l流，也能在播放器中比較流暢地播放。但在30%丟包率下，雖然最終數(shù)據(jù)損傷極小，但在視頻播放中還是偶爾可以看到明顯卡頓現(xiàn)象。這是由于RaptorQ在解碼失敗的情況下會產(chǎn)生多個(gè)相鄰的無效數(shù)據(jù)包，導(dǎo)致實(shí)際的數(shù)據(jù)損失都集中在較小的范圍內(nèi)，影響了播放效果。

5 結(jié)論

本文介紹了在UDP傳輸中應(yīng)用FEC編碼的仿真環(huán)境，并結(jié)合網(wǎng)絡(luò)損傷儀對RS編碼和Raptor編碼的解碼性能。實(shí)驗(yàn)表明，RS編碼和Raptor編碼在丟包率較低的情況下(＜5%)都能夠很好地恢復(fù)數(shù)據(jù)。但隨著丟包率的提高，RS碼的糾錯(cuò)性能下降比較明顯;而Raptor碼仍能夠以較小的開銷保持優(yōu)秀的解碼成功率，因而更適于運(yùn)用到復(fù)雜的網(wǎng)絡(luò)環(huán)境中。本文還提出了結(jié)合ARQ和Raptor碼的多路傳輸方案，實(shí)驗(yàn)結(jié)果表明，該方案能有效地利用多條傳輸線路對數(shù)據(jù)流進(jìn)行高效可靠的傳輸。

［1］劉琪.DVB-H中RS碼的算法研究和ASIC設(shè)計(jì)［D］.上海:上海交通大學(xué)，2008.

［2］余亞芳，張勇，王化深.RS碼的譯碼算法及軟件實(shí)現(xiàn)［J］.現(xiàn)代電子技術(shù)，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］余國華.刪除信道中的噴泉碼譯碼技術(shù)研究［D］.上海:上海交通大學(xué)，2009.

［7］吳丹，田亞飛，楊晨陽.噴泉碼多路并行轉(zhuǎn)發(fā)中繼系統(tǒng)傳輸時(shí)間分析［J］.通信學(xué)報(bào)，2010，31(8):121-126.