LT碼度分布改進及在認知無線電鏈路保持中的應(yīng)用

易本順，姚渭箐

（1. 武漢大學電子信息學院，湖北 武漢 430072；2. 武漢大學深圳研究院，廣東 深圳 518057；3. 國網(wǎng)湖北省電力有限公司信息通信公司，湖北 武漢 430077）

1 引言

認知無線電作為一種有效的技術(shù)用于解決頻譜資源短缺的問題。次用戶可以機會式接入主用戶暫未使用的信道[1]，當主用戶突然出現(xiàn)時，次用戶數(shù)據(jù)通信被強制中斷，需要重構(gòu)它們的通信鏈路。這不僅耗時，而且會降低次用戶系統(tǒng)的性能。

Willkomm 等[2]首次提出認知無線電系統(tǒng)的次用戶鏈路保持模型，并采用基于冗余糾錯碼[3]LT碼實現(xiàn)對主用戶干擾的補償，隨后Yue等[4,5]進行了進一步研究。在該模型的基礎(chǔ)上，本文提出一種適用于認知無線電系統(tǒng)的次用戶鏈路保持的新型LT碼度分布設(shè)計方法。其核心思路是將譯碼開銷較小時具有高譯碼成功率的度分布與譯碼開銷較大時具有高譯碼成功率的頑健孤子分布結(jié)合在一起來構(gòu)建新型度分布。首先，對經(jīng)典的泊松分布（PD,Poisson distribution）函數(shù)進行局部改進，并基于 PD的數(shù)學特性以及平均度數(shù)，推導出λ參數(shù)的最優(yōu)值；然后，基于LT碼的期望可譯集以及次用戶鏈路的有效吞吐量與 LT碼度分布的相關(guān)性，構(gòu)建雙層優(yōu)化目標，采用雙層尋優(yōu)算法（THOA,two-layer hierarchical optimization algorithm）作為尋優(yōu)工具在IPD與RSD間進行尋優(yōu)。將改進的LT碼作為信道編碼應(yīng)用于認知無線電鏈路保持中，能最大限度地降低誤比特率（BER,bit error rate），同時從一定程度上提高了次用戶鏈路的有效吞吐量。

2 次用戶鏈路保持模型

在基于 LT碼的認知無線電次用戶鏈路保持模型[4,5]中，發(fā)送端將長度為k×lbit的原始數(shù)據(jù)均分為k個輸入分組；接著，編碼器對k個輸入分組進行LT編碼生成N=k+K個編碼分組，其中，K為冗余編碼分組的數(shù)量；隨后，這N個編碼分組通過次用戶鏈路的N個并行子信道發(fā)送給接收端，即一個子信道傳輸一個編碼分組。接收端接收到任意略大于k且小于N個編碼分組，接收端的譯碼器便能完全恢復k個輸入分組，而不需要關(guān)心是哪些編碼分組用于譯碼。

如圖 1所示，次用戶通信的幀結(jié)構(gòu)(tframe)被分為4個部分：感知時間段(tsens)、控制時間段(tcontrol)、獲取時間段(tacquire)和數(shù)據(jù)傳輸時間段(tdata)。其中，tsens、tcontrol和tacquire一起構(gòu)成鏈路保持時間。在tsens中，通過頻譜感知確定未被主用戶使用的子信道。在tcontrol中，發(fā)送端和接收端之間互換感知結(jié)果，并達成共識，決定哪些子信道必須排除，而哪些子信道則可以用來通信。tacquire為獲取新子信道所需的時間。tdata為信息在當前次用戶鏈路上的傳輸時長。

假設(shè)所有子信道干擾概率都是相等的，并且不同子信道的干擾概率是獨立的。同樣，對于連續(xù)的時間幀，子信道干擾概率也是獨立的。

定義ne表示解調(diào)和譯碼后丟失的數(shù)據(jù)分組，Pne表示丟失ne個數(shù)據(jù)分組的概率，E表示譯碼失敗事件。由于當ne＞K時，信息錯誤概率為1，于是得到LT碼的總信息錯誤概率[4]為

