噴泉碼多路并行轉發中繼系統傳輸時間分析

吳丹，田亞飛，楊晨陽

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

1 引言

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

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

為了保證傳輸的可靠性，通信網絡在數據鏈路層一般會采用差錯控制，如自動重傳請求（ARQ）協議。但是，基于多跳通信的ARQ方案[4]難以直接應用于多路并行傳輸的中繼網絡中。多級傳輸的時序非常復雜，當某一級的某一路信號出現傳輸錯誤時，信源很難判斷何時重新發射信號。如果層層向上反饋，則會給網絡帶來大量額外的開銷。

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

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

本文考慮寬帶多中繼協作網絡。利用噴泉碼的性質和多路并行傳輸的特點，中繼端都不進行噴泉碼譯碼，而是對每一個收到的數據分組進行循環冗余校驗（CRC），如果正確接收就進行轉發，如果錯誤則直接丟棄，完整譯碼只在目的接收端進行。通過分析和仿真，比較這種傳輸方案和基于 ARQ方案的傳輸時間。結果表明，基于噴泉碼的方案優于 ARQ傳輸方案，并且隨著系統誤包率和網絡中繼數的增加，噴泉碼方案的優勢越來越明顯。

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

2 系統模型

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

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

以單用戶一級多中繼系統為例，在多路并行傳輸模式下，信源可以向M個中繼節點發送不同的數據，多中繼也可以同時向信宿傳輸?？紤]實際系統的可實現性，這里中繼采用時分雙工模式[12]。

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

圖1 中繼協作網絡

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

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

3.1 噴泉碼方案與傳輸時間

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

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

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

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

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

3.2 ARQ方案與傳輸時間

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

圖3 ARQ傳輸協議幀結構

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

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

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

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

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

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

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

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

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

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

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

3.4 多級中繼傳輸

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

假設各級傳輸的誤包率相等，均為pe；每級轉發的中繼數也相等，均為M。則采用噴泉碼傳輸時系統的傳輸時間為

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

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

因此，對于n級傳輸系統，2種傳輸協議下系統的傳輸時間比值為

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

4 數值與仿真分析

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

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

表1 Raptor碼譯碼性能

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

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

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

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

圖4 TFC/TARQ的數值和仿真結果

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

圖5 不同ARQ協議下，TFC/TARQ與中繼數的關系

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

5 結束語

本文將噴泉碼應用于多路并行傳輸中繼網絡中，給出了基于噴泉碼傳輸的中繼協作網絡的傳輸方案和幀格式，分析了系統的傳輸時間。

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

[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.