學術產出-Theses
Article View/Open
Publication Export
-
題名 用於混合式耐延遲網路之適地性服務資料搜尋方法
Location-based content search approach in hybrid delay tolerant networks作者 李欣諦
Lee, Hsin Ti貢獻者 蔡子傑
Tsai, Tzu Chieh
李欣諦
Lee, Hsin Ti關鍵詞 耐延遲網路
適地性服務
內容
查詢
路由協定
Delay Tolerant Networks
Location-based
Content
Query
Routing protocol日期 2011 上傳時間 30-Oct-2012 11:07:50 (UTC+8) 摘要 在耐延遲網路上，離線的使用者，可以透過節點的相遇，以點對點之特定訊息繞送方法，將資訊傳遞至目的地。如此解決了使用者暫時無法上網時欲傳遞資訊之困難。因此，在本研究中，當使用者在某一地區，欲查詢該地區相關之資訊，但又一時無法連上網際網路時，則可透過耐延遲網路之特性，尋求其它同樣使用本服務之使用者幫忙以達到查詢之目的。 本論文提出一適地性服務之資料搜尋方法，以三層式區域概念，及混合式節點型態，並透過資料訊息複製、查詢訊息複製、資料回覆及資料同步等四項策略來達成使用者查詢之目的。特別在訊息傳遞方面，提出一訊息佇列選擇演算法，賦予優先權概念於每一訊息中，使得較為重要之訊息得以優先傳送，藉此提高查詢之成功率及減少查詢之延遲時間。最後，我們將本論文方法與其它查詢方法比較評估效能，其模擬結果顯示我們提出的方法有較優的查詢效率與延遲。
In Delay Tolerant Networks (DTNs), the offline users can, through the encountering nodes, use the specific peer-to-peer message routing approach to deliver messages to the destination. Thus, it solves the problem that users have the demands to deliver messages while they are temporarily not able to connect to Internet. Therefore, by the characteristics of DTNs, people who are not online can still query some location based information, with the help of users using the same service in the nearby area. In this thesis, we proposed a Location-based content search approach. Based on the concept of three-tier area and hybrid node types, we presented four strategies to solve the query problem. They are Data Replication, Query Replication, Data Reply and Data synchronization strategies. Especially in message transferring, we proposed a Message Queue Selection algorithm. We set the priority concept to every message such that the most important one could be sent first. In this way, it can increase the query success ratio and reduce the query delay time. Finally, we evaluated our approach, and compared with other routing schemes. The simulation results showed that our proposed approach had better query efficiency and shorter delay.參考文獻 [1] V. Cerf, S. Burleigh, A. Hooke, L. Torgerson, R. Durst, K. Scott, K. Fall and H. Weiss, “Delay-Tolerant Networking Architecture”, RFC4838, April 2007, [Online]. Available: http://www.ietf.org/rfc/rfc4838.txt[2] K. Fall, “A Delay-Tolerant Network Architecture for Challenged Internets”, In Proc. SIGCOMM, August 2003.[3] A. Vahdat and D. Becker, “Epidemic routing for partially-connected ad hoc networks,” Tech. Rep. CS-2000-06, Duke University, July 2000.[4] T. Spyropoulos, K. Psounis, C.S. Raqhavendra, “Spray and wait: an efficient routing scheme for intermittently connected mobile networks”, EE, USC, USA, In Proc. SIGCOMM, August 2005.[5] T. Spyropoulos, K. Psounis, C.S. Raqhavendra, “Spray and Focus: Efficient Mobility-Assisted Routing for Heterogeneous and Correlated Mobility”, USC, EECS, USA, In Proc. PERCOM, March 2007.[6] A.Lindgren, A.Doria, and O. Schel’en, “Probabilistic Routing in Intermittently Connected Networks”, LUT, Sweden, In Proc. SIGMOBILE, vol. 7-3, July 2003.[7] D.K. Cho, C.W. Chang, M.H. Tsai, M. Gerla, “Networked medical monitoring in the battlefield”, CS, UCLA, USA, In Proc. MILCOM, November 2008.[8] C. Caini, P. Cornice, R. Firrincieli, D. Lacamera, S. Tamagnini, “A DTN Approach to Satellite Communications”, DEIS/ ARCES, University of Bologna, Italy, In Proc. IEEE Journal on Selected Areas in Communications, vol. 26-5, June 2008. [9] Y. Sasaki, Y. Shibata, “Distributed Disaster Information System in DTN Based Mobile Communication Environment”, Japan, In Proc. BWCCA, November 2010.[10] P. Jinag, J. Bigham, E. Bodanese, “Adaptive Service Provisioning for Emergency Communications with DTN”, EECS, Queen Mary University of London, UK, In Proc. WCNC, March 2011.[11] Nathanael Thompson, Riccardo Crepaldi and Robin Kravets, “Locus: A Location-based Data Overlay for Disruption-tolerant Networks”, CS, University of Illinois Urbana-Champaign, USA, In Proc. CHANTS, September 2010.[12] P. Yang, M.C. Chuah, “Performance evaluations of data-centric information retrieval schemes for DTNs”, CSE, Lehigh University, USA, In Proc. MILCOM, November 2008.[13] Cong Liu, Jie Wu, Xin Guan and Li Chen, “Cooperative File Sharing in Hybrid Delay Tolerant Networks”, In Proc. ICDCSW, June 2011.[14] Mikko Pitk¨anen, Teemu K¨arkk¨ainen, Janico Greifenberg, and J¨org Ott, “Searching for Content in Mobile DTNs”, Helsinki University of Technology, Finland, In Proc. PERCOM, March 2009.[15] S.C. Nelson, M. Bakht, R. Kravets, “Encounter–Based Routing in DTNs”, CS, University of Illinois at Urbana-Champaign, USA, In Proc. INFOCOM, April 2009.[16] E.C.R de Oliveria, C.V.N. de Albuquerque, “NECTAR: A DTN Routing Protocol Based on Neighborhood Contact History”, Universidade Federal Fluminense, Brasil, In Proc. SAC, March 2009[17] J. LeBrun, C.N. Chuah, D. Ghosal, M. Zhang, “Knowledge-Based Opportunistic Forwarding in Vehicular Wireless Ad Hoc Networks”, UC Davis, USA, In Proc. VTC, May 2005.[18] P. Hui, J. Crowcroft, E. Yoneki, “BUBBLE Rap: Social-based Forwarding in Delay Tolerant Networks”, University of Cambridge, UK, In Proc. MobiHoc, May 2008.[19] P. Juang, H. Oki, Y. Wang, M. Martonosi, L.S. Peh, D. Rubenstein, “Energy-Efficient Computing for Wildlife Tracking: Design Tradeoffs and Early Experiences with ZebraNet”, Princeton University, USA, In Proc. ASPLOS-X, October 2002.[20] G. Sollazzo, M. Musolesi, C. Mascolo, “TACO-DTN: a time-aware content-based dissemination system for delay tolerant networks”, CS, University College London, UK, In Proc. MobiOpp, June 2007.[21] S. Carrilho, G. Valadon, H. Esaki, “Hikari: DTN message distribute system”, The University of Tokyo, Japan, IPSJ SIG Technical Report, January 2009.[22] C.E. Palazzi, A. Bujari, “A Delay/Disruption Tolerant Solution for Mobile-to-Mobile File Sharing”, University of Padova, Italy, Wireless Day, In Proc. IFIP, October 2010.[23] B. Cohen, “Incentives Build Robustness in BitTorrent”, May 2003[24] “InMobi Mobile Market 2011 Review: Explosive Growth in Mobile, Tablet Impressions Increase 771%*”, InMobi, January 2012.Available: http://www.inmobi.com/press-releases/[25] “Steve Jobs Declares Post-PC Era”, InformationWeek, June 2010.Available: http://www.informationweek.com/news/software/productivity_apps/225300193[26] T. Vincenty, “Direct and Inverse Solutions of Geodesics on the Ellipsoid with application of nested equations”, Survey Review, Vol.23, 1975.[27] Ari Keränen, Jörg Ott, Teemu Kärkkäinen, “The ONE Simulator for DTN Protocol Evaluation”, In Proc. SimuTools, March 2009.[28] Sicai Lin, Tzu-Chieh Tsai, Shindi Lee, Sheng-Chih Chen, "Location-Based Mobile Collaborative Digital Narrative Platform", In Proc. The Third International Conference on Creative Content Technologies (CONTENT 2011), Sep 2011. 描述 碩士
國立政治大學
資訊科學學系
99753010
100資料來源 http://thesis.lib.nccu.edu.tw/record/#G0099753010 資料類型 thesis dc.contributor.advisor 蔡子傑 zh_TW dc.contributor.advisor Tsai, Tzu Chieh en_US dc.contributor.author (Authors) 李欣諦 zh_TW dc.contributor.author (Authors) Lee, Hsin Ti en_US dc.creator (作者) 李欣諦 zh_TW dc.creator (作者) Lee, Hsin Ti en_US dc.date (日期) 2011 en_US dc.date.accessioned 30-Oct-2012 11:07:50 (UTC+8) - dc.date.available 30-Oct-2012 11:07:50 (UTC+8) - dc.date.issued (上傳時間) 30-Oct-2012 11:07:50 (UTC+8) - dc.identifier (Other Identifiers) G0099753010 en_US dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/54464 - dc.description (描述) 碩士 zh_TW dc.description (描述) 國立政治大學 zh_TW dc.description (描述) 資訊科學學系 zh_TW dc.description (描述) 99753010 zh_TW dc.description (描述) 100 zh_TW dc.description.abstract (摘要) 在耐延遲網路上，離線的使用者，可以透過節點的相遇，以點對點之特定訊息繞送方法，將資訊傳遞至目的地。如此解決了使用者暫時無法上網時欲傳遞資訊之困難。因此，在本研究中，當使用者在某一地區，欲查詢該地區相關之資訊，但又一時無法連上網際網路時，則可透過耐延遲網路之特性，尋求其它同樣使用本服務之使用者幫忙以達到查詢之目的。 本論文提出一適地性服務之資料搜尋方法，以三層式區域概念，及混合式節點型態，並透過資料訊息複製、查詢訊息複製、資料回覆及資料同步等四項策略來達成使用者查詢之目的。特別在訊息傳遞方面，提出一訊息佇列選擇演算法，賦予優先權概念於每一訊息中，使得較為重要之訊息得以優先傳送，藉此提高查詢之成功率及減少查詢之延遲時間。最後，我們將本論文方法與其它查詢方法比較評估效能，其模擬結果顯示我們提出的方法有較優的查詢效率與延遲。 zh_TW dc.description.abstract (摘要) In Delay Tolerant Networks (DTNs), the offline users can, through the encountering nodes, use the specific peer-to-peer message routing approach to deliver messages to the destination. Thus, it solves the problem that users have the demands to deliver messages while they are temporarily not able to connect to Internet. Therefore, by the characteristics of DTNs, people who are not online can still query some location based information, with the help of users using the same service in the nearby area. In this thesis, we proposed a Location-based content search approach. Based on the concept of three-tier area and hybrid node types, we presented four strategies to solve the query problem. They are Data Replication, Query Replication, Data Reply and Data synchronization strategies. Especially in message transferring, we proposed a Message Queue Selection algorithm. We set the priority concept to every message such that the most important one could be sent first. In this way, it can increase the query success ratio and reduce the query delay time. Finally, we evaluated our approach, and compared with other routing schemes. The simulation results showed that our proposed approach had better query efficiency and shorter delay. en_US dc.description.tableofcontents CHAPTER 1 Introduction 11.1 Background 11.2 Motivation 21.3 Objective 31.3.1 Replication issues 41.3.2 Data Reply issue 41.3.3 Data Synchronize issue 51.4 Organization 5CHAPTER 2 Related Work 62.1 Common DTN routing protocol 62.1.1 Flooding-based routing schemes 62.1.2 Forwarding-based routing schemes 82.2 Query-based DTN routing protocol 82.2.1 Locus: A Location-based Data Overlay for Disruption-tolerant Networks [11] 92.2.2 Performance Evaluations of Data-centric Information Retrieval Schemes for DTNs [12] 102.2.3 Cooperative File Sharing in Hybrid Delay Tolerant Networks [13] 112.2.4 Searching for Content in Mobile DTNs [14] 12CHAPTER 3 Location-Based Content Search Approach 133.1 Data replication strategic 203.2 Query replication strategic 223.3 Data Reply strategic 253.4 Data synchronization and update strategic 283.5 Message queue selection algorithm 29CHAPTER 4 Simulation Results 314.1 Simulation Setup 324.2 Simulation Settings 334.3 Simulation Results 344.3.1 The percentage of node type 344.3.2 Radius of Inside Area 374.3.3 Node Density 394.3.4 Buffer Size 434.3.4 Time to Live 45CHAPTER 5 Conclusions and Future Work 48REFERENCE 49 zh_TW dc.language.iso en_US - dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0099753010 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 (關鍵詞) Location-based en_US dc.subject (關鍵詞) Content en_US dc.subject (關鍵詞) Query en_US dc.subject (關鍵詞) Routing protocol en_US dc.title (題名) 用於混合式耐延遲網路之適地性服務資料搜尋方法 zh_TW dc.title (題名) Location-based content search approach in hybrid delay tolerant networks en_US dc.type (資料類型) thesis en dc.relation.reference (參考文獻) [1] V. Cerf, S. Burleigh, A. Hooke, L. Torgerson, R. Durst, K. Scott, K. Fall and H. Weiss, “Delay-Tolerant Networking Architecture”, RFC4838, April 2007, [Online]. Available: http://www.ietf.org/rfc/rfc4838.txt[2] K. Fall, “A Delay-Tolerant Network Architecture for Challenged Internets”, In Proc. SIGCOMM, August 2003.[3] A. Vahdat and D. Becker, “Epidemic routing for partially-connected ad hoc networks,” Tech. Rep. CS-2000-06, Duke University, July 2000.[4] T. Spyropoulos, K. Psounis, C.S. Raqhavendra, “Spray and wait: an efficient routing scheme for intermittently connected mobile networks”, EE, USC, USA, In Proc. SIGCOMM, August 2005.[5] T. Spyropoulos, K. Psounis, C.S. Raqhavendra, “Spray and Focus: Efficient Mobility-Assisted Routing for Heterogeneous and Correlated Mobility”, USC, EECS, USA, In Proc. PERCOM, March 2007.[6] A.Lindgren, A.Doria, and O. Schel’en, “Probabilistic Routing in Intermittently Connected Networks”, LUT, Sweden, In Proc. SIGMOBILE, vol. 7-3, July 2003.[7] D.K. Cho, C.W. Chang, M.H. Tsai, M. Gerla, “Networked medical monitoring in the battlefield”, CS, UCLA, USA, In Proc. MILCOM, November 2008.[8] C. Caini, P. Cornice, R. Firrincieli, D. Lacamera, S. Tamagnini, “A DTN Approach to Satellite Communications”, DEIS/ ARCES, University of Bologna, Italy, In Proc. IEEE Journal on Selected Areas in Communications, vol. 26-5, June 2008. [9] Y. Sasaki, Y. Shibata, “Distributed Disaster Information System in DTN Based Mobile Communication Environment”, Japan, In Proc. BWCCA, November 2010.[10] P. Jinag, J. Bigham, E. Bodanese, “Adaptive Service Provisioning for Emergency Communications with DTN”, EECS, Queen Mary University of London, UK, In Proc. WCNC, March 2011.[11] Nathanael Thompson, Riccardo Crepaldi and Robin Kravets, “Locus: A Location-based Data Overlay for Disruption-tolerant Networks”, CS, University of Illinois Urbana-Champaign, USA, In Proc. CHANTS, September 2010.[12] P. Yang, M.C. Chuah, “Performance evaluations of data-centric information retrieval schemes for DTNs”, CSE, Lehigh University, USA, In Proc. MILCOM, November 2008.[13] Cong Liu, Jie Wu, Xin Guan and Li Chen, “Cooperative File Sharing in Hybrid Delay Tolerant Networks”, In Proc. ICDCSW, June 2011.[14] Mikko Pitk¨anen, Teemu K¨arkk¨ainen, Janico Greifenberg, and J¨org Ott, “Searching for Content in Mobile DTNs”, Helsinki University of Technology, Finland, In Proc. PERCOM, March 2009.[15] S.C. Nelson, M. Bakht, R. Kravets, “Encounter–Based Routing in DTNs”, CS, University of Illinois at Urbana-Champaign, USA, In Proc. INFOCOM, April 2009.[16] E.C.R de Oliveria, C.V.N. de Albuquerque, “NECTAR: A DTN Routing Protocol Based on Neighborhood Contact History”, Universidade Federal Fluminense, Brasil, In Proc. SAC, March 2009[17] J. LeBrun, C.N. Chuah, D. Ghosal, M. Zhang, “Knowledge-Based Opportunistic Forwarding in Vehicular Wireless Ad Hoc Networks”, UC Davis, USA, In Proc. VTC, May 2005.[18] P. Hui, J. Crowcroft, E. Yoneki, “BUBBLE Rap: Social-based Forwarding in Delay Tolerant Networks”, University of Cambridge, UK, In Proc. MobiHoc, May 2008.[19] P. Juang, H. Oki, Y. Wang, M. Martonosi, L.S. Peh, D. Rubenstein, “Energy-Efficient Computing for Wildlife Tracking: Design Tradeoffs and Early Experiences with ZebraNet”, Princeton University, USA, In Proc. ASPLOS-X, October 2002.[20] G. Sollazzo, M. Musolesi, C. Mascolo, “TACO-DTN: a time-aware content-based dissemination system for delay tolerant networks”, CS, University College London, UK, In Proc. MobiOpp, June 2007.[21] S. Carrilho, G. Valadon, H. Esaki, “Hikari: DTN message distribute system”, The University of Tokyo, Japan, IPSJ SIG Technical Report, January 2009.[22] C.E. Palazzi, A. Bujari, “A Delay/Disruption Tolerant Solution for Mobile-to-Mobile File Sharing”, University of Padova, Italy, Wireless Day, In Proc. IFIP, October 2010.[23] B. Cohen, “Incentives Build Robustness in BitTorrent”, May 2003[24] “InMobi Mobile Market 2011 Review: Explosive Growth in Mobile, Tablet Impressions Increase 771%*”, InMobi, January 2012.Available: http://www.inmobi.com/press-releases/[25] “Steve Jobs Declares Post-PC Era”, InformationWeek, June 2010.Available: http://www.informationweek.com/news/software/productivity_apps/225300193[26] T. Vincenty, “Direct and Inverse Solutions of Geodesics on the Ellipsoid with application of nested equations”, Survey Review, Vol.23, 1975.[27] Ari Keränen, Jörg Ott, Teemu Kärkkäinen, “The ONE Simulator for DTN Protocol Evaluation”, In Proc. SimuTools, March 2009.[28] Sicai Lin, Tzu-Chieh Tsai, Shindi Lee, Sheng-Chih Chen, "Location-Based Mobile Collaborative Digital Narrative Platform", In Proc. The Third International Conference on Creative Content Technologies (CONTENT 2011), Sep 2011. zh_TW
