楊　湘, 王偉平, 王建新

(1. 中南大學(xué)信息科學(xué)與工程學(xué)院, 湖南 長(zhǎng)沙 410083;2. 武漢科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 湖北 武漢 430081)

?

無(wú)線mesh網(wǎng)絡(luò)中編碼感知的跨層優(yōu)化機(jī)制

楊湘1,2, 王偉平1, 王建新1

(1. 中南大學(xué)信息科學(xué)與工程學(xué)院, 湖南 長(zhǎng)沙 410083;2. 武漢科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 湖北 武漢 430081)

摘要：無(wú)線網(wǎng)絡(luò)的廣播和易于偵聽(tīng)的特點(diǎn),使得網(wǎng)絡(luò)編碼技術(shù)能夠很好地應(yīng)用于無(wú)線網(wǎng)絡(luò)中,以提高無(wú)線網(wǎng)絡(luò)的吞吐量。通過(guò)理論分析和仿真實(shí)驗(yàn)發(fā)現(xiàn),IEEE802.11標(biāo)準(zhǔn)的MAC層機(jī)制會(huì)使得成功競(jìng)爭(zhēng)到信道的節(jié)點(diǎn)在短時(shí)間內(nèi)在競(jìng)爭(zhēng)信道方面更具優(yōu)勢(shì),這會(huì)導(dǎo)致編碼節(jié)點(diǎn)在短期內(nèi)獲得的屬于不同編碼流的數(shù)據(jù)包數(shù)目不均衡,從而喪失很多的編碼機(jī)會(huì)。提出了一種跨層協(xié)作的優(yōu)化機(jī)制,在編碼節(jié)點(diǎn)根據(jù)編碼流的隊(duì)列占用情況計(jì)算編碼流的優(yōu)先級(jí)別,并將其發(fā)送給相應(yīng)上游節(jié)點(diǎn)以調(diào)節(jié)MAC層參數(shù),進(jìn)而平衡編碼節(jié)點(diǎn)中參與編碼的不同流的隊(duì)列占用率,增加編碼機(jī)會(huì)。仿真實(shí)驗(yàn)結(jié)果表明,這種編碼感知的跨層優(yōu)化機(jī)制,能夠很好地協(xié)調(diào)參與編碼的流的速率,提高了整個(gè)網(wǎng)絡(luò)的吞吐量。

關(guān)鍵詞：無(wú)線mesh網(wǎng)絡(luò); MAC協(xié)議; 網(wǎng)絡(luò)編碼; 跨層優(yōu)化

0引言

無(wú)線網(wǎng)絡(luò)天生具有的廣播和易于偵聽(tīng)的特性,使得網(wǎng)絡(luò)編碼技術(shù)能夠很好地應(yīng)用于無(wú)線網(wǎng)絡(luò)環(huán)境,提高了網(wǎng)絡(luò)的吞吐能力。流間編碼的研究主要針對(duì)網(wǎng)絡(luò)局部范圍的編碼和解碼,文獻(xiàn)[1]中首次提出了結(jié)合流間編碼的轉(zhuǎn)發(fā)機(jī)制COPE,其基本思想是編碼節(jié)點(diǎn)通過(guò)對(duì)編碼條件的判定,將屬于不同單播流的數(shù)據(jù)包進(jìn)行編碼操作,然后再進(jìn)行廣播發(fā)送;而參與編碼的單播流的下游節(jié)點(diǎn)通過(guò)對(duì)鄰居節(jié)點(diǎn)的偵聽(tīng),保證對(duì)接收到的編碼包以一個(gè)足夠大的概率進(jìn)行解碼,得到原始數(shù)據(jù)包。通過(guò)這樣的方式,在一次傳輸時(shí)間內(nèi),發(fā)送了多個(gè)數(shù)據(jù)包,從而減少了傳輸次數(shù),提高了網(wǎng)絡(luò)的整體吞吐量。

COPE機(jī)制提出之后,人們針對(duì)流間編碼機(jī)制進(jìn)行了大量的研究。一部分研究工作集中在編碼方案的設(shè)計(jì)和性能分析上,而另一部分研究工作則集中在基于編碼感知的路由協(xié)議方面。在針對(duì)編碼方案設(shè)計(jì)的研究工作中,人們針對(duì)各種不同的網(wǎng)絡(luò)場(chǎng)景提出了多種編碼方案。其中文獻(xiàn)[2]在2跳局部網(wǎng)絡(luò)場(chǎng)景下考慮了2條流進(jìn)行編碼的情況,對(duì)COPE進(jìn)行建模,并分析了其性能表現(xiàn)以及相對(duì)傳統(tǒng)的單徑路由的吞吐量增益;文獻(xiàn)[3]則分析了在2跳局部網(wǎng)絡(luò)場(chǎng)景多條流進(jìn)行編碼的情況下,不同的流數(shù)量對(duì)吞吐量的影響,并基于“編碼對(duì)齊”提出了一種編碼機(jī)制,有效地提高了網(wǎng)絡(luò)的吞吐量;另外文獻(xiàn)[4-6]則利用“干擾對(duì)齊”、“線性規(guī)劃”和“整數(shù)規(guī)劃”等技術(shù)討論了編碼方案的設(shè)計(jì)與實(shí)現(xiàn);文獻(xiàn)[7]則通過(guò)建立網(wǎng)絡(luò)效用最大化方程,分析并設(shè)計(jì)了一種結(jié)合流間編碼和流內(nèi)編碼的編碼機(jī)制,在考慮鏈路丟包率和不需要鄰居節(jié)點(diǎn)偵聽(tīng)隊(duì)列信息的情況下,能很好地提高網(wǎng)絡(luò)的吞吐量。目前研究的編碼系統(tǒng)分為兩種:確定編碼系統(tǒng)和隨機(jī)編碼系統(tǒng),確定編碼系統(tǒng)中根據(jù)顯式的通知報(bào)文來(lái)做出編碼決策;而隨機(jī)編碼系統(tǒng)根據(jù)偵聽(tīng)鏈路的報(bào)文傳輸成功概率來(lái)做出編碼決策,文獻(xiàn)[8]推導(dǎo)出了確定編碼系統(tǒng)下的吞吐量區(qū)間以及隨機(jī)編碼系統(tǒng)下的編碼限制區(qū)域,并提出了一種簡(jiǎn)單高效的編碼機(jī)制,能很好地提高吞吐量。在文獻(xiàn)[9]中作者研究了在考慮一條多播流或多條單播流的不同場(chǎng)景下網(wǎng)絡(luò)編碼機(jī)制的收益區(qū)間。文獻(xiàn)[10]研究了在IEEE802.11s機(jī)制下編碼延時(shí)對(duì)無(wú)線mesh網(wǎng)絡(luò)吞吐量的影響,并提出了一種自適應(yīng)調(diào)整編碼延時(shí)的機(jī)制,以提高網(wǎng)絡(luò)編碼的吞吐量增益。

此外,大量的研究工作都集中在基于編碼感知的路由協(xié)議方面,這類(lèi)研究工作的出發(fā)點(diǎn)在于利用流間網(wǎng)絡(luò)編碼提高吞吐量的特點(diǎn),在尋找路由時(shí)將編碼機(jī)會(huì)作為路由度量值的計(jì)算指標(biāo)之一,更多地增加傳輸路徑上的編碼機(jī)會(huì),提出了一系列的基于編碼機(jī)會(huì)感知的路由協(xié)議[11-19]。DCAR[14]提出了一種分布式的基于編碼機(jī)會(huì)感知的路由協(xié)議,在路徑度量值的計(jì)算中考慮了鏈路的編碼機(jī)會(huì),使得具有更多編碼機(jī)會(huì)的結(jié)點(diǎn)更容易被選為路由的中繼節(jié)點(diǎn),從而利用網(wǎng)絡(luò)編碼的優(yōu)勢(shì)提高網(wǎng)絡(luò)的整體吞吐量;CORE[15]通過(guò)將逐跳機(jī)會(huì)轉(zhuǎn)發(fā)和流間編碼相結(jié)合,達(dá)到提高吞吐量的目的;PNCAR[18]在計(jì)算鏈路的度量值時(shí)考慮了數(shù)據(jù)流之間的編碼關(guān)系,同時(shí)將實(shí)際網(wǎng)絡(luò)映射為一個(gè)虛擬網(wǎng)絡(luò)以解決了路由協(xié)議的等分性問(wèn)題,能夠在無(wú)線多跳的場(chǎng)景下提高網(wǎng)絡(luò)的吞吐量。

