 |
|
|
|
以作者查詢圖書館館藏 、以作者查詢臺灣博碩士 、以作者查詢全國書目 、勘誤回報 、線上人數：10 、訪客IP：3.145.23.123
姓名 黃毓芳(Yu-Fang Huang) 查詢紙本館藏 畢業系所 通訊工程學系 論文名稱 基於賽局理論之耐延遲網路儲存空間管理機制
(Buffer Management Based on Game Theory for Bundle Protocol in DTN)相關論文 檔案 [Endnote RIS 格式]
[相關文章]
[文章引用]
[完整記錄]
[館藏目錄]
[檢視]
- 本電子論文使用權限為同意立即開放。
- 已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
- 請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。
摘要(中) 在耐延遲網路(Delay Tolerant Networks, DTNs)中，由於節點移動的不可預期性造成的間斷式連線，網路中一個訊息的來源端到目的端難以建立一條end-to-end path來傳輸此訊息。因此，耐延遲網路採用了集束協定(Bundle Protocol)所提出的store-carry-and-forward方式取代傳統網路的store-and-forward方式來傳輸訊息。而一個來自於上層的訊息(Message)會在集束層(Bundle Layer)被切割成多個較小的資料單位，這些資料單位就叫做束(Bundle)。同時，為了確保束在網路中的傳輸可靠度，集束協定採用了保護傳輸機制(Custody Transfer)，透過其hop-by-hop的傳輸方式及重傳和確認回傳的機制來確保每個束在成功被網路中的下一個節點接收前不被丟棄。
然而使用集束協定可能會面臨兩個問題：透過保護傳輸機制，束的不可被丟棄性將會使網路中節點消耗許多儲存空間資源來儲存束，尤其是在資源有限的耐延遲網路中，這樣的情況可能會阻礙束在網路中的傳輸，進而降低了訊息抵達率；另外，由於耐延遲網路的間歇性連線的特性，要等到一個訊息的所有切割束都抵達訊息目的端並且完成一個訊息的回復是相對困難的。
因此，本篇論文提出了一個基於賽局理論的儲存空間管理機制(Buffer Management based on Game Theory, BMGT)，網路中節點可以透過此機制來管理其儲存空間的使用情況進而避免發生儲存空間不足的壅塞情形。當網路中的兩個節點相遇後，這兩個相遇節點即會進入轉送賽局(Forwarding game)，並且根據賽局理論模型同時考慮節點自身的儲存空間使用情況來決定是否要接收或是轉送束給其相遇節點。BMGT的目的就是希望透過賽局理論將節點儲存空間資源納入考量，對於網路中兩相遇節點決定出一個合適轉送或是接收機率。同時，為了避免儲存空間溢出(Buffer overflow)，我們提出了激勵函式(Incentive function)。激勵函式的概念是希望兩相遇節點中，擁有較低儲存空間使用率的節點有較高的機率會採取接收束的行為，而擁有較高儲存空間使用率的節點有較高的機率會採取轉送束的行為。如此一來不但可以避免儲存空間壅塞問題同時還能促進束在網路中的流動。另外，BMGT在訊息的產生上採用了湧泉編碼(Fountain Code)的原理，使得訊息的目的端只需要接收到部分的束即可回復其原始訊息。模擬結果顯示，BMGT不但可以達到較有效的儲存空間資源分配，同時解決集束協定的儲存空間壅塞問題，並且達到較好的網路效能。摘要(英) Delay tolerant networks (DTNs) contain resource-constrained nodes moving in highly dynamic network environments, which makes persistent end-to-end routing paths impossible between any pair of source and destination nodes. The DTN architecture with the Bundle Protocol (BP) are thus advocated a reliable message delivery service on intermittently connected networks. The BP provides a new encapsulation representation by which a message from an upper layer is divided into a series of bundles. Instead of store-and-forward paradigms commonly used in wireless and mobile ad hoc networks, the DTN architecture adopts the extit{store-carry-and forward} paradigm by which nodes can store bundles, carry them and forward these bundles to next encountered nodes during movement in a network. In addition, BP guarantees delivery reliability among bundles using the extit{Custody Transfer} mechanism. Nodes are not allowed to drop any bundles of which they take the custody until these bundles are successfully delivered to next nodes that can take the custody in turn.
Using the Bundle Protocol in DTNs, however, faces two possible problems. First, opportunistic or unpredictable contacts among nodes may make it difficult for all divided bundles to arrive at a destination, this problem which might enforce the failure of message reconstruction services in a network. Second, the non-dropped feature of custody transfer may cause nodes spend excessive storage space to store custody bundles, this problem which might induce buffer overflow on the nodes.
In this study, we propose a Buffer Management scheme based on Game Theory (BMGT) that nodes can control the number of bundles in their own storage and avoid the likelihood of bundle congestion in DTNs. Regarding the first problem above, BMGT combines the principle of Fountain Code that any destination does not need to receive all divided bundles to recover original message. Regarding the second problem, BMGT derives the appropriate forwarding and receiving probability based on the game theory model, which takes node storage utilization into account, for two nodes in communications. In BMGT, nodes will enter a forwarding game upon contacting with the other nodes and then follow the game theory model to select a forward or receiving action with some merit of reward. To prevent buffer overflow, an incentive function is further devised to encourage reciprocal actions of bundle forwarding and receiving between two nodes in contact. Finally, we conduct extensive simulation to investigate the effects of BMGT under various synthetic contexts. Performance results manifest that BMGT can not only achieve efficient storage resource allocation but also resolve the congestion issue against the convention of Bundle Protocol in DTNs.關鍵字(中) ★ 耐延遲網路
★ 集束協定
★ 保護傳輸
★ 湧泉編碼
★ 賽局理論
★ 儲存空間管理關鍵字(英) ★ Delay Tolerant Network
★ Bundle Protocol
★ Custody Transfer
★ Fountain Code
★ Game Theory
★ Buffer Management論文目次 1 Introduction1
2 Research Background 4
2.1 Bundle Protocol................................. 4
2.1.1 Custody Transfer............................ 5
2.1.2 Problem of Custody Transfer..................... 6
2.2 Game Theory.................................. 7
2.2.1 Pure Strategy Game.......................... 7
2.2.2 Mixed Strategy Game......................... 8
2.3 Fountain Code................................. 9
3 Related Work 11
3.1 Research on Bundle Protocol....................... 11
3.2 Research on Game Theory in DTNs................... 12
3.3 Research on Coding in DTNs....................... 14
4 Buff er Management Based on Game Theory (BMGT) 15
4.1 Motivation and Design Abstract.................... 15
4.2 System Model.................................. 16
4.3 Architecture of BMGT............................. 17
4.4 Message Generation with Fountain Code............. 18
4.4.1 Modifi ed Fountain Code........................ 19
4.4.2 Hybrid Bundle Transfer........................ 19
4.4.3 Message Reconstruction........................ 19
4.5 Data Delivery Based on Game Theory................ 20
4.5.1 Mixed Strategy Forwarding Game.................. 21
4.5.2 Incentive Function........................... 26
5 Simulations 29
5.1 Performance Metrics.............................. 30
5.2 Mobility Model................................. 30
5.3 Comparison Method.............................. 31
5.3.1 Comparison Methods in the analysis of Coding Eff ect........ 31
5.3.2 The Comparison Method in the analysis of BMGT......... 32
5.4 Environment Setting.............................. 33
5.4.1 Environment Setting in the Analysis of Coding Eff ect........ 33
5.4.2 Environment Setting in the Analysis of BMGT........... 33
6 Results and Analysis - Coding E ffect 36
6.1 Results with Diff erent Values of TTL..................... 36
6.2 Results with Di fferent Values of k . ...................... 37
6.3 Results with Diff erent Values of Bu rffer Size.................. 38
7 Results and Analysis - BMGT 44
7.1 Influence of bn and bc . ............................. 44
7.2 Influence of r ................................... 46
7.3 Influence of w . ................................. 48
7.4 Performance Analysis.............................. 50
7.4.1 Results with Diff erent Values of TTL................. 50
7.4.2 Results with Dffi erent Values of k . .................. 53
7.4.3 Results with Diff erent Values of Bu erSize.............. 55
7.4.4 Analysis of Storage Utilization.................... 56
8 Conclusions and Future Works 59
Bibliography 61
A Recommended Parameters of BMGT 64參考文獻 [1] V.Cerf,S.Burleigh,A.Hooke,L.Torgerson,R.Durst,K.Scott,K.Fall,and H. Weiss,"Delay-tolerant networking architecture,"RFC4838,2007.
[2] S.Burleigh,A.Hooke,L.Torgerson,K.Fall,V.Cerf,B.Durst,K.Scott,and H. Weiss,"Delay-tolerant networking:Anapproach to interplanetary internet," IEEE Communications Magazine,vol.41,no.6,pp.128-136,2003.
[3] S.BurleighandK.Fall,"Bundle protocol speci cation," RFC5050,2007.
[4] K.Fall,W.Hong,and S.Madden,"Custody transfer for reliable delivery in delay tolerant networks," Tech.Rep.,2003.
[5] E.daS.Miranda,J.F.Naves,I.M.Moraes,and P.B.Velloso,"A joint custody-based forwarding policy for delay-tolerant networks,"in Proceedings of IEEE Global
Information Infrastructure and Networking Symposium(GIIS′12), 2012.
[6] T.deCola and M.Marchese, "Joint use of custody transfer and erasure codes in dtn space networks : bene ts and shortcomings,"in Proceedings of IEEE Global Telecommunications Conference(GLOBECOM′10), 2010.
[7] P.U.Tournoux,E.Lochin,J.Leguay,and J.Lacan,"Robust streaming in delay tolerant networks,"in Proceedings of IEEE International Conference on Communications(ICC′10), May 2010.
[8] P.U.Tournoux,E.Lochin,J.Lacan,A.Bouabdallah,and V.Roca,"On-the-
fly erasure coding for real-time video applications," IEEE Transactions on Multimedia, vol.13,pp.797-812,2011.
[9] D.Zeng, S.Guo, H.Jin, and V.Leung, "Segmented network coding for stream-like applications in delay tolerant networks,"in Proceeding of IEEE Global Telecommunications Conference(GLOBECOM′11), 2011.
[10] M.Seligman,K.Fall,and P.Mundur, "Alternative custodians for congestion control in delay tolerant networks,"in Proceedings of ACM SIGCOMM Work shop on
Challenged Networks(CHANTS′06), 2006,pp.229-236.
[11] D.Hua,X.Du,G.Xu,L.Cao,and H.Chen,"A dtn congestion mechanism based on distributed storage,"in Proceedings of the 2nd IEEE International Conference on Information Management and Engineering (ICIME′10), 2010,pp.385-389.
[12] I.Bisio,M.Marchese,and T.deCola,"Congestion aware routing strategies for dtn-based interplanetary networks,"in Proceeding of IEEE Global Telecommunications
Conference(GLOBECOM′08), 2008,pp.1-5.
[13] F. D.Rango,M.Tropea,G.B.Laratta,and S.Marano,"Hop-by-hop local flow control over interplanetary networks based on dtn architecture," in Proceeding of
IEEE International Conference on Communications(ICC′08), May 2008,pp.1920-1924.
[14] D.Hua,X.Du,L.Cao,G.Xu,andY.Qian,"A dtn congestion avoidance strategy based on path avoidance,"in Proceedings of the 2nd IEEE International Conference on Future Computer and Communication (ICFCC′10), May 2010,pp.855-860.
[15] W.Li,F.Lin,J.Zhou,and Y.Wang,"GTDM : A dtn routing on noncoopertive game theory in a city enironment," Hindai Journal of Sensors, 2015.
[16] Y. Mao and P.Zhu,"A game theoretical model for energy-aware dtn routing in manets with nodes selfi shness," Springer Journal of Mobile Network and Application,2015.
[17] Z.Gao,H.Zhu,S.Du,C.Xiao,and R.Lu,"PMDS : A probabilistic misbehavior detection scheme in dtn ,"in Proceedings of IEEE International Conference on
Communications(ICC′12), 2012,pp.4970-4974.
[18] M.Naserian and K.Tepe,"Dynamic probabilistic forwarding in wireless ad hoc networks based on game theory,"in Proceedings of the 79th IEEE Vehicular Technology Conference (VTC Spring′14), May 2014,pp.1-5.
[19] K.Chen,H.Shen,and L.Yan,"Multicent : A multifunctional incentive scheme
adaptive to diverse performance objectives for dtn routing," IEEE Transactions on Parallel and Distributed Systems, vol.26,no.6,pp.1643-1653,2015.
[20] L. Wei,Z.Cao,and H.Zhu,"MobiGame : A user-centric reputation based incentive protocol for delay/disruption tolerant networks,"in Proceeding of IEEE Global
Telecommunications Conference(GLOBECOM′11), 2011,pp.1-5.
[21] M.Naserian and K.Tepe,"Game theoretic approach in routing protocol for wireless ad hoc networks," ELSEVIER Journal of Ad Hoc Networks, vol.7,pp.569-578,May 2009.
[22] J.W.Byers,M.Luby,and M.Mitzenmacher,"A digital fountain approach to asynchronous reliable multicast," IEEE Journal on Selected Areas in Communications, vol.20,no.8,pp.1528-1540,2002.
[23] J. W.Byers,M.Luby,M.Mitzenmacher,and A.Rege,"A digital fountain approach to reliable distribution of bulk data," ACM SIGCOMM Computer Communication Review, vol.28,no.4,pp.56-67,1998.
[24] A.Kernen,J.Ott,and T.Krkkinen,"The one simulator for dtn protocol evaluation,"in Proceedings of the 2nd ACM International Conference on Simulation Tools and
Techniques(Simtool′09), Rome,Italy,2009,pp.55:1-10.指導教授 胡誌麟(Chih-Lin Hu) 審核日期 2016-8-17 推文 plurk
funp
live
udn
HD
myshare
netvibes
friend
youpush
delicious
baidu
網路書籤 Google bookmarks
del.icio.us
hemidemi
facebook
twitter
google
reddit