耐延遲網路下訊息傳遞時間分析與高效能路由演算法設計

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：15

、訪客IP：3.143.168.172

姓名

陳大猷(Da-you Chen) 查詢紙本館藏

畢業系所

通訊工程學系

論文名稱

耐延遲網路下訊息傳遞時間分析與高效能路由演算法設計
(On Analyzing Message Delivery Time for Efficient Routing Designs in Delay Tolerant Networks)

相關論文

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

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

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

摘要(中)

在耐延遲網路中，由於節點密度稀疏以及傳輸距離的限制，網路拓撲往往是破碎、不連通的。在此種環境下，大部分的節點之間並不存在一條點到點的路徑，故傳統隨建即連網路(MANET)上的路由協定並不適合直接使用在耐延遲網路上。為了提高訊息在耐延遲網路中的到達率，大多數的耐延遲路由協定會採用複製而非轉送的方式傳遞訊息。但是，在資源有限的環境下，大量的訊息副本會快速的消耗網路中的頻寬、儲存空間與電力等資源，造成整體訊息到達率的下降。因此，如何在資源有限的環境下，以較小的訊息複製量達到良好的訊息到達率是本論文考量的首要課題。先前研究觀察到，人類、動物的行為模式具有歷史特性。根據此現象，本論文提出一套以訊息傳遞延遲時間做為合適性指標的時間戳記路由機制，將節點過去與其它節點的訊息傳遞延遲時間做為參考依據，判斷節點對於某份訊息的合適程度高低，透過此項資訊，節點可做出聰明的路由決策，避免盲目的訊息複製。時間戳記路由機制包含訊息傳遞延遲時間估測機制與路由策略兩個部份，在訊息傳遞延遲時間估測機制中，本論文以廣播時間戳記的方法為基礎，配合一系列的分析、觀察、設計與改良，提出一套易於管理且低訊息量成本的估測機制，使節點可以在低訊息量複雜度O(n)的花費下，藉由簡單的控制訊息交換，估測出自身與環境中其它節點的訊息傳遞延遲時間。在路由策略方面，本論文考量到真實環境中，網路資源(頻寬、儲存空間、電力)有限的問題，針對複製對象篩選、傳送佇列排序以及儲存空間管理三個部份做出相應的演算法設計，使節點可以更有效率的利用頻寬與儲存空間等資源，在每個訊息可分配到的網路資源降低時，減緩訊息到達率的下降幅度。最後，本研究透過不同的節點移動模型來模擬驗證所提出的時間戳記路由演算機制在訊息到達成功率、訊息傳遞延遲時間與訊息複製數量等三個指標上的表現，並與其它路由協定做比較，模擬結果顯示本論文所提出的路由方法有更佳的訊息到達率，亦能大幅降低訊息複製的數量及傳輸成本。

摘要(英)

Due to the sparse node density and limited transmission range, delay tolerant networks(DTNs) are lack of continuous network connectivity. In such environments, most of the time, end-to-end paths does not exist between any pair of source and destination nodes, thus the traditional end-to-end based MANET routing protocols can not achieve satisfactory performance in DTNs. In order to improve the message delivery ratio in DTN environments, most of the DTN routing protocols apply replication-based routing, however, in resource-constraint environments, large number of message copies will consume great amounts network resource like bandwidth or storage space. Therefore, the primary goal of this study is to design a DTN routing protocol which can achieve good message delivery ratio with low message replications. Previous studies observed that humans mobility patterns have historic properties. Based on this observation, this paper proposes a routing algorithm called Timestamp Routing Scheme (TRS) which used the message delivery delay as an utility metric to operate smart routing. TRS contains two part: message delivery delay estimation scheme and routing strategy. In message delivery delay estimation scheme, each node estimated the message delivery delay by broadcasting timestamp. Through a series of analysis and design, the proposed estimation scheme can let node to estimated the message delivery delay to other nodes under low control message overhead O(n). In routing strategy, TRS takes the real environment constraint into
consideration and design corresponding routing strategies include replicate message selection, transmission queue schedule and buffer management scheme. By those strategies, nodes can use bandwidth and storage resources more efficiently and achieve better message delivery ratio under resource-constraint environments. Finally, the simulation result shows that the proposed Timestamp Routing Scheme can achieve higher delivery ratio and generate less message copies than compared routing protocols in three experiment mobility model.