目前大部分的研究工作都是從路由層面出發(fā),通過(guò)改變路由機(jī)制使得中間節(jié)點(diǎn)獲得更多的編碼機(jī)會(huì),或者同時(shí)考慮了擁塞、負(fù)載均衡等問(wèn)題,從而提高整體吞吐量。但是很少有人研究MAC層機(jī)制對(duì)局部網(wǎng)絡(luò)編碼機(jī)會(huì)的影響。文獻(xiàn)[19]指出了現(xiàn)有的MAC層機(jī)制會(huì)影響編碼流和非編碼流之間的公平性,從而影響編碼機(jī)會(huì)的產(chǎn)生,提出了一種虛擬隊(duì)列的輪詢(xún)機(jī)制,使得編碼數(shù)據(jù)包能獲得更多發(fā)送機(jī)會(huì),從而能更充分發(fā)揮網(wǎng)絡(luò)編碼提高吞吐量的優(yōu)勢(shì)。但是文獻(xiàn)[19]僅僅考慮了MAC層機(jī)制對(duì)編碼流與非編碼流之間公平性的影響,并沒(méi)有注意到MAC層機(jī)制會(huì)影響不同編碼流之間的公平性。我們觀察到由于IEEE802.11MAC層的退避窗口調(diào)整機(jī)制,會(huì)導(dǎo)致可編碼流短期內(nèi)到達(dá)編碼節(jié)點(diǎn)的數(shù)據(jù)包數(shù)目是不平衡的,從而導(dǎo)致很多編碼機(jī)會(huì)的喪失。在本文的研究工作中,我們首先分析了IEEE802.11MAC層機(jī)制導(dǎo)致短時(shí)間內(nèi)可編碼流到達(dá)的不平衡性,并通過(guò)仿真實(shí)驗(yàn)驗(yàn)證了這種不平衡性的存在及對(duì)編碼機(jī)會(huì)的影響。然后,我們基于跨層設(shè)計(jì)的方法,提出了一種無(wú)線mesh網(wǎng)絡(luò)中編碼感知的跨層優(yōu)化機(jī)制CACLOM (coding-aware cross-layer optimization mechanism),能有效地增加編碼節(jié)點(diǎn)的編碼機(jī)會(huì),提高網(wǎng)絡(luò)的整體吞吐量。

1IEEE 802.11 MAC機(jī)制對(duì)編碼機(jī)會(huì)的影響

流間編碼示意圖如圖1所示,節(jié)點(diǎn)存在f1(n1->n3->n2)和f2(n4->n3->n5)兩條流,數(shù)據(jù)包p1和p2分別屬于流f1和f2,節(jié)點(diǎn)n3先后收到p1和p2,由于n5能夠偵聽(tīng)到n1的數(shù)據(jù)包p1,而n2能夠偵聽(tīng)到n4的數(shù)據(jù)包p2,n3就可以將數(shù)據(jù)包p1和p2編碼成p1⊕p2數(shù)據(jù)包進(jìn)行發(fā)送,而當(dāng)節(jié)點(diǎn)n2和n5收到編碼數(shù)據(jù)包p1⊕p2后就能夠解碼分別得到數(shù)據(jù)包p1和p2。

圖1　流間編碼示意圖

在IEEE802.11MAC機(jī)制中,網(wǎng)絡(luò)中的節(jié)點(diǎn)共同競(jìng)爭(zhēng)信道資源,當(dāng)一個(gè)節(jié)點(diǎn)競(jìng)爭(zhēng)到信道并成功發(fā)送數(shù)據(jù)幀之后,它的競(jìng)爭(zhēng)窗口被設(shè)置成最小值CWmin,而發(fā)送失敗的節(jié)點(diǎn)會(huì)將它的競(jìng)爭(zhēng)窗口增大一倍。這種機(jī)制會(huì)導(dǎo)致成功競(jìng)爭(zhēng)到信道的節(jié)點(diǎn)比發(fā)送失敗的節(jié)點(diǎn)在競(jìng)爭(zhēng)信道方面具備更大的優(yōu)勢(shì),進(jìn)而搶占更多的發(fā)送機(jī)會(huì),從而導(dǎo)致成功獲得信道的流在短期內(nèi)更易獲得發(fā)送機(jī)會(huì)。在圖1的場(chǎng)景中,節(jié)點(diǎn)n1和n4都要向節(jié)點(diǎn)n3發(fā)送數(shù)據(jù)包,若節(jié)點(diǎn)n1成功競(jìng)爭(zhēng)到信道則會(huì)調(diào)低競(jìng)爭(zhēng)窗口,若此時(shí)節(jié)點(diǎn)n4發(fā)送數(shù)據(jù)包失敗則會(huì)增加自己的競(jìng)爭(zhēng)窗口,那么節(jié)點(diǎn)n1在和節(jié)點(diǎn)n4競(jìng)爭(zhēng)信道時(shí)短期會(huì)更具備優(yōu)勢(shì)。這樣在節(jié)點(diǎn)n3中,短期內(nèi)屬于流f1的數(shù)據(jù)包會(huì)相對(duì)比較多,而屬于流f2的數(shù)據(jù)包則會(huì)相對(duì)少甚至沒(méi)有,這樣會(huì)影響編碼機(jī)會(huì)的產(chǎn)生。

為了觀察不同鏈路丟包率對(duì)吞吐量以及編碼機(jī)會(huì)的影響,利用圖1的“X”型拓?fù)渚W(wǎng)絡(luò)做了一個(gè)簡(jiǎn)單的實(shí)驗(yàn)。節(jié)點(diǎn)網(wǎng)絡(luò)層采用AODV路由協(xié)議,鏈路層采用MAC802.11b協(xié)議;節(jié)點(diǎn)的通信距離為150m,偵聽(tīng)距離為330m,無(wú)線鏈路帶寬為11Mbps。網(wǎng)絡(luò)中節(jié)點(diǎn)n1到n2之間有一條UDP流f1,n4到n5之間有一條UDP流f2,速率均為1Mbps,每個(gè)數(shù)據(jù)包大小固定為512字節(jié),按照網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和偵聽(tīng)關(guān)系,流f1和f2的數(shù)據(jù)包在節(jié)點(diǎn)n3處是可編碼的。除了節(jié)點(diǎn)n1到節(jié)點(diǎn)n3鏈路之外的其他鏈路丟包率均為0,觀察當(dāng)n1到n3節(jié)點(diǎn)間鏈路的丟包率分別為0、5%、10%、15%、20%,其他鏈路丟包率為0的情況下,吞吐量等一些性能指標(biāo)的變化。表1記錄了仿真實(shí)驗(yàn)運(yùn)行20s時(shí)間內(nèi)的測(cè)試結(jié)果。其中總發(fā)送次數(shù)是指節(jié)點(diǎn)n3發(fā)送數(shù)據(jù)包的次數(shù);緩沖區(qū)只存在單流的次數(shù)是指節(jié)點(diǎn)n3發(fā)送數(shù)據(jù)包時(shí)其隊(duì)列中只存在編碼流中的某一個(gè)單流出現(xiàn)的次數(shù);編碼次數(shù)是指節(jié)點(diǎn)n3發(fā)送編碼數(shù)據(jù)包的次數(shù);吞吐量是單位時(shí)間內(nèi)數(shù)據(jù)流f1和f2被成功接收的數(shù)據(jù)量之和。Q1和Q2分別表示f1和f2兩條流在編碼節(jié)點(diǎn)n3緩存隊(duì)列中數(shù)據(jù)包的個(gè)數(shù),將隊(duì)列中僅存在流f1的情況表示為Q1≠0|Q2=0,而將隊(duì)列中僅存在流f2的情況表示為Q1=0|Q2≠0,顯然這兩種情況下n3是沒(méi)有編碼機(jī)會(huì)的。不采用編碼機(jī)制是指n3直接轉(zhuǎn)發(fā);采用COPE機(jī)制即n3采用COPE機(jī)制對(duì)f1和f2的數(shù)據(jù)包進(jìn)行編碼發(fā)送。

表1　仿真實(shí)驗(yàn)結(jié)果

通過(guò)表1所示的仿真實(shí)驗(yàn)結(jié)果可以看出:

