一種編碼感知路由低時(shí)延數(shù)據(jù)傳輸算法

蘆存博,肖 嵩,權(quán) 磊,薛 曉

(西安電子科技大學(xué)綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室,陜西西安 710071)

一種編碼感知路由低時(shí)延數(shù)據(jù)傳輸算法

蘆存博,肖 嵩,權(quán) 磊,薛 曉

(西安電子科技大學(xué)綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室,陜西西安 710071)

當(dāng)前的編碼感知路由算法在數(shù)據(jù)包編碼時(shí)采用基于機(jī)會(huì)的網(wǎng)絡(luò)編碼策略,不會(huì)推遲數(shù)據(jù)包的轉(zhuǎn)發(fā)來(lái)等待未來(lái)的編碼機(jī)會(huì),這樣會(huì)降低網(wǎng)絡(luò)編碼對(duì)時(shí)延的貢獻(xiàn).為克服以上問(wèn)題,提出了一種基于緩存管理的編碼感知路由低時(shí)延數(shù)據(jù)傳輸算法.在編碼節(jié)點(diǎn),該算法采用基于隊(duì)列長(zhǎng)度的數(shù)據(jù)包決策策略來(lái)替代現(xiàn)有編碼感知路由算法中的基于機(jī)會(huì)的網(wǎng)絡(luò)編碼策略.該算法在數(shù)據(jù)傳輸階段之前引入了網(wǎng)絡(luò)時(shí)延訓(xùn)練階段,使編碼節(jié)點(diǎn)獲得了基于隊(duì)列長(zhǎng)度策略的最優(yōu)閾值.仿真結(jié)果表明,在網(wǎng)絡(luò)擁塞的情況下,此算法比傳統(tǒng)的基于機(jī)會(huì)的網(wǎng)絡(luò)編碼策略具有更低的數(shù)據(jù)包傳遞時(shí)延和數(shù)據(jù)包丟失率,并且具有更高的吞吐量.

網(wǎng)絡(luò)編碼;時(shí)延;緩存管理;路由

近年來(lái),隨著多媒體業(yè)務(wù)的發(fā)展,多媒體業(yè)務(wù)數(shù)據(jù)在網(wǎng)絡(luò)數(shù)據(jù)流量中占有越來(lái)越大的比例.一些多媒體業(yè)務(wù)需要考慮時(shí)延等方面的需求,這對(duì)無(wú)線網(wǎng)絡(luò)的設(shè)計(jì)提出了新的需求.數(shù)據(jù)包傳遞時(shí)延是網(wǎng)絡(luò)性能的重要指標(biāo)之一,對(duì)實(shí)時(shí)應(yīng)用尤為重要.

現(xiàn)有的以自組網(wǎng)按需平面距離矢量路由(Ad hoc On-demand Distance Vector routing,AODV)機(jī)制為代表的路由協(xié)議在數(shù)據(jù)包傳輸時(shí)采用存儲(chǔ)和轉(zhuǎn)發(fā)方式,網(wǎng)絡(luò)擁塞情況下的時(shí)延性能不能得到很好的改善.網(wǎng)絡(luò)編碼[1]的出現(xiàn)為彌補(bǔ)此類路由算法的不足提供了一條有效的路徑.在新的數(shù)據(jù)流與已有數(shù)據(jù)流可進(jìn)行編碼的條件下,新的數(shù)據(jù)流可與已有數(shù)據(jù)流編碼在一起,并在信道中被捎帶走,而不占用額外的信道容量,這樣可降低因排隊(duì)等待空閑信道所帶來(lái)的時(shí)延,達(dá)到降低時(shí)延[2]的目的.所謂編碼感知路由,是將“路由發(fā)現(xiàn)”和“編碼機(jī)會(huì)發(fā)現(xiàn)”兩者統(tǒng)一,即在路由發(fā)現(xiàn)的過(guò)程中發(fā)現(xiàn)編碼機(jī)會(huì).但當(dāng)前以分布式編碼感知路由(Distributed Coding-Aware Routing,DCAR)[3]機(jī)制為代表的編碼感知路由算法[3-8]都集中在網(wǎng)絡(luò)編碼的路由度量設(shè)計(jì)上,在數(shù)據(jù)傳輸階段,它們?cè)跀?shù)據(jù)包編碼時(shí)采用基于機(jī)會(huì)的網(wǎng)絡(luò)編碼策略COPE[9],當(dāng)無(wú)線信道可用時(shí),節(jié)點(diǎn)取出其輸出隊(duì)列的隊(duì)首數(shù)據(jù)包,檢查其輸出隊(duì)列中的其他數(shù)據(jù)包能否與此隊(duì)首數(shù)據(jù)包進(jìn)行編碼,如果能編碼,則編碼這些數(shù)據(jù)包,然后廣播轉(zhuǎn)發(fā);否則,節(jié)點(diǎn)直接將此數(shù)據(jù)包根據(jù)路由表轉(zhuǎn)發(fā)出去.

