網絡編碼VS.存儲轉發：移動自組網中實時多播機制仿真研究

譚國平, 季 敏, 倪新洋, 馬賽賽

(河海大學計算機與信息學院通信與信息系統研究所,江蘇南京210098)

1 引言

移動自組織網絡(Mobile Ad Hoc Network,MANET)是一種由網絡中的一組節點或終端形成的無中心、自組織、自管理的無線網絡。與有線網絡相比較,MANET對節點能耗及高效的帶寬利用率的要求更高,設計高效的MANET路由協議是目前研究的熱點問題之一。

目前已經存在多種MANET多播協議,但基于網絡編碼的多播協議打破了原有基于存儲轉發協議性能的局限。由文獻[1]可知,采用網絡編碼的多播協議的信道容量可以達到最大流最小割定理的上界。而根據文獻[2]可知,采用網絡編碼的數據分發機制可以大幅度減少數據包交換次數,減少能量開銷。但是,與傳統的基于存儲轉發的多播協議相比,基于網絡編碼的實時多播協議在時延、可靠性以及系統開銷等方面性能增益尚不明確。因此采用網絡編碼技術,在NS2仿真平臺上實現了一種基于網絡編碼的實時多播協議(Network Coding based Realtime Multicast,NCRM)。為了比較NCRM與傳統的基于存儲轉發多播協議的性能,文章選取典型的基于樹的MAODV[3](Multicast operation of the Ad hoc On-demand Distance Vector routing protocol)協議以及基于mesh的PUMA[4](Protocol for Unified Multicasting though Announcements)協議作為比較對象,在延時、開銷以及可靠性等方面的性能進行仿真比較研究。

2 MAODV、PUMA及網絡編碼簡介

2.1 MAODV協議

MAODV多播路由協議采用廣播路由請求-答復機制。當某個節點想加入一個多播組或有數據分組需要發送到多播組時,便發起建立多播路由過程。如圖1所示,MAODV的多播樹中包括組成員和非組成員(也稱樹成員)兩種,每個多播樹有一個組長,主要負責維護多播樹。

當某個節點想加入多播組時,它就廣播一個帶有“J”標志和多播組地址的RREQ消息。具有不小于接收到的RREQ-J消息中的組序列號的多播組成員單播一個RREP-J的應答消息。每一個接收到RREQ的節點都更新自己的路由表,并記錄到請求源節點的下一跳信息以及傳輸RREP到源請求節點的路由信息。經過一段等待時間,發送RREQ消息的節點會在已接收到的RREP消息中選擇一條具有最大序列號和最短距離的路徑,并向下一跳發送一個MACT消息,激活多播表中選定的下一跳。這樣一個更新后的多播樹便建立完成。

圖1 MAODV的多播路由過程

2.2 PUMA協議

PUMA協議是一種基于Mesh網絡的多播路由協議,支持IP多播服務模式,采用由接收節點發起路由的方式,接收端通過使用核心節點的地址加入多播分組。核心節點周期性的發出單一的控制報文(Multicast Announcement,MA)給網絡中的節點,節點根據接收到的MA中的信息建立起連接表。通過連接表,網絡中的節點和核心節點之間的最短連接路徑相連,所有這些最短路徑一起構成mesh網格。沿著節點和核心節點間的最短路徑發送多播數據。當多播數據到達任意一個mesh成員,mesh成員再將這個數據多播給其他所有mesh成員,并且每個節點都構建一個包ID緩存來驗證是否收到重復的MA。

2.3 網絡編碼簡介

網絡編碼的概念最初是由R.Ahlswed等[1]提出的。從信息論的角度出發,嚴格證明了在單點對多點的通信網絡中,通過節點編碼的方式可以使信息傳輸速率達到網絡的最大流量。Li等[5]證明了可以使用線性網絡編碼方法使多播能夠達到最大容量。隨后Ho及Medard等[6]提出了隨機線性網絡編碼的概念,文中NCRM的編碼過程就采用了線性隨機網絡編碼方式。

