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 two-phase network coding design for mobile time-valued group-message dissemination
作者 劉亭侁
Liu, Ting Shen
貢獻者 蔡子傑
Tsai, Tzu Chieh
劉亭侁
Liu, Ting Shen
關鍵詞 聊天應用程式
間歇性連接網路
廣播傳輸
網絡編碼
政大軌跡紀錄
機會性社群網路
Chat App
Intermittently Connected Networks
Broadcast
Network Coding
NCCU Trace Data
Opportunistic Mobile Social Network
日期 2017
上傳時間 8-Feb-2017 16:42:03 (UTC+8)
摘要 現今因無線通訊技術的進步，使得人們能方便地利用智慧型裝置透過3G，4G和Wi-Fi等技術彼此溝通聊天。其中，聊天應用是最受智慧型裝置使用者歡迎的應用程式。大部分的聊天應用程式需依賴網路以達到訊息交換的目的。然而網路的頻寬是非常有限的，當使用者處在擁擠的環境中時，他們可能會面臨資源耗盡問題。此外，例如在漫遊的情況下有些使用者並沒有行動網路的存取，導致使用者無法使用聊天應用。

因此我們希望利用無線廣播傳輸的特性，開發一個應用於間歇性網路連接的聊天應用程式。然而，廣播傳輸的散播策略若沒有設計得宜，可能導致廣播風暴的問題，使得整體網路效能低落。我們研究的目標是要如何在間歇性網路增加訊息的傳輸效率。為了達成此目標，在我們的研究中考量了許多技術要求，如：訊息具有截止時間與優先權特性、多聊天室應用、傳輸效率。

我們提出了一種兩階段基於網絡編碼設計的訊息散播方法，實現在機會性社群網路中的訊息散播。網絡編碼階段，提高網路頻寬的傳輸效率，也能增加網路傳輸的可靠性；預熱階段能提升網路編碼訊息被解開的機率。最後，利用政大的真實軌跡紀錄評估我們所設計的訊息傳播方法。結果顯示，我們的方法是有效率且優於氾濫式的路由協議和一般的網絡編碼散播技術。
Nowadays, the advancement of wireless communication technology has allowed people to use smart phones to communicate with each other more easily via 3G/4G, Wi-Fi, etc. One kind of popular mobile Apps is “chat” App. Most chat Apps rely on the Internet to exchange the messages. However, the bandwidth of network is limited in some circumstances. When users stay in the crowded environment, they will face the resource depletion problem. Besides, some people may not subscribe to any cellular network access, e.g. in roaming scenarios.

Therefore, we want to develop a novel mobile Chat APP in intermittently connected networks. We utilize the characteristic of the wireless broadcast transmission. However, it may cause the broadcast storm problem without careful design. How to increase the efficiency of message delivery in such intermittently connected networks is our research goal. To achieve this, technical issues in our research involve message priority, multi-chatroom, deadline and transmission efficiency.