然而,基于機(jī)會(huì)的網(wǎng)絡(luò)編碼策略COPE沒(méi)有考慮編碼節(jié)點(diǎn)的緩存狀態(tài),不會(huì)推遲數(shù)據(jù)包的轉(zhuǎn)發(fā)來(lái)等待未來(lái)的編碼機(jī)會(huì).由于編碼節(jié)點(diǎn)相應(yīng)數(shù)據(jù)流的異步和隨機(jī)到達(dá),這種做法會(huì)損失掉一些潛在的編碼機(jī)會(huì),降低網(wǎng)絡(luò)編碼對(duì)時(shí)延的貢獻(xiàn).在網(wǎng)絡(luò)擁塞的情況下,考慮時(shí)延敏感業(yè)務(wù)的需要,降低無(wú)線網(wǎng)絡(luò)數(shù)據(jù)包傳遞時(shí)延對(duì)實(shí)時(shí)應(yīng)用有重要的意義.文中利用編碼緩存狀態(tài)改善編碼感知路由,以降低數(shù)據(jù)包投遞時(shí)延.

筆者在編碼感知路由的基礎(chǔ)上,從數(shù)據(jù)傳輸?shù)慕嵌瘸霭l(fā),提出了一種基于緩存管理的編碼感知路由低時(shí)延數(shù)據(jù)傳輸算法(Buffer management based Low-delay data transmission algorithm in Coding Aware Routing,BLCAR),該算法在數(shù)據(jù)包編碼時(shí)采用基于隊(duì)列長(zhǎng)度的策略,并在數(shù)據(jù)傳輸階段之前引入了網(wǎng)絡(luò)時(shí)延訓(xùn)練階段,使編碼節(jié)點(diǎn)獲得了基于隊(duì)列長(zhǎng)度策略的最優(yōu)閾值,理論分析和仿真實(shí)驗(yàn)說(shuō)明了該算法的有效性.在網(wǎng)絡(luò)擁塞的情況下,該算法比傳統(tǒng)的基于機(jī)會(huì)的網(wǎng)絡(luò)編碼策略具有更低的數(shù)據(jù)包傳遞時(shí)延和數(shù)據(jù)包丟失率,并且具有更高的吞吐量.

1　算法的基本思想

根據(jù)文獻(xiàn)[8],3個(gè)以上數(shù)據(jù)包的可編碼概率遠(yuǎn)遠(yuǎn)低于兩個(gè)數(shù)據(jù)包的可編碼概率,不失一般性,假設(shè)文中算法的可編碼數(shù)據(jù)流的條數(shù)為2.

