分布式無標度LT碼*

李騰飛,蘇偉偉,文 紅

(電子科技大學通信抗干擾國家級重點實驗室,四川成都611731)

分布式無標度LT碼*

李騰飛,蘇偉偉,文 紅

(電子科技大學通信抗干擾國家級重點實驗室,四川成都611731)

LT碼是噴泉碼的一種,在刪除信道中性能優越,分布式噴泉碼多信源多中繼的特性適合用于深空通信中。無標度網絡(SF network)具有平均路徑(APL)長最小的特性,非常適合噴泉碼的度分布設計需求。首先介紹了LT碼的編譯碼算法,然后對無標度網絡和基于無標度網絡的SF-LT碼度分布設計進行了詳細分析和優化,最后在刪除信道條件下,選取碼長較短、刪除概率較小的情形對分布式二信源SF-LT碼進行仿真分析,仿真結果表明,與LT碼相比,分布式SF-LT碼具有更好的性能。

噴泉碼 LT碼 分布式SF-LT碼

0 引 言

LT碼[1]是噴泉碼[2-3]的一種,度分布是其構造的關鍵,LT碼節點間平均路徑(APL)長度越短代表其譯碼效率越高,無標度網絡平均路徑長最小的特性,非常適合LT碼節點度分度設計的需求,對于固定的節點數和平均路徑長,無標度網絡可以提供最小的連線數目。本文將復雜網絡的無標度特性應用在LT碼的度分布設計中,設計一類網絡結構具有無標度特性的SF-LT碼,然后根據深空通信載體資源受限的特性,設計更具實用性的分布式SF-LT碼,最后在碼長500,刪除概率0.05的刪除信道條件下對SF-LT碼和分布式二信源SF-LT碼的譯碼性能進行仿真驗證,證明了分布式SF-LT碼比LT碼具有更好的性能。

LT碼是一種由K個源數據包根據自身的度分布進行編碼而生成的,而接收端只要接收到N(N稍大于K)個編碼數據包就可以高概率地譯碼,LT碼自身的度分布決定了其譯碼性能,度是指與該編碼包相連的源數據包數目,LT碼度分布用S(d)表示,其意義在于:對于所有的度d,編碼分組出現度為d的概率為S(d)。

LT碼的編碼就是根據度分布函數S(d),從k個數據包中隨機地選取d個源數據包,然后將這d個源數據包進行模二加,生成一個編碼數據包。

LT碼的譯碼過程為:找到一個度為1的編碼符號tn,令與之相連的源數據包sk=tn,然后將sk與所有和sk有聯系的編碼數據包進行異或,最后刪除所有與sk相連的編碼數據包。不斷重復上述過程,直到找不到度為1的編碼數據包。如果存在這樣的數據包,表明沒有全部譯碼。

1 LT碼無標度網絡

1.1 無標度網絡

網絡可以表示為G=(V,E),其中V表示給定點集,E表示邊集。點集中的元素稱為節點,節點間的連接稱為邊[4]。節點i的度ki定義為與節點i相連的邊數。定義網絡的平均路徑(APL)長度L為網絡中任意兩個節點間距離的平均值,也稱為網絡的特征路徑長度,

式中,N為網絡節點數,dij為網絡中節點i與節點j之間連通的最小邊數,也稱為節點對(i,j)之間的距離。

無標度網絡是目前較為常見的網絡結構之一,具有特殊拓撲結構,它的度分布服從冪方律分布,在給定規模的通信網絡中,無標度網絡的平均路徑長最小[5],典型的BA(Barabási-Albert)無標度網絡模型的構造算法如下[6]:

1)初始:開始給定一個有m0個節點的網絡。

2)增長:在每個時間步重復增加一個帶有m條邊的新節點,并且按照步驟3)中的擇優概率選擇m個節點與新節點相連,其中m＜m0。

3)擇優連接:按照擇優概率:

選擇舊節點i與新節點相連,其中ki是舊節點i的度。

經過t個時間步后,生成一個有t+m0個節點和mt條邊的BA無標度網絡。

1.2 LT碼無標度網絡模型

首先從一個簡單的譯碼例子出發,圖1為LT碼的編碼tanner圖。

圖1 輸入數據包為10的LT碼的編碼Tanner圖Fig.1 Tanner graph of LT code which the input data packet is 10

si代表源數據包,ci代表編碼數據包。LT碼的譯碼過程是一個消息傳遞的過程。信息的傳輸依賴于Tanner圖中的節點連線。用一個網絡模型表示圖1,網絡節點表示編碼數據包ci,節點之間的連線遵循以下規則:如果兩個編碼數據包在Tanner圖中與同一個源數據包si相連,在網絡模型中這兩個節點之間相連。圖2為圖1匹配的網絡模型。

