基于噴泉碼的多跳中繼通信

茍 亮，徐志平，宋普星

(中國人民解放軍96862部隊，河南 洛陽 471003)

0 引言

在空間信息網絡等大尺度時空環境下，信息傳輸面臨損耗大、時延長、接收信噪比極低、節點能量等資源受限的窘境。通過多跳中繼，各節點能以更小的發射功率實現更可靠的信息傳輸，同時多跳中繼傳輸還能增加信道容量，減小信號間干擾，延長電池使用時間和壽命[1-2]，有效解決大尺度時空網絡中數據的遠距離傳輸難題。

在使用噴泉碼的系統中，只要收集到足夠的源節點信息編碼包，任何節點都能夠重構源節點信息[3-5]。所以，在采用噴泉碼的中繼網絡系統中，處于路由路徑上的中繼節點只要收集到足夠的源節點信息編碼包，就能夠譯出原始信息并輔助源節點進行信息的傳輸，因此噴泉碼非常適用于中繼網絡[6-9]。近年來，一些文獻已經對噴泉碼應用在中繼網絡的吞吐量性能進行了分析[10-12]。在這些系統中，各中繼節點作為獨立的噴泉碼編譯碼器，在成功譯碼源信息后重新編碼并發送信息，這一過程持續到源節點信息被目的節點成功接收[13-15]。在文獻[16]中，Tran Trung Duy等提出了基于噴泉碼的多種多跳協同傳輸協議，減小了端到端傳輸時延。Ashish James等人分析了噴泉碼在時延受限多跳無線中繼網絡中的性能及吞吐量-平均時延均衡問題，其得出的結論是：在一固定的源-目的節點對之間增加中繼節點能夠提高多跳網絡傳輸的可靠性，但是會降低系統吞吐量，要選取適當的中繼傳輸跳數和每跳傳輸次數以最小化總時延和數據包的丟失。

以上基于噴泉碼的多跳中繼傳輸網絡中，均假設每個節點在發送數據時都具有廣播特性，因此能充分利用該特性實現節點之間的協同傳輸。然而，在大尺度時空網絡中，由于信息傳輸距離遠，為了提高接收信噪比，傳輸節點之間一般不采用全向天線，而是采用定向增益大的定向天線，以將發送功率集中在下一跳節點所在方向上，信息傳輸一般不具有廣播特性，利用協同傳輸的可能性不大。因此，本文將在沒有協同傳輸背景的條件下，對基于噴泉碼的多跳傳輸協議及其性能進行分析和研究，實現信息的高效可靠傳輸。

1 系統模型

N跳中繼傳輸模型在如圖1所示，其中節點0為源節點，節點N為目的節點，節點1,2,…,N-2,N-1為N-1個中繼節點，節點i-1和節點i之間的數據包刪除概率為pi。

假設源節點發送一個數據塊給目的節點N，該數據塊包含M個原始數據包P={P1,…,PM}。源節點0將M個數據包使用隨機網絡編碼和LT碼進行編碼，然后再發送給中繼節點，中繼節點依次進行數據包的編碼和傳輸，直到目的節點成功譯出原始數據包。與文獻[17-18]中一樣，在中繼節點和目的節點上，只要接收至少M個線性無關編碼數據包，就能成功譯出原始數據包。

圖1 N跳中繼傳輸模型

假設：為了性能分析和評估的方便，假設各接收節點(節點1,2,…,N)能向上級節點發送ACK數據反饋狀態信息，且狀態信息在反饋信道中不存在丟失。

假設：對于一個收發節點對，一個時隙能傳輸一個數據包。

假設：各跳路徑之間的信道是互相獨立的。

假設：在傳輸一個數據包的時隙內，發送節點和接收節點之間的鏈路狀態不變，即丟包率不發生變化。

假設：所有節點均安裝高增益定向收發天線，既可工作在半雙工狀態，也可工作在雙工狀態。

假設：每跳節點之間的信號傳播時延為0。

2 協議設計

2.1 協議A

步驟1：源節點不斷生成編碼數據包，逐跳中繼轉發到目的節點。

步驟2：當目的節點收集到足夠的編碼包，并成功譯碼后，目的節點逐跳回傳ACK信息直至源節點。

步驟3：每一個接收到ACK信息的節點立即停止數據包的發送。

步驟4.源節點在接收到ACK信息后停止該數據塊的發送或開始下一個數據塊的發送。

2.2 協議B

步驟1：源節點生成編碼數據包，通過中繼節點1,2,…,N-2,N-1逐跳轉發。

步驟2：節點i在成功譯出節點i-1發送的編碼包后，發送ACK信息給節點i-1，再重新編碼轉發新的編碼包給節點i+1；節點i-1接收到ACK信息后，停止編碼數據包發送或開始下一個數據塊編碼包的傳輸。

