無線組播網(wǎng)絡(luò)中應(yīng)用網(wǎng)絡(luò)編碼的動態(tài)組合重傳算法

李彬,李泉,張若南,蔣毅,楊榮

(1.西北工業(yè)大學(xué)電子信息學(xué)院,710072,西安;2.西安交通大學(xué)工程坊,710049,西安)

?

無線組播網(wǎng)絡(luò)中應(yīng)用網(wǎng)絡(luò)編碼的動態(tài)組合重傳算法

李彬1,李泉1,張若南1,蔣毅1,楊榮2

(1.西北工業(yè)大學(xué)電子信息學(xué)院,710072,西安;2.西安交通大學(xué)工程坊,710049,西安)

針對無線組播網(wǎng)絡(luò)中降低數(shù)據(jù)包重傳次數(shù)及對抗信道衰落、建立穩(wěn)定無線連接的需求,提出了一種基于網(wǎng)絡(luò)編碼的動態(tài)組合重傳算法。該算法采用動態(tài)線性組合編碼算法(DLCCA),以提高無線組播網(wǎng)絡(luò)帶寬利用效率。首先,利用發(fā)送端向用戶發(fā)送原始數(shù)據(jù)包;其次,通過組播網(wǎng)絡(luò)的控制信道,發(fā)送端獲取了網(wǎng)絡(luò)用戶的接收狀態(tài),對未正確解碼的數(shù)據(jù)包進(jìn)行編碼,并在傳輸過程中根據(jù)網(wǎng)絡(luò)狀態(tài)采用動態(tài)組合策略來形成網(wǎng)絡(luò)編碼包,從而有效提高了網(wǎng)絡(luò)的整體吞吐量。與此同時(shí),還進(jìn)一步提出了低復(fù)雜度編碼算法,并分析了所提編碼算法的性能,獲得了相應(yīng)的理論分析結(jié)果。仿真實(shí)驗(yàn)表明,與傳統(tǒng)的無編碼算法和XOR網(wǎng)絡(luò)編碼算法相比,動態(tài)組合重傳算法可以顯著減少30%的數(shù)據(jù)重傳次數(shù),提高了網(wǎng)絡(luò)吞吐量。

組播網(wǎng)絡(luò);網(wǎng)絡(luò)編碼;動態(tài)線性組合

近年來,隨著4G/5G網(wǎng)絡(luò)中圖像、視頻等多媒體業(yè)務(wù)的相繼開展,人們對多媒體視頻傳輸質(zhì)量的要求越來越高。由于無線組播技術(shù)能以高效、可擴(kuò)展的方式發(fā)送單點(diǎn)到多點(diǎn)、多點(diǎn)到多點(diǎn)的數(shù)據(jù)流,因此越來越受到人們的重視,而且在無線組播網(wǎng)絡(luò)中如何保證收發(fā)端之間建立可靠的連接也已成為人們所關(guān)心和長期研究的問題。通常,自動重傳請求(automatic repeat request,ARQ)等機(jī)制采用重傳策略對接收錯誤的數(shù)據(jù)包進(jìn)行重傳,但同時(shí)也帶來了頻譜資源利用率低、延時(shí)長等問題,導(dǎo)致用戶服務(wù)質(zhì)量的降低。對此,網(wǎng)絡(luò)編碼提出了在網(wǎng)絡(luò)節(jié)點(diǎn)存儲轉(zhuǎn)發(fā)過程中通過對接收到的數(shù)據(jù)包進(jìn)行重組編碼來減少重傳時(shí)間,并提高了無線組播網(wǎng)絡(luò)的信道利用效率。網(wǎng)絡(luò)編碼的關(guān)鍵之處在于:中繼節(jié)點(diǎn)在完成路由功能的同時(shí)還需要將在不同鏈路傳輸中的數(shù)據(jù)包進(jìn)行組合編碼。這種方式在無線信道帶寬資源利用率、能量利用率及其他潛在方面帶來顯著的益處。值得關(guān)注的是,隨機(jī)網(wǎng)絡(luò)編碼技術(shù)(random network coding,RNC)[1-2]——一種將原始數(shù)據(jù)包進(jìn)行隨機(jī)線性加權(quán)的編碼方式,已經(jīng)被證明可達(dá)到組播容量的上限。因此,越來越多的研究者把目光聚集到網(wǎng)絡(luò)編碼技術(shù)上。Katti等人在文獻(xiàn)[3]中闡述了一種COPE方法,該方法在無線傳感器網(wǎng)絡(luò)中利用網(wǎng)絡(luò)編碼減少了數(shù)據(jù)包重傳次數(shù),并提高了單播網(wǎng)絡(luò)數(shù)據(jù)傳輸效率;Chachulski等人在文獻(xiàn)[4]中則針對無線傳感器網(wǎng)絡(luò)提出了一種傳輸協(xié)議,在該協(xié)議中,數(shù)據(jù)包在轉(zhuǎn)發(fā)之前先進(jìn)行隨機(jī)合并,從而顯著地減少數(shù)據(jù)包路由中的重傳次數(shù);文獻(xiàn)[5]將機(jī)會式網(wǎng)絡(luò)編碼應(yīng)用到無線網(wǎng)絡(luò)的廣播傳輸中,提高了網(wǎng)絡(luò)帶寬的利用率。此外,文獻(xiàn)[6-9]的研究則側(cè)重于改善無線衰落信道下的數(shù)據(jù)包重傳效率;文獻(xiàn)[10]中提出了一種基于網(wǎng)絡(luò)編碼的重傳機(jī)制,并根據(jù)發(fā)包順序依次發(fā)送丟失的編碼包,以期降低重傳次數(shù)。Ren則提出了一種改進(jìn)重傳機(jī)制[11],從而有效地提高聯(lián)合數(shù)據(jù)包的解碼概率從而降低重傳次數(shù);同時(shí),Nguyen在文獻(xiàn)[12]中也提出了一種無線組播網(wǎng)絡(luò)中利用網(wǎng)絡(luò)編碼的優(yōu)勢減少傳輸次數(shù)的方法。

