基于網絡編碼的III型HARQ無線廣播跨層設計

呂振興 許 魁 徐友云

(解放軍理工大學通信工程學院 南京 210007)

1 引言

無線通信系統中，多種數據業務傳輸方案都要求具有低誤碼率和高吞吐量的性能。常用的混合自動重傳請求(HARQ)技術有效地結合前向糾錯(Forward Error Correction FEC)和自動重傳請求(Automatic Repeat reQuest ARQ)這兩種基本的差錯控制機制，為傳輸提供了更高的可靠性和系統吞吐量[1]。根據重傳內容的不同，HARQ技術可分為3種類型[2,3]。I型HARQ是一種信息序列及其校驗位全部重傳并單獨譯碼的機制。Ⅱ型和Ⅲ型HARQ系統屬于增量冗余機制。不同之處在于II型HARQ機制，重傳的只是數據信息或只是FEC冗余信息，只能與先前的錯誤版本并譯碼，而III型HARQ機制中，重傳數據均包含數據信息和冗余信息，接收端可單獨譯碼，也可與緩存的出錯版本進行合并譯碼。III型HARQ機制可以克服快速變化的信道以及信道條件瞬時惡化對系統性能的影響，尤其適用于時變衰落信道。

無線廣播場景中大量用戶丟失不同的數據包，傳統的 HARQ技術每次只能重傳一個出錯的數據包，造成了重傳效率的低下。因此，如何提高廣播中的重傳效率成為研究熱點之一，而具有顯著優勢的網絡編碼[4]技術為研究者提供了一種新的途徑。基于無線信道的不可靠性和廣播特性，網絡編碼在無線通信領域得到了靈活有效的應用，Katti 等人[5]設計了實用的網絡層編碼協議 COPE，其在重負載時吞吐量性能較傳統路由有 40%的提高；Gollakota 等人[6]設計了靈活的物理層編碼協議ZigZag, 14個節點的仿真表明其相比傳統的802.11協議平均吞吐率提高25%，平均丟包率從15.8%減小至0.2%。大量研究表明，無線通信中的網絡編碼技術不僅可以改善誤碼性能，增強網絡的容錯性和魯棒性，還能夠減少數據包重傳次數[7,8]，顯著提升網絡吞吐量。

無線廣播模型中常用的網絡編碼重傳策略有兩種。一種策略是基站首次廣播數據包后，根據ARQ反饋，將所有需重傳數據包重復進行隨機網絡編碼(RNC)后發送，用戶只要接收到足夠多的編碼包，就能根據求解逆矩陣的思想得到所需的數據包[7,9]。但這種策略有兩個明顯的缺點：一是譯碼過程復雜，二是重傳包延時過大。另一種策略是基站廣播發送數據包的同時，根據實時接收的ARQ反饋進行異或型(XORing)網絡編碼[5,10-12]。這種策略的網絡譯碼過程簡單，且在廣播的同時就能穿插編碼重傳過程，延時較低。由于文獻[10]中提出的數據包組合策略可能會導致該用戶不可譯碼，本文將對其進行改進，提出了新的異或型網絡編碼聯合(XORing Network Coding Combined, XNCC)策略。

文獻[11]研究了認知網絡中聯合網絡編碼和傳統ARQ技術的NC-ARQ廣播方案，基本思想是在ARQ重傳階段對丟失包進行網絡編碼聯合，以減少傳輸次數。文獻[12,13]分別研究廣播中繼和雙向中繼模型下，聯合網絡編碼和HARQ技術所帶來的吞吐量增益。文獻[14]研究了無線下行鏈路中基于傳統 HARQ的網絡編碼技術 NC-HARQ，理論分析了網絡編碼在重傳效率和傳輸時延方面的性能增益。本文進一步將網絡編碼技術和III型HARQ機制相結合，提出一種基于網絡編碼的NC-HARQ III型廣播系統。其主要思想是在重傳階段，利用所提XNCC策略聯合需重傳數據包，一方面使每次編碼包的重傳能服務于多個用戶，減少重傳次數；另一方面通過聯合網絡-信道譯碼(Joint Network and Channel Decoding, JNCD)設計，降低譯碼錯誤性能，減少再次重傳次數。仿真表明該方案，較網絡層或鏈路層的分層設計方案，能有效減少重傳次數，獲得顯著的時延增益。

