在地理性路由(geographic routing)中，每個節點(node)都選擇鄰居之中離目的節點(destination)最近的作為轉送的下一個節點。這種轉送(forwarding)的方式稱之為貪婪轉送(greedy forwarding)，同時此種方法在成功實施的情況下也被證明為會近似最短路徑。然而貪婪轉送遇到局部極小(local minima)的情況時，會因為死路(dead end)的發生而無法繼續進行傳送。此問題可透過將整個網路分割成可單獨執行貪婪轉送的區塊來改善。以往的網路分割演算法大多為集中式，而集中式的演算法會存在傳輸訊息壅塞以及單點故障(single point of failure)的問題。在本論文，我們設計一個分散式的演算法Localized GRR Decomposition (LGD)來對整個網路進行貪婪區塊(Greedily Routable Region)的切割。在亂數產生網路中，我們的演算法與已知的演算法比較可產生更少的貪婪區塊。此外，LGD演算法也會因為分散式演算法的特性，使得分割所需的溝通負擔(overhead)減少。 In geographic routing, a node selects the neighbor closest to the destination to forward the packet. This scheme is known as the greedy forwarding, and has been shown to produce sub-optimal route when it works. However, the greedy forwarding may fail if the packet is forwarded to a local minimum. One way to solve this issue is to partition the network into a number of pieces. Within each piece, the greedy forwarding scheme is guaranteed to work. The network partition algorithms proposed in the past are centralized, which naturally suffer from message congestion and the single point of failure. In this thesis, we propose a distributed algorithm, namely Localized GRR Decomposition (LGD), to partition the network into a number of greedily routable regions. Using randomly generated sensor networks, we show that our algorithm is able to produce a lower number of GRRs when compared with the best known result. Additionally, the communication overhead of our LGD algorithm is lower due to its distributed nature.