在上述研究工作中,特別是文獻(xiàn)[12]提出的算法中,作者探討了當(dāng)接收端無法對原始數(shù)據(jù)包進(jìn)行正確解碼時(shí)如何利用異或(XOR)機(jī)制通過數(shù)據(jù)包編碼進(jìn)行重傳。具體地,若編碼包被丟失,發(fā)送端則會重復(fù)發(fā)送相同的XOR編碼包,直到所有接收端都正確解碼后才繼續(xù)發(fā)送下一個(gè)編碼包。因此,這種機(jī)制對編碼包丟失的情況處理時(shí)依然回到了常規(guī)的ARQ解決思路,而已有研究表明ARQ這種方式在無線組播網(wǎng)絡(luò)中效率極低。事實(shí)上,當(dāng)網(wǎng)絡(luò)中只有部分接收端成功接收了某編碼包時(shí),網(wǎng)絡(luò)狀態(tài)已經(jīng)產(chǎn)生了相應(yīng)的改變。此時(shí)發(fā)送端可以依據(jù)當(dāng)前的網(wǎng)絡(luò)狀態(tài),對編碼包的組合方式進(jìn)行重新規(guī)劃,即只將成功解碼的原始數(shù)據(jù)包進(jìn)行動態(tài)組合,以此來提高網(wǎng)絡(luò)的吞吐量。

針對上述問題,本文提出了無線組播網(wǎng)絡(luò)中基于隨機(jī)網(wǎng)絡(luò)編碼的動態(tài)線性組合編碼算法(DLCCA)。DLCCA的核心思想在于如何在傳輸過程中,根據(jù)網(wǎng)絡(luò)的實(shí)時(shí)狀態(tài),對原始數(shù)據(jù)包進(jìn)行動態(tài)組合來形成即將發(fā)送的編碼包,從而有效地提高網(wǎng)絡(luò)的整體吞吐量。此外,為了簡化算法的計(jì)算復(fù)雜度,本文進(jìn)一步提出了低復(fù)雜度的確定線性組合編碼算法(FLCCA),FLCCA同時(shí)也是DLCCA的性能下界。最后,針對所提出的算法進(jìn)行了性能分析,并得到了相應(yīng)的理論分析結(jié)果。仿真實(shí)驗(yàn)結(jié)果表明,相比傳統(tǒng)的XOR編碼算法和非編碼算法,DLCCA與FLCCA算法可以顯著地減少重傳次數(shù)(減少30%以上),有效改善了組播網(wǎng)絡(luò)的信道利用率。

1 系統(tǒng)模型