在數(shù)據(jù)包編碼時(shí)考慮編碼緩存狀態(tài)的情況下,若推遲數(shù)據(jù)包的轉(zhuǎn)發(fā)來(lái)等待未來(lái)的編碼機(jī)會(huì),一條數(shù)據(jù)流的數(shù)據(jù)包必須等待另一條數(shù)據(jù)流的數(shù)據(jù)包到來(lái)時(shí)才能進(jìn)行編碼.這可能會(huì)引入大量的等待時(shí)延,從而增加網(wǎng)絡(luò)的數(shù)據(jù)包傳遞時(shí)延,并造成大量的數(shù)據(jù)包丟失,這是因?yàn)榫幋a緩存的隊(duì)列長(zhǎng)度是有限的.此時(shí)如果允許一部分?jǐn)?shù)據(jù)包不編碼而直接進(jìn)行轉(zhuǎn)發(fā),將會(huì)起到減少數(shù)據(jù)包傳遞時(shí)延和數(shù)據(jù)包丟失的作用,但是這樣會(huì)失去一部分編碼機(jī)會(huì),降低網(wǎng)絡(luò)編碼的貢獻(xiàn).因此,需要一種緩存管理策略實(shí)現(xiàn)編碼機(jī)會(huì)和等待時(shí)延的權(quán)衡,達(dá)到網(wǎng)絡(luò)的時(shí)延最優(yōu).由文獻(xiàn)[10-11]可知,基于隊(duì)列長(zhǎng)度的策略能夠達(dá)到編碼機(jī)會(huì)和等待時(shí)延的很好的權(quán)衡,達(dá)到數(shù)據(jù)包傳遞時(shí)延最優(yōu).

在基于隊(duì)列長(zhǎng)度的策略中,如果緩存的隊(duì)列長(zhǎng)度超過(guò)1個(gè)閾值,數(shù)據(jù)包將會(huì)被無(wú)編碼地轉(zhuǎn)發(fā),該方法實(shí)施起來(lái)比較簡(jiǎn)單.但如果閾值選取不當(dāng),數(shù)據(jù)包的等待時(shí)延可能較大,則可能對(duì)分組時(shí)延造成負(fù)面的影響.

BLCAR的基本思想是在編碼感知路由發(fā)現(xiàn)的基礎(chǔ)上,利用編碼緩存狀態(tài)來(lái)改善編碼感知路由.通過(guò)網(wǎng)絡(luò)時(shí)延訓(xùn)練階段測(cè)出編碼節(jié)點(diǎn)所使用的基于隊(duì)列長(zhǎng)度策略的最優(yōu)閾值,從而可在數(shù)據(jù)傳輸階段使編碼節(jié)點(diǎn)采用最優(yōu)的基于隊(duì)列長(zhǎng)度的策略傳輸數(shù)據(jù)包,以降低數(shù)據(jù)包傳遞時(shí)延.算法步驟如下:

(1)網(wǎng)絡(luò)時(shí)延訓(xùn)練:對(duì)經(jīng)過(guò)路由發(fā)現(xiàn)后在路徑上尋找出的編碼節(jié)點(diǎn),用基于隊(duì)列長(zhǎng)度策略的緩存管理方式進(jìn)行網(wǎng)絡(luò)時(shí)延訓(xùn)練,實(shí)現(xiàn)最優(yōu)閾值的選取.

(2)數(shù)據(jù)傳輸:根據(jù)編碼節(jié)點(diǎn)的最優(yōu)閾值選擇網(wǎng)絡(luò)數(shù)據(jù)傳輸方案,即中間節(jié)點(diǎn)根據(jù)編碼機(jī)會(huì)、緩存狀態(tài)和給定的最優(yōu)閾值對(duì)接收到的數(shù)據(jù)包進(jìn)行編碼轉(zhuǎn)發(fā)、直接轉(zhuǎn)發(fā)或等待.

2　算法的理論依據(jù)

文中的基于隊(duì)列長(zhǎng)度的策略與文獻(xiàn)[10-11]不同的是,BLCAR設(shè)計(jì)的算法是基于一個(gè)實(shí)際的輸出隊(duì)列,而不是基于虛擬的隊(duì)列,對(duì)應(yīng)于原來(lái)的不同虛擬緩存的最優(yōu)閾值是相同的.而在文獻(xiàn)[10-11]中,不同虛擬緩存的最優(yōu)閾值可能是不同的,并且對(duì)緩存隊(duì)列的長(zhǎng)度沒(méi)有限制,最優(yōu)閾值可能達(dá)不到.

2.1編碼緩存建模