圖1 次用戶通信的幀結(jié)構(gòu)

定義pI為子信道總干擾概率，表示為

其中，pPU為主用戶的干擾概率，pa為信道質(zhì)量較差時譯碼失敗概率。

Pne表示為

定義Ndec為k×lbit的數(shù)據(jù)信息完全成功譯出所需的比特數(shù)量，于是得到

定義Pa為次用戶鏈路保持的概率，即在上一個幀內(nèi)，正在被次用戶鏈路使用的子信道中，至少一個被主用戶占用從而需要重新獲取子信道的概率。根據(jù)式(3)，Pa可表示為

根據(jù)式(5)，時間幀的平均長度可表示為

從而得到平均有效吞吐量為

其中，bsc為子信道的比特率。

3 LT碼原理

3.1 LT碼編譯碼過程

LT碼的編碼過程非常簡單，具體步驟如下。

Step1 從度分布中隨機選擇一個度d。

Step2 隨機且均勻地選取d個原始分組。

Step3 將這d個輸入分組進行異或（XOR）生成一個編碼分組。

通常，LT碼采用BP算法進行譯碼，具體步驟如下。

Step1 度數(shù)為1（d= 1）的編碼分組直接譯碼。

Step2 譯出的原始分組與跟其相連的編碼分組進行異或后替代原編碼分組，同時刪除其連接關(guān)系。

Step3 重復步驟Step1和Step2，直至譯碼完成。LT碼編譯碼過程如圖2所示。

圖2 LT碼編譯碼過程

3.2 LT碼經(jīng)典度分布

其中，Ωd是一個編碼分組選取度數(shù)為d的概率，并

LT過程的隨機行為完全取決于度分布Ωd，編碼分組數(shù)量N以及輸入分組數(shù)量k。一個好的度分布需滿足2個設(shè)計目標。

1) LT過程成功所需的平均編碼分組數(shù)量盡可能少，確保 LT過程成功的編碼數(shù)量對應(yīng)于確保原始數(shù)據(jù)全部恢復的編碼分組數(shù)量。

2) 編碼分組的平均度數(shù)盡可能小，平均度數(shù)是生成一個編碼分組所需的平均 XOR運算次數(shù)。平均度數(shù)乘以N就是恢復原始數(shù)據(jù)所需異或運算的平均次數(shù)。

常見的 LT碼度分布有理想孤子分布（ISD,ideal soliton distribution）和 RSD[3]。

1) 理想孤子度分布

ISD表示的是一種理想情況，即在每次譯碼迭代中，只有一個度為1的編碼分組，并且在每次迭代譯碼之后，只出現(xiàn)一個新的度為1的編碼分組。其度分布函數(shù)為

其中，d為每個編碼分組的度，k為原始分組數(shù)量。

然而，這種度分布的實際性能很差，一個很小的偏差就會導致度為1的編碼分組消失從而造成譯碼終止。

2) 頑健孤子度分布

針對ISD的不足，RSD在度分布函數(shù)中引入2個參數(shù)c和δ，期望度為1的編碼分組數(shù)量在譯碼過程中始終保持為其中，k為原始分組數(shù)量，c為大于0的常數(shù)，δ為譯碼失敗概率。

首先，定義一個函數(shù)

盡管RSD優(yōu)于ISD，但采用RSD進行LT編碼所產(chǎn)生的編碼分組多為度數(shù)較大的編碼分組，在譯碼過程中可能會由于缺少足量度數(shù)較小的編碼分組而導致譯碼中斷。

4 LT碼度分布改進方法

4.1 改進的泊松分布

大量的研究工作證實，一個好的度分布具有某些特征[6]。度分布中某些度數(shù)的比例對LT碼的可譯碼性起主導作用。一個重要特征是度數(shù)為2在度分布中所占比例最高。在 BEC中，為保證譯碼率，需要同時，度數(shù)為1的編碼分組的比例必須要小[8～10]。因此，LT碼可通過調(diào)整這些度數(shù)的比例獲得良好的性能。