在本文無線組播網(wǎng)絡(luò)模型中,發(fā)送端(例如基站或者AP)將N個(gè)原始數(shù)據(jù)包通過時(shí)分的方式發(fā)送給M個(gè)接收端,并規(guī)定系統(tǒng)每個(gè)時(shí)隙傳輸一個(gè)數(shù)據(jù)包(原始包或者編碼包)。發(fā)送端利用控制信道獲取網(wǎng)絡(luò)中接收端反饋的數(shù)據(jù)包接收狀態(tài)。與數(shù)據(jù)包相比,由于反饋信息包往往很短,只包含必要的節(jié)點(diǎn)狀態(tài)信息,因此該模型假設(shè)反饋信息不會發(fā)生錯誤和丟失。此外,系統(tǒng)的無線信道為瑞利信道模型,并假定不同收發(fā)端的無線信道是相互獨(dú)立的,其中第i個(gè)接收端的誤包率設(shè)為pi。為了更清晰地闡述DLCCA算法,本文做出如下定義。

定義1 狀態(tài)矩陣T。T為根據(jù)接收端反饋信息而形成的矩陣,用來表示數(shù)據(jù)傳輸期間每個(gè)接收端的數(shù)據(jù)包接收狀態(tài)。矩陣中的元素稱之為標(biāo)志位。其中,第i行的標(biāo)志位代表第i個(gè)接收端接收數(shù)據(jù)包的狀態(tài)(1≤i≤M),而第j列的標(biāo)志位代表每個(gè)接收端接收第j個(gè)數(shù)據(jù)包的接收狀態(tài)(1≤j≤N)。若某個(gè)原始數(shù)據(jù)包被接收端成功解碼,則T中的相應(yīng)的標(biāo)志位記為1,否則標(biāo)記為0。

定義2 傳輸帶寬η。發(fā)送端成功將一個(gè)原始數(shù)據(jù)包發(fā)送給所有接收端所使用的平均傳輸次數(shù)。

定義3 原始數(shù)據(jù)包傳輸階段。該階段發(fā)送端利用N個(gè)時(shí)隙向用戶傳輸N個(gè)原始數(shù)據(jù)包。

定義4 編碼包傳輸階段。在該階段中發(fā)送端根據(jù)網(wǎng)絡(luò)狀態(tài)動態(tài)生成編碼包并進(jìn)行傳輸,直到所有的接收端均能解碼出所有原始數(shù)據(jù)包。

2 動態(tài)線性組合重傳機(jī)制

在動態(tài)線性組合編碼策略中,數(shù)據(jù)的發(fā)送分為兩個(gè)階段。首先,發(fā)送端進(jìn)行原始數(shù)據(jù)包傳輸階段。在該階段中,發(fā)送端利用N個(gè)時(shí)隙將N個(gè)原始數(shù)據(jù)包進(jìn)行時(shí)分傳輸。當(dāng)該階段結(jié)束后,由于無線信道的衰落特性,所以并不是所有接收端對所有原始數(shù)據(jù)包都能進(jìn)行正確解碼。因此,接收端利用控制信道將自身的解碼情況反饋回發(fā)送端,而發(fā)送端則根據(jù)反饋信息形成網(wǎng)絡(luò)狀態(tài)矩陣T。因此,狀態(tài)矩陣T記錄了某個(gè)數(shù)據(jù)包是否被某一接收端正確解碼的信息。當(dāng)原始數(shù)據(jù)包傳輸階段完成之后,發(fā)送端進(jìn)入編碼包傳輸階段。在該階段中發(fā)送端將會根據(jù)狀態(tài)矩陣T對部分被接收端丟失的原始數(shù)據(jù)進(jìn)行組合,從而生成新的編碼包。因此,如何對丟失的數(shù)據(jù)包進(jìn)行組合是該編碼策略的關(guān)鍵所在。據(jù)此,本文提出如下編碼和調(diào)度策略。

(1)發(fā)送端在T的每一行中查找第一個(gè)0值標(biāo)志位,并將這些值為0的標(biāo)志位所對應(yīng)的原始數(shù)據(jù)包按照隨機(jī)線性編碼的方式[1]生成新的編碼包。同時(shí),參與編碼的標(biāo)志位則被改寫為1。

