1. NCCU Academic Hub
  2. Publications
  3. College of Informatics
  4. Theses
  5. Item

Publications-Theses

Article View/Open

Publication Export

Google ScholarTM

NCCU Library

Citation Infomation

Related Publications in TAIR

題名 基於社群聯盟並有地理輔助之耐延遲網路的路由協定
A novel DTN routing by social ally with geographic enhancement
作者 羅文卿
貢獻者 蔡子傑
羅文卿
關鍵詞 耐延遲網路
社交模式
地理資訊
路由協定
Delay Tolerant Network
Social-based
Social ally
Routing
Geographic
日期 2014
上傳時間 1-Jun-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 (Authors) 羅文卿zh_TW
dc.creator (作者) 羅文卿zh_TW
dc.date (日期) 2014en_US
dc.date.accessioned 1-Jun-2017 09:53:15 (UTC+8)-
dc.date.available 1-Jun-2017 09:53:15 (UTC+8)-
dc.date.issued (上傳時間) 1-Jun-2017 09:53:15 (UTC+8)-
dc.identifier (Other Identifiers) G0096753017en_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 (描述) 96753017zh_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 1
1.1 Background 1
1.2 Motivation 1
1.2.1 Social Graph and Contact Graph 2
1.2.2 Community 2
1.2.3 Centrality 3
1.2.4 Similarity 4
1.2.5 Friendship and Selfishness 4
1.3 Our Goal 4
1.4 Organization 4
CHAPTER 2 Related Work 6
2.1 Message-ferry-based routing Protocol 6
2.2 Opportunity-based Protocol 6
2.2.1 Epidemic Routing Protocol 6
2.2.2 Direct Contact Routing Protocol 7
2.3 Prediction-based Routing Protocol 7
2.3.1 PROPHET Routing Protocol 7
2.4 Social-based routing protocol 7
2.4.1 SimBet Routing Protocol 8
2.4.2 Bubble rap Routing Protocol 8
2.4.3 SMART Routing Protocol 9
CHAPTER 3 SAGE Routing 11
3.1 System Model 13
3.2 Leverage Algorithm 14
3.2.1 Social Layer 14
3.2.2 Geographic Layer 19
CHAPTER 4 Simulation and Results 22
4.1 Simulation Setup 23
4.1.1 General Settings of Simulator 24
4.1.2 Parameters about SAGE Routing Protocol 25
4.1.2.1 Social Ally 25
4.1.2.2 Geographic parameter 29
4.2 Simulation Results 33
CHAPTER 5 Conclusions and Future Work 39
5.1 Conclusion 39
5.2 Future Work 40
References 41		zh_TW
dc.format.extent 3578703 bytes-
dc.format.mimetype application/pdf-
dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0096753017en_US
dc.subject (關鍵詞) 耐延遲網路zh_TW
dc.subject (關鍵詞) 社交模式zh_TW
dc.subject (關鍵詞) 地理資訊zh_TW
dc.subject (關鍵詞) 路由協定zh_TW
dc.subject (關鍵詞) Delay Tolerant Networken_US
dc.subject (關鍵詞) Social-baseden_US
dc.subject (關鍵詞) Social allyen_US
dc.subject (關鍵詞) Routingen_US
dc.subject (關鍵詞) Geographicen_US
dc.title (題名) 基於社群聯盟並有地理輔助之耐延遲網路的路由協定zh_TW
dc.title (題名) A novel DTN routing by social ally with geographic enhancementen_US
dc.type (資料類型) thesisen_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