FLYER: Fine-grained landmark based greedy geographic routing under uncertain locations

Greedy geographic routing is widely adopted in practical wireless networks due to its simplicity. However, greedy geographic routing alone cannot guarantee the delivery of packets due to the existence of local minima. A number of solutions have been proposed to address this issue, such as face routing, landmark-based routing, network segmentation or virtual coordinate based methods, etc. However, these solutions either have various limitations, such as depending on exact node locations, requiring costly preprocessing of the global network topology, or have obvious performance shortcomings, such as severe load-imbalance, large path stretch factors, etc. In this work, we attempt to combine the advantages of existing solutions, and present a hierarchical greedy geographic routing scheme. This design, FLYER, neither depends on exact node locations, nor needs to store any global state information in each node, which makes it applicable and scalable in large-scale practical systems. Moreover, our routing scheme is able to produce route paths with lower stretch factors and more load-balancing property than existing solutions. The algorithm works in a completely localized fashion, and the additional storage and computation complexity is extremely low. Extensive simulations are conducted, and the results demonstrate the superior performance of our approach against the state-of-the-art methods.