協同網絡中AR碼的度分布優化設計

黃加佳 雷 菁 黃 英

(國防科技大學電子科學學院, 湖南長沙 410073)

1 引言

無碼率碼(Rateless Code)又稱噴泉碼(Fountain Codes)[1],其發送端可以根據接收端譯碼情況而產生無限多的編碼符號。無碼率碼的這一特性非常適用于廣播及視頻等應用場景,已經應用于3GPP的多媒體廣播和多播服務標準[2],以及DVB的數據廣播內容分發協議[3]中。

無碼率碼的研究發展以提高不同場景傳輸性能和減小復雜度為目標:Luby等人[4]在2002年提出第一款簡單實用的LT碼(Luby Transform Code),其在刪除信道中擁有良好性能,但在噪聲信道下存在明顯錯誤平層;Shokrollahi等人[5]于2006年提出了在LT碼基礎上增加低密度奇偶校驗碼(low-density parity-check,LDPC)作為預編碼的Raptor碼,該碼在改善錯誤平層的同時極大增加了編譯碼的復雜性;2008年Wu Kedi等人[6]針對加性高斯白噪聲(Additive White Gaussian Noise, AWGN)信道,提出結構復雜度低、性能良好的累積無碼率碼(Accumulate Rateless Code,AR碼),但其度分布的設計依賴信道質量的優劣;非規則重復碼(Irregular Repeat-Accumulate,IRA)在2000年被提出,孫蓉等人[7]于2010年證明了該碼的無碼率特性,但該碼的最小碼率受到限制;2011年由Ma Xiao等人針對噪聲信道,并引入p序列設計了Kite碼,其缺陷在于與時間相關的p序列求取算法復雜;2012年Jonathan Perry等人[8]通過在編碼結構中引入哈希函數,提出新型無碼率碼Spinal碼,在安全性提高的同時也存在譯碼復雜度過高的問題;為提高不同場景的適應性,不斷有新的無碼率碼(如網絡噴泉碼[9]等)被提出。相對于其他無碼率碼,AR碼在復雜度和傳輸性能上有較好的折衷。Chen Shaolei等人[10]使用外信息轉移(extrinsic information transfer,EXIT)圖法對系統與非系統AR碼進行分析研究,在優先選取度值較小信息節點的前提下使用逐步邊緣增長算法和凸優化算法,求出其在不同信道噪聲功率條件下的最佳度分布,并仿真得到與Raptor碼相近傳輸性能。雷維嘉等人[11]以最小化譯碼迭代次數為約束條件,對非系統AR碼的度分布進行優化設計,并給出在固定迭代次數下的最佳度分布。上述對AR碼的研究主要集中在點對點通信上,并不能很好拓展到網絡通信當中。

針對5G物聯網[12-13]、無人機蜂群[14-15]等大規模網絡,固定碼率帶來的時延和多反饋問題無法回避,將無碼率碼引入可很好地適應不同信道環境。Castura J等人[16]首先提出中繼傳輸系統中的無碼率碼方案,使用Raptor碼編碼,在信道狀態信息未知情況下表現得更加穩定高效。雷維嘉等人[17]針對無碼率碼在協作中繼傳輸系統的應用,提出能量累積和信息累積兩種方式以降低反饋,減小傳輸時間和功耗。文獻[18-21]將無碼率碼結合分布式網絡編碼應用到無線傳感器網絡中,在源節點、中繼節點和目的節點形成基于圖碼的傳輸結構。文獻[22-23]則分析了多路并行的傳感器中繼網絡中無碼率碼方案較自動重傳請求(Automatic Repeat-reQuest,ARQ)方案時延更小。現有研究主要集中在LT碼和Raptor碼,而從性能與復雜度的折衷來考慮,探討基于AR碼的可行傳輸方案有著重要價值。本文將基于多中繼模型探討AR碼的傳輸方案,設計聯合度分布優化方法,開展性能分析與仿真。

2 信道模型

多中繼模型是大規模網絡中的典型模型,如圖1所示。

圖1 多中繼網絡模型Fig.1 Multi-relay network model

源節點S為數據采集節點,將收集到的數據向中繼和目的節點廣播發送,定義i時刻發送的信號向量為Xi。中繼節點R1～Rn負責接收和轉發數據,協助源節點通信,對應其轉發信號向量分別為Ui1～Uin。目的節點D同時接收來自源節點和中繼節點的數據,匯總處理后傳入上級網絡,定義其接收的總信號向量為Yi。考慮準靜態瑞利衰落信道,即信號噪聲在同一傳輸數據包內保持恒定,在包與包之間獨立變化。同時假設直傳信道S-D與所有中繼信道Ri-D均具有相同的衰落特征,根據文獻[15]可知:

