王士恒，劉恒，唐林，蘇金領(lǐng)，張瑞琦

（1. 西南交通大學(xué)信息編碼與傳輸省重點(diǎn)實(shí)驗(yàn)室，四川 成都 611756；2. 現(xiàn)代交通通信與傳感網(wǎng)絡(luò)國(guó)家級(jí)國(guó)際聯(lián)合研究中心，四川 成都 611756;3. 中國(guó)電子科技集團(tuán)第三十研究所，四川 成都 610031）

0 引言

在無(wú)線網(wǎng)絡(luò)中，從源節(jié)點(diǎn)到宿節(jié)點(diǎn)之間的直接鏈路往往是不可達(dá)的，因此多跳的通信方式變得十分重要。在多跳通信網(wǎng)絡(luò)中，部分節(jié)點(diǎn)作為網(wǎng)絡(luò)中間節(jié)點(diǎn)通過(guò)逐跳轉(zhuǎn)發(fā)的方式將接收的數(shù)據(jù)包傳輸?shù)剿薰?jié)點(diǎn)。由于噪聲、干擾或者信道失真等影響，在多跳網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)包仍然可能以一定概率出現(xiàn)丟包的現(xiàn)象，此時(shí)可使用網(wǎng)絡(luò)編碼[1]處理丟包問(wèn)題。

作為多跳網(wǎng)絡(luò)中的一種新型信道編碼方案，同時(shí)也是傳統(tǒng)隨機(jī)線性網(wǎng)絡(luò)編碼（random linear network coding, RLNC）[2]的加強(qiáng)型方案，分批稀疏（batched sparse，BATS）碼是一種能夠在丟包網(wǎng)絡(luò)中改進(jìn)網(wǎng)絡(luò)性能的編碼方案[3]。分批稀疏碼提供了一個(gè)兩段式編碼框架，源節(jié)點(diǎn)處的外碼（噴泉碼的矩陣形式）在理論上可以生成無(wú)限數(shù)量的批次數(shù)據(jù)包（batch），而內(nèi)碼（采用線性網(wǎng)絡(luò)編碼）則在網(wǎng)絡(luò)中間節(jié)點(diǎn)處對(duì)屬于同一個(gè)批次的數(shù)據(jù)包進(jìn)行再次編碼。分批稀疏碼適用于任何允許在中間節(jié)點(diǎn)上進(jìn)行線性網(wǎng)絡(luò)編碼的網(wǎng)絡(luò)。由于端到端的操作為線性編碼，因此分批稀疏碼對(duì)動(dòng)態(tài)網(wǎng)絡(luò)拓?fù)浜蛠G包具有魯棒性。此外，分批稀疏碼可以在較小的有限域下運(yùn)行，相比之下，現(xiàn)有的隨機(jī)線性網(wǎng)絡(luò)編碼雖然可以使網(wǎng)絡(luò)吞吐量達(dá)到網(wǎng)絡(luò)容量[4-5]，但也需要較大的場(chǎng)大小去保證傳輸矩陣為滿秩。分批稀疏碼解決了基于塊的方法的順序調(diào)度的反饋問(wèn)題：由于無(wú)速率的特性，批次的順序調(diào)度不需要反饋。同時(shí)，分批稀疏碼解決了基于噴泉碼的方法的度分布問(wèn)題，因?yàn)榉峙∈璐a的內(nèi)碼不會(huì)改變批次的度值[3]。

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

目前，國(guó)內(nèi)外諸多學(xué)者在許多方面對(duì)BATS碼進(jìn)行了研究與優(yōu)化。Yang 等[9]首先提出了一種簡(jiǎn)單的支持分批稀疏碼的網(wǎng)絡(luò)協(xié)議，稱為BATS-Pro-0，該協(xié)議由上到下將信息傳輸?shù)目蚣芊譃閼?yīng)用層、傳輸層、網(wǎng)絡(luò)層、鏈路層和物理層，演示了如何使用分批稀疏碼在網(wǎng)絡(luò)中進(jìn)行通信，并為后續(xù)的研究提供了一個(gè)最基本的協(xié)議。

