噴泉碼多路并行轉發(fā)中繼系統(tǒng)傳輸時間分析

吳丹，田亞飛，楊晨陽

（北京航空航天大學 電子信息工程學院， 北京 100191）

1 引言

中繼技術可以有效地擴展無線通信系統(tǒng)的覆蓋范圍或者提升用戶的吞吐量[1]。在能量受限的系統(tǒng)中，如超寬帶通信系統(tǒng)，使用多中繼并行轉發(fā)可以大大擴展其傳輸距離。如果中繼節(jié)點之間可以聯(lián)合同步，并且每個節(jié)點傳輸?shù)臄?shù)據(jù)率相同，則多中繼可以形成虛擬天線陣，進行波束形成以得到能量增益。但是，在實際的系統(tǒng)中中繼之間往往難以進行聯(lián)合同步，而且中繼節(jié)點的位置往往不同，導致傳輸數(shù)據(jù)率不同，此時進行多路數(shù)據(jù)流并行轉發(fā)是更有效的方式[2,3]。

本文考慮多級多路并行轉發(fā)寬帶中繼系統(tǒng)。多路不同的碼流可以通過時分、頻分或碼分來區(qū)分，中繼系統(tǒng)可以服務一個用戶也可以服務多個用戶。

為了保證傳輸?shù)目煽啃?，通信網(wǎng)絡在數(shù)據(jù)鏈路層一般會采用差錯控制，如自動重傳請求（ARQ）協(xié)議。但是，基于多跳通信的ARQ方案[4]難以直接應用于多路并行傳輸?shù)闹欣^網(wǎng)絡中。多級傳輸?shù)臅r序非常復雜，當某一級的某一路信號出現(xiàn)傳輸錯誤時，信源很難判斷何時重新發(fā)射信號。如果層層向上反饋，則會給網(wǎng)絡帶來大量額外的開銷。

為了降低多級多路中繼系統(tǒng)中反饋和重傳的負擔，本文考慮采用噴泉碼進行開環(huán)差錯控制。

噴泉碼是在刪除信道上設計的編碼[5]，在加性白高斯噪聲信道和衰落信道下也能達到很好的性能[6,7]。采用噴泉碼編碼的傳輸過程不需要經(jīng)常反饋重傳信息，只需接收端在接收到足夠的數(shù)據(jù)并正確解調(diào)信息后給信源發(fā)送一個終止信號，從而可以避免建立大量的反饋鏈路。噴泉碼已被考慮應用于各類無線通信場景中，如由無線局域網(wǎng)構成的ad hoc網(wǎng)絡[8]、廣播、多址網(wǎng)絡[9]，單中繼協(xié)作網(wǎng)絡[10]和窄帶協(xié)作中繼網(wǎng)絡[3,11]。文獻[3]首次研究了噴泉碼在兩級多中繼協(xié)作網(wǎng)絡中的應用，并給出了中繼同步和異步時的傳輸方案及性能。在文獻[3,11]研究的窄帶協(xié)作網(wǎng)絡中，信源向各中繼節(jié)點廣播同樣的數(shù)據(jù)，而中繼節(jié)點只有在收到足夠多的數(shù)據(jù)并完整解出原始信息后才會進行轉發(fā)，在多級中繼系統(tǒng)中，這會造成過長的傳輸延遲。

本文考慮寬帶多中繼協(xié)作網(wǎng)絡。利用噴泉碼的性質(zhì)和多路并行傳輸?shù)奶攸c，中繼端都不進行噴泉碼譯碼，而是對每一個收到的數(shù)據(jù)分組進行循環(huán)冗余校驗（CRC），如果正確接收就進行轉發(fā)，如果錯誤則直接丟棄，完整譯碼只在目的接收端進行。通過分析和仿真，比較這種傳輸方案和基于 ARQ方案的傳輸時間。結果表明，基于噴泉碼的方案優(yōu)于 ARQ傳輸方案，并且隨著系統(tǒng)誤包率和網(wǎng)絡中繼數(shù)的增加，噴泉碼方案的優(yōu)勢越來越明顯。

本文安排如下：第2節(jié)給出多級多路協(xié)作中繼系統(tǒng)模型，并簡要介紹噴泉碼；第3節(jié)對噴泉碼和ARQ傳輸方案下的系統(tǒng)傳輸時間進行理論分析與比較；第4節(jié)通過數(shù)值分析和仿真對這2種方案的性能進行比較；最后是結束語。

2 系統(tǒng)模型

