地理式路由(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.

[1] N. Bulusu, J. Heidemann, and D. Estrin, “GPS-less low cost outdoor localizationfor very small devices’’ IEEE Pers. Commun., vol. 5, no. 5, pp. 28–34, Oct. 2000.

[2] Colin Lemmon, Siu Man Lui, Ickjai Lee “Review of Location-Aware Routing Protocols” Advances in Information Sciences and Service SciencesVolume 2, Number 2, June 2010

[3] S. Ruhrup. “Theory and Practice of Geographic Routing” Department of Computer Science, University of Freiburg, Germany. Feb 2009.

[4] B. Karp and H. T. Kung, “GPSR: Greedy perimeter stateless routing forwireless networks,” in Proc. ACM MOBICOM, Aug. 2000, pp. 243–254.

[5] Q. Fang, J. Gao, und L. J. Guibas, “Locating and bypassing routing holes in sensor networks”. In Proc. of INFOCOM 2004, vol.4, March 2004 pp.2458-2468

[6] E. Kranakis, H. Singh, and J. Urrutia, "Compass routing on geometric networks," in Proceedings of the 11th Canadian Conference on Computational Geometry (CCCG'99), Vancouver, 1999, pp. 51--54

[7] G. Finn, "Routing and addressing problems in large metropolitan-scale internetworks," Technical Report ISI/RR-87-180, ISI, 1987

[8] H. Takagi and L. Kleinrock, "Optimal transmission ranges for randomly distributed packet radio terminals," IEEE Transactions on Communications, vol. 32, pp. 246-257, March 1984.

[9] I. Stojmenovic and X. Lin, "Loop-free hybrid single-path/flooding routing algorithms with guaranteed delivery for wireless networks," IEEE Transactions on Parallel and Distributed Systems, vol. 12, pp. 1023-1032, October 2001.

[10] F. Kuhn, R. Wattenhofer, and A. Zollinger, "Asymptotically optimal geometric mobile ad-hoc routing," in Proc. of the 6th Int. Workshop on discrete algorithms and methods for mobile computing and communications, Atlanta, Georgia, USA, 2002, pp. 24-33.

[11] F. Kuhn, R. Wattenhofer, and A. Zollinger, "Worst-Case optimal and average-case efficient geometric ad-hoc routing," in Proc. of the 4th ACM Int. Symp. on Mobile Ad Hoc Networking & Computing, Annapolis, Maryland, USA, 2003, pp. 267-278.

[12] H. Hwang, I. Hur, and H. Choo, "GOAFR Plus-ABC: geographic routing based on adaptive boundary circle in MANETs," in Proc. of the 23rd int. conf. on Information Networking, Chiang Mai, Thailand, 2009, pp. 359-361.

[13] TOUSSAINT, G. The relative neighborhood graph of a _nite planar set,. Pattern Recognition 12, 4 (1980), 261.268.

[14] Y.Fucai , L.Euisin, “A Modeling for Hole Problem in Wireless Sensor Networks” IWCNC 2008.