多跳無線網(wǎng)絡(luò)中基于節(jié)點(diǎn)編碼感知的組播路由協(xié)議

姚玉坤,朱麗青,余志龍,徐亞偉,陳曦

(重慶郵電大學(xué)移動通信技術(shù)重慶市重點(diǎn)實(shí)驗(yàn)室, 400065, 重慶)

?

多跳無線網(wǎng)絡(luò)中基于節(jié)點(diǎn)編碼感知的組播路由協(xié)議

姚玉坤,朱麗青,余志龍,徐亞偉,陳曦

(重慶郵電大學(xué)移動通信技術(shù)重慶市重點(diǎn)實(shí)驗(yàn)室, 400065, 重慶)

針對在編碼感知組播路由協(xié)議CAMR中存在中間轉(zhuǎn)發(fā)節(jié)點(diǎn)因計(jì)算編碼流對不完全且有錯誤而導(dǎo)致不能充分發(fā)現(xiàn)節(jié)點(diǎn)的編碼機(jī)會,以及RREQ請求分組中存在冗余開銷和編碼感知度量值重復(fù)計(jì)算等問題,提出一種適用于多跳無線網(wǎng)絡(luò)的節(jié)點(diǎn)編碼感知組播路由協(xié)議(node network coding aware multicast routing protocol, NAMP)。NAMP協(xié)議對節(jié)點(diǎn)編碼流對算法進(jìn)行了優(yōu)化,以保證所計(jì)算出的編碼流對具有可解性和完整性。在路由請求階段,該協(xié)議去掉了RREQ分組中因循環(huán)添加中間節(jié)點(diǎn)的鄰居信息和丟包率信息而產(chǎn)生的冗余信息,在路由回復(fù)階段,該協(xié)議優(yōu)化了中間節(jié)點(diǎn)收到多個RREP分組的回復(fù)方式,在不影響原有數(shù)據(jù)傳輸功能的前提下減小了網(wǎng)絡(luò)開銷。仿真結(jié)果表明:與CAMR和MAODV兩種現(xiàn)有協(xié)議相比,NAMP協(xié)議提高了網(wǎng)絡(luò)吞吐量,降低了網(wǎng)絡(luò)控制開銷,其中平均吞吐量提高了25.6%,網(wǎng)絡(luò)控制開銷降低了8.1%。

多跳無線網(wǎng)絡(luò);網(wǎng)絡(luò)編碼;編碼感知;編碼流對;平均吞吐量;控制開銷

香港中文大學(xué)的Ahlswede等在2000年首次提出網(wǎng)絡(luò)編碼的概念[1],通過網(wǎng)絡(luò)編碼可以達(dá)到網(wǎng)絡(luò)信息傳輸?shù)睦碚撟畲笾?在此基礎(chǔ)上,人們研究發(fā)現(xiàn)在無線多跳網(wǎng)絡(luò)中能夠提前預(yù)測節(jié)點(diǎn)有無編碼機(jī)會以及編碼能力的大小,這種提前預(yù)測的方法稱為編碼感知,近年來得到了學(xué)者的高度關(guān)注。文獻(xiàn)[2]提出了一種“編碼+路由”的DCAR協(xié)議,但是DCAR協(xié)議沒有考慮單個節(jié)點(diǎn)編碼能力的大小,也不能直接修改用于組播網(wǎng)絡(luò)。文獻(xiàn)[3]提出MORE協(xié)議,通過機(jī)會路由的思想,避免機(jī)會路由中間節(jié)點(diǎn)需要協(xié)商的弊端,但是由于節(jié)點(diǎn)可能會傳輸一些與其編碼系數(shù)相關(guān)的非新數(shù)據(jù)編碼包給接收節(jié)點(diǎn),而導(dǎo)致網(wǎng)絡(luò)帶寬消耗增加。文獻(xiàn)[4]提出了基于遺傳算法的編碼感知路由,利用遺傳算法優(yōu)秀的尋優(yōu)能力,找尋具有最大編碼機(jī)會的路由。文獻(xiàn)[5]通過跨層調(diào)度的方法,提出了一種編碼感知組播MAC協(xié)議,但是該協(xié)議只是考慮了組播樹上節(jié)點(diǎn)的編碼機(jī)會,對于那些非組播樹上的節(jié)點(diǎn)是否具有更大的編碼能力沒有考慮。

