基于網絡編碼的低信噪比多跳中繼傳輸方案*

陳 超,張士兵,李 業

(南通大學 信息科學技術學院,江蘇 南通 226019)

0 引 言

中繼通信是擴大傳輸范圍的重要方式[1]。傳統的反饋機制存在反饋時延，難以滿足多跳中繼通信快速響應的要求。作為新興的傳輸技術，網絡編碼提高了網絡吞吐率。將噴泉碼的無反饋技術與網絡編碼相結合，可以降低傳輸時延[2-3]。文獻[4]將物理層安全技術和網絡編碼結合，保障了通信的安全性。文獻[5]將網絡編碼運用到中繼協作無線網絡中，提高了傳輸有效性。文獻[6]證明了基于無反饋機制的網絡編碼傳輸技術可以滿足水下傳感器網絡低時延的要求。

隨機線性網絡編碼(Random Linear Network Coding,RLNC)是一種經典網絡編碼方式，基于無反饋機制，可以降低傳輸時延[7]。文獻[8]將RLNC運用到車聯網信息分發中，以滿足車聯網通信低時延的要求。

在基于無反饋機制的RLNC中，待傳輸的信息被分成若干源分組，源分組分別乘以編碼系數進行線性組合形成RLNC分組。編碼系數攜帶于RLNC分組包頭以便接收端進行譯碼。在低信噪比場景下，信道容量較小，當源分組數較多時，包頭開銷增加，易造成較高的丟包率[9]，增加傳輸時延。

文獻[10-11]通過優化系數的有限域，減輕了系數開銷對兩跳通信傳輸時間的影響。在編碼長度不受限制的情況下，文獻[12-14]將固定編碼密度的稀疏編碼(Sparse Coding,SC)應用到點對點通信中，形成SC分組的源分組數小于RLNC，以此降低編碼系數開銷，減少傳輸時延。但是，目前的多跳中繼傳輸方案主要通過控制反饋次數來降低傳輸時延[15]，如何在低信噪比場景下設計多跳中繼通信的低時延無反饋傳輸方案仍是一個需要解決的問題。

為了保障低信噪比下多跳中繼通信的低時延傳輸，本文提出了一種基于網絡編碼的無反饋傳輸方案，主要工作如下：制定了適用于多跳中繼的通信框架和網絡編碼方式，構建了應用層-編碼層-物理層參數之間的關系式；通過馬爾科夫鏈對網絡編碼方案下多跳中繼通信的傳輸時間進行建模，并根據信道的信噪比優化編碼方式和參數以獲取最短傳輸時間；設計了搜索算法優化編碼密度等參數，通過比較不同搜索算法的計算量，確定了低信噪比場景下多跳中繼通信的編碼傳輸方案。

1 系統模型設計

設S為源節點，Ri(1≤i≤L-1)為中繼節點，D為目的節點，系統模型如圖1所示。其中，εj(1≤j≤L)表示各跳鏈路丟包率。根據多跳模型，通信框架可分為3層，如圖2所示。應用層中，信息被分成M個源分組；編碼層中，源分組進行線性組合形成編碼分組，s表示源分組，a表示編碼系數，N為編碼長度；物理層中，編碼分組被傳輸到下一節點，n為信道編碼碼字的符號數。

圖1 多跳中繼系統模型

圖2 多跳中繼系統的通信框架

設源節點需發送F比特信息。同時，將每L個時隙記作1次鏈路使用，每次鏈路使用對應每跳依次發送1個編碼分組。

在多跳中繼通信中，若采用RLNC，所有源分組均參與編碼，編碼系數攜帶在分組頭中，開銷為Mlbq比特，q為編碼系數的有限域大小。RLNC的編碼輸出為

(1)

式中：K表示編碼分組中信息編碼后的長度。由于采用固定位數的二進制計算，源分組與編碼輸出的長度一致，均為K比特。

若采用SC，每b次鏈路使用前，隨機選擇W(W≤M)個源分組構成Batch子集[13]，b稱為子集傳輸大小(Batch Transmission Size,BTS)，W/M稱為編碼密度。在b次鏈路使用中，S對Batch中的W個分組進行RLNC編碼并傳輸;在b次鏈路使用后，S重新選擇W個分組構成新的Batch。重復上述過程。每次編碼有W個分組參與，編碼系數開銷為Wlbq比特。RLNC或SC在目的節點均使用高斯消去法進行解碼[7,13]。當目的節點成功解碼M個線性無關源分組(Linearly Independent Source Packet,LISP)時，通信結束。

