利用網路編碼提升有限緩衝儲存裝置之耐延遲網路效率

Efficient Transmission Protocols Using Network Coding in Delay Tolerant Networks with Limited Buffers

李知穎(Chih-Yin Lee)

指導教授 ： 許健平

國立清華大學/電機資訊學院/資訊工程學系/碩士(2012年)

摘要

流行性繞徑協定(Epidemic routing protocol)近年來已被廣泛地研究和應用在耐延遲網路之中。在耐延遲網路中，因移動節點與移動節點之間的連線是間歇性的，使得封包的傳輸延遲通常很長，但流性繞徑協定藉著大量複製並散播起始封包在網路中，得以縮短封包的傳輸延遲時間，及增進封包傳遞率，但卻會大量消耗記憶空間及網路頻寬。本論文提出一個網路編碼(Network coding)為基礎的繞徑協定，此協定在有限記憶空間的限制下，與流行性繞徑協定相比，可以提昇多個起始節點傳輸資料到一個目的節點(封包聚集)的傳輸效率。我們提出的方法主要是讓網路中的節點，在沒有多餘的記憶空間時，將兩個封包以網路編碼的方式合成為一個混合封包。在本論文的分析中，網路編碼為基礎的繞徑協定，在各種參數下所需的封包聚集時間，皆不會長於流行性繞徑協定，在起始結點數多時，時間節省比率甚至大於百分之七十。本篇論文的模擬結果與我們的分析結果相符，我們提出的網路編碼為基礎的繞徑協定，相對於流行性繞徑協定在各種參數的耐延遲網路中都能夠有較佳的表現。

關鍵字

耐延遲網路 ； 網路編碼 ； 流行性繞徑協定 ； 有限緩衝儲存裝置 ； 多對一網路架構

並列摘要

Epidemic routing protocol (ERP) had been widely studied and applied to the Delay Tolerant Networks (DTNs). In DTNs, the delay of packets is long due to the intermittent connections cause by the mobility of nodes. However, ERP can reduce the delay time and raise the packet delivery rate by replicating and spread several copies of a source packet into the network, but inevitably exhaust enormous memory resources and network bandwidth.
We propose a network coding with limited buffer routing protocol (NC-LB) in this thesis. NC-LB improves the performance of ERP in many-to-one communications in DTNs when the buffer size is limited. When the buffer of a node is full, two packets in the buffer are randomly chosen and be linearly encoded together in to a packet to save buffer space. From our analysis, the converging time of NC-LB is equal or lower than ERP, NC-LB even saves more than 70% converging time than ERP when the source node number to buffer size ratio is high. The simulation results conform to the analysis that NC-LB outperforms ERP in DTNs for many-to-one model with limited buffer size

並列關鍵字

Delay tolerant networks ； epidemic routing ； limited buffer ； multicast ； network coding

參考文獻

[3] K. E. Atkinson, An Introduction to Numerical Analysis: Wiley-India, 2009.

[7] G. Fathima and R. Wahidabanu, "Integrating Buffer Management with Epidemic Routing in Delay Tolerant Networks," Journal of Computer Science, vol. 7.

[10] R. Groenevelt, P. Nain, and G. Koole, "The message delay in mobile ad hoc networks," Performance Evaluation, vol. 62, pp. 210-228, 2005.

[12] T. Hossmann, T. Spyropoulos, and F. Legendre, "Know thy neighbor: Towards optimal mapping of contacts to social graphs for dtn routing," in In Proceedings of IEEE INFOCOM 2010, 2010, pp. 1-9.

[13] D. B. Johnson and D. A. Maltz, "Dynamic source routing in ad hoc wireless networks," Mobile computing, pp. 153-181, 1996.