Alwis等提出了基于無線Mesh網(wǎng)絡(luò)的內(nèi)容編碼感知組播傳輸算法[6],該算法利用信道編碼和網(wǎng)絡(luò)編碼技術(shù)優(yōu)化數(shù)據(jù)轉(zhuǎn)發(fā)和改善視頻組播服務(wù)在傳輸時延、帶寬利用等方面的效果,但是由于該算法需要傳輸冗余的數(shù)據(jù)來保證視頻的質(zhì)量,因此會增加一定的傳輸開銷。Youghourta等提出了DYGES算法,該算法通過對網(wǎng)絡(luò)環(huán)境中組播流的特性變化自適應(yīng)調(diào)整數(shù)據(jù)分塊的大小,保證每次組播傳輸具有穩(wěn)定的時延[7]。

1 問題分析

為了便于問題描述,本文給出如下幾個定義。

定義1 雙向鄰居補(bǔ)圖GX由頂點(diǎn)集VX和雙向邊集合EX組成,GX表示節(jié)點(diǎn)X一跳范圍內(nèi)節(jié)點(diǎn)構(gòu)成的鄰居圖的補(bǔ)圖。

定義2 雙向邊ea,b表示在雙向鄰居補(bǔ)圖GX中的一條沿節(jié)點(diǎn)a發(fā)出到節(jié)點(diǎn)b的流e(a,b)和沿節(jié)點(diǎn)b發(fā)出到節(jié)點(diǎn)a的流e(b,a)組成的雙向邊。

定義3 流集合eu表示在雙向鄰居補(bǔ)圖GX中,u∈EX,進(jìn)入到節(jié)點(diǎn)u的所有流組成的集合,k條流可以分別用e(1,u),e(2,u),…,e(k,u)表示。

定義4 編碼流對為在雙向鄰居補(bǔ)圖GX中,如果兩條流能夠在節(jié)點(diǎn)X處編碼,那么這兩條流組成一組編碼流對。

經(jīng)過深入研究,我們發(fā)現(xiàn)CAMR協(xié)議主要存在以下兩個缺陷。①在原協(xié)議中,從節(jié)點(diǎn)X的雙向鄰居補(bǔ)圖的流集合中隨機(jī)選出第一條流之后再從剩余的流集合中隨機(jī)篩出第二條流組成一組編碼流對,然后再把第一條流從流集合中刪除,繼續(xù)在流集合中進(jìn)行下一次循環(huán)查找,但是分析發(fā)現(xiàn)上述方法會引起兩個問題,不能保證所選出的編碼流對的完整性。對于第一條流,假如有多條流存在與之組成編碼流對的可能,而原算法只選擇一條流組成一對編碼流對后就刪除第一條邊,由此會導(dǎo)致在以后的循環(huán)查找中不能找到剩余的編碼流對,不能保證所選出的編碼流對具有可解性。選定流集合中的任意流e(u,v)后,并不是刪除進(jìn)入節(jié)點(diǎn)v和發(fā)出節(jié)點(diǎn)u的邊后,再從剩余流集合中任選一條流都可以與e(u,v)組成一組編碼流對,CAMR協(xié)議隨機(jī)選擇這樣的流來進(jìn)行編碼會導(dǎo)致編碼包不能被解碼。②在CAMR協(xié)議的路由請求過程中,中間節(jié)點(diǎn)對請求分組RREQ攜帶的鄰居信息和丟包率需要一直添加,這樣會導(dǎo)致越到后面中間節(jié)點(diǎn)轉(zhuǎn)發(fā)的RREQ里面攜帶的冗余信息越多;在路由回復(fù)過程中,如果中間節(jié)點(diǎn)收到多個RREP響應(yīng)分組時,按原協(xié)議是中間節(jié)點(diǎn)單獨(dú)對每個RREP分組進(jìn)行轉(zhuǎn)發(fā),而分析發(fā)現(xiàn)這樣會導(dǎo)致發(fā)送冗余的RREP分組以及攜帶冗余的信息。

為了解決上述CAMR協(xié)議存在的問題,本文提出了一種節(jié)點(diǎn)編碼感知組播路由協(xié)議(node network coding-aware multicast routing protocol,NAMP)。

2 NAMP協(xié)議

2.1 NAMP協(xié)議提出的新機(jī)制

