學術產出-Theses
Article View/Open
Publication Export
-
題名 耐延遲車載網路上利用網路編碼之位置輔助路由
Location assisted routing with network coding in vehicular delay tolerant networks作者 陳界誠
Chen, Chieh Cheng貢獻者 蔡子傑
Tsai, Tzu-Chieh
陳界誠
Chen, Chieh Cheng關鍵詞 耐延遲網路
路由協定
網路編碼
Delay tolerant network
routing
network coding日期 2010 上傳時間 4-Sep-2013 17:05:58 (UTC+8) 摘要 耐延遲網路(Delay Tolerant Networks)上的路由協定可以區分為兩大類:flooding-based protocols 跟forwarding-based protocols。網路編碼(Network Coding)是一種編碼技術可以提高訊息傳輸的可靠度；並且運作時不需要知道整體網路的拓樸資訊。我們提出的演算法結合了flooding-based protocols 跟forwarding-based protocol特性，最主要的概念是讓訊息不是被傳送給每一個節點，而是傳送給朝向目的地或是接近目的地的節點。當節點相遇時，我們的方法會利用節點的路徑、移動方向與速度去預測到達目的地的機率。同時我們利用網路編碼的技巧傳送編碼後的資料來代替訊息的片段，來避免重複傳送多餘的訊息；並讓通訊更加可靠。根據實驗模擬的結果，我們的機制有較好的效能，特別是在頻寬的使用上。
The routing protocols of delay tolerant networks could be divided in two categories: flooding-based protocols and forwarding-based protocols. Network coding is an encoding technique that could make data transmission more reliable. It operates without the needed of information about the network topology. We proposed a routing protocol integrating the characteristic of flooding-based protocol and forwarding-based protocol. The main idea of our protocol is to let message would not be flooded to every node but to the nodes moving toward or moving closer to destination. When nodes contact with each other, our approach will use the path of node, node’s moving direction and its velocity to estimate the probability to reach the destination of message. At the same time, we exploit network coding to transmit coded block instead of message fragment in order to avoid sending redundant replication, make data transmit more reliable and more robust to packet losses or delays. From the result of simulation, we could see that our protocol have a higher performance especially in the bandwidth consumption compared to other protocols.參考文獻 [1] Jian Shen, Sangman Moh, and Ilyong Chung, “Routing Protocols in Delay Tolerant Networks: A Comparative Survey” in International Technical Conference on Circuits/Systems, Computers and Communications (ITC-CSCC’ 08), July 2008[2] R. Ahlswede, N. Cai, S.-Y. R. Li, and R.W. Yeung, “Network information flow,” IEEE Trans. on Information Theory, vol. 46, no. 4, July 2000.[3] T. Ho, R. Koetter, M. Medard, D. R. Karger, and M.Effros. “The benefits of coding over routing in a randomized setting”International Symposium on Information Theory (ISIT), page 442, July 2003[4] P. A. Chou, Y. Wu, and K. Jain. Practical network coding. In Proc. Allerton, Oct. 2003.[5] R. H. Frenkiel, B. R. Badrinath, J. Borres, and R. D. Yates, “The infostations challenge: balancing cost and ubiquity in delivering wireless data,” IEEE Personal Communications, vol. 7, no. 2, pp. 66–71, 2000[6] D. Nain, N. Petigara, and H. Balakrishnan,“Integrated routing and storage for messaging applications in mobile ad hoc networks,” Mobile Networks and Applications (MONET), vol. 9, pp. 595–604, December 2004.[7] T. Spyropoulos, K. Psounis, and C. S. Raghavendra,“Spray and wait: an efficient routing scheme for intermittently connected mobile networks,” in Proceedings of the ACM SIGCOMM Workshop on Delay-Tolerant Networking (WDTN’05), pp. 252–259, August 2005.[8] A. Demers, D. Greene, C. Houser, W. Irish, J. Larson, S. Shenker, H. Sturgis, D. Swinehart, and D. Terry,“Epidemic algorithms for replicated database maintenance,” SIGOPS Operating Systems Review, vol. 22, pp. 8–32, January 1988.[9] A. Vahdat and D. Becker, “Epidemic routing for partially-connected ad hoc networks,” Tech. Rep. CS-2000-06, Duke University, July 2000.[10] J. Lebrun, C.-N. Chuah, D. Ghosal, and M. Zhang,“Knowledge-based opportunistic forwarding in vehicular wireless ad hoc networks,” in Proceedings ofIEEE Vehicular Technology Conference (VTC), vol. 4, pp. 2289–2293, May 2005.[11] P. Juang, H. Oki, Y. Wang, M. Martonosi, L. S. Peh, and D. Rubenstein, “Energy-efficient computing for wildlife tracking: design tradeoff’s and early experiences with zebranet,” in Proceedings of ASPLOS-X, pp. 96–107, October 2002.[12] A. Lindgren, A. Doria, and O. Schel´en, “Probabilistic routing in intermittently connected networks,” Lecture Notes in Computer Science, vol. 3126, pp. 239–254, January 2004.[13] S. Jain, K. Fall, and R. Patra, “Routing in a delay tolerant network,” in Proceedings of ACM SIGCOMM, vol. 34, pp. 145–158, ACM Press, October 2004.[14] C. Gkantsidis and P. Rodriguez. Network coding for large scale content distribution. In Infocom, Miami,FL, Mar. 2005. [15] C. Gkantsidis, J. Miller and P. Rodrques. Comprehensive view of a live network coding P2P system[16] S. Katti, H. Rahul, D. Katabi, W. Hu M. M´edard, and J. Crowcroft. XORs in the Air:Practical Wireless Network Coding. In SIGCOMM, 2006.[17] U. Lee, J.-S. Park, J. Yeh, G. Pau, and M. Gerla. “CodeTorrent: Content Distribution using Network Coding in VANETs. “ in MobiShare’06, Los Angeles, CA, Sept. 2006.[18] S. Ahmed and S. S. Kanhere, “VANETCODE: Network coding to enhance cooperative downloading in vehicular ad-hoc networks,” in Proc. ACM Int. Conf. on Commun. And Mobile Comput., 2006, pp. 527–532.[19] J. Widmer and J.-Y. LeBoudec. “Network coding for efficient communication in extreme networks. “ in WDTN, Aug. 2005.[20] X. Zhang, G. Neglia, J. Kurose, D. Towsley. “On the Benefits of Random Linear Coding for Unicast Applications in Disruption Tolerant Networks. “ in Second Workshop on Network Coding, Theory, and Applications. 2006[21] A. Keränen, J. Ott, and T. Kärkkäinen, "The ONE Simulator for DTN Protocol Evaluation," in SIMUTools`09: 2nd International Conference on Simulation Tools and Techniques, Rome, March 2-6, 2009. 描述 碩士
國立政治大學
資訊科學學系
97753003
99資料來源 http://thesis.lib.nccu.edu.tw/record/#G0097753003 資料類型 thesis DOI http://dx.doi.org/10.1109/ICCChina.2012.6356967 dc.contributor.advisor 蔡子傑 zh_TW dc.contributor.advisor Tsai, Tzu-Chieh en_US dc.contributor.author (Authors) 陳界誠 zh_TW dc.contributor.author (Authors) Chen, Chieh Cheng en_US dc.creator (作者) 陳界誠 zh_TW dc.creator (作者) Chen, Chieh Cheng en_US dc.date (日期) 2010 en_US dc.date.accessioned 4-Sep-2013 17:05:58 (UTC+8) - dc.date.available 4-Sep-2013 17:05:58 (UTC+8) - dc.date.issued (上傳時間) 4-Sep-2013 17:05:58 (UTC+8) - dc.identifier (Other Identifiers) G0097753003 en_US dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/60239 - dc.description (描述) 碩士 zh_TW dc.description (描述) 國立政治大學 zh_TW dc.description (描述) 資訊科學學系 zh_TW dc.description (描述) 97753003 zh_TW dc.description (描述) 99 zh_TW dc.description.abstract (摘要) 耐延遲網路(Delay Tolerant Networks)上的路由協定可以區分為兩大類:flooding-based protocols 跟forwarding-based protocols。網路編碼(Network Coding)是一種編碼技術可以提高訊息傳輸的可靠度；並且運作時不需要知道整體網路的拓樸資訊。我們提出的演算法結合了flooding-based protocols 跟forwarding-based protocol特性，最主要的概念是讓訊息不是被傳送給每一個節點，而是傳送給朝向目的地或是接近目的地的節點。當節點相遇時，我們的方法會利用節點的路徑、移動方向與速度去預測到達目的地的機率。同時我們利用網路編碼的技巧傳送編碼後的資料來代替訊息的片段，來避免重複傳送多餘的訊息；並讓通訊更加可靠。根據實驗模擬的結果，我們的機制有較好的效能，特別是在頻寬的使用上。 zh_TW dc.description.abstract (摘要) The routing protocols of delay tolerant networks could be divided in two categories: flooding-based protocols and forwarding-based protocols. Network coding is an encoding technique that could make data transmission more reliable. It operates without the needed of information about the network topology. We proposed a routing protocol integrating the characteristic of flooding-based protocol and forwarding-based protocol. The main idea of our protocol is to let message would not be flooded to every node but to the nodes moving toward or moving closer to destination. When nodes contact with each other, our approach will use the path of node, node’s moving direction and its velocity to estimate the probability to reach the destination of message. At the same time, we exploit network coding to transmit coded block instead of message fragment in order to avoid sending redundant replication, make data transmit more reliable and more robust to packet losses or delays. From the result of simulation, we could see that our protocol have a higher performance especially in the bandwidth consumption compared to other protocols. en_US dc.description.tableofcontents CHAPTER 1 Introduction 11.1 Background 11.1.1 DTNs Routing Protocols 11.1.2 Network Coding 21.2 Motivation 31.3 Organization 4CHAPTER 2 Related Work 52.1 Flooding-based routing protocol 62.1.1 Direct Contact 62.1.2 Two-Hop Relay 62.1.3 Tree-based Flooding 72.1.4 Epidemic Routing 72.2 Forwarding-based routing protocol 82.2.1 Location-based Routing 82.2.2 Gradient Routing 82.2.3 Link Metrics 92.3 Flooding-based protocol vs. Forwarding-based protocol 92.4 Random Linear Network Coding 102.5 Network Coding on DTNs 11CHAPTER 3 The LANC Protocol 133.1 System Model 143.2 Delivery Probability Estimation 143.2.1 Algorithm Path(c) 153.2.2 Algorithm Dir(c) 173.2.3 Algorithm V(c) 183.3 Location-assisted routing with network coding 193.3.1 Initialization 193.3.2 Probability Estimation 203.3.3 Coding Operation 213.3.4 Scheduling 223.3.5 Termination 24CHAPTER 4 Simulation and Results 264.1 Performance Evaluation 264.2 Simulation Setup 274.3 Simulation Results 294.3.1 Single Flow 294.3.2 Two Flows 314.3.3 Multiple flows 34CHAPTER 5 Conclusion and Future Work 38 zh_TW dc.format.extent 747907 bytes - dc.format.mimetype application/pdf - dc.language.iso en_US - dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0097753003 en_US dc.subject (關鍵詞) 耐延遲網路 zh_TW dc.subject (關鍵詞) 路由協定 zh_TW dc.subject (關鍵詞) 網路編碼 zh_TW dc.subject (關鍵詞) Delay tolerant network en_US dc.subject (關鍵詞) routing en_US dc.subject (關鍵詞) network coding en_US dc.title (題名) 耐延遲車載網路上利用網路編碼之位置輔助路由 zh_TW dc.title (題名) Location assisted routing with network coding in vehicular delay tolerant networks en_US dc.type (資料類型) thesis en dc.relation.reference (參考文獻) [1] Jian Shen, Sangman Moh, and Ilyong Chung, “Routing Protocols in Delay Tolerant Networks: A Comparative Survey” in International Technical Conference on Circuits/Systems, Computers and Communications (ITC-CSCC’ 08), July 2008[2] R. Ahlswede, N. Cai, S.-Y. R. Li, and R.W. Yeung, “Network information flow,” IEEE Trans. on Information Theory, vol. 46, no. 4, July 2000.[3] T. Ho, R. Koetter, M. Medard, D. R. Karger, and M.Effros. “The benefits of coding over routing in a randomized setting”International Symposium on Information Theory (ISIT), page 442, July 2003[4] P. A. Chou, Y. Wu, and K. Jain. Practical network coding. In Proc. Allerton, Oct. 2003.[5] R. H. Frenkiel, B. R. Badrinath, J. Borres, and R. D. Yates, “The infostations challenge: balancing cost and ubiquity in delivering wireless data,” IEEE Personal Communications, vol. 7, no. 2, pp. 66–71, 2000[6] D. Nain, N. Petigara, and H. Balakrishnan,“Integrated routing and storage for messaging applications in mobile ad hoc networks,” Mobile Networks and Applications (MONET), vol. 9, pp. 595–604, December 2004.[7] T. Spyropoulos, K. Psounis, and C. S. Raghavendra,“Spray and wait: an efficient routing scheme for intermittently connected mobile networks,” in Proceedings of the ACM SIGCOMM Workshop on Delay-Tolerant Networking (WDTN’05), pp. 252–259, August 2005.[8] A. Demers, D. Greene, C. Houser, W. Irish, J. Larson, S. Shenker, H. Sturgis, D. Swinehart, and D. Terry,“Epidemic algorithms for replicated database maintenance,” SIGOPS Operating Systems Review, vol. 22, pp. 8–32, January 1988.[9] A. Vahdat and D. Becker, “Epidemic routing for partially-connected ad hoc networks,” Tech. Rep. CS-2000-06, Duke University, July 2000.[10] J. Lebrun, C.-N. Chuah, D. Ghosal, and M. Zhang,“Knowledge-based opportunistic forwarding in vehicular wireless ad hoc networks,” in Proceedings ofIEEE Vehicular Technology Conference (VTC), vol. 4, pp. 2289–2293, May 2005.[11] P. Juang, H. Oki, Y. Wang, M. Martonosi, L. S. Peh, and D. Rubenstein, “Energy-efficient computing for wildlife tracking: design tradeoff’s and early experiences with zebranet,” in Proceedings of ASPLOS-X, pp. 96–107, October 2002.[12] A. Lindgren, A. Doria, and O. Schel´en, “Probabilistic routing in intermittently connected networks,” Lecture Notes in Computer Science, vol. 3126, pp. 239–254, January 2004.[13] S. Jain, K. Fall, and R. Patra, “Routing in a delay tolerant network,” in Proceedings of ACM SIGCOMM, vol. 34, pp. 145–158, ACM Press, October 2004.[14] C. Gkantsidis and P. Rodriguez. Network coding for large scale content distribution. In Infocom, Miami,FL, Mar. 2005. [15] C. Gkantsidis, J. Miller and P. Rodrques. Comprehensive view of a live network coding P2P system[16] S. Katti, H. Rahul, D. Katabi, W. Hu M. M´edard, and J. Crowcroft. XORs in the Air:Practical Wireless Network Coding. In SIGCOMM, 2006.[17] U. Lee, J.-S. Park, J. Yeh, G. Pau, and M. Gerla. “CodeTorrent: Content Distribution using Network Coding in VANETs. “ in MobiShare’06, Los Angeles, CA, Sept. 2006.[18] S. Ahmed and S. S. Kanhere, “VANETCODE: Network coding to enhance cooperative downloading in vehicular ad-hoc networks,” in Proc. ACM Int. Conf. on Commun. And Mobile Comput., 2006, pp. 527–532.[19] J. Widmer and J.-Y. LeBoudec. “Network coding for efficient communication in extreme networks. “ in WDTN, Aug. 2005.[20] X. Zhang, G. Neglia, J. Kurose, D. Towsley. “On the Benefits of Random Linear Coding for Unicast Applications in Disruption Tolerant Networks. “ in Second Workshop on Network Coding, Theory, and Applications. 2006[21] A. Keränen, J. Ott, and T. Kärkkäinen, "The ONE Simulator for DTN Protocol Evaluation," in SIMUTools`09: 2nd International Conference on Simulation Tools and Techniques, Rome, March 2-6, 2009. zh_TW dc.identifier.doi (DOI) 10.1109/ICCChina.2012.6356967 en_US dc.doi.uri (DOI) http://dx.doi.org/10.1109/ICCChina.2012.6356967 en_US
