系統識別號 | U0002-1607201218321300 |
---|---|
DOI | 10.6846/TKU.2012.00656 |
論文名稱(中文) | 基於社群網路與賽局理論之新型點對點分享機制之研究 |
論文名稱(英文) | A Novel P2P Sharing Mechanism based on Social Network and Game Theory |
第三語言論文名稱 | |
校院名稱 | 淡江大學 |
系所名稱(中文) | 電機工程學系碩士班 |
系所名稱(英文) | Department of Electrical and Computer Engineering |
外國學位學校名稱 | |
外國學位學院名稱 | |
外國學位研究所名稱 | |
學年度 | 100 |
學期 | 2 |
出版年 | 101 |
研究生(中文) | 王子銘 |
研究生(英文) | Tzu-Ming Wang |
學號 | 699450069 |
學位類別 | 碩士 |
語言別 | 繁體中文 |
第二語言別 | |
口試日期 | 2012-06-14 |
論文頁數 | 60頁 |
口試委員 |
指導教授
-
李維聰
委員 - 朱國志 委員 - 劉豐豪 委員 - 衛信文 委員 - 吳庭育 |
關鍵字(中) |
點對點分享系統 獎懲機制 社群網路 賽局理論 |
關鍵字(英) |
P2P Incentive mechanism Social network Game theory |
第三語言關鍵字 | |
學科別分類 | |
中文摘要 |
近年來,隨著點對點傳輸技術的興起,許多用於點對點傳輸的軟體相繼出現,而如何有效的抑制free-riders一直是重要的議題,根據統計,大多數的點對點傳輸軟體採用Gnutella和BitTorrent協定, BitTorrent使用Choking algorithm來抑制free-riders,Choking algorithm只是單純的給予free-riders阻塞,Gnutella使用EigenTrust algorithm來打擊惡意節點,而現實證明EigenTrust algorithm不夠完善,所以兩者的效果都不好,根據2005年統計,在Gnutella網路中有85%的使用者是free-riders,甚至只有1%的使用者主動分享新的檔案。 由於點對點傳輸的軟體上的資源猶如公有資源,所有人都可以使用,以至於大多數的人都不願意分享自身的資源,造成社會困境,導致效率低落,因此本論文將導入社群網路的資料,透過長期的合作促進節點分享,也同時透過社群網路中節點間的關係排斥free-riders。 在本論文提出的系統架構中,我們將考慮各使用者的上傳頻寬、計算能力與電力等因素給與使用者籌碼,這些籌碼將儲存在伺服器中,由伺服器統一管理。系統分享檔案的模式可以分為即時影像傳流分享與檔案分享。在即時影像串流分享系統中,使用者可以使用其籌碼參與競標高畫質即時影像串流的門票。在檔案分享系統中,使用者每時間區段都必須為每單位的下載頻寬支付一定數量的籌碼,換句話說,使用者在本系統中必須使用這些籌碼來競標或購買系統的服務,如此一來,籌碼系統便能夠促進使用者自發性的分享自身的資源。 |
英文摘要 |
In recent years, with the emergence of P2P technology, there are many of the applications for P2P technology has emerged and how to effectively inhibit the free-riders is a hot issue. According to statistics, most of the P2P applications used Gnutella protocol and BitTorrent protocol. BitTorrent uses the Choking algorithm to isolate free-riders, but Choking algorithm is simply giving free-riders choke. Gnutella uses the EigenTrust algorithm to combat free-riders. However according to the actuality, EigenTrust algorithm is not a consummated algorithm. Therefore, both of Choking algorithm and EigenTrust algorithm have a bed effect. A research was conducted in 2005, there are nearly 85 percent of Gnutella network users are free-riders from all users. Furthermore, there is only 1 percent of users voluntary to share new files. Due to the resource in the P2P applications are like public goods that everyone can use it for free. It makes most of the users were not sharing their own resource, to cause tragedy of the commons and inefficiency. Therefore, in this paper, we propose an incentive mechanism on the basis of game theory; it promotes the peers to spontaneous sharing their own resource. We also use social network to promote users to share their resource, to maintain a long-term cooperation between users, and also use user's relationship of social network to exclude free-riders. To deploy the mechanism to the architecture, the system will give users counters by considering bandwidth, computing power and electricity of each user. These counters will be stored in server and managed by server. In addition, the sharing model of the system can be divided into live media streaming sharing and file sharing. In live media streaming sharing, users can participate in the auction and using their counters to bid the tickets of high-quality live media streaming. In file sharing, users have to pay counters for every unit download bandwidth. In other words, users need to use the counters to bid or buy service from server. Therefore, the mechanism can promotes the peers to spontaneous sharing their own resource if they need some resources from server. |
第三語言摘要 | |
論文目次 |
第一章 緒論 1 1.1 前言 1 1.2 動機與目的 2 1.3 論文章節架構 4 第二章 相關研究與背景資料 6 2.1 P2P檔案分享架構 6 2.1.1 BitTorrent架構 8 2.1.2 Gnutella架構 12 2.1.3 Private tracker架構 14 2.2 社群網路 15 2.3 賽局理論 16 2.3.1 帕瑞圖最優(Pareto Efficiency) 18 2.4 (k,t)-強健(robust) 20 2.5 研究問題 21 第三章 新式P2P檔案分享機制 23 3.1 平台架構 23 3.2 獎懲機制 25 3.2.1 籌碼機制 25 3.2.2 競標與購買服務 28 3.3 系統強健性 30 3.4 Turing machine 31 第四章 模擬結果與效能分析 33 4.1 模擬環境 33 4.1.1 進化賽局理論模型 33 4.1.2 系統公平性 40 4.2 各重要參數分析 41 4.2.1 各參數權重值之趨勢 46 4.2.2 不同狀況下之權重值等級 48 4.3 系統賽局模擬 52 4.4 主要貢獻 55 第五章 結論與未來展望 56 參考文獻 58 圖目錄 圖2.1 集中式系統架構 7 圖2.2 P2P系統架構 7 圖2.3 分散式雜P2P架構系統 9 圖2.4 Kademlia DHT路由結構 10 圖3.1 NIM系統架構 24 圖3.2 節點籌碼簡單狀態圖 27 圖4.1 兩個系統中節點選擇策略0的比例 39 圖4.2 NIM系統公平性 41 圖4.3 傳統點對點分享賽局之報酬分析 42 圖4.4 參賽者A、B、C、D之社群關係 44 圖4.5 考慮系統效能之參賽者報酬分析 45 圖4.6 上傳頻寬貢獻度影響參賽者之報酬分析 46 圖4.7 新節點與一般節點所得籌碼變化 49 圖4.8 行動裝置節點與一般節點所得籌碼變化 51 圖4.9 模擬結果 54 表目錄 表2.1 囚徒困境之相對報酬 17 表4.1 本機制之參賽者報酬矩陣 43 表4.2 考慮社群網路之參賽者報酬矩陣 44 表4.3 新節點與一般節點之初始參數值 49 表4.4 行動節點與一般節點之初始參數值 51 表4.5 模擬設定參數 53 |
參考文獻 |
[1] Brownson O. Obele, Augustine I.Ukaegbu, Minho Kang, “On Tackling Free-riders in P2P Networks,” 11th International Conference on Advanced Communication Technology, 15-18 Feb. 2009, Vol. 03, pp. 2084-2089. [2] Fabian Rozario, Zhu Han, Dusit Niyato, “Optimization of non-cooperative P2P network from the game theory point of view,” 2011 IEEE Wireless Communications and Networking Conference, 28-31 March 2011, USA, pp.868-873. [3] Daniel Hughes, Geoff Coulson, James Walkerdine, “Free riding on Gnutella revisited: the bell tolls?,” IEEE Distributed Systems Online, Vol. 6, Issue 6, 2005. [4] Tzu-Ming Wang, Wei-Tsong Lee, Tin-Yu Wu, Hsin-Wen Wei, Yu-San Lin, “New P2P Sharing Incentive Mechanism Based on Social Network and Game Theory,” 2012 26th International Conference on Advanced Information Networking and Applications Workshops, 26-29 March 2012, pp. 915-990. [5] Xiaowei Chen; Xiaowen Chu; Yixin Jiang; Fengyuan Ren, “Measurements, analysis and modeling of private tracker sites,” 2010 18th International Workshop on Quality of Service, 16-18 June 2010, China, pp.1-2. [6] Jiayin Qi, Hongli Zhang, Zhenzhou Ji, Liuyun, “Analyzing BitTorrent Traffic Across Large Network,” 2008 International Conference on Cyberworlds, 22-24 Sept. 2008, Harbin, pp.759-764. [7] Mehyar, M.; WeiHsin Gu; Low, S.H.; Effros, M.; Ho, T., “Optimal Strategies for Efficient Peer-to-Peer File Sharing,”2007 IEEE International Conference on Acoustics, Speech and Signal Processing, 15-20 April 2007, Vol 4, pp. IV-1337 - IV-1340. [8] 柯 佳 宏, 曾 黎 明, “Building a Locality-aware P2P System Based on Cache Collaboration,” 國立中央大學碩士畢業論文, 中華民國95年7月. [9] Portmann, M.; Sookavatana, P.; Ardon, S.; Seneviratne, A., “The Cost of Peer Discovery and Searching in the Gnutella Peer-to-peer File Sharing Protocol,” Ninth IEEE International Conference on Networks, 2001. Proceedings, 10-12 Oct. 2001, Australia, pp.263-268. [10] Altmann, J.; Bedane, Z.B., “A P2P File Sharing Network Topology Formation Algorithm Based on Social Network Information,” IEEE INFOCOM Workshops 2009, 19-25 April 2009, pp. 1-6. [11] Abboud, Osama; Zinner, Thomas; Lidanski, Eduardo; Pussep, Konstantin; Steinmetz, Ralf, “StreamSocial: A P2P Streaming System with Social Incentives,” 2010 IEEE International Symposium on a World of Wireless Mobile and Multimedia Networks, 14-17 June 2010, pp1-2. [12] Mani, M.; Ngyuen, A.-M.; Crespi, N., “What’s up: P2P Spontaneous Social Networking,” IEEE International Conference on Pervasive Computing and Communications, 9-13 March 2009, pp.1-2. [13] Huibin Feng; Shunyi Zhang; Chao Liu; Junrong Yan; Ming Zhang, “ P2P Incentive Model On Evolutionary Game Theory,” 4th International Conference on Wireless Communications, Networking and Mobile Computing, 12-14 Oct. 2008, pp.1-4. [14] Ouyang Jing-cheng; Wang Yue-bin; Hu Xu-huai; Lin Ya-ping, “An Incentive Mechanism Using Game Theory for P2P Networks,” NSWCTC '09. International Conference on Networks Security, Wireless Communications and Trusted Computing, 25-26 April 2009, Vol. 2, pp.715-718. [15] Chunzhi Wang; Ke Zhou; Hongwei Chen; Li Chen, “A Game Model of P2P Based on Punishment Strategies,” 2010 2nd International Symposium on Information Engineering and Electronic Commerce, 23-25 July 2010, China, pp. 1-3. [16] Jaeok Park; van der Schaar, M., “A Game Theoretic Analysis of Incentives in Content Production and Sharing Over Peer-to-Peer Networks,” IEEE Journal of Selected Topics in Signal Processing, Aug. 2010, USA, Vol. 4, pp. 704-717. [17] Mani, M.; Anh-Minh Nguyen; Crespi, N., “SCOPE: A prototype for spontaneous P2P social networking,” 2010 8th IEEE International Conference on Pervasive Computing and Communications Workshops , March 29 2010-April 2 2010, France, pp. 220-225. [18] Jongtack Kim; Yugyung Lee; Saewoong Bahk, “SALSA: Super-Peer Assisted Live Streaming Architecture,” IEEE International Conference on Communications, 14-18 June 2009, South Korea, pp. 1-5. [19] Ittai Abraham, Lorenzo Alvisi, Joseph Y. Halpern, “Distributed Computing Meets Game Theory:Combining Insights From Two Fields,” ACM SIGACT News, June 2011, Vol. 42, no. 2, pp. 69-76. [20] Seungyun Cho, Thinh Nguyen, “Modeling and Dynamics Analysis of P2P Networks based on Evolutionary Games,” First International Conference on Advances in P2P Systems, 11-16 Oct. 2009, USA, pp. 34-38. [21] Bin Fan; Lui, J.C.S.; Dah-Ming Chiu, “The design trade-off of bittorrent-like file sharing protocols,” IEEE/ACM Transactions on Networking, April 2009, Hong Kong, Vol. 17, Issue 2, pp. 365-376. |
論文全文使用權限 |
如有問題,歡迎洽詢!
圖書館數位資訊組 (02)2621-5656 轉 2487 或 來信