圖2 圖1所生成的將原始數據包節點移除的復雜網絡Fig.2 Complex network figure 1 generation which the original packet removed

在譯碼端,譯碼“信息”從度為1的節點開始,沿著圖2中的連線將信息傳輸給與之相鄰的節點,然后從圖2網絡中去除與之關聯的邊,不斷重復上述過程,直到網絡中不存在度為1的節點。如果圖2中的網絡節點關聯了所有源數據包,在譯碼端可以成功譯碼。

圖2中,兩個節點間的路徑長度代表著“譯碼信息”從一個節點更新到另一個節點的更新操作的次數。在一個給定規模的網絡中,節點間平均路徑(APL)越短,譯碼成功的概率越高,同時譯碼效率越高,基于無標度網絡的平均路徑長最小的特性,可以將無標度網絡引入LT碼度分布的設計中,構造一類網絡結構具有無標度特性的LT碼——SF-LT碼,同時根據深空通信載體資源受限的特性,可以將SF-LT碼引入分布式系統中,設計更具實用性的分布式SF-LT碼。無標度網絡的度分布有著冪方律特性,節點的度分布是λ(d)=Ad-γ,其中d是節點的度,λ是冪指數參數,A是使得∑dλ(d)=1的歸一化參數。由于圖2映射到的編碼數據包和原始數據tanner圖并不是唯一的,所以要對度分布進行一定的改進。定義修正后的冪律分度為[7-8]:

式中,參數P1為度為1的編碼數據包概率,r為衰減因子,A為歸一化因子。

考慮到由式(3)構造的度分布,度高的編碼數據包的數量很少,會導致在接收編碼數據包較多的情況下譯碼性能降低,魯棒孤波分布(RSD)在接收編碼數據包較多的情況下可以高概率地譯碼[1],可以考慮將二者進行有效的結合,由此定義SF-LT碼的度分布,采用將無標度分布與魯棒分布相結合的方法,具體實現方法如下:

理想的孤波度分布ρ(·):

體現其魯棒性的分布τ(·):

式中,參數R=c·ln(k/σ)·,R則代表度為1編碼數據包在整個編碼數據包中的平均個數,參數σ表示接收到n個編碼數據包后譯碼失敗的概率。參數0＜c＜1,SF-LT碼度分布μ(·)是理想孤波分布ρ(·)、子分布τ(·)和無標度分布λ(i)和的概率歸一化結果,這樣的結合使得其既有無標度特性又對實際信道有良好的適應性,最后SF-LT碼度分布μ(i)定義為:

雖然SF-LT碼子分布τ(i)在形式上與LT碼的RSD子分布相同,但由于受無標度網絡冪律分布影響,子分布參數選擇可能需要調整。不同信道條件下,μ(i)子分布對于譯碼性能的影響程度不同,例如在低刪除概率條件下,接近于理想信道,子分布ρ(·)對譯碼性能的影響程度最高,因為在理想信道條件下,ρ(·)的譯碼性能最好[1],因此,根據實際信道狀況可以通過仿真測試對ρ(i)、τ(i)、λ(i)選取適當的權重系數x1、x2、x3對μ(i)進行優化,相應的,,通過這種方法使其譯碼性能達到較好的效果。

2 兩信源分布式SF-LT碼

深空通信中,通信實體距離遙遠,資源受限,傳播損耗較大,為了保證通信質量,在設計通信設備時有更高的要求,分布式噴泉碼多信源多中繼的特性,非常適合用于深空通信中,兩信源單中繼分布式通信系統模型如圖3所示。

圖3 兩信源單中繼分布式通信系統模型Fig.3 Model of two source and single relay communication system

2.1 分布式兩信源SF-LT碼度分布

考慮分布式兩信源情況,如圖3所示,信源s1和信源s2分別獨立發送k/2個數據包,我們的目標是選擇度分布p(·)使得中繼R到目的節點D的數據傳送服從SF-LT碼度分布μ(i)。

為了求出p(·)需要進行解卷積運算,若k≥2,求SF-LT碼度分布的解卷積按如下進行[9]:直接解卷積很復雜,而且還存在很多問題,例如,解出的p(k/s)可能為負值,類似于分布式LT碼的度分布構造方法[9],把μ(·)分布分解并做標準化處理,首先把μ(·)分解為兩個分布μ′(·)和μ″(·)的線性組合:

現在,定義新的函數:

可以計算出:

SF-LT碼的參數優化方案同樣適用于分布式系統,針對實際的信道條件,可以考慮為μ(i)的子分布分配不同的權重系數,提升分布式SF-LT碼的譯碼性能。

2.2 分布式兩信源SF-LT碼的編譯碼過程

編碼的第一步:圖3中的兩信源發送的數據X1和X2按照度分布p(·)各自獨立進行LT編碼,由

式中,于p(·)是f(·)、μ″(·)和參數λ的組合,我們可以認為某個數據包的度d的產生是以概率λ按照度分布f(·)產生或者以概率1-λ按照度分布μ″(·)產生。編碼的第二步:信源s1和s2編碼后形成的數據包在中繼需要進行處理操作,由于中繼知道兩個信源的度分布,處理方法如下:

1)如果兩個信源發出的數據包的度d都是以概率λ按照度分布f(·)產生,則在中繼進行異或后傳輸到目的節點。

2)如果某個信源發出的數據包的度d是以概率1-λ按照度分布μ″(·)產生,則中繼將該信源的數據包傳輸到目的節點,丟棄另外一個信源的數據包。

3)如果某個信源發出的數據包的度d都是以概率1-λ按照度分布μ″(·)產生,則中繼就隨機選取某個信源發生的數據包傳輸到目的節點。

具體實現方法如下:中繼按下式產生二元變量b1和b2:

式中,di表示d1和d2,分別是X1和X2的度,Ui表示U1和U2,是中繼節點產生的兩個獨立隨機變量,兩變量U1,U2在區間[0,1]服從均勻分布。然后中繼經過如下處理后發送到目的節點。

式中,flip(X1,X2)表示以相同的概率隨機取X1或X2的值。

數據包從中繼到目的節點的傳送服從SF-LT碼度分布,目的節點的數據包譯碼過程與LT碼的譯碼一樣。

3 分布式SF-LT碼性能仿真

本文在刪除信道模型下,選取刪除概率q= 0.05,源數據包(LT碼)長度K=1 000,以接收一定數目編碼包條件下,譯碼端的譯碼成功率為評價準則,對分布式SF-LT碼進行性能仿真,其中,LT碼選用度分布參數為c=0.05,δ=0.5,受無標度特性冪律分布的影響,SF-LT碼選用度分布參數為c= 0.02,δ=0.5。

LT碼與3種不同系數SF-LT碼的性能仿真結果比較如圖4所示。3種SF-LT碼均選擇參數P1= 0.08,r=2.1,其中,SF-LT碼選擇系數x1=0、x2=0、x3=1,SF-LT碼1選擇系數x1=0、x2=1、x3=1,SFLT碼2選擇系數x1=1、x2=1、x3=1,由仿真結果可以看到:SF-LT碼在接收數據包較少的情況下譯碼性能比LT碼好很多,但隨著譯碼端接收數據包的增多,SF-LT碼的譯碼性能開始下降,譯碼成功率低于LT碼,但此時SF-LT碼1和SF-LT碼2的譯碼性能依然高于LT碼,這是因為經過優化后的度分布既有無標度特性又保證了度高編碼包的數目,SF -LT碼2的譯碼性能最好。

圖4 碼長為1 000的4種LT碼的性能比較Fig.4 Performance comparison of four kinds of LT codes which length is 1 000

對SF-LT碼進行參數優化,因為仿真選用的是低刪除概率,對子分布ρ(·)分配較大的權重系數,參數選擇如表1所示。仿真結果如圖5所示,由仿真結果可以得知:通過適當的改變參數,可以得到性能較好的SF-LT碼。

表1 不同種類SF-LT碼參數選擇Table 1 Parameters choice of different types of SF-LT code

圖5 碼長為1 000的4種SF-LT碼的性能比較Fig.5 Performance comparison of four kinds of SF-LT codes which length is 1 000

在兩信源情況下,4種編碼性能仿真結果比較如圖6所示。其中,兩種SF-LT碼均選擇系數x1= 1、x2=1、x3=1,參數選擇P1=0.08,r=2.1,由仿真結果看到:SF-LT碼的譯碼性能優于LT碼,分布式SF-LT碼在接收數據包較少的情況下,譯碼性能最好,隨著接收數據包數目的增多,與分布式LT碼相比,譯碼性能雖然有所下降,但仍保持較高的譯碼成功率。整體而言,分布式SF-LT碼的譯碼性能優于LT碼,與LT碼相比,在載體資源受限的深空通信系統中,分布式SF-LT碼更具實用價值。

圖6 碼長為1 000的LT碼、SF-LT碼的性能比較Fig.6 Performance comparison of LT codes and SF-LT codes which length is 1 000

4 結 語