(2)發(fā)送端將步驟1中形成的編碼包在全網(wǎng)內(nèi)廣播。若部分接收端仍無法正確解碼該編碼包,該接收端則通過控制信道將其狀態(tài)信息反饋給發(fā)送端。此時(shí),T中所對應(yīng)標(biāo)志位再次變?yōu)?。

(3)針對步驟2中更新的T,發(fā)送端再次檢查狀態(tài)矩陣T中是否仍然有值為0的標(biāo)志位。若有,發(fā)送端則需重復(fù)上述的步驟直到矩陣T中沒有0值。為了便于對DLCCA的理解,圖1進(jìn)行了舉例說明。在圖1中,狀態(tài)矩陣代表發(fā)送端將N=10個(gè)數(shù)據(jù)包向M=5個(gè)接收端進(jìn)行組播。若接收端在原始數(shù)據(jù)包發(fā)送階段成功解碼某個(gè)數(shù)據(jù)包,則矩陣T中相應(yīng)標(biāo)志位的值記為1,否則記為0。

圖1 采用DLCCA機(jī)制進(jìn)行組合的矩陣T

圖1為DLCCA機(jī)制進(jìn)行組合的狀態(tài)矩陣T,矩陣中標(biāo)記的虛線框給出了在編碼包傳輸階段中組合形成新的編碼包所包含的原始數(shù)據(jù)包。圖中,每個(gè)虛線框包括了每一行中具有相同出現(xiàn)順序的0標(biāo)志位。例如,狀態(tài)矩陣T最左邊的虛線框包含了每一行中的第一個(gè)0標(biāo)志位。狀態(tài)矩陣中處于同一個(gè)虛線框的原始數(shù)據(jù)包將會被組合后形成新的編碼包,而狀態(tài)矩陣中其他的虛線框會按照相同的規(guī)則進(jìn)行數(shù)據(jù)包編碼。隨后,發(fā)送端依次將新形成的編碼包進(jìn)行發(fā)送。

需要特別指出的是,若某個(gè)編碼包在傳輸時(shí)發(fā)生錯誤,發(fā)送端會根據(jù)網(wǎng)絡(luò)狀態(tài)動態(tài)調(diào)整編碼策略。例如圖1中矩陣第3行第6列的圓圈代表第3個(gè)虛線框和第4個(gè)虛線框的重疊部分。這意味著由第3個(gè)虛線框所生成的編碼包沒有被接收端R3成功接收。此時(shí)圓圈位置處的標(biāo)志位將被置為0,而發(fā)送端進(jìn)行動態(tài)編碼策略調(diào)整,將數(shù)據(jù)包a6與第4個(gè)虛線框內(nèi)的原始數(shù)據(jù)包組合后形成編碼包。據(jù)此,發(fā)送端共依次生成6個(gè)編碼包c(diǎn)1～c6,并按照如下順序發(fā)送

(1)

(2)

(3)

(4)

(5)

(6)

式中:βij是從伽羅華域Fq中隨機(jī)獲得的網(wǎng)絡(luò)編碼系數(shù)。需要注意的是,與傳統(tǒng)的隨機(jī)網(wǎng)絡(luò)編碼將所有原始數(shù)據(jù)包進(jìn)行組合的方式不同,本文所提出的編碼算法會根據(jù)實(shí)時(shí)網(wǎng)絡(luò)狀態(tài)對原始數(shù)據(jù)包進(jìn)行動態(tài)組合。DLCCA與XOR編碼機(jī)制不同之處在于:在XOR中若一個(gè)XOR數(shù)據(jù)包丟失,發(fā)送端會重傳該XOR編碼包直至所有接收端都能正確接收到該編碼包;在DLCCA中,發(fā)送端利用線性無關(guān)的隨機(jī)系數(shù)對原始數(shù)據(jù)包進(jìn)行編碼并發(fā)送。根據(jù)線性代數(shù)理論可知接收端只要接收到足夠數(shù)量的編碼包便可以解出原始數(shù)據(jù)包,從而獲取比XOR更高的傳輸效率。DLCCA算法的代碼如下。

輸入N,M,P=[p1,p2,…,pM]

輸出 傳輸帶寬η

(1)初始化矩陣T=zeros(M,N),n

(2) fort=1:Ndo

(3)fori=1:Mdo

(4) if rand(1)>P(i) then

(5)T(t,i)=1;

(6)n=n+1;

(7) end if

(8)end for

(9) end for

(10)fort=1:Ndo

(11) fori=1:Mdo

