多跳無線網絡中基于節點編碼感知的組播路由協議

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

(重慶郵電大學移動通信技術重慶市重點實驗室, 400065, 重慶)

?

多跳無線網絡中基于節點編碼感知的組播路由協議

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

(重慶郵電大學移動通信技術重慶市重點實驗室, 400065, 重慶)

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

多跳無線網絡;網絡編碼;編碼感知;編碼流對;平均吞吐量;控制開銷

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

Alwis等提出了基于無線Mesh網絡的內容編碼感知組播傳輸算法[6],該算法利用信道編碼和網絡編碼技術優化數據轉發和改善視頻組播服務在傳輸時延、帶寬利用等方面的效果,但是由于該算法需要傳輸冗余的數據來保證視頻的質量,因此會增加一定的傳輸開銷。Youghourta等提出了DYGES算法,該算法通過對網絡環境中組播流的特性變化自適應調整數據分塊的大小,保證每次組播傳輸具有穩定的時延[7]。

1 問題分析

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

定義1 雙向鄰居補圖GX由頂點集VX和雙向邊集合EX組成,GX表示節點X一跳范圍內節點構成的鄰居圖的補圖。

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

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

定義4 編碼流對為在雙向鄰居補圖GX中,如果兩條流能夠在節點X處編碼,那么這兩條流組成一組編碼流對。

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

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

2 NAMP協議

2.1 NAMP協議提出的新機制

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

2.2 NAMP協議編碼感知度量值的計算機制設計

根據上述改進機制,NAMP協議通過節點理論編碼流算法和計算節點平均緩存隊列長度算法來設計NAMP協議的編碼感知度量機制。

2.2.1 節點編碼流對算法 為了判斷節點的編碼機會,NAMP協議設計節點編碼流對的計算步驟如下。

輸入 節點X的雙向鄰居補圖。

步驟1 從EX中選出流集合H,P=?,其中EX是節點X的雙向鄰居補圖的邊集,P是輸出的編碼流對的集合。

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

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

步驟4 從集合K中選擇從節點v發出的流集合ev,P=P∪{e,ev},如果有j條從節點v發出的流ev,P中需要分別統計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沒有公共節點,且雙向邊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沒有公共節點,且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沒有公共節點,且e(u,w)存在于EX中,e(v,z)存在于EX中,那么P=P∪{e,e(w,z)},同理,如果滿足ew,z存在于EX中,ew,z與邊eu,v沒有公共節點,且eu,z存在于EX中,ev,w存在于EX中,那么此時P為P=P∪{e,e(z,w)}。

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

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

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

2.2.2 節點編碼流平均隊列長度算法 計算節點編碼流平均隊列長度算法[2]如下:

(1)刪除編碼圖中緩存隊列長度為0的頂點和它們相應的邊;

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

(3)在剩余的頂點集中隨機選擇頂點i;

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

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

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

(7)去掉集合V中的所有頂點和對應的邊;

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

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

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

由于無線鏈路的穩定性對數據的成功傳輸有著直接影響,因此提出將節點的鏈路質量和編碼能力作為路由度量,定義度量值為

(1)

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

2.3NAMP協議路由發現

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

通過HELLO_Prob探測包周期性發送,每個節點可以獲得Cl度量中的E、B和L的值。

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

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

步驟2 中間節點收到RREQ分組后的操作。

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

步驟3 目的節點收到RREQ消息后不刪除從不同路徑收到的RREQ消息,這樣獲得多條可能到達目的節點的路徑。

2.3.2 路由回復階段 NAMP協議的路由請求過程有以下4個步驟。

步驟1 收到RREQ消息的目的節點單播回復RREP消息到組播源節點,在RREP消息中有一條組播源到目的節點的完整路徑信息Ff。

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

步驟3 如果中間節點在已回復過RREP的情況下,再次收到從不同路徑轉發來的RREP消息,此時不再計算自己到下一條鏈路的Cl值,直接將該RREP消息回復給下一節點。

步驟4 源節點收到一個RREP消息后就獲取了到達一個目的節點的路徑Ff,以及每條鏈路上的Cl值,源節點在收到所有目的節點回復的RREP消息后,源節點就獲得了到達所有目的節點的一個Mesh結構以及該結構每條邊的Cl值。在此Mesh結構的基礎上,利用最小生成樹的方法,源節點計算出一棵包含所有目的節點的最小生成樹,并按照此最小生成樹發送數據。

3 NAMP協議性能的理論分析

假定網絡中有N個組播源節點,且每個中間節點可以對來自N條流的數據進行緩存。

3.1 節點平均吞吐量

由于組播接收節點接收的數據塊大小是一樣的,所以平均吞吐量其實是和節點平均傳輸時延成反比的。假設組播接收節點的個數為h,整個數據塊大小為M,則平均吞吐量為

(2)

式中:Di表示節點的傳輸時延。由于NAMP協議的節點傳輸時延D小于CAMR協議的節點傳輸時延,所以NAMP協議的平均吞吐量大于CAMR協議的平均吞吐量。

3.2 節點轉發RREQ開銷

假設每個節點的平均鄰居節點個數為B,在RREQ中,一個鄰居節點信息和對應的丟包率所占的大小分別為s1和s2,在CAMR協議中,中間節點需要不斷添加其鄰居信息到RREQ中,轉發W個RREQ到目的節點所帶的開銷為

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

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

(3)

在NAMP協議中,RREQ只包含節點自己的額外信息,即轉發W個RREQ所帶的開銷為

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

WB(s1+s2)

(4)

由式(3)與(4)比較可得R1>R2,說明對于CAMR協議而言,其節點轉發RREQ消息所產生的控制開銷(即網絡消耗)要大于NAMP協議所產生的控制開銷。

4 仿真實驗及分析

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

4.1 仿真環境及參數設置

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

4.2 仿真結果及分析

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

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

4.2.2 RREQ控制開銷 3種協議的仿真結果如

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

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

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

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

4.2.4 平均端到端時延 由圖4可知,NAMP協議的平均端到端時延小于CAMR和MAODV協議,這是由于在NAMP協議中的中間轉發節點緩存的平均隊列長度經過編碼感知后小于CAMR協議,而MAODV協議沒有采用編碼技術,節點緩存的平均隊列長度又大于CAMR協議,故在節點中的平均傳輸時延D的比較結果是MAODV協議大于CAMR協議,CAMR協議大于NAMP協議。

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

5 結 論

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

[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網中編碼感知組播路由協議CAMR [J]. 計算機研究與發展, 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—),女,教授。

長江學者和創新團隊發展計劃資助項目(IRT1299);重慶市自然科學基金資助項目(cstc2012jjA40040)。

10.7652/xjtuxb201510013

TP393

A

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