步驟3：在每一個中繼節點執行步驟2直至節點N成功譯碼，節點N發送ACK信息給節點N-1，該數據塊的傳輸結束。

2.3 協議C

步驟1：源節點生成編碼數據包，通過中繼節點1，2，…，N-2,N-1逐跳轉發。

步驟2：在逐跳轉發過程中，節點i(i=1,2,…,N-1)接收節點i-1發送的編碼包，如果節點i收集到足夠的編碼包并成功譯碼，則將譯出的原始數據包重新編碼后再轉發，并發送ACK信息給節點i-1，節點i-1停止該數據塊的傳輸；如果節點i沒有成功譯碼，則直接轉發從節點i-1接收到的數據包給節點i+1。

步驟3：當目的節點N接收到足夠的編碼包并成功譯碼后，回傳ACK信息給節點N-1，該數據塊的傳輸結束。

3 性能分析

本節將對各協議在確定數據包數目、傳輸跳數和數據包刪除概率下的傳輸次數和傳輸時延兩個性能指標進行分析。

3.1 協議A

在協議A中，源節點不斷產生編碼數據包，中間節點只負責轉發這些編碼包，而不進行存儲和譯碼。一個編碼包從源節點0發出，只有每一跳都傳輸成功，該編碼包才能經過N跳到達目的節點N。在傳輸過程中，第i跳成功傳輸的概率為1-pi。因此，N跳傳輸都成功的概率為:

(1)

總的數據包刪除概率為:

(2)

采用隨機網絡編碼，當編碼所用有限域足夠大時，編碼包之間線性獨立的概率趨近于1。假設發送的所有編碼包之間都是線性獨立的，那么節點N要譯出所有的原始數據包，則至少需要正確接收到M個數據包。因此傳輸M個數據包，源節點需要發送的總的數據包數目，即源節點的傳輸次數為:

(3)

(4)

同理，節點i傳輸M個數據包給目的節點所需要的總的傳輸次數為

(5)

因此，系統總的傳輸次數為

(6)

總傳輸時延為源節點發送的次數及節點1到目的節點的跳數之和，即

(7)

(8)

(9)

3.2 協議B

在該協議中，每一跳傳輸都是在成功譯碼后才開始下一跳傳輸。因此該協議傳輸次數和時延相同。第i跳所需的傳輸次數為：

(10)

因此總的傳輸次數為：

(11)

總時延為：

(12)

與協議A分析相同，基于LT碼和協議B的多跳傳輸性能為：

(13)

(14)

3.3 協議C

協議C與協議B的主要區別是協議C的節點都可工作在雙工模式，中繼節點不是等待完全譯碼才進行下一跳編碼傳輸，而是在完全譯碼之前在線轉發，因此其工作效率更高。協議C總的傳輸次數與協議B相同，為：

(15)

在協議C中，源節點0總共發送M/(1-p1)個數據包，所用時隙為M/(1-p1)。從統計上來說，在節點i-1未成功譯碼之前的任何時刻，節點i成功接收的編碼包數目是節點i-1的(1-pi)倍。因此，節點1成功譯碼的時候，節點2所接收的線性無關編碼包為M(1-p2)個，還有Mp2個數據包需要從節點1獲取，因此節點1在成功譯碼后發送數據包的個數和傳輸時隙為Mp2/(1-p2)。同樣，當節點i-1成功譯碼后，它還要發送Mpi/(1-pi)個數據包給節點i，耗費Mpi/(1-pi)個時隙。因此，對于N跳中繼傳輸和協議C，總的傳輸時延為：

(16)

與協議A分析相同，基于LT碼和協議C的多跳傳輸次數為：

(17)

總的傳輸時延為：

(18)

4 仿真與分析

為了驗證各協議的傳輸性能，進行了一系列仿真，通過仿真評估平均傳輸次數、平均傳輸時延與傳輸跳數、數據包數目、丟包率之間的關系。在仿真過程中，假設RNC方案的有限域為Fq(q=28)，LT編碼方案的編碼參數為c=0.03，δ=0.2，所有節點發出的LT編碼包均服從RSD分布。通過蒙特卡洛仿真得到仿真結果的統計平均值。

圖2給出了RNC各協議的平均傳輸次數和平均傳輸時延隨跳數變化比較的情況，仿真設置參數為數據包數目M=50，丟包率p=0.3，跳數H從1～5變化。

圖2 RNC在跳數變化情況下的傳輸性能

