學術產出-Theses
Article View/Open
Publication Export
-
題名 基於社群感知之耐延遲網路群播路由機制
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 Chieh en_US dc.contributor.author (Authors) 林煜泓 zh_TW dc.contributor.author (Authors) Lin, Yu Hong en_US dc.creator (作者) 林煜泓 zh_TW dc.creator (作者) Lin, Yu Hong en_US dc.date (日期) 2012 en_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) G0100753036 en_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 (描述) 100753036 zh_TW dc.description (描述) 101 zh_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 11.1 Background 11.2 Motivation 21.3 Purpose 41.4 Organization 4CHAPTER 2 Related Work 52.1 Common DTN Routing Protocol 52.2 Social-based Multicasting Scheme 62.3 Social-based DTN Routing Protocol 7CHAPTER 3 Methodology 93.1 System Environment 93.1.1 Scenario 103.1.2 Technical Challenges 103.1.3 Operating Environment 113.2 Grouping 123.2.1 Similarity 123.3 Social-Aware Local Utility Calculation (SALUC) Routing Protocol 143.3.1 Centrality Metric 173.3.2 Probability 203.3.3 Formulation 213.4 Buffer Management Strategy 24CHAPTER 4 Simulation Results 264.1 Simulation Setup 284.2 Simulation Results 314.2.1 Common DTNs Routing Protocol 314.2.2 Social-based Forwarding Scheme 36CHAPTER 5 Conclusions and Future Work 43REFERENCES 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/#G0100753036 en_US 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 (關鍵詞) Social Network Analysis en_US dc.subject (關鍵詞) Multicasting en_US dc.subject (關鍵詞) Routing Protocol en_US dc.title (題名) 基於社群感知之耐延遲網路群播路由機制 zh_TW dc.title (題名) A Social-Aware Multicast Scheme in Delay Tolerant Networks en_US dc.type (資料類型) thesis en 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