We proposed a two-phase network coding design for message dissemination to enable the multi-hop instant messaging in Opportunistic Mobile Social Networks. The network coding phase can increase the bandwidth utility and transmission efficiency. Moreover, it can improve transmission robustness and adaptability. The warm up phase can increase the decoding probability of coded packets. Finally, we evaluated our approach with real trace data from NCCU. The results showed that our approach is effective and superior to the flooding based routing protocol and the pure network coding technique.
參考文獻 [1] FireChat: https://opengarden.com/firechat
[2] Yu-Chee Tseng , Sze-Yao Ni , Yuh-Shyan Chen , Jang-Ping Sheu, The broadcast storm problem in a mobile ad hoc network, Wireless Networks, v.8 n.2/3, p.153-167, March-May 2002
[3] R. Ahlswede, N. Cai, S.-Y. R. Li and R. W. Yeung, "Network information flow," IEEE Trans. On Information Theory, vol. 46, pp. 1204-1216, 2000.
[4] K. Fall, “A delay-tolerant network architecture for challenged internets.” in Proc. SIGCOMM, 2003.
[5] Jian Shen, Sangman Moh, and Ilyong Chung, “Routing Protocols in Delay Tolerant Networks: A Comparative Survey” in International Technical Conference on Circuits/Systems, Computers and Communications (ITC-CSCC’ 08), July 2008
[6] T. Ho, R. Koetter, M. Medard, D. R. Karger, and M.Effros. “The benefits of coding over routing in a randomized setting”International Symposium on Information Theory (ISIT), page 442, July 2003
[7] R. H. Frenkiel, B. R. Badrinath, J. Borres, and R. D. Yates, “The infostations challenge: balancing cost and ubiquity in delivering wireless data,” IEEE Personal Communications, vol. 7, no. 2, pp. 66–71, 2000
[8] A. Demers, D. Greene, C. Houser, W. Irish, J. Larson, S. Shenker, H. Sturgis, D. Swinehart, and D. Terry,“Epidemic algorithms for replicated database maintenance,” SIGOPS Operating Systems Review, vol. 22, pp. 8–32, January 1988.
[9] TSAI, Tzu-Chieh; CHAN, Ho-Hsiang. NCCU Trace: social-network-aware mobility trace. IEEE Communications Magazine, 2015, 53.10: 144-149.
[10] N. Eagle and A. Pentland. Reality mining: sensing complex social systems. Personal and Ubiquitous Computing, Vol 10(4):255–268, May 2006.
[11] 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
[12] 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.
[13] CHEN, Yuanzhu, et al. Delay-tolerant networks and network coding: Comparative studies on simulated and real device experiments. Computer Networks, 2015, 83: 349-362.
[14] OSTOVARI, Pouya; KHREISHAH, Abdallah; WU, Jie. Broadcasting with hard deadlines in wireless multihop networks using network coding. Wireless Communications and Mobile Computing, 2015, 15.5: 983-999.
[15] Ostovari, Pouya, Jie Wu, and Abdallah Khreishah. "Deadline-aware broadcasting in wireless networks with local network coding." Computing, Networking and Communications (ICNC), 2012 International Conference on. IEEE, 2012.
[16] Spyropoulos, Thrasyvoulos, Konstantinos Psounis, and Cauligi S. Raghavendra. "Spray and wait: an efficient routing scheme for intermittently connected mobile networks." Proceedings of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking. ACM, 2005.
[17] Xiao, Mingjun, Jie Wu, and Liusheng Huang. "Community-aware opportunistic routing in mobile social networks." IEEE Transactions on Computers 63.7 (2014): 1682-1695.
[18] Jorg Widmer, Jean-Yves Le Boudec, Network coding for efficient communication in extreme networks, in: Proceedings of the 2005 ACM SIGCOMM Workshop on Delay-Tolerant Networking, 2005, pp. 284–291.
[19] 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.
[20] 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.
[21] 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.
[22] 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.
[23] https://github.com/NCCU-MCLAB/NCCU-Trace-Data
[24] L. Li, R. Ramjee, M. Buddhikot, and S. Miller, “Network coding-based broadcast in mobile ad-hoc networks,” in IEEE INFOCOM, May 2007.
[25] http://www.investopedia.com/terms/t/timevalue.asp
[26] 郭振茂, "淺談選擇權評價Black-Scholes 公式中希臘字母的應用", 2003
[27] https://en.wikipedia.org/wiki/Greeks_(finance)
[28] 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.
[29] Marin, Radu-Corneliu, Ciprian Dobre, and Fatos Xhafa. "Exploring Predictability in Mobile Interaction." EIDWT. 2012.
描述 碩士
國立政治大學
資訊科學學系
103753010
資料來源 http://thesis.lib.nccu.edu.tw/record/#G0103753010
資料類型 thesis
dc.contributor.advisor 蔡子傑zh_TW
dc.contributor.advisor Tsai, Tzu Chiehen_US
dc.contributor.author (Authors) 劉亭侁zh_TW
dc.contributor.author (Authors) Liu, Ting Shenen_US
dc.creator (作者) 劉亭侁zh_TW
dc.creator (作者) Liu, Ting Shenen_US
dc.date (日期) 2017en_US
dc.date.accessioned 8-Feb-2017 16:42:03 (UTC+8)-
dc.date.available 8-Feb-2017 16:42:03 (UTC+8)-
dc.date.issued (上傳時間) 8-Feb-2017 16:42:03 (UTC+8)-
dc.identifier (Other Identifiers) G0103753010en_US
dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/106436-
dc.description (描述) 碩士zh_TW
dc.description (描述) 國立政治大學zh_TW
dc.description (描述) 資訊科學學系zh_TW
dc.description (描述) 103753010zh_TW
dc.description.abstract (摘要) 現今因無線通訊技術的進步，使得人們能方便地利用智慧型裝置透過3G，4G和Wi-Fi等技術彼此溝通聊天。其中，聊天應用是最受智慧型裝置使用者歡迎的應用程式。大部分的聊天應用程式需依賴網路以達到訊息交換的目的。然而網路的頻寬是非常有限的，當使用者處在擁擠的環境中時，他們可能會面臨資源耗盡問題。此外，例如在漫遊的情況下有些使用者並沒有行動網路的存取，導致使用者無法使用聊天應用。

因此我們希望利用無線廣播傳輸的特性，開發一個應用於間歇性網路連接的聊天應用程式。然而，廣播傳輸的散播策略若沒有設計得宜，可能導致廣播風暴的問題，使得整體網路效能低落。我們研究的目標是要如何在間歇性網路增加訊息的傳輸效率。為了達成此目標，在我們的研究中考量了許多技術要求，如：訊息具有截止時間與優先權特性、多聊天室應用、傳輸效率。