基于度分布特性，通過調(diào)整度數(shù)為2的比例對PD進行改進來獲得更高的初始譯碼成功率。改進的泊松分布（IPD,improved Poisson distribution）為

然后，對函數(shù)μd進行歸一化，得到IPD函數(shù)ΩdIPD為

其中，λ是為大于0的常數(shù)。

參數(shù)λ直接影響LT碼的編譯碼過程，因此，有必要為其選擇合適的參數(shù)值。為了滿足一個好的度分布的設(shè)計需要[3]，編碼分組的平均度數(shù)越小越好。IPD和ISD平均度數(shù)的問題可轉(zhuǎn)換為和(式(9))均值的問題。和均值的表達式為

ISD表示的是一種理想情況，即編碼分組進入可譯集的速度與移除的速度相同[3]。理想情況下，λ的參數(shù)值可通過和值相等來推出。均值將會隨k增加而增大?；赑D的數(shù)學特性，當k< 2 0時PD近似于BD[11]。因此，考慮從k=20點推導出λ的參數(shù)值。根據(jù)當k= 2 0時

假設(shè)輸入分組k= 1 000，RSD、PD和IPD度分布函數(shù)的概率分布如圖3所示。得到λ≈3.04。

圖3 RSD、PD和IPD概率分布

為了驗證IPD性能，采用IPD對LT碼進行1 000次編譯碼仿真。當λ選取不同參數(shù)時，IPD成功譯出的輸入分組比率隨譯碼開銷變化情況的仿真結(jié)果如圖4所示，表示譯碼開銷，N為譯碼成功所需編碼分組個數(shù)。很明顯，當λ=3時，IPD具有較好的譯碼性能，隨著譯碼開銷的增加，譯碼成功率一直保持較高的狀態(tài)，甚至可達 90%以上。不足的是，當譯碼開銷較大時，RSD（參數(shù)c=0.1,δ=0.005）的譯碼性能表現(xiàn)更佳，而此時IPD的譯碼成功率上升速度減緩。因此，驗證了IPD在譯碼開銷較小時具有高譯碼成功率的度分布，而 RSD在譯碼開銷較大時具有高譯碼成功率的度分布。

圖4 IPD和RSD的譯碼成功率

4.2 基于兩層遞階優(yōu)化算法的度分布優(yōu)化

為了將IPD和RSD的優(yōu)點進行有機結(jié)合，考慮采用優(yōu)化算法在2種度分布間進行尋優(yōu)得到BER性能更佳的度分布，從而提高認知無線電次用戶鏈路的通信可靠性。同時，優(yōu)化過程中還需要考慮次用戶鏈路的通信可靠性。

改進的度分布優(yōu)化方法基本思路如下。首先，分析LT碼的可譯集和次用戶鏈路的有效吞吐量這2個因素與度分布的關(guān)聯(lián)性來構(gòu)建目標函數(shù)；然后，通過最大化目標值，采用兩層遞階優(yōu)化算法（THOA,two-layer hierarchical optimization algorithm）對度分布進行尋優(yōu)；此外，為提高THOA的全局搜索能力，提出一個搜索算法來動態(tài)調(diào)整搜索域。

4.2.1 2個重要因素與度分布關(guān)聯(lián)性研究

1) 可譯集

LT碼的BER性能是衡量認知無線電次用戶鏈路保持系統(tǒng)的通信可靠性的重要標準。本文通過優(yōu)化度分布來改善BER性能，而LT碼可譯集一定程度上反映度分布與LT碼譯碼性能的相關(guān)性。

可譯集是LT譯碼過程中度為1的編碼分組集合，一定程度上反映譯碼成功率和度分布函數(shù)之間的關(guān)系。在譯碼過程的每一步中，一方面，隨著譯出的原始分組與跟其相連的所有編碼分組之間的連接關(guān)系在 XOR運算后被移除，度數(shù)較高的編碼分組便變成度數(shù)為1的編碼分組，從而進入可譯集；另一方面，度數(shù)為1的編碼分組直接被譯出后便從可譯集中移出。因此，可譯集的大小在譯碼過程中不斷發(fā)生變化。對于一個好的度分布來說，希望產(chǎn)生足夠多的度數(shù)為1的編碼分組的同時，能盡可能降低這種波動幅度。Karp等[12]第一次提出期望可譯集的表達式。