(1)

3 基于AR碼的協同傳輸方案

在中繼傳輸中使用無碼率碼,能夠降低反饋信息的傳輸量,并在多中繼的情況下明顯提高傳輸效率[17]。而LT碼存在明顯的錯誤平層,考慮性能和復雜度的折衷,我們采用結構簡單的AR編碼方案,以提高通信質量。

3.1 協同傳輸方案

以無線傳感器網絡(Wireless Sensor Network, WSN)為應用背景,其中源節點因資源受限而不進行數據編碼,中繼節點可進行簡單編碼轉發,目的節點擁有足夠的處理能力。通過中繼節點選擇機制選擇兩個最優節點R1和R2并采用AR編碼轉發,具體協同方案如圖2所示。

圖2 AR碼協同傳輸方案Fig.2 Cooperative transmission scheme of AR code

廣播階段:假設源節點S需要發送的源數據為獨立同分布的信息序列,我們將其按一定長度分成多個組別,每個組中數據按照802.15.4協議規定添加包頭地址信息和尾部循環冗余校驗(Cyclic Redundancy Check, CRC)封裝成數據包,經過BPSK調制后不斷向中繼節點和目的節點廣播發送。當收到中繼節點全部正確接收數據的反饋后停止廣播,進入監聽狀態以節約能量。

圖3 中繼節點數據包格式Fig.3 Packet format of relay node

譯碼階段:目的節點D對接收數據解調后根據標識符信息進行分類存儲,當總的存儲數據量大于某一設定值時進行譯碼。譯碼后的數據可根據CRC信息判斷正確性。當源數據全部正確譯出時,向源節點和中繼節點發送反饋信息,開始下一組數據傳輸;反之則繼續接收更多數據包后再譯。

相比傳統ARQ方案的不斷等待反饋確認,AR方案與其他無碼率碼(Raptor碼和LT碼)方案[21-22]一樣,其數據具有獨立性和無限性,使得中繼節點與源節點能夠很好協同傳輸而提高惡劣信道條件下的適應性,減少反饋次數。

3.2 等效編碼結構

假設源節點需要發送的信息序列為(s1,s2,...,sK),根據3.1分析可知,每個編碼數據校驗節點都有一個度值d,對于節點S直接發送的數據可等效看成其度值為1,將節點D收到的所有數據對應到同一個碼圖上來,其等效編碼結構如圖4所示。

圖4 整體編碼結構等效圖Fig.4 Overall coding structure

圖4中虛線框將校驗節點和編碼節點分成了三部分,P0,1～P0,k為直傳數據,P1,1～P1,∞為R1產生的任意數量編碼數據,P2,1～P2,∞對應R2。校驗節點C1,1～C1,∞的度分布(不包括與編碼節點所連接的邊)為Ω1(x),對應邊分布為ρ1(x);C2,1～C2,∞對應為Ω2(x)和ρ2(x)。信息節點的度分布和邊分布為Λ(x)和λ(x)(不包括與直傳數據檢驗節點連接的邊)。根據編碼規則有:

Cq,i=sj1⊕sj2⊕...⊕sjn,(q=0,1,2)

(2)

式(2)中sj表示所有與校驗節點Cq,i相連的信息節點。

(3)

我們使用優先選取度值較小信息節點的方式進行編碼,以減小AR碼Tanner圖中小環的出現。這樣信息節點的度數絕大部分將為ds,極小部分為(ds±1)或(ds±2)。若中繼1對應信息節點度為d1s,中繼2為d2s,有:ds?d1s+d2s。假設信息節點長度為K,兩個中繼編碼節點長度均為N,則該方案的近似瞬時碼率為:

(4)

3.3 譯碼原理

我們在接收端使用對數似然比置信傳播(Log Likelihood Ratio Based Belief Propagation, LLR-BP)算法進行迭代譯碼,AR碼的譯碼迭代過程如圖5所示。

圖5 AR碼譯碼軟信息迭代示意圖Fig.5 Diagram of AR code decoding whit soft information iteration

