Geographical quadtree routing

In this paper we offer a novel geographical routing algorithm that relies on a well known data structure called Quadtree. Quadtree is an efficient method of mapping a two-dimensional area by recursively partitioning it to disjoint squares. We present a greedy, guaranteed delivery routing algorithm called Greedy-Quadtree-Greedy (GQG). The algorithm is robust to dynamics in the non-Quadtree edges and overcomes local minimums without the use of planarization, face routing, or searching. GQG is a tree-based routing algorithm; it makes greedy forwarding based the location information that is extracted from the Quadtree addresses of the nodes. Bypassing voids is done by a concept of ”tree routing with shortcuts”, which can significantly improve hop stretch and load balancing. As part of the routing system, we present three algorithms: address distribution, network topology discovery, and geographical routing with guaranteed delivery. We keep all broadcasts bounded to one hop, and the nodes´ routing state depends on their degree rather than the overall network size. We prove the correctness of the algorithms and present simulations that show the protocol improvement over simple tree-based routing.