陷阱阵列:一个衡量几何路由可扩展性的通用模型

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

提出了一个新颖的陷阱阵列拓扑模型作为一个统一的框架来揭示一种代表性的几何路由算法的极限性能。以紧凑路由的性能为基准,本文给出了一系列新的路由性能的理论对比结果。鉴于这一种算法的利弊分析,我们尝试结合上述两类路由策略的优点,进一步设计出了一种紧凑几何路由算法(CGR)。理论分析和仿真都显示了本文提出的陷阱阵列拓扑模型和紧凑几何路由算法的优越之处。

Scalable routing for large -scale wireless networks needs to find near shortest paths with low state on each node, preferably sub - linear with the network size. Two approaches are considered promising towards 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 fol- low. In particular, it remains unclear how they compare with each other in the worst case, despite extensive experimental results show- ing the superiority of one or another in particular cases. We develop a novel Trap Array topology model that provides a unified frame- work to uncover the limiting behavior of ten representative geo - routing algorithms. We present a series of new theoretical results, in comparison with the performance of compact routing as a baseline. In light of their pros and cons, we further design a Compact Geomet- ric 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.