編碼節(jié)點(diǎn)處編碼緩存可劃分為兩份虛擬緩存,分別對(duì)應(yīng)1條編碼流.編碼節(jié)點(diǎn)的緩存隊(duì)列長(zhǎng)度可表示為一個(gè)二維隨機(jī)變量Y=(Y1,Y2),(Y1,Y2)隨時(shí)間的變化可模擬成一個(gè)馬爾可夫過(guò)程.

根據(jù)定理1,在每個(gè)觀察窗口內(nèi),編碼隊(duì)列中只可能有1種類型的數(shù)據(jù)包.由于實(shí)際中只存在1個(gè)輸出隊(duì)列,在BLCAR中,假定對(duì)應(yīng)于原來(lái)的兩份虛擬緩存的最優(yōu)閾值是相同的設(shè)計(jì),是合理的.當(dāng)基于隊(duì)列長(zhǎng)度策略的閾值是L時(shí),馬爾科夫鏈的狀態(tài)空間為{(0,L),(0,L-1),…,(0,1),(0,0),(1,0),…,(L-1,0), (L,0}),根據(jù)定理2,當(dāng)緩存狀態(tài)發(fā)生變化時(shí),狀態(tài)轉(zhuǎn)移只可能發(fā)生在相鄰狀態(tài)之間.在網(wǎng)絡(luò)達(dá)到穩(wěn)定的情況下,假設(shè)編碼流i到達(dá)對(duì)應(yīng)編碼緩存隊(duì)列的概率為θi,令πi,j表示馬爾科夫鏈中狀態(tài)空間(i,j)的穩(wěn)態(tài)概率.

定理3 當(dāng)基于隊(duì)列長(zhǎng)度策略的閾值為L(zhǎng)時(shí),馬爾科夫鏈的穩(wěn)態(tài)概率的表達(dá)式為

根據(jù)定理3,在網(wǎng)絡(luò)達(dá)到穩(wěn)定時(shí),可用1個(gè)時(shí)間觀察窗口內(nèi)的性能度量表征網(wǎng)絡(luò)的長(zhǎng)期性能,這由馬爾科夫鏈的穩(wěn)態(tài)性質(zhì)所決定.為定性分析BLCAR的數(shù)據(jù)包傳遞時(shí)延,可定性分析1個(gè)觀察窗口內(nèi)的數(shù)據(jù)包傳遞時(shí)延.

2.2最優(yōu)閾值的計(jì)算

下面通過(guò)仿真說(shuō)明在基于隊(duì)列長(zhǎng)度策略中,不同閾值對(duì)網(wǎng)絡(luò)時(shí)延的影響.

文中采用NS2.35仿真平臺(tái),在如圖1所示的無(wú)線骨干網(wǎng)絡(luò)拓?fù)渲?分析比較了在編碼感知路由中編碼節(jié)點(diǎn)采用基于隊(duì)列長(zhǎng)度的緩存管理策略不同閾值下的平均端到端時(shí)延變化,如圖2所示.文中仿真采用用戶數(shù)據(jù)報(bào)協(xié)議(User Datagram Protocol,UDP)數(shù)據(jù)源,媒體接入控制(Media Access Control,MAC)層協(xié)議采用IEEE802.11的分布式協(xié)調(diào)功能(Distributed Coordination Function,DCF)機(jī)制,在仿真的網(wǎng)絡(luò)中存在兩條數(shù)據(jù)流,分別為數(shù)據(jù)流1和數(shù)據(jù)流2,其中,數(shù)據(jù)流1的源節(jié)點(diǎn)是節(jié)點(diǎn)A,目的節(jié)點(diǎn)是節(jié)點(diǎn)C;數(shù)據(jù)流2的源節(jié)點(diǎn)是節(jié)點(diǎn)C,目的節(jié)點(diǎn)是節(jié)點(diǎn)E.數(shù)據(jù)流1和數(shù)據(jù)流2兩者速率相等且為350 kb/s,其中編碼感知路由發(fā)現(xiàn)階段的路由度量采用考慮編碼機(jī)會(huì)的路由跳數(shù).

圖1　無(wú)線骨干網(wǎng)絡(luò)拓?fù)?/p>