2 NC-HARQ Ⅲ型廣播系統

NC-HARQ III型廣播系統傳輸結構如圖1所示。基站通過偵聽來自各用戶的控制信號，獲取信道狀態信息(CSI)來實施自適應編碼調制(AMC)控制，以獲得最大的頻譜利用率。本文不對AMC技術做重點討論，簡單起見，調制方式采用BPSK調制，信道編碼采用遞歸系統卷積碼(RSC)編碼，這主要是考慮到重傳數據可以與先前緩存數據聯合構成分布式Turbo碼，降低誤包率。整個傳輸過程可分為兩個階段：數據包的首次發送稱為廣播階段，錯誤數據包的再次發送稱為重傳階段。為了滿足系統的QoS要求，兩階段可穿插進行，保證數據業務的實時性和流暢度。

廣播階段，基站將信源數據包添加循環冗余校驗(CRC)后進行RSC編碼、調制發送；用戶對接收到的解調數據進行RSC譯碼，通過CRC校驗判斷是否正確譯碼，同時將HARQ反饋通過控制信道發送到基站。譯碼正確的數據包將被送入數據包緩存，以便重傳階段進行網絡譯碼；譯碼錯誤時，軟解調數據將被送入軟信息緩存，以便與重傳階段接收數據聯合進行信道譯碼。

圖1 NC-HARQ III型廣播系統傳輸結構

重傳階段，基站根據HARQ反饋，采用XNCC策略，在源數據包緩存中選擇合適的數據包進行XORing網絡編碼，生成的編碼包經CRC校驗、交織、RSC編碼后發送。接收端從軟解調數據中網絡譯碼出丟失數據包的重傳信息，將其與廣播階段的解調數據聯合進行信道譯碼，以此獲得較低的誤包率。譯碼結果的處理模式同廣播階段一樣：譯碼正確時，數據包將被送入數據包緩存；譯碼錯誤時，軟解調數據將被送入軟信息緩存。

需要注意的是，數據包的 CRC校驗編碼與RSC信道編碼都具有良好的線性性質，網絡編碼中的XOR操作不影響其發揮作用。以等數據長度的數據包i1和i2為例，CRC(*)和RSC(*)分別表示具有相同生成多項式的 CRC校驗編碼和具有相同生成矩陣的 RSC信道編碼。若C1=CRC(i1),C2=CRC(i2)，則等式C1⊕C2=CRC(i1⊕i2)仍然成立；若R1=RSC(i1),R2=RSC(i2)，則等式R1⊕R2=RSC(i1⊕i2)仍然成立。限于篇幅，不作證明。

2.1 XNCC策略

基站根據接收到的HARQ反饋，獲得數據包的丟失情況，其包括：(1)數據包是否丟失；(2)丟失數據包的序列號和丟失節點序列號[10]。假定反饋信道不存在損耗。基站將丟失情況記錄在矩陣T中，如圖2所示，該矩陣中行表示用戶接收情況，列表示數據包被接收情況。若某個數據包在某個接收節點被成功接收，相應位置賦值為“0”；若丟失，相應位置賦值為“1”。

圖2 數據包傳輸錯誤標志矩陣T

為了使每次重傳過程中，盡量多的用戶節點通過簡單的XOR操作，就能獲得丟失數據包的重傳信息，有以下兩個選擇編碼準則：(1)針對任一用戶只能有一個丟失包參與網絡編碼；(2)每次生成的編碼包能服務于盡量多的用戶。參照選擇準則，我們設計了在數據包傳輸錯誤標志矩陣T中尋找編碼組合的XNCC策略，具體步驟為：

步驟 1 將被全部用戶正確接收的數據包序列去除，比如圖 2中的ID:8數據包，清空編碼列表CodingList，清空服務用戶列表UserList；

步驟 2 從第1列開始，將該列中錯誤標志為“1”的所有用戶ID設為向量UserList_temp；

(1)若UserList_temp與UserList有交集，則該列不能添加進編碼列表，丟棄。

(2)若UserList_temp與UserList無交集，則將該列ID添加進編碼列表CodingList，該列中所有的錯誤標志置為“0”，更新服務用戶列表：UserList=UserList+UserList_temp。

