學術產出-Theses
Article View/Open
Publication Export
-
題名 基於社交行為對興趣導向訊息之耐延遲網路傳輸策略
An Interest-based Message Dissemination Approach with Social Behavior Consideration in Delay Tolerant Networks作者 陳柏錡
Chen, Po Chi貢獻者 蔡子傑
Tsai, Tzu Chieh
陳柏錡
Chen, Po Chi關鍵詞 耐延遲網路
校園環境
個人資訊
個人興趣
社群關係
Delay-Tolerant Network
campus environment
personal information
personal interest
social relationship日期 2016 上傳時間 22-Aug-2016 11:07:08 (UTC+8) 摘要 耐延遲網路相較於一般的3G、4G或是Wi-Fi網路是相對受限的，只能利用節點之間短暫的相遇時利用Bluetooth以及Wi-Fi direct交流訊息，他不僅沒有穩定的連線能力，頻寬也相對較小。但耐延遲網路卻因是斷斷續續且可以傳送給現實中相遇的人，使他人幫忙攜帶訊息進而傳送至目的而成優點。因現今社會的人們大多有固定的行經路線像平日的上下班，亦或是學生一定有著固定的課表和交通路線。另外，有共同興趣的人也會朝著特定的地標前進，像喜歡運動的人會往運動中心集中、喜歡閱讀的人會往圖書館借閱書籍、喜歡文藝的人會賞閱展覽。這無形中讓我們可以利用耐延遲網路的方式傳送有特定屬性的廣告訊息給對這特定屬性有興趣的人們。我們在此論文中提出兩種在耐延遲網路上新的資料傳遞方式，我們集合人們有各自的喜好並以人們有相同路徑及有著相同興趣的人們會聚集的特性在人群中傳送訊息，我們預先用手機蒐集歷史資料並統計人群的移動模型再用以驗證未來節點相遇的情況。最後，我們將本論文方法與其它資料傳送方法比較評估效能，模擬結果顯示我們提出的傳送方法有較優的傳送成功率與相對較低的資源耗費。
Compared with 3G, 4G and Wi-Fi, Delay-Tolerant Networking (DTN) can only have intermittent chance to transmit messages with Bluetooth or Wi-Fi direct. Without a clear end-to-end path and relatively lower bandwidth, routing a message in DTN to the destination is difficult. But in some particular case, it could be an advantage. People around the world have their personal habit and it will be projected on their social life. Also, most people have their own routine to work or to school. Therefore we use the social behavior as a foundation feature of our routing algorithm.We propose two new kinds of routing algorithms with our own trace file. On one hand, birds of a feather flock together, so people who have similar interests tend to go to the same places. In case of this, we combining the personal interests and the trace file to different buildings where each node locates, we propose the building-based routing algorithm. On the other hand, we think people who have similar interests hang out together more often, so we use the social relationship as a feature and propose social-based routing algorithm. In the end, we compare our algorithms with Epidemic, MaxProp and PRoPHET routing algorithms. The result shows that our algorithms exceed the others in performance.參考文獻 [1] K. Fall, “A delay-tolerant network architecture for challenged internets.” in Proc. SIGCOMM, 2003.[2] E. P. C. Jones, L. Li, and P. A. S. Ward, “Practical routing in delay-tolerant networks,” in Proc. WDTN, 2005.[3] A.Lindgren, A.Doria, and O.Schelen, “Probabilistic routing in intermittently connected networks,” in Proc. SAPIR, 2004[4] Tzu-Chieh Tsai and Ho-Hsiang Chan, “NCCU Trace: social-network-aware mobility trace,” Communications Magazine, IEEE, vol. 53, pp. 144–149, 2015.[5] A. Vahdat and D. Becker, “Epidemic Routing for Partially Connected Ad Hoc Networks,” Tech. Rep. CS-2000- 06, Duke Univ., July 2000.[6] BURGESS, J., GALLAGHER, B., JENSEN, D., AND LEVINE, B. N. MaxProp: Routing for Vehicle-Based Disruption-Tolerant Networks. In Proceedings of IEEE Infocom (April 2006).[7] LINDGREN, A., DORIA, A., AND SCHELEN, O. Probabilistic routing in intermittently connected networks. In The First International Workshop on Service Assurance with Partial and Intermittent Resources (SAPIR) (2004).[8] Zhang, Xiaomei, and Guohong Cao. "Transient community detection and its application to data forwarding in delay tolerant networks." 2013 21st IEEE International Conference on Network Protocols (ICNP). IEEE, 2013.[9] Bigwood, Greg, et al. "Exploiting self-reported social networks for routing in ubiquitous computing environments." 2008 IEEE International Conference on Wireless and Mobile Computing, Networking and Communications. IEEE, 2008.[10] Sanguankotchakorn, Teerapat, Shradha Shrestha, and Nobuhiko Sugino. "Effective ad hoc social networking on OLSR MANET using similarity of interest approach." International Conference on Internet and Distributed Computing Systems. Springer Berlin Heidelberg, 2012.[11] A. Mei, G. Morabito, P. Santi and J. Stefa, “Social-aware stateless forwarding in pocket switched networks,” in Proc. 30th IEEE Conference on Computer Communications(INFOCOM) mini-conference, 2011.[12] K. Zhu, W. Li, and X. Fu. Rethinking routing information in mobile social networks: Location-based or social-based? Elsevier Computer Communications (to appear), 2014.[13] W. Gao, Q. Li, B. Zhao, G. Cao Multicasting in delay tolerant networks: a social network perspective MobiHoc ’09: Proceedings of the 10th ACM International Symposium on Mobile ad hoc Networking and Computing, ACM, New York, NY, USA (2009), pp. 299–308[14] N. Eagle and A. Pentland. Reality mining: sensing complex social systems. Personal and Ubiquitous Computing, Vol 10(4):255–268, May 2006.[15] P. Hui, People are the network: experimental design and evaluation of social-based forwarding algorithms, Ph.D. dissertation, UCAM-CL-TR-713. University of Cambridge, Comp.Lab., 2008[16] V. Srinivasan, M. Motani, and W. T. Ooi, “Analysis and implications of student contact patterns derived from campus schedules,” in Proc.ACM MobiCom, Los Angeles,CA, Sep.2006,pp.86–97.[17] P. Hui, J. Crowcroft, and E. Yoneki. Bubble rap: social-based forwarding in delay tolerant networks. Proc. MobiHoc, pages 241–250, 2008.[18] 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. INFOCOM, April 2006.[19] T. Karagiannis, J.-Y. Le Boudec, and M. Vojnovic, “Power law and exponential decay of inter contact times between mobile ´ devices,” in ACM MobiCom ’07, 2007.[20] J. Leguay, A. Lindgren, J. Scott, T. Friedman, and J. Crowcroft, “Opportunistic content distribution in an urban setting,” in ACM CHANTS, 2006, pp. 205–212.[21] Y. Zhang, W. Gao, G. Cao, T. L. Porta, B. Krishnamachari, and A. Iyengar, “Social-Aware Data Diffusion in Delay Tolerant MANET,” Handbook of Optimization in Complex Networks: Communication and Social Networks, 2010[22] E. Daly and M. Haahr, “Social network analysis for routing in disconnected delay-tolerant manets,” in Proceedings of ACM MobiHoc, 2007.[23] Socievole, Annalisa, Floriano De Rango, and Antonio Caputo. "Wireless contacts, Facebook friendships and interests: Analysis of a multi-layer social network in an academic environment." 2014 IFIP Wireless Days (WD). IEEE, 2014.[24] Cabrero, Sergio, et al. "Understanding Opportunistic Networking for Emergency Services: Analysis of One Year of GPS Traces." Proceedings of the 10th ACM MobiCom Workshop on Challenged Networks. ACM, 2015.[25] https://github.com/NCCU-MCLAB/NCCU-Trace-Data[26] A. Ker¨anen, J. Ott, and T. K¨arkk¨ainen. The ONE Simulator for DTN Protocol Evaluation. In Proceedings of the 2nd International Conference on Simulation Tools and Techniques, March 2009. 描述 碩士
國立政治大學
資訊科學學系
103753009資料來源 http://thesis.lib.nccu.edu.tw/record/#G0103753009 資料類型 thesis dc.contributor.advisor 蔡子傑 zh_TW dc.contributor.advisor Tsai, Tzu Chieh en_US dc.contributor.author (Authors) 陳柏錡 zh_TW dc.contributor.author (Authors) Chen, Po Chi en_US dc.creator (作者) 陳柏錡 zh_TW dc.creator (作者) Chen, Po Chi en_US dc.date (日期) 2016 en_US dc.date.accessioned 22-Aug-2016 11:07:08 (UTC+8) - dc.date.available 22-Aug-2016 11:07:08 (UTC+8) - dc.date.issued (上傳時間) 22-Aug-2016 11:07:08 (UTC+8) - dc.identifier (Other Identifiers) G0103753009 en_US dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/100500 - dc.description (描述) 碩士 zh_TW dc.description (描述) 國立政治大學 zh_TW dc.description (描述) 資訊科學學系 zh_TW dc.description (描述) 103753009 zh_TW dc.description.abstract (摘要) 耐延遲網路相較於一般的3G、4G或是Wi-Fi網路是相對受限的，只能利用節點之間短暫的相遇時利用Bluetooth以及Wi-Fi direct交流訊息，他不僅沒有穩定的連線能力，頻寬也相對較小。但耐延遲網路卻因是斷斷續續且可以傳送給現實中相遇的人，使他人幫忙攜帶訊息進而傳送至目的而成優點。因現今社會的人們大多有固定的行經路線像平日的上下班，亦或是學生一定有著固定的課表和交通路線。另外，有共同興趣的人也會朝著特定的地標前進，像喜歡運動的人會往運動中心集中、喜歡閱讀的人會往圖書館借閱書籍、喜歡文藝的人會賞閱展覽。這無形中讓我們可以利用耐延遲網路的方式傳送有特定屬性的廣告訊息給對這特定屬性有興趣的人們。我們在此論文中提出兩種在耐延遲網路上新的資料傳遞方式，我們集合人們有各自的喜好並以人們有相同路徑及有著相同興趣的人們會聚集的特性在人群中傳送訊息，我們預先用手機蒐集歷史資料並統計人群的移動模型再用以驗證未來節點相遇的情況。最後，我們將本論文方法與其它資料傳送方法比較評估效能，模擬結果顯示我們提出的傳送方法有較優的傳送成功率與相對較低的資源耗費。 zh_TW dc.description.abstract (摘要) Compared with 3G, 4G and Wi-Fi, Delay-Tolerant Networking (DTN) can only have intermittent chance to transmit messages with Bluetooth or Wi-Fi direct. Without a clear end-to-end path and relatively lower bandwidth, routing a message in DTN to the destination is difficult. But in some particular case, it could be an advantage. People around the world have their personal habit and it will be projected on their social life. Also, most people have their own routine to work or to school. Therefore we use the social behavior as a foundation feature of our routing algorithm.We propose two new kinds of routing algorithms with our own trace file. On one hand, birds of a feather flock together, so people who have similar interests tend to go to the same places. In case of this, we combining the personal interests and the trace file to different buildings where each node locates, we propose the building-based routing algorithm. On the other hand, we think people who have similar interests hang out together more often, so we use the social relationship as a feature and propose social-based routing algorithm. In the end, we compare our algorithms with Epidemic, MaxProp and PRoPHET routing algorithms. The result shows that our algorithms exceed the others in performance. en_US dc.description.tableofcontents CHAPTER 1 Introduction 91.1 Background & Motivation 91.2 Delay-Tolerant Network (DTN) 91.3 Cosine similarity 11CHAPTER 2 Related work 122.1 Social Trace Data 122.1.1 Reality mining: MIT [11] 122.1.2 Cambridge [12] 132.1.3 Infocom05, 06 [13] 142.2 Social-based in Delay-Tolerant Network 152.2.1 Social-Aware Data Diffusion in Delay Tolerant MANETs [18] 152.2.2 Social Network Analysis for Routing in Disconnected Delay-Tolerant MANETS [19] 16CHAPTER 3 NCCU Trace Data 163.1 Form (Selecting Participants) 173.1.1 College 173.1.2 Interest 183.2 Trace data 184 Routing Approach 194.1 Environment definition 194.2 Routing strategy 204.2.1 Direct Contact 214.2.2 Indirect Contact 214.2.2.1 Building Based Indirect Routing 214.2.2.2 Social Based Indirect Routing 25CHAPTER 5 Simulation settings 285.1 Simulation environment 285.2 Simulation setting 295.3 Simulation results 305.3.1 Delivery ratio 315.3.2 Overhead 325.3.3 Feature choosen insight 34CHAPTER 6 Conclusion and future work 36Reference 37 zh_TW dc.format.extent 2942728 bytes - dc.format.mimetype application/pdf - dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0103753009 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 Network en_US dc.subject (關鍵詞) campus environment en_US dc.subject (關鍵詞) personal information en_US dc.subject (關鍵詞) personal interest en_US dc.subject (關鍵詞) social relationship en_US dc.title (題名) 基於社交行為對興趣導向訊息之耐延遲網路傳輸策略 zh_TW dc.title (題名) An Interest-based Message Dissemination Approach with Social Behavior Consideration in Delay Tolerant Networks en_US dc.type (資料類型) thesis en_US dc.relation.reference (參考文獻) [1] K. Fall, “A delay-tolerant network architecture for challenged internets.” in Proc. SIGCOMM, 2003.[2] E. P. C. Jones, L. Li, and P. A. S. Ward, “Practical routing in delay-tolerant networks,” in Proc. WDTN, 2005.[3] A.Lindgren, A.Doria, and O.Schelen, “Probabilistic routing in intermittently connected networks,” in Proc. SAPIR, 2004[4] Tzu-Chieh Tsai and Ho-Hsiang Chan, “NCCU Trace: social-network-aware mobility trace,” Communications Magazine, IEEE, vol. 53, pp. 144–149, 2015.[5] A. Vahdat and D. Becker, “Epidemic Routing for Partially Connected Ad Hoc Networks,” Tech. Rep. CS-2000- 06, Duke Univ., July 2000.[6] BURGESS, J., GALLAGHER, B., JENSEN, D., AND LEVINE, B. N. MaxProp: Routing for Vehicle-Based Disruption-Tolerant Networks. In Proceedings of IEEE Infocom (April 2006).[7] LINDGREN, A., DORIA, A., AND SCHELEN, O. Probabilistic routing in intermittently connected networks. In The First International Workshop on Service Assurance with Partial and Intermittent Resources (SAPIR) (2004).[8] Zhang, Xiaomei, and Guohong Cao. "Transient community detection and its application to data forwarding in delay tolerant networks." 2013 21st IEEE International Conference on Network Protocols (ICNP). IEEE, 2013.[9] Bigwood, Greg, et al. "Exploiting self-reported social networks for routing in ubiquitous computing environments." 2008 IEEE International Conference on Wireless and Mobile Computing, Networking and Communications. IEEE, 2008.[10] Sanguankotchakorn, Teerapat, Shradha Shrestha, and Nobuhiko Sugino. "Effective ad hoc social networking on OLSR MANET using similarity of interest approach." International Conference on Internet and Distributed Computing Systems. Springer Berlin Heidelberg, 2012.[11] A. Mei, G. Morabito, P. Santi and J. Stefa, “Social-aware stateless forwarding in pocket switched networks,” in Proc. 30th IEEE Conference on Computer Communications(INFOCOM) mini-conference, 2011.[12] K. Zhu, W. Li, and X. Fu. Rethinking routing information in mobile social networks: Location-based or social-based? Elsevier Computer Communications (to appear), 2014.[13] W. Gao, Q. Li, B. Zhao, G. Cao Multicasting in delay tolerant networks: a social network perspective MobiHoc ’09: Proceedings of the 10th ACM International Symposium on Mobile ad hoc Networking and Computing, ACM, New York, NY, USA (2009), pp. 299–308[14] N. Eagle and A. Pentland. Reality mining: sensing complex social systems. Personal and Ubiquitous Computing, Vol 10(4):255–268, May 2006.[15] P. Hui, People are the network: experimental design and evaluation of social-based forwarding algorithms, Ph.D. dissertation, UCAM-CL-TR-713. University of Cambridge, Comp.Lab., 2008[16] V. Srinivasan, M. Motani, and W. T. Ooi, “Analysis and implications of student contact patterns derived from campus schedules,” in Proc.ACM MobiCom, Los Angeles,CA, Sep.2006,pp.86–97.[17] P. Hui, J. Crowcroft, and E. Yoneki. Bubble rap: social-based forwarding in delay tolerant networks. Proc. MobiHoc, pages 241–250, 2008.[18] 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. INFOCOM, April 2006.[19] T. Karagiannis, J.-Y. Le Boudec, and M. Vojnovic, “Power law and exponential decay of inter contact times between mobile ´ devices,” in ACM MobiCom ’07, 2007.[20] J. Leguay, A. Lindgren, J. Scott, T. Friedman, and J. Crowcroft, “Opportunistic content distribution in an urban setting,” in ACM CHANTS, 2006, pp. 205–212.[21] Y. Zhang, W. Gao, G. Cao, T. L. Porta, B. Krishnamachari, and A. Iyengar, “Social-Aware Data Diffusion in Delay Tolerant MANET,” Handbook of Optimization in Complex Networks: Communication and Social Networks, 2010[22] E. Daly and M. Haahr, “Social network analysis for routing in disconnected delay-tolerant manets,” in Proceedings of ACM MobiHoc, 2007.[23] Socievole, Annalisa, Floriano De Rango, and Antonio Caputo. "Wireless contacts, Facebook friendships and interests: Analysis of a multi-layer social network in an academic environment." 2014 IFIP Wireless Days (WD). IEEE, 2014.[24] Cabrero, Sergio, et al. "Understanding Opportunistic Networking for Emergency Services: Analysis of One Year of GPS Traces." Proceedings of the 10th ACM MobiCom Workshop on Challenged Networks. ACM, 2015.[25] https://github.com/NCCU-MCLAB/NCCU-Trace-Data[26] A. Ker¨anen, J. Ott, and T. K¨arkk¨ainen. The ONE Simulator for DTN Protocol Evaluation. In Proceedings of the 2nd International Conference on Simulation Tools and Techniques, March 2009. zh_TW