從圖2(a)的仿真結果可以看出，協議B和C在跳數逐漸增大的情況下傳輸次數小于協議A，且隨著跳數的增加，協議B和C的傳輸次數線性增加。這是因為協議A中的所有數據包都必須通過系統中所有的中繼節點轉發，從而增加了數據包丟失的概率。圖2(b)中協議B的傳輸時延最大，這是因為協議B中所有的中繼節點都是譯碼成功后再重新編碼轉發，并非在線轉發一些已接收到的數據包。協議C的傳輸時延最小，且協議B和C的傳輸時延是線性變化，而協議A則指數增加。隨著跳數的逐步增加，協議A的傳輸時延將超過協議B。

圖3給出了RNC各協議的平均傳輸次數和平均傳輸時延隨數據包數目變化比較的情況，仿真設置參數為跳數H=3，丟包率p=0.3，數據包數目M從10～50變化。

圖3 RNC在數據包數目變化情況下的傳輸性能

從圖3(a)的仿真結果可以看出，協議B和C的傳輸次數小于協議A，且三個協議所得到的平均傳輸次數隨著數據包數目變化沒有顯著變化。在圖3(b)中，當傳輸跳數為3時，協議B的傳輸時延最大，協議A次之，協議C最小，且所有協議的平均傳輸時延與平均傳輸次數一樣隨著數據包數目變化基本不變。

圖4給出了RNC各協議的平均傳輸次數和平均傳輸時延隨丟包率變化比較的情況，仿真設置參數為數據包數目M=50，傳輸跳數H=3，丟包率p從0.1～0.5變化。

圖4 RNC在丟包率變化情況下的傳輸性能

從圖4(a)的仿真結果可以看出，協議B和C在丟包率逐漸增大的情況下平均傳輸次數小于協議A，且隨著跳數的增加，協議B和C的傳輸次數增加較慢，而協議A的傳輸次數增加較快，這是因為協議A中數據包要通過每跳中繼節點，隨著每跳丟包率的增加，總的丟包率也迅速增大。圖4(b)中協議B的傳輸時延在丟包率較小時最大，協議A次之，但隨著丟包率的增大，協議A的平均傳輸時延迅速超過協議B，其原因與上述一樣，協議C是三個協議中傳輸時延最小的。

圖5給出了LT碼各協議的平均傳輸次數和平均傳輸時延隨跳數變化比較的情況，仿真設置參數為數據包數目M=50，丟包率p=0.3，跳數H從1～5變化。圖中的曲線變化情況和性能分析與圖2相似。

圖6給出了LT碼各協議的平均傳輸次數和平均傳輸時延隨數據包數目變化比較的情況，仿真設置參數為跳數H=3，丟包率p=0.3，數據包數目M從10～50變化。圖中的曲線變化情況和性能分析與圖3相似。

圖5 LT碼在跳數變化情況下的傳輸性能

圖6 LT碼在數據包數目變化情況下的傳輸性能

圖7給出了LT碼各協議的平均傳輸次數和平均傳輸時延隨丟包率變化比較的情況，仿真設置參數為數據包數目M=50，傳輸跳數H=3，丟包率p從0.1～0.5變化。圖中的曲線變化情況和性能分析與圖4相似。

圖7 LT碼在丟包率變化情況下的傳輸性能

圖8給出了RNC和LT編碼各協議的傳輸性能隨跳數變化的比較情況，仿真設置參數為數據包數目M=50，傳輸跳數H從1～5變化，丟包率p=0.3。從圖8(a)可以看出，RNC編碼和LT編碼方案的平均傳輸次數隨中繼跳數變化的趨勢基本相同。而且從3種協議的仿真中可以看出，RNC編碼方案的性能都略優于LT編碼方案，這是因為RNC方案在有限域設置較大時每個編碼包的編碼系數基本都能保持線性獨立，而LT碼的編碼系數只有0和1，每個編碼包編碼系數保持線性獨立和滿足可解性條件的概率要低一些。圖8(b)中RNC編碼和LT編碼方案的平均傳輸時延變化趨勢也基本相同，且RNC編碼方案的平均傳輸時延都小于LT編碼方案，但差距不大。由于LT編解碼復雜度隨數據包數目而線性增加，而RNC方案則指數增加。因此，在節點處理能力有限的情況下，LT編碼方案更可取。

圖8 RNC和LT碼在跳數變化情況下的傳輸性能

RNC編碼方案和LT編碼方案性能隨數據包數目、丟包率變化比較的情況與圖8類似，RNC編碼方案的性能均略優于LT編碼方案的性能，這里不再作贅述。

