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 Social-Aware Multicast Scheme in Delay Tolerant Networks
作者 林煜泓
Lin, Yu Hong
貢獻者 蔡子傑
Tsai, Tzu Chieh
林煜泓
Lin, Yu Hong
關鍵詞 耐延遲網路
社群網路分析
群播機制
路由協定
Delay Tolerant Networks
Social Network Analysis
Multicasting
Routing Protocol
日期 2012
上傳時間 2-Sep-2013 16:49:12 (UTC+8)
摘要 在耐延遲網路環境下節點的相遇情況不是很頻繁，這可能導致節點間的連線斷斷續續，使得有效地將訊息傳遞成為一件困難的事情。藉由社群感知轉送機制的中間度指標特性，可以來提升傳送成功率。雖然大多數研究幾乎都是將訊息轉送到單一目的地或是多個且已知的目的地。然而，一些應用像是廣告的散佈，要將訊息送給對訊息有興趣的人，但卻不知道是誰。因此，關鍵的問題為如何建立社群網路關係的親密度機制，來選擇作為轉送訊息的節點，並利用群體廣播的方式盡可能有效地傳播至最多可能目標目的地，進而提升效能。
本論文以群播機制和社群感知當作基礎概念，來設計新的轉送訊息的方法和公式化選擇中繼節點的機制。最後，我們使用政治大學實際軌跡來模擬，將模擬結果與其它路由演算法比較，其結果證明我們所提出的方法能提高訊息傳送成功率和正確率，降低傳送延遲時間和傳送訊息的成本。
In delay tolerant networks (DTNs), nodes infrequently encounter with each others. This results in intermittent connectivity of the nodes, and makes it difficult to deliver the message effectively. A social-aware forwarding scheme can help for successful delivery ratio by utilizing the characteristic of their centrality metric. Most of the previous studies focus on message delivery to single destination or some priori known destinations. However, some applications like advertisement dissemination may not know who will be the interested persons to be delivered. Therefore, the key challenge is how to establish the social relationship strategy to select appropriate nodes as relays, and furthermore to use multicasting to disseminate effectively as many “target” destinations as possible to improve the performance.
This thesis developed a new strategy which has a new forwarding message scheme and formulates the selection of the relay nodes based on the concept of the multicasting and the social network. Finally, we used the reality trace data of National Chengchi University to simulate. The simulation results are compared to others DTNs routing protocols as well as other social-aware forwarding schemes. The results showed that our proposed approach can enhance the successful delivery ratio and delivery accuracy, decrease the delivery delay and reduce the delivery overhead.
參考文獻 [1]N. Eagle and A. Pentland. Reality mining: sensing complex social systems. Personal and Ubiquitous Computing, Vol 10(4):255–268, May 2006.
[2]Zhensheng Zhang. Routing in Intermittently Connected Mobile Ad Hoc Networks and Delay Tolerant Networks: Overview and Challenges. IEEE Communications Surveys & Tutorials, 8(1):24–37, 2006.
[3]Christoph P. Mayer. Hybrid Routing in Delat Tolerant Networks. KIT Scientific Publishing, July 3, 2012.
[4]Wi-Fi alliance : http://www.wi-fi.org/index.php
[5]Social Network Analytics : http://crawdad.cs.dartmouth.edu/
[6]E. Daly and M. Haahr, “Social network analysis for routing in disconnected delay-tolerant MANETs,” in Proc. ACM MobiHoc, 2007, pp. 32–40.
[7]W.Gao,Q.Li, B. Zhao, andG. Cao, “Multicasting in delay tolerant networks: A social network perspective,” in Proc. ACM MobiHoc, 2009, pp. 299–308.
[8]P. Hui, J. Crowcroft, and E. Yoneki, “Bubble Rap: Social-based forwarding in delay tolerant networks,” in Proc. ACM MobiHoc, 2008, pp. 241–250.
[9]Wei Gao, Qinghua Li, Bo Zhao and Guohong Cao, “Social-Aware Multicast in Disruption-Tolerant Networks,” in IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 20, NO. 5, OCTOBER 2012
[10]Jiuxin Cao, Liu Yang, Xiao Zheng, Bo Liu, Lei Zhao, Xudong Ni, Fang Dong and Bo Mao, “Social attribute based web service information publication mechanism in Delay Tolerant Network,” in IEEE International Conference on Computational Science and Engineering CSE/I-SPAN
[11]VAHDAT, A., AND BECKER, D. Epidemic routing for partially connected ad hoc networks. Technical Report CS-200006, Duke University (2000).
[12]LINDGREN, A., DORIA, A., AND SCHELÉN, O. Probabilistic routing in intermittently connected networks. Lecture Notes in Computer Science 3126 (2004), 239–254.
[13]SPYROPOULOS, T., PSOUNIS, K., AND RAGHAVENDRA, C. S. Spray and wait: an efficient routing scheme for intermittently connected mobile networks. In proc. WDTN ’05 (2005), ACM Press, pp. 252–259.
[14]K. Jahanbakhsh, G.C. Shoja, V. King, Social-greedy: a socially-based greedy routing algorithm for delay tolerant networks, MobiOpp’10: Proceedings of the Second International Workshop on Mobile Opportunistic Networking, ACM, New York, NY, USA (2010), pp. 159–162
[15]J. Leguay, T. Friedman, and V. Conan, “Evaluating mobility pattern space routing for DTNs,” in Proceedings of the 25th IEEE International Conference on Computer Communications (INFOCOM), Barcelona, Spain, April 2006.
[16]E. Bulut and B. K. Szymanski, “Friendship based routing in delay tolerant mobile social networks,” in Proceedings of IEEE Global Telecommunications Conference (GLOBECOM),, Dec, 2010.
[17]A. Mei, G. Morabito, P. Santi and J. Stefa, “Social-aware stateless forwarding in pocket switched networks,” in Proceeding of the 30th IEEE Conference on Computer Communications(INFOCOM) mini-conference, 2011.
[18]F. Fabbri and R. Verdone, “A sociability-based routing scheme for delay-tolerant networks,” In EURASIP Journal on Wireless Communications and Networking, vol. 2011, January, 2011.
[19]P. Hui, A. Chaintreau, J. Scott, R. Gass, J. Crowcroft, and C. Diot, “Pocket switched networks and the consequences of human mobility in conference environments,” in WDTN ’05: Proceedings of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, 2005.
[20]Ying Zhu, Bin Xu, Xinghua Shi, and Yu Wang. A Survey of Social-based Routing in Delay Tolerant Networks: Positive and Negative Social Effects. IEEE Communications Surveys & Tutorial, Volume: pp , Issue: 9, April,2012
[21]P. Hui, E. Yoneki, S.Y. Chan, and J. Crowcroft, “Distributed community detection in delay tolerant networks,” in Proc. of ACM SIGCOMM Workshop, MobiArch’07, 2007.
[22]A.Lindgren, A.Doria, and O. Schel’en, “Probabilistic Routing in Intermittently Connected Networks, ” ACM SIGMOBILE Mobile Computing and Communications Review, 7(3), 2003.
[23]M. C. Chuah. Social network aided multicast delivery scheme for human contact-based networks. In Proceedings of the 1st Workshop on Simplifying Complex Network for Practitioners (Simplex), 2009.
[24]FREEMAN, L. C. A set of measures of centrality based on betweenness. Sociometry (1977), 35–41.
[25]FREEMAN, L. C. Centrality in social networks conceptual clarification. Social networks (Soc. networks) (1979), 215–239.
[26]Ari Keränen, Jörg Ott and Teemu Kärkkäinen: The ONE Simulator for DTN Protocol Evaluation. SIMUTools`09: 2nd International Conference on Simulation Tools and Techniques. Rome, March 2009.
[27]Deza, M.M., Deza, E.: Encyclopedia of Distances. Springer, Berlin (2009)
[28]Mei, A., Morabito, G., Santi, P., Stefa, J.: Social-Aware Stateless Forwarding in Pocket Switched Networks. In: Proc. IEEE Infocom, MiniConference (2011)
描述 碩士
國立政治大學
資訊科學學系
100753036
101
資料來源 http://thesis.lib.nccu.edu.tw/record/#G0100753036
資料類型 thesis
dc.contributor.advisor 蔡子傑zh_TW
dc.contributor.advisor Tsai, Tzu Chiehen_US
dc.contributor.author (Authors) 林煜泓zh_TW
dc.contributor.author (Authors) Lin, Yu Hongen_US
dc.creator (作者) 林煜泓zh_TW
dc.creator (作者) Lin, Yu Hongen_US
dc.date (日期) 2012en_US
dc.date.accessioned 2-Sep-2013 16:49:12 (UTC+8)-
dc.date.available 2-Sep-2013 16:49:12 (UTC+8)-
dc.date.issued (上傳時間) 2-Sep-2013 16:49:12 (UTC+8)-
dc.identifier (Other Identifiers) G0100753036en_US
dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/59443-
dc.description (描述) 碩士zh_TW
dc.description (描述) 國立政治大學zh_TW
dc.description (描述) 資訊科學學系zh_TW
dc.description (描述) 100753036zh_TW
dc.description (描述) 101zh_TW
dc.description.abstract (摘要) 在耐延遲網路環境下節點的相遇情況不是很頻繁，這可能導致節點間的連線斷斷續續，使得有效地將訊息傳遞成為一件困難的事情。藉由社群感知轉送機制的中間度指標特性，可以來提升傳送成功率。雖然大多數研究幾乎都是將訊息轉送到單一目的地或是多個且已知的目的地。然而，一些應用像是廣告的散佈，要將訊息送給對訊息有興趣的人，但卻不知道是誰。因此，關鍵的問題為如何建立社群網路關係的親密度機制，來選擇作為轉送訊息的節點，並利用群體廣播的方式盡可能有效地傳播至最多可能目標目的地，進而提升效能。
本論文以群播機制和社群感知當作基礎概念，來設計新的轉送訊息的方法和公式化選擇中繼節點的機制。最後，我們使用政治大學實際軌跡來模擬，將模擬結果與其它路由演算法比較，其結果證明我們所提出的方法能提高訊息傳送成功率和正確率，降低傳送延遲時間和傳送訊息的成本。		zh_TW
dc.description.abstract (摘要) In delay tolerant networks (DTNs), nodes infrequently encounter with each others. This results in intermittent connectivity of the nodes, and makes it difficult to deliver the message effectively. A social-aware forwarding scheme can help for successful delivery ratio by utilizing the characteristic of their centrality metric. Most of the previous studies focus on message delivery to single destination or some priori known destinations. However, some applications like advertisement dissemination may not know who will be the interested persons to be delivered. Therefore, the key challenge is how to establish the social relationship strategy to select appropriate nodes as relays, and furthermore to use multicasting to disseminate effectively as many “target” destinations as possible to improve the performance.
This thesis developed a new strategy which has a new forwarding message scheme and formulates the selection of the relay nodes based on the concept of the multicasting and the social network. Finally, we used the reality trace data of National Chengchi University to simulate. The simulation results are compared to others DTNs routing protocols as well as other social-aware forwarding schemes. The results showed that our proposed approach can enhance the successful delivery ratio and delivery accuracy, decrease the delivery delay and reduce the delivery overhead.		en_US
dc.description.tableofcontents CHAPTER 1 Introduction 1
1.1 Background 1
1.2 Motivation 2
1.3 Purpose 4
1.4 Organization 4
CHAPTER 2 Related Work 5
2.1 Common DTN Routing Protocol 5
2.2 Social-based Multicasting Scheme 6
2.3 Social-based DTN Routing Protocol 7
CHAPTER 3 Methodology 9
3.1 System Environment 9
3.1.1 Scenario 10
3.1.2 Technical Challenges 10
3.1.3 Operating Environment 11
3.2 Grouping 12
3.2.1 Similarity 12
3.3 Social-Aware Local Utility Calculation (SALUC) Routing Protocol 14
3.3.1 Centrality Metric 17
3.3.2 Probability 20
3.3.3 Formulation 21
3.4 Buffer Management Strategy 24
CHAPTER 4 Simulation Results 26
4.1 Simulation Setup 28
4.2 Simulation Results 31
4.2.1 Common DTNs Routing Protocol 31
4.2.2 Social-based Forwarding Scheme 36
CHAPTER 5 Conclusions and Future Work 43
REFERENCES 44		zh_TW
dc.format.extent 2075843 bytes-
dc.format.mimetype application/pdf-
dc.language.iso en_US-
dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0100753036en_US
dc.subject (關鍵詞) 耐延遲網路zh_TW
dc.subject (關鍵詞) 社群網路分析zh_TW
dc.subject (關鍵詞) 群播機制zh_TW
dc.subject (關鍵詞) 路由協定zh_TW
dc.subject (關鍵詞) Delay Tolerant Networksen_US
dc.subject (關鍵詞) Social Network Analysisen_US
dc.subject (關鍵詞) Multicastingen_US
dc.subject (關鍵詞) Routing Protocolen_US
dc.title (題名) 基於社群感知之耐延遲網路群播路由機制zh_TW
dc.title (題名) A Social-Aware Multicast Scheme in Delay Tolerant Networksen_US
dc.type (資料類型) thesisen
dc.relation.reference (參考文獻) [1]N. Eagle and A. Pentland. Reality mining: sensing complex social systems. Personal and Ubiquitous Computing, Vol 10(4):255–268, May 2006.
[2]Zhensheng Zhang. Routing in Intermittently Connected Mobile Ad Hoc Networks and Delay Tolerant Networks: Overview and Challenges. IEEE Communications Surveys & Tutorials, 8(1):24–37, 2006.
[3]Christoph P. Mayer. Hybrid Routing in Delat Tolerant Networks. KIT Scientific Publishing, July 3, 2012.
[4]Wi-Fi alliance : http://www.wi-fi.org/index.php
[5]Social Network Analytics : http://crawdad.cs.dartmouth.edu/
[6]E. Daly and M. Haahr, “Social network analysis for routing in disconnected delay-tolerant MANETs,” in Proc. ACM MobiHoc, 2007, pp. 32–40.
[7]W.Gao,Q.Li, B. Zhao, andG. Cao, “Multicasting in delay tolerant networks: A social network perspective,” in Proc. ACM MobiHoc, 2009, pp. 299–308.
[8]P. Hui, J. Crowcroft, and E. Yoneki, “Bubble Rap: Social-based forwarding in delay tolerant networks,” in Proc. ACM MobiHoc, 2008, pp. 241–250.
[9]Wei Gao, Qinghua Li, Bo Zhao and Guohong Cao, “Social-Aware Multicast in Disruption-Tolerant Networks,” in IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 20, NO. 5, OCTOBER 2012
[10]Jiuxin Cao, Liu Yang, Xiao Zheng, Bo Liu, Lei Zhao, Xudong Ni, Fang Dong and Bo Mao, “Social attribute based web service information publication mechanism in Delay Tolerant Network,” in IEEE International Conference on Computational Science and Engineering CSE/I-SPAN
[11]VAHDAT, A., AND BECKER, D. Epidemic routing for partially connected ad hoc networks. Technical Report CS-200006, Duke University (2000).
[12]LINDGREN, A., DORIA, A., AND SCHELÉN, O. Probabilistic routing in intermittently connected networks. Lecture Notes in Computer Science 3126 (2004), 239–254.
[13]SPYROPOULOS, T., PSOUNIS, K., AND RAGHAVENDRA, C. S. Spray and wait: an efficient routing scheme for intermittently connected mobile networks. In proc. WDTN ’05 (2005), ACM Press, pp. 252–259.
[14]K. Jahanbakhsh, G.C. Shoja, V. King, Social-greedy: a socially-based greedy routing algorithm for delay tolerant networks, MobiOpp’10: Proceedings of the Second International Workshop on Mobile Opportunistic Networking, ACM, New York, NY, USA (2010), pp. 159–162
[15]J. Leguay, T. Friedman, and V. Conan, “Evaluating mobility pattern space routing for DTNs,” in Proceedings of the 25th IEEE International Conference on Computer Communications (INFOCOM), Barcelona, Spain, April 2006.
[16]E. Bulut and B. K. Szymanski, “Friendship based routing in delay tolerant mobile social networks,” in Proceedings of IEEE Global Telecommunications Conference (GLOBECOM),, Dec, 2010.
[17]A. Mei, G. Morabito, P. Santi and J. Stefa, “Social-aware stateless forwarding in pocket switched networks,” in Proceeding of the 30th IEEE Conference on Computer Communications(INFOCOM) mini-conference, 2011.
[18]F. Fabbri and R. Verdone, “A sociability-based routing scheme for delay-tolerant networks,” In EURASIP Journal on Wireless Communications and Networking, vol. 2011, January, 2011.
[19]P. Hui, A. Chaintreau, J. Scott, R. Gass, J. Crowcroft, and C. Diot, “Pocket switched networks and the consequences of human mobility in conference environments,” in WDTN ’05: Proceedings of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, 2005.
[20]Ying Zhu, Bin Xu, Xinghua Shi, and Yu Wang. A Survey of Social-based Routing in Delay Tolerant Networks: Positive and Negative Social Effects. IEEE Communications Surveys & Tutorial, Volume: pp , Issue: 9, April,2012
[21]P. Hui, E. Yoneki, S.Y. Chan, and J. Crowcroft, “Distributed community detection in delay tolerant networks,” in Proc. of ACM SIGCOMM Workshop, MobiArch’07, 2007.
[22]A.Lindgren, A.Doria, and O. Schel’en, “Probabilistic Routing in Intermittently Connected Networks, ” ACM SIGMOBILE Mobile Computing and Communications Review, 7(3), 2003.
[23]M. C. Chuah. Social network aided multicast delivery scheme for human contact-based networks. In Proceedings of the 1st Workshop on Simplifying Complex Network for Practitioners (Simplex), 2009.
[24]FREEMAN, L. C. A set of measures of centrality based on betweenness. Sociometry (1977), 35–41.
[25]FREEMAN, L. C. Centrality in social networks conceptual clarification. Social networks (Soc. networks) (1979), 215–239.
[26]Ari Keränen, Jörg Ott and Teemu Kärkkäinen: The ONE Simulator for DTN Protocol Evaluation. SIMUTools`09: 2nd International Conference on Simulation Tools and Techniques. Rome, March 2009.
[27]Deza, M.M., Deza, E.: Encyclopedia of Distances. Springer, Berlin (2009)
[28]Mei, A., Morabito, G., Santi, P., Stefa, J.: Social-Aware Stateless Forwarding in Pocket Switched Networks. In: Proc. IEEE Infocom, MiniConference (2011)		zh_TW