朱宏鵬，張更新，李廣俠

（解放軍理工大學 通信工程學院，江蘇 南京 210007）

1 引言

衛(wèi)星數據廣播分發(fā)系統(tǒng)具有天然廣播特性，能夠實現(xiàn)各類信息的綜合、分發(fā)和管理。由于衛(wèi)星信道發(fā)生分組差錯的概率較高，加上各接收機分處不同的地點，其工作環(huán)境和地球站技術指標可能各不相同，導致系統(tǒng)具有異構性。因此，必須采取一些措施來降低分組差錯率、克服系統(tǒng)異構性，否則會嚴重制約衛(wèi)星數據廣播分發(fā)系統(tǒng)的應用。采用分組級前向糾錯編碼（FEC）技術，能夠有效解決衛(wèi)星數據廣播分發(fā)系統(tǒng)中高分組差錯率和信道特性異構性所帶來的時延長、分組成功分發(fā)概率低、信道利用率低等問題[1]。

RSE碼是一項傳統(tǒng)的分組級FEC技術，其編譯碼時延大，系統(tǒng)資源消耗大，容忍的丟包率低，不適合大量用戶的數據傳輸[2]。文獻[3]提出了一類新的分組級FEC技術，即噴泉碼，其主要包括LT碼[4]和Raptor碼[5]。該技術采用隨機編碼思想，編碼碼率動態(tài)可變，在有限數目的原始數據分組輸入的情況下可以產生無限數目的編碼數據分組，接收端在收到任意一組稍多于原始數據分組總數的編碼分組后，就能正確恢復出所有的原始數據分組，而不管具體接收到的是哪些編碼分組。噴泉碼編譯碼時延小，且能夠保證任意數量信道特性異構的用戶可以在任意時刻接入系統(tǒng)并以很高的效率完成數據的接收[3]，因此，已經被第三代蜂窩網絡多媒體廣播/多點傳送服務(MBMS)和 DVB-H標準（手機電視標準）所采用[6]。

度分布算法是影響噴泉碼中LT碼性能的關鍵。目前LT碼采用的是健壯孤立子度分布算法[4]，其恢復出所有原始數據分組所需要編碼分組的數目仍然偏大，且多次實驗結果存在較大的波動。本文提出一種理論上可解但并不實用的最優(yōu)度分布算法，并在此基礎上給出一種實用的次優(yōu)度分布算法。仿真結果表明，次優(yōu)度分布算法的譯碼性能優(yōu)于健壯孤立子度分布算法，采用基于次優(yōu)度分布算法的改進型LT碼對提高衛(wèi)星數據廣播分發(fā)系統(tǒng)的信道利用率大有裨益。

2 系統(tǒng)模型與協(xié)議框架

在衛(wèi)星數據廣播分發(fā)系統(tǒng)中，作為信息源的數據分發(fā)中心將信息通過同一條上行鏈路發(fā)送到衛(wèi)星，然后由衛(wèi)星轉發(fā)給大量的接收機。由于采用同一條上行鏈路，各接收機具有相同的上行鏈路誤碼特性，但各接收機所處地點和工作環(huán)境不同，各自的下行鏈路具有不同的誤碼特性。圖1給出了衛(wèi)星數據廣播分發(fā)系統(tǒng)的簡化模型，其中，Pu為上行鏈路的分組出錯概率，Pdm為第m個接收機下行鏈路的分組出錯概率。

為了克服信道特性的異構性，降低分組出錯概率，減少重發(fā)丟失的分組，提高系統(tǒng)的信道利用率，在分發(fā)系統(tǒng)的協(xié)議棧中加入分組級FEC層，使其位于網絡層之上，用于保證上層協(xié)議的可靠工作，協(xié)議棧結構如圖2所示。

在上述協(xié)議棧結構中，分組級 FEC層可以采用RSE碼或噴泉碼等，本文在此采用噴泉碼中的LT碼。

3 LT碼編譯碼原理