(1) 即使當(dāng)n1到n3鏈路丟包率為0時(shí),即所有競(jìng)爭(zhēng)鏈路丟包率一致的情況下,節(jié)點(diǎn)n3緩沖隊(duì)列中只存在單流的次數(shù)占了總發(fā)送次數(shù)的20%左右,即短期內(nèi)f1和f2流的數(shù)據(jù)包到達(dá)節(jié)點(diǎn)n3是不均衡的,這也驗(yàn)證了MAC層競(jìng)爭(zhēng)機(jī)制導(dǎo)致短期內(nèi)流到達(dá)的不均衡性,從而影響編碼機(jī)會(huì)的產(chǎn)生。

(2) 同時(shí)我們看到隨著n1到n3鏈路的丟包率逐漸增大,流f1的丟包增多,即節(jié)點(diǎn)n3處接收的數(shù)據(jù)包總數(shù)減少,且大部分屬于流f2。由于可編碼包的比例(即編碼次數(shù)和總發(fā)送次數(shù)之比)下降,從而使得吞吐量下降,編碼增益下降。

2CACLOM機(jī)制的層級(jí)結(jié)構(gòu)

通過(guò)第1節(jié)的分析和實(shí)驗(yàn)數(shù)據(jù),可以看到傳統(tǒng)的IEEE802.11標(biāo)準(zhǔn)MAC層機(jī)制不能很好地適應(yīng)網(wǎng)絡(luò)編碼的需要,其引起的可編碼流到達(dá)的不平衡性會(huì)減少編碼機(jī)會(huì),從而不能充分發(fā)揮網(wǎng)絡(luò)編碼提高吞吐量的優(yōu)勢(shì)。為此設(shè)計(jì)了CACLOM機(jī)制,該機(jī)制能夠根據(jù)編碼節(jié)點(diǎn)中各參與編碼流的隊(duì)列占用對(duì)比情況,動(dòng)態(tài)地調(diào)節(jié)各上游節(jié)點(diǎn)的MAC層競(jìng)爭(zhēng)信道能力,使緩沖隊(duì)列中各編碼流的數(shù)據(jù)包更加均衡,獲得更多的編碼機(jī)會(huì)。

CACLOM機(jī)制中,采用了與COPE一樣的數(shù)據(jù)包編碼方式。所有節(jié)點(diǎn)保持偵聽(tīng)狀態(tài),將偵聽(tīng)到的數(shù)據(jù)包緩存在偵聽(tīng)隊(duì)列中用于解碼,每個(gè)節(jié)點(diǎn)定期廣播自身偵聽(tīng)隊(duì)列中的數(shù)據(jù)包,同時(shí)依據(jù)鄰居節(jié)點(diǎn)偵聽(tīng)到的數(shù)據(jù)包來(lái)決定轉(zhuǎn)發(fā)數(shù)據(jù)包是否能夠編碼,以確保該節(jié)點(diǎn)的下一跳節(jié)點(diǎn)在接收到編碼數(shù)據(jù)包之后能解碼。節(jié)點(diǎn)接收數(shù)據(jù)包時(shí),若是編碼數(shù)據(jù)包,則從偵聽(tīng)隊(duì)列中找到解碼所需的數(shù)據(jù)包用于解碼還原原始數(shù)據(jù)包,然后遞交給上層協(xié)議進(jìn)行處理或放入轉(zhuǎn)發(fā)隊(duì)列等待調(diào)度。與其他基于網(wǎng)絡(luò)編碼的轉(zhuǎn)發(fā)機(jī)制不同的是,在CACLOM機(jī)制中,對(duì)數(shù)據(jù)流賦予了不同的優(yōu)先級(jí),在MAC層依據(jù)數(shù)據(jù)流的優(yōu)先級(jí)別進(jìn)行區(qū)分處理:MAC層依據(jù)該優(yōu)先級(jí)來(lái)確定發(fā)送數(shù)據(jù)幀的MAC層參數(shù),使得優(yōu)先級(jí)高的數(shù)據(jù)幀在競(jìng)爭(zhēng)信道時(shí)具備更強(qiáng)的優(yōu)勢(shì),以盡快獲得發(fā)送機(jī)會(huì)。CACLOM機(jī)制的層級(jí)結(jié)構(gòu)如圖2所示,對(duì)原有協(xié)議棧的改動(dòng)分為兩個(gè)部分,分別為:流優(yōu)先級(jí)的計(jì)算與調(diào)整和MAC層優(yōu)先級(jí)的處理。

圖2　CACLOM機(jī)制層級(jí)結(jié)構(gòu)圖

數(shù)據(jù)流優(yōu)先級(jí)的計(jì)算與調(diào)整完成的功能是依據(jù)發(fā)送緩沖隊(duì)列中各編碼流數(shù)據(jù)包的數(shù)量,計(jì)算得到相對(duì)富余的流和相對(duì)短缺的流。所謂的富余流是將編碼節(jié)點(diǎn)發(fā)送隊(duì)列中所有能進(jìn)行編碼的數(shù)據(jù)包編碼完之后,仍然有數(shù)據(jù)包需單獨(dú)發(fā)送的流,與富余流構(gòu)成編碼關(guān)系的流即為短缺流。

根據(jù)各編碼流在隊(duì)列中數(shù)據(jù)包個(gè)數(shù)差值來(lái)計(jì)算這些編碼流對(duì)應(yīng)的優(yōu)先級(jí),然后通知上一跳節(jié)點(diǎn),以降低富余流競(jìng)爭(zhēng)信道的能力同時(shí)增強(qiáng)短缺流競(jìng)爭(zhēng)信道的能力,從而使得到達(dá)編碼節(jié)點(diǎn)的編碼流的數(shù)據(jù)包數(shù)目趨向平衡,以獲得更多的編碼機(jī)會(huì)。關(guān)于流優(yōu)先級(jí)的計(jì)算與調(diào)整的詳細(xì)描述見(jiàn)第3節(jié)。

IP層將數(shù)據(jù)包遞交給編碼層時(shí),會(huì)將該數(shù)據(jù)包所屬流的優(yōu)先級(jí)值寫(xiě)入此IP數(shù)據(jù)包頭部的ToS字段。編碼層按照文獻(xiàn)[1]中的數(shù)據(jù)包編碼機(jī)制對(duì)可編碼數(shù)據(jù)包進(jìn)行編碼,當(dāng)參與編碼的原始數(shù)據(jù)包的優(yōu)先級(jí)別不同的時(shí)候,編碼包的優(yōu)先級(jí)別取其中高的優(yōu)先級(jí)別。

IP頭部ToS字段可以在路由層提供區(qū)分服務(wù),對(duì)優(yōu)先級(jí)別不同的數(shù)據(jù)包,路由器會(huì)區(qū)分對(duì)待。本文提出的機(jī)制是在路由層沒(méi)有啟用優(yōu)先級(jí)別的情況下使用,如果路由層已經(jīng)使用了ToS字段,則應(yīng)該以路由層的服務(wù)質(zhì)量?jī)?yōu)先,即保持路由層優(yōu)先級(jí)別高的數(shù)據(jù)占用較大的傳輸速率,在MAC層維持原來(lái)的競(jìng)爭(zhēng)機(jī)制。

MAC層優(yōu)先級(jí)的處理完成的功能是依據(jù)攜帶在IP頭部ToS字段中的優(yōu)先級(jí),將數(shù)據(jù)幀送入不同的硬件接口隊(duì)列。在CACLOM機(jī)制中,MAC層采用了IEEE802.11e協(xié)議,并對(duì)其參數(shù)設(shè)置進(jìn)行了一些修改,采用了8個(gè)優(yōu)先級(jí)的參數(shù)設(shè)置,具體每個(gè)優(yōu)先級(jí)的參數(shù)設(shè)置如表2所示,其中AIFS為從檢測(cè)到空閑到發(fā)送數(shù)據(jù)幀(進(jìn)入Contention Window)的間隔時(shí)間;CWmin為競(jìng)爭(zhēng)窗口最小值；CWmax為競(jìng)爭(zhēng)窗口最大值?？梢钥闯?0號(hào)優(yōu)先級(jí)為IEEE802.11b的MAC層采用的參數(shù)設(shè)置。優(yōu)先級(jí)越高,數(shù)據(jù)幀就越容易競(jìng)爭(zhēng)到信道。

表2　修改的IEEE802.11e MAC層參數(shù)設(shè)置

3數(shù)據(jù)流優(yōu)先級(jí)的計(jì)算與調(diào)整