由于秩分布決定了數(shù)據(jù)傳輸?shù)淖畲罂蛇_(dá)速率，因此秩分布是在分析分批稀疏碼性能時(shí)的一個(gè)十分重要的參數(shù)，目前已有相關(guān)文獻(xiàn)研究了分批稀疏碼在不同網(wǎng)絡(luò)拓?fù)浜徒Y(jié)構(gòu)下的秩分布。Yang 等[7]基于BATS-Pro-0 協(xié)議，研究分析了RLNC 重編碼作為內(nèi)碼編碼方案時(shí)分批稀疏碼的歸一化秩期望，并提出了一個(gè)批的秩在網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)上形成一個(gè)馬爾可夫鏈[7]，推導(dǎo)得到刪除信道下RLNC 重編碼的最大可達(dá)速率，即在批次數(shù)足夠大的情況下，該速率會(huì)收斂到一個(gè)常數(shù)，該數(shù)值只隨丟包率變化。之后Yang 等[7]對(duì)RLNC 重編碼進(jìn)行改進(jìn)，提出系統(tǒng)重編碼作為內(nèi)碼編碼的方案并分析其秩分布。該方案在批次數(shù)足夠大的情況下與RLNC 重編碼的最大可達(dá)速率相同，但在批次數(shù)較小時(shí)有著更明顯的優(yōu)勢(shì)。作為一種新的編碼技術(shù)，其在計(jì)算開銷和重編碼時(shí)延上都要低于RLNC 重編碼，同時(shí)在相同節(jié)點(diǎn)上的秩期望也更大，因此，以系統(tǒng)重編碼作為分批稀疏碼的內(nèi)碼會(huì)獲得較RLNC 重編碼更優(yōu)的性能。同時(shí)根據(jù)線性重編碼，Yin 等[10]提出了自適應(yīng)重編碼方案，Yang 等[7]提出了一個(gè)批在下一跳上的秩期望，Yue 等[6]在此基礎(chǔ)上研究了兩種能夠應(yīng)用于工業(yè)互聯(lián)網(wǎng)上行鏈路的分布式分批稀疏碼的秩期望。

網(wǎng)絡(luò)編碼可分為確定網(wǎng)絡(luò)編碼和隨機(jī)網(wǎng)絡(luò)編碼。為了能夠設(shè)計(jì)出高效的確定網(wǎng)絡(luò)編碼，通常需要獲取信道狀態(tài)的相關(guān)信息[11]。而隨機(jī)線性網(wǎng)絡(luò)編碼達(dá)到較高的編碼增益的代價(jià)是較高的編碼開銷[12]。為了降低編碼開銷，各種稀疏隨機(jī)線性網(wǎng)絡(luò)編碼方案被提出[13-16]。

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

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

1 分批稀疏碼

1.1 外碼編碼

分批稀疏碼是隨機(jī)線性網(wǎng)絡(luò)編碼的加強(qiáng)型方案，該編碼方案分為外部和內(nèi)碼兩部分。外碼在源節(jié)點(diǎn)處生成批Xi，一個(gè)包含M個(gè)已編碼數(shù)據(jù)包的批通常利用K個(gè)輸入數(shù)據(jù)包的子集生成，即：

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

1.2 內(nèi)碼編碼

內(nèi)碼編碼是指在網(wǎng)絡(luò)中間節(jié)點(diǎn)將接收的屬于同一個(gè)批的數(shù)據(jù)包進(jìn)行重編碼，將得到的編碼數(shù)據(jù)包轉(zhuǎn)發(fā)至下一節(jié)點(diǎn)。

分批稀疏碼的內(nèi)碼通常采用隨機(jī)線性網(wǎng)絡(luò)編碼的重編碼方案，該方案有較大的計(jì)算開銷和重編碼時(shí)延。