噴泉碼的基本編譯碼思想為：發(fā)射端對原始K個分組做隨機線性編碼，接收端只需接收到N = K ( 1 + ε )個分組后（N略大于K），就能以很大的概率正確恢復原始分組，這里ε表示接收端正確譯碼所需要接收的冗余度。Raptor碼的編譯碼復雜度與數(shù)據(jù)分組數(shù)K呈線性關系，并且當K很大時，冗余度很小[15]。3GPP組織的多媒體廣播和多播業(yè)務標準中采用的系統(tǒng)Raptor碼[16]，在分組數(shù)較小的情況下也有較好的冗余性能。由于接收端對數(shù)據(jù)分組的接收順序沒有要求，采用噴泉碼傳輸?shù)木W(wǎng)絡可以直接丟棄接收錯誤的分組，無需反饋重傳信息，

考慮如圖1所示的多級中繼協(xié)作網(wǎng)絡，包含一個信源節(jié)點，一個或多個目的接收節(jié)點以及多級中繼轉發(fā)節(jié)點。這個網(wǎng)絡由廣播和多址2個基本階段構成。其中，由一個節(jié)點向多個節(jié)點發(fā)送數(shù)據(jù)的過程為廣播階段，由多個節(jié)點向一個節(jié)點發(fā)送數(shù)據(jù)的過程為多址階段。

以單用戶一級多中繼系統(tǒng)為例，在多路并行傳輸模式下，信源可以向M個中繼節(jié)點發(fā)送不同的數(shù)據(jù)，多中繼也可以同時向信宿傳輸?？紤]實際系統(tǒng)的可實現(xiàn)性，這里中繼采用時分雙工模式[12]。

通信網(wǎng)絡可以看作一種刪除信道[5]。噴泉碼是刪除信道中的一種稀疏圖編碼[5]，由 Luby等人在1998年第一次提出[13]，但是并沒有給出明確的實現(xiàn)方法和結構。LT碼是噴泉碼的第一次實現(xiàn)[14]，Raptor碼是LT碼和一個線性預編碼的級聯(lián)[15]，可以降低編譯碼復雜度，同時提高性能。從而開環(huán)控制網(wǎng)絡，減少網(wǎng)絡信令開銷，降低網(wǎng)絡復雜度。

圖1 中繼協(xié)作網(wǎng)絡

3 傳輸方案與傳輸時間分析

下面將噴泉碼應用于多路并行中繼協(xié)作網(wǎng)絡，給出一種網(wǎng)絡傳輸方案，并分析所需傳輸時間。作為比較，也將給出在上述網(wǎng)絡中應用 ARQ協(xié)議的傳輸方案。

3.1 噴泉碼方案與傳輸時間

考慮傳輸一份大小為K個數(shù)據(jù)分組的源文件，信源端使用噴泉碼對原始分組編碼，對每組噴泉碼數(shù)據(jù)再進行 CRC編碼。編碼后一個分組內(nèi)的比特數(shù)為l，持續(xù)時間為pT。各分組通過不同的中繼進行傳輸，出現(xiàn)傳輸錯誤的分組被中繼和目的端直接丟棄，目的端只需收到一定冗余量的分組即可正確恢復數(shù)據(jù)，數(shù)據(jù)分組到達的順序不影響最終譯碼性能。假設所有發(fā)射接收設備的處理都是理想的，沒有延遲。

如圖2所示，信源在廣播階段向中繼廣播不同數(shù)據(jù)，之后開始監(jiān)聽。中繼對接收到的數(shù)據(jù)進行CRC校驗后，向目的節(jié)點轉發(fā)校驗正確的數(shù)據(jù)分組，即為多址階段，完成后也轉入監(jiān)聽狀態(tài)lT。當目的節(jié)點接收到足夠多正確的數(shù)據(jù)分組，可以成功譯碼時，在1T時間內(nèi)發(fā)出終止信號。當信源和中繼監(jiān)聽到終止信號時，文件傳輸結束；若未監(jiān)聽到終止信號，則轉入下一個廣播狀態(tài)，繼續(xù)發(fā)射后續(xù)數(shù)據(jù)分組。

圖 2 噴泉碼傳輸方案幀結構

一組數(shù)據(jù)由信源發(fā)出，經(jīng)中繼i轉發(fā)，正確到達目的節(jié)點的概率為其中，為廣播階段各鏈路的誤包率，為多址階段各鏈路的誤包率。因此，信源向每個中繼發(fā)射的數(shù)據(jù)分組數(shù)sN滿足下式：