數(shù)據(jù)流優(yōu)先級(jí)的計(jì)算與調(diào)整是CACLOM機(jī)制的核心。本節(jié)中,我們將描述數(shù)據(jù)流優(yōu)先級(jí)的計(jì)算與調(diào)整的具體方法。首先定義了節(jié)點(diǎn)的流表, 用于保存經(jīng)過(guò)節(jié)點(diǎn)的活動(dòng)流信息;然后引入編碼圖作為分析流之間編碼關(guān)系的工具,給出了緩沖隊(duì)列中富余流以及富余量的估算方法;在此基礎(chǔ)之上,設(shè)計(jì)了數(shù)據(jù)流的優(yōu)先級(jí)計(jì)算和調(diào)整方法。

3.1流表

CACLOM機(jī)制中,每個(gè)節(jié)點(diǎn)維護(hù)一張流表,用以記錄每條經(jīng)過(guò)本節(jié)點(diǎn)的“局部流”的信息。在每個(gè)節(jié)點(diǎn)的流表中,具有相同上一跳節(jié)點(diǎn)和下一跳節(jié)點(diǎn)的數(shù)據(jù)流聚合成同一局部數(shù)據(jù)流。在生成路由表的同時(shí),就根據(jù)每條流的上一跳節(jié)點(diǎn)、目標(biāo)節(jié)點(diǎn)地址、以及下一跳節(jié)點(diǎn)信息生成如表3所示的流表的每條記錄前4項(xiàng)信息。周期性輪詢(xún)整個(gè)轉(zhuǎn)發(fā)隊(duì)列,統(tǒng)計(jì)屬于各個(gè)流的數(shù)據(jù)包個(gè)數(shù),動(dòng)態(tài)更新queue size表項(xiàng)的值。顯然,對(duì)于中間節(jié)點(diǎn)進(jìn)行網(wǎng)絡(luò)編碼而言,同一局部流的數(shù)據(jù)包在可編碼性上是等價(jià)的。對(duì)應(yīng)于每一條局部流,流表記錄了<流序號(hào),目的節(jié)點(diǎn),上一跳節(jié)點(diǎn),下一跳節(jié)點(diǎn),數(shù)據(jù)包數(shù)目>五個(gè)表項(xiàng)。為了清楚說(shuō)明流表的含義,我們舉例說(shuō)明。假設(shè)在圖3(a)對(duì)應(yīng)的網(wǎng)絡(luò)中,存在7條流,分別為f1(v1->v2->v5->v8->v10)、f2(v1->v2->v5->v7->v9)、f3(v1->v2->v5->v12)、f4(v9->v6->v5->v3->v4)、f5(v6->v5->v8->v11)、f6(v8->v5->v2->v1)、f7(v1->v2->v5->v8->v11)。表3為圖中節(jié)點(diǎn)v5的流表,以第一條記錄對(duì)應(yīng)的局部流為例,這條局部流相對(duì)于節(jié)點(diǎn)v5的上一跳節(jié)點(diǎn)為v2,下一跳節(jié)點(diǎn)為v8,是由f1和f7兩條端到端數(shù)據(jù)流匯聚而成的,相應(yīng)的,數(shù)據(jù)包數(shù)目為f1和f7在節(jié)點(diǎn)v5緩沖隊(duì)列中的數(shù)據(jù)包個(gè)數(shù)總和。

圖3　網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖以及對(duì)應(yīng)的編碼圖

流編號(hào)目的節(jié)點(diǎn)上一跳節(jié)點(diǎn)下一跳節(jié)點(diǎn)占用隊(duì)列長(zhǎng)度1v10,v11v2v82+3=52v9v2v763v12v2v1224v4v6v385v11v6v876v1v8v210

3.2編碼圖(coding graph)

基于流表和局部流之間的編碼關(guān)系,每個(gè)編碼節(jié)點(diǎn)可以生成一張編碼圖。編碼圖為一無(wú)向圖,反應(yīng)了經(jīng)過(guò)本節(jié)點(diǎn)的局部流之間的編碼關(guān)系和局部流的流量大小。編碼圖的構(gòu)建方法為:局部流fi對(duì)應(yīng)編碼圖中的一個(gè)頂點(diǎn)i,頂點(diǎn)i對(duì)應(yīng)的權(quán)值Qi表示局部流fi在節(jié)點(diǎn)緩存隊(duì)列中的數(shù)據(jù)包的個(gè)數(shù),如果兩個(gè)局部流具有編碼關(guān)系,則相應(yīng)兩個(gè)頂點(diǎn)間增加一條邊,去除沒(méi)有任何邊的頂點(diǎn)(即不能與其他任何流進(jìn)行編碼的局部流)。

這里對(duì)局部流具有編碼關(guān)系的判定是單純依靠物理位置關(guān)系來(lái)確定的,即從物理位置關(guān)系而言,兩個(gè)流的下一跳節(jié)點(diǎn)都能得到另一流的上一跳節(jié)點(diǎn)的發(fā)送數(shù)據(jù)包,當(dāng)中間節(jié)點(diǎn)編碼后,兩個(gè)下一跳節(jié)點(diǎn)都能解碼。其定義是:假設(shè)存在兩個(gè)局部流f1和f2,若f1的下一跳節(jié)點(diǎn)即為f2的上一跳節(jié)點(diǎn),或者是其鄰居節(jié)點(diǎn),反之f2的下一跳節(jié)點(diǎn)即為f1的上一跳節(jié)點(diǎn),或者是其鄰居節(jié)點(diǎn),就稱(chēng)f1和f2具有編碼關(guān)系。例如圖3(a)中,經(jīng)過(guò)節(jié)點(diǎn)v5的兩個(gè)流f5(v6->v5->v8->v11)和f6(v8->v5->v2->v1),由于節(jié)點(diǎn)v2是節(jié)點(diǎn)v6的鄰居,同時(shí)f5的下一跳v8即為f6的上一跳節(jié)點(diǎn),因此我們稱(chēng)f5和f6具有編碼關(guān)系。

同樣,多個(gè)流之間具有編碼關(guān)系是指這多個(gè)流中的每個(gè)流的下一跳節(jié)點(diǎn)從物理位置關(guān)系來(lái)說(shuō)能監(jiān)聽(tīng)到或者直接獲得其他流上一跳節(jié)點(diǎn)發(fā)出的數(shù)據(jù)包,即中間節(jié)點(diǎn)將這多個(gè)流的數(shù)據(jù)包做異或編碼后,這多個(gè)流的下一跳節(jié)點(diǎn)都能解碼。圖3(b)為圖3(a)和表3對(duì)應(yīng)的編碼圖。

3.3富余流估算方法

依據(jù)上述編碼圖,給出了估算富余流以及富余量的方法。我們首先通過(guò)幾個(gè)常見(jiàn)的編碼圖結(jié)構(gòu)簡(jiǎn)單說(shuō)明一下如何利用編碼圖估算富余流及其富余量。

圖4為幾種常見(jiàn)的簡(jiǎn)單編碼圖結(jié)構(gòu)。如圖4(a)所示的編碼圖,表示局部流f1和f2具有編碼關(guān)系,此時(shí),流f1在該編碼節(jié)點(diǎn)的隊(duì)列中有10個(gè)數(shù)據(jù)包,而流f2在編碼節(jié)點(diǎn)的隊(duì)列中有4個(gè)數(shù)據(jù)包。顯然此時(shí)流f1為富余流,富余的數(shù)據(jù)包個(gè)數(shù)為6。因此,這種情況下的估算方法很簡(jiǎn)單,權(quán)值大的頂點(diǎn)代表的局部流為富余流,富余量為權(quán)值之差6。

圖4　幾種常見(jiàn)的編碼圖結(jié)構(gòu)

類(lèi)似地,圖4(b)中反映出流f1、f2和f3的數(shù)據(jù)包能一起編碼的情況。這種情況下,3條流有一部分?jǐn)?shù)據(jù)包可以3個(gè)編碼在一起發(fā)送,在這個(gè)例子中,可以形成4個(gè)3編碼的編碼包,此后,流f1剩余6個(gè)數(shù)據(jù)包,流f2剩余2個(gè)數(shù)據(jù)包,這時(shí),流f1和流f2的數(shù)據(jù)包可以進(jìn)行一起編碼,最后是流f1為富余流,富余的數(shù)據(jù)包個(gè)數(shù)為4。這種情況的估算方法是權(quán)值最大的頂點(diǎn)代表的流為富余流,富余量為最大權(quán)值減去次大的權(quán)值。以此類(lèi)推,同樣的估算方法可以適用于包含多個(gè)頂點(diǎn)的全連通編碼圖,即多個(gè)數(shù)據(jù)流可以編碼在一起的情況。

