學術產出-Theses
Article View/Open
Publication Export
-
題名 在耐延遲網路中依人氣與接觸關聯為基礎之訊息散播與優先排程之轉發機制
Popularity spray and utility-based forwarding scheme with message priority scheduling in delay tolerant networks作者 陳英明
Chen, Ying Ming貢獻者 蔡子傑
Tsai, Tzu Chieh
陳英明
Chen, Ying Ming關鍵詞 耐延遲網路
路由協定
優先權
優先排程
接觸關聯性
Delay Tolerant Networks
Routing
Priority
Scheduling
Contact association日期 2012 上傳時間 1-Mar-2013 09:25:53 (UTC+8) 摘要 在耐延遲網路環境下，訊息資料的傳送依賴於節點間因移動性而產生的間斷性連結，並使用「儲存並攜帶再轉送」的方式傳遞至其目的地，因此網路中各個節點的儲存空間以及與其他節點的「接觸關連性」將扮演訊息傳遞品質的重要因素。 本論文提出一以Flooding-based與Forwarding-based兩類路由協定為基礎設計結構、並加以擴充考量訊息優先權於轉發機制之三階段式路由演算法。其主要概念在於利用網路中節點的移動特性來週期性地預測節點與節點間未來的相遇人氣做為訊息散播時的分配權重、及以累計相遇時間之比率為接觸關聯性做為訊息是否進一步轉送之依據、最後並在訊息傳送順序上加入優先權排序的策略。根據與其他路由演算法的模擬實驗，顯示我們所提的演算法能有較高的訊息傳遞成功率、相對低的資源耗費、以及差異化訊息傳送服務的效能。
Delay Tolerant Networks (DTNs) use the “Store-Carry-and-Forward” approach to deliver the messages to the destinations. It relies on the intermittent link that occurs when two nodes contact each other due to mobility. Therefore, the buffer and “contact association” of nodes are two important factors that affect the delivery performance. In this thesis, we propose a three-phase algorithm (SFMS: Spray and Forwarding scheme with Message Scheduling) that integrates the concepts of flooding-based and forwarding-based protocols, and considers message priority. The main idea of SFMS is to periodically predict the contact popularity and contact association among nodes, such that we can determine the fast message spraying and efficient forwarding strategy. Furthermore, we come up with a message scheduling mechanism to enhance the resource allocation. Simulation results show that our scheme has a better performance for delivering messages. Besides, it also achieves a differential delivery performance for different priorities of messages while maintaining a better resource allocation.參考文獻 [1] J. Shen, S. Moh, I. Chung, “Routing Protocols in Delay Tolerant Networks: A Comparative Survey,” In ITC-CSCC, Chosun University, Korea, July 2008.[2] E.P.C. Jones, P.A.S. Ward, “Routing Strategies for Delay-Tolerant Networks,” Submitted to Computer Communication Review, University of Waterloo, Canada, 2008[3] R.H. Frenkiel, B.R. Badrinath, J. Borras, R.D. Yates, “The Infostations Challenge: Balancing Cost and Ubiquity in Delivering Wireless Data,” In IEEE Personal Communications, vol. 7, no. 2, pp. 66-71, April 2000.[4] L. Pelusi, A. Passarella, M. Conti, IIT-CNR, “Opportunistic Networking: Data Forwarding in Disconnected mobile ad hoc networks,” In IEEE Communications Magazine, Vol. 44, no. 11, pp. 134-141, November 2006.[5] A. Vahdat and D. Becher, “Epidemic Routing for Partially-Connected Ad Hoc networks,” In Technical Report CS-2000-06, Duke University, July 2000.[6] 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,” In SIGOPS Operating Systems Review, vol. 22, pp. 8-32, January 1988.[7] T. Spyropoulos, K. Psounis, C.S. Raqhavendra, “Spray and Wait: An Efficient Routing Scheme for Intermittently Connected Mobile Networks,” In Proc. SIGCOMM, EE, USC, USA, August 2005.[8] A. Lindgren, A. Doria, and O. Schel’en, “Probabilistic Routing in Intermittently Connected Networks,” In Proc. SIGMOBILE, vol. 7-3, LUT, Sweden, July 2003.[9] J. LeBrun, C.N. Chuah, D. Ghosal, M. Zhang, “Knowledge-Based Opportunistic Forwarding in Vehicular Wireless Ad Hoc Networks,” In Proceedings of IEEE Vehicular Technology Conference (VTC), vol. 4, pp. 2289-2293, University of California, Davis, USA, May 2005.[10] T. Umedu, H. Urabe, J. Tsukamoto, K. Sato, T. Higashino, “A MANET Protocol for Information Gathering from Disaster Victims,” In PERCOMW, Osaka University, Japan, March 2006.[11] X. Pallot, L.E. Miller, “IMPLEMENTING MESSAGE PRIORITY POLICIES OVER AN 802.11 BASED MOBILE AD HOC NETWORK,” In MILCOM, NIST, USA, 2001.[12] C. Suthaputchakun, A. Ganz, “Military Inter-Vehicle Communication with Message Priority using IEEE 802.11e,” In MILCOM, University of Massachusetts Amherst, USA, October 2006.[13] H. Gong, J.W. Kim, “A Prioritization-Based Application-Oriented Broadcast Protocol for Delay-Tolerant Networks,” In WCNC, GIST, Korea, 2009.[14] Z. Li, H. Shen, “Utility-based Distributed Routing in Intermittently Connected Networks,” In ICPP, University of Arkansas, USA, September 2008.[15] Z. Li, H. Shen, “SEDUM: Exploiting Social Networks in Utility-Based Distributed Routing for DTNs,” In IEEE Transactions on Computers, Vol. 62, no 1, pp. 83-97, Clemson University, USA, January 2013.[16] H. Dubois-Ferriere, M. Grossglauser, M. Vetterli, “Age Matters: Efficient Route Discovery in Mobile Ad Hoc Networks Using Encounter Ages,” In MobiHoc, EPFL, Switzerland, June 2003.[17] I. Joe, K. Sang-Bo, “A Message Priority Routing Protocol for Delay Tolerant Networks (DTN) in Disaster Areas,” In FGIT, Hanyang University, Korea, December 2010.[18] R. Ramanathan, R. Hansen, P. Basu, R. Rosales-Hain, R. Krishnan, “Prioritized Epidemic Routing for Opportunistic Networks,” In MobiOpp, BBN Technologies, USA, June 2007.[19] Z. Li, L. Sun, E.C. Ifeachor, “Adaptive Multi-Copy Routing for Intermittently Connected Mobile Ad Hoc Networks,” In GLOBECOM, University of Plymouth, UK, December 2006.[20] T. Spyropoulos, K. Psounis, C.S. Raghavendra, “Spray and Focus: Efficient Mobility-Assisted Routing for Heterogeneous and Correlated Mobility,” In PerCom, March 2007.[21] A. Keranen, J. Ott, T. Karkkainen, “The ONE Simulator for DTN Protocol Evaluation,” In SIMUTools, Helsinki University, Finland, March 2009.[22] Haris, Abdullah, “A DTN Study: Analysis of Implementations and Tools,” In IMM-MSC-2010-65, Technical University of Denmark, Denmark, 2010.[23] M. McNett, G.M. Voelker, “Acm Mobile Computing and Communication Review,” In Access and mobility of wireless pda users, 2007.[24] Nielsen, http://www.nielsen.com/us/en.html.[25] eMarketer, http://www.emarketer.com/. 描述 碩士
國立政治大學
資訊科學學系
99753008
101資料來源 http://thesis.lib.nccu.edu.tw/record/#G0099753008 資料類型 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, Ying Ming en_US dc.creator (作者) 陳英明 zh_TW dc.creator (作者) Chen, Ying Ming en_US dc.date (日期) 2012 en_US dc.date.accessioned 1-Mar-2013 09:25:53 (UTC+8) - dc.date.available 1-Mar-2013 09:25:53 (UTC+8) - dc.date.issued (上傳時間) 1-Mar-2013 09:25:53 (UTC+8) - dc.identifier (Other Identifiers) G0099753008 en_US dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/57063 - dc.description (描述) 碩士 zh_TW dc.description (描述) 國立政治大學 zh_TW dc.description (描述) 資訊科學學系 zh_TW dc.description (描述) 99753008 zh_TW dc.description (描述) 101 zh_TW dc.description.abstract (摘要) 在耐延遲網路環境下，訊息資料的傳送依賴於節點間因移動性而產生的間斷性連結，並使用「儲存並攜帶再轉送」的方式傳遞至其目的地，因此網路中各個節點的儲存空間以及與其他節點的「接觸關連性」將扮演訊息傳遞品質的重要因素。 本論文提出一以Flooding-based與Forwarding-based兩類路由協定為基礎設計結構、並加以擴充考量訊息優先權於轉發機制之三階段式路由演算法。其主要概念在於利用網路中節點的移動特性來週期性地預測節點與節點間未來的相遇人氣做為訊息散播時的分配權重、及以累計相遇時間之比率為接觸關聯性做為訊息是否進一步轉送之依據、最後並在訊息傳送順序上加入優先權排序的策略。根據與其他路由演算法的模擬實驗，顯示我們所提的演算法能有較高的訊息傳遞成功率、相對低的資源耗費、以及差異化訊息傳送服務的效能。 zh_TW dc.description.abstract (摘要) Delay Tolerant Networks (DTNs) use the “Store-Carry-and-Forward” approach to deliver the messages to the destinations. It relies on the intermittent link that occurs when two nodes contact each other due to mobility. Therefore, the buffer and “contact association” of nodes are two important factors that affect the delivery performance. In this thesis, we propose a three-phase algorithm (SFMS: Spray and Forwarding scheme with Message Scheduling) that integrates the concepts of flooding-based and forwarding-based protocols, and considers message priority. The main idea of SFMS is to periodically predict the contact popularity and contact association among nodes, such that we can determine the fast message spraying and efficient forwarding strategy. Furthermore, we come up with a message scheduling mechanism to enhance the resource allocation. Simulation results show that our scheme has a better performance for delivering messages. Besides, it also achieves a differential delivery performance for different priorities of messages while maintaining a better resource allocation. en_US dc.description.tableofcontents CHAPTER 1 Introduction 11.1 Background 11.2 Motivation 21.3 Our Goal 51.4 Organization 5CHAPTER 2 Related Work 62.1 Flooding-based Routing Protocol 72.1.1 Direct Delivery Routing Protocol 72.1.2 Epidemic Routing Protocol 72.1.3 Spray and Wait Routing Protocol 82.2 Forwarding-based Routing Protocol 82.2.1 Gradient Routing Protocol 82.2.2 Location-based Routing Protocol 92.3 Main Schemes for Our Design Concepts 92.3.1 A Message Priority Routing Protocol for Delay Tolerant Networks (DTN) in Disaster Areas [17] 92.3.2 Utility-based Distributed Routing in Intermittently Connected Networks [14] 122.3.3 IMPLEMENTING MESSAGE PRIORITY POLICIES OVER AN 802.11 BASED MOBILE AD HOC NETWORK [11] 13CHAPTER 3 Spray and Forwarding scheme with Message Scheduling 153.1 Popularity Spray Phase 153.2 Utility-based Forwarding Phase 193.3 Message Forwarding with Priority Scheduling Phase 233.4 Buffer Management Strategy 26CHAPTER 4 Simulation and Results 294.1 Performance Metrics 294.2 Simulation Setup 304.2.1 Simulation Settings 314.3 Simulation Results 324.3.1 Performance of Different Buffer Sizes 324.3.2 Performance of Different Node Densities 40CHAPTER 5 Conclusions and Future Work 45REFERENCES 46 zh_TW dc.language.iso en_US - dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0099753008 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 Networks en_US dc.subject (關鍵詞) Routing en_US dc.subject (關鍵詞) Priority en_US dc.subject (關鍵詞) Scheduling en_US dc.subject (關鍵詞) Contact association en_US dc.title (題名) 在耐延遲網路中依人氣與接觸關聯為基礎之訊息散播與優先排程之轉發機制 zh_TW dc.title (題名) Popularity spray and utility-based forwarding scheme with message priority scheduling in delay tolerant networks en_US dc.type (資料類型) thesis en dc.relation.reference (參考文獻) [1] J. Shen, S. Moh, I. Chung, “Routing Protocols in Delay Tolerant Networks: A Comparative Survey,” In ITC-CSCC, Chosun University, Korea, July 2008.[2] E.P.C. Jones, P.A.S. Ward, “Routing Strategies for Delay-Tolerant Networks,” Submitted to Computer Communication Review, University of Waterloo, Canada, 2008[3] R.H. Frenkiel, B.R. Badrinath, J. Borras, R.D. Yates, “The Infostations Challenge: Balancing Cost and Ubiquity in Delivering Wireless Data,” In IEEE Personal Communications, vol. 7, no. 2, pp. 66-71, April 2000.[4] L. Pelusi, A. Passarella, M. Conti, IIT-CNR, “Opportunistic Networking: Data Forwarding in Disconnected mobile ad hoc networks,” In IEEE Communications Magazine, Vol. 44, no. 11, pp. 134-141, November 2006.[5] A. Vahdat and D. Becher, “Epidemic Routing for Partially-Connected Ad Hoc networks,” In Technical Report CS-2000-06, Duke University, July 2000.[6] 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,” In SIGOPS Operating Systems Review, vol. 22, pp. 8-32, January 1988.[7] T. Spyropoulos, K. Psounis, C.S. Raqhavendra, “Spray and Wait: An Efficient Routing Scheme for Intermittently Connected Mobile Networks,” In Proc. SIGCOMM, EE, USC, USA, August 2005.[8] A. Lindgren, A. Doria, and O. Schel’en, “Probabilistic Routing in Intermittently Connected Networks,” In Proc. SIGMOBILE, vol. 7-3, LUT, Sweden, July 2003.[9] J. LeBrun, C.N. Chuah, D. Ghosal, M. Zhang, “Knowledge-Based Opportunistic Forwarding in Vehicular Wireless Ad Hoc Networks,” In Proceedings of IEEE Vehicular Technology Conference (VTC), vol. 4, pp. 2289-2293, University of California, Davis, USA, May 2005.[10] T. Umedu, H. Urabe, J. Tsukamoto, K. Sato, T. Higashino, “A MANET Protocol for Information Gathering from Disaster Victims,” In PERCOMW, Osaka University, Japan, March 2006.[11] X. Pallot, L.E. Miller, “IMPLEMENTING MESSAGE PRIORITY POLICIES OVER AN 802.11 BASED MOBILE AD HOC NETWORK,” In MILCOM, NIST, USA, 2001.[12] C. Suthaputchakun, A. Ganz, “Military Inter-Vehicle Communication with Message Priority using IEEE 802.11e,” In MILCOM, University of Massachusetts Amherst, USA, October 2006.[13] H. Gong, J.W. Kim, “A Prioritization-Based Application-Oriented Broadcast Protocol for Delay-Tolerant Networks,” In WCNC, GIST, Korea, 2009.[14] Z. Li, H. Shen, “Utility-based Distributed Routing in Intermittently Connected Networks,” In ICPP, University of Arkansas, USA, September 2008.[15] Z. Li, H. Shen, “SEDUM: Exploiting Social Networks in Utility-Based Distributed Routing for DTNs,” In IEEE Transactions on Computers, Vol. 62, no 1, pp. 83-97, Clemson University, USA, January 2013.[16] H. Dubois-Ferriere, M. Grossglauser, M. Vetterli, “Age Matters: Efficient Route Discovery in Mobile Ad Hoc Networks Using Encounter Ages,” In MobiHoc, EPFL, Switzerland, June 2003.[17] I. Joe, K. Sang-Bo, “A Message Priority Routing Protocol for Delay Tolerant Networks (DTN) in Disaster Areas,” In FGIT, Hanyang University, Korea, December 2010.[18] R. Ramanathan, R. Hansen, P. Basu, R. Rosales-Hain, R. Krishnan, “Prioritized Epidemic Routing for Opportunistic Networks,” In MobiOpp, BBN Technologies, USA, June 2007.[19] Z. Li, L. Sun, E.C. Ifeachor, “Adaptive Multi-Copy Routing for Intermittently Connected Mobile Ad Hoc Networks,” In GLOBECOM, University of Plymouth, UK, December 2006.[20] T. Spyropoulos, K. Psounis, C.S. Raghavendra, “Spray and Focus: Efficient Mobility-Assisted Routing for Heterogeneous and Correlated Mobility,” In PerCom, March 2007.[21] A. Keranen, J. Ott, T. Karkkainen, “The ONE Simulator for DTN Protocol Evaluation,” In SIMUTools, Helsinki University, Finland, March 2009.[22] Haris, Abdullah, “A DTN Study: Analysis of Implementations and Tools,” In IMM-MSC-2010-65, Technical University of Denmark, Denmark, 2010.[23] M. McNett, G.M. Voelker, “Acm Mobile Computing and Communication Review,” In Access and mobility of wireless pda users, 2007.[24] Nielsen, http://www.nielsen.com/us/en.html.[25] eMarketer, http://www.emarketer.com/. zh_TW
