Trap Array: A Unified Model for Scalability Evaluation of Geometric Routing

Scalable routing for large-scale wireless networks needs to find near shortest paths with low state on each node, preferably sublinear with the network size. Two approaches are considered promising toward this goal: compact routing and geometric routing (geo-routing). To date, the two lines of research have been largely independent, perhaps because of the distinct principles they follow. In particular, it remains unclear how they compare to each other in the worst case, despite extensive experimental results showing the superiority of one or another in particular cases. We develop a novel Trap Array topology model that provides a unified framework to uncover the limiting behavior of 10 representative geo-routing algorithms. We present a series of new theoretical results, in comparison to the performance of compact routing as a baseline. In light of their pros and cons, we further design a Compact Geometric Routing (CGR) algorithm that attempts to leverage the benefits of both approaches. Theoretical analysis and simulations show the advantages of the topology model and the algorithm.