圖4(c)反映的情況稍微復(fù)雜一些,流f1不僅能和流f2和f3一起編碼(連通部分1),而且能和流f4進(jìn)行編碼(連通部分2)。依據(jù)采用的COPE編碼機(jī)制,總是取隊(duì)首數(shù)據(jù)包與緊接其后的可編碼數(shù)據(jù)包編碼,并逐個(gè)判定是否可以多個(gè)編碼在一起。因此f1的數(shù)據(jù)包是與f2和f3的編碼在一起,還是與f4的數(shù)據(jù)包編碼在一起,取決于數(shù)據(jù)包在緩沖隊(duì)列中的位置。因此為了估算的合理性,首先分別計(jì)算兩個(gè)全連通部分的可編碼流量,連通部分1的可編碼流量為6(即為該連通部分的次大頂點(diǎn)權(quán)值Q3=6),連通部分2的可編碼流量也是6(Q4=6),我們將f1的流量按比例與可編碼流的權(quán)值相消,即相當(dāng)于將頂點(diǎn)1虛擬成兩個(gè)不相連的頂點(diǎn),將頂點(diǎn)1的權(quán)值按比例分配給這兩個(gè)虛擬節(jié)點(diǎn)。在這個(gè)例子中,我們將權(quán)值均分。這時(shí),圖4(c)就變成了圖5所示的分解圖,然后再按照?qǐng)D4(a)和圖4(b)的估算方法,可以得到富余流為f4和f3,富余量分別都是1。

圖4(d)與圖4(c)不同的是,除了權(quán)值最大的頂點(diǎn)1在多個(gè)連通部分外,該點(diǎn)的鄰居頂點(diǎn)2也在多個(gè)連通部分。

為了簡(jiǎn)化估算,先將位于多個(gè)連通部分的鄰居點(diǎn)2分解成多個(gè)虛擬點(diǎn),分解的方法同樣按比例劃分,即分別計(jì)算所在的幾個(gè)連通部分的不包含自身的次大頂點(diǎn)權(quán)值,按比例分解分配權(quán)值。接著按圖4(c)的方法估算富裕流,得到如圖6所示的分解圖。觀察此圖6(b)可知,頂點(diǎn)4和頂點(diǎn)3對(duì)應(yīng)的流為富余流,它們的富余量均為1。

圖5　圖4(c)對(duì)應(yīng)的分解圖

圖6　圖4(d)對(duì)應(yīng)的分解圖

CACLOM機(jī)制中,首先依據(jù)編碼節(jié)點(diǎn)當(dāng)時(shí)的緩存隊(duì)列中數(shù)據(jù)流的編碼關(guān)系生成編碼圖CG(V,E,W)。當(dāng)一個(gè)節(jié)點(diǎn)的局部流較多時(shí),可能會(huì)出現(xiàn)比較復(fù)雜的編碼圖。在這種更為一般的編碼圖中,富裕流估算的基本方法和步驟如下：

步驟 1在編碼圖中選擇權(quán)值最大的頂點(diǎn),由該頂點(diǎn)與其直接鄰居點(diǎn)構(gòu)成局部的編碼圖,在局部編碼圖中對(duì)權(quán)值相抵消;

步驟 2在權(quán)值抵消后,對(duì)編碼圖進(jìn)行裁剪,具體的方法是去除權(quán)值為0的頂點(diǎn)及該頂點(diǎn)的所有的邊,合并相應(yīng)的虛擬節(jié)點(diǎn),其權(quán)值為相應(yīng)虛擬節(jié)點(diǎn)剩余權(quán)值之和;

步驟 3在裁剪后的殘圖中,遞歸執(zhí)行步驟1和步驟2,直至殘圖中不存在邊;

步驟 4輸出殘圖中權(quán)值不為0的頂點(diǎn)和相應(yīng)剩余權(quán)值,輸出原圖中這些點(diǎn)的鄰居節(jié)點(diǎn)。這些權(quán)值不為0的頂點(diǎn)代表的流就是富余流,富余量即為該點(diǎn)相消后的剩余權(quán)值,其鄰居點(diǎn)代表的流為短缺流。

步驟1中局部編碼圖權(quán)值相抵消的具體方法如下:

(1) 若某個(gè)點(diǎn)的局部編碼圖包含多個(gè)全連通部分。首先,若該點(diǎn)的某個(gè)鄰居點(diǎn)屬于多個(gè)全連通部分,則為該點(diǎn)生成多個(gè)虛擬節(jié)點(diǎn),并將該鄰居點(diǎn)權(quán)值分配給虛擬節(jié)點(diǎn),用虛擬節(jié)點(diǎn)將多個(gè)全連通部分在該鄰居點(diǎn)分離。若僅有該節(jié)點(diǎn)被包含在多個(gè)全聯(lián)通部分,為該點(diǎn)生成相應(yīng)的虛擬點(diǎn),權(quán)值分配給虛擬節(jié)點(diǎn),將局部編碼圖在該點(diǎn)出分拆成多個(gè)獨(dú)立的全連通部分。

(2) 對(duì)于大于等于3個(gè)頂點(diǎn)的連通部分,即如圖4(b)的情況,相抵消的具體方法是將權(quán)值最大的頂點(diǎn)的權(quán)值改為最大權(quán)值減去次大權(quán)值,其他點(diǎn)權(quán)值都改為0。

(3) 對(duì)于只有兩個(gè)點(diǎn)的全連通部分,將原來(lái)權(quán)值大的頂點(diǎn)的權(quán)值改為權(quán)值之差,原來(lái)權(quán)值小的點(diǎn)賦值為0。

關(guān)于在編碼圖中查找富余流的算法描述如圖7～圖9所示。

圖7　Finding _Richflow(CG)查找富余流方法

圖8　Weight_offset(G)權(quán)值抵消算法

3.4流優(yōu)先級(jí)的計(jì)算與調(diào)整

CACLOM機(jī)制中,各流的優(yōu)先級(jí)初始時(shí)刻均設(shè)置為0。當(dāng)編碼節(jié)點(diǎn)根據(jù)估算方法得到了剩余權(quán)值不為0的頂點(diǎn)和其權(quán)值后,將通知上一跳節(jié)點(diǎn)降低這些頂點(diǎn)對(duì)應(yīng)的流的發(fā)送優(yōu)先級(jí),同時(shí)提升與其鄰居節(jié)點(diǎn)對(duì)應(yīng)的流的優(yōu)先級(jí)別。為了盡量減少這種調(diào)節(jié)機(jī)制對(duì)整體信道競(jìng)爭(zhēng)激烈程度的影響,我們?cè)趨?shù)調(diào)節(jié)上盡量讓富余流與其對(duì)應(yīng)的短缺流的優(yōu)先級(jí)調(diào)整量是平衡的,使得所有流競(jìng)爭(zhēng)信道的能力維持在一定水平,保證CACLOM機(jī)制不會(huì)帶來(lái)更多的MAC層沖突。

具體的優(yōu)先級(jí)計(jì)算方法如下:

假設(shè)估算得到的剩余編碼圖中頂點(diǎn)k對(duì)應(yīng)剩余權(quán)值為Qk(Qk>0),計(jì)算頂點(diǎn)k對(duì)應(yīng)的局部編碼流fk的優(yōu)先級(jí)調(diào)整量公式為

(1)

式中,N為編碼節(jié)點(diǎn)緩沖隊(duì)列的最大長(zhǎng)度;Δ為CACLOM機(jī)制中設(shè)定的優(yōu)先級(jí)的個(gè)數(shù)，如表2所示,Δ=8。

同時(shí)計(jì)算在原始編碼圖中頂點(diǎn)k的鄰居i所對(duì)應(yīng)流fi的優(yōu)先級(jí)調(diào)整量。由于可能存在多個(gè)鄰居點(diǎn),意味著多個(gè)流可以與流fk編碼,這里的策略是同時(shí)提高這些流的優(yōu)先級(jí)別,只是提高量作了平均。因此流fi的優(yōu)先級(jí)調(diào)整量計(jì)算公式為

(2)

式中,m為頂點(diǎn)k的鄰居節(jié)點(diǎn)的數(shù)目。

圖9　Decompose(G)分解子圖算法