從圖2可以看出,在基于隊(duì)列長(zhǎng)度的策略中,不同閾值對(duì)應(yīng)的平均端到端時(shí)延不同,這是由于編碼緩存中等待時(shí)延和由于數(shù)據(jù)包等待從而擁有的編碼機(jī)會(huì),兩者對(duì)網(wǎng)絡(luò)時(shí)延性能不同權(quán)衡的緣故.結(jié)果表明,閾值的選取非常重要,如果閾值選取不當(dāng),網(wǎng)絡(luò)時(shí)延性能會(huì)受到很大影響.

圖2　不同閾值下的時(shí)延性能

為表征網(wǎng)絡(luò)的數(shù)據(jù)包傳遞時(shí)延,可用1個(gè)觀察窗口內(nèi)的平均數(shù)據(jù)包等待時(shí)延來(lái)表征,即

BLCAR引入了網(wǎng)絡(luò)時(shí)延訓(xùn)練階段,相當(dāng)于獲得D(L)在L∈{0,1, 2,…,N-1}上的最小值對(duì)應(yīng)的L,其中,N為編碼隊(duì)列的長(zhǎng)度.

在網(wǎng)絡(luò)時(shí)延訓(xùn)練階段,編碼節(jié)點(diǎn)可通過(guò)遍歷從0到N-1之間的基于隊(duì)列長(zhǎng)度策略的每個(gè)閾值在一個(gè)固定的采樣間隔(例如0.2 s)內(nèi)的成功傳輸數(shù)據(jù)包的平均等待時(shí)延,并通過(guò)其大小比較,來(lái)搜索出相應(yīng)的最優(yōu)閾值,因?yàn)榫幋a隊(duì)列的長(zhǎng)度N是有限的,一般為幾十,最優(yōu)閾值可很快獲得.

傳統(tǒng)編碼感知路由算法采用的是基于機(jī)會(huì)的網(wǎng)絡(luò)編碼策略COPE,相當(dāng)于L=0的場(chǎng)景D(0),是基于隊(duì)列長(zhǎng)度策略的一個(gè)特例,其閾值是0,而BLCAR算法引入了網(wǎng)絡(luò)時(shí)延訓(xùn)練階段獲得了基于隊(duì)列長(zhǎng)度策略的最優(yōu)閾值,設(shè)其為L(zhǎng)*,可得到D(L*)≤D(0).所以,BLCAR的數(shù)據(jù)包傳遞時(shí)延要優(yōu)于相應(yīng)的基于機(jī)會(huì)的網(wǎng)絡(luò)編碼策略.

3　算法具體實(shí)現(xiàn)

3.1網(wǎng)絡(luò)時(shí)延訓(xùn)練

定義mi為編碼節(jié)點(diǎn)對(duì)應(yīng)閾值i在采樣間隔t內(nèi)傳輸?shù)臄?shù)據(jù)包個(gè)數(shù),其中有mci個(gè)編碼數(shù)據(jù)包.L為編碼節(jié)點(diǎn)的編碼隊(duì)列長(zhǎng)度,pij為編碼節(jié)點(diǎn)對(duì)應(yīng)閾值i在采樣間隔t內(nèi)收到的第j個(gè)數(shù)據(jù)包,B(pij)和A(pij)分別表示數(shù)據(jù)包pij在編碼隊(duì)列中的出隊(duì)時(shí)間和入隊(duì)時(shí)間.

基于以上分析,表征基于隊(duì)列長(zhǎng)度策略的每一個(gè)閾值i的數(shù)據(jù)包平均等待時(shí)延為

(1)將閾值i初始化為0,源節(jié)點(diǎn)發(fā)送數(shù)據(jù)包,編碼節(jié)點(diǎn)用基于隊(duì)列長(zhǎng)度策略的緩存管理方式對(duì)來(lái)自不同數(shù)據(jù)流的數(shù)據(jù)包進(jìn)行有效傳輸或等待,在數(shù)據(jù)傳輸穩(wěn)定時(shí),在一個(gè)固定的采樣間隔t內(nèi),記錄下傳輸?shù)拿總€(gè)數(shù)據(jù)包p0j對(duì)于編碼緩存隊(duì)列中的入隊(duì)時(shí)間A(p0j)和出隊(duì)時(shí)間B(p0j),并統(tǒng)計(jì)傳輸?shù)臄?shù)據(jù)包個(gè)數(shù)m0和編碼包個(gè)數(shù)mc0,根據(jù)式(4),計(jì)算得到D0,并同時(shí)使閾值i加1,重復(fù)上述過(guò)程,節(jié)點(diǎn)可得到對(duì)應(yīng)閾值i在間隔t內(nèi)的數(shù)值D0,D1,…,DL-1.