對文中所用的參數作如下說明：原始數據長度為 N，分組長度為l，原始數據分組的數目為 k，k=［N/l］，接收端參加譯碼的一共有 E 個編碼分組，編碼分組的度為d。

LT碼編碼過程如下。

1) 欲產生一個編碼分組，則需要按照度分布函數隨機選擇一個度d。

2) 從所有的原始數據分組中等概隨機地選取d個分組作為生成該編碼分組的原始數據分組。

3) 將選取的d個原始數據分組進行異或運算，得出的結果便是編碼分組的值。

4) 重復以上步驟可以源源不斷地產生編碼分組。

上面第2步在隨機選取d個原始數據分組時，如果完全隨機選擇，為了在編碼分組的報頭信息中傳送原始數據分組的位置信息，需要占用 dlbkbit的開銷，其中，k為原始數據分組的數目。當k和d較大時，此項開銷很大，在實際應用中并不可取，因此文獻[7]給出了實用的有限隨機LT碼的構造方法，可大大節(jié)省報頭開銷。

下面介紹LT碼的譯碼過程和度分布函數。

定義1LT譯碼過程：開始時k個原始數據分組均未被恢復。首先，釋放E個編碼分組中所有度數為1的分組，恢復出它們所對應的原始數據分組。已經被恢復出來但還未被處理的原始數據分組的集合構成預處理集。譯碼過程中每一步處理操作如下：從預處理集中選出一個原始數據分組，將該分組與E個編碼分組中尚未被釋放的且和它相關的所有分組進行異或運算，所有參加異或運算的編碼分組度數減1，異或之后度數變?yōu)?的編碼分組被釋放，所對應的原始數據分組被恢復出來并加到預處理集當中。剛剛處理的原始數據分組從預處理集當中剔出，而處理之后新恢復的原始數據分組如果不在預處理集當中，則這些分組就會引起預處理集的增長，反之，則不會引起預處理集的增長。當預處理集為空時，即沒有可以被處理的原始數據分組時，此過程結束。譯碼失敗是指在所有的原始數據分組被恢復出來之前預處理集就已經變空。

定義 2度分布函數：對于所有的度 d，度分布函數ρ(d)是編碼分組度數為d的概率。

定義3編碼分組釋放概率∶ q(i,L)表示度數為i的編碼分組在還有L個原始數據分組未被處理時被釋放的概率。

定理1編碼分組釋放概率如下：i和L為其他 (1)

定理1的證明參見文獻[4]。

定義4編碼分組總釋放概率：r(i,L)表示在還有L個原始數據分組未被處理時度數為i的編碼分組被選中并被釋放的概率，即r(i,L)= ρ(i)q(i,L)。r(L)表示還有L個原始數據分組未被處理時一個編碼分

定義5理想孤立子度分布函數：

定理 2對于理想孤立子度分布函數，編碼分組總釋放概率，對于L=1, 2,…, k中所有的值都成立。

定理2的證明參見文獻[4]。

采用理想孤立子度分布函數的 LT碼每個編碼分組在每一步被釋放的概率為 1/k，當編碼分組的數目E=k時，每一步平均釋放一個編碼分組，即每處理完預處理集中的一個原始數據分組后，剛釋放的編碼分組所對應的原始數據分組就會增加到預處理集當中，使預處理集的大小保持為 1，經過 k步處理后，k個編碼分組都被釋放，k個原始數據分組均被恢復。但上面的過程都是基于均值進行分析的，實際應用中會出現(xiàn)波動，常常在所有原始數據分組被恢復出之前預處理集就會變空。因此采用理想孤立子分布函數的LT碼用k個編碼分組恢復出k個原始數據分組的成功概率極小，正確恢復出所有的原始數據分組通常所需要的編碼分組的數目要遠遠大于k。

針對理想孤立子分布函數存在的問題，文獻[4]通過增加預處理集的初始大小來減小實際應用中譯碼失敗的概率，并給出了健壯孤立子度分布函數。

定義6健壯孤立子度分布函數：設預處理集的初始大小為R+1，定義

把 τ(i)與理想孤立子度分布函數 ρ(i)相加并作歸一化處理，就得到健壯孤立子度分布函數μ(i)，即