當中繼位置相近時，廣播和多址階段各中繼鏈路的誤包率可認為近似相等，分別為e,BCp 和e,MAp ，從而采用噴泉碼傳輸方案時系統(tǒng)傳輸時間約為

3.2 ARQ方案與傳輸時間

圖3給出了采用停發(fā)等候ARQ協(xié)議[17]時的幀結構。同樣采用分組傳輸和 CRC校驗，系統(tǒng)的延遲可以忽略，數(shù)據(jù)發(fā)送完成之后，發(fā)送方等待接收方的 CRC校驗信息，如顯示成功，則發(fā)送后續(xù)數(shù)據(jù)，否則重傳。

圖3 ARQ傳輸協(xié)議幀結構

在廣播階段，信源向中繼廣播不同數(shù)據(jù)，發(fā)射完成后進入長度為TW的時隙等待中繼反饋校驗信息；信源重發(fā)沒有接收到 ACK信息的數(shù)據(jù)分組，直至接收到所有 ACK信息后，發(fā)出通知信號（發(fā)射完成信號），信源節(jié)點切換為監(jiān)聽狀態(tài)。

假設對于沒有接收到 ACK確認的數(shù)據(jù)分組只需重傳一次即可保證正確接收，則廣播階段正確傳輸所需的平均時間為

信源節(jié)點切換為監(jiān)聽狀態(tài)時，系統(tǒng)進入多址階段，所有中繼開始轉發(fā)數(shù)據(jù)，等待目的節(jié)點的反饋。中繼接收到 ACK信號后，向信源發(fā)送轉發(fā)完成信號，并轉入接收狀態(tài)。當信源監(jiān)聽到所有中繼的轉發(fā)完成信號后，系統(tǒng)切回廣播狀態(tài)，完成一次傳輸。不難得到，多址階段正確傳輸所需的平均時間為

只有所有中繼（或目的節(jié)點）正確接收到各自的數(shù)據(jù)（或所有轉發(fā)數(shù)據(jù)）時，傳輸才算完成。因此ARQ方案下一次完整傳輸所需時間為

事實上，在 ARQ傳輸協(xié)議中，隨著中繼數(shù)的增加，信源需要等待的通知信號（包括廣播階段ACK信號和多址階段轉發(fā)完成信號）越多，等待時間 TW越長。對于ARQ協(xié)議，一個時隙的平均持續(xù)時間為

3.3 2種傳輸方案的性能比較

由式(2)和式(5)可以得到采用噴泉碼方案和重發(fā)一次即正確的ARQ方案時系統(tǒng)傳輸時間的比值：

式(6)中(1)ε+是噴泉碼的冗余性能對傳輸性能的影響。

tFC/tARQ反映了傳輸協(xié)議的復雜度對傳輸時間的影響。根據(jù)3.1節(jié)和3.2節(jié)的傳輸方案，有 tARQ＞tFC。

式(6)中第2行的第2個因子反映的是傳輸方案對傳輸時間的影響，2種協(xié)議的主要差別在于當網(wǎng)絡中某條鏈路傳輸出錯時，噴泉碼協(xié)議可以繼續(xù)傳輸，而ARQ協(xié)議必須等待同級的所有鏈路傳輸均正確后才能轉入下一級，這是影響系統(tǒng)傳輸時間的主要因素。當 pe,BC和 pe,MA較小時，這一項因子可以用Taylor展開進一步化簡得到

可以看出，當中繼數(shù) M ≥ 2 時，式(7)小于或等于1，當噴泉碼的冗余度較小時，有即采用噴泉碼方案的系統(tǒng)傳輸時間較??；當中繼數(shù)M= 1時，式(7)略大于 1，但是由于這表明在點對點單跳鏈路中，2種方案的傳輸時間基本相同?？梢姡瑖娙a可以降低多中繼系統(tǒng)的反饋量，減少傳輸時間，提高吞吐量。

3.4 多級中繼傳輸

考慮由(n-1)級轉發(fā)中繼( 2n≥ )構成的n級傳輸系統(tǒng)。采用噴泉碼方案，每個轉發(fā)節(jié)點以2個幀時隙（一個時隙用于接收上一級節(jié)點的數(shù)據(jù)，一個時隙用于向下一個節(jié)點轉發(fā)數(shù)據(jù)）為周期，進行級聯(lián)轉發(fā)。為了終止傳輸，接收端可以發(fā)射一個足夠強的終止信號，使各級節(jié)點均可監(jiān)聽到；也可通過各級中繼進行逐級回傳，但這會犧牲一些傳輸時間。