(12)ifT(t,i)==0 then

(13) 獲取相應(yīng)的丟失數(shù)據(jù)包,T(t,i)=1;

(14)end if

(15) end for

(16)end for

(17)將這些數(shù)據(jù)包組合形成一個(gè)新的數(shù)據(jù)包并重新發(fā)送

(18)n=n+1;

(19)if某些接收節(jié)點(diǎn)接收新數(shù)據(jù)包失敗then

(20) 知陣T中相應(yīng)位置的值保持不變;

(21)end if

(22)執(zhí)行步驟10～18直到矩陣T中沒有0值;

(23)η=n/N。

3 確定線性組合重傳算法

在DLCCA算法中,發(fā)送端在編碼包傳輸發(fā)生錯誤后會動態(tài)地調(diào)整編碼包的組合形式,以此來實(shí)現(xiàn)更高的吞吐量,但該算法也同時(shí)帶來了更大的計(jì)算復(fù)雜度。對此,本文提出了一種稱為確定線性組合重傳算法(FLCCA)的新算法,可作為DLCCA的下界。與DLCCA一樣,FLCCA仍分為2個(gè)傳輸階段:原始數(shù)據(jù)包傳輸階段和編碼包傳輸階段。第一個(gè)階段即原始數(shù)據(jù)包傳輸階段與動態(tài)線性組合重傳算法DLCCA的第一階段相同;第二階段則根據(jù)狀態(tài)矩陣T選擇相對簡單的規(guī)則對原始數(shù)據(jù)包進(jìn)行組合。具體步驟與細(xì)節(jié)如下所述。

(1)與DLCCA算法機(jī)制相同,發(fā)送端首先查找狀態(tài)矩陣T中每一行的第一個(gè)0標(biāo)志位值所對應(yīng)的數(shù)據(jù)包,并將該組數(shù)據(jù)包組合形成新的編碼包。

(2)發(fā)送端將上一步驟形成的編碼包進(jìn)行發(fā)送。若在該階段傳輸中仍有部分接收端沒有成功接收到新的編碼包,發(fā)送端會再次重新發(fā)送該編碼包直至所有接收端都實(shí)現(xiàn)成功接收。此時(shí),狀態(tài)矩陣T中相應(yīng)為0的標(biāo)志位會更新為1。

(3)發(fā)送端根據(jù)接收端發(fā)送的反饋信息更新狀態(tài)矩陣,直至狀態(tài)矩陣中的所有元素都為1。

4 算法性能分析

4.1 DLCCA算法性能分析

假設(shè)網(wǎng)絡(luò)中有M個(gè)接收端,其誤包率遵循如下順序p1≤p2≤…≤pM。發(fā)送端進(jìn)行了N輪傳輸后,接收端R1,R2,…,RM的平均丟包數(shù)分別為Np1,Np2,…,NpM。根據(jù)DLCCA算法的編碼規(guī)則,在編碼包傳輸階段,如果一個(gè)編碼包沒有被某一接收端成功接收,就會依據(jù)狀態(tài)矩陣T形成一個(gè)新的編碼包,以確保與先前成功接收到的編碼包進(jìn)行聯(lián)合解碼,從而獲取所有的原始數(shù)據(jù)包。因此,從統(tǒng)計(jì)學(xué)角度來看,網(wǎng)絡(luò)的重傳次數(shù)主要取決于具有最高誤包率的接收端,而傳輸次數(shù)等于NpM(pM=max{p1,p2,…,pM})。將X記為一個(gè)接收端成功解出一個(gè)數(shù)據(jù)包的傳輸次數(shù),則X的期望為

(7)

因此,DLCCA的傳輸帶寬為

(8)

4.2 FLCCA算法性能分析