基于健壯孤立子度分布函數的傳統(tǒng) LT碼，其恢復出所有原始數據分組所需要編碼分組的數目仍然偏大，且多次實驗結果存在較大的波動。

4 改進型LT碼

本節(jié)將對 LT碼的度分布算法進行改進，提出基于實用的次優(yōu)度分布算法的改進型LT碼。

4.1 最優(yōu)度分布算法

本節(jié)將對 LT碼的譯碼過程進行分析，找出最優(yōu)度分布算法。

預處理集的大小設為R+1，在還有L個原始數據分組未被處理時，為了保證預處理集的大小不變，在處理完第k-L個原始數據分組后，需要一個新的原始數據分組增加到預處理集中。一個被釋放的編碼分組所對應的原始數據分組不落在原來的預處理集中的概率為(L-R)/L，因此為了增加一個新的原始數據分組到預處理集中，平均需要釋放L/(L-R)個編碼分組。

設編碼分組度數為i的概率是ρ(i)，根據定義4，在還有L個原始數據分組未被處理時，一個編碼分組被釋放的概率為

假設一共有E個編碼分組，則第k-L步處理后平均釋放的編碼分組的數目為

根據上面的分析，第k-L步處理平均需要釋放L/(L-R)個編碼分組，因此

剛開始需要保證預處理集的大小為R+1，因此編碼分組度數為1的概率

將式(1)和式(7)結合起來，再令 n(i)=Eρ(i)，可以得到：

將式(9)用矩陣形式表示

上面等式的系數矩陣可由式(1)求得，且其為下三角矩陣，從而可以求出n(i),i=2,3,…,k-R。

度數為1到k-R之間的所有編碼分組的數目之和為E，即

可以得出E的值。

因此由式(8)、式(10)和式(11)可以得出最優(yōu)度分布函數：

在實際應用中，當原始數據分組的數目k較大時，式(10)中系數矩陣對角線上大部分元素的值都非常小，系數矩陣的行列式近似為 0，矩陣呈現(xiàn)病態(tài)，基于運算能力的限制，常規(guī)方法無法求出變量n(i)，因此最優(yōu)度分布算法理論上可解，但不實用。

4.2 次優(yōu)度分布算法

本節(jié)將在最優(yōu)度分布算法的基礎上提出實用的次優(yōu)度分布算法。

譯碼過程中預處理集的大小仍設為R+1，在處理第k-L個原始數據分組時，為了保證預處理集的大小不變，平均需要釋放 L/(L-R)個編碼分組，即式(7)仍然成立。

由文獻[4]中對理想孤立子分布函數的分析可知

根據式(13)，當還有L個原始數據分組未被處理時，若

則式(7)成立。

式(14)存在的問題是在譯碼過程中隨著L的變化，ρ(i)需要取不同的值，但在實際應用中對于整個編譯碼的設計，ρ(i)的值是固定的，因此對式(14)中不同的L得出的ρ(i)取平均得到

為了保證預處理集的初始大小為R+1，

在處理完第k-R個原始數據分組時，由于譯碼過程的隨機效應，剩下的未被處理的R個原始數據分組并不一定都在預處理集中。在經典的小球扔盒子的模型[8]中，將小球以相等的概率扔到R個盒子中的任意一個盒子，最終為了保證每個盒子中都有小球的概率大于 1-δ，約需要 Rln(R/δ)個小球。為使剩下的 R個分組都能以大于 1-δ的概率恢復出來，令度數為k-R+1的編碼分組的數目為Rln(R/δ)/(k-R+1)，因此

所有度的概率之和為1，即

根據式(15)～式(18)可以求出所需編碼分組的數目E。

綜合式(15)～式(17)，即可得到 LT碼的次優(yōu)度分布函數。

改進型 LT碼則根據次優(yōu)度分布算法決定每個編碼分組的度，進而隨機選取相應數量的原始數據分組進行編碼。

5 性能仿真與分析

