陳 超,張士兵,李 業(yè)

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

0 引 言

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

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

在基于無反饋機制的RLNC中，待傳輸?shù)男畔⒈环殖扇舾稍捶纸M，源分組分別乘以編碼系數(shù)進行線性組合形成RLNC分組。編碼系數(shù)攜帶于RLNC分組包頭以便接收端進行譯碼。在低信噪比場景下，信道容量較小，當(dāng)源分組數(shù)較多時，包頭開銷增加，易造成較高的丟包率[9]，增加傳輸時延。

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

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

1 系統(tǒng)模型設(shè)計

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

圖1 多跳中繼系統(tǒng)模型

圖2 多跳中繼系統(tǒng)的通信框架

設(shè)源節(jié)點需發(fā)送F比特信息。同時，將每L個時隙記作1次鏈路使用，每次鏈路使用對應(yīng)每跳依次發(fā)送1個編碼分組。

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

(1)

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

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

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

MK≥F，

(2)

Wlbq+K≤N，

(3)

N/nj≤Cj。

(4)

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

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

2 編碼傳輸時間分析

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

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

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

(5)

當(dāng)Xl-1=mi(1

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

(6)

以兩跳為例，設(shè)需要傳輸?shù)腖ISP數(shù)為2，各跳丟包率相同，中繼緩存大小為2個源分組，則2元組(X,Y)的AMC模型如圖3所示。其中，X和Y分別表示中繼和目的節(jié)點的LISP數(shù);(X=0,Y=0)是初始狀態(tài)，(X,Y=2)為吸收狀態(tài);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)為初始狀態(tài)，(X1,X2,X3,…,Y=min(b,W))為吸收態(tài)建立AMC。根據(jù)式(5)和式(6)，可以得到1次鏈路使用后的L元組狀態(tài)轉(zhuǎn)移概率矩陣：

(7)

式中：Q表示L元組從吸收態(tài)到非吸收態(tài)的轉(zhuǎn)移概率矩陣，R表示L元組從非吸收態(tài)到吸收態(tài)的轉(zhuǎn)移概率矩陣。

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

(8)

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

由于不同Batch間涵蓋的LISP可能有重疊，需要確定所收到的Batch內(nèi)LISP是否與之前已解碼的源分組線性無關(guān)，即全局線性無關(guān)?？梢霠顟B(tài)(r,c)[12]的AMC模型，其中r為目的節(jié)點已收到的全局線性無關(guān)源分組數(shù)，c為目的節(jié)點收到的Batch中已涵蓋的源分組數(shù)。1個Batch內(nèi)含有z個全局線性無關(guān)源分組的概率為

(9)

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

(1)當(dāng)0≤z≤y時，目的節(jié)點收到的Batch含有z個全局線性無關(guān)源分組，r值至少增加z，min(y-z,c-r)表示Batch中剩余的全局線性無關(guān)源分組數(shù)。(r,c)狀態(tài)轉(zhuǎn)移概率為

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

(10)

(2)當(dāng)y

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

(11)

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

(12)

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

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

(13)

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

(14)

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

(15)

式中：

(16)

(17)

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

3 優(yōu)化算法設(shè)計

本節(jié)將基于傳輸時間的分析結(jié)果，設(shè)計相關(guān)的編碼參數(shù)，并提出優(yōu)化算法搜索本方案的最短傳輸時間。

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

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

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

(18)

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

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

圖4 b的搜索流程圖

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

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

4 仿真與分析

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

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

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

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

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

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

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

圖8比較了ε-S、BATCH、RLNC和LFS四種傳輸方案在低信噪比多跳通信中的傳輸時間。從圖中可知，ε-S和BATCH方案相比，因調(diào)整了編碼密度，可以更好地適應(yīng)低信噪比場景下的多跳中繼通信；ε-S和RLNC方案相比，減少了參與編碼的分組數(shù)，降低了編碼開銷，提高了信息傳輸?shù)挠行裕欣趥鬏敃r延的降低；ε-S和LFS方案相比，在確保信息有效傳輸?shù)那闆r下，無反饋機制可以降低傳輸時延。LFS方案的傳輸時延隨著信噪比的變化有較大波動，這是由于在反饋機制中每跳發(fā)送分組成功的概率各不相同，造成不同節(jié)點反饋的次數(shù)不同，所以傳輸時間會隨著信噪比的變化而波動。

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

5 結(jié) 論

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