若服務用戶列表UserList遍及所有用戶或達到限制重傳次數，則可退出循環。

步驟 3 將編碼列表 CodingList指示的所有數據包進行XOR操作。

實用過程中，XNCC策略的詳細編碼算法如表1所示，其中N表示用戶數目，l表示待重傳包數目。

表1 XNCC策略編碼算法

根據XNCC策略，可得到表1的網絡編碼方式為：1⊕2⊕6, 3⊕5, 4⊕9, 7⊕10，則重傳次數從傳統的9次減少到4次，大幅降低了重傳次數。每次組合對應的編碼列表 CodingList可通過控制信道發送給各用戶，以便其進行網絡譯碼。同時，通過觀察可知：當廣播數據包足夠多時，根據XNCC策略得到的網絡編碼包數等于所有用戶丟包個數的最大值。用戶數目為2時，結論顯然成立，當用戶數目增加時也是如此。因針對任一用戶，每次編碼組合只能重傳一個數據包，則所需的重傳次數取決于丟包率最大的用戶[14]，故網絡編碼組合次數等于最大丟包數，這為第4節的性能分析提供了依據。

2.2 聯合網絡-信道譯碼

用戶端重傳階段的聯合網絡-信道譯碼結構如圖3所示，用戶從控制信號獲取參與網絡編碼的數據包 ID，從數據包緩存中取出對應的數據包進行XOR操作、添加CRC校驗、交織后進行RSC信道編碼。這里的CRC校驗、交織方式、RSC方式均與基站發送端的相同，目的是重構基站數據包(除丟失信息外)的編碼過程，使用戶能從本地解調數據中根據得到的編碼信息，軟判決出丟失包的重傳信息。通過網絡譯碼得到丟失包的重傳信息后，首先進行單獨的 RSC譯碼，若不成功，則聯合先前軟信息緩存中的校驗位進行Turbo譯碼。既然廣播階段的數據譯碼錯誤，表明其已經歷嚴重的衰落，故不能利用其信息位進行分集合并，只能利用校驗位進行碼字合并譯碼。然而Turbo譯碼必需的是每個解調數據的對數似然比(LLR)，怎樣從網絡編碼包中提取重傳數據每個比特的 LLR值是一個不可避免的問題。

圖3 重傳階段的聯合網絡-信道譯碼結構

3 中繼廣播模型及方案擴展

實施機會中繼的具體方法是每個基站/中繼站采用最小信道增益h的倒數當作倒計時器的初始值，選擇計時器最先歸零的基站/中繼站進行重傳。當選定某一中繼站重傳時，其內部的NC-HARQ III型編碼廣播方案與基站處的相同。采用中繼站進行重傳的目的是，進一步降低重傳階段的誤包率，以減少重傳次數。需要注意的是：當用戶數目增多時，機會中繼帶來的誤包率性能增益逐漸減小。

4 性能分析

圖4 中繼站的編碼重傳結構

時分復用系統中，因系統的傳輸延時取決于數據的傳輸次數，所以本文衡量的性能指標是平均每一源數據包傳輸至所有用戶終端所需要的傳輸次數。傳統的HARQ I型重傳機制下，基站對數據添加 FEC編碼后廣播發送，用戶根據本次接收數據進行譯碼。鏈路層采用網絡編碼的HARQ I型方案(NC-HARQ I)中，基站根據XNCC策略選擇合適的重傳包，網絡編碼后添加 FEC編碼，用戶也只是根據本次接收數據信道譯碼，再通過網絡譯碼得到重傳數據。選取上述兩種方案與本文所提NC-HARQ III型廣播方案進行對比，是要分別驗證網絡編碼技術和聯合網絡-信道譯碼設計帶來的時延增益。

基站要發送K個數據包至N個用戶終端。設采用RSC信道編譯碼進行首次廣播的誤包率為Pb，則 HARQ I型重傳模式的誤包率也始終為Pb。設HARQ III型冗余重傳模式下第i次重傳的誤包率為Pri，由于采取聯合譯碼，顯然誤包率會逐次降低，即Pb＞Pr1＞Pr2＞Pr3…。為分析方便，這里取Pr1為HARQ III型冗余重傳模式下的誤包率，并假設每個用戶終端的誤包率相同。

