臺灣博碩士論文加值系統

流行性繞徑協定(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

Abstract iv
List of Contents v
List of Figures vi
List of Tables vii
Chapter 1 Introduction 1
Chapter 2 Related Work 5
Chapter 3 Protocol Design 9
3.1 Network model 9
3.2 Single-packet network model 10
3.2.1 Performance Analysis 18
3.2.2 Analysis of ERP 20
3.2.3 Analysis of NC-LB 22
3.3 Protocol Design for Multiple-Packet Network Model 24
Chapter 4 Simulation Results 28
4.1 Simulation environment 28
4.2 Simulation of single-packet network model 28
4.3 Simulation of multiple-packet network model 31
4.4 Analysis of LD and PWD 34
Chapter 5 Conclusions 36
References 37
Appendix I 40

[1] M. Abdulla and R. Simon, "Controlled Epidemic Routing for Multicasting in Delay Tolerant Networks," in Modeling, Analysis and Simulation of Computers and Telecommunication Systems, 2008. IEEE International Symposium , Baltimore, MD. USA, 2008, pp. 1-10.
[2] R. Ahlswede, N. Cai, S. Y. R. Li, and R. W. Yeung, "Network Information Flow,", IEEE Transactions on Information Theory, vol. 46, pp. 1204-1216, 2000.
[3] K. E. Atkinson, An Introduction to Numerical Analysis: Wiley-India, 2009.
[4] G. Blom, L. Holst, and D. Sandell, Problems and Snapshots from the World of Probability: Springer, 1994.
[5] P. A. Chou, Y. Wu, and K. Jain, "Practical Network Coding," in Proceedings of the Annual Allerton Conference on Communication, Control and Computing, 2003.
[6] K. Fall, "A delay-tolerant network architecture for challenged internets," presented at the Proceedings of conference on Applications, technologies, architectures, and protocols for computer communications, Karlsruhe, Germany, 2003.
[7] G. Fathima and R. Wahidabanu, "Integrating Buffer Management with Epidemic Routing in Delay Tolerant Networks," Journal of Computer Science, vol. 7.
[8] G. Ferrari Aggradi, F. Esposito, and I. Matta, "Supporting predicate routing in dtn over manet," Proceedings of the third ACM workshop on Challenged networks, San Francisco, California, USA, 2008, pp. 125-128.
[9] G. H. Golub and C. F. Van Loan, Matrix Computations: Johns Hopkins University Press, 1996.
[10] R. Groenevelt, P. Nain, and G. Koole, "The message delay in mobile ad hoc networks," Performance Evaluation, vol. 62, pp. 210-228, 2005.
[11] T. Ho, M. Médard, R. Koetter, D. R. Karger, M. Effros, J. Shi, and B. Leong, "A Random linear network coding approach to multicast," Information Theory, IEEE Transactions on, vol. 52, pp. 4413-4430, 2006.
[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.
[14] A. Keränen, J. Ott, and T. Kärkkäinen, "The ONE Simulator For DTN Protocol Evaluation," in Proceedings of the 2nd International Conference on Simulation Tools and Techniques, Rome, Italy, 2009, p. 50.
[15] R. Koetter and M. Médard, "An Algebraic Approach To Network Coding," Networking, IEEE/ACM Transactions on, vol. 11, pp. 782-795, 2003.
[16] Q. Li, S. Zhu, and G. Cao, "Routing In Socially Selfish Delay Tolerant Networks," in Proceedings of the 29th conference on Information communications, 2010, pp. 1-9.
[17] R. Lidl, H. Niederreiter, and P. M. Cohn, Finite fields vol. 20: Cambridge Univ Pr, 1997.
[18] Y. Lin, B. Liang, and B. Li, "Performance Modeling Of Network Coding In Epidemic Routing," presented at the Proceedings of the 1st international MobiSys workshop on Mobile opportunistic networking, San Juan, Puerto Rico, 2007.
[19] Y. Lin, B. Li, and B. Liang, "Stochastic Analysis Of Network Coding In Epidemic Routing," Selected Areas in Communications, IEEE Journal on, vol. 26, pp. 794-808, 2008.
[20] A. Lindgren and K. S. Phanse, "Evaluation Of Queueing Policies And Forwarding Strategies For Routing In Intermittently Connected Networks," in Communication System Software and Middleware, 2006. Comsware 2006. First International Conference on, 2006, pp. 1-10.
[21] X. Lu and P. Hui, "An Energy-Efficient N-Epidemic Routing Protocol For Delay Tolerant Networks," presented at the Proceedings of the 2010 IEEE Fifth International Conference on Networking, Architecture, and Storage, 2010.
[22] R. Motwani and P. Raghavan, Randomized algorithms: Chapman &; Hall/CRC, 2010.
[23] R. C. Shah, S. Roy, S. Jain, and W. Brunette, "Data Mules: Modeling And Analysis Of A Three-Tier Architecture For Sparse Sensor Networks," Ad Hoc Networks, vol. 1, pp. 215-233, 2003.
[24] A. Vahdat and D. Becker, "Epidemic Routing For Partially Connected Ad Hoc Networks," Technical Report CS-200006, Duke University2000.
[25] S. K. Yoon and Z. J. Haas, "Application Of Linear Network Coding In Delay Tolerant Networks," in 2010 Second International Conference on Ubiquitous and Future Networks (ICUFN 2010), Jeju Island, Korea, 2010, pp. 338-343.
[26] L. Yunfeng, L. Baochun, and L. Ben, "Efficient Network Coded Data Transmissions In Disruption Tolerant Networks," INFOCOM 2008. The 27th Conference on Computer Communications. IEEE, Phoenix Arizona USA, 2008, pp. 1508-1516