Trap array: a unified model for scalability evaluation of geometric routing
Trap array: a unified model for scalability evaluation of geometric routing
复制标题
DOI：
10.1109/tnet.2014.2362943
复制
发表时间：
2013-06
期刊：
影响因子：
--
通讯作者：
Guang Tan;Zhimeng Yin;Hongbo Jiang
中科院分区：
文献类型：
--
作者：
Guang Tan;Zhimeng Yin;Hongbo Jiang
大规模无线网络的可扩展路由需要在每个节点上寻找状态较低的近最短路径，最好与网络规模呈次线性关系。有两种方法被认为有望实现这一目标：紧凑路由和几何路由（地理路由）。迄今为止，这两种研究在很大程度上是独立的，也许是因为它们遵循不同的原则。特别是，尽管大量的实验结果显示在特定情况下其中一个或另一个具有优势，但在最坏的情况下它们如何相互比较仍不清楚。我们开发了一种新的Trap阵列拓扑模型，该模型提供了一个统一的框架来揭示10种代表性地理路由算法的限制行为。我们提出了一系列新的理论结果，比较了紧凑路由作为基准的性能。考虑到它们的优缺点，我们进一步设计了一种紧凑几何路由（CGR）算法，试图利用这两种方法的优点。理论分析和仿真结果表明了该拓扑模型和算法的优越性。
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.