其中，Ω(?)為度分布，k為原始分組數(shù)量，ρ表示成功譯碼的原始分組數(shù)量。表示LT碼譯碼開銷，即次用戶鏈路保持模型中子信道的冗余開銷。

基于上述理論分析，本文通過增大期望可譯集均值并同時降低其方差[13]，即最大化式(17)來獲得優(yōu)化度分布。

其中， α ∈ (0,1)。α過大會降低均值的容忍度。如果α=0，目標則轉(zhuǎn)化為求期望可譯集方差的最大值。通常情況下，將α的取值范圍設(shè)置為0到1之間，本文設(shè)置 α = 0 .25。

2) 有效吞吐量

另外一個重要因素是次用戶鏈路的平均有效吞吐量，用作衡量認知無線電次用戶鏈路保持系統(tǒng)的通信有效性。期望通過優(yōu)化度分布來提高次用戶鏈路的有效吞吐量并降低達到最大有效吞吐量所需的冗余子信道數(shù)量，所以需要找到有效吞吐量與度分布關(guān)聯(lián)性。

根據(jù)LT碼編譯碼原理可知，生成N個編碼分組總共需要進行 N E[Ωd]次異或運算，即編碼分組與輸入分組之間總共存在 N E[Ωd]個連接關(guān)系。在一個隨機編碼過程中，每個輸入分組未參與編碼的概率為因此，可計算出輸入分組的漏選概率為在所有參與編碼的輸入分組全部被譯出的理想情況下，輸入分組的漏選概率即無法避免的譯碼失敗概率，因此，輸入分組的漏選概率直接影響LT碼譯碼性能。將 Pr(E| ne)近似為無法避免的譯碼失敗概率，表達如下。

將式(18)代入式(1)得

基于以上分析，與度分布相關(guān)的有效吞吐量可表示為

其中，

4.2.2 算法設(shè)計

為防止尋優(yōu)過程中搜索結(jié)果超出邊界而為負值，設(shè)計一種動態(tài)搜索算法（DSA,dynamic search algorithm），對尋優(yōu)算法的每一步驟中的搜索域和步長進行動態(tài)調(diào)整，從而提高搜索能力和收斂性能。

DSA算法具體實現(xiàn)步驟如下。

Step1 基于IPD和RSD產(chǎn)生初始度分布，例如，集合大小為m，有k個待優(yōu)化的參數(shù)，即要隨機產(chǎn)生一個k行m列初始度分布集合{Ωj|j=1 ,2,…,m}。每個度分布表示為向量Ω= (Ω1,Ω2,… ,Ωk)，其中d= 1 ,2,3,… ,k。在第一次迭代中，

Step2 每個度分布Ω在Region內(nèi)進行隨機搜索nb個度分布{φi|i= 1 ,2,…,nb}。其中，每個度分布為φ= (φ1,φ2,… ,φk)，每個度數(shù)φd,d= 1 ,2,3,…,k的選取過程可以表示為

Step3 比較這nb個度分布的目標函數(shù)值，選取函數(shù)值最大/小者作為該集合{φi|i= 1 ,2,…,nb}的最優(yōu)值φlocal。

Step4 比較φlocal和Ω的目標函數(shù)值，如果φlocal的目標函數(shù)值大于Ω的目標函數(shù)值，表明φlocal優(yōu)于Ω，則Ω朝φlocal方向前進一步，否則保持不變，該過程可以表示為

其中，Step=0.5Region。

Step5 動態(tài)調(diào)整Region，該過程可以表示如下。

本節(jié)驗證新型LT碼度分布優(yōu)化方法（簡稱為THOA度分布）對于認知無線電次用戶鏈路保持的有效性。將分別從LT碼的誤比特率（BER）性能和次用戶鏈路的有效吞吐量2個方面進行評估。假設(shè)該認知無線電系統(tǒng)模型有N= 1 00個信道，并且添加K個子信道用于保持次用戶鏈路的通信質(zhì)量。將一個長為10 000 bit的原始數(shù)據(jù)信息均分為100個輸入分組。

