時變信道下線性網絡分批稀疏碼秩分布研究

王士恒，劉恒，唐林，蘇金領，張瑞琦

（1. 西南交通大學信息編碼與傳輸省重點實驗室，四川 成都 611756；2. 現代交通通信與傳感網絡國家級國際聯合研究中心，四川 成都 611756;3. 中國電子科技集團第三十研究所，四川 成都 610031）

0 引言

在無線網絡中，從源節點到宿節點之間的直接鏈路往往是不可達的，因此多跳的通信方式變得十分重要。在多跳通信網絡中，部分節點作為網絡中間節點通過逐跳轉發的方式將接收的數據包傳輸到宿節點。由于噪聲、干擾或者信道失真等影響，在多跳網絡中傳輸的數據包仍然可能以一定概率出現丟包的現象，此時可使用網絡編碼[1]處理丟包問題。

作為多跳網絡中的一種新型信道編碼方案，同時也是傳統隨機線性網絡編碼（random linear network coding, RLNC）[2]的加強型方案，分批稀疏（batched sparse，BATS）碼是一種能夠在丟包網絡中改進網絡性能的編碼方案[3]。分批稀疏碼提供了一個兩段式編碼框架，源節點處的外碼（噴泉碼的矩陣形式）在理論上可以生成無限數量的批次數據包（batch），而內碼（采用線性網絡編碼）則在網絡中間節點處對屬于同一個批次的數據包進行再次編碼。分批稀疏碼適用于任何允許在中間節點上進行線性網絡編碼的網絡。由于端到端的操作為線性編碼，因此分批稀疏碼對動態網絡拓撲和丟包具有魯棒性。此外，分批稀疏碼可以在較小的有限域下運行，相比之下，現有的隨機線性網絡編碼雖然可以使網絡吞吐量達到網絡容量[4-5]，但也需要較大的場大小去保證傳輸矩陣為滿秩。分批稀疏碼解決了基于塊的方法的順序調度的反饋問題：由于無速率的特性，批次的順序調度不需要反饋。同時，分批稀疏碼解決了基于噴泉碼的方法的度分布問題，因為分批稀疏碼的內碼不會改變批次的度值[3]。

與傳統的隨機線性網絡編碼相比，分批稀疏碼能夠顯著降低編碼開銷和譯碼復雜度[6]，同時由于不再需要為每個數據包發送ACK/NACK 反饋信息，分批稀疏碼的無速率特性還能明顯簡化傳輸協議[7]。另外，分批稀疏碼在網絡中間節點僅需要進行有限域運算，因此BATS 碼適用于網絡中間節點存儲空間有限、數據傳輸量巨大且對時延敏感的數據傳輸場景[6]。同時，對不同的5G應用場景[8]，如增強型移動寬帶（enhanced mobile broadband，eMBB），結合丟包率、時延等性能指標要求以及節點處理能力，也可以有針對性地設計相應的分析稀疏碼傳輸協議。

目前，國內外諸多學者在許多方面對BATS碼進行了研究與優化。Yang 等[9]首先提出了一種簡單的支持分批稀疏碼的網絡協議，稱為BATS-Pro-0，該協議由上到下將信息傳輸的框架分為應用層、傳輸層、網絡層、鏈路層和物理層，演示了如何使用分批稀疏碼在網絡中進行通信，并為后續的研究提供了一個最基本的協議。

由于秩分布決定了數據傳輸的最大可達速率，因此秩分布是在分析分批稀疏碼性能時的一個十分重要的參數，目前已有相關文獻研究了分批稀疏碼在不同網絡拓撲和結構下的秩分布。Yang 等[7]基于BATS-Pro-0 協議，研究分析了RLNC 重編碼作為內碼編碼方案時分批稀疏碼的歸一化秩期望，并提出了一個批的秩在網絡中的每個節點上形成一個馬爾可夫鏈[7]，推導得到刪除信道下RLNC 重編碼的最大可達速率，即在批次數足夠大的情況下，該速率會收斂到一個常數，該數值只隨丟包率變化。之后Yang 等[7]對RLNC 重編碼進行改進，提出系統重編碼作為內碼編碼的方案并分析其秩分布。該方案在批次數足夠大的情況下與RLNC 重編碼的最大可達速率相同，但在批次數較小時有著更明顯的優勢。作為一種新的編碼技術，其在計算開銷和重編碼時延上都要低于RLNC 重編碼，同時在相同節點上的秩期望也更大，因此，以系統重編碼作為分批稀疏碼的內碼會獲得較RLNC 重編碼更優的性能。同時根據線性重編碼，Yin 等[10]提出了自適應重編碼方案，Yang 等[7]提出了一個批在下一跳上的秩期望，Yue 等[6]在此基礎上研究了兩種能夠應用于工業互聯網上行鏈路的分布式分批稀疏碼的秩期望。

