FEC在高波動性網絡中的應用研究

段 濤，孫 軍

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

1 FEC在UDP傳輸中的應用

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

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

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

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

可以看出，在k固定的情況下，n和ε越大，傳輸的可靠性也越高，相應的數據冗余量和延遲也越大。在實際應用中，需要在可靠性和延遲中取得平衡，根據能夠承受的數據損失量合理設置譯碼開銷。

2 RS碼和Raptor碼

2.1 RS碼原理和仿真設計

Reed-Solomon碼(RS碼)，是一類糾錯能力較強的多進制循環碼。RS碼能較好地糾正突發錯誤和隨機錯誤，在數據存儲和視頻廣播等多個領域有著很好的表現。在DVB-H 標準中［1］，采用了 RS(204，188)碼，即數據源為188 byte，編碼冗余數據為16 byte，糾錯能力為8 byte。RS碼是一類循環碼，以生成多項式G(x)為基礎，通過計算校驗位，其中M(x)是信息碼多項式，Q(x)為校驗多項式。最終編碼結果為 C(x)=xn-kM(x)+xn-k·M(x)modQ(x)。

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

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

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

圖1 RS碼+卷積交織流程

2.2 噴泉碼原理和仿真設計

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

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

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

3 性能分析

為了反映UDP傳輸中的數據損傷，采用網絡損傷儀來模擬數據損傷。網絡損傷儀兩端相當于高損傷率的網絡環境，可以設置通過其傳輸的數據的延遲、丟包、亂序和帶寬抖動等損傷參數。在FEC編碼的測試中，主要調整丟包率(Loss)參數。

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

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

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

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

為了進一步衡量Raptor碼的譯碼開銷和丟包率的關系，測試在不同丟包率下能夠99%成功解碼所需的譯碼開銷，實驗結果如圖4所示。可以看出，隨著丟包率的上升，Raptor碼仍能以近似線性關系的代價提升獲得穩定的解碼成功率，非常適合在惡劣的網絡環境中進行數據傳輸。

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

4 ARQ-Raptor多路數據傳輸方案

針對Internet傳輸環境，從發送端到接收端可能存在多條傳輸通路。為了能夠充分利用多路傳輸資源，將數據流分攤到多路進行傳輸是一個必然的選擇。在多路傳輸中，由于每一條傳輸線路都有自身的性能特性，因此其糾刪策略難以簡單地應用ARQ或者FEC。如果采用ARQTCP方式，每一條傳輸線路都將獨立產生較大延遲，且互相之間嚴重不同步，對數據包的整合將變得十分復雜和不可靠。如果采用UDP-FEC方式，由于每條傳輸線路的丟包率和延時各不相同，導致接收端數據包發生亂序的幾率大大上升，其傳輸可靠性和效率將低于FEC在單一傳輸線路上的表現［7］。

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

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

1)編碼器:接收流媒體數據包并進行Raptor編碼，將編碼結果推入轉發器。

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

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

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

5)解碼器:Raptor解碼，解碼出原始數據。

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

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

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

在實驗過程中，發現即使在丟包率較高的情況下，本方案也能以很高的幾率成功解碼。經過多路傳輸的視頻流，也能在播放器中比較流暢地播放。但在30%丟包率下，雖然最終數據損傷極小，但在視頻播放中還是偶爾可以看到明顯卡頓現象。這是由于RaptorQ在解碼失敗的情況下會產生多個相鄰的無效數據包，導致實際的數據損失都集中在較小的范圍內，影響了播放效果。

5 結論

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

［1］劉琪.DVB-H中RS碼的算法研究和ASIC設計［D］.上海:上海交通大學，2008.

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

［7］吳丹，田亞飛，楊晨陽.噴泉碼多路并行轉發中繼系統傳輸時間分析［J］.通信學報，2010，31(8):121-126.