(2)從上述得到的D0,D1,…,DL-1中找出數(shù)值最小的元素的下標(biāo),作為最優(yōu)的閾值.

3.2數(shù)據(jù)傳輸

定義L*為網(wǎng)絡(luò)時(shí)延訓(xùn)練階段編碼節(jié)點(diǎn)所獲得的基于隊(duì)列長(zhǎng)度策略的最優(yōu)閾值.中間節(jié)點(diǎn)數(shù)據(jù)傳輸?shù)牧鞒虉D如圖3所示.在中間節(jié)點(diǎn),當(dāng)收到的數(shù)據(jù)包是編碼包時(shí),則該中間節(jié)點(diǎn)檢查解碼緩存中是否有用于解碼此編碼包的其余數(shù)據(jù)流信息,如果沒(méi)有,則丟棄該編碼包;如果有,則分離出需要的數(shù)據(jù)流的原始包;對(duì)從編碼包中分離出來(lái)的原始包和未經(jīng)過(guò)分離的原始包進(jìn)行判斷,判斷此中間節(jié)點(diǎn)是否是編碼節(jié)點(diǎn):如果此中間節(jié)點(diǎn)不是編碼節(jié)點(diǎn),則將此原始包根據(jù)路由表轉(zhuǎn)發(fā)出去;如果該中間節(jié)點(diǎn)是編碼節(jié)點(diǎn),則檢查該中間節(jié)點(diǎn)是否有其他路徑上的數(shù)據(jù)包到達(dá),如果有,則對(duì)來(lái)自不同路徑的數(shù)據(jù)包進(jìn)行編碼轉(zhuǎn)發(fā);如果沒(méi)有,則該中間節(jié)點(diǎn)把其插入到編碼緩存中,然后檢查該緩存隊(duì)列的長(zhǎng)度,設(shè)為L(zhǎng),并執(zhí)行以下步驟:如果L＞L*,則直接無(wú)編碼轉(zhuǎn)發(fā);否則,在編碼隊(duì)列中進(jìn)行等待.

圖3　中間節(jié)點(diǎn)數(shù)據(jù)傳輸描述

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

比較了在網(wǎng)絡(luò)擁塞的情況下AODV路由算法、基于機(jī)會(huì)的網(wǎng)絡(luò)編碼策略COPE的編碼感知路由算法(COPE-based coding aware routing,COPE-based)和文中算法BLCAR的平均端到端時(shí)延、網(wǎng)絡(luò)吞吐量和數(shù)據(jù)包丟失率3種網(wǎng)絡(luò)性能,分別如圖4(a)、圖4(b)和圖4(c)所示.其中,緩存隊(duì)列的大小為50,網(wǎng)絡(luò)時(shí)延訓(xùn)練中節(jié)點(diǎn)采樣間隔采用經(jīng)驗(yàn)值0.2 s.數(shù)據(jù)流1和數(shù)據(jù)流2兩者速率相等且為220～400 kb/s.