文獻(xiàn)[7]提出了基于系統(tǒng)重編碼（systematic recoding）的內(nèi)碼方案。作為一種新的編碼技術(shù)，系統(tǒng)重編碼在計(jì)算開銷和重編碼時(shí)延上都要低于RLNC 重編碼，同時(shí)在相同節(jié)點(diǎn)上的秩期望也更大，因此，以系統(tǒng)重編碼作為分批稀疏碼的內(nèi)碼會(huì)獲得比RLNC 重編碼更優(yōu)的性能。在系統(tǒng)重編碼的內(nèi)碼方案中，假設(shè)網(wǎng)絡(luò)中間節(jié)點(diǎn)接收k*個(gè)屬于同一個(gè)批的數(shù)據(jù)包，r是k*個(gè)數(shù)據(jù)包中線性無(wú)關(guān)數(shù)據(jù)包的數(shù)量。令M'表示系統(tǒng)重編碼生成并轉(zhuǎn)發(fā)至下一節(jié)點(diǎn)的數(shù)據(jù)包數(shù)量。系統(tǒng)重編碼按照如下步驟進(jìn)行。

步驟1 從接收的數(shù)據(jù)包中選擇r個(gè)線性無(wú)關(guān)的數(shù)據(jù)包作為重編碼數(shù)據(jù)包的一部分。

步驟2 從步驟1 選擇的r個(gè)線性無(wú)關(guān)的數(shù)據(jù)包中使用隨機(jī)線性網(wǎng)絡(luò)編碼生成 'M-r個(gè)編碼數(shù)據(jù)包。

鏈路間的丟包率可建模為對(duì)角矩陣E，其中，對(duì)角線元素為0 的概率對(duì)應(yīng)鏈路上的丟包率ε。中間節(jié)點(diǎn)的系統(tǒng)重編碼矩陣為Φ，其中Φ的前r列構(gòu)成一個(gè)單位矩陣，后 'M-r列中的元素在有限域內(nèi)隨機(jī)取值[3]。因此，第n個(gè)節(jié)點(diǎn)收到的數(shù)據(jù)包Y為：

2 時(shí)變信道下的歸一化秩期望分析

2.1 時(shí)不變信道下的歸一化秩分布

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

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

2.2 時(shí)變信道下的歸一化秩分布

式（13）表明，若要計(jì)算節(jié)點(diǎn)nR的秩，需要結(jié)合具體的重編碼方案與概率密度分布函數(shù)進(jìn)行分析，因此，本文將基于不同的信道條件以及不同重編碼方式對(duì)線性網(wǎng)絡(luò)中的分批稀疏碼秩分布進(jìn)行分析。

2.3 有限區(qū)間正態(tài)分布

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

其中，k、a和μ分別表示有限區(qū)間正態(tài)分布的階數(shù)、有限區(qū)間半?yún)^(qū)間長(zhǎng)度和有限區(qū)間的均值。有限區(qū)間正態(tài)分布概率密度函數(shù)如圖1 所示，可見不同階數(shù)k所對(duì)應(yīng)的曲線。

圖1 有限區(qū)間正態(tài)分布概率密度函數(shù)

當(dāng)有限區(qū)間正態(tài)分布的階數(shù)為0 時(shí)，概率密度函數(shù)為：

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

文獻(xiàn)[20]研究了有限區(qū)間正態(tài)分布階數(shù)為0和1 時(shí)，RLNC 重編碼在時(shí)變信道下的秩分布并推導(dǎo)了閉合解。本節(jié)將階數(shù)從0 和1 推廣到更具有一般性的自然數(shù)k，討論任意階數(shù)下RLNC 重編碼在時(shí)變信道下的秩分布及其閉合解。

假設(shè)一個(gè)節(jié)點(diǎn)接收一個(gè)秩為i的批，且采用系統(tǒng)重編碼作為內(nèi)碼編碼方案生成M個(gè)編碼數(shù)據(jù)包并發(fā)送到下一節(jié)點(diǎn)，對(duì)于0 ≤j≤i≤M,有：

