耐延遲網路下以靜態中繼節點（暫存盒）最佳化訊息傳遞效能之研究

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：18

、訪客IP：3.141.100.120

姓名

阮明英(nguyen huu minh anh) 查詢紙本館藏

畢業系所

通訊工程學系

論文名稱

耐延遲網路下以靜態中繼節點（暫存盒）最佳化訊息傳遞效能之研究
(Using Stationary Relay Nodes (Thrown Boxes) to Optimize Message Forwarding Performance in Delay-Tolerant Networks)

相關論文

★ 非結構同儕網路上以特徵相似度為基準之搜尋方法	★ 以階層式叢集聲譽為基礎之行動同儕網路拓撲架構
★ 線上RSS新聞資料流中主題性事件監測機制之設計與實作	★ 耐延遲網路下具密度感知的路由方法
★ 整合P2P與UPnP內容分享服務之家用多媒體閘道器：設計與實作	★ 家庭網路下簡易無縫式串流影音播放服務之設計與實作
★ 耐延遲網路下訊息傳遞時間分析與高效能路由演算法設計	★ BitTorrent P2P 檔案系統下載端網路資源之可調式配置方法與效能實測
★ 耐延遲網路中利用訊息編碼重組條件之資料傳播機制	★ 耐延遲網路中基於人類移動模式之路由機制
★ 車載網路中以資料匯集技術改善傳輸效能之封包傳送機制	★ 適用於交叉路口環境之車輛叢集方法
★ 車載網路下結合路側單元輔助之訊息廣播機制	★ 耐延遲網路下以動態叢集感知建構之訊息傳遞機制
★ 跨裝置影音匯流平台之設計與實作	★ 耐延遲網路下基於封包複製模式的路由機制之模擬及效能比較

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

由於傳統無線網路架構受到間歇性的傳輸連結、有限的傳輸距離以及低節點密度等因素，會使得行動及無線網路應用間的通訊中斷，造成無法確保端點至端點存在連線。因此，耐延遲網路技術被用來解決上述的訊息傳遞問題。耐延遲網路不同於傳統電腦網路和行動隨意網路，其訊息傳遞至目的端是採用「儲存、攜帶和轉送」的方法，只有當節點與其他節點相遇時，才會傳遞訊息。在耐延遲網路的路由協定方法中，透過部署靜態中繼節點(又稱暫存盒)的策略被認為可以有效地增加訊息的傳遞成功率或減少訊息的傳遞成本。然而，目前在這類於耐延遲網路使用暫存盒的研究中，只有少數的研究提供完整的分析模型和路由方法。
本研究提出的演算法將有效的減少的訊息傳遞成本於節點是異質性的耐延遲網路。本論文的內容可分為下列三部份：首先，本研究認為暫存盒的部署能幫助耐延遲網路的訊息傳遞，並提出一個基於效用值的演算法來決策兩節點相遇時，訊息該如何傳遞。接著，本研究介紹如何用Absorbing馬可夫鏈設計一個分析架構以量化和預測本論文提出的演算法之效能。特別地，這個架構能夠將最佳化的問題轉化成馬卡夫鍵問題，當兩個節點相遇時，即可決定轉移機率，進一步解出最佳解。最後，本研究透過模擬來衡量所提出的演算法在訊息傳遞成功率和訊息傳遞成本之效能。結果顯示，本研究提出的方法相較幾個有名的演算法有著較好的效能

摘要(英)

Many data and network applications for mobile and wireless networks cause disruptions in communications where traditional Internet architectures fail to ensure end-to-end connections due to intermittent connectivity, limited transmission range and low nodal density. The delay-tolerant networking (DTN) technology is introduced to deal with these problems. Contrary to traditional computer networks and MANETs, the message forwarding in delay-tolerant networks adopts the store-carry-and-forward approach to send messages to destinations when nodes have any opportunistic contacts with others in a network. Among the approaches for routing protocols in DTNs, the strategy of deploying the stationary relay nodes called “thrown boxes” is considered for increasing message delivery probability and reducing the message overhead efficiently. Till now, few studies have provided comprehensive analysis models and routing solutions for thrown-box-based network paradigms in the DTN research field.