NAMP協(xié)議針對CAMR協(xié)議中出現(xiàn)的問題以及結(jié)合NAMP協(xié)議的編碼理論分析提出了如下改進(jìn):通過優(yōu)化節(jié)點(diǎn)編碼流對來解決原協(xié)議出現(xiàn)的編碼流對尋找不完全和找到錯誤編碼流對的問題,去掉路由請求分組中的冗余字段以及改進(jìn)路由回復(fù)方式。

2.2 NAMP協(xié)議編碼感知度量值的計(jì)算機(jī)制設(shè)計(jì)

根據(jù)上述改進(jìn)機(jī)制,NAMP協(xié)議通過節(jié)點(diǎn)理論編碼流算法和計(jì)算節(jié)點(diǎn)平均緩存隊(duì)列長度算法來設(shè)計(jì)NAMP協(xié)議的編碼感知度量機(jī)制。

2.2.1 節(jié)點(diǎn)編碼流對算法 為了判斷節(jié)點(diǎn)的編碼機(jī)會,NAMP協(xié)議設(shè)計(jì)節(jié)點(diǎn)編碼流對的計(jì)算步驟如下。

輸入 節(jié)點(diǎn)X的雙向鄰居補(bǔ)圖。

步驟1 從EX中選出流集合H,P=?,其中EX是節(jié)點(diǎn)X的雙向鄰居補(bǔ)圖的邊集,P是輸出的編碼流對的集合。

步驟2 任選一條流e(u,v)∈H,K=H-{e}。

步驟3 從集合K中選擇進(jìn)入到節(jié)點(diǎn)u的流集合eu,P=P∪{e,eu},如果有i條進(jìn)入到節(jié)點(diǎn)u的流eu,P中需要分別統(tǒng)計(jì)這i(i>1)個編碼流對,即P=P∪{e,e(1,u)}∪{e,e(2,u)}∪…∪{e,e(i,u)}。

步驟4 從集合K中選擇從節(jié)點(diǎn)v發(fā)出的流集合ev,P=P∪{e,ev},如果有j條從節(jié)點(diǎn)v發(fā)出的流ev,P中需要分別統(tǒng)計(jì)j(j>1)個編碼流對,即P=P∪{e,e(1,u)}∪{e,e(2,u)}∪…∪{e,e(j,u)}。

步驟5 在集合K中,如果滿足e(w,z)存在于EX中,邊ew,z與邊eu,v沒有公共節(jié)點(diǎn),且雙向邊eu,w、eu,z、ev,w以及ev,z都不屬于EX,那么P滿足P=P∪{e,e(w,z)}∪{e,e(z,w)}。

步驟6 在集合K中,如果滿足e(w,z)存在于EX中,ew,z與邊eu,v沒有公共節(jié)點(diǎn),且4條雙向邊eu,w、eu,z、ev,w、ev,z中有1條屬于EX,那么P會滿足P=P∪{e,e(w,z)}。

步驟7 在集合K中,如果滿足e(w,z)存在于EX中,ew,z與邊eu,v沒有公共節(jié)點(diǎn),且e(u,w)存在于EX中,e(v,z)存在于EX中,那么P=P∪{e,e(w,z)},同理,如果滿足ew,z存在于EX中,ew,z與邊eu,v沒有公共節(jié)點(diǎn),且eu,z存在于EX中,ev,w存在于EX中,那么此時P為P=P∪{e,e(z,w)}。

步驟8 從流集合H中刪除選定流e(u,v),即H=H-{e}。

步驟9 重復(fù)步驟2～8直到集合H為空。

步驟10 輸出所有可能的編碼流對集合P。

2.2.2 節(jié)點(diǎn)編碼流平均隊(duì)列長度算法 計(jì)算節(jié)點(diǎn)編碼流平均隊(duì)列長度算法[2]如下:

(1)刪除編碼圖中緩存隊(duì)列長度為0的頂點(diǎn)和它們相應(yīng)的邊;

(2)初始化L=0,頂點(diǎn)集V=?;

(3)在剩余的頂點(diǎn)集中隨機(jī)選擇頂點(diǎn)i;

(4)找到包含頂點(diǎn)i的最大子圖;

(5)把節(jié)點(diǎn)i的最大子圖添加到集合V中;

(6)L=L+max(Li),i∈V;

(7)去掉集合V中的所有頂點(diǎn)和對應(yīng)的邊;

(8)再次將頂點(diǎn)集V置空,V=?;