從圖4(a)可以看出,對(duì)于BLCAR算法,從數(shù)據(jù)發(fā)送速率大于220 kb/s開始,沖突開始出現(xiàn),路由節(jié)點(diǎn)的發(fā)送隊(duì)列中開始積累數(shù)據(jù)包,隨著網(wǎng)絡(luò)負(fù)載的增加,平均端到端時(shí)延開始迅速增加,最后在260 kb/s處達(dá)到相對(duì)穩(wěn)定的狀態(tài).對(duì)于3種算法的平均端到端時(shí)延,文中算法BLCAR的時(shí)延性能最好,COPE-based算法次之.原因是BLCAR算法既考慮了網(wǎng)絡(luò)編碼的特性,又考慮了基于時(shí)延最優(yōu)的緩存管理策略,而AODV算法兩種特性都沒(méi)考慮,COPE-based算法采用了基于機(jī)會(huì)的網(wǎng)絡(luò)編碼策略,只考慮了網(wǎng)絡(luò)編碼的特性,但沒(méi)有考慮數(shù)據(jù)包編碼時(shí)的緩存狀態(tài).在穩(wěn)定狀態(tài)下,BLCAR算法的平均端到端延時(shí)要比COPE-based算法的平均降低了0.395 s.

從圖4(b)和圖4(c)可以看出,BLCAR算法的網(wǎng)絡(luò)吞吐量性能和數(shù)據(jù)包丟失率性能在3種算法中是最好的,COPE-based算法次之.這是由于AODV算法沒(méi)有網(wǎng)絡(luò)編碼的功能,COPE-based算法采用了網(wǎng)絡(luò)編碼,在瓶頸節(jié)點(diǎn)處能減少數(shù)據(jù)的傳輸次數(shù),緩解了信道沖突,使得能夠傳送更多的數(shù)據(jù)包.BLCAR算法考慮了網(wǎng)絡(luò)編碼的特性和基于時(shí)延最優(yōu)的緩存管理策略,在單位時(shí)間內(nèi)比COPE-based算法能夠傳送更多的數(shù)據(jù)包.

圖4　不同速率下的網(wǎng)絡(luò)性能比較

圖5　不同跳數(shù)下的網(wǎng)絡(luò)性能比較

上述仿真場(chǎng)景下,數(shù)據(jù)流1的轉(zhuǎn)發(fā)路徑為A→B→C,對(duì)應(yīng)的路由跳數(shù)為2;數(shù)據(jù)流2的轉(zhuǎn)發(fā)路徑為C→B→E,對(duì)應(yīng)的路由跳數(shù)為2.在數(shù)據(jù)流1和數(shù)據(jù)流2兩者速率相等且為400 kb/s,數(shù)據(jù)流1目的節(jié)點(diǎn)分別是節(jié)點(diǎn)C、節(jié)點(diǎn)D和節(jié)點(diǎn)H的情況下,對(duì)網(wǎng)絡(luò)性能進(jìn)行仿真,可得到此時(shí)數(shù)據(jù)流1的轉(zhuǎn)發(fā)路徑的對(duì)應(yīng)路由跳數(shù)分別是2、3和4.圖5(a)、圖5(b)和圖5(c)分別顯示了相應(yīng)的3種算法的性能變化.可以看出,BLCAR算法在平均端到端時(shí)延、網(wǎng)絡(luò)吞吐量和數(shù)據(jù)包丟失率方面的優(yōu)勢(shì)在3種算法中是最明顯的.

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

為提高編碼感知路由的分組時(shí)延性能,在編碼感知路由的基礎(chǔ)上,筆者提出了一種高效的數(shù)據(jù)傳輸算法BLCAR,其在編碼節(jié)點(diǎn)采用基于時(shí)延最優(yōu)的隊(duì)列長(zhǎng)度緩存管理策略對(duì)數(shù)據(jù)包進(jìn)行傳輸.理論分析和仿真實(shí)驗(yàn)說(shuō)明了文中算法的有效性.在網(wǎng)絡(luò)擁塞的情況下,該算法比傳統(tǒng)的基于機(jī)會(huì)的網(wǎng)絡(luò)編碼策略具有更低的數(shù)據(jù)包傳遞時(shí)延和數(shù)據(jù)包丟失率,并且具有更高的吞吐量.文中研究的算法對(duì)于基于網(wǎng)絡(luò)編碼的多媒體業(yè)務(wù)的實(shí)時(shí)應(yīng)用的實(shí)現(xiàn)具有參考價(jià)值.

[1]AHLSWEDE R,CAI N,LI S Y R,et al.Network Information Flow[J].IEEE Transactions on Information Theory, 2000,46(4):1204-1216.