網絡編碼可分為確定網絡編碼和隨機網絡編碼。為了能夠設計出高效的確定網絡編碼，通常需要獲取信道狀態的相關信息[11]。而隨機線性網絡編碼達到較高的編碼增益的代價是較高的編碼開銷[12]。為了降低編碼開銷，各種稀疏隨機線性網絡編碼方案被提出[13-16]。

Sehat 等[17]分析了稀疏矩陣秩的概率分布，指出稀疏網絡編碼的提出正是為了解決犧牲通信負載而造成的巨大計算復雜度的問題。Li 等[18]也研究了稀疏隨機線性網絡編碼傳輸矩陣非奇異的概率。此外，Li 等[19]分析了稀疏隨機線性網絡編碼譯碼失敗概率，將求解譯碼失敗概率問題轉換為隨機傳輸矩陣秩分布問題，而該問題同樣可以通過矩陣零模式來解決，得到秩分布的上限和下限，進而可以得到譯碼失敗概率。

然而上述文獻的研究都基于時不變信道，即假定各條鏈路上的丟包率均為常數。正如前文所述，分批稀疏碼是一種多跳信道編碼機制，該機制不僅能夠應用在固定節點上，同樣也適用于移動節點。而在節點移動的場景下，鏈路的丟包率將很難保持恒定不變。本文作者在文獻[20]中提出了時變信道下的分批稀疏碼傳輸模型，討論了網絡中間節點使用RLNC 重編碼時，分批稀疏碼在時變信道下的秩分布，在該信道下，各鏈路上的丟包率假定為隨機變量而不是固定值?；诖耍疚倪M一步對時變信道下分批稀疏碼的秩分布展開研究，重點研究了鏈路丟包率服從有限區間正態分布時的秩分布且階數k為任意值時，RLNC和系統重編碼的歸一化秩期望的通用閉合解。

1 分批稀疏碼

1.1 外碼編碼

分批稀疏碼是隨機線性網絡編碼的加強型方案，該編碼方案分為外部和內碼兩部分。外碼在源節點處生成批Xi，一個包含M個已編碼數據包的批通常利用K個輸入數據包的子集生成，即：

其中，M列矩陣Gi是第i個批的生成矩陣，而Bi則是K個輸入數據包的一個子集。令dgi表示第i個批的度，即批中原始數據包的個數。一般情況下，批的度為一個隨機數，其服從的隨機分布稱為度分布，度分布是在設計分批稀疏碼外碼時的一個十分重要的參數。

1.2 內碼編碼

內碼編碼是指在網絡中間節點將接收的屬于同一個批的數據包進行重編碼，將得到的編碼數據包轉發至下一節點。

分批稀疏碼的內碼通常采用隨機線性網絡編碼的重編碼方案，該方案有較大的計算開銷和重編碼時延。

文獻[7]提出了基于系統重編碼（systematic recoding）的內碼方案。作為一種新的編碼技術，系統重編碼在計算開銷和重編碼時延上都要低于RLNC 重編碼，同時在相同節點上的秩期望也更大，因此，以系統重編碼作為分批稀疏碼的內碼會獲得比RLNC 重編碼更優的性能。在系統重編碼的內碼方案中，假設網絡中間節點接收k*個屬于同一個批的數據包，r是k*個數據包中線性無關數據包的數量。令M'表示系統重編碼生成并轉發至下一節點的數據包數量。系統重編碼按照如下步驟進行。

步驟1 從接收的數據包中選擇r個線性無關的數據包作為重編碼數據包的一部分。

步驟2 從步驟1 選擇的r個線性無關的數據包中使用隨機線性網絡編碼生成 'M-r個編碼數據包。

鏈路間的丟包率可建模為對角矩陣E，其中，對角線元素為0 的概率對應鏈路上的丟包率ε。中間節點的系統重編碼矩陣為Φ，其中Φ的前r列構成一個單位矩陣，后 'M-r列中的元素在有限域內隨機取值[3]。因此，第n個節點收到的數據包Y為：

2 時變信道下的歸一化秩期望分析

2.1 時不變信道下的歸一化秩分布

文獻[7]討論了在時不變信道下基于線性重編碼的分批稀疏碼的歸一化秩分布。在一個長度為l的線性網絡中，其中R0表示源節點，Rl表示宿節點。令πn,n= 0,1,… ,l表示一個批在第n個節點處的秩分布，其是一個含M+1 個元素的向量，且一個批在節點Rn,n= 0,1,… ,l處的秩形成一個馬爾可夫鏈。假設P表示重編碼時該馬爾可夫鏈的概率轉移矩陣，因為數據包在傳輸過程中，其轉移矩陣H的秩不可能增大，所以P為下三角矩陣。若所有節點使用相同的重編碼方案生成M個數據包發送至下一節點，則：

并有π0[M] = 1。因此要計算在第n個節點Rn處的秩分布πn，僅需要計算概率轉移矩陣P。設宿節點lR接收r個數據包，則其歸一化秩期望可表示為：

2.2 時變信道下的歸一化秩分布

