地理式路由在隨意無線網路的死路改進

Abstract

地理式路由(Geographic routing)近年來一直被應用在各種網路環境，例如:無線隨意網路(Wireless Ad-Hoc Networks)、無線感測網路(Wireless Sensor Networks)、以及車載網路(VANET)，而地理式路由基本假設在於網路環境中的節點均知道自己所在的位置資訊，這點可經由全球定位系統(GPS)的技術達成。而在地理式路由中所遭遇到local minima的問題則經由Greedy Perimeter Stateless Routing (GPSR)演算法解決，然而GPSR演算法在選擇路徑的過程中，當在進入環繞模式中，因為逆時針定則導致產生路徑hop數較高的現象，因此造成封包延遲上升，為減緩這個現象，本論文提供兩個利用節點位置資訊將節點鄰居分群的路由演算法以延緩進入環繞模式的時間點來改善此一問題。 在本作中，我們提供了Quasi Greedy Geographic routing (QGGR)演算法藉由利用了與鄰居節點的相對位置給予每個節點一個θα值，再以依此作為分群的依據給予不同的優先度，以降低發生Dead end的機率，並且減少了Hop count，再來我們更進一步的導入Dynamic-Quasi Greedy的概念，讓分群的標準基於鄰居節點和目的端的距離，不需要預先知道節點密度或是網路大小等其他資訊；我們的模擬實驗結果顯示此二方法有助改善環繞模式中逆時針定則所產生路徑數上升之現象。

Many geographic routing protocols for wireless ah-hoc network have been proposed in the literatures in recent years. In geographic routing, each node in networks is aware of the location itself by GPS. The solution of local minima problem is Greedy Perimeter Stateless Routing (GPSR). However, in GPSR, when packets enter perimeter mode, hop count will increase because of right-hand rule. To improve this problem, we provide two algorithms to achieve Dead-end reduction. The essential technique employed is to divide neighbor nodes into two groups according to location information and angles between each pair of circularly consecutive neighboring nodes. In the thesis, we propose a Quasi Greedy Geographic routing (QGGR) algorithm in which a constant threshold θt is used to determine a partition of neighbor nodes into two groups. The group of neighbor nodes with max angle less than θt has higher priority than other group in the process of greedy forwarding. Furthermore, we introduce a Dynamic-Quasi Greedy algorithm in which the threshold θt is adapted according to the distance between current node and destination node. The simulation results show that QGGR and DQGGR could achieve better hop count performance and Dead-end reduction than GPSR.