當(dāng)編碼節(jié)點(diǎn)有數(shù)據(jù)包要發(fā)送時(shí),將計(jì)算得到的流的優(yōu)先級(jí)調(diào)整量信息攜帶在數(shù)據(jù)包中;鄰居節(jié)點(diǎn)偵聽(tīng)到此數(shù)據(jù)包時(shí),將對(duì)應(yīng)本節(jié)點(diǎn)的流調(diào)整信息取出,并將相應(yīng)的流優(yōu)先級(jí)調(diào)整為Δ/2+η。

圖10　編碼圖中查找富余流算法示例圖

在CACLOM機(jī)制中,優(yōu)先級(jí)信息的傳輸是采用攜帶的方式,在編碼節(jié)點(diǎn)定期生成編碼圖計(jì)算出優(yōu)先級(jí)調(diào)整量后,用一個(gè)發(fā)送數(shù)據(jù)包攜帶相應(yīng)的調(diào)整信息。數(shù)據(jù)包格式如圖11所示。CACLOM數(shù)據(jù)包格式與COPE數(shù)據(jù)包格式基本相同,只是在COPE數(shù)據(jù)包格式的基礎(chǔ)上增加了“優(yōu)先級(jí)調(diào)整信息”字段,其中PRI_REPORT_NUM為攜帶的優(yōu)先級(jí)調(diào)整記錄的條數(shù),每條記錄是針對(duì)某個(gè)上游節(jié)點(diǎn)的一條流的調(diào)整信息,對(duì)應(yīng)一個(gè)的三元組,USNODE_IP為上游節(jié)點(diǎn)的IP地址,FLOW_DEST_IP為需要調(diào)整流的目的地址,PRI_ADJUST為優(yōu)先級(jí)調(diào)整量。一條記錄占用9個(gè)字節(jié),用于表示兩個(gè)IP地址和一個(gè)調(diào)整量。

仍然是以圖3和表3所示的網(wǎng)絡(luò)為例,在第3.3節(jié)最后得到Q1=2.5、Q5=3.5,其他頂點(diǎn)的權(quán)值均為0,節(jié)點(diǎn)隊(duì)列的最大長(zhǎng)度N為10,設(shè)定的優(yōu)先級(jí)的個(gè)數(shù)Δ=8。針對(duì)Q1=2.5,首先根據(jù)式(1)計(jì)算頂點(diǎn)1對(duì)應(yīng)的流的優(yōu)先級(jí)調(diào)整值h1=-|2.5×8/(10×2)|=-1,根據(jù)式(2)計(jì)算頂點(diǎn)1的鄰居頂點(diǎn)6對(duì)應(yīng)的流的優(yōu)先級(jí)調(diào)整值h6=|2.5×8/(10×2)|=1。類(lèi)似的計(jì)算頂點(diǎn)5及其鄰居頂點(diǎn)6對(duì)應(yīng)的流的優(yōu)先級(jí)調(diào)整值分別為h5=-|3.5×8/(10×2)|=-1和h6=|3.5×8/(10×2)|=1,合并頂點(diǎn)6對(duì)應(yīng)的流的優(yōu)先級(jí)調(diào)整值h6=2。所以流f1和f5的優(yōu)先級(jí)將被調(diào)整為4-1=3,而流f6的優(yōu)先級(jí)將被調(diào)整為4+2=6。

圖11　CACLOM數(shù)據(jù)包格式圖

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

在本節(jié)中,將在簡(jiǎn)單的“X”型簡(jiǎn)單拓?fù)浣Y(jié)構(gòu)網(wǎng)絡(luò)和隨機(jī)部署節(jié)點(diǎn)的復(fù)雜拓?fù)浣Y(jié)構(gòu)網(wǎng)絡(luò)中,測(cè)試CACLOM機(jī)制的性能表現(xiàn)。在下面的仿真實(shí)驗(yàn)中,如無(wú)特別說(shuō)明,各參數(shù)設(shè)置如表4所示。

表4　仿真實(shí)驗(yàn)參數(shù)設(shè)置

4.1簡(jiǎn)單網(wǎng)絡(luò)拓?fù)湎路抡鎸?shí)驗(yàn)

為了驗(yàn)證CACLOM機(jī)制的有效性,模擬仿真了CACLOM機(jī)制,將其性能與COPE機(jī)制作了比較。我們首先在如圖1所示的簡(jiǎn)單網(wǎng)絡(luò)拓?fù)湎逻M(jìn)行仿真。網(wǎng)絡(luò)中存在兩條交匯于節(jié)點(diǎn)n3的UDP流,分別是n1到n2的流f1,n4到n5的流f2,速率均為1 Mbps。

在仿真中兩者的網(wǎng)絡(luò)層均采用按需路由機(jī)制AODV,不同的是COPE機(jī)制中MAC層采用IEEE802.11b,而CACLOM機(jī)制采用了結(jié)合流量估算和優(yōu)先級(jí)調(diào)整的改進(jìn)IEEE802.11e機(jī)制。測(cè)試中改變n1到n3節(jié)點(diǎn)間鏈路的丟包率,分別為0、5%、10%、15%、20%,將COPE協(xié)議與CACLOM機(jī)制相比較,觀察在此過(guò)程中網(wǎng)絡(luò)總吞吐量(所有流吞吐量的總和)、公平系數(shù)(兩條參與編碼流的吞吐量比值)、編碼節(jié)點(diǎn)參與編碼流的隊(duì)列占用對(duì)比情況，具體如圖12所示。

從圖12(a)可以看出,CACLOM機(jī)制較單純的COPE機(jī)制在吞吐能力上面提升了大概20%～80%,鏈路質(zhì)量差異越大,吞吐量提升越明顯。這是因?yàn)殡S著n1->n3鏈路丟包率的增加,使得編碼節(jié)點(diǎn)n3成功接收到f1的數(shù)據(jù)包數(shù)目與f2的數(shù)據(jù)包數(shù)目的差異越來(lái)越大,造成編碼機(jī)會(huì)的減少。而CACLOM機(jī)制在這種情況下,會(huì)適當(dāng)提高f1的競(jìng)爭(zhēng)信道能力,使得n3節(jié)點(diǎn)上流f1和f2的數(shù)據(jù)包數(shù)目趨向平衡,從而提高了網(wǎng)絡(luò)編碼的機(jī)會(huì),從而使得吞吐量是能夠得到提高的。

圖12(b)給出了本次仿真實(shí)驗(yàn)中兩種機(jī)制公平性的比較,其中公平系數(shù)的計(jì)算方法是兩條流所獲得的平均帶寬的比值。

圖12(c)給出了兩種機(jī)制中流f1和f2的端到端延時(shí)的對(duì)比,其中流f2為富余流,流f1為與其對(duì)應(yīng)的短缺流?？梢钥闯?在部署了CACLOM機(jī)制之后,流f2的端到端延時(shí)基本沒(méi)有發(fā)生變化,而流f1的延時(shí)則減小了很多。之所以能夠不影響流f2的延時(shí),是因?yàn)樵诰幋a轉(zhuǎn)發(fā)的情況下,流f2數(shù)據(jù)包會(huì)與流f1數(shù)據(jù)包編碼發(fā)送,從而不會(huì)對(duì)流f2數(shù)據(jù)包的轉(zhuǎn)發(fā)造成影響。

表5給出的仿真實(shí)驗(yàn)中的編碼次數(shù)和隊(duì)列中數(shù)據(jù)包數(shù)目統(tǒng)計(jì)結(jié)果也驗(yàn)證了CACLOM機(jī)制可以調(diào)節(jié)參與編碼的數(shù)據(jù)流到達(dá)速率,使得編碼節(jié)點(diǎn)n3上的編碼機(jī)會(huì)增多,從而提高了網(wǎng)絡(luò)的吞吐量。

如表5所示,我們可以看到CACLOM在Q1=0|Q2≠0和Q1≠0|Q2=0出現(xiàn)的次數(shù)上都有非常明顯的減少且更加趨近平衡,說(shuō)明f1和f2兩條流在隊(duì)列占用率上面更加平衡,不能編碼的情況減少;從編碼次數(shù)的指標(biāo)上來(lái)看,CACLOM機(jī)制增加了編碼節(jié)點(diǎn)的編碼次數(shù),能更好地發(fā)揮網(wǎng)絡(luò)編碼的優(yōu)勢(shì)。

為了測(cè)試節(jié)點(diǎn)緩存大小N對(duì)網(wǎng)絡(luò)性能的影響,在上述仿真實(shí)驗(yàn)場(chǎng)景中,固定n1到n3節(jié)點(diǎn)間鏈路的丟包率為10%,僅改變節(jié)點(diǎn)緩存大小N的值,觀察其對(duì)網(wǎng)絡(luò)編碼次數(shù)以及總吞吐量的影響，具體如圖13所示。