選取參數(shù)c=0.1和δ=0.5，分別采用RSD和

Step6 如果迭代次數(shù)小于設(shè)定值，轉(zhuǎn)移到步驟Step2；否則，度分布Ω搜索到其局部最優(yōu)度分布Ωglobal。從而得到m個度分布各自的局部最優(yōu)度分布 {Ωjglobal|j=1 ,2,…,m}。

Step7比較 {Ωjglobal|j=1 ,2,…,m}的目標函數(shù)值，得到全局最優(yōu)度分布Ωbest。

設(shè)計THOA算法對度分布進行尋優(yōu)，將LT碼的純理論研究過渡到認知無線電系統(tǒng)的實際應(yīng)用中。主要思路是將搜索過程分為2層結(jié)構(gòu)。首先在IPD和RSD的動態(tài)搜索域中選擇合適的初始度分布集；接著進行第一層尋優(yōu)，基于可譯集特性搜索最優(yōu)度分布；將第一層的優(yōu)化結(jié)果用作第二層的輸入集；隨后進行第二層尋優(yōu)，基于有效吞吐量特性獲得最優(yōu)度分布。THOA算法的過程如下。

Step1 構(gòu)建M個初始度分布集合其中，通過

1,2,3,…,k選取初始集合。

Step3 采用 DSA算法作為尋優(yōu)工具，以最大化式(17)為目標，搜索得到最優(yōu)度分布Ωbest。從而得到這m個分組的最優(yōu)度分布集合

Step4m個組的尋優(yōu)結(jié)果用作第2層的輸入集。

5 實驗仿真

THOA對100個輸入分組進行編碼?；? 000次編譯碼仿真結(jié)果，分析和比較這2種方法的BER。當 K = 3 0、40、50、60時，不同干擾概率下 RSD和THOA的BER比較如圖5所示。

可明顯看出，當冗余子信道的數(shù)量相同時，隨著干擾概率減小，2種方法的BER都逐漸降低。相比RSD、THOA的BER性能始終表現(xiàn)較優(yōu)。如圖5(c)所示，假設(shè)鏈路存在 50個冗余子信道，當pI=0 .01時，THOA的BER僅為 3 .68×1 0-3，明顯低于RSD；而當 pI= 0 .001時，THOA的BER降低到1.87×1 0-3，BER性能依舊優(yōu)于RSD。并且，隨著冗余子信道的數(shù)量增多，即接收端接收較多編碼分組，2種方法的 BER都有明顯降低，THOA的BER性能始終占有絕對優(yōu)勢。例如，在相同干擾概率 pI=0 .001下，當 K = 3 0時，THOA的 BER為2.49×1 0-2，RSD的BER為 3 .26×1 0-1；當 K = 6 0時，THOA的BER降低到 5 .10×1 0-4，RSD的BER為3.11×1 0-3。

圖5 THOA和RSD誤比特率

另一個重要的性能指標是次用戶鏈路的有效吞吐量。文獻[2]證實信息錯誤概率與鏈路保持概率之間存在一個折中。使用更多數(shù)量的冗余并不一定能帶來更大的有效吞吐量。更多數(shù)量的冗余提高了鏈路保持概率，但是卻降低了次用戶鏈路的有效吞吐量。因此，為了獲得可能的最大有效吞吐量，有必要選擇最優(yōu)的冗余子信道數(shù)量。本文假設(shè)每個子信道的

有效吞吐量隨冗余子信道數(shù)量的變化情況如圖6所示?？梢钥吹?，隨著子信道數(shù)量增加，RSD和THOA這2種方法的次用戶鏈路的有效吞吐量都逐漸增大。當達到最大有效吞吐量以后，再隨著子信道數(shù)量增加，有效吞吐量則開始非常緩慢地下降，但幾乎看不出。