關鍵字(中)

★ 訊息傳遞
★ 路由協定
★ 耐延遲網路

關鍵字(英)

★ message delivery
★ routing protocol
★ Delay tolerant network

論文目次

1 簡介1
2 相關文獻探討6
2.1 現有的路由技術之探討與比較： 6
2.2 耐延遲網路中節點移動模型之探討與比較12
3 訊息傳遞延遲時間分析16
3.1 前提與假設16
3.2 路由模型分析18
3.3 系統架構19
3.4 多跳數與多路徑狀況下之分析21
3.5 多變量轉換法26
3.6 數值計算法複雜度分析31
4 訊息傳遞延遲時間估測機制35
4.1 基本估測機制與控制訊息格式36
4.2 控制訊息的運作規則：戳記的產生、交換與刪除38
4.3 訊息傳遞延遲時間之估算40
4.4 同步機制之探討41
4.5 控制訊息之精簡化45
5 時間戳記路由機制之策略與設計47
5.1 前置訊息交換48
5.2 複製對象篩選49
5.3 傳送佇列排序機制53
5.4 儲存空間管理54
6 模擬及數據分析55
6.1 模擬環境55
6.2 對照路由技術介紹56
6.3 移動模型58
6.4 模擬結果與分析62
6.5 實驗結果總結94
7 結論97
參考文獻98

參考文獻