式（20）和式（21）所示的結(jié)果與文獻(xiàn)[20]中的一致。

2.5 時(shí)變信道下系統(tǒng)重編碼的歸一化秩期望

基于文獻(xiàn)[20]所述的RLNC 重編碼在時(shí)變信道下的秩分布研究思路，本節(jié)討論采用系統(tǒng)重編碼作為內(nèi)碼時(shí)，分批稀疏碼在時(shí)變信道下的歸一化秩期望，并推導(dǎo)求解出k在任意值下，歸一化秩期望的閉合解。

當(dāng)有限區(qū)間正態(tài)分布的階數(shù)為0 時(shí)，將k=0代入式（30），有：

3 仿真結(jié)果與分析

本節(jié)基于蒙特卡洛仿真對(duì)以上結(jié)論的數(shù)值分析的結(jié)論進(jìn)行驗(yàn)證，數(shù)值計(jì)算與仿真參數(shù)見表1。

表1 數(shù)值計(jì)算與仿真參數(shù)

圖2～圖5 分別是有限區(qū)間正態(tài)分布的階數(shù)為0、1、2 和3 時(shí)基于系統(tǒng)重編碼的分批稀疏碼歸一化秩期望仿真結(jié)果?？梢钥闯觯S著網(wǎng)絡(luò)長(zhǎng)度的增加，歸一化秩期望逐漸減小，且數(shù)值分析結(jié)果與蒙特卡洛仿真結(jié)果完全吻合。此外，對(duì)比圖2～圖5 可以發(fā)現(xiàn)，當(dāng)基域qm、批大小M和網(wǎng)絡(luò)長(zhǎng)度L相同時(shí)，有限區(qū)間正態(tài)分布階數(shù)越大，系統(tǒng)重編碼的歸一化秩期望越大。如當(dāng)qm=256、M= 32、L= 20 時(shí)，k= 3 對(duì)應(yīng)的重編碼方案具有更高的歸一化秩期望。

圖2 k = 0 時(shí)基于系統(tǒng)重編碼的分批稀疏碼歸一化秩期望

圖5 k = 3 時(shí)基于系統(tǒng)重編碼的分批稀疏碼歸一化秩期望

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

圖3 k = 1 時(shí)基于系統(tǒng)重編碼的分批稀疏碼歸一化秩期望

圖4 k = 2 時(shí)基于系統(tǒng)重編碼的分批稀疏碼歸一化秩期望

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

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

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

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

4 結(jié)束語(yǔ)

本文分析了在時(shí)變信道下基于系統(tǒng)重編碼的分批稀疏碼秩分布，通過(guò)將信道鏈路上的丟包率建模成隨機(jī)變量，得到了時(shí)變信道下秩分布的通用表達(dá)式，同時(shí)，本文進(jìn)一步研究了鏈路丟包率服從有限區(qū)間正態(tài)分布時(shí)的秩分布且階數(shù)k為任意值時(shí)，RLNC 和系統(tǒng)重編碼的歸一化秩期望的通用閉合解。隨后通過(guò)蒙特卡洛仿真，驗(yàn)證了該閉合解的正確性與通用性。本文的研究均基于多跳線性網(wǎng)絡(luò)模型，在實(shí)際生產(chǎn)生活中，無(wú)線網(wǎng)絡(luò)的模型會(huì)更加多樣。因此，對(duì)于更貼近實(shí)際生活的諸多非線性網(wǎng)絡(luò)環(huán)境下，分批稀疏碼在時(shí)變信道下的秩分布也同樣具有研究?jī)r(jià)值，后續(xù)可進(jìn)一步進(jìn)行理論分析，探討線性網(wǎng)絡(luò)下的諸多結(jié)論和性質(zhì)是否同樣適用于其他非線性網(wǎng)絡(luò)模型。