線性網絡編碼就是將一個或多個源節點產生的數據信息包線性的映射到一個有限域內,利用線性關系實現編譯碼的過程。線性網絡編碼在算法設計上分為確定性編碼和隨機編碼兩種。下面就是隨機線性網絡編碼的實現過程。

源節點S要發送n個原始信息向量X1…Xn給目的節點,源節點發送前隨機選擇全局編碼向量g1…gn將X1…Xn編碼成Y=g1X1+g2X2+…gnXn之后再傳輸,記為(g,Y)。中繼節點再隨機在有限域內生成局部編碼向量h=(h1…hn)對收到的 n個(g,Y)進行線性編碼得到一個新的信息包(g′,Y′)再發送給鄰節點。當目的節點接收到n個線性無關的(g′,Y′)后,則可根據高斯消元法進行解碼。

3 基于網絡編碼的實時多播協議NCRM

3.1 NCRM協議的報文格式

為了在仿真平臺中實現NCRM協議,設計的NCRM報文格式如圖2所示。

3.2 NCRM處理流程

與文獻[7]的編碼方法不同,NCRM是在基于PUMA協議的基礎之上,利用隨機網絡編碼算法對要發送的多播信息進行處理。發送數據包時不是直接單個發送,而是在發送端和中間節點對需要發送的一系列數據包采用隨機網絡編碼的方式進行處理,同時在接收節點也采用網絡編碼的方式來協助解碼。這樣可顯著減少網絡中數據的傳輸次數,從而節省網絡帶寬并降低節點能耗。

3.2.1 發送端處理

假定發送節點的上層應用持續生成并連續發送數據包。當網絡層接收到數據包時,根據數據包的UID將包分組成不同的block,且每BLOCK-SIZE個數據包組成一個block,隨之將處理完的數據包存入發送節點的本地緩存中。

圖2 NCRM的報文格式

當本地緩存中接收滿一個block的數據包時,隨即對block進行初始編碼操作,生成編碼包,同時將生成的隨機編碼向量存入編碼包的encoding vector域中,隨編碼包一同傳輸。每次初始編碼都將block編碼成BLOCKSIZE個編碼包發送給鄰居節點,以確保包含了下游節點恢復原始數據包所需的足夠多的線性無關的編碼向量。

3.2.2 中間節點處理

網絡中的某一節點收到一個編碼包時,檢查編碼包是否攜帶新信息,若有則將編碼包存入本地緩存,否則丟棄編碼包。當中間節點在一定時間內尚未收集到足夠多的關于某block的編碼包,便利用已收集到的編碼包進行二次編碼,將編碼成的一個編碼包廣播給鄰居節點以期某個鄰居節點可以提供節點所需的編碼包。若中間節點在一定時間內收到關于某block足夠多編碼系數線性無關的編碼包時,節點也會對block進行二次編碼,接著將生成的編碼包轉發給鄰居節點。

3.2.3 接收節點處理

當接收節點收到關于某個block足夠多的編碼向量線性無關的編碼包時,節點可以順利通過高斯消元法恢復出該block的原始數據包。若在一定時間內接收節點仍然無法收集滿足夠多的編碼向量線性無關的編碼包,則利用類似于中間節點的操作,即將已收集到的編碼包二次編碼生成一個編碼包,以向鄰居節點請求相關資源。

若接收節點順利地恢復出某一block的原始數據包,則節點同時對block進行二次編碼后將編碼包廣播給鄰居節點,以期向下游節點傳遞該block或者為鄰居節點提供block的冗余編碼包。

4 仿真及分析

4.1 仿真環境介紹

4.1.1 NS2軟件

NS2[8]是一種源代碼公開免費仿真平臺,是面向對象的離散時間驅動的網絡模擬器,由UC Berkeley研發,能夠對現有的網絡協議提供很好的支持,提供基本的網絡元素支持并用對象實現,易于組合,易于擴展,大大減少了網絡模擬研究的工作量。