[1] P. Juang, H. Oki, Y. Wang, M. Martonosi, L. S. Peh, and D. Rubenstein, “Energy-efficient computing for wildlife tracking: design tradeoffs and early experiences with zebranet,” SIGOPS Oper. Syst. Rev., vol. 36, pp. 96–107, Oct. 2002.
[2] A. Lindgren and A. Doria, “Experiences from deploying a real-life dtn system,” in Proceedings of IEEE International Conference Consumer Communications and Networking,pp. 217 –221, Jan 2007.
[3] K. Fall, “A delay-tolerant network architecture for challenged internets,” in Proceedings of ACM conference on Applications, technologies, architectures, and protocols for computer communications, SIGCOMM ’03, pp. 27–34, 2003.
[4] E. M. Daly and M. Haahr, “The challenges of disconnected delay-tolerant manets,” Ad Hoc Networks, vol. 8, no. 2, pp. 241 – 250, 2010.
[5] D. Johnson and D. Maltz, “Dynamic source routing in ad hoc wireless networks,” Mobile computing, pp. 153–181, 1996.
[6] C. Perkins and E. Royer, “Ad-hoc on-demand distance vector routing,” in Proceedings of Mobile Computing Systems and Applications, pp. 90 –100, feb 1999.
[7] P. Jacquet, P. Muhlethaler, T. Clausen, A. Laouiti, A. Qayyum, and L. Viennot, “Optimized link state routing protocol for ad hoc networks,” in Proceedings of of IEEE International INMIC, pp. 62 – 68, 2001.
[8] Y. Li, M. Qian, D. Jin, L. Su, and L. Zeng, “Adaptive optimal buffer management policies for realistic dtn,” in Proceedings of IEEE Global Telecommunications Conference, pp. 1–5, 30 2009-dec. 4 2009.
[9] J. Burgess, B. Gallagher, D. Jensen, and B. N. Levine, “Maxprop: Routing for vehiclebased disruption-tolerant networks,” in Proceedings of IEEE INFOCOM, pp. 1 –11, April 2006.
[10] T. Spyropoulos, R. N. Rais, T. Turletti, K. Obraczka, and A. Vasilakos, “Routing for disruption tolerant networks: taxonomy and design,” Wireless Networks, vol. 16, pp. 2349–2370, Nov 2010.
[11] W. Zhao, M. Ammar, and E. Zegura, “A message ferrying approach for data delivery in sparse mobile ad hoc networks,” in Proceedings of ACM international symposium onMobile ad hoc networking and computing, pp. 187–198, 2004.
[12] R. C. Shah, S. Roy, S. Jain, and W. Brunette, “Data mules: modeling and analysis of a three-tier architecture for sparse sensor networks,” Ad Hoc Networks, vol. 1, pp. 215 –233, 2003.
[13] M. C. Gonz’alez, C. A. Hidalgo, and A.-L. Barab’asi, “Understanding individual human mobility patterns,” Nature, vol. 453, no. 7196, pp. 779–782, 2008.
[14] C. Song, Z. Qu, N. Blumm, and A.-L. Barabasi, “Limits of predictability in human mobility,” Science, vol. 327, no. 5968, pp. 1018–1021, 2010.
[15] H. Dubois-Ferriere, M. Grossglauser, and M. Vetterli, “Age matters: efficient route discovery in mobile ad hoc networks using encounter ages,” in Proceedings of ACM International Symposium on Mobile Ad Hoc Networking and Computin, pp. 257–266, 2003.
[16] V. Erramilli, A. Chaintreau, M. Crovella, and C. Diot, “Diversity of forwarding paths in pocket switched networks,” in Proceedings of ACM SIGCOMM conference on Internet measurement, pp. 161–174, ACM, 2007.
[17] A. Lindgren, A. Doria, and O. Schelen, “Probabilistic routing in intermittently connected networks,” SIGMOBILE Mob. Comput. Commun. Rev., vol. 7, pp. 19–20, Jul 2003.
[18] E. Jones, L. Li, J. Schmidtke, and P. Ward, “Practical routing in delay-tolerant networks,” Mobile Computing, IEEE Transactions on, vol. 6, pp. 943 –959, Aug 2007.
[19] C. Liu and J. Wu., “Practical routing in a cyclic mobispace,” IEEE/ACM Transactions on Networking (TON), vol. 19, no. 2, pp. 369–382, 2011.
[20] T. Spyropoulos, K. Psounis, and C. Raghavendra, “Single-copy routing in intermittently connected mobile networks,” in Proceedings of IEEE SECON, pp. 235–244, IEEE, 2004.
[21] A. Vahdat and D. Becker, “Epidemic routing for partially connected ad hoc networks,” tech. rep., Technical Report CS-200006, Duke University, 2000.
[22] A. Keranen, T. Karkkainen, and J. Ott, “Simulating mobility and dtns with the one,” Journal of Communications, vol. 5, no. 2, pp. 92–105, 2010.
[23] S. C. Nelson, A. F. H. III, and R. Kravets, “Event-driven, role-based mobility in disaster recovery networks,” in Proceedings of ACM workshop on Challenged networks, pp. 27–34, 2007.
[24] K. Lee, S. Hong, S. J. Kim, I. Rhee, and S. Chong, “Slaw: A new mobility model for human walks,” in Proceedings of IEEE INFOCOM, pp. 855 –863, April 2009.
[25] Spyropoulos, Thrasyvoulos, P. Konstantinos,Raghavendra, and C. S., “Spray and wait: an efficient routing scheme for intermittently connected mobile networks,” in Proceedings of SIGCOMM workshop on Delay-tolerant networking, pp. 252–259, 2005.
[26] S. C. Nelson, M. Bakht, and R. Kravets, “Encounter-based routing in dtns,” in Proceedings of IEEE INFOCOM, pp. 846 –854, April 2009.
[27] T. Spyropoulos, K. Psounis, and C. S. Raghavendra, “Spray and focus: Efficient mobilityassisted routing for heterogeneous and correlated mobility,” in Proceedings of IEEE International Conference on Pervasive Computing and Communications Workshops, pp. 79–85, March 2007.
[28] V. Erramilli, M. Crovella, A. Chaintreau, and Christophe, “Delegation forwarding,” in Proceedings of ACM international symposium on Mobile ad hoc networking and computing,pp. 251–260, 2008.
[29] A. Balasubramanian, B. N. Levine, and A. Venkataramani, “Replication routing in dtns: A resource allocation approach,” IEEE/ACM Transactions on Networking, vol. 18, pp. 596–609, April 2010.
[30] A. Chaintreau, P. Hui, J. Crowcroft, C. Diot, R. Gass, and J. Scott, “Impact of human mobility on opportunistic forwarding algorithms,” IEEE Transactions on Mobile Computing,vol. 6, pp. 606 –620, June 2007.
[31] T. Karagiannis, J.-Y. L. Boudec, and M. Vojnović, “Power law and exponential decay of intercontact times between mobile devices,” IEEE Transactions on Mobile Computing,vol. 9, pp. 1377 –1390, Oct 2010.
[32] C. Bettstetter, H. Hartenstein, and X. Perez-Costa, “Stochastic properties of the random waypoint mobility model,” Wireless Network, vol. 10, pp. 555–567, Sep 2004.
[33] S. Yang, X. Yang, C. Zhang, and E. Spyrou, “Using social network theory for modeling human mobility,” IEEE Network, vol. 24, pp. 6 –13, September-October 2010.
[34] C. Boldrini and A. Passarella, “Hcmm: Modelling spatial and temporal properties of human mobility driven by users’ social relationships,” Computer Communications, vol. 33,no. 9, pp. 1056 – 1074, 2010.
[35] P. Nain, D. Towsley, B. Liu, and Z. Li, “Properties of random direction models,” in Proceedings of of IEEE INFOCOM, vol. 3, pp. 1897 – 1907 vol. 3, March 2005.
[36] W. jen Hsu, T. Spyropoulos, K. Psounis, and A. Helmy, “Modeling time-variant user mobility in wireless mobile networks,” in Proceedings of of IEEE INFOCOM, pp. 758–766, May 2007.
[37] M. Musolesi and C. Mascolo, “Designing mobility models based on social network theory,” SIGMOBILE, vol. 11, pp. 59–70, July 2007.
[38] I. Rhee, M. S. S. Hong, K. Lee, S. J. Kim, and S. Chong, “On the levy-walk nature of human mobility,” IEEE/ACM Transactions on Networking, vol. 19, pp. 630–643, Jun 2011.
[39] D. Brockmann, L. Hufnagel, and T. Geisel, “The scaling laws of human travel,” Nature,vol. 439, no. 7075, pp. 462–465, 2006.
[40] M. Kim, D. Kotz, and S. Kim, “Extracting a mobility model from real user traces,” in Proceedings of IEEE INFOCOM, pp. 1 –13, April 2006.
[41] V. Conan, J. Leguay, and T. Friedman, “The heterogeneity of inter-contact time distributions:its importance for routing in delay tolerant networks,” Arxiv preprint cs/0609068,2006.
[42] W. Gao, Q. Li, B. Zhao, and G. Cao, “Multicasting in delay tolerant networks: a social network perspective,” in Proceedings of ACM international symposium on Mobile ad hoc networking and computing, pp. 299–308, 2009.
[43] Y. Li, Z. Wang, D. Jin, L. Su, L. Zeng, and S. Chen, “Optimal beaconing control for epidemic routing in delay-tolerant networks,” IEEE Transactions on Vehicular Technology,vol. 61, pp. 311 –320, Jan 2012.
[44] E. Altman, G. Neglia, F. De Pellegrini, and D. Miorandi, “Decentralized stochastic control of delay tolerant networks,” in Proceedings of IEEE INFOCOM, pp. 1134 –1142, April 2009.
[45] H. Jun, M. H. Ammar, and E. W. Zegura, “Power management in delay tolerant networks:A framework and knowledge-based mechanisms,” in Proceedings of IEEE SECON,vol. 60, 2005.
[46] Y. Xi, M. Chuah, and K. Chang, “Performance evaluation of a power management scheme for disruption tolerant network,” Mobile Networks and Applications, vol. 12, pp. 370–380, Dec. 2007.
[47] M. Sasabe and T. Takine, “A simple scheme for relative time synchronization in delay tolerant manets,” in Proceedings of IEEE International Conference on Intelligent Networking and Collaborative Systems, pp. 395–396, 2009.
[48] B. J. Choi and X. Shen, “Distributed clock synchronization in delay tolerant networks,”in Proceedings of IEEE International Conference on Communications (ICC), pp. 1 –6,May 2010.
[49] A. Keranen, J. Ott, and T. Karkkainen, “The one simulator for dtn protocol evaluation,”in Proceedings of ICST International Conference on Simulation Tools and Techniques,2009.
[50] J. Vig, “Introduction to quartz frequency standards. revision,” tech. rep., DTIC Document,1992.

指導教授

胡誌麟(Chih-Lin Hu)

審核日期

2012-7-25

推文