(9)重復(fù)步驟(3)～(8)直到所有頂點(diǎn)都去掉;

(10)最后得到L的長度就是節(jié)點(diǎn)X的平均編碼長度。

由于無線鏈路的穩(wěn)定性對數(shù)據(jù)的成功傳輸有著直接影響,因此提出將節(jié)點(diǎn)的鏈路質(zhì)量和編碼能力作為路由度量,定義度量值為

(1)

式中:E(l)表示鏈路l上的期望傳輸次數(shù);L表示鏈路l發(fā)送節(jié)點(diǎn)緩存的平均編碼長度;A表示鏈路l的有效帶寬。

2.3NAMP協(xié)議路由發(fā)現(xiàn)

NAMP協(xié)議采用MAODV組播路由協(xié)議[9]作為設(shè)計(jì)基礎(chǔ),并針對本文研究的編碼機(jī)會感知的需要進(jìn)行了改進(jìn)。在路由發(fā)現(xiàn)階段采用Cl作為路由度量選擇。為確定Cl的值,NAMP協(xié)議需要新增HELLO_Prob包用以路由探測。

通過HELLO_Prob探測包周期性發(fā)送,每個節(jié)點(diǎn)可以獲得Cl度量中的E、B和L的值。

2.3.1 路由請求階段 NAMP協(xié)議的路由請求過程有以下3個步驟。

步驟1 組播源廣播路由請求消息RREQ,RREQ消息需要攜帶節(jié)點(diǎn)的鄰居信息和對應(yīng)的丟包率并將上一跳節(jié)點(diǎn)添加到路徑表F中。

步驟2 中間節(jié)點(diǎn)收到RREQ分組后的操作。

中間節(jié)點(diǎn)收到RREQ消息后,首先判斷是否接收過該RREQ,若已經(jīng)接收過,則直接丟棄;否則,繼續(xù)添加中間節(jié)點(diǎn)的上一跳節(jié)點(diǎn)信息到路徑表F中,用中間節(jié)點(diǎn)自身的鄰居節(jié)點(diǎn)信息和對應(yīng)的丟包率替換原來RREQ對應(yīng)的信息,中間節(jié)點(diǎn)暫存此時的路徑表F,然后廣播RREQ。每個節(jié)點(diǎn)周期性廣播HELLO_Prob包,獲取該節(jié)點(diǎn)各條鏈路的E值與有效帶寬B。

步驟3 目的節(jié)點(diǎn)收到RREQ消息后不刪除從不同路徑收到的RREQ消息,這樣獲得多條可能到達(dá)目的節(jié)點(diǎn)的路徑。

2.3.2 路由回復(fù)階段 NAMP協(xié)議的路由請求過程有以下4個步驟。

步驟1 收到RREQ消息的目的節(jié)點(diǎn)單播回復(fù)RREP消息到組播源節(jié)點(diǎn),在RREP消息中有一條組播源到目的節(jié)點(diǎn)的完整路徑信息Ff。

步驟2 中間節(jié)點(diǎn)判斷其鄰居節(jié)點(diǎn)是否有多個是目的節(jié)點(diǎn),如果是,在等待收到多個RREP分組后,將RREP消息中的Ff與節(jié)點(diǎn)以前暫存的路徑信息F進(jìn)行比較,如果F∈Ff,則此中間節(jié)點(diǎn)通過節(jié)點(diǎn)編碼流對算法、節(jié)點(diǎn)編碼流平均隊(duì)列長度算法以及式(1)計(jì)算出節(jié)點(diǎn)到下一條鏈路的編碼感知度量值Cl,并將已收到的多個RREP中對應(yīng)鏈路的C值與Cl一起添加到一個RREP消息中,然后單播回復(fù)。

步驟3 如果中間節(jié)點(diǎn)在已回復(fù)過RREP的情況下,再次收到從不同路徑轉(zhuǎn)發(fā)來的RREP消息,此時不再計(jì)算自己到下一條鏈路的Cl值,直接將該RREP消息回復(fù)給下一節(jié)點(diǎn)。

