在耐延遲網路上利用時間與空間資訊的叢集式路由機制

Abstract

耐延遲網路因為高延遲的因素而與傳統網路在路徑尋找的方法有所不同，其差別是耐延遲網路中封包在空間上沒有路徑可以傳遞，因此利用空間與時間的資訊將未來的連線狀況加以考慮而形成一個具空間連結與時間連結的圖形，並用最短路徑演算法在此圖形中尋找延遲最小的封包傳遞路徑。此圖形因為具有時間連結，因此圖形大小與考慮的時間成正比。而在耐延遲網路中，因其高延遲而導致考慮的時間增大，形成的圖形與計算最短路徑的複雜度亦因此過高•本篇即是假設節點之間的未來連線狀況可由知識庫得知的情形下，提出一個減小計算圖形，同時接近最小延遲路徑的繞徑演算法。我們的方法是將節點利用叢集的方式分群，並利用叢集形成具空間連結與時間連結的圖形即叢集拓撲，然後利用此叢集拓撲來找尋最短路徑。根據模擬實驗結果顯示，此方法使圖形減小而計算複雜度也因此降低，同時可以找到接近最小延遲路徑。而利用叢集以減少複雜度的方法，由於節點會透過叢集管理者來傳遞封包，導致叢集管理者負擔過重，因此我們提出叢集負載平衡選擇較低負擔的節點當作叢集管理者和閘道節點來減少壅塞。

Routing in Delay Tolerance Network (DTN) is different from that in conventional networks because of high delivery delay. The main difference is that packets in DTN do not have end to end paths in the space domain. Therefore, we use space and time information to form a graph with links in the space and time domain, and apply the Dijkstra algorithm to find the shortest routing path. Because the graph contains links in time domain, the graph size is proportional with time. In DTN, the high delay leads to a larger graph, so the complexity of finding the shortest path becomes large. In this thesis, we assume the connections between nodes can be known by a knowledge oracle, and propose a cluster-based algorithm to reduce the size of the space and time graph needed by finding the shortest routing path with minimal delivery delay. Our proposed method is using clustering to group the nodes into clusters, and using the clusters to form a cluster topology with links in the space and time domain. Then, we can use the cluster topology to find the routing path. Through simulation, the complexity of cluster-based routing is decreased, and the routing path is also close to the path with minimal delivery delay. However, the load of cluster heads becomes heavier because packets will be sent through cluster heads in cluster-based routing. So we propose load balance clustering to choose nodes with lower loads to be cluster heads and gateway nodes in order to avoid congestion of nodes with higher loads.