圖12　總吞吐量、公平指數(shù)和端到端延時(shí)對(duì)比圖

圖13　不同節(jié)點(diǎn)緩存大小對(duì)性能的影響

通過(guò)圖13可以看出,當(dāng)節(jié)點(diǎn)緩存大小變化時(shí),相對(duì)于COPE機(jī)制,CACLOM機(jī)制均能獲得更多的編碼機(jī)會(huì),以及很好的吞吐量增益。在接下來(lái)的仿真實(shí)驗(yàn)中,節(jié)點(diǎn)緩存大小取NS2中的默認(rèn)值50 packets。

表5　編碼次數(shù)以及隊(duì)列情況

在CACLOM機(jī)制中,對(duì)參與編碼的數(shù)據(jù)流中速率較小的流賦予了較高的優(yōu)先級(jí),而速率較大的流賦予了較低的優(yōu)先級(jí)。為了觀察CACLOM機(jī)制對(duì)于速率不同的編碼流的影響, 我們?cè)谏鲜鰧?shí)驗(yàn)中僅改變編碼流的發(fā)送速率,同時(shí)固定所有鏈路的丟包率為0,觀察在各種情況下兩條流所獲得的帶寬對(duì)比情況。

仿真實(shí)驗(yàn)結(jié)果如表6所示,當(dāng)網(wǎng)絡(luò)比較空閑的時(shí)候(表6中的前兩條記錄對(duì)應(yīng)的情況),CACLOM機(jī)制下流f1和f2所獲得的帶寬與其發(fā)送速率成比例。這是因?yàn)楸M管提高了速率較低流的信道競(jìng)爭(zhēng)能力,但是由于網(wǎng)絡(luò)中有足夠的帶寬資源,使得被賦予較低優(yōu)先級(jí)的數(shù)據(jù)流仍然能獲得足夠的帶寬。同時(shí),當(dāng)網(wǎng)絡(luò)較擁塞的時(shí)候(表6中的后兩條記錄對(duì)應(yīng)的情況),流f1和f2所獲得的帶寬都高于COPE機(jī)制,但流f2獲得了更好地帶寬/速率比,這說(shuō)明了CACLOM機(jī)制能提高流速較低的流搶占信道的能力,使得網(wǎng)絡(luò)中產(chǎn)生了更多的編碼機(jī)會(huì),從而能夠更好地發(fā)揮網(wǎng)絡(luò)編碼提高網(wǎng)絡(luò)吞吐量的優(yōu)勢(shì)。

4.2復(fù)雜網(wǎng)絡(luò)拓?fù)湎路抡鎸?shí)驗(yàn)

為了測(cè)試更為一般的網(wǎng)絡(luò)拓?fù)洹⒍嗔鞑⒋媲闆r下協(xié)議的特征,我們仿真了更為一般的網(wǎng)絡(luò)拓?fù)鋱?chǎng)景,在1 000×1 000的區(qū)域內(nèi)隨機(jī)部署25個(gè)節(jié)點(diǎn),然后每隔30 s加入一條UDP流,部署多條UDP流,流數(shù)為3～12條不等,速度為100 kbps,每條鏈路丟包率在0%～10%之間隨機(jī)取值。

表6　編碼流速率不同情況下帶寬占用情況

由于一些相關(guān)研究已經(jīng)在COPE機(jī)制上改進(jìn)并提出了編碼感知的路由協(xié)議,為了驗(yàn)證CACLOM機(jī)制與這些已經(jīng)考慮了編碼機(jī)會(huì)的路由機(jī)制結(jié)合之后的有效性,在測(cè)試中選擇了文獻(xiàn)[15]提出的編碼感知路由協(xié)議PNCAR,并且在其上結(jié)合了MAC層優(yōu)先級(jí)調(diào)整機(jī)制,對(duì)結(jié)合前后的性能進(jìn)行了比較。(PNCAR是一個(gè)編碼感知的路由協(xié)議,它在選擇路由時(shí)考慮了編碼機(jī)會(huì)的因素,同時(shí)解決了路由選擇的等分性(isotonic)問(wèn)題,性能上比單純的COPE機(jī)制要好。)用PNCAR+CACLOM表示結(jié)合了MAC層優(yōu)先級(jí)調(diào)整之后的機(jī)制。

仿真實(shí)驗(yàn)在10種不同的隨機(jī)網(wǎng)絡(luò)場(chǎng)景下進(jìn)行,實(shí)驗(yàn)結(jié)果取10次實(shí)驗(yàn)的均值,同時(shí)我們給出了當(dāng)流的數(shù)目為9時(shí),10種隨機(jī)網(wǎng)絡(luò)場(chǎng)景下各“路由協(xié)議+編碼機(jī)制”組合在總吞吐量和編碼次數(shù)上的對(duì)比情況。測(cè)試的性能指標(biāo)包括:

(1) 網(wǎng)絡(luò)總吞吐量(所有流吞吐量的綜合);

(2) 總編碼次數(shù)(所有編碼節(jié)點(diǎn)編碼次數(shù)之和);

圖14為不同網(wǎng)絡(luò)負(fù)載情況下,網(wǎng)絡(luò)總吞吐量和編碼次數(shù)均值的變化情況,而圖15為當(dāng)網(wǎng)絡(luò)中存在9個(gè)流時(shí),各個(gè)不同網(wǎng)絡(luò)場(chǎng)景下的吞吐量和編碼次數(shù)。

圖14　平均吞吐量和編碼次數(shù)的對(duì)比圖

圖15　流數(shù)目為9時(shí)不同網(wǎng)絡(luò)場(chǎng)景的吞吐量和編碼次數(shù)的對(duì)比圖

觀察圖14和圖15可得:

(1) 從圖14可以看出,采用同樣的路由協(xié)議,引入CACLOM機(jī)制之后(即COPE與CACLOM相比較,PNCAR與PNCAR+CACLOM相比較),在流的數(shù)目超過(guò)6以后,吞吐量和編碼包數(shù)目都有很明顯的提升。說(shuō)明CACLOM機(jī)制能夠有效地增加網(wǎng)絡(luò)中的編碼機(jī)會(huì),更好地發(fā)揮網(wǎng)絡(luò)編碼提高吞吐量的優(yōu)勢(shì)。圖15中給出了不同場(chǎng)景下的吞吐量和編碼次數(shù)的比較,可以看出在測(cè)試的所有場(chǎng)景中,引入MAC層優(yōu)先級(jí)別調(diào)整機(jī)制CACLOM后,網(wǎng)絡(luò)中的編碼次數(shù)和整體吞吐量都得到了有效的提高。

(2) PNCAR與CACLOM的結(jié)合較單純采用一種機(jī)制進(jìn)一步提高了吞吐量。這是因?yàn)镻NCAR在選擇路由時(shí)考慮鏈路的編碼機(jī)會(huì),能夠?qū)⒏嗟木W(wǎng)絡(luò)流量聚合到具有編碼機(jī)會(huì)的鏈路上來(lái),使得網(wǎng)絡(luò)擁有更多的編碼節(jié)點(diǎn)。同時(shí),CACLOM機(jī)制能夠增加編碼節(jié)點(diǎn)上的編碼機(jī)會(huì),也就是說(shuō),CACLOM機(jī)制能夠進(jìn)一步放大基于編碼感知的路由協(xié)議相對(duì)于最短路徑路由協(xié)議的優(yōu)勢(shì)。

圖16為4種機(jī)制的公平性比較。由于PNCAR有流量匯聚的特點(diǎn),流量匯聚之后會(huì)使得流之間競(jìng)爭(zhēng)帶寬資源的情況加劇,故采用了PNCAR的機(jī)制的公平性比采用COPE機(jī)制公平性要稍差一些。而CACLOM機(jī)制和PNCAR+CACLOM則有比較好的公平性表現(xiàn)。這是因?yàn)檫M(jìn)行網(wǎng)絡(luò)編碼的節(jié)點(diǎn)在發(fā)送一個(gè)數(shù)據(jù)包時(shí),如果隊(duì)列中有符合編碼條件的數(shù)據(jù)包,節(jié)點(diǎn)會(huì)將多個(gè)數(shù)據(jù)包編碼進(jìn)行發(fā)送,這種行為會(huì)改善網(wǎng)絡(luò)流之間的公平性,并且編碼次數(shù)越多,這種改善公平性的效果會(huì)越明顯。這也從側(cè)面說(shuō)明了本文提出的CACLOM機(jī)制能夠有效地增加編碼機(jī)會(huì),從而提升吞吐量。