HARQ I型方案中，一個數據包的平均傳輸次數L1為[7]

網絡編碼方案中，定義平均傳輸次數為L(Pb,Pr) ，其中Pr為重傳階段的誤包率。廣播階段，每一用戶的錯誤包數為KPb，由第2.1節的分析可知：需要重傳的網絡編碼包數即為KPb。因XNCC策略根據HARQ反饋實時進行動態編碼，且每次編碼都能服務一次指定用戶，故此時網絡編碼包的重傳次數相當于基站發送KPb個數據包到單一指定用戶的傳輸次數，重傳次數Lr為

所需平均傳輸次數L(Pb,Pr)為

故NC-HARQ I型方案的平均傳輸次數為L(Pb,Pb) ,NC-HARQ III型方案的平均傳輸次數為L(Pb,Pr1)。

5 仿真驗證

基站廣播104個數據包至10個用戶終端，每數據包長度為200 bit(含CRC校驗)，信道編碼采用碼率為1/2的(37, 21)RSC編碼，BPSK調制發送，Turbo譯碼采用MAP算法，且均為8次迭代。仿真環境為疊加高斯白噪聲的瑞利慢衰落信道，廣播或重傳階段經過RSC編碼的400 bit經歷相同的信道衰落。假設基站/中繼站針對每一用戶具有相同的發送信噪比SNR。

圖5反映了在廣播階段RSC譯碼錯誤的情況下，3種HARQ機制首次重傳的誤包率。其中HARQ II型經過兩次重傳發送了 RSC編碼的全部信息位和校驗位，這樣保證其重傳數據也為400 bit，其中信息位與緩存數據的信息位進行等增益分集合并，校驗位采用碼字合并進行聯合Turbo譯碼。為方便下文引用，對應的誤包率曲線在圖示中用P1,P3,P1r,P3r來標志。由圖 5可以看出：在低信噪比(SNR ＜4 dB)時，HARQ II型重傳機制由于采用合并譯碼技術，誤包率要好于HARQ I型機制；當信噪比增加時，若廣播階段仍譯碼錯誤，表示其首次廣播數據衰落較嚴重，即使增加冗余信息也難以爭取譯碼；HARQ III型重傳數據包的誤包率始終好于其它兩種HARQ機制。針對存在6個中繼節點的情況，仿真表明機會中繼策略能顯著降低重傳數據包的誤包率。

圖6反映了傳統的HARQ I型方案，融合網絡編碼的NC-HARQ I型方案以及NC-HARQ III型方案，在圖6所示誤包率的基礎上，平均每一源數據包傳輸至所有用戶終端所需要的傳輸次數，圖示中的P1,P3,P1r,P3r分別對應圖5中的誤包率。NC-HARQ I型方案與HARQ I型方案相比，傳輸次數的減少得益于網絡編碼機制(XNCC策略)在減少重傳次數方面的潛在優勢。NC-HARQ III型方案與NC-HARQ I型方案相比，傳輸次數的減少應歸功于JNCD設計帶來的更低的誤包性能。存在6個中繼站時，兩方案下平均傳輸次數套用式(5)可得：L(P1 ,P1r),L(P1 ,P3r)，仿真表明機會中繼策略能有效降低重傳次數。

圖7反映了信噪比設定為2 dB的情況下，3種傳輸方案中平均傳輸次數隨用戶終端數目增加的變化情況。傳統的HARQ I型重傳方案中，當用戶終端數目增加，所需平均傳輸次數快速增加；采用網絡編碼后，平均傳輸次數與終端數目無關。可見采用網絡編碼的重傳方案更適用于用戶密集的場景。中繼廣播模型下，隨著用戶終端數目的增加，所需平均傳輸次數趨近于無中繼模型，這主要是因為隨著用戶終端數目的增加，機會中繼帶來的誤包率性能增益越來越小。

6 結論

圖5 針對某一用戶廣播階段的丟失包不同HARQ機制首次重傳的誤包率

圖6 不同重傳方案下的平均傳輸次數

圖7 不同重傳方案下的平均傳 輸次數隨用戶數目的變化情況