本文通過信道利用率來衡量改進型LT碼對衛(wèi)星數據廣播分發(fā)系統(tǒng)分發(fā)性能的影響，并將其與基于健壯孤立子度分布函數的傳統(tǒng)LT碼、RSE碼以及不采用分組級FEC技術時系統(tǒng)的性能進行比較。

定義7 信道利用率：信道利用率e表示原始數據分組數目k與為完成譯碼而發(fā)送的編碼分組數目S的比值，即e=k/S。

本節(jié)在局域網環(huán)境下仿真衛(wèi)星數據廣播分發(fā)系統(tǒng)，利用局域網中的服務器充當分發(fā)系統(tǒng)的分發(fā)中心，5臺客戶機分別充當分發(fā)系統(tǒng)中的5臺接收機。為了模擬信道特性異構的網絡環(huán)境，5臺接收機的分組出錯概率分別設為0.05、0.1、0.15、0.2和0.25。原始數據選用 350Kbyte的文件，分組長度設為512byte。對于傳統(tǒng)LT碼和改進型LT碼，預處理集的大小設定參見文獻[9]， R = a + b4k ，其中 a 、b的確定則根據對仿真結果的比較選擇一組較優(yōu)的值，在本文的仿真中a=2，b=8。對于RSE碼，編碼碼率設為（5，10）。為了克服突發(fā)錯的影響，先對所有碼組中的 R SE編碼分組進行交織編碼然后發(fā)送。在不采用分組級 F EC技術時，同樣為了克服突發(fā)錯，將源文件分為多個文件塊，塊大小與采用 R SE碼時碼組大小相同，設為5個分組，然后對所有文件塊中的原始數據分組進行交織編碼，再發(fā)送出去。對采用改進型LT碼、傳統(tǒng)LT碼、RSE碼以及不采用分組級FEC技術4種情形下系統(tǒng)的信道利用率分別仿真200次，計算出200次仿真得出的信道利用率的均值，并以該參數作為指標來衡量系統(tǒng)的分發(fā)性能。

從圖3的仿真結果可以看出，對于分組出錯概率不同的5個接收機，分組出錯概率越高，信道利用率越低。對于所有的接收機而言，信道利用率從高到低依次為改進型LT碼、傳統(tǒng)LT碼、RSE碼，不采用分組級FEC時性能最差。

分組級 FEC技術通過引入冗余分組和增強發(fā)送分組之間的相關性來提高系統(tǒng)的糾錯能力，從而減小重發(fā)概率，提高系統(tǒng)的信道利用率。因此圖 3中2種LT碼和RSE碼的性能要優(yōu)于不采用分組級FEC時的性能。

圖3 分組出錯概率不同的接收機對應的信道利用率

改進型LT碼的性能優(yōu)于傳統(tǒng)LT碼，是因為傳統(tǒng)LT碼在分析譯碼過程時進行了較大程度的近似。在還有L個原始數據分組未被處理時，度數為 k/L的編碼分組被釋放的概率最大[10]，因此在第k-L步處理中只對度數i=k/L的編碼分組進行分析，再將得出的結果推廣到所有的i；而改進型LT碼采用的次優(yōu)度分布函數基于最優(yōu)度分布函數，在分析 LT碼的譯碼過程時相對更加精確，因此性能更優(yōu)。

下面分析2種LT碼的性能均優(yōu)于RSE碼的原因。RSE碼的編譯碼時延與碼組大小的平方成正比，為了減小譯碼時延，碼組不能設得很大，因此一個文件需要分為多個碼組。在接收端，一部分碼組正確譯碼，另一部分碼組由于分組出錯沒能完成譯碼，需要繼續(xù)接收編碼分組，而已經完成譯碼的碼組就會收到屬于該碼組的但對譯碼無用的分組，降低了信道利用率。LT碼的編譯碼時延與碼組大小呈近似線性關系，碼組可以遠遠大于 RSE碼的碼組； LT碼采用了隨機編碼的思想，接收端收到的每一個編碼分組幾乎都能提供有用的譯碼信息，接收端只要收到稍多于原始數據分組的編碼分組就能正確恢復出所有的原始數據分組，因此系統(tǒng)的信道利用率更加接近于理論上的極限值。