我們定義各參數如下:接收到的中繼編碼節點信息(y1,y2,...,yN);信息節點i傳遞給校驗節點j的信息L(scij);校驗節點j傳給信息節點i的信息為L(csji);校驗節點j傳給編碼節點k的信息為L(cpjk); 編碼節點k傳給校驗節點j的信息為L(pckj);與信息節點i相連的校驗節點j的集合Q1(i);與校驗節點j相連的信息節點i的集合Q2(j);與校驗節點j相連的編碼節點k的集合Q3(j);與編碼節點k相連的校驗節點j的集合Q4(k)。

LLR-BP算法的譯碼基本步驟如下:

1)初始化

編碼節點的初始信息概率的似然比為:

(5)

2)校驗節點更新

對所有校驗節點j和其相鄰的信息節點i,第l次迭代時,計算校驗節點傳向信息節點的信息:

(6)

對所有校驗節點j和其相鄰的編碼節點k,第l次迭代時,計算校驗節點傳向編碼節點的信息:

(7)

3)信息節點更新

對所有的信息節點i和其相鄰的校驗節點j,第l次迭代時,計算信息節點傳向校驗節點的信息:

(8)

4)編碼節點更新

對所有的編碼節點k和其相鄰的校驗節點j,第l次迭代時,計算編碼節點傳向校驗節點的信息:

(9)

5)譯碼判決

信息節點利用收集到的所有信息進行硬判決:

(10)

6)停止條件

設定門限值L0(s),當|L(si)|L0(s)或者達到最大迭代次數后,結束運算。

3.4 度分布優化

接下來利用EXIT圖分析AR方案譯碼的迭代過程,進而優化編碼度分布。

該方案的EXIT圖模型如圖6所示,兩中繼校驗節點C到編碼節點P的輸出平均互信息分別為IC1P1(zp1)和IC2P2(zp2),到信息節點S的輸出平均互信息為IC1S(zs1)和IC2S(zs2),編碼節點P到校驗節點C的輸出平均互信息為IP1C1(x1)和IP2C2(x2),信息節點S到校驗節點C的輸出平均互信息為ISC1(y1)和ISC2(y2)。

圖6 AR方案EXIT圖模型Fig.6 EXIT chart of AR scheme

根據迭代規則[10],可以拓展雙中繼AR方案在第l次迭代譯碼時的互信息轉換式為:

(11)

(12)

(13)

(14)

(15)

J函數為發送端與接收端LLR信息間的互信息函數,在定義域[0,+∞)和值域[0,1)上單調遞增,其具體表達式為:

(16)

(17)

其中:

(18)

(19)

g1與g2分別表示某一固定度值j時y1關于y2的軟信息迭代譯碼曲線。

綜上分析,以最大化碼率為目標,保證譯碼的有效性,提出兩個中繼節點的AR碼度分布聯合優化方法如下:

(20)

由于式(20)不滿足凸優化的要求而無法直接求解,我們提出以下三種優化策略。

策略一:

假設兩個中繼節點具有相同的度函數,則邊函數和絕大部分信息節點度值也相同,即:

(21)

將式(20)轉換為一個凸優化問題,我們可以使用Matlab的凸優化工具CVX進行求解。

策略二:

先只考慮一個中繼節點,使用文獻[10]中單個度分布優化方法求出該情況下的最優度分布,然后在R1度分布求出的情況下,對R2度分布進行聯合優化求解,同樣可以轉換為一個凸優化問題。

策略三:

策略二中默認R1較R2傳輸信道信噪比低,將其中繼優化順序進行交換,其他參數設置均不變,使用同樣的方法聯合求解度分布。

3.5 理論分析

與相關文獻不同的是,我們使用三維圖來進行方案的EXIT理論分析。假設每個校驗節點連接信息節點的邊數為相同固定值,即:ρ1(j1)=ρ2(j2)=1。為有一個直觀印象,假設各噪聲方差σ0=2.266,σ1=0.7666,σ2=0.6770,信息節點平均度數d1s=2,d2s=3,校驗節點連接邊數固定值j1=j2=3,最大迭代次數為150。根據式(11)～(15)同時畫出x1,x2與y1,y2的迭代關系曲面,如圖7所示。

圖7 迭代關系三維圖Fig.7 3D diagram of iterative relationship

將圖7中曲面交線投影到y1Oy2平面,并畫出縱向曲面與y1Oy2平面交線,如圖8所示。

圖8 曲面交線投影及y1,y2迭代變化圖Fig.8 Projection of surface intersecting line and iterative change of y1,y2