This thesis addresses the efficiency on message forwarding over heterogeneous nodes in DTNs. The technical content of this thesis includes three parts. Firstly, this study considers the deployment of thrown boxes that can assist in message delivery in delay-tolerant networks. A utility-based algorithm is applied to make the message forwarding decision between two nodes whenever they are in contact. Secondly, this study introduces the adaptation of absorbing Markov chain to develop an analytical framework to quantify and predict the performance of the proposed algorithm. Specifically, this framework is able to map an optimization problem over the presence of thrown box into a Markov chain over the relevant solution space. The contact between two nodes can dictate the chain transition probability and be used to advance the finding of an optimal solution by following neighboring solutions in chain. Finally, this study runs simulations to evaluate the proposed scheme in terms of the message overhead ratio and message delivery probability. Performance results show that the proposed algorithm performs better than other popular algorithms.

關鍵字(中)

★ 耐延遲網路
★ 暫存盒
★ 效用演算法

關鍵字(英)

★ DTNs
★ thrown boxes
★ Utility-based algorithm

論文目次

摘要 i
Contents iv
Figures vi
Table viii
Chapter 1 Introduction 1
Chapter 2 Related Work 4
Chapter 3 Problem Statement and Model 6
3.1 System modeling and problem description 6
3.2 The utility-based algorithm using Thrown boxes (U-thrown boxes) 8
3.2.1 The Utility Function 9
3.2.2 The U-Thrown box Phases 10
3.2.3 The Thrown box placement schemes 11
3.3 The Class of Optimization Problem 13
3.3.1 The contact probability matrix 13
3.3.2 Network state 14
3.3.3 Utility Function 18
3.3.4 Acceptance probability 20
3.3.5 Transition probability 21
3.4 The absorbing Markov chain approach 24
Chapter 4 Evaluation Results 28
4.1 The implementation of thrown boxes in mobility traces 28
4.2 Simulation settings 29
4.3 Simulation results 31
4.3.1 Scenario 1 31
4.3.2 Scenario 2 52
4.3.3 Scenario 3 73
Chapter 5 Conclusion and Future works 80
Bibliography 81

參考文獻

