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

題名 基於耐延遲網路之移動式信任者與獎勵機制設計
Mobile trusted bank and incentive strategy design in delay tolerant networks
作者 林昶瑞
Lin, Chan Juei
貢獻者 蔡子傑
Tsai, Tzu Chieh
林昶瑞
Lin, Chan Juei
關鍵詞 耐延遲網路
獎勵機制
自私節點
DTN
Incentive
Selfish
日期 2011
上傳時間 30-Oct-2012 14:01:31 (UTC+8)
摘要 DTN(Delay Tolerant Networks)是一種缺乏網路基礎設備的網路架構，在這類的網路架構下，無線節點之間的通訊連線並非同時存在，而是間歇式建立的。因為節點的移動、或是裝置省電模式運作與環境因素的影響，造成連線可能不定時的失效。有不保證連線特性的網路，在DTN網路中節點間相遇的機會很少，節點間利用 Store-Carry-Forward 的方式傳遞訊息，且有相當長的傳遞延遲(Propagation Delay)。在這樣的網路特性下，傳統的文獻中，都是假設所有節點都會幫忙傳遞。但不幸的，在現實生活中有自私節點(Selfish Nodes)的存在，因自己本身設備資源有限，如電力資源、網路資源...等，節點不願意幫忙傳送訊息，這些自私節點的存在，會對DTN網路架構造成破壞，導致無法傳送訊息到目的地。為了解決自私節點的問題，我們提出了MTBIS(Mobile Trusted Bank of Incentive Strategies)，當發送節點(Source Node)要求傳送訊息時，給予回饋給幫忙轉傳訊息的節點，來鼓勵節點間互相幫忙傳送訊息，我們稱這些回饋為Incentive Credit。而節點也可利用Incentive Credit來要求別的節點幫忙轉傳訊息。另外也加入SI(Social Incentive)機制，與DGT(Dynamic Grudger Threshold) ，吸引自私節點願意幫忙轉傳訊息，改進了 MTBIS 在自私節點環境下的不足， 利用經濟學的角度來解決節點運用Credit的問題，借此提高訊息的傳遞率(Delivery Ratio)。
本篇研究也注重於自私節點的模擬，利用四種不同特性的節點： Sucker(傻瓜)、Cheater (騙子)、Grudger(小氣鬼)、Ecci(投機者)， 這些自私節點會照成DTN在設計上無法使用，甚至降低訊息的傳達率，因此我們模擬了這些自私節點的行為，並且使用我們所提出的獎勵機制，來解決這些自私節點的問題，實驗結果也證明，Grudger可以有效的抑制自私節點對效能大幅降低的問題，與傳統的演算法相較，效能高出34%。
DTN (Delay Tolerant Networks) is a network structure without need to use any infrastructure. In DTNs, wireless connections between nodes do not always exist, i.e., nodes are connected intermittently. Due to the mobility, power issues, or surrounding environment of nodes, connections between nodes may be disruptive occasionally or randomly. In a DTN, nodes usually transfer the message to the encountering nodes. By this way, the messages are stored, carried, and forwarded to the next nodes, possibly the destination. However, in reality, nodes may not be willing to help each other for the message forwarding. More specifically, there are “Selfish nodes” which refuse to forward messages due to issues such as energy and network bandwidth. Thus it will prevent messages from being forwarded to its destination.
In order to solve the problem of message forwarding failure caused by selfish nodes, we proposed an Incentive Strategy called “MTBIS (Mobile Trusted Bank and Incentive Strategies)”. We construct a rewarding scheme called “Incentive Credit” for nodes who forward the messages for the source node. In addition, to increase the intention of the selfish nodes for forwarding messages, we add two more mechanism called SI(Social Incentive) and DGT(Dynamic Grudger Threshold). The DGT uses credits to solve selfish node problems from an economics point of view to enhance MTBIS to work with existence of selfish nodes.
In this thesis, we emphasis on the simulation of the behaviors of selfish nodes, using four different types of nodes: the “Sucker”, the “Cheater”, the “Grudger”, and the “Ecci”. These selfish nodes will decrease the success rate of message forwarding, and even make the DTN unusable. We simulated the behaviors of these selfish nodes, using the rewarding scheme we proposed. From the results of our experiment, we see that the Grudger can effectively deal with performance issues caused by selfish nodes, and the system can gain 34% in performance compared to the traditional algorithms.
參考文獻 【1】Rongxing Lu; Xiaodong Lin; Haojin Zhu; Xuemin Shen; Preiss, B.; , "Pi: A practical incentive protocol for delay tolerant networks," Wireless Communications, IEEE Transactions on , vol.9, no.4, pp.1483-1493, April 2010
【2】Haojin Zhu; Xiaodong Lin; Rongxing Lu; Yanfei Fan; Xuemin Shen; , "SMART: A Secure Multilayer Credit-Based Incentive Scheme for Delay-Tolerant Networks,"Vehicular Technology, IEEE Transactions on , vol.58, no.8, pp.4628-4639, Oct. 2009
【3】Qi He; Dapeng Wu; Khosla, P.; , "SORI: a secure and objective reputation-based incentive scheme for ad-hoc networks," Wireless Communications and Networking Conference, 2004. WCNC. 2004 IEEE , vol.2, no., pp. 825- 830 Vol.2, 21-25 March 2004
【4】Richard T. B. Ma, Sam C. M. Lee, John C. S. Lui, and David K. Y. Yau. 2004. A game theoretic approach to provide incentive and service differentiation in P2P networks. In Proceedings of the joint international conference on Measurement and modeling of computer systems(SIGMETRICS `04/Performance `04). ACM, New York, NY, USA, 189-198.
【5】Richard Dawkins. The Selfish Gene. Oxford University Press, 1989 edition, 1976.
【6】Rongxing Lu; Xiaodong Lin; Haojin Zhu; Chenxi Zhang; Pin-Han Ho; Xuemin Shen; , "A Novel Fair Incentive Protocol for Mobile Ad Hoc Networks," Wireless Communications and Networking Conference, 2008. WCNC 2008. IEEE , vol., no., pp.3237-3242, March 31 2008-April 3 2008
【7】Tanase, M.; Cristea, V.; , "Quality of Service in Large Scale Mobile Distributed Systems Based on Opportunistic Networks," Advanced Information Networking and Applications (WAINA), 2011 IEEE Workshops of International Conference on , vol., no., pp.849-854, 22-25 March 2011
【8】 Alan Demers, Carl Hauser, Dan Greene, John Larson, and Wes Irish, “Epidemic algorithms for replicated database maintenance,” Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, pp. 1-12, August 1987.
【9】Vahdat A and Becker D, “Epidemic routing for partially connected ad hoc networks,” Technical report, Duke University, 2000.
【10】Cauligi S. Raghavendra, Konstantinos Psounis, and Thrasyvoulos Spyropoulos, “Spray and Wait: an efficient routing scheme for intermittently connected mobile networks,” Proceeding of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, pp. 252–259, August 2005.
【11】 Silvia Giordano, Alessandro Puiatti, and Hoang Anh Nguyen, “Probabilistic routing in intermittently connected networks,” A World of Wireless, Mobile and Multimedia Networks, International Symposium, pp. 1-6, June 2007.
【12】Mihai Tanase and Valentin Cristea. 2011. Quality of Service in Large Scale Mobile Distributed Systems Based on Opportunistic Networks. In Proceedings of the 2011 IEEE Workshops of International Conference on Advanced Information Networking and Applications (WAINA `11). IEEE Computer Society, Washington, DC, USA, 849-854.
【13】Shevade, U.; Han Hee Song; Lili Qiu; Yin Zhang; , "Incentive-aware routing in DTNs," Network Protocols, 2008. ICNP 2008. IEEE International Conference on , vol., no., pp.238-247, 19-22 Oct. 2008.
【14】Philippe Golle, Kevin Leyton-Brown, Ilya Mironov, and Mark Lillibridge. 2001. Incentives for Sharing in Peer-to-Peer Networks. In Proceedings of the Second International Workshop on Electronic Commerce (WELCOM `01), Ludger Fiege, Gero M\\&\\#252;hl, and Uwe G. Wilhelm (Eds.). Springer-Verlag, London, UK, 75-87.
【15】Sonja Buchegger and Jean-Yves Le Boudec. 2002. Performance analysis of the CONFIDANT protocol. In Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking \\& computing (MobiHoc `02). ACM, New York, NY, USA, 226-236. DOI=10.1145/513800.513828.
【16】Elgan Huang, Jon Crowcroft, and Ian Wassell. 2004. Rethinking incentives for mobile ad hoc networks. In Proceedings of the ACM SIGCOMM workshop on Practice and theory of incentives in networked systems (PINS `04). ACM, New York, NY, USA, 191-196.
【17】Michal Feldman, Kevin Lai, Ion Stoica, and John Chuang. 2004. Robust incentive techniques for peer-to-peer networks. In Proceedings of the 5th ACM conference on Electronic commerce (EC `04). ACM, New York, NY, USA, 102-111. DOI=10.1145/988772.988788
【18】Ari Keränen, Jörg Ott, and Teemu Kärkkäinen. 2009. The ONE simulator for DTN protocol evaluation. In Proceedings of the 2nd International Conference on Simulation Tools and Techniques (Simutools `09). ICST (Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering), ICST, Brussels, Belgium, Belgium, , Article 55 , 10 pages. DOI=10.4108/ICST.SIMUTOOLS2009.5674.
描述 碩士
國立政治大學
資訊科學學系
99753018
100
資料來源 http://thesis.lib.nccu.edu.tw/record/#G0997530182
資料類型 thesis
dc.contributor.advisor 蔡子傑zh_TW
dc.contributor.advisor Tsai, Tzu Chiehen_US
dc.contributor.author (Authors) 林昶瑞zh_TW
dc.contributor.author (Authors) Lin, Chan Jueien_US
dc.creator (作者) 林昶瑞zh_TW
dc.creator (作者) Lin, Chan Jueien_US
dc.date (日期) 2011en_US
dc.date.accessioned 30-Oct-2012 14:01:31 (UTC+8)-
dc.date.available 30-Oct-2012 14:01:31 (UTC+8)-
dc.date.issued (上傳時間) 30-Oct-2012 14:01:31 (UTC+8)-
dc.identifier (Other Identifiers) G0997530182en_US
dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/54866-
dc.description (描述) 碩士zh_TW
dc.description (描述) 國立政治大學zh_TW
dc.description (描述) 資訊科學學系zh_TW
dc.description (描述) 99753018zh_TW
dc.description (描述) 100zh_TW
dc.description.abstract (摘要) DTN(Delay Tolerant Networks)是一種缺乏網路基礎設備的網路架構，在這類的網路架構下，無線節點之間的通訊連線並非同時存在，而是間歇式建立的。因為節點的移動、或是裝置省電模式運作與環境因素的影響，造成連線可能不定時的失效。有不保證連線特性的網路，在DTN網路中節點間相遇的機會很少，節點間利用 Store-Carry-Forward 的方式傳遞訊息，且有相當長的傳遞延遲(Propagation Delay)。在這樣的網路特性下，傳統的文獻中，都是假設所有節點都會幫忙傳遞。但不幸的，在現實生活中有自私節點(Selfish Nodes)的存在，因自己本身設備資源有限，如電力資源、網路資源...等，節點不願意幫忙傳送訊息，這些自私節點的存在，會對DTN網路架構造成破壞，導致無法傳送訊息到目的地。為了解決自私節點的問題，我們提出了MTBIS(Mobile Trusted Bank of Incentive Strategies)，當發送節點(Source Node)要求傳送訊息時，給予回饋給幫忙轉傳訊息的節點，來鼓勵節點間互相幫忙傳送訊息，我們稱這些回饋為Incentive Credit。而節點也可利用Incentive Credit來要求別的節點幫忙轉傳訊息。另外也加入SI(Social Incentive)機制，與DGT(Dynamic Grudger Threshold) ，吸引自私節點願意幫忙轉傳訊息，改進了 MTBIS 在自私節點環境下的不足， 利用經濟學的角度來解決節點運用Credit的問題，借此提高訊息的傳遞率(Delivery Ratio)。
本篇研究也注重於自私節點的模擬，利用四種不同特性的節點： Sucker(傻瓜)、Cheater (騙子)、Grudger(小氣鬼)、Ecci(投機者)， 這些自私節點會照成DTN在設計上無法使用，甚至降低訊息的傳達率，因此我們模擬了這些自私節點的行為，並且使用我們所提出的獎勵機制，來解決這些自私節點的問題，實驗結果也證明，Grudger可以有效的抑制自私節點對效能大幅降低的問題，與傳統的演算法相較，效能高出34%。		zh_TW
dc.description.abstract (摘要) DTN (Delay Tolerant Networks) is a network structure without need to use any infrastructure. In DTNs, wireless connections between nodes do not always exist, i.e., nodes are connected intermittently. Due to the mobility, power issues, or surrounding environment of nodes, connections between nodes may be disruptive occasionally or randomly. In a DTN, nodes usually transfer the message to the encountering nodes. By this way, the messages are stored, carried, and forwarded to the next nodes, possibly the destination. However, in reality, nodes may not be willing to help each other for the message forwarding. More specifically, there are “Selfish nodes” which refuse to forward messages due to issues such as energy and network bandwidth. Thus it will prevent messages from being forwarded to its destination.
In order to solve the problem of message forwarding failure caused by selfish nodes, we proposed an Incentive Strategy called “MTBIS (Mobile Trusted Bank and Incentive Strategies)”. We construct a rewarding scheme called “Incentive Credit” for nodes who forward the messages for the source node. In addition, to increase the intention of the selfish nodes for forwarding messages, we add two more mechanism called SI(Social Incentive) and DGT(Dynamic Grudger Threshold). The DGT uses credits to solve selfish node problems from an economics point of view to enhance MTBIS to work with existence of selfish nodes.
In this thesis, we emphasis on the simulation of the behaviors of selfish nodes, using four different types of nodes: the “Sucker”, the “Cheater”, the “Grudger”, and the “Ecci”. These selfish nodes will decrease the success rate of message forwarding, and even make the DTN unusable. We simulated the behaviors of these selfish nodes, using the rewarding scheme we proposed. From the results of our experiment, we see that the Grudger can effectively deal with performance issues caused by selfish nodes, and the system can gain 34% in performance compared to the traditional algorithms.		en_US
dc.description.tableofcontents CHAPTER 1 p.1
Introduction! p.1
1.1 Background p.1
1.2 Motivation p.2
1.3 Organization p.3
CHAPTER 2 p.4
Related Work p.4
2.1 DTN Routing Protocol p.4
2.1.1 Opportunistic Protocol p.4
2.1.1.1 Epidemic Routing Protocol p.4
2.1.1.2 Spray and Wait Routing Protocol p.5
2.1.2 Prediction-based Protocol p.5
2.1.2.1 PROPHET Routing Protocol p.5
2.2 Incentive Techniques p.6
2.2.1 Pi A Practical Incentive Protocol for Delay Tolerant Networks p.6
2.2.2 SMART A Secure Multilayer Credit-Based Incentive Scheme for Delay- Tolerant Networks p.7
2.2.3 SORI A Secure and Objective Reputation-based Incentive Scheme for Ad-hoc Networks p.8
2.3 Design Goal p.8
CHAPTER 3 p.9
Research Methods p.9
3.1 Challenges p.9
3.2 Mobile Trusted Bank (MTB) p.9
3.3 Selfish Nodes Simulation Environment p.11
3.3.1 Selfish Nodes Species p.11
3.3.2 Nodes Behavior p.13
3.3.3 The Discrimination between Selfish Nodes and Unselfish Nodes p.16
3.4 Receipt Data p.17
3.5 Credit Clearance p.19
3.6 Dynamic Grudger Threshold (DGT) p.20
3.7 Social Incentive (SI) p.21
3.8 MTBIS(Mobile Trusted Bank Incentive Strategy) p.22
CHAPTER 4 p.26
Simulation and Results p.26
4.1 Performance Evaluation p.26
4.2 Assumptions p.27
4.3 Simulation Setup p.27
4.4 Simulation Results p.28
4.4.1 The Selection of Grudger Threshold and ESC Threshold p.28
4.4.2 Selfish Nodes Density p.30
4.4.3 Grudger Nodes Density p.34
4.4.4 Delivery Ratio in each Nodes p.36
4.4.5 MTB Density p.38
5. Conclusion and Future Work! References p.41
References p.43		zh_TW
dc.language.iso en_US-
dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0997530182en_US
dc.subject (關鍵詞) 耐延遲網路zh_TW
dc.subject (關鍵詞) 獎勵機制zh_TW
dc.subject (關鍵詞) 自私節點zh_TW
dc.subject (關鍵詞) DTNen_US
dc.subject (關鍵詞) Incentiveen_US
dc.subject (關鍵詞) Selfishen_US
dc.title (題名) 基於耐延遲網路之移動式信任者與獎勵機制設計zh_TW
dc.title (題名) Mobile trusted bank and incentive strategy design in delay tolerant networksen_US
dc.type (資料類型) thesisen
dc.relation.reference (參考文獻) 【1】Rongxing Lu; Xiaodong Lin; Haojin Zhu; Xuemin Shen; Preiss, B.; , "Pi: A practical incentive protocol for delay tolerant networks," Wireless Communications, IEEE Transactions on , vol.9, no.4, pp.1483-1493, April 2010
【2】Haojin Zhu; Xiaodong Lin; Rongxing Lu; Yanfei Fan; Xuemin Shen; , "SMART: A Secure Multilayer Credit-Based Incentive Scheme for Delay-Tolerant Networks,"Vehicular Technology, IEEE Transactions on , vol.58, no.8, pp.4628-4639, Oct. 2009
【3】Qi He; Dapeng Wu; Khosla, P.; , "SORI: a secure and objective reputation-based incentive scheme for ad-hoc networks," Wireless Communications and Networking Conference, 2004. WCNC. 2004 IEEE , vol.2, no., pp. 825- 830 Vol.2, 21-25 March 2004
【4】Richard T. B. Ma, Sam C. M. Lee, John C. S. Lui, and David K. Y. Yau. 2004. A game theoretic approach to provide incentive and service differentiation in P2P networks. In Proceedings of the joint international conference on Measurement and modeling of computer systems(SIGMETRICS `04/Performance `04). ACM, New York, NY, USA, 189-198.
【5】Richard Dawkins. The Selfish Gene. Oxford University Press, 1989 edition, 1976.
【6】Rongxing Lu; Xiaodong Lin; Haojin Zhu; Chenxi Zhang; Pin-Han Ho; Xuemin Shen; , "A Novel Fair Incentive Protocol for Mobile Ad Hoc Networks," Wireless Communications and Networking Conference, 2008. WCNC 2008. IEEE , vol., no., pp.3237-3242, March 31 2008-April 3 2008
【7】Tanase, M.; Cristea, V.; , "Quality of Service in Large Scale Mobile Distributed Systems Based on Opportunistic Networks," Advanced Information Networking and Applications (WAINA), 2011 IEEE Workshops of International Conference on , vol., no., pp.849-854, 22-25 March 2011
【8】 Alan Demers, Carl Hauser, Dan Greene, John Larson, and Wes Irish, “Epidemic algorithms for replicated database maintenance,” Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, pp. 1-12, August 1987.
【9】Vahdat A and Becker D, “Epidemic routing for partially connected ad hoc networks,” Technical report, Duke University, 2000.
【10】Cauligi S. Raghavendra, Konstantinos Psounis, and Thrasyvoulos Spyropoulos, “Spray and Wait: an efficient routing scheme for intermittently connected mobile networks,” Proceeding of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, pp. 252–259, August 2005.
【11】 Silvia Giordano, Alessandro Puiatti, and Hoang Anh Nguyen, “Probabilistic routing in intermittently connected networks,” A World of Wireless, Mobile and Multimedia Networks, International Symposium, pp. 1-6, June 2007.
【12】Mihai Tanase and Valentin Cristea. 2011. Quality of Service in Large Scale Mobile Distributed Systems Based on Opportunistic Networks. In Proceedings of the 2011 IEEE Workshops of International Conference on Advanced Information Networking and Applications (WAINA `11). IEEE Computer Society, Washington, DC, USA, 849-854.
【13】Shevade, U.; Han Hee Song; Lili Qiu; Yin Zhang; , "Incentive-aware routing in DTNs," Network Protocols, 2008. ICNP 2008. IEEE International Conference on , vol., no., pp.238-247, 19-22 Oct. 2008.
【14】Philippe Golle, Kevin Leyton-Brown, Ilya Mironov, and Mark Lillibridge. 2001. Incentives for Sharing in Peer-to-Peer Networks. In Proceedings of the Second International Workshop on Electronic Commerce (WELCOM `01), Ludger Fiege, Gero M\\&\\#252;hl, and Uwe G. Wilhelm (Eds.). Springer-Verlag, London, UK, 75-87.
【15】Sonja Buchegger and Jean-Yves Le Boudec. 2002. Performance analysis of the CONFIDANT protocol. In Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking \\& computing (MobiHoc `02). ACM, New York, NY, USA, 226-236. DOI=10.1145/513800.513828.
【16】Elgan Huang, Jon Crowcroft, and Ian Wassell. 2004. Rethinking incentives for mobile ad hoc networks. In Proceedings of the ACM SIGCOMM workshop on Practice and theory of incentives in networked systems (PINS `04). ACM, New York, NY, USA, 191-196.
【17】Michal Feldman, Kevin Lai, Ion Stoica, and John Chuang. 2004. Robust incentive techniques for peer-to-peer networks. In Proceedings of the 5th ACM conference on Electronic commerce (EC `04). ACM, New York, NY, USA, 102-111. DOI=10.1145/988772.988788
【18】Ari Keränen, Jörg Ott, and Teemu Kärkkäinen. 2009. The ONE simulator for DTN protocol evaluation. In Proceedings of the 2nd International Conference on Simulation Tools and Techniques (Simutools `09). ICST (Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering), ICST, Brussels, Belgium, Belgium, , Article 55 , 10 pages. DOI=10.4108/ICST.SIMUTOOLS2009.5674.		zh_TW