本文提出了聯合網絡編碼的III型HARQ廣播系統跨層設計方法，其主要思想是在重傳階段，利用XNCC策略XOR重傳數據包，一方面使每次編碼包的重傳能服務于多個用戶，減少重傳次數；另一方面通過聯合網絡-信道譯碼設計，降低誤包率。本文進一步利用機會中繼的思想，將提出的 NCHARQ III機制擴展到中繼廣播系統。在不同HARQ類型丟包率的仿真基礎上，論文推導出聯合網絡編碼設計時廣播系統的所需平均傳輸次數，并通過仿真對比了采用網絡編碼和不同 HARQ類型進行聯合設計時的延時性能。數值分析和仿真表明：所提NC-HARQ III型廣播方案，較傳統的HARQ I型或NC-HARQ I型廣播方案，能有效減少重傳次數，獲得顯著的時延增益。

[1]Cheng J. Coding performance of hybrid ARQ schemes [J].IEEE Transactions on Communications, 2006, 54(6):1017-1029.

[2]Garg D, Kimura R, and Adachi F. RCPT hybrid ARQ with limited number of retransmissions in DS-CDMA[J].Electronic Letters, 2003, 39(2): 241-242.

[3]劉鋒, 黃生葉, 馮穗力, 等. 新型的基于信道狀況的自適應HARQ方案[J]. 計算機工程與應用, 2010, 46(8): 99-102.

Liu Feng, Huang Sheng-ye, Feng Hui-li,et al.. Novel adaptive HARQ system based on channel condition [J].Computer Engineering and Applications, 2010, 46(8): 99-102.

[4]Ahlswede R, Cai N, Robert Li S Y,et al.. Network information flow [J].IEEE Transactions on Information Theory, 2000, 46(4): 1204-1216.

[5]Katti S, Rahul H, Hu W,et al.. XORs in the air: practical wireless network coding [J].IEEE/ACM Transactions on Networking, 2008, 16(3): 497-510.

[6]Gollakota S and Katabi D. ZigZag decoding: combating hidden terminals in wireless networks[C]. SIGCOMM’08,Washington, USA, Aug. 2008: 159-170.

[7]Ahmed E, Eryilmaz A, Medard M,et al.. On the scaling law of network coding gains in wireless networks[C]. IEEE MILCOM 2007, Orlando, USA, Oct. 2007: 1-7.

[8]Ding Z, Zheng M, and Leung K K. Impact of network coding on system delay for multisource-multidestination scenarios[J].IEEE Transactions on Vehicular Technology, 2010, 59(2):831-841.

[9]Dong N, Tran T, Nguyen T,et al.. Hybrid ARQ-random network coding for wireless media streaming [C].International Conference on Communications and Electronics (ICCE) 2008, Hoi an Vietnam, Jun. 2008:115-120.

[10]肖瀟, 王偉平, 楊路明, 等. 基于網絡編碼的無線網絡廣播重傳方法[J]. 通信學報, 2009, 30(9): 69-75.

Xiao Xiao, Wang Wei-ping, Yang Lu-ming,et al.. Wireless broadcasting retransmission approach based on network coding [J].Journal on Communications, 2009, 30(9): 69-75.

[11]Liu Y, Feng Z, and Zhang P. A novel ARQ scheme based on network coding theory in cognitive radio networks [C]. IEEE International Conference on Wireless Information Technology and Systems (ICWITS) 2010, Honolulu, USA,Aug. 2010: 1-4.

[12]Hong S K and Chung J M. Network-coding-based hybrid ARQ scheme for mobile relay networks [J].Electronics Letters, 2010, 46(7): 539-540.

[13]Vien Q T, Tran L N, and Nguyen H X. Network coding-based ARQ retransmission strategies for two-way wireless relay networks [C]. Softcom 2010, Split Jugoslavia,Sept. 2010: 180-184.

[14]Peng Q, Zhang T, and Cuthbert L. Research on network coding based hybrid-ARQ scheme for wireless networks [C].IEEE International Conference on Communication Systems(ICCS) 2010, Singapore, Nov. 2010: 218-222.

[15]Bletsas A, Khisti A, Reed D P,et al.. A simple cooperative diversity method based on network path selection [J].IEEE Journal on Selected Areas in Communications, 2006, 24(3):659-672.