本文將S開始發送編碼分組到D解碼M個LISP所需的時隙數記作傳輸時間，用以表示時延。由于編解碼時間較短，所以不予以考慮。在編碼長度固定的情況下，本文提出的方案與文獻[13]方案不同之處在于，為了滿足低信噪比場景下多跳中繼通信低時延的要求，本文方案會根據信道條件選擇合適的M和W等編碼參數。當W=M時，SC和RLNC等價，故可以將RLNC并入SC進行分析。結合圖2中的通信框架可得：應用層中，各源分組的長度之和不小于F，如式(2)；編碼層中，編碼系數開銷和編碼輸出長度之和不得大于編碼分組長度N，如式(3)；物理層中，編碼分組在傳輸時的速率受限于信道容量，如式(4)。

MK≥F，

(2)

Wlbq+K≤N，

(3)

N/nj≤Cj。

(4)

式中：nj和Cj分別表示第j跳鏈路信道編碼碼字的符號數和信道容量。

當信噪比變小時，信道容量變小。根據式(3)和(4)，N也會變小。此時，可以通過減小W來保障有效信息的傳輸，控制傳輸時延。文獻[14]闡述了N與丟包率ε之間關系，ε是影響傳輸時間的直接因素，所以N也會影響傳輸時間；傳輸Batch內W個分組的時間又與b有關,因此，需要結合信道信息，分析傳輸時間與ε、N、W和b之間的關系。

2 編碼傳輸時間分析

為便于敘述，設各跳均為刪除信道，第i個中繼節點和目的節點所含LISP數分別為Xi和Y，Ri可解碼并暫存mi個源分組。整個傳輸過程中，各節點LISP的未來狀態變化僅依賴于當前狀態，具有馬爾科夫性質。同時，所有的狀態都在向(X,Y=M)轉移。因此傳輸過程可建立為吸收馬爾科夫鏈(Absorbing Markov Chain,AMC)。由于RLNC是SC在W=M時的一種情況，所以時間分析是基于SC展開的。

首先考慮1個Batch的傳輸過程。在1個時隙后，R1所含LISP數加1的概率為

PL{(X1,X2,X3,…,XL-1,Y)→(X1+1,X2,X3,…,XL-1,Y)}=

(5)