圖8中曲線1表示圖7(a)中縱向曲面與y1Oy2平面交線,曲線2對應圖7(b)中交線;曲線3表示圖7(a)中兩曲面交線在y1Oy2平面投影,曲線4對應圖7(b)中投影;紅色圓圈表示點(y1,y2)在迭代過程中的變化情況,其收斂區域為所在曲線3與曲線4之間區域。根據前述定義及分析,兩曲線對應y1關于y2表達式分別為:

(22)

(23)

由曲線位置關系得到成功譯碼的條件為:

(24)

將式(24)中固定j值拓展為所有可能j值的概率累加,即得到式(20)中的限制條件。通過以上分析,我們所提方案在所給約束條件下能夠成功譯碼,降低譯碼錯誤平層。并且較文獻[10]方法拓展為兩個節點的聯合優化,可獲得更好性能。

4 性能仿真

根據WSN的實際情況,設置三組不同的信噪比,對所提三種優化策略分別求得度分布。同時也給出文獻[10]中方法所求度分布進行對照,具體表達式如表1、表2和表3所示。

表1 不同方案下SNR0=-5 dB,SNR1=0 dB, SNR2=2 dB時的度分布表達式

表2 不同方案下SNR0=-5 dB,SNR1=1 dB, SNR2=2 dB時的度分布表達式

表3 不同方案下SNR0=-4 dB,SNR1=1 dB, SNR2=2 dB時的度分布表達式

對照LT碼方案使用Shokrollahi的經典度分布如下:

Ω(x)=0.008x+0.494x2+0.166x3+0.073x4+ 0.083x5+0.056x8+0.037x9+0.056x19+ 0.025x65+0.003x66

(25)

我們對以上度分布方案進行蒙特卡洛仿真,采用BPSK調制方式,傳輸信道為AWGN信道,原始信息碼長為10000,循環次數為1000,最大譯碼迭代次數為150。結果如圖9所示。

從圖9(a)中可以看到,LT方案在較低碼率倒數時(1/R<3.1)誤碼率比AR方案低,但隨著碼率的減小其誤碼率緩慢降低而趨于同一層級;四種AR方案在仿真中并沒有出現明顯的錯誤平層,由于AR碼在編碼結構上較LT碼級聯了一個累加器,使得相鄰的編碼節點之間通過校驗節點直接產生聯系,錯誤的編碼節點信息在譯碼迭代時能夠被及時糾正,這也與式(17)的平均誤碼率分析結果相對應;文獻[10]度分布方案比聯合方案二在較高碼率倒數時(1/R>3.3)的誤碼率相差近一個數量級,這說明聯合度分布優化是有效的;聯合方案一與方案三近乎重合,且明顯優于方案二,分析原因為信道條件較好節點對成功譯碼的影響更大,對其優先進行度分布優化能夠提高譯碼性能;在聯合相同度的優化時,同時考慮了兩個中繼到目的節點的信道條件,整體上進行優化對性能也有一定提升。

圖9 誤碼率性能仿真圖Fig.9 Simulation performance of bit error rate

圖9(b)和圖9(c)中LT方案的變化并不明顯,但是AR方案的誤碼曲線性能明顯提升,因為信噪比增大使得數據在傳輸過程中產生錯誤的概率減小。方案一和方案三也拉開差距,這說明對不同信道條件的中繼設置不同度分布更接近最優策略。圖9綜合顯示我們所提方案三譯碼性能最優,較已有文獻AR度分布方案在誤碼率達10-5數量級上,分別至少減小7.14%、8.75%和6.25%的碼率倒數。本文所提方案是在已有文獻方案基礎上,充分考慮不同節點信道參數的相異性進行聯合度分布優化所得結果,EXIT圖分析中已經在迭代譯碼時考慮了兩個節點的協同配合,使得所提方案的譯碼效率獲得極大提升。

5 結論

本文探討了協同網絡中通信方案設計及度分布優化問題,針對“1-n-1”模型提出了AR碼方案,利用其無碼率特性有效解決了網絡通信中信道變化帶來的適應性問題;通過編碼結構以及EXIT圖分析,進行度分布聯合優化設計,并對優化條件進行理論推導和驗證。提出了三種優化策略,使用凸優化工具分別進行求解。仿真分析表明,我們所提的AR方案最優策略降低了LT方案的錯誤平層,在譯碼性能上較現有文獻[10]度分布方案更優。下一步將考慮所有中繼節點等效看成同一度分布進行整體分析研究,以減小復雜度和提高傳輸效率。