圖16　流的數(shù)目 vs. Jain公平指數(shù)

5結(jié)論

本文首先分析了IEEE802.11標(biāo)準(zhǔn)的MAC機(jī)制帶來(lái)的短期競(jìng)爭(zhēng)信道不公平的特點(diǎn),并指出這會(huì)減少編碼機(jī)會(huì)的產(chǎn)生,進(jìn)而結(jié)合跨層優(yōu)化的思想,提出了一種具有編碼機(jī)會(huì)感知的跨層協(xié)作機(jī)制CACLOM。這種機(jī)制通過(guò)檢查參與編碼流在編碼節(jié)點(diǎn)隊(duì)列中的占用情況以通知相應(yīng)上游結(jié)點(diǎn)調(diào)整MAC參數(shù),從而調(diào)節(jié)參與編碼流的速率,使得編碼節(jié)點(diǎn)上不同編碼流的數(shù)據(jù)包數(shù)目更加平衡,最終達(dá)到增加編碼次數(shù),提高網(wǎng)絡(luò)整體吞吐量的目的。通過(guò)NS2上的仿真實(shí)驗(yàn)表明,CACLOM機(jī)制能夠平衡編碼流競(jìng)爭(zhēng)信道的能力,有效地增加了編碼機(jī)會(huì),提高了網(wǎng)絡(luò)的整體吞吐量。

參考文獻(xiàn)：

[1] Katti S, Rahul H, Hu W, et al. XORs in the air: practical wireless network coding[J].IEEE/ACMTrans.onNetworking, 2008, 16(3): 497-510.

[2] Wang C C, Shroff N, Khreishah A. Cross-layer optimizations for intersession network coding on practical 2-hop relay networks[C]∥Proc.oftheIEEEAsilomarConferenceonSignals,SystemsandComputers, 2009: 771-775.

[3] Wang C C. On the capacity of wireless 1-hop intersession network coding—a broadcast packet erasure channel approach[J].IEEETrans.onInformationTheory, 2012, 58(2): 957-988.

[4] Ramakrishnan A, Das A, Maleki H, et al. Network coding for three unicast sessions: interference alignment approaches[C]∥Proc.ofthe48thIEEEAnnualAllertonConferenceonCommunication,Control,andComputing, 2010: 1054-1061.

[5] Eryilmaz A, Lun D S. Control for inter-session network coding[C]∥Proc.ofthe3rdIEEEWorkshoponNetworkCoding,Theory&Applications, 2007: 1-9.

[6] Traskov D, Ratnakar N, Lun D S, et al. Network coding for multiple unicasts: an approach based on linear optimization[C]∥Proc.oftheIEEEInternationalSymposiumonInformationTheory, 2006: 1758-1762.

[7] Seferoglu H, Markopoulou A, Ramakrishnan K K. I2NC: intra-and inter-session network coding for unicast flows in wireless networks[C]∥Proc.ofthe30thIEEEInternationalConferenceonComputerCommunications, 2011: 1035-1043.

[8] Paschos G S, Fragiadakis C, Georgiadis L. Wireless network coding with partial overhearing information[C]∥Proc.ofthe32ndIEEEInternationalConferenceonComputerCommunications, 2013: 2337-2345.

[9] Keshavarz-Haddad A, Riedi R H. Bounds on the benefit of network coding for wireless multicast and unicast[J].IEEETrans.onComputing, 2014, 13(1): 102-115.

[10] Carrillo E, Ramos V. On the impact of network coding delay for IEEE 802.11 s infrastructure wireless mesh networks[C]∥Proc.ofthe28thIEEEInternationalConferenceonAdvancedInformationNetworkingandApplications, 2014: 305-312.

[11] Wei X, Zhao L, Xi J, et al. Network coding-aware routing protocol for lossy wireless networks[C]∥Proc.ofthe5thIEEEInternationalConferenceonWirelessCommunicationsNetworkingandMobileComputing, 2009: 1-4.

[12] Fan K, Li L, Long D. Study of on-demand cope-aware routing protocol in wireless mesh networks[J].JournalonCommunications, 2009, 30(1):128-34.

[13] Wu Y, Das S M, Chandra R. Routing with a Markovian metric to promote local mixing[C]∥Proc.ofthe26thIEEEInternationalConferenceonComputerCommunications, 2007: 2381-2385.

[14] Le J, Lui J C S, Chiu D M. DCAR: distributed coding-aware routing in wireless networks[J].IEEETrans.onMobileComputing, 2010, 9(4): 596-608.

[15] Yan Y, Zhang B, Zheng J, et al. CORE: a coding-aware opportunistic routing mechanism for wireless mesh networks[J].IEEEWirelessCommunications, 2010, 17(3): 96-103.

[16] Zhang J, Zhang Q. Cooperative network coding-aware routing for multi-rate wireless networks[C]∥Proc.ofthe28thIEEEInternationalConferenceonComputerCommunications, 2009: 181-189.

[17] Jhang M F, Lin S W, Liao W. C2AR: coding and capacity aware routing for wireless ad hoc networks[C]∥Proc.oftheIEEEInternationalConferenceonCommunications, 2010: 1-5.

[18] Peng Y, Yang Y, Lu X, et al. Coding-aware routing for unicast sessions in multi-hop wireless networks[C]∥Proc.oftheIEEEGlobalTelecommunicationsConference, 2010: 1-5.

[19] Zhao F, Médard M. On analyzing and improving COPE performance[C]∥Proc.ofInformationTheoryandApplicationsWorkshop, 2010: 1-6.

[20] Jain R, Chiu D M, Hawe W R.Aquantitativemeasureoffairnessanddiscriminationforresourceallocationinsharedcomputersystem[M]. Eastern Research Laboratory: Digital Equipment Corporation, 1984: 5-10.

楊湘(1980-),男,博士研究生,主要研究方向?yàn)榫W(wǎng)絡(luò)協(xié)議性能優(yōu)化、網(wǎng)絡(luò)編碼。

E-mail:yangxiang1027@163.com

王偉平(1969-),女,教授,博士研究生導(dǎo)師,博士,主要研究方向?yàn)榫W(wǎng)絡(luò)優(yōu)化、網(wǎng)絡(luò)編碼、網(wǎng)絡(luò)安全、匿名通信。

E-mail:wpwang@mail.csu.edu.cn

王建新(1969-),男,教授,博士研究生導(dǎo)師,博士,主要研究方向?yàn)閰?shù)計(jì)算理論、網(wǎng)絡(luò)優(yōu)化理論。

E-mail:jxwang@mail.csu.edu.cn

A coding-aware cross-layer optimization mechanism for wireless mesh network

YANG Xiang1,2, WANG Wei-ping1, WANG Jian-xin1

(1.SchoolofInformationScienceandEngineering,CentralSouthUniversity,Changsha410083,China;2.SchoolofComputerScienceandTechnology,WuhanUniversityofScienceandTechnology,Wuhan430081,China)

Abstract:Due to the inherent broadcast and overhearing capabilities of wireless network, the network coding technique is very suitable for the wireless mesh network. Through the theoretical analysis and simulation results, it is observed that the MAC mechanism of the IEEE802.11 standard may make the node more competitive after accessing the channel successfully, which unbalances the amount of packets of different coding flows in the buffer of the coding node in a short period, and finally, some coding opportunities are lost. A cross-layer optimization mechanism is proposed. In the mechanism, the priorities of coding flows are calculated by using the buffer occupancy information and are sent to the upstream node, and then the corresponding upstream node adjusts its MAC parameters, which yields more coding opportunities. Simulation results show that the proposed mechanism can adjust the rate of flows whose packets can be encoded together adaptively, and improve the total throughput of network.

Keywords:wireless mesh network; MAC protocol; network coding; cross-layer optimization

收稿日期：2015-02-05；修回日期：2015-05-09；網(wǎng)絡(luò)優(yōu)先出版日期：2015-12-29。

基金項(xiàng)目：國(guó)家自然科學(xué)基金(61173169)資助課題

中圖分類(lèi)號(hào)：TP 393

文獻(xiàn)標(biāo)志碼：A

DOI:10.3969/j.issn.1001-506X.2016.06.29

作者簡(jiǎn)介：

網(wǎng)絡(luò)優(yōu)先出版地址：http://www.cnki.net/kcms/detail/11.2422.TN.20151229.1142.004.html