當Xl-1=mi(1

PL{(X1,X2,…,XL-1,Y)→(X1,X2,…,Xl-1-1,Xl+1,…,Y)}=

(6)

以兩跳為例，設需要傳輸的LISP數為2，各跳丟包率相同，中繼緩存大小為2個源分組，則2元組(X,Y)的AMC模型如圖3所示。其中，X和Y分別表示中繼和目的節點的LISP數;(X=0,Y=0)是初始狀態，(X,Y=2)為吸收狀態;PX+1,Y表示P{(X,Y)→(X+1,Y)}，可由式(5)求得;PX-1,Y+1表示P{(X,Y)→(X-1,Y+1)}，可由式(6)求得。

圖3 兩跳通信AMC模型

以L元組(X1=0,X2=0,…,XL-1=0,Y=0)為初始狀態，(X1,X2,X3,…,Y=min(b,W))為吸收態建立AMC。根據式(5)和式(6)，可以得到1次鏈路使用后的L元組狀態轉移概率矩陣：

(7)

式中：Q表示L元組從吸收態到非吸收態的轉移概率矩陣，R表示L元組從非吸收態到吸收態的轉移概率矩陣。

根據式(7)可得，在b次鏈路使用后，目的節點LISP數的概率分布為

(8)

式中：my表示在Y=y的情況下；L元組所有可能狀態的個數;下標“1,v”表示矩陣的第1行第v列的元素。

由于不同Batch間涵蓋的LISP可能有重疊，需要確定所收到的Batch內LISP是否與之前已解碼的源分組線性無關，即全局線性無關。可引入狀態(r,c)[12]的AMC模型，其中r為目的節點已收到的全局線性無關源分組數，c為目的節點收到的Batch中已涵蓋的源分組數。1個Batch內含有z個全局線性無關源分組的概率為

(9)

式中：z表示新增的全局線性無關源分組數。設Batch包含y個LISP，需要對(r,c)的變化分情況討論。

(1)當0≤z≤y時，目的節點收到的Batch含有z個全局線性無關源分組，r值至少增加z，min(y-z,c-r)表示Batch中剩余的全局線性無關源分組數。(r,c)狀態轉移概率為

P{(r,c)→(r+z+min(y-z,c-r),c+z)}=fY(y)p(z)。

(10)

(2)當y

P{(r,c)→(r+y,c+z)}=fY(y)p(z)。

(11)

根據式(10)和式(11)，可知(r，c)各個狀態之間的轉移概率。以(r=0,c=0)為初始狀態，(r=M,c)為吸收狀態，可得(r，c)狀態轉移概率矩陣：

(12)

式中：Qs表示(r,c)從非吸收態到吸收態的轉移概率矩陣。

基于Us可以得到傳輸完成(即r=M)所需Batch的期望個數為

(13)

式中：nr,c表示所有(r，c)的狀態個數。由于BTS大小為b次鏈路使用，每次鏈路使用包含L個時隙，故期望傳輸時隙數為

(14)

文獻[14]總結并證明了刪除信道下ε和N的表達式：

(15)

式中：

(16)

(17)

式中：SNR表示信噪比，e表示自然常數。根據以上分析，可通過搜索N(或ε)、M、W和b得到最短傳輸時間。

3 優化算法設計

本節將基于傳輸時間的分析結果，設計相關的編碼參數，并提出優化算法搜索本方案的最短傳輸時間。

根據系統模型可知，當N或ε確定時，M、W等參數取值范圍會依次確定。因此考慮由N或ε為初始的搜索方式，分別稱為N初始(N-start,N-S)算法和ε初始(ε-start,ε-S)算法。

N-S算法對首先對N進行搜索，通過式(4)中的信道限制條件，可以得到N的搜索區間為(0,nC]。之后，通過式(15)可以得到ε。根據式(3)可以得到W的表達式為

W=min{M,「(N-K)/lbq?}。

(18)

式中：M搜索范圍為[「F/N?,「F?]。當W/M<1時，表示采用SC進行通信，W/M=1則對應RLNC。

當N、ε、M和W確定后，設置b=1，可計算出傳輸時間。將此傳輸時間與已計算的最小時間進行比較，來控制b的增減，以得到最短的傳輸時間，如圖4所示。其中，最小傳輸時間初始化為∞。

圖4 b的搜索流程圖

根據編碼傳輸時間分析可知，每次搜索的計算量集中在矩陣的冪和逆運算，而減少這些操作的計算量相對困難，所以設計算法的關鍵是控制搜索次數。但從式(15)可知，ε隨N的變化平緩，導致算法可能在同一個搜索點進行重復計算，不利于控制算法的計算量。

通過式(15)可以得到N隨ε變化的關系式：

(19)

輸入:F、q、mi、nj、SNR。

1Tmin←∞

4 ForMin 「F/N-1,F? do

5 IfTFB>Tmin

6 Break

7 End If

8K←?F/M」,b←1,W←min{M,「(N-K)/lbq?}

9 IfW==0

10 Break

11 End If

12Tlmin←∞

13 While 1 do

14Tcomp←Lbnbat

15 IfTcomp>Tlmin

16b←b-1

17 Break

18 Else

19Tlmin←Tcomp

20b←b+1

21 End If

22 End While

23 IfTlmin

24Tmin←Tlmin

25 End If

26 End For

27 End For

輸出：Tmin、M、W、N、b、K。

在ε-S算法中，由于本方案考慮低信噪比場景，所以設置的SNR值較小。第5～7步將本方案與反饋機制[15]的傳輸時間TFB比較，在相同條件下，如果反饋機制的傳輸時間較少，則不必采用本方案，算法直接終止，以提高搜索效率；第8步中，當SNR較小時，N的值會變小，W減少，以此保證有效信息的傳輸；算法允許W=M，以便比較RLNC和SC的傳輸時間，確定較好的編碼方式；第9～11步刪除W=0的情況，避免不必要的搜索；在第14～15步中，Tcomp表示當前條件下計算的傳輸時間,Tlmin表示當前最小的傳輸時間；在第13～22步中，由于1-Qs中各個元素都不大于1，隨著b的增加，nbat的變化趨于平緩，而Lbnbat在b較大時會隨著b單增，所以當b較小時，Lbnbat存在最小值；第23～25步是比較不同編碼參數下的傳輸時間，算法的輸出為最短的傳輸時間Tmin及其對應的編碼參數。

4 仿真與分析

使用Matlab對提出的編碼傳輸方案進行仿真，并與RLNC傳輸方案[10]、BATCH編碼傳輸方案[13]和有限反饋策略[15](Limited Feedback Strategy,LFS)進行傳輸時延比較。設置F=1 000 b，mi均設置為2，nj均設置為400，有限域大小q=256(文獻[10]證明了q=256是網絡編碼最佳有限域大小)。

圖5分別比較了N-S和ε-S算法在低信噪比下的最短傳輸時間和編碼參數的設置。由圖可知，N-S和ε-S算法的搜索得到的最短傳輸時間及其編碼參數相等,這是由于N-S和ε-S算法都是基于相同的邏輯關系得到傳輸時間和編碼參數。從優化結果可知，當信噪比較小時，為了保證信息的有效傳輸，編碼密度會變小,這與本文的分析相符。

圖5 N-S和ε-S算法在低信噪比多跳中繼系統中最短傳輸時間及其編碼參數比較

圖6是N-S和ε-S算法的搜索次數比較。由于N-S和ε-S算法每個搜索點的計算量相同，可通過搜索次數反映兩種算法的總計算量。由圖可知，ε-S算法的搜索次數小于N-S算法,這是由于N-S算法會重復計算相同編碼參數下的傳輸時間，浪費搜索資源;而ε-S算法的搜索區間相對固定，所以搜索次數不會隨著SNR的增加而有明顯的增加。當SNR較大時，N-S算法的搜索次數趨于平緩，這是因為SNR較大時信道環境較好，可以優先考慮最佳情況，進而搜索次數增速變緩。綜合來看，ε-S算法的性能要好于N-S算法。

圖6 N-S和ε-S算法的搜索次數比較

圖7是通過ε-S算法獲取的低信噪比多跳中繼系統最短傳輸時間及其編碼參數。從圖中可知，SNR較小時，W/M<1，采用SC以獲取最短傳輸時間；而SNR較大時，W=M，則采用RLNC進行傳輸。編碼長度隨著SNR的增加呈現上升趨勢，W/M也趨向于1，這是由于SNR變大，信道容量變大，N可以取到較大值，SC在傳輸時間上就沒有優勢。上述結果表明，SC比RLNC更適用于低信噪比場景。

圖7 ε-S算法在低信噪比多跳中繼系統的最短傳輸時間及其編碼參數

圖8比較了ε-S、BATCH、RLNC和LFS四種傳輸方案在低信噪比多跳通信中的傳輸時間。從圖中可知，ε-S和BATCH方案相比，因調整了編碼密度，可以更好地適應低信噪比場景下的多跳中繼通信；ε-S和RLNC方案相比，減少了參與編碼的分組數，降低了編碼開銷，提高了信息傳輸的有效性，有利于傳輸時延的降低；ε-S和LFS方案相比，在確保信息有效傳輸的情況下，無反饋機制可以降低傳輸時延。LFS方案的傳輸時延隨著信噪比的變化有較大波動，這是由于在反饋機制中每跳發送分組成功的概率各不相同，造成不同節點反饋的次數不同，所以傳輸時間會隨著信噪比的變化而波動。

圖8 ε-S、BATCH、RLNC和LFS在低信噪比多跳通信中的傳輸時間比較

5 結 論

本文提出了一種適用于低信噪比多跳中繼通信的編碼傳輸方案，該方案根據信道條件選擇合適的編碼參數以獲取較短的傳輸時間。同時，文中提出并比較了N-S和ε-S兩種搜索最短傳輸時間的算法，揭示了ε-S具有較少的計算量。優化結果證明了稀疏編碼較隨機線性網絡編碼更適用于低信噪比多跳中繼通信系統。理論分析和數值仿真表明，本文的編碼傳輸方案在低信噪比多跳場景下有較短的傳輸時延。