步驟4 源節(jié)點(diǎn)收到一個RREP消息后就獲取了到達(dá)一個目的節(jié)點(diǎn)的路徑Ff,以及每條鏈路上的Cl值,源節(jié)點(diǎn)在收到所有目的節(jié)點(diǎn)回復(fù)的RREP消息后,源節(jié)點(diǎn)就獲得了到達(dá)所有目的節(jié)點(diǎn)的一個Mesh結(jié)構(gòu)以及該結(jié)構(gòu)每條邊的Cl值。在此Mesh結(jié)構(gòu)的基礎(chǔ)上,利用最小生成樹的方法,源節(jié)點(diǎn)計(jì)算出一棵包含所有目的節(jié)點(diǎn)的最小生成樹,并按照此最小生成樹發(fā)送數(shù)據(jù)。

3 NAMP協(xié)議性能的理論分析

假定網(wǎng)絡(luò)中有N個組播源節(jié)點(diǎn),且每個中間節(jié)點(diǎn)可以對來自N條流的數(shù)據(jù)進(jìn)行緩存。

3.1 節(jié)點(diǎn)平均吞吐量

由于組播接收節(jié)點(diǎn)接收的數(shù)據(jù)塊大小是一樣的,所以平均吞吐量其實(shí)是和節(jié)點(diǎn)平均傳輸時延成反比的。假設(shè)組播接收節(jié)點(diǎn)的個數(shù)為h,整個數(shù)據(jù)塊大小為M,則平均吞吐量為

(2)

式中:Di表示節(jié)點(diǎn)的傳輸時延。由于NAMP協(xié)議的節(jié)點(diǎn)傳輸時延D小于CAMR協(xié)議的節(jié)點(diǎn)傳輸時延,所以NAMP協(xié)議的平均吞吐量大于CAMR協(xié)議的平均吞吐量。

3.2 節(jié)點(diǎn)轉(zhuǎn)發(fā)RREQ開銷

假設(shè)每個節(jié)點(diǎn)的平均鄰居節(jié)點(diǎn)個數(shù)為B,在RREQ中,一個鄰居節(jié)點(diǎn)信息和對應(yīng)的丟包率所占的大小分別為s1和s2,在CAMR協(xié)議中,中間節(jié)點(diǎn)需要不斷添加其鄰居信息到RREQ中,轉(zhuǎn)發(fā)W個RREQ到目的節(jié)點(diǎn)所帶的開銷為

R1=B(s1+s2)+2B(s1+s2)+…+W(s1+s2)=

0.5W(W+1)B(s1+s2)

(3)

在NAMP協(xié)議中,RREQ只包含節(jié)點(diǎn)自己的額外信息,即轉(zhuǎn)發(fā)W個RREQ所帶的開銷為

R2=B(s1+s2)+B(s1+s2)+…+B(s1+s2)=

WB(s1+s2)

(4)

由式(3)與(4)比較可得R1>R2,說明對于CAMR協(xié)議而言,其節(jié)點(diǎn)轉(zhuǎn)發(fā)RREQ消息所產(chǎn)生的控制開銷(即網(wǎng)絡(luò)消耗)要大于NAMP協(xié)議所產(chǎn)生的控制開銷。

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

采用業(yè)內(nèi)主流的OPNET14.5軟件進(jìn)行建模和仿真,相同場景條件下,從數(shù)據(jù)分組平均端到端時延、數(shù)據(jù)分組傳送成功率以及平均吞吐量等方面,將提出的NAMP協(xié)議與CAMR協(xié)議以及MAODV協(xié)議進(jìn)行性能分析與比較。

4.1 仿真環(huán)境及參數(shù)設(shè)置

仿真實(shí)驗(yàn)采用的網(wǎng)絡(luò)模型是100個節(jié)點(diǎn)隨機(jī)分布在1 000 m×1 000 m的矩形區(qū)域,在這100個節(jié)點(diǎn)中隨機(jī)選擇不同個數(shù)的節(jié)點(diǎn)按照MAODV路由協(xié)議的要求加入一個組播樹中形成組播網(wǎng)絡(luò),改變組播組的成員數(shù)使組播組成員在5～30之間變化。無線信道傳輸模型采用two-ray模型,鏈路層協(xié)議為IEEE 802.11b,上層通過CBR流量生成器產(chǎn)生整個網(wǎng)絡(luò)仿真的數(shù)據(jù)。節(jié)點(diǎn)的平均傳輸范圍設(shè)置為250 m,分組大小為1 kb。

4.2 仿真結(jié)果及分析