4.1.2 仿真協議棧

采用的仿真協議棧如圖3所示,應用層中使用CBR(恒定比特率)的數據流作為傳送的數據源,發送端CBR沿著傳輸層、網絡層、MAC層以及使用Two-ray ground reflection模型的物理層進行傳輸。而接收端則沿著相反路徑將接收的CBR傳輸到應用層。應用層主要提供面向用戶的協通應用服務,而傳輸層主要是向應用層提供可靠的端到端服務。主要工作是在網絡層中實現,網絡層需要完成鄰居發現、分組路由、擁塞控制以及網絡互聯等功能。在MAC層采用隨機競爭機制IEEE802.11控制節點對無線信道的訪問,而物理層負責無線信號的檢測,調制解調,信號發送接收等工作。

4.2 仿真參數及性能指標

為了評估NCRM的性能,在NS2仿真平臺上搭建了相應的仿真環境,仿真環境的參數設置如表1所示。

圖3 仿真協議棧

表1 仿真參數設置

為了能合理的評估NCRM機制的性能仿真,選取3個指標進行性能評估,其定義如下：

分組投遞率：即接收節點實際接受收的數據包的個數與希望接被接收節點接收到數據包的個數之比,反映了協議的可靠性,即分組率越高,可靠性越大。分組投遞率=接收節點實際接收到數據包/(發送節點發送的數據包個數×接收節點個數)。

路由總開銷：即發送的控制包、數據包個數之和與接收到的數據包的個數之比,反映了協議的有效性,即總開銷越小,協議的效率越高。總開銷=(發送的控制包個數+發送的數據包個數)/實際接收到的數據包的個數。

端到端延時：即數據包從發送節點到接收節點經歷的時間,包括路由查找延時,數據包在接口隊列的等待延時,傳輸延時及MAC層的重傳延時,反映了路由的有效性。端到端延時=∑(接收到數據包時間-發送數據包時間)/發送數據包的個數。

4.3 仿真結果比較及分析

4.3.1 節點密度變化時性能的比較

為了研究多播組中的總節點密度對協議性能的影響,設置總節點密度分別為41/64、41/49、41/36、41/25、41/16、41/9(個/104m2),此外設置節點的移動速度為15m/s,則關于分組投遞率、總開銷以及端到端延時的仿真結果比較圖如圖4所示。

圖4 節點密度對性能的影響

首先,如圖4(a)所示,隨著節點密度的增大,對于每個節點,處在其信號覆蓋范圍內的鄰居節點也隨之增多,從而使節點間鏈路的可靠性得到增強。因此3種協議的分組投遞率都逐漸增大,其中NCRM的分組投遞率始終保持在90%以上。但NCRM和PUMA的分組投遞率相對于MAODV始終保持5%以上的優勢。因為基于mesh的PUMA和NCRM在節點增多的情況下,無需建立額外的節點間通信鏈路。而基于樹形結構的MAODV,則需要更多的控制開銷來建立、維護其多播樹結構。而這些控制開銷導致的信道資源占用將影響MAODV的分組投遞率。

其次,如圖4(b)所示,隨著節點密度的增大,3種協議的總開銷均呈下降趨勢。節點密度的增大,使得NCRM中參與網絡編碼的節點個數增多,極大的減小了其總開銷。MAODV借助于樹形結構,其投遞分組的效率高于PUMA。此外,由于存在mesh網之內的分組洪泛,PUMA的總開銷在3種協議中始終最大。可以看出,為達到同樣的分組投遞率,NCRM所耗費的信道資源遠遠小于PUMA。

最后,如圖4(c)所示,隨著節點密度的增大NCRM的端到端時延呈下降趨勢,但相較于PUMA和MAODV而言,NCRM的時延要遠大于其他兩個協議,是因為NCRM緩存數據包要花費大量的時間,因而NCRM的時延在3種協議中最大。

