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

蘆存博,肖 嵩,權 磊,薛 曉

(西安電子科技大學綜合業(yè)務網(wǎng)理論及關鍵技術國家重點實驗室,陜西西安 710071)

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

蘆存博,肖 嵩,權 磊,薛 曉

(西安電子科技大學綜合業(yè)務網(wǎng)理論及關鍵技術國家重點實驗室,陜西西安 710071)

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

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

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

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

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

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

1　算法的基本思想

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

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

在基于隊列長度的策略中,如果緩存的隊列長度超過1個閾值,數(shù)據(jù)包將會被無編碼地轉發(fā),該方法實施起來比較簡單.但如果閾值選取不當,數(shù)據(jù)包的等待時延可能較大,則可能對分組時延造成負面的影響.

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

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

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

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

文中的基于隊列長度的策略與文獻[10-11]不同的是,BLCAR設計的算法是基于一個實際的輸出隊列,而不是基于虛擬的隊列,對應于原來的不同虛擬緩存的最優(yōu)閾值是相同的.而在文獻[10-11]中,不同虛擬緩存的最優(yōu)閾值可能是不同的,并且對緩存隊列的長度沒有限制,最優(yōu)閾值可能達不到.

2.1編碼緩存建模

編碼節(jié)點處編碼緩存可劃分為兩份虛擬緩存,分別對應1條編碼流.編碼節(jié)點的緩存隊列長度可表示為一個二維隨機變量Y=(Y1,Y2),(Y1,Y2)隨時間的變化可模擬成一個馬爾可夫過程.

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

定理3 當基于隊列長度策略的閾值為L時,馬爾科夫鏈的穩(wěn)態(tài)概率的表達式為

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

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

下面通過仿真說明在基于隊列長度策略中,不同閾值對網(wǎng)絡時延的影響.

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

圖1　無線骨干網(wǎng)絡拓撲

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

圖2　不同閾值下的時延性能

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

BLCAR引入了網(wǎng)絡時延訓練階段,相當于獲得D(L)在L∈{0,1, 2,…,N-1}上的最小值對應的L,其中,N為編碼隊列的長度.

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

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

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

3.1網(wǎng)絡時延訓練

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

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

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

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

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

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

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

4　仿真實驗

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

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

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

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

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

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

5　結束語

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

[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)絡編碼的SVC高效傳輸系統(tǒng)[J].西安電子科技大學學報,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)絡出版時間：2015-10-21

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

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

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