接下來對不同分組長度對應的數據分發(fā)性能進行仿真。以分組出錯概率為0.1的接收機為例，分組長度l分別設為256byte、512byte和1 024byte。每個仿真做200次，統(tǒng)計平均信道利用率。仿真結果如圖4所示。

圖4 不同分組長度對應的信道利用率

從仿真結果可以看出，對于同一個分發(fā)文件，當分組長度增加時，原始數據分組的數目就會減少，改進型LT碼和傳統(tǒng)LT碼對應的信道利用率會隨之降低，而采用RSE碼和不采用分組級FEC技術時對應的信道利用率會隨之增大，下面給出2種不同趨勢的原因。當原始數據分組的數目減少時，采用隨機編碼思想的LT碼隨機性下降，隨機產生的編碼分組含有相同信息的概率就會增大，因此信道利用率會隨分組長度的增加呈下降趨勢。對于采用RSE碼以及不采用分組級FEC技術而言，由于對源文件都采用了分塊處理，當每個碼組的分組數目固定時，原始數據分組數目的減少會導致碼組數目的減少。當某個碼組沒有接收到足夠多的分組而繼續(xù)接收時，其他碼組接收到的無用分組就會變少，因此信道利用率會隨著分組長度的增加呈上升趨勢。

最后，本文還比較了改進型LT碼、傳統(tǒng)LT碼和RSE碼的譯碼時間，仿真結果如圖5所示。從圖中可以看出，改進型LT碼與傳統(tǒng)LT碼的譯碼時間相近，并遠遠小于RSE碼。RSE碼采用復雜的矩陣運算，編譯碼復雜度與碼組中包含的分組數目的平方成正比，因此譯碼時間很長。改進型 LT碼和傳統(tǒng)LT碼均是基于簡單的異或運算，運算復雜度低，譯碼時間短，如本文仿真中2種LT碼的譯碼時間都只有250ms左右。

圖5 3種分組級FEC的譯碼時間對比

6 結束語

分組級 FEC層能夠在網絡層上有效解決異構網絡中存在的分組成功分發(fā)概率低、時延大、信道利用率低等問題。噴泉碼中的 LT碼是一項適合在分組級 FEC層上采用的技術，度分布算法是影響

LT碼性能好壞的關鍵。本文通過研究，理論上可解但實際中不可用的 LT碼最優(yōu)度分布算法，提出了實用的次優(yōu)度分布算法，并將基于次優(yōu)度分布算法的改進型LT碼應用于衛(wèi)星數據廣播分發(fā)系統(tǒng)，考察其對分發(fā)系統(tǒng)信道利用率的影響。仿真結果表明，本文提出的改進型 LT碼譯碼復雜度低，將其應用于衛(wèi)星數據廣播分發(fā)系統(tǒng)，系統(tǒng)的信道利用率要優(yōu)于傳統(tǒng)LT碼，且遠遠好于采用RSE碼和不采用分組級FEC技術時的信道利用率。研究結果為基于LT碼的Raptor碼[5]的性能改進奠定了基礎，對提高衛(wèi)星數據廣播分發(fā)系統(tǒng)的信道利用率具有重要的實用價值。

[1] 張更新, 張有志, 周坡. 衛(wèi)星數據分發(fā)系統(tǒng)中的分組級FEC技術性能分析[J]. 電子與信息學報,2006, 28(1)∶112-115.ZHANG G X, ZHANG Y Z, ZHOU P. Performance analyse of packet level FEC in satellite data distribution system[J]. Journal of Electronics and Information Technology, 2006, 28(1)∶ 112-115.

Processing Advances in Wireless Communications (SPAWC)[C].Cesme, Turkey, 2012. 545-549.

[17] 張賢達. 矩陣分析與應用[M]. 北京∶ 清華大學出版社, 2004.ZHANG X D. Matrix Analysis and Application[M]. Beijing∶ Tsinghua University Press, 2004.