式（13）表明，若要計算節點nR的秩，需要結合具體的重編碼方案與概率密度分布函數進行分析，因此，本文將基于不同的信道條件以及不同重編碼方式對線性網絡中的分批稀疏碼秩分布進行分析。

2.3 有限區間正態分布

在時變信道中，鏈路上的丟包率總是分布在有限區間，因此本文假設ε服從有限區間正態分布，其概率密度分布函數fk(ε)為：

其中，k、a和μ分別表示有限區間正態分布的階數、有限區間半區間長度和有限區間的均值。有限區間正態分布概率密度函數如圖1 所示，可見不同階數k所對應的曲線。

圖1 有限區間正態分布概率密度函數

當有限區間正態分布的階數為0 時，概率密度函數為：

2.4 時變信道下RLNC 重編碼的歸一化秩期望

文獻[20]研究了有限區間正態分布階數為0和1 時，RLNC 重編碼在時變信道下的秩分布并推導了閉合解。本節將階數從0 和1 推廣到更具有一般性的自然數k，討論任意階數下RLNC 重編碼在時變信道下的秩分布及其閉合解。

假設一個節點接收一個秩為i的批，且采用系統重編碼作為內碼編碼方案生成M個編碼數據包并發送到下一節點，對于0 ≤j≤i≤M,有：

式（20）和式（21）所示的結果與文獻[20]中的一致。

2.5 時變信道下系統重編碼的歸一化秩期望

基于文獻[20]所述的RLNC 重編碼在時變信道下的秩分布研究思路，本節討論采用系統重編碼作為內碼時，分批稀疏碼在時變信道下的歸一化秩期望，并推導求解出k在任意值下，歸一化秩期望的閉合解。

當有限區間正態分布的階數為0 時，將k=0代入式（30），有：

3 仿真結果與分析

本節基于蒙特卡洛仿真對以上結論的數值分析的結論進行驗證，數值計算與仿真參數見表1。

表1 數值計算與仿真參數

圖2～圖5 分別是有限區間正態分布的階數為0、1、2 和3 時基于系統重編碼的分批稀疏碼歸一化秩期望仿真結果。可以看出，隨著網絡長度的增加，歸一化秩期望逐漸減小，且數值分析結果與蒙特卡洛仿真結果完全吻合。此外，對比圖2～圖5 可以發現，當基域qm、批大小M和網絡長度L相同時，有限區間正態分布階數越大，系統重編碼的歸一化秩期望越大。如當qm=256、M= 32、L= 20 時，k= 3 對應的重編碼方案具有更高的歸一化秩期望。

圖2 k = 0 時基于系統重編碼的分批稀疏碼歸一化秩期望

圖5 k = 3 時基于系統重編碼的分批稀疏碼歸一化秩期望

為了比較時變信道下基于系統重編碼與基于RLNC 重編碼的歸一化秩期望，圖6～圖9 給出了當有限區間正態分布階數k= 0、1、2 和3 時基于RLNC 重編碼的分批稀疏碼歸一化秩期望，其中數值計算的結果根據式（19）計算所得，其結果與蒙特卡洛仿真相吻合。此外，對比圖2 與圖6、圖3與圖7、圖4 與圖8、圖5 與圖9，可以發現當qm、M和L較小時，基于系統重編碼的分批稀疏碼比基于RLNC 重編碼的分批稀疏碼具有更好的歸一化秩期望；當基域mq較大時，基于系統重編碼的分批稀疏碼與基于RLNC 重編碼的分批稀疏碼具有近乎一致的性能。因此，若基域mq較小時，使用系統重編碼來傳輸數據具有更好的性能。

圖3 k = 1 時基于系統重編碼的分批稀疏碼歸一化秩期望

圖4 k = 2 時基于系統重編碼的分批稀疏碼歸一化秩期望

圖6 k = 0 時基于RLNC 重編碼的分批稀疏碼歸一化秩期望

圖7 k = 1 時基于RLNC 重編碼的分批稀疏碼歸一化秩期望

圖8 k = 2 時基于RLNC 重編碼的分批稀疏碼歸一化秩期望

圖9 k = 3 時基于RLNC 重編碼的分批稀疏碼歸一化秩期望

4 結束語

本文分析了在時變信道下基于系統重編碼的分批稀疏碼秩分布，通過將信道鏈路上的丟包率建模成隨機變量，得到了時變信道下秩分布的通用表達式，同時，本文進一步研究了鏈路丟包率服從有限區間正態分布時的秩分布且階數k為任意值時，RLNC 和系統重編碼的歸一化秩期望的通用閉合解。隨后通過蒙特卡洛仿真，驗證了該閉合解的正確性與通用性。本文的研究均基于多跳線性網絡模型，在實際生產生活中，無線網絡的模型會更加多樣。因此，對于更貼近實際生活的諸多非線性網絡環境下，分批稀疏碼在時變信道下的秩分布也同樣具有研究價值，后續可進一步進行理論分析，探討線性網絡下的諸多結論和性質是否同樣適用于其他非線性網絡模型。