基于網(wǎng)絡(luò)編碼的低信噪比多跳中繼傳輸方案*

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

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

0 引 言

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

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

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

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

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

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

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

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

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

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

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

(1)

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

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

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

MK≥F，

(2)

Wlbq+K≤N，

(3)

N/nj≤Cj。

(4)

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

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

2 編碼傳輸時(shí)間分析

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

首先考慮1個(gè)Batch的傳輸過(guò)程。在1個(gè)時(shí)隙后，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個(gè)源分組，則2元組(X,Y)的AMC模型如圖3所示。其中，X和Y分別表示中繼和目的節(jié)點(diǎn)的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é)點(diǎn)LISP數(shù)的概率分布為

(8)

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

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

(9)

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

(1)當(dāng)0≤z≤y時(shí)，目的節(jié)點(diǎn)收到的Batch含有z個(gè)全局線性無(wú)關(guān)源分組，r值至少增加z，min(y-z,c-r)表示Batch中剩余的全局線性無(wú)關(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)各個(gè)狀態(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的期望個(gè)數(shù)為

(13)

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

(14)

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

(15)

式中：

(16)

(17)

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

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

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

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

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

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

(18)

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

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

圖4 b的搜索流程圖

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

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

4 仿真與分析

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

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

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

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

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

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

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

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

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

5 結(jié) 論

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