隨著干擾概率的增大，達到最大有效吞吐量所需的冗余子信道數(shù)量也增多。如圖 6(b)所示，當pI= 0 .01時，采用RSD方法進行LT碼編碼，需要80個冗余子信道，次用戶鏈路才能達到最大有效吞吐量，而THOA方法則只需35個。當 pI= 0 .05時，采用RSD方法進行LT碼編碼，需要90個冗余子信道，次用戶鏈路才能達到最大有效吞吐量，而THOA方法則只需45個冗余子信道，降低了頻譜資源消耗。可以明顯看出，相比RSD、THOA方法達到最大有效吞吐量所需的冗余子信道數(shù)量最少。

6 結(jié)束語

本文研究了一種適用于認知無線電鏈路保持的新型LT碼度分布設(shè)計方法，將譯碼開銷較小時擁有高譯碼成功率的IPD與譯碼開銷較大時擁有高譯碼成功率的RSD進行有機結(jié)合?；贚T碼的期望可譯集以及次用戶鏈路的有效吞吐量與LT碼度分布的相關(guān)性，構(gòu)建雙層優(yōu)化目標，采用雙層尋優(yōu)算法作為尋優(yōu)工具在2種度分布間進行尋優(yōu)，實現(xiàn)了次用戶通信可靠性和有效性的提高。

圖6 THOA和RSD有效吞吐量

參考文獻：

[1]張勇,滕穎蕾,宋梅. 認知無線電與認知網(wǎng)絡(luò)[M]. 北京：北京郵電大學出版社,2012.ZHANG Y,TENG Y L,SONG M. Cognitive radio and cognitive networks[M]. Beijing: Beijing University of Posts and Telecommunications Press,2012.

[2]WILLKOMM D,GROSS J,WOLISZ A. Reliable link maintenance in cognitive radio systems[C]//2005 First IEEE International Symposium on New Frontiers in Dynamic Spectrum Access Networks. 2005: 371-378.

[3]LUBY M. LT codes[C]//43rd Annual IEEE Symposium on Foundations of Computer Science. 2002: 271-280

[4]YUE G,WANG X. Anti-jamming coding techniques with application to cognitive radio[J]. IEEE Transactions on Wireless Communications,2009,8(12):5996-6007.

[5]YUE G. Antijamming coding techniques[J]. IEEE Signal Processing Magazine,2008,25(6):35-45.

[6]LIAU A,YOUSEFI S,KIM I M. Binary soliton-like rateless coding for the Y-network[J]. IEEE Transactions on Communications,2011,59(12): 3217-3222.

[7]ETESAMI O,SHOKROLLAHI A. Raptor codes on binary memoryless symmetric channels[J]. IEEE Transactions on Information Theory,2006,52(5): 2033-2051.

[8]MACKAY D J C. Fountain codes[J]. IEEE Proceedings Communications,2005,152(6): 1062-1068.

[9]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. 2006.

[10]SHOKROLLAHI A. Raptor codes[J]. IEEE Transactions on Information Theory,2006,52(6): 2551-2567.

[11]盛驟,謝式千,潘承毅. 概率論與數(shù)理統(tǒng)計(第四版)[M]. 北京: 高等教育出版社,2010.SHENG Z,XIE S Q,PAN C Y. Probability theory and mathematical statistics (4th ed) [M]. Beijing: Higher Education Press,2010.

[12]KARP R,LUBY M,SHOKROLLAHI A. Finite length analysis of LT codes[C]//International Symposium on Information Theory. 2004.

[13]YEN K K,LIAO Y C,CHEN C L,et al. Modified robust soliton distribution (MRSD) with improved ripple size for LT codes[J]. IEEE Communications Letters,2013,17(5): 976-979.

[14]焦健,楊志華,顧術(shù)實,等.基于隨機置換展開與停止集的 LT 碼聯(lián)合編譯碼算法[J].通信學報,2013,34(2): 31-39.JIAO J,YANG Z H,GU S S,et al. Novel joint encoding/decoding algorithms of LT codes based on random permute egde-growth and stopping set[J]. Journal on Communications,2013,34(2): 31-39.