假設各級傳輸?shù)恼`包率相等，均為pe；每級轉發(fā)的中繼數(shù)也相等，均為M。則采用噴泉碼傳輸時系統(tǒng)的傳輸時間為

其中， M(1-pe)n為經(jīng)過n級傳輸并正確到達接收端的平均數(shù)據(jù)分組數(shù)；系統(tǒng)需要等待(n-2)個時隙，才能接收到第一個時隙發(fā)出的數(shù)據(jù)，隨后，每隔 2個時隙接收一次數(shù)據(jù)。當n=2時，式(8)退化為式(2)。

ARQ方案在重傳一次即正確的假設下，也可以進行級聯(lián)轉發(fā)，但是反饋量隨級數(shù)的增加也增加，協(xié)議較為復雜。ARQ傳輸方案的傳輸時間為

因此，對于n級傳輸系統(tǒng)，2種傳輸協(xié)議下系統(tǒng)的傳輸時間比值為

隨著級數(shù)n的增加，式(10)中 TFC/TARQ也增大，這是由于噴泉碼方案中每級成功傳輸?shù)臄?shù)據(jù)分組遞減。但是只要M＞n，噴泉碼方案就優(yōu)于ARQ方案。

4 數(shù)值與仿真分析

本節(jié)給出采用噴泉碼傳輸協(xié)議、一般 ARQ傳輸協(xié)議和重傳一次即正確ARQ傳輸協(xié)議這3種協(xié)議時一級中繼系統(tǒng)的性能。對每個中繼節(jié)點發(fā)射105分組進行蒙特卡洛仿真實驗。假設ARQ反饋信號可以保證無誤傳輸，且不考慮同步等處理時間。

仿真中采用3GPP多媒體廣播和組播業(yè)務標準中的系統(tǒng)Raptor碼[16]。表1給出 100次Raptor編譯碼實驗中接收端成功譯碼的次數(shù)。可以看出，當分組數(shù)K在1 000~3 000之間時，接收端在多收10個分組后即能以很大的概率正確譯碼，即冗余度ε＜ 1 %。

表1 Raptor碼譯碼性能

式(6)中 tFC/ tARQ因子的影響在實際系統(tǒng)中不能忽略，與信令設計有關，但由于本文不涉及具體的物理層包頭設計，因此僅仿真第2項因子的影響，故仿真結果為時分雙工系統(tǒng)中實際值的上界。

圖4給出了噴泉碼方案和ARQ方案（重發(fā)一次即正確ARQ與重發(fā)直至正確的一般ARQ方案）傳輸時間比值的數(shù)值和仿真結果。其中，中繼數(shù)M=4，數(shù)值結果由式(6)給出?？梢钥闯?，重發(fā)一次即正確ARQ方案的仿真結果與數(shù)值結果吻合；當2個階段誤包率均較小時，如小于 0.04，一般 ARQ的仿真結果也與數(shù)值結果基本吻合。圖中比值均小于 1，說明采用噴泉碼傳輸方案時系統(tǒng)的傳輸時間小于ARQ傳輸方案，前者可以獲得更高的吞吐量。

從圖中還可以看出，多址階段誤包率 pe,MA越高，相對于一般 ARQ方案，采用噴泉碼方案時系統(tǒng)的傳輸時間越短，噴泉碼方案越有優(yōu)勢。根據(jù)傳輸協(xié)議設計，可知廣播階段誤包率 pe,BC對系統(tǒng)傳輸時間的影響也是如此。當 pe,BC分別為0.01和0.1時，噴泉碼在后者條件下優(yōu)勢更為明顯。

隨著pe,MA的增加，噴泉碼方案與重傳一次即正確 ARQ方案的時間比值先下降再上升。這是由于在誤包率較大時，ARQ方案使數(shù)據(jù)分組在每個階段的傳輸時間控制在2個時隙內(nèi)，人為地縮短了傳輸時間。而在實際系統(tǒng)中要滿足重傳一次即成功的假設，需要增大發(fā)射機信號功率，或采用糾錯性能更好的編碼進行重發(fā)，或者選擇信道條件更好的中繼進行轉發(fā)，是一種混合ARQ控制和中繼選擇問題，不在本文的討論范圍內(nèi)。

圖4 TFC/TARQ的數(shù)值和仿真結果

圖5給出了在給定廣播階段誤包率 pe,BC=0.01的情況下， TFC/TARQ與中繼數(shù)M的關系。

圖5 不同ARQ協(xié)議下，TFC/TARQ與中繼數(shù)的關系

可以看出，在2種ARQ傳輸方案下，隨著M的增多，TFC/TARQ均減小。在多路并行傳輸模式下，盡管可以采用時分、頻分和碼分等方式傳輸多個數(shù)據(jù)流，但是由于時間、頻率同步、衰落信道等各種實際因素的影響，多路數(shù)據(jù)的正交性無法完全保證。這意味著隨著中繼數(shù)的增加，每個中繼節(jié)點受到其他節(jié)點的總干擾一般會增大，系統(tǒng)誤包率也會增大。此時，噴泉碼的優(yōu)勢更加明顯。另外，網(wǎng)絡中繼數(shù)越多，ARQ方案中一個幀時隙持續(xù)時間越長，反饋鏈路越復雜；而噴泉碼傳輸方案在大規(guī)模網(wǎng)絡中具有十分優(yōu)越的性能。

5 結束語

本文將噴泉碼應用于多路并行傳輸中繼網(wǎng)絡中，給出了基于噴泉碼傳輸?shù)闹欣^協(xié)作網(wǎng)絡的傳輸方案和幀格式，分析了系統(tǒng)的傳輸時間。

本文針對一級和多級中繼協(xié)作網(wǎng)絡，理論分析了采用噴泉碼與采用重發(fā)一次即正確的 ARQ時系統(tǒng)的傳輸時間之比，并通過仿真驗證了理論分析的正確性。分析的結果表明，噴泉碼方案的傳輸時間小于ARQ方案；隨著中繼數(shù)和系統(tǒng)誤包率的增加，噴泉碼方案的優(yōu)勢更加明顯；在多級中繼系統(tǒng)中，只要轉發(fā)中繼數(shù)大于轉發(fā)級數(shù)，采用噴泉碼方案的系統(tǒng)就會具有很大的性能優(yōu)勢?？梢?，采用噴泉碼的傳輸方案無需復雜的協(xié)議設計，無需引入反饋鏈路，即可以在保證系統(tǒng)傳輸可靠性的前提下減小傳輸時間，提高系統(tǒng)的吞吐量。

[1] FITZEKF H P, KATZM D. Cooperation in Wireless Networks: Principles and Applications[M]. Netherlands: Springer, 2006.

[2] TIAN Y F, YANG C Y. Space-time focusing transmission in ultra-wideband cooperative relay networks[A]. ICUWB[C]. 2009. 353-358.

[3] MOLISCH A F, MEHTA N B, YEDIDIA J S, et al. Performance of fountain codes in collaborative relay networks[J]. IEEE Transactions on Wireless Communications, 2007, 6(11): 4108-4119.

[4] JEON S Y, CHO D H. Modeling and analysis of ARQ mechanisms for wireless multi-hop relay system[A]. VTC Spring[C]. 2008. 2436-2440.

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

[6] CASTURA J, MAO Y. Rateless coding for wireless relay channels[J].IEEE Transactions on Wireless Communications, 2007, 6(5): 1638-1642.

[7] CASTURA J, MAO Y. Rateless coding over fading channels[J]. IEEE Communication Letters, 2006, 10(1): 46-48.

[8] KSENTINI A, CHAHED T. Extending the ad hoc horizon in dense 802.11 networks using fountain codes[A]. ICSNC[C]. 2009.63-67.

[9] JANKAC H, STOCKHAMMER T. Asynchronous media streaming over wireless broadcast channels[A]. IEEE International Conference on Multimedia Expo[C]. 2005. 1318-1321

[10] LIU X, LIM T J. Fountain codes over fading relay channels[J]. IEEE Transactions on Wireless Communications, 2009, 6(6): 3278-3287.

[11] LEI W J, LI X M, LI G J. Wireless cooperative relay system using digital fountain codes[A]. ICCCAS[C]. 2009. 123-127.

[12] PETERS S W, PANAH A Y, TRUONG K T, et al. Relay architectures for 3GPP LTE-advanced[J]. EURASIP Journal on Wireless Communications and Networking, 2009, Article ID 618787: 1-14.

[13] BYERS J, LUBY M. A digital fountain approach to reliable distribution of bulk data[A]. ACM SIGCOMM[C]. 1998. 56-67.

[14] LUBY M. LT codes[A]. FOCS[C]. 2002. 271-282.

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

[16] 3rdGeneration Partnership Project (3GPP). Technical Specification Group Services and System Aspects; Multi-media Broadcast/Multicast Services (MBMS); Protocols and Codecs (Release6)[R]. Tech Rep 3GPP TS 26.346 V6.3.0, 3GPP, 2005.