假設(shè)FLCCA和DLCCA算法具有相同的參數(shù)設(shè)定。根據(jù)FLCCA的編碼規(guī)則,第二階段中發(fā)送端可能會對某個(gè)組合編碼包進(jìn)行多輪重復(fù)發(fā)送。第一輪里,由于R1擁有最少數(shù)量的丟失數(shù)據(jù)包,因此接收端R1所有的丟失數(shù)據(jù)包都可以與R2,R3,…,RM的丟失數(shù)據(jù)包進(jìn)行組合,形成Np1個(gè)編碼包。當(dāng)這些編碼包均被所對應(yīng)的接收端正確接收后,R1,R2,…的丟失數(shù)據(jù)包數(shù)分別變?yōu)?,N(p2-p1),N(p3-p1),…,N(pM-p1)。在第二輪中,R2變成了擁有最少丟包的接收端,這些丟失的數(shù)據(jù)包將會與R3,R4,…,RM的丟失數(shù)據(jù)包進(jìn)行組合。經(jīng)過第二輪傳輸后,R1,R2,…,RM的丟失數(shù)據(jù)包數(shù)分別為0,0,N(p3-p2),…,N(pM-p2)。依據(jù)這一規(guī)律,在經(jīng)過M輪傳輸后,所有的丟失數(shù)據(jù)包均已經(jīng)被組合形成了新的編碼包。因此,將N個(gè)數(shù)據(jù)包成功傳給所有接收端的傳輸次數(shù)為

(9)

式中:φi表示在第i輪中將一個(gè)編碼包成功傳給所有相應(yīng)的接收端所需的平均重傳次數(shù)。因此,FLCCA算法的傳輸帶寬為

(10)

(11)

式中:z為傳播次數(shù)。

由式(7)可得

(12)

因此,將一個(gè)原始數(shù)據(jù)包成功傳給L(1≤L≤M)個(gè)接收端所需的平均傳輸次數(shù)為

(13)

式中:i1,i2,…,iL∈{0,1},并且?ij≠0。

在式(5)中,Np1個(gè)編碼包被M個(gè)接收端成功接收,N(p2-p1)個(gè)編碼包被M-1個(gè)接收端成功接收,以此類推。因此,根據(jù)φL的定義,可知φi=φM-i+1。

4.3 反饋信息性能分析

從反饋信息角度來看,在整個(gè)傳輸過程中(原始數(shù)據(jù)包的傳輸和編碼包的傳輸),每傳輸一次數(shù)據(jù)包,總會有M個(gè)反饋信息在一定的時(shí)間段Δt內(nèi)被反饋到發(fā)送節(jié)點(diǎn)。由于反饋信息只是反映數(shù)據(jù)包是否被接收節(jié)點(diǎn)成功地接收,因此所有的反饋信息數(shù)據(jù)量很小,且假設(shè)都被發(fā)送節(jié)點(diǎn)正確地接收到,那么DLCCA和FLCCA算法需要的平均反饋信息次數(shù)分別為nD和nF,平均傳送時(shí)間為tnD和tnF。因此,對于不同的重傳算法,不同的傳輸帶寬對應(yīng)的反饋信息的平均傳送時(shí)間也不一樣,傳輸帶寬越大的算法,對應(yīng)的反饋消息所占用的時(shí)間也越長,通信傳輸性能也越差,反之亦然。

5 仿真實(shí)驗(yàn)

在仿真實(shí)驗(yàn)中,將文獻(xiàn)[12]所提出的NC機(jī)制與本文提出的算法進(jìn)行比較。為了便于描述,文獻(xiàn)[12]中所提出的兩種編碼算法分別記為算法1和算法2。在下述的仿真實(shí)驗(yàn)中,原始數(shù)據(jù)包數(shù)量N設(shè)為1 000,同時(shí)設(shè)定如下4類場景。

場景1 假定接收端數(shù)量M=8,每個(gè)接收端的誤包率pi(i=1,2,…,8)均相同,且設(shè)定誤包率的值均從0.02變化到0.24。圖2給出了傳輸帶寬η的理論推導(dǎo)值和仿真結(jié)果。從圖2可以得出,在傳輸帶寬占用方面,本文所提出的兩種機(jī)制所需帶寬要明顯小于文獻(xiàn)[12]中提出的機(jī)制。同時(shí),本文提出的機(jī)制所對應(yīng)的仿真曲線與理論推導(dǎo)值曲線可以很好地吻合。此外,在參與對比的所有機(jī)制中傳輸帶寬占用情況都隨著誤包率的上升而增大,而隨著誤包率的上升,本文提出的機(jī)制與對比機(jī)制之間的差距變得更大,這也表明本文所提出的機(jī)制在網(wǎng)絡(luò)具有較高誤包率的情況下優(yōu)勢更加明顯。

圖2 不同誤包率下4種算法的傳輸帶寬

