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

NCUIR > College of Electrical Engineering & Computer Science > Graduate Institute of Communication Engineering > Electronic Thesis & Dissertation > Item 987654321/54376

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/54376

Title:	耐延遲網路下訊息傳遞時間分析與高效能路由演算法設計;On Analyzing Message Delivery Time for Efficient Routing Designs in Delay Tolerant Networks
Authors:	陳大猷;Chen,Da-you
Contributors:	通訊工程研究所
Keywords:	訊息傳遞;路由協定;耐延遲網路;message delivery;routing protocol;Delay tolerant network
Date:	2012-07-25
Issue Date:	2012-09-11 18:49:32 (UTC+8)
Publisher:	國立中央大學
Abstract:	在耐延遲網路中，由於節點密度稀疏以及傳輸距離的限制，網路拓撲往往是破碎、不連通的。在此種環境下，大部分的節點之間並不存在一條點到點的路徑，故傳統隨建即連網路(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 intoconsideration 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.
Appears in Collections:	[Graduate Institute of Communication Engineering] Electronic Thesis & Dissertation

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	497	View/Open

社群 sharing

Loading...