[1] Ad Hoc Networking, Addison-Wesley Longman Publishing Co., Inc., Boston, Ma, USA, 2001
[2] Z. Zhang, “Routing in intermittently connected mobile ad hoc networks and delay tolerant networks: overview and challenges,” IEEE Communications Surveys and Tutorials, vol. 8, no. 1, pp. 24–37, Nov. 2006.
[3] E. Daly and M. Haahr, “Social network analysis for routing in disconnected delay-tolerant manets,” in Proceedings of the 8th ACM Interational Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc’07), Quebec, Canada, Sep. 9–14, 2007, pp. 32–40.
[4] R. Groenevelt, P. Nain, and G. Koole, “The message delay in mobile ad hoc networks,” Performance Evaluation, vol. 62, no. 1-4, pp. 210–228, Oct. 2005.
[5] A. Al Hanbali, A. A. Kherani, and P. Nain, “Simple models for the performance evaluation of a class of two-hop relay protocols,” in Proceedings of the 6th International IFIP-TC6 Conference on Ad Hoc and Sensor Networks, Wireless Networks, Next Generation Internet(NETWORKING’07), Atlanta, GA, USA, 2007, pp. 191–202.
[6] A. Balasubramanian, B. N. Levine, and A. Venkataramani, “Replication routing in dtns: a resource allocation approach,” IEEE/ACM Transactions on Networking, vol. 18, no. 2, pp. 596–609, Apr. 2010.
[7] J. Burgess, B. Gallagher, D. Jensen, and B. N. Levine, “Maxprop: Routing for vehicle-based disruption-tolerant networks,” in Proceedings of INFOCOM’06, Barcelona, Catalunya, SPAIN, Apr. 23–29, 2006.
[8] A. Lindgren, A. Doria, and O. Scheln, “Probabilistic routing in intermittently connected networks,” SIGMOBILE Mobile Computing and Communications Review, vol. 7, no. 3, pp. 19–20, Jul. 2003.
[9] T. Spyropoulos, K. Psounis, and C. S. Raghavendra, “Spray and wait: an efficient routing scheme for intermittently connected mobile networks,” in Proceedings of ACM SIGCOMM Workshop on Delay-Tolerant Networking, Philadelphia, Pennsylvania, USA, Aug. 22–26, 2005, pp. 252–259.
[10] T. Spyropoulos, K. Psounis, and C. S. Raghavendra, “Spray and focus: Efficient mobility-assisted routing for heterogeneous and correlated mobility,” in Proceedings of the 5th Annual IEEE International Conference on Pervasive Computing and Communications Workshops (PerCom’07 Workshops), White Plains, New York, USA, Mar. 19–23, 2007, pp. 79–85.
[11] M. Ibrahim, P. Nain, and I. Carreras, “Analysis of relay protocols for throwbox-equipped dtns,” in Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks, 2009. WiOPT 2009. 7th International Symposium on, 2009, pp. 1–9.
[12] M. M. Bin Tariq, M. Ammar, and E. Zegura, “Message ferry route design for sparse ad hoc networks with mobile nodes,” in Proceedings of the 7th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc’06), Florence, Italy, May 22-25, 2006, pp. 37–48.
[13] B. Gu and X. Hong, “Optimal routing strategy in throw-box based delay tolerant network,” in Proceedings of the 6th International ICST Conference on Communications and Networking in China (CHINACOM’11), Harbin, China, Aug. 17–19, 2011, pp. 501–506.
[14] B. Gu and X. Hong, “Capacity-aware routing using throw-boxes,” in Proceedings of IEEE Global Telecommunications Conference (GLOBECOM’11), Houston, TX, USA, Dec. 5–9, 2011.
[15] B. Gu, X. Hong, and P. Wang, “Analysis for bio-inspired thrown-box assisted message dissemination in delay tolerant networks,” Telecommunication Systems, vol. 52, no. 1, pp. 217–227, 2013.
[16] X. Hong, B. Gu, Y. Zeng, and J. Zhang, “Constructing time-varying contact graphs for heterogeneous delay tolerant networks,” in Proceedings of IEEE Global Communications Conference (GLOBECOM’12), Anaheim, CA, USA, Dec. 3–7, 2012, pp. 5302–5307.
[17] W. Zhao, Y. Chen, M. Ammar, M. Corner, B. Levine, and E. Zegura, “Capacity enhancement using throwboxes in dtns,” in Proceedings of IEEE International Conference on Mobile Adhoc and Sensor Systems (MASS’06), 2006, pp. 31–40.
[18] Grinstead, C. Miller, and J. L. Snell, Introduction to Probability. American Mathematical Soc, 1997.

[19] W.-J. Hsu, T. Spyropoulos, K. Psounis, and A. Helmy, “Modeling spatial and temporal dependencies of user mobility in wireless mobile networks,” IEEE/ACM Transactions on Networking, vol. 17, no. 5, pp. 1564–1577, Oct. 2009.
[20] A. Kera ̈nen, J. Ott, and T. Ka ̈rkka ̈inen, “The one simulator for dtn protocol evaluation,” in Proceedings of 2nd International Conference on Simulation Tools and Techniques (SIMUTools’09), Rome, Italy, Mar. 2009.
[21] X. Zhang, J. Kurose, B. N. Levine, D. Towsley, and H. Zhang, “Study of a bus-based disruption-tolerant network: mobility modeling and impact on routing,” in Proceedings of the 13th annual ACM international conference on Mobile computing and networking (MobiCom’07), Montreal, Quebec, Canada, 2007, pp. 195–206.

指導教授

胡誌麟(Chih-Lin Hu)

審核日期

2014-8-22

推文