學術產出-學位論文
文章檢視/開啟
書目匯出
-
題名 基於社群聯盟並有地理輔助之耐延遲網路的路由協定
A novel DTN routing by social ally with geographic enhancement作者 羅文卿 貢獻者 蔡子傑
羅文卿關鍵詞 耐延遲網路
社交模式
地理資訊
路由協定
Delay Tolerant Network
Social-based
Social ally
Routing
Geographic日期 2014 上傳時間 1-六月-2017 09:53:15 (UTC+8) 摘要 在DTN(Delay Tolerant Networks)這類的網路架構下，無線節點之間的通訊連線是採非連續性建立的。DTN 路由協定中, 決定中繼節點方式大致可以分成兩類:依地理位置考量的路由協定（Geographic Routing Protocal）和依社交模式考量的路由協定（Social-based Routing Portocal）。 由於人與人間的互動是透過社交關係, 但是真實的資訊傳遞又須 仰賴當時的地理位置。因此我們提出的演算法將網路拓墣分成社交層與地理層, 在社交層中利用Social Ally Selection Algorithm 挑選出合適的社交盟友(Social Ally)。在地理層中利用Geographic Messenger Forwarding Algorithm 挑選合適的節點將訊息傳送給朝向目的地或是社交中繼站的節點。根據實驗模擬結果, 我們的路由協定能有較佳的傳遞成功率, 並降低了延遲時間。
Delay Tolerant networks (DTN) may lack continuous network connectivity. Most of these DTN routing protocol, which attempt to make better routing decision, could be divided in two categories: Geographic routing protocols and Social-based routing protocols. Due to the interaction between people through social behaviors and message transmissions rely on geographic position information, we proposed a routing protocol which network topology is divided into two sub layers: social layer and geographic layer. In social layer, we propose a Social Ally Selection Algorithm to decide social allies that are controlled to improve delivery performance. In geographic layer, we propose a Geographic Messenger Forwarding Algorithm to transmit message to the nodes moving toward to social ally or destination. According to the simulation results, we could show that our routing protocol have higher delivery ratio and lower delay latency compare to other protocols.參考文獻 [1] Jian Shen, Sangman Moh, Ilyong Chung, “Routing Protocols in Delay Tolerant Networks: A Comparative Survey”, The 23rd International Technical Conference on Circuits/Systems,Computers and Communications, pp. 1577 - 1580, 8 July, 2008[2] E.P.C. Jones and P.A.S ward, “Routing Strategies for Delay-Tolerant Networks”, Submitted to Computer Communacation Review,2008[3] A. Vahdat and D. Becker, “Epidemic routing for partially connected ad hoc networks,” Duke University Technical Report CS-200006, April 2000. [4] T. Spyropoulos, K. Psounis, and C. S. Raghavendra, “Spray and wait: an efficient routing scheme for intermittently connected mobile networks,” in WDTN ’05: Proc. 2005 ACM SIGCOMM workshop on Delay-tolerant networking, 2005, pp. 252–259. [5] J. Lebrun, C.-N. Chuah, D. Ghosal, and 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, May 2005.[6] A. Lindgren, A. Doria, and O. Schelen, “Probabilistic routing in intermittently connected networks”, in Proc. First International Workshop on Service Assurance with Partial and Intermittent Resources, pp. 239––254,2004.[7] H. Dang and H. Wu, “Clustering and Cluster-Based Routing Protocol for Delay-Tolerant Mobile Networks”, IEEE Transactions on Wireless Communications, Vol. 9, No.6, pp.1874–1881, June 2010.[8] P. Hui, A. Chaintreau, J. Scott, R. Gass, J. Crowcroft, and C. Diot, “Pocket switched networks and human mobility in conference environments”, in Proc. ACM SIGCOMM Workshop on DTN and Related Topics, pp. 244––251, 2005.[9] C. Liu and J. Wu, “Scalable routing in delay tolerant networks”, in Proc.ACM MobiHoc, 2007.[10] A. Chaintreau, P. Hui, J. Crowcroft, C. Diot, R. Gass, and J. Scott, “Impact of human mobility on the design of opportunistic forwarding algorithms”, in Proc. IEEE INFOCOM, pp. 1––13, 2006.[11] M. Kim, D. Kotz, and S. Kim, “Extracting a mobility model from real user traces”, in Proc. IEEE INFOCOM, pp. 1––13, 2006.[12] T. Spyropoulos, K. Psounis, and C. Raghavendra, “Performance analysis of mobility-assisted routing”, in Proc. MobiHoc’06: 7th ACM International Symposium on Mobile Ad Hoc Networking and Computing,pp. 49––60, 2006.[13] J. Leguay, T. Friedman, and V. Conan, “DTN routing in a mobility pattern space”, in Proc. WDTN‘05: 2005 ACM SIGCOMM Workshop on Delay-tolerant Networking, pp. 276––283, 2005. [14] Ari Keränen, Jörg Ott, Teemu Kärkkäinen, “The ONE Simulator for DTN Protocol Evaluation”, in SIMUTools’09: 2nd International Conference on Simulation Tools ans Techniques, Rome, March 2-6,2009[15] H. Zhu, X. Lin, R. Lu, and X. Shen, “A secure incentive scheme for delay tolerant networks,” in Proc. 3rd International Conference on Communications and Networking in China (ChinaCom), Aug. 2008. [16] H. Zhu, X. Lin, R. Lu, Y. Fan, and X. Shen, “Smart: A secure multilayer credit-based incentive scheme for delay-tolerant networks,” IEEE Trans. Veh. Technol., vol. 58, no. 8, pp. 4628–4639, Oct. 2009. [17] P. Hui and J. Crowcroft, “How small labels create big improvements,” in International Workshop on Intermittently Connected Mobile Ad hoc Networks in conjunction with IEEE PerCom 2007, March 19-23, 2007. [18] E. M. Daly and M. Haahr, “Social network analysis for routing in disconnected delay-tolerant manets,” in MobiHoc ’07 Proc. 8th ACM international symposium on Mobile ad hoc networking and computing, 2007. [19] P. Hui, J. Crowcroft, and E. Yonek, “Bubble rap: Social-based for- warding in delay tolerant networks,” in Proc. 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), May, 2008. [20] W. Zhao, M. Ammar, and E. Zegura, “A message ferrying approach for data delivery in sparse mobile ad hoc networks,” in MobiHoc ’04: Proc. 5th ACM international symposium on Mobile ad hoc networking and computing, pp. 187–198, 2004. [21] W. Zhao, M. Ammar, and E. Zegura, “Controlling the mobility of multiple data transport ferries in a delay-tolerant network,” in Proc. 24th IEEE International Conference on Computer Communications (INFOCOM), 2005. [22] P. Juang, H. Oki, Y. Wang, M. Martonosi, L. S. Peh, and D. Rubenstein, “Energy-efficient computing for wildlife tracking: design tradeoffs and early experiences with zebranet,” SIGOPS Oper. Syst. Rev., vol. 36, no. 5, pp. 96–107, 2002. [23] T. Hossmann, F. Legendre, and T. Spyropoulos, “From contacts to graphs: pitfalls in using complex network analysis for DTN routing,” in INFOCOM’09: Proc. 28th IEEE International conference on Computer Communications Workshops, pp. 260–265, 2009.[24] T. Hossmann, T. Spyropoulos, and F. Legendre, “Know thy neighbor: Towards optimal mapping of contacts to social graphs for DTN routing,” in INFOCOM’10: Proc. 29th IEEE International conference on Computer Communications, 2010. [25] P. Hui, E. Yoneki, S.Y. Chan, and J. Crowcroft, “Distributed community detection in delay tolerant networks,” in Proc. ACM SIGCOMM Workshop, MobiArch’07, 2007. [26] E. Yoneki, P. Hui, and J. Crowcroft, “Visualizing community detection in opportunistic networks,” in Proc. ACM MobiCom Workshop on Challenged Networks (CHANTS), September, 2007. [27] P. Hui, E. Yoneki, and J. Crowcroft, “Identifying social communities in complex communications for network efficiency,” in Proc. 1st In- ternational Conference on Complex Sciences: Theory and Applications (Complex 2009), February, 2009. [28] S. Y. Chan, P. Hui, and K. Xu, “Community detection of time-varying mobile social networks,” in Proc. 1st International Conference on Complex Sciences: Theory and Applications (Complex 2009), February, 2009. [29] W. Wang, S. Eidenbenz, Y. Wang, and X.-Y. Li, “OURS: Optimal unicast routing system in non-cooperative wireless networks,” in Proc. 12th ACM Annual International Conference on Mobile Computing and Networking (MobiCom 2006), 2006. 描述 碩士
國立政治大學
資訊科學學系
96753017資料來源 http://thesis.lib.nccu.edu.tw/record/#G0096753017 資料類型 thesis dc.contributor.advisor 蔡子傑 zh_TW dc.contributor.author (作者) 羅文卿 zh_TW dc.creator (作者) 羅文卿 zh_TW dc.date (日期) 2014 en_US dc.date.accessioned 1-六月-2017 09:53:15 (UTC+8) - dc.date.available 1-六月-2017 09:53:15 (UTC+8) - dc.date.issued (上傳時間) 1-六月-2017 09:53:15 (UTC+8) - dc.identifier (其他 識別碼) G0096753017 en_US dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/110148 - dc.description (描述) 碩士 zh_TW dc.description (描述) 國立政治大學 zh_TW dc.description (描述) 資訊科學學系 zh_TW dc.description (描述) 96753017 zh_TW dc.description.abstract (摘要) 在DTN(Delay Tolerant Networks)這類的網路架構下，無線節點之間的通訊連線是採非連續性建立的。DTN 路由協定中, 決定中繼節點方式大致可以分成兩類:依地理位置考量的路由協定（Geographic Routing Protocal）和依社交模式考量的路由協定（Social-based Routing Portocal）。 由於人與人間的互動是透過社交關係, 但是真實的資訊傳遞又須 仰賴當時的地理位置。因此我們提出的演算法將網路拓墣分成社交層與地理層, 在社交層中利用Social Ally Selection Algorithm 挑選出合適的社交盟友(Social Ally)。在地理層中利用Geographic Messenger Forwarding Algorithm 挑選合適的節點將訊息傳送給朝向目的地或是社交中繼站的節點。根據實驗模擬結果, 我們的路由協定能有較佳的傳遞成功率, 並降低了延遲時間。 zh_TW dc.description.abstract (摘要) Delay Tolerant networks (DTN) may lack continuous network connectivity. Most of these DTN routing protocol, which attempt to make better routing decision, could be divided in two categories: Geographic routing protocols and Social-based routing protocols. Due to the interaction between people through social behaviors and message transmissions rely on geographic position information, we proposed a routing protocol which network topology is divided into two sub layers: social layer and geographic layer. In social layer, we propose a Social Ally Selection Algorithm to decide social allies that are controlled to improve delivery performance. In geographic layer, we propose a Geographic Messenger Forwarding Algorithm to transmit message to the nodes moving toward to social ally or destination. According to the simulation results, we could show that our routing protocol have higher delivery ratio and lower delay latency compare to other protocols. en_US dc.description.tableofcontents CHAPTER 1 Introduction 11.1 Background 11.2 Motivation 11.2.1 Social Graph and Contact Graph 21.2.2 Community 21.2.3 Centrality 31.2.4 Similarity 41.2.5 Friendship and Selfishness 41.3 Our Goal 41.4 Organization 4CHAPTER 2 Related Work 62.1 Message-ferry-based routing Protocol 62.2 Opportunity-based Protocol 62.2.1 Epidemic Routing Protocol 62.2.2 Direct Contact Routing Protocol 72.3 Prediction-based Routing Protocol 72.3.1 PROPHET Routing Protocol 72.4 Social-based routing protocol 72.4.1 SimBet Routing Protocol 82.4.2 Bubble rap Routing Protocol 82.4.3 SMART Routing Protocol 9CHAPTER 3 SAGE Routing 113.1 System Model 133.2 Leverage Algorithm 143.2.1 Social Layer 143.2.2 Geographic Layer 19CHAPTER 4 Simulation and Results 224.1 Simulation Setup 234.1.1 General Settings of Simulator 244.1.2 Parameters about SAGE Routing Protocol 254.1.2.1 Social Ally 254.1.2.2 Geographic parameter 294.2 Simulation Results 33CHAPTER 5 Conclusions and Future Work 395.1 Conclusion 395.2 Future Work 40References 41 zh_TW dc.format.extent 3578703 bytes - dc.format.mimetype application/pdf - dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0096753017 en_US 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 (關鍵詞) Social-based en_US dc.subject (關鍵詞) Social ally en_US dc.subject (關鍵詞) Routing en_US dc.subject (關鍵詞) Geographic en_US dc.title (題名) 基於社群聯盟並有地理輔助之耐延遲網路的路由協定 zh_TW dc.title (題名) A novel DTN routing by social ally with geographic enhancement en_US dc.type (資料類型) thesis en_US dc.relation.reference (參考文獻) [1] Jian Shen, Sangman Moh, Ilyong Chung, “Routing Protocols in Delay Tolerant Networks: A Comparative Survey”, The 23rd International Technical Conference on Circuits/Systems,Computers and Communications, pp. 1577 - 1580, 8 July, 2008[2] E.P.C. Jones and P.A.S ward, “Routing Strategies for Delay-Tolerant Networks”, Submitted to Computer Communacation Review,2008[3] A. Vahdat and D. Becker, “Epidemic routing for partially connected ad hoc networks,” Duke University Technical Report CS-200006, April 2000. [4] T. Spyropoulos, K. Psounis, and C. S. Raghavendra, “Spray and wait: an efficient routing scheme for intermittently connected mobile networks,” in WDTN ’05: Proc. 2005 ACM SIGCOMM workshop on Delay-tolerant networking, 2005, pp. 252–259. [5] J. Lebrun, C.-N. Chuah, D. Ghosal, and 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, May 2005.[6] A. Lindgren, A. Doria, and O. Schelen, “Probabilistic routing in intermittently connected networks”, in Proc. First International Workshop on Service Assurance with Partial and Intermittent Resources, pp. 239––254,2004.[7] H. Dang and H. Wu, “Clustering and Cluster-Based Routing Protocol for Delay-Tolerant Mobile Networks”, IEEE Transactions on Wireless Communications, Vol. 9, No.6, pp.1874–1881, June 2010.[8] P. Hui, A. Chaintreau, J. Scott, R. Gass, J. Crowcroft, and C. Diot, “Pocket switched networks and human mobility in conference environments”, in Proc. ACM SIGCOMM Workshop on DTN and Related Topics, pp. 244––251, 2005.[9] C. Liu and J. Wu, “Scalable routing in delay tolerant networks”, in Proc.ACM MobiHoc, 2007.[10] A. Chaintreau, P. Hui, J. Crowcroft, C. Diot, R. Gass, and J. Scott, “Impact of human mobility on the design of opportunistic forwarding algorithms”, in Proc. IEEE INFOCOM, pp. 1––13, 2006.[11] M. Kim, D. Kotz, and S. Kim, “Extracting a mobility model from real user traces”, in Proc. IEEE INFOCOM, pp. 1––13, 2006.[12] T. Spyropoulos, K. Psounis, and C. Raghavendra, “Performance analysis of mobility-assisted routing”, in Proc. MobiHoc’06: 7th ACM International Symposium on Mobile Ad Hoc Networking and Computing,pp. 49––60, 2006.[13] J. Leguay, T. Friedman, and V. Conan, “DTN routing in a mobility pattern space”, in Proc. WDTN‘05: 2005 ACM SIGCOMM Workshop on Delay-tolerant Networking, pp. 276––283, 2005. [14] Ari Keränen, Jörg Ott, Teemu Kärkkäinen, “The ONE Simulator for DTN Protocol Evaluation”, in SIMUTools’09: 2nd International Conference on Simulation Tools ans Techniques, Rome, March 2-6,2009[15] H. Zhu, X. Lin, R. Lu, and X. Shen, “A secure incentive scheme for delay tolerant networks,” in Proc. 3rd International Conference on Communications and Networking in China (ChinaCom), Aug. 2008. [16] H. Zhu, X. Lin, R. Lu, Y. Fan, and X. Shen, “Smart: A secure multilayer credit-based incentive scheme for delay-tolerant networks,” IEEE Trans. Veh. Technol., vol. 58, no. 8, pp. 4628–4639, Oct. 2009. [17] P. Hui and J. Crowcroft, “How small labels create big improvements,” in International Workshop on Intermittently Connected Mobile Ad hoc Networks in conjunction with IEEE PerCom 2007, March 19-23, 2007. [18] E. M. Daly and M. Haahr, “Social network analysis for routing in disconnected delay-tolerant manets,” in MobiHoc ’07 Proc. 8th ACM international symposium on Mobile ad hoc networking and computing, 2007. [19] P. Hui, J. Crowcroft, and E. Yonek, “Bubble rap: Social-based for- warding in delay tolerant networks,” in Proc. 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), May, 2008. [20] W. Zhao, M. Ammar, and E. Zegura, “A message ferrying approach for data delivery in sparse mobile ad hoc networks,” in MobiHoc ’04: Proc. 5th ACM international symposium on Mobile ad hoc networking and computing, pp. 187–198, 2004. [21] W. Zhao, M. Ammar, and E. Zegura, “Controlling the mobility of multiple data transport ferries in a delay-tolerant network,” in Proc. 24th IEEE International Conference on Computer Communications (INFOCOM), 2005. [22] P. Juang, H. Oki, Y. Wang, M. Martonosi, L. S. Peh, and D. Rubenstein, “Energy-efficient computing for wildlife tracking: design tradeoffs and early experiences with zebranet,” SIGOPS Oper. Syst. Rev., vol. 36, no. 5, pp. 96–107, 2002. [23] T. Hossmann, F. Legendre, and T. Spyropoulos, “From contacts to graphs: pitfalls in using complex network analysis for DTN routing,” in INFOCOM’09: Proc. 28th IEEE International conference on Computer Communications Workshops, pp. 260–265, 2009.[24] T. Hossmann, T. Spyropoulos, and F. Legendre, “Know thy neighbor: Towards optimal mapping of contacts to social graphs for DTN routing,” in INFOCOM’10: Proc. 29th IEEE International conference on Computer Communications, 2010. [25] P. Hui, E. Yoneki, S.Y. Chan, and J. Crowcroft, “Distributed community detection in delay tolerant networks,” in Proc. ACM SIGCOMM Workshop, MobiArch’07, 2007. [26] E. Yoneki, P. Hui, and J. Crowcroft, “Visualizing community detection in opportunistic networks,” in Proc. ACM MobiCom Workshop on Challenged Networks (CHANTS), September, 2007. [27] P. Hui, E. Yoneki, and J. Crowcroft, “Identifying social communities in complex communications for network efficiency,” in Proc. 1st In- ternational Conference on Complex Sciences: Theory and Applications (Complex 2009), February, 2009. [28] S. Y. Chan, P. Hui, and K. Xu, “Community detection of time-varying mobile social networks,” in Proc. 1st International Conference on Complex Sciences: Theory and Applications (Complex 2009), February, 2009. [29] W. Wang, S. Eidenbenz, Y. Wang, and X.-Y. Li, “OURS: Optimal unicast routing system in non-cooperative wireless networks,” in Proc. 12th ACM Annual International Conference on Mobile Computing and Networking (MobiCom 2006), 2006. zh_TW