場景2 在該場景中論文研究接收端數(shù)目對平均傳輸帶寬的影響。仿真實(shí)驗(yàn)假設(shè)所有接收端的誤包率均相同且為0.12,而接收端數(shù)量則從2逐漸增加至12,如圖3所示。根據(jù)傳輸帶寬的理論與仿真結(jié)果可以看出,隨著接收端數(shù)量的增加,傳輸帶寬占用也隨之增大,但本文所提出的兩種傳送算法的傳輸帶寬占用始終低于其他傳送算法。更為重要的是,當(dāng)接收端數(shù)量明顯增大時(shí),本文提出的算法具有更明顯的優(yōu)勢,其性能要遠(yuǎn)優(yōu)于其他對比算法。同樣,從圖3中可以看到本文提出的算法的仿真結(jié)果與理論結(jié)果很吻合。

圖3 不同接收端數(shù)量時(shí)4種算法的傳輸帶寬

場景3 該場景研究較大誤包率(pi=0.24)和較小誤包率(pi=0.12)情形下的傳輸帶寬特性,并假設(shè)網(wǎng)絡(luò)中的每個(gè)接收端都具有相同的誤包率。仿真實(shí)驗(yàn)得到的結(jié)果如圖4所示,可以看到,無論在信道質(zhì)量好或壞的情況下,本文提出的算法在較大誤包率或較多接收端時(shí)均比傳統(tǒng)的算法具有更高的傳輸效率。因此,本文提出的算法更適合信道質(zhì)量較差時(shí)的數(shù)據(jù)傳輸。

圖4 誤包率較大及較小時(shí)4種算法的傳輸帶寬

圖5 原始數(shù)據(jù)包數(shù)對傳輸帶寬影響

場景4 在該場景中論文研究原始數(shù)據(jù)包數(shù)量對平均傳輸帶寬的影響。接收端數(shù)量設(shè)為12,且誤包率均為0.04。如圖5所示,根據(jù)傳輸帶寬的仿真結(jié)果可以看出,傳輸帶寬隨著數(shù)據(jù)包數(shù)的增長沒有變化,這說明該類機(jī)制不受原始數(shù)據(jù)包數(shù)量的影響,從而保證傳輸帶寬不受堆棧內(nèi)編碼數(shù)據(jù)包多少的影響。從圖5可以看出,本文所提出的兩種傳送算法的傳輸帶寬占用仍始終低于其他傳送算法。

6 結(jié)論和展望

本文提出了兩種可以在無線組播網(wǎng)絡(luò)中降低傳輸帶寬占用的重傳算法。在DLCCA算法中,發(fā)射端利用系統(tǒng)控制信道獲取接收端數(shù)據(jù)包接收狀態(tài),并根據(jù)當(dāng)前全網(wǎng)數(shù)據(jù)包接收狀態(tài)動態(tài)地利用隨機(jī)線性網(wǎng)絡(luò)編碼生成編碼包。在傳輸過程中,發(fā)射機(jī)不斷進(jìn)行編碼生成策略調(diào)整,從而有效提高網(wǎng)絡(luò)的整體吞吐量。此外,本文還提出了一種低復(fù)雜度的FLCCA算法,該機(jī)制對DLCCA在編碼包生成過程中進(jìn)行了化簡,從而降低了系統(tǒng)實(shí)現(xiàn)復(fù)雜度。最后,通過理論推導(dǎo)和仿真實(shí)驗(yàn)證明了本文所提出算法的傳輸效率與傳統(tǒng)的重傳算法相比具有明顯優(yōu)勢。

[1] ZHANG D, MANDAYAM N B. Analyzing random network coding with differential equations and differential inclusions [J]. IEEE Transactions on Information Theory, 2011, 57(12): 7932-7949.

[2] MOHAMMAD M, ZHANG Q, DUTKIEWICZ E. Reading damaged scripts: partial packet recovery based on compressive sensing for efficient random linear coded transmission [J]. IEEE Transactions on Communications, 2016, 64(2): 3296-3310.

[3] CHI K, JIANG X, HORIGUCHI S. A more efficient cope architecture for network coding in multi-hop wireless networks [J]. IEICE Transactions on Communications, 2009, 92(3): 766-775.

[4] LIU H, YANG H, WANG Y. CAR: coding-aware opportunistic routing for unicast traffic in wireless mesh networks [J]. Journal of Network & Systems Management, 2015, 23(4): 1-21.