4.3.2 節點移動速度對性能的影響

為了研究在節點移動速度變化情況下協議的性能,設置節點移動速度分別為0、5、10、15、20、25(m/s)。則關于分組投遞率、總開銷以及端到端延時的仿真結果比較圖如圖5所示。

首先,如圖5(a)所示,NCRM的包投遞率基本維持在94%以上,體現了良好的魯棒性。是因為隨著節點移動速度的增加,雖然鏈路的不穩定性增大,但由于NCRM中進行網絡編碼操作的概率將逐漸增大,致使數據包的轉發次數將少于PUMA以及MAODV。另外,NCRM中控制消息也很少,因此其在數據包轉發過程中出現沖突的概率也較小。最終,當移動速度達到一定值時,NCRM中的包投遞率明顯優于其他兩個協議。

其次,如圖5(b)所示,由于PUMA在mesh網中所采用的數據包洪泛機制,其數據包轉發次數明顯高于NCRM及MAODV,致使PUMA協議的總開銷高于MAODV及NCRM。但隨著多播組個數的增加,MAODV需要維護多個多播樹,其產生的控制開銷將急劇增大,導致總開銷也隨之增大。文獻[3]表明,若存在足夠多的多播組,MAODV的總開銷將會是PUMA以及ODMPR的數百倍,在這種情況下MAODV的包投遞率呈逐步下降趨勢。

最后,如圖5(c)所示,此時NCRM的時延與密度變化時的情況變化不大,都是由于緩存數據包時花費了大量時間,因而其時延上面的性能遠不及其他兩個協議。綜上,由密度變化和移動速度變化的情況可以看出,NCRM在分組投遞率和總開銷方面都有很大的優勢,但由于NCRM機制的不成熟,NCRM在時延方面仍有很大的改進空間。

圖5 節點移動速度對性能的影響

5 結束語

采用NS2仿真平臺,實現了一種基于網絡編碼的實時多播協議(NCRM),與傳統基于存儲轉發的協議(PUMA和MAODV)進行了性能比較。通過仿真結果發現與傳統的基于存儲轉發技術的多播路由協議相比較,NCRM協議在可靠性,系統開銷方面具有顯著優勢,但在時延性能方面不如傳統的路由協議,由此可以看出,通過合理的參數設置,NCRM可以在以上幾個方面取得很好的性能均衡。最后值得指出的是,僅基于單個多播場景對NCRM協議的性能進行了初步的仿真研究,多個多播場景并存的混合發送以及延時控制的問題將是下一步的研究內容。

[1]R Ahlswede,N Cai,S YR Li,et al.Network information flow[J].IEEE Trans.Inform.Theory,2000,46：1204-1216.

[2]黃辰,王芙蓉.基于網絡編碼的無線自組織網數據分發機制[J].電子學報,2010,38：1853-1857.

[3]E M Royer,C E Perkins.Multicast operation ofthe ad-hoc on-demand distance vector routing protocol[J].IEEE International Conference on Mobile Computingand Networking(MOBICOM),1999：207-218.

[4]Ravindraand J J.Efficient and Robust Multicast Routing in Mobile AdHoc Networks[J].IEEE International Conference on Mobile Ad-hoc andSensor System,2004：304-313.

[5]S YR Li,R W Yeung,N Cai.Liner network coding[J].IEEE Trans.Inform.Theory,2003,49：371-381.

[6]Ho T,Koetter M,Medard M,el at.Toward,A random operation of networks[J].IEEE Trans.Inform.Theory,2004：442-445.

[7]焦進,楊銘熙.基于網絡編碼的Ad Hoc網PUMA協議的研究[J].中國科技論文在線,2010：1-7.

[8]黃化吉,馮德力.NS網絡模擬和協議仿真[M].北京：人民郵電出版社,2010.