本文分析了SF-LT碼和兩信源分布式SF-LT碼各自的度分布實現和編譯碼方法,并對刪除概率較小、短碼長的SF-LT碼和兩信源分布式SF-LT碼進行了仿真分析,仿真結果表明,與LT碼相比,分布式SF-LT碼具有更好的性能,在深空通信中更具實用價值,本文的結果還為SF-LT碼技術的應用提供了很好的參數選擇依據。

[1] LUBY M.LT Codes[C]//Foundations of Computer Science.United States:IEEE press,2002:271-280.

[2] 楊玲,宋時立,劉國超,等.LT碼的性能分析及仿真[J].通信技術,2012,45(05):1-3.

YANG ling,SONG Shi-li,LIU Guo-chao,et al.The Performance of LT Codes Analysis and Simulation[J].Communications Technology,2012,45(05):1-3.

[3] 劉國超,陳霄,蘇偉偉,等.短長度分布式噴泉碼的性能分析[J].通信技術,2012,45(08):5-8.

LIU Guo-chao,CHEN Xiao,SU Wei-wei,et al.The Performance of Short Length of Distributed LT Codes[J]. Communications Technology,2012,45(08):5-8.

[4] 汪小帆,李翔,陳關榮.復雜網絡理論及其應用[M].北京:清華大學出版社,2006:3-33.

WANG Xiao-fan,LI Xiang,CHEN Guan-rong.Complex Network Theory and Its Application[M].Version 1.Beijing:Tsinghua University Press,2006:3-33.

[5] BOLLOBáS B,RIORDAN O.Robustness and Vulnerability of Scale-free Random Graphs[J].Internet Math, 2003,1(01):1-35.

[6] BARABáSI A.L,ALBERT R.Emergence of Scaling in Random Networks[J].Science,1999,286(5439):509-512.

[7] HYYTI? E,TIRRONEN T,VIRTAMO J.Optimizing the Degree Distribution of LT Codes with an Importance Sampling Approach[C]//6th International Workshop on Rare Event Simulation.Bamberg:RESIM press,2006:64-73.

[8] CHEN C M,CHEN Y,SHEN T C,et al.Optimizing Degree Distributions in LT Codes by Using the Multiobjective Evolutionary Algorithmbased on Decomposition [C]//Evolutionary Computation(CEC),2010 IEEE Congress on.Shanghai:IEEE press,2010:1-8.

[9] PUDUCHERI S,KLIEWER J,FUJA T E.Didtributed LT Codes[C]//2006 IEEE International Symposium on Information Theory.United States:IEEE press,2006:987-991.

LI Teng-fei(1988-),male,M.Sci., majoring in channel coding,image processing.

蘇偉偉(1988—),男,碩士,主要研究方向為信道編碼;

SU Wei-wei(1988-),male,M.Sci.,majoring in channel coding.

文 紅(1969—),女,博士,教授,主要研究方向為編碼原理與技術、密碼學、信號處理、網絡安全通信。

WEN Hong(1969-),female,Ph.D.,professor,mainly working at coding theory and technology,cryptography,signal processing and network communication security.

Distributed Scale-free LT Codes

LI Teng-fei,SU Wei-wei,WEN Hong
National Key Lab of Communication of UESTC,Chengdu Sichuan 611731,China;

LT code is one of the fountain codes which performs well in erasure channel.The characteristics of multi sources and multi relays make distributed fountain codes fit for deep space communications.Scale -free network has the characteristic of the minimum average path length which makes it perfect for the design requirement of degree distribution in fountain codes.The encoding and decoding algorithm of LT codes is introduced in this paper first,then the design of degree distribution in scale-free networks and SF-LT codes based on the scale-free network is analyzed and optimized.At last,under the condition of erasure channel,the simulation of SF-LT codes with distributed binary sources under shorter code length and lower erasure probability is done.The result shows that distributed SF-LT codes have better performance than LT codes.

fountain codes,LT codes,distributed SF-LT codes

TN911.22

A

1002-0802(2014)08-0854-06

10.3969/j.issn.1002-0802.2014.08.003

李騰飛(1988—),男,碩士,主要研究方向信道編碼、圖像處理;

2014-05-20;

2014-07-03 Received date：2014-05-20;Revised date：2014-07-03

國家自然科學基金項目(No.61032003,No.61271172);高等學校博士學科點專項科研基金(No.20120185110030, No.20130185130002)和四川省國際合作研究項目(No.2013HH0005)聯合資助

Foundation Item:NSFC(No.61032003,61271172),RFDP(No.20120185110030,No.20130185130002),Sichuan International Corporation Project(No.2013HH0005)and SRF for ROCS,SEM.