[5] CHEN T, ZHONG S. An enforceable scheme for packet forwarding cooperation in network coding wireless networks with opportunistic routing [J]. IEEE Transactions on Vehicular Technology, 2014, 63(9): 4476-4491.

[6] 盧冀, 肖嵩, 吳成柯. 無線網(wǎng)絡(luò)中應(yīng)用機(jī)會式網(wǎng)絡(luò)編碼的廣播重傳方法 [J]. 西安交通大學(xué)學(xué)報(bào), 2011, 45(2): 68-72. LU Ji, XIAO Song, WU Chengke. A broadcast retransmission method using opportunistic network coding in wireless networks [J]. Journal of Xi’an Jiaotong University, 2011, 45(2): 68-72.

[7] LI H, LI B, TRAN T T, et al. Transmission schemes for multicasting hard deadline constrained prioritized data in wireless multimedia streaming [J]. IEEE Transactions on Wireless Communications, 2016, 15(3): 1631-1641.

[8] 王斌, 王文鼐. 一種基于并行網(wǎng)絡(luò)編碼的無線廣播重傳方案 [J]. 南京郵電大學(xué)學(xué)報(bào)(自然科學(xué)版), 2014, 34(6): 9-14. WANG Bin, WANG Wennai. Wireless broadcast retransmission scheme based on parallel network coding [J]. Journal of Nanjing University of Posts and Telecommunications (Natural Science Edition), 2014, 34(6): 9-14.

[9] DAI M, KWAN H Y, SUNG C W. Linear network coding strategies for the multiple access relay channel with packet erasures [J]. IEEE Transactions on Wireless Communications, 2013, 12(1): 218-227.

[10]SUN W, ZHANG G X, GOU L. Network coding based broadcasting retransmission approach in satellite communications [J]. Advanced Materials Research, 2012, 54(7): 1302-1307.

[11]REN Z, WEN Y, YAO Y. An improved wireless broadcasting retransmission approach based on network coding [C]∥Proceeding of IEEE International Conference on Wireless Communications, Networking & Mobile Computing. Piscataway, NJ, USA: IEEE, 2012: 1-4.

[12]NGUYEN D, TRAN T, NGUYEN T. Wireless broadcast using network coding [J]. IEEE Transactions on Vehicular Technology, 2009, 58(2): 914-925.

(編輯 劉楊)

A Retransmission Algorithm with Dynamic Linear Combination Based on Network Coding in Wireless Multicast Networks

LI Bin1,LI Quan1,ZHANG Ruonan1,JIANG Yi1,YANG Rong2

(1. School of Electronics and Information, Northwestern Polytechnical University, Xi’an 710072, China;2. Engineering Workshop, Xi’an Jiaotong University, Xi’an 710049, China)

A retransmission algorithm with dynamic linear combination based on the network coding is proposed to meet the demands for decreasing the packets retransmission, to overcome the wireless channel fading, to build reliable wireless connection and to improve the efficiency of the bandwidth utilization in multicast networks. A dynamic linear combining coding algorithm (DLCCA) is used in the algorithm. Firstly, the transmitter in DLCCA sends original packets to users in the network. Then, the transmitter obtains the receiving status feedback from the users through control channel, and encodes the original packets that have not been correctly decoded by the users. Meanwhile, the encoding strategy is dynamically adjusted based on the network status so that the network throughput is improved. Furthermore, a coding algorithm with lower complexity is proposed, and the performance of the coding algorithm is analyzed. Theoretical result is obtained through analysis. Simulation results and comparisons with the transmission algorithm without network coding and the traditional XOR network coding algorithm show that the proposed algorithm greatly reduces 30% of packet retransmission, and the network throughput is increased.

multicast networks; network coding; dynamic linear combination

2016-05-11。 作者簡介:李彬(1983—),男,博士,講師。 基金項(xiàng)目:國家自然科學(xué)基金資助項(xiàng)目(61202394,61571370,61203233,61601365);陜西省自然科學(xué)基金資助項(xiàng)目(2016JQ6017);中央高?；A(chǔ)科研基金資助項(xiàng)目(3102014 KYJD033,3102015ZY093)。

時(shí)間:2016-10-10

10.7652/xjtuxb201612007

TN92

A

0253-987X(2016)12-0038-07

網(wǎng)絡(luò)出版地址:http: ∥www.cnki.net/kcms/detail/61.1069.T.20161010.1753.008.html