4.2.1 節(jié)點(diǎn)平均吞吐量 如圖1所示,當(dāng)組播組的成員數(shù)變化時,NAMP和CAMR協(xié)議的平均吞吐量雖然都是隨著組播組成員數(shù)的增大而明顯增加,但是NAMP協(xié)議的平均吞吐量大于CAMR協(xié)議和MAODV協(xié)議。分析其原因主要是由于CAMR協(xié)議在中間節(jié)點(diǎn)計(jì)算可能的編碼流對的時候簡單地刪除尋找過的編碼流,卻可能遺漏某些實(shí)際存在的編碼流對,而CAMR協(xié)議能尋找到所有可能的編碼流對且更準(zhǔn)確的編碼流對,使得節(jié)點(diǎn)編碼機(jī)會更大,當(dāng)組播組成員數(shù)增加時,編碼機(jī)會也進(jìn)一步增加;對于MAODV協(xié)議,由于沒有捕獲編碼機(jī)會,其吞吐量沒有太大變化,不會隨著組播組成員數(shù)的增大而明顯增加。

圖1 平均吞吐量隨組播組成員數(shù)的變化

4.2.2 RREQ控制開銷 3種協(xié)議的仿真結(jié)果如

圖2所示。圖2表明,NAMP、CAMR和MAODV協(xié)議的RREQ控制開銷均會隨著組播組成員數(shù)的增大而呈上升趨勢。其中,NAMP協(xié)議的RREQ控制開銷小于CAMR協(xié)議的控制開銷,但是大于MAODV協(xié)議的RREQ控制開銷,原因是相對于CAMR協(xié)議,NAMP協(xié)議去掉路由請求分組中不必要的鄰居節(jié)點(diǎn)和丟包率信息,故開銷減小,而在MAODV協(xié)議中,中間節(jié)點(diǎn)轉(zhuǎn)發(fā)的RREQ消息不需要攜帶鄰居節(jié)點(diǎn)和丟包率信息,所以NAMP協(xié)議的控制開銷比MAODV協(xié)議的大。

圖2 RREQ控制開銷隨組播組成員數(shù)的變化

4.2.3 RREP控制開銷 由圖3可知,隨著組播組成員數(shù)的增加,RREP控制開銷也隨之增加,但是NAMP協(xié)議的增長趨勢明顯小于CAMR協(xié)議,其原因是:相較于CAMR協(xié)議,NAMP協(xié)議在回復(fù)RREP消息且中間節(jié)點(diǎn)的鄰居節(jié)點(diǎn)有多個目的節(jié)點(diǎn)時,中間節(jié)點(diǎn)會把收到的多個RREP消息中的編碼感知度量值添加到一個RREP消息中繼續(xù)轉(zhuǎn)發(fā),且對于已經(jīng)轉(zhuǎn)發(fā)過RREP消息的中間節(jié)點(diǎn),再次收到來自不同路徑的RREP消息時不再將自身下一條鏈路的編碼感知度量值添加到RREP中進(jìn)行轉(zhuǎn)發(fā),故RREP控制開銷減小。

圖3 RREP控制開銷隨組播組成員數(shù)的變化

4.2.4 平均端到端時延 由圖4可知,NAMP協(xié)議的平均端到端時延小于CAMR和MAODV協(xié)議,這是由于在NAMP協(xié)議中的中間轉(zhuǎn)發(fā)節(jié)點(diǎn)緩存的平均隊(duì)列長度經(jīng)過編碼感知后小于CAMR協(xié)議,而MAODV協(xié)議沒有采用編碼技術(shù),節(jié)點(diǎn)緩存的平均隊(duì)列長度又大于CAMR協(xié)議,故在節(jié)點(diǎn)中的平均傳輸時延D的比較結(jié)果是MAODV協(xié)議大于CAMR協(xié)議,CAMR協(xié)議大于NAMP協(xié)議。

圖4 平均端到端時延隨組播組成員數(shù)的變化

5 結(jié) 論

