基於社交及連接拓樸之延遲網路路由機制

Abstract

近年來在延遲網路上有許多路由的方法被發展出來，我們可以將它們細分成三大類: deterministic routing, message-ferrying routing 和opportunistic routing。deterministic routing假設系統知道不同時間點任二點之間的連接情況，並且利用最短路徑演算法找出一條具時序性的路由路徑(temporal path)，message-ferrying的路由主要是控制message ferry的行徑路徑來經過網路中所有的節點以達到任二個節點之間的通訊，opportunistic routing主要是算一個傳送評量(delivery metric)用以衝量一個節點有多好能傳送封包至目的地。 然而，如何計算一個正確的傳送評量(delivery metric)或是路由路徑基於不同的網路資訊如時間-空間圖 (space-time graph)或是社會關係資圖(social relation graph)是一個重要的問題，此外，怎麼在延遲網路中提供服務品質(QoS)是另一項挑戰，最後，在有限的記憶空間內怎麼樣提供好的管理和複本的散佈(replica distribution)也是重要的議題。 本論文共分成三個部分，在第一個部分我們提供了一個結合deterministic routing和message ferrying routing好處的方法，該方法使用了螞蟻演算法去設計一個多message ferry的路徑計算演法為了達到任二點之間的延遲降到最低，和過去的方法不同的是該方法的路徑設計考慮了網路節點會移動的情形。 本論文的第二部分主要是設計一個Early-Acknowledgment Opportunistic Routing提供不同的服務品質，我們稱之為EAOR，而這個方法的主要洞見是設計了一個傳送評量是依據在具機率性的時間-空間圖上算出最短具可靠度之時序性的路由路徑(shortest reliable temporal path)，此外，該方法也利用該可靠度時序性的路由路徑設計了early-acknowledgement的方法為了來提升系統的記憶體的使用率。 本論文的第三部分，我們設計了一個以Community-Relevance Opportunistic Routing，我們稱之為CROP，CROP主要是計算傳送評量基於在社交網路上的社群的資料結構(community structure)，這個新的傳送評量我們稱之為社群關聯 (community relevance)，社群關聯代表著社群-社群之間重要程度的關係，也表示著每個社群重要的程度會依封包所在的社群而有所有不同。 而實驗結果證明了我們所提出的三個方法至少可以有30%的網路傳送的提升，其外，EAOR可以有一個很好的取舍(trade-off)在封包傳輸時間和封包傳輸成功率上，實驗結果更證明了CROP可以將封包更公平的分散在網路中。

Researchers have developed several routing protocols for delay tolerant networks (DTNs) over the past few years. There are three major categories of the routing schemes in DTN: deterministic routing, message-ferrying routing and opportunistic routing. Deterministic routing discovers a shortest temporal routing path over the space-time graph. Message-ferry routing controls the motion of message ferries to visit all of the nodes for the packet dissemination. Opportunistic routing computes a delivery metric value to decide how best for a node to reach the destination node. However, how to compute an accurate delivery metric or routing path based on different networking information such as the time-varying graph or social relation graph is a major concern in DTN. On the other hand, how to provide different Quality of Service (QoS) is another important issue. Finally, how to management or distribute replica in the network is the other important issue. This dissertation contains three parts. In the first part, we propose a Mixed Deterministic and Message-Ferrying Routing (MDMFR) to get the benefit of the deterministic routing and the message-ferrying routing. MDMFR uses an Ant Colony Optimization (ACO) based algorithm to obtain the multi-ferry routes for minimizing the overall end-to-end routing delay between any two nodes. The main feature of MDMFR is that we compute a ferry route under consideration of the network nodes’ mobility. In the second part, we propose an Early-Acknowledgement Opportunistic Routing (EAOR) to achieve different levels of QoS in DTN. The key insight of EAOR is to compute a delivery metric based on a shortest reliable path over probabilistic time-varying graph. EAOR also designs a clever early-acknowledgement scheme based on the discovered shortest reliable path to enhance the buffer utilization in the network. In the third part, we propose a Community-Relevance Opportunistic Routing (CROP) based on social graph. CROP computes a new delivery metric called community relevance based on the social community structure. Community relevance represents each community-community relationship individually, which means that the level of importance of one community depends on the packet’s destination community. Simulation results validate that the proposed routing schemes achieve at least 30% delivery improvement compared to their relevant routing schemes, respectively. The simulation also confirms that EAOR can achieve a good trade-off between delay and reliability and CROP can distribute packets more fairly within the network.