我們提出了一種兩階段基於網絡編碼設計的訊息散播方法，實現在機會性社群網路中的訊息散播。網絡編碼階段，提高網路頻寬的傳輸效率，也能增加網路傳輸的可靠性；預熱階段能提升網路編碼訊息被解開的機率。最後，利用政大的真實軌跡紀錄評估我們所設計的訊息傳播方法。結果顯示，我們的方法是有效率且優於氾濫式的路由協議和一般的網絡編碼散播技術。		zh_TW
dc.description.abstract (摘要) Nowadays, the advancement of wireless communication technology has allowed people to use smart phones to communicate with each other more easily via 3G/4G, Wi-Fi, etc. One kind of popular mobile Apps is “chat” App. Most chat Apps rely on the Internet to exchange the messages. However, the bandwidth of network is limited in some circumstances. When users stay in the crowded environment, they will face the resource depletion problem. Besides, some people may not subscribe to any cellular network access, e.g. in roaming scenarios.

Therefore, we want to develop a novel mobile Chat APP in intermittently connected networks. We utilize the characteristic of the wireless broadcast transmission. However, it may cause the broadcast storm problem without careful design. How to increase the efficiency of message delivery in such intermittently connected networks is our research goal. To achieve this, technical issues in our research involve message priority, multi-chatroom, deadline and transmission efficiency.