[2]盧冀,肖嵩,吳成柯.基于網(wǎng)絡(luò)編碼的SVC高效傳輸系統(tǒng)[J].西安電子科技大學(xué)學(xué)報(bào),2010,37(3):405-411. LU Ji,XIAO Song,WU Chengke.Efficient SVC Transmission System Based on Network Coding[J].Journal of Xidian University,2010,37(3):405-411.

[3]LE J,LUI J C S,CHIU D M.DCAR:Distributed Coding-aware Routing in Wireless Networks[J].IEEE Transactions on Mobile Computing,2010,9(4):596-608.

[4]SHAO X,WANG C X,RAO Y.Network Coding Aware QoS Routing for Wireless Sensor Network[J].Journal of Communications,2015,10(1):24-32.

[5]SHAO X,WANG R C,HUANG H P,et al.Load Balanced Coding Aware Multipath Routing for Wireless Mesh Networks[J].Chinese Journal of Electronics,2015,24(1):8-12.

[6]GENG R,NING Z L,YE N.A Load-balancing and Coding-aware Multicast Protocol for Mobile Ad Hoc Networks[J/ OL].[2015-03-02].http://onlinelibrary.wiley.com/doi/10.1002/dac.2928/full.

[7]YUE H,ZHU X,ZHANG C,et al.Cptt:A High-throughput Coding-aware Routing Metric for Multi-hop Wireless Networks[C]//Proceedings of 2012 IEEE Global Communications Conference.New York:IEEE,2012:5687-5692.

[8]WANG W,WU W,GUAN Q,et al.TCAR:A New Network Coding-aware Routing Mechanism Based on Local Topology Detection[J].Journal of Central South University,2014,21(8):3178-3185.

[9]KATTI S,RAHUL H,HU W,et al.XORs in the Air:Practical Wireless Network Coding[J].IEEE/ACM Transactions on Networking,2008,16(3):497-510.

[10]HSU Y P,ABEDINI N,RAMASAMY S,et al.Opportunities for Network Coding:to Wait or Not to Wait[C]// Proceedings of 2011 IEEE International Symposium on Information Theory.Piscataway:IEEE,2011:791-795.

[11]MOHAPATRA A,GAUTAM N,SHAKKOTTAI S,et al.Network Coding Decisions for Wireless Transmissions with Delay Consideration[J].IEEE Transactions on Communications,2014,62(8):2965-2976.

(編輯:齊淑娟)

Low-delay data transmission algorithm for coding-aware routing

LU Cunbo,XIAO Song,QUAN Lei,XUE Xiao
(State Key Lab.of Integrated Service Networks,Xidian Univ.,Xi’an 710071,China)

It is significant to reduce packet delivery delay for real-time applications in a wireless network. Existing coding aware routing algorithms use the opportunistic coding scheme in the packet coding algorithm.They never delay packets to wait for the arrival of a future coding opportunity which results in the degradation of the contribution of network coding to delay performance.To overcome the above problem,for coding-aware routing,this paper presents a low-delay data transmission algorithm based buffer management.In the coding node,this algorithm decides packets according to the queue-length based threshold policy instead of the regular opportunistic coding policy as used in existing coding-aware routing algorithms.This algorithm introduces the network delay training phase before the data transmission phase to make the coding node obtain the optimal threshold for the queue-length based threshold policy. Simulation results show that our algorithm can achieve a lower packet delivery delay,a lower packet loss ratio and a higher throughput than the traditional opportunistic coding policy in network congestion.

network coding;delay;buffer management;routing

TN913.1+1

A

1001-2400(2016)04-0017-06

10.3969/j.issn.1001-2400.2016.04.004

2015-05-18 網(wǎng)絡(luò)出版時(shí)間：2015-10-21

國(guó)家自然科學(xué)基金資助項(xiàng)目(61372069);高等學(xué)校學(xué)科創(chuàng)新引智計(jì)劃(111計(jì)劃)資助項(xiàng)目(B08038)

蘆存博(1989-),男,西安電子科技大學(xué)博士研究生,E-mail:444180647@qq.com.

網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/61.1076.TN.20151021.1046.008.html