本文針對CAMR協(xié)議中尋找編碼感知流不完全、路由請求信息中存在冗余開銷以及重復(fù)計(jì)算編碼感知度量值的問題,提出了一種節(jié)點(diǎn)編碼感知組播路由協(xié)議NAMP。NAMP協(xié)議分別對節(jié)點(diǎn)編碼流對算法和路由發(fā)現(xiàn)算法進(jìn)行了優(yōu)化,確保所計(jì)算出的編碼流對具有可解性和完整性,同時,去掉了RREQ中的冗余信息并優(yōu)化了RREP的回復(fù)方式,提高了網(wǎng)絡(luò)吞吐量,減小了網(wǎng)絡(luò)開銷。仿真結(jié)果表明,與CAMR和MAODV兩種現(xiàn)有協(xié)議相比,NAMP協(xié)議的平均網(wǎng)絡(luò)吞吐量提高了25.6%,網(wǎng)絡(luò)控制開銷降低了8.1%。但是,NAMP協(xié)議在發(fā)送數(shù)據(jù)時沒有考慮節(jié)點(diǎn)的發(fā)送速率,在未來工作中,我們將重點(diǎn)考慮節(jié)點(diǎn)發(fā)送速率對于編碼感知度量值設(shè)計(jì)的影響。

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

[2] LE Jilin, 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.

[3] CHACHUlLSKI S, JENNINGS M, KATTI S, et al. Trading structure for randomness in wireless opportunistic routing [M]. New York, USA: ACM, 2007: 172-181.

[4] SHAO Xing, WANG Ruchuan, XU Hai, et al. Genetic algorithm based coding aware routing for wireless mesh networks [J]. Advances in Information Sciences and Service Sciences, 2012, 4(5): 752-763.

[5] CHOID J, BANG H, LEE C. Network coding-aware multicast optimization in multi-hop wireless networks [C]∥Proceedings of the 2014 IEEE International Conference on Consumer Electronics. Piscataway, NJ, USA: IEEE, 2014: 466-467.

[6] DE C, ARACHCHI H K, FEMANDO A, et al. Content and network-aware multicast over wireless networks [C]∥Proceedings of the 2014 10th IEEE International Conference on Heterogeneous Networking for Quality, Reliability, Security and Robustness. Piscataway, NJ, USA: IEEE, 2014: 122-128.

[7] BENFATTOUM Y, MARTIN S, AGHA K A. QoS for real-time reliable multicasting in wireless multi-hop networks using a generation-based network coding [J]. Computer Networks, 2013, 57(6): 1488-1502.

[8] 黃傳河, 楊文忠, 王博, 等. 無線Mesh網(wǎng)中編碼感知組播路由協(xié)議CAMR [J]. 計(jì)算機(jī)研究與發(fā)展, 2011, 48(6): 1000-1009. HUANG Chuanhe, YANG Wenzhong, WANG Bo, et al. CAMR: network coding-aware muticast routing protocol in wireless mesh networks [J]. Journal of Computer Research and Development, 2013, 48(6): 1000-1009.

[9] ROYER E M. Multicast operation of the Ad-hoc on-demand distance vector protocol [C]∥Proceedings of the Annual International Conference on Mobile Computing and Networking. New York, USA: ACM, 1999: 207-218.

(編輯 武紅江)

A Multicast Routing Protocol Based on Node Network Coding-Aware for Multi-Hop Wireless Network

YAO Yukun,ZHU Liqing,YU Zhilong,XU Yawei,CHEN Xi

(Key Laboratory of Mobile Communications Technology of Chongqing, Chongqing University of Posts and Telecommunications, Chongqing 400065, China)

A multicast routing protocol based on node network coding-aware (NAMP) is proposed to address some problems in the current CAMR (network coding-aware multicast routing) protocol for wireless mesh networks. These problems are the incomplete and erroneous searching of coding flow at middle node, the existence of redundant information of RREQ packet, and the repeated calculation of coding-aware measurements. The NAMP protocol optimizes the algorithm of node coding flow, and ensures the solvability and integrity of the calculated coding flow. The protocol removes the redundant information of RREQ during the routing request stage, and optimizes reply ways of an intermediate node when it receives multiple RREP packets in the routing phase. The network control overhead is also decreased without affecting the original data transmission function. Simulation results and comparisons with existing CAMR and MAODV schemes show that the NAMP improves the average throughput and reduces network control overhead, respectively, and that the average throughput is improved by more than 25.6% and the network control overhead decreases by more than 8.1%.

multi-hop wireless network; network coding; coding-aware; pair of coding flow; average throughput; control overhead

2015-06-01。

姚玉坤(1964—),女,教授。

長江學(xué)者和創(chuàng)新團(tuán)隊(duì)發(fā)展計(jì)劃資助項(xiàng)目(IRT1299);重慶市自然科學(xué)基金資助項(xiàng)目(cstc2012jjA40040)。

10.7652/xjtuxb201510013

TP393

A

0253-987X(2015)10-0079-05