學術產出-Theses
Article View/Open
Publication Export
-
題名 混合階層式路由於公車基底之耐延遲網路
A hybrid hierarchy routing in bus-based delay tolerant networks作者 陳志宏
Chen, Chih Hung貢獻者 蔡子傑
Tsai, Tzu-Chieh
陳志宏
Chen, Chih Hung關鍵詞 耐延遲網路
混合階層式
市區
公車基底
路由協定
Delay Tolerant Network
hybrid hierarchy
urban areas
bus-based
routing protocol日期 2010 上傳時間 4-Sep-2013 17:10:14 (UTC+8) 摘要 在耐延遲網路(Delay Tolerant Network)中，因為節點具有移動性，因此找不到穩定且持續的點對點資料傳送路徑。常見的路由協定可分為機會路由、基於預測的路由以及調度路由，然而這些路由協定使用在市區環境中，有著些許不足與不適用，因此本論文提出一個適用在市區資料傳送的演算法。本論文提出之混合階層式路由演算法，是在市區環境中建立一個以公車為基礎的資料傳送架構，包含行人與公車兩種節點。我們建立節點與節點相遇時資料交換傳送規則，例如行人與行人相遇、行人與公車相遇或是公車與公車相遇時各自有不同的資料傳送判斷與限制。實驗結果也證明所提出之混合階層式演算法，除了可以有效地減少傳送延遲時間並提高訊息傳送成功率，並且在給定節點一定的移動速度與緩衝區大小下，我們的演算法有著最突出的效能。
In Delay Tolerant Networks (DTNs), there is no guarantee that a stable connected path between source and destination nodes always exists because of high node mobility. The current DTN routing protocols can be summarized into three categories: opportunistic, prediction-based and scheduling protocols. However, these routing protocols have some deficiencies and are not specifically focused on the urban areas which have primarily two hierarchical nodes, namely pedestrian and bus nodes.We proposed a Hybrid Hierarchy Routing Protocol, a bus-based architecture for urban areas. We established the rules of data transmission when one node contacts other nodes. More specifically, Ped-to-Ped, Ped-to-Bus and Bus-to-Bus contacts, have different judgments and restrictions for data forwarding.The simulation results demonstrate that the Hybrid Hierarchy Routing Protocol can effectively reduce the delivery delay and improve the successful delivery rate. And in given certain speed and buffer sizes, our algorithm has the most prominent performance.參考文獻 [1] Shaoge Yan, Yanbin Qian, Daowen Hua, and Xuehui Du, “A DTN Routing Protocol base on Hierarchy Forwarding and Control Cluster,” Computational Intelligence and Security, International Conference, pp. 397-401, December 2009.[2] P. Jacquet, B. Mans, and G. Rodolakis, “Information Propagation Speed in Mobile and Delay Tolerant Networks,” Information Theory, IEEE Transactions , vol. 56, pp. 5001-5015, Oct. 2010.[3] Mooi Choo Chuah and Wen-Bin Ma, “Integrated Buffer and Route Management in a DTN with Message Ferry,” Military Communications Conference, pp. 1-7, October 2006.[4] Alan Demers, Carl Hauser, Dan Greene, John Larson, and Wes Irish, “Epidemic algorithms for replicated database maintenance,” Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, pp. 1-12, August 1987.[5] Vahdat A and Becker D, “Epidemic routing for partially connected ad hoc networks,” Technical report, Duke University, 2000.[6] Cauligi S. Raghavendra, Konstantinos Psounis, and Thrasyvoulos Spyropoulos, “Spray and wait: an efficient routing scheme for intermittently connected mobile networks,” Proceeding of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, pp. 252–259, August 2005.[7] Spyropoulos T, Psounis K, and Raghavendra CS, “Spray and focus: efficient mobility-assisted routing for heterogeneous and correlated mobility,” In: PERCOMW ’07. Washington, DC, USA, pp. 79–85, 2007.[8] R.H. Frenkiel, B.R. Badrinath, J. Borres, and R.D. Yates, “The infostations challenge: Balancing cost and ubiquity in delivering wireless data,” Personal Communications, IEEE, vol. 7, pp. 66-71, Apr 2000.[9] J. LeBrun, Chen-Nee Chuah, and M. Zhang, “Knowledge-based opportunistic forwarding in vehicular wireless ad hoc networks,” Vehicular Technology Conference, Vol. 4, pp. 2289-2293, June 2005.[10] M. Mauve, A. Widmer, and H. Hartenstein, “A Survey on Position-Based Routing in Mobile Ad Hoc Networks,” Network, IEEE, vol. 15, pp. 30-39, Nov/Dec 2001.[11] Silvia Giordano, Alessandro Puiatti, and Hoang Anh Nguyen, “Probabilistic routing in intermittently connected networks,” A World of Wireless, Mobile and Multimedia Networks, International Symposium, pp. 1-6, June 2007. [12] Etienne C. R. de Oliveira and Célio V. N. de Albuquerque, “NECTAR: A DTN Routing Protocol Based on Neighborhood Contact History,” Proceedings of the 2009 ACM symposium on Applied Computing, 2009. [13] Daniel Rubenstein, Hidekazu Oki, Li Shiuan Peh, Margaret Martonosi, Philo Juang, and Yong Wang, “Energy-efficient computing for wildlife tracking: design tradeoffs and early experiences with ZebraNet,” Tenth international conference on architectural support for programming languages and operating systems on Proceedings of the 10th international conference on architectural support for programming languages and operating systems (ASPLOS-X) (ASPLOS `02) , pp. 205-209, October 2002.[14] J. Han, P. Yang, and M. Chuah, “A message ferrying approach for data delivery in sparse mobile ad hoc networks,” Mobile and Ubiquitous Systems, Annual International Conference, pp. 1-8, August 2007.[15] Elizabeth M. Daly and Mads Haahr, “Social Network Analysis for Routing in Disconnected Delay-Tolerant MANETs,” IEEE Transactions on Mobile Computing, pp. 606-621, May 2009.[16] Elizabeth M. Daly and Mads Haahr, “Social Network Analysis for Information Flow in Disconnected Delay-Tolerant MANETs,” IEEE Transactions on Mobile Computing, pp. 606-621, May 2009.[17] Small Dynamic World：http://en.wikipedia.org/wiki/Six_degrees_of_separation 描述 碩士
國立政治大學
資訊科學學系
98971013
99資料來源 http://thesis.lib.nccu.edu.tw/record/#G0098971013 資料類型 thesis dc.contributor.advisor 蔡子傑 zh_TW dc.contributor.advisor Tsai, Tzu-Chieh en_US dc.contributor.author (Authors) 陳志宏 zh_TW dc.contributor.author (Authors) Chen, Chih Hung en_US dc.creator (作者) 陳志宏 zh_TW dc.creator (作者) Chen, Chih Hung en_US dc.date (日期) 2010 en_US dc.date.accessioned 4-Sep-2013 17:10:14 (UTC+8) - dc.date.available 4-Sep-2013 17:10:14 (UTC+8) - dc.date.issued (上傳時間) 4-Sep-2013 17:10:14 (UTC+8) - dc.identifier (Other Identifiers) G0098971013 en_US dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/60261 - dc.description (描述) 碩士 zh_TW dc.description (描述) 國立政治大學 zh_TW dc.description (描述) 資訊科學學系 zh_TW dc.description (描述) 98971013 zh_TW dc.description (描述) 99 zh_TW dc.description.abstract (摘要) 在耐延遲網路(Delay Tolerant Network)中，因為節點具有移動性，因此找不到穩定且持續的點對點資料傳送路徑。常見的路由協定可分為機會路由、基於預測的路由以及調度路由，然而這些路由協定使用在市區環境中，有著些許不足與不適用，因此本論文提出一個適用在市區資料傳送的演算法。本論文提出之混合階層式路由演算法，是在市區環境中建立一個以公車為基礎的資料傳送架構，包含行人與公車兩種節點。我們建立節點與節點相遇時資料交換傳送規則，例如行人與行人相遇、行人與公車相遇或是公車與公車相遇時各自有不同的資料傳送判斷與限制。實驗結果也證明所提出之混合階層式演算法，除了可以有效地減少傳送延遲時間並提高訊息傳送成功率，並且在給定節點一定的移動速度與緩衝區大小下，我們的演算法有著最突出的效能。 zh_TW dc.description.abstract (摘要) In Delay Tolerant Networks (DTNs), there is no guarantee that a stable connected path between source and destination nodes always exists because of high node mobility. The current DTN routing protocols can be summarized into three categories: opportunistic, prediction-based and scheduling protocols. However, these routing protocols have some deficiencies and are not specifically focused on the urban areas which have primarily two hierarchical nodes, namely pedestrian and bus nodes.We proposed a Hybrid Hierarchy Routing Protocol, a bus-based architecture for urban areas. We established the rules of data transmission when one node contacts other nodes. More specifically, Ped-to-Ped, Ped-to-Bus and Bus-to-Bus contacts, have different judgments and restrictions for data forwarding.The simulation results demonstrate that the Hybrid Hierarchy Routing Protocol can effectively reduce the delivery delay and improve the successful delivery rate. And in given certain speed and buffer sizes, our algorithm has the most prominent performance. en_US dc.description.tableofcontents 第一章 緒論 11.1 簡介 11.2 研究動機 31.3 研究目的 31.4 章節提要 4第二章 相關研究 52.1 Opportunistic Protocol 52.1.1 Epidemic Routing Protocol 52.1.2 Spray Routing Protocol 62.1.3 Direct Contact Routing Protocol 62.2 Prediction-based Protocol 62.2.1 Location-based Routing Protocol 62.2.2 Prophet Routing Protocol 72.3 Scheduling Protocol 72.3.1 MF Routing Protocol 7第三章 研究方法與系統架構 93.1 研究方法 93.2 系統架構 93.3 簡單階層式路由演算法 113.3.1 行人相遇行人 113.3.2 行人相遇公車 133.3.3 公車相遇公車 143.3.4 公車相遇行人 153.4 混合階層式路由演算法 173.4.1 公車相遇公車 173.4.2 公車相遇行人 193.4.3 行人相遇行人 21第四章 模擬實驗與結果分析 254.1 效能評估 254.2 模擬設定 264.2.1 公車路線設定 264.2.2 參數設定 274.2.3 系統畫面 284.3 實驗結果 294.3.1 初始模擬結果 294.3.2 行人節點密度 314.3.3 公車節點密度 334.3.4 公車移動速度 364.3.5 節點緩衝區大小 38第五章 結論與未來展望 405.1 結論 405.2 未來展望 41參考文獻 42 zh_TW dc.format.extent 1739762 bytes - dc.format.mimetype application/pdf - dc.language.iso en_US - dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0098971013 en_US dc.subject (關鍵詞) 耐延遲網路 zh_TW dc.subject (關鍵詞) 混合階層式 zh_TW dc.subject (關鍵詞) 市區 zh_TW dc.subject (關鍵詞) 公車基底 zh_TW dc.subject (關鍵詞) 路由協定 zh_TW dc.subject (關鍵詞) Delay Tolerant Network en_US dc.subject (關鍵詞) hybrid hierarchy en_US dc.subject (關鍵詞) urban areas en_US dc.subject (關鍵詞) bus-based en_US dc.subject (關鍵詞) routing protocol en_US dc.title (題名) 混合階層式路由於公車基底之耐延遲網路 zh_TW dc.title (題名) A hybrid hierarchy routing in bus-based delay tolerant networks en_US dc.type (資料類型) thesis en dc.relation.reference (參考文獻) [1] Shaoge Yan, Yanbin Qian, Daowen Hua, and Xuehui Du, “A DTN Routing Protocol base on Hierarchy Forwarding and Control Cluster,” Computational Intelligence and Security, International Conference, pp. 397-401, December 2009.[2] P. Jacquet, B. Mans, and G. Rodolakis, “Information Propagation Speed in Mobile and Delay Tolerant Networks,” Information Theory, IEEE Transactions , vol. 56, pp. 5001-5015, Oct. 2010.[3] Mooi Choo Chuah and Wen-Bin Ma, “Integrated Buffer and Route Management in a DTN with Message Ferry,” Military Communications Conference, pp. 1-7, October 2006.[4] Alan Demers, Carl Hauser, Dan Greene, John Larson, and Wes Irish, “Epidemic algorithms for replicated database maintenance,” Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, pp. 1-12, August 1987.[5] Vahdat A and Becker D, “Epidemic routing for partially connected ad hoc networks,” Technical report, Duke University, 2000.[6] Cauligi S. Raghavendra, Konstantinos Psounis, and Thrasyvoulos Spyropoulos, “Spray and wait: an efficient routing scheme for intermittently connected mobile networks,” Proceeding of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, pp. 252–259, August 2005.[7] Spyropoulos T, Psounis K, and Raghavendra CS, “Spray and focus: efficient mobility-assisted routing for heterogeneous and correlated mobility,” In: PERCOMW ’07. Washington, DC, USA, pp. 79–85, 2007.[8] R.H. Frenkiel, B.R. Badrinath, J. Borres, and R.D. Yates, “The infostations challenge: Balancing cost and ubiquity in delivering wireless data,” Personal Communications, IEEE, vol. 7, pp. 66-71, Apr 2000.[9] J. LeBrun, Chen-Nee Chuah, and M. Zhang, “Knowledge-based opportunistic forwarding in vehicular wireless ad hoc networks,” Vehicular Technology Conference, Vol. 4, pp. 2289-2293, June 2005.[10] M. Mauve, A. Widmer, and H. Hartenstein, “A Survey on Position-Based Routing in Mobile Ad Hoc Networks,” Network, IEEE, vol. 15, pp. 30-39, Nov/Dec 2001.[11] Silvia Giordano, Alessandro Puiatti, and Hoang Anh Nguyen, “Probabilistic routing in intermittently connected networks,” A World of Wireless, Mobile and Multimedia Networks, International Symposium, pp. 1-6, June 2007. [12] Etienne C. R. de Oliveira and Célio V. N. de Albuquerque, “NECTAR: A DTN Routing Protocol Based on Neighborhood Contact History,” Proceedings of the 2009 ACM symposium on Applied Computing, 2009. [13] Daniel Rubenstein, Hidekazu Oki, Li Shiuan Peh, Margaret Martonosi, Philo Juang, and Yong Wang, “Energy-efficient computing for wildlife tracking: design tradeoffs and early experiences with ZebraNet,” Tenth international conference on architectural support for programming languages and operating systems on Proceedings of the 10th international conference on architectural support for programming languages and operating systems (ASPLOS-X) (ASPLOS `02) , pp. 205-209, October 2002.[14] J. Han, P. Yang, and M. Chuah, “A message ferrying approach for data delivery in sparse mobile ad hoc networks,” Mobile and Ubiquitous Systems, Annual International Conference, pp. 1-8, August 2007.[15] Elizabeth M. Daly and Mads Haahr, “Social Network Analysis for Routing in Disconnected Delay-Tolerant MANETs,” IEEE Transactions on Mobile Computing, pp. 606-621, May 2009.[16] Elizabeth M. Daly and Mads Haahr, “Social Network Analysis for Information Flow in Disconnected Delay-Tolerant MANETs,” IEEE Transactions on Mobile Computing, pp. 606-621, May 2009.[17] Small Dynamic World：http://en.wikipedia.org/wiki/Six_degrees_of_separation zh_TW