We proposed a two-phase network coding design for message dissemination to enable the multi-hop instant messaging in Opportunistic Mobile Social Networks. The network coding phase can increase the bandwidth utility and transmission efficiency. Moreover, it can improve transmission robustness and adaptability. The warm up phase can increase the decoding probability of coded packets. Finally, we evaluated our approach with real trace data from NCCU. The results showed that our approach is effective and superior to the flooding based routing protocol and the pure network coding technique.		en_US
dc.description.tableofcontents CHAPTER 1 Introduction 1
1.1 Background & Motivation 1
1.2 Goal 2
1.3 Opportunistic Mobile Social Network 3
1.4 Network Coding 4
CHAPTER 2 Related work 6
2.1 Social Trace Data 6
2.1.1 Reality Mining: MIT 6
2.1.2 Cambridge 7
2.1.3 INFOCOM 8
2.1.4 UPB Trace 8
2.1.5 NCCU 9
2.2 Flooding-based routing protocol 9
2.2.1 Direct Delivery Routing Protocol 9
2.2.2 Epidemic Routing protocol 10
2.2.3 Spray and wait routing protocol 10
2.3 Network coding technique in the network 11
2.3.1 Delay-tolerant networks and network coding 11
2.3.2 Broadcasting with hard deadlines in wireless multi-hop networks 11
2.3.3 Deadline-aware Broadcasting in Wireless Networks 12
CHAPTER 3 NCCU Trace Data 13
3.1 The composition of trace data 14
3.1.1 Participant 14
3.1.2 Interest Relation 14
3.1.3 Trace Data 15
CHAPTER 4 A Two-Phase Network Coding Design for Mobile Time-valued Group-message Dissemination 16
4.1 Environment Definition 16
4.2 Time Value 18
4.3 Warm Up phase 22
4.4 Network Coding Phase 22
4.5 2-Phase: Dynamic Threshold 23
4.6 Activity Ratio (AR) 25
4.7 Meta-data 26
4.8 Buffer management 28
4.9 Routing Strategy 29
4.9.1 Exchange Meta-data 29
4.9.2 Generate Message Candidate Set (CS) 30
4.9.3 Message Forwarding Sequence 33
4.9.4 Update Meta-data 36
Chapter 5 Simulation setting 37
5.1 Simulation environment 37
5.2 Simulation Setting 38
5.3 Simulation results 40
5.3.1 Delivery ratio 41
5.3.2 Delay time 42
5.3.3 Time value 43
5.3.4 Overhead ratio 44
5.4 Insight Analysis 45
5.4.1 Delivery Ratio 45
5.4.2 Dynamic 2-phase Optimization 47
5.4.3 Other method 49
Chapter 6 Conclusion and Future Work 50
Reference 51		zh_TW
dc.format.extent 2089558 bytes-
dc.format.extent 2089558 bytes-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0103753010en_US
dc.subject (關鍵詞) 聊天應用程式zh_TW
dc.subject (關鍵詞) 間歇性連接網路zh_TW
dc.subject (關鍵詞) 廣播傳輸zh_TW
dc.subject (關鍵詞) 網絡編碼zh_TW
dc.subject (關鍵詞) 政大軌跡紀錄zh_TW
dc.subject (關鍵詞) 機會性社群網路zh_TW
dc.subject (關鍵詞) Chat Appen_US
dc.subject (關鍵詞) Intermittently Connected Networksen_US
dc.subject (關鍵詞) Broadcasten_US
dc.subject (關鍵詞) Network Codingen_US
dc.subject (關鍵詞) NCCU Trace Dataen_US
dc.subject (關鍵詞) Opportunistic Mobile Social Networken_US
dc.title (題名) 考慮時間價值的兩階段群組訊息網路編碼的散播機制zh_TW
dc.title (題名) A two-phase network coding design for mobile time-valued group-message disseminationen_US
dc.type (資料類型) thesisen_US
dc.relation.reference (參考文獻) [1] FireChat: https://opengarden.com/firechat
[2] Yu-Chee Tseng , Sze-Yao Ni , Yuh-Shyan Chen , Jang-Ping Sheu, The broadcast storm problem in a mobile ad hoc network, Wireless Networks, v.8 n.2/3, p.153-167, March-May 2002
[3] R. Ahlswede, N. Cai, S.-Y. R. Li and R. W. Yeung, "Network information flow," IEEE Trans. On Information Theory, vol. 46, pp. 1204-1216, 2000.
[4] K. Fall, “A delay-tolerant network architecture for challenged internets.” in Proc. SIGCOMM, 2003.
[5] Jian Shen, Sangman Moh, and Ilyong Chung, “Routing Protocols in Delay Tolerant Networks: A Comparative Survey” in International Technical Conference on Circuits/Systems, Computers and Communications (ITC-CSCC’ 08), July 2008
[6] T. Ho, R. Koetter, M. Medard, D. R. Karger, and M.Effros. “The benefits of coding over routing in a randomized setting”International Symposium on Information Theory (ISIT), page 442, July 2003
[7] R. H. Frenkiel, B. R. Badrinath, J. Borres, and R. D. Yates, “The infostations challenge: balancing cost and ubiquity in delivering wireless data,” IEEE Personal Communications, vol. 7, no. 2, pp. 66–71, 2000
[8] A. Demers, D. Greene, C. Houser, W. Irish, J. Larson, S. Shenker, H. Sturgis, D. Swinehart, and D. Terry,“Epidemic algorithms for replicated database maintenance,” SIGOPS Operating Systems Review, vol. 22, pp. 8–32, January 1988.
[9] TSAI, Tzu-Chieh; CHAN, Ho-Hsiang. NCCU Trace: social-network-aware mobility trace. IEEE Communications Magazine, 2015, 53.10: 144-149.
[10] N. Eagle and A. Pentland. Reality mining: sensing complex social systems. Personal and Ubiquitous Computing, Vol 10(4):255–268, May 2006.
[11] 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
[12] 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.
[13] CHEN, Yuanzhu, et al. Delay-tolerant networks and network coding: Comparative studies on simulated and real device experiments. Computer Networks, 2015, 83: 349-362.
[14] OSTOVARI, Pouya; KHREISHAH, Abdallah; WU, Jie. Broadcasting with hard deadlines in wireless multihop networks using network coding. Wireless Communications and Mobile Computing, 2015, 15.5: 983-999.
[15] Ostovari, Pouya, Jie Wu, and Abdallah Khreishah. "Deadline-aware broadcasting in wireless networks with local network coding." Computing, Networking and Communications (ICNC), 2012 International Conference on. IEEE, 2012.
[16] Spyropoulos, Thrasyvoulos, Konstantinos Psounis, and Cauligi S. Raghavendra. "Spray and wait: an efficient routing scheme for intermittently connected mobile networks." Proceedings of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking. ACM, 2005.
[17] Xiao, Mingjun, Jie Wu, and Liusheng Huang. "Community-aware opportunistic routing in mobile social networks." IEEE Transactions on Computers 63.7 (2014): 1682-1695.
[18] Jorg Widmer, Jean-Yves Le Boudec, Network coding for efficient communication in extreme networks, in: Proceedings of the 2005 ACM SIGCOMM Workshop on Delay-Tolerant Networking, 2005, pp. 284–291.
[19] 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.
[20] 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.
[21] 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.
[22] 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.
[23] https://github.com/NCCU-MCLAB/NCCU-Trace-Data
[24] L. Li, R. Ramjee, M. Buddhikot, and S. Miller, “Network coding-based broadcast in mobile ad-hoc networks,” in IEEE INFOCOM, May 2007.
[25] http://www.investopedia.com/terms/t/timevalue.asp
[26] 郭振茂, "淺談選擇權評價Black-Scholes 公式中希臘字母的應用", 2003
[27] https://en.wikipedia.org/wiki/Greeks_(finance)
[28] 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.
[29] Marin, Radu-Corneliu, Ciprian Dobre, and Fatos Xhafa. "Exploring Predictability in Mobile Interaction." EIDWT. 2012.		zh_TW