由以上的理論和仿真分析可以得出：協議C的傳輸效率和傳輸時延都要優于協議A和B，因此無論是從能量效率還是時延的角度看，協議C都是最佳方案；協議A的傳輸效率最低，其傳輸時延在跳數較少的情況下也大于協議B，且源節點要不斷產生編碼包和發送編碼包，增加了源節點的負荷，因此不可取。但協議C要求每個節點都具有雙工功能，這樣會增加中繼節點的復雜度。為了適應節點的不同功能和配置，對于中繼節點不具有雙工功能且跳數較少的網絡背景，可以采用協議B的工作模式。而對于信息傳輸路由中既有雙工節點又有半雙工節點的情況，可以采用協議B和C的混合協議，即在半雙工節點處采用協議B，在全雙工節點處采用協議C，半雙工節點就充當了協議C中的臨時目的節點。這樣以半雙工節點進行分割，實施分段傳輸，從而兼顧節點功能配置情況和傳輸性能。

5 結束語

針對多跳中繼傳輸距離遠、時延長、接收信噪比低等特點，建立了多跳傳輸模型，提出采用噴泉碼進行多跳中繼信息傳輸的方案。對3種基于噴泉碼的多跳中繼傳輸協議進行了研究，并分別對傳輸次數和傳輸時延進行了分析和仿真。研究結果表明，基于RNC編碼和全雙工在線傳輸協議的傳輸方案效率更高、時延更小；基于LT編碼的協議傳輸性能稍次于RNC編碼，但LT碼編譯碼復雜度更低。在進行方案和協議的選取時，要綜合考慮節點能量、工作模式、處理能力等多方面因素，研究最佳方案和協議組合，以實現高效可靠的多跳中繼信息傳輸。

[1] Frodigh M,Parkvall S,Roobol C,et al.Future Generation Wireless Networks[J].IEEE Personal Communications,2001,8(5):10-17.

[2] Mohapatra P,Li J,Gui C.QoS in Mobile Ad Hoc Networks[J].IEEE Wireless Communications,2003,10(3):44-52.

[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] Nikjah R,Beaulieu N C.Achievable Rates and Fairness in Rateless Coded Relaying Schemes[J].IEEE Transactions on Wireless Communications,2008,7(11):4439-4444.

[5] Gummadi R,Sreenivas R S.Relaying a Fountain Code across Multiple Nodes[C]∥Proc.of SIGCOMM’08.Seattle,Washington,USA,2008:149-153.

[6] James A,Madhukumar A S,Adachi F.Throughput Optimization in Rateless Coded Cooperative Relay Networks[J].IEICE Transactions on Communications,2012,95(5):1810-1814.

[7] James A,Madhukumar A S,Kurniawan E.Performance Analysis of Fountain Codes in Multihop Relay Networks[J].IEEE Transactions on Vehicular Technology,2013,62(9):4379-4391.

[8] Castura J,Mao Y.Rateless Coding for Wireless Relay Channels[J].IEEE Transactions on Wireless Communications,2007,6(5):1638-1642.

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

[10] Huang J X,Fei Z S,Cao C Z,et al.On-Line Fountain Codes With Unequal Error Protection[J].IEEE Communications Letter,2017,21(6):1225-1228.

[11] Sun K,Wu D P.MPC-based Delay-Aware Fountain Codes for Live Video Streaming[C]∥IEEE ICC’2016,Kuala Lumpur,Malaysia,2016:1-6.

[12] Abbas WB,Casari P,Zorzi M.Controlled Flooding of Fountain Codes[J].IEEE Transactions on Wireless Communications,2017,16(7):4698-4710.

[13] Sun K,Zhang H X,Wu D P,et al.MPC-based Delay-Aware Fountain Codes for Real-Time Video Communication[J].IEEE Internet of Things Journal,2018,5(1):415-424.

[14] Hohmann F,Klein A.Opportunistic Forwarding Using Rateless Codes in OFDMA Multihop Networks[C]∥IEEE 84th VTC-Fall,Montreal,QC,Canada,2017:1-5.

[15] Rajanna A,Haenggi M.Enhanced Cellular Coverage and Throughput Using Rateless Codes[J].IEEE Transactions on Communications,2017,65(5):1899-1912.

[16] Duy T T,Anpalagan A,Kong H Y.Multi-Hop Cooperative Transmission Using Fountain Codes over Rayleigh Fading Channels[J].Journal of Communications and Networks,2012,14(3):267-272.

[17] James A,Madhukumar A S,Kurniawan E,et al.Performance Analysis of Fountain Codes in Multihop Relay Networks[J].IEEE Transactions on Vehicular Technology,2013,62(9):4379-4391.

[18] James A,Madhukumar A S,Kurniawan E,et al.Spectrally Efficient Packet Recovery in Delay Constrained Rateless Coded Multihop Networks[J].IEEE Transactions on Communications,2013,61(11):4462-4474.