基于贪婪陷阱模型的几何路由可伸缩性研究

Point-to-point routing for multi-hop wireless networks needs to be highly scalable. Toward this goal, geomeric routing is considered an important apporach, and has thus attracted intensive research efforts in recent years.The existing algorithms are mostly verified thourgh simulations only, without rigorous theorectical characterization. Our analysis shows that the greedy nature of geometric routing has serious limitations in extrmeme conditions, thus making many algorithms exhibit far worse performance than the ecpectation of prior work. We attempt to conduct the first systematic study on this issue, with the following objectives: (1) Establishment of a novel topology model, with the notion of "greediness traps", in support of more powerful, more controllable, and observable stress testing of geometric routing algorithms; (2) Establishment of theoretical bounds for the scalability of more than ten representative algorithms; (3) Design of new algorithms by introducing the element of compact routing, which helps to avoid the short-sightedness of geometric routing while preserving its advantages; (4) Design of highly scalable geometric routing algorithms for 3D spaces. The results of this research project are expected to bring important insights into the properties of geometric routing and to advance our understanding of multi-hop wireless networks.

在大规模无线多跳网络中，点对点路由必须满足高可伸缩性（Scalability）。几何路由被认为是实现这个目标的一个重要途径，因而近年来得到高度关注。已有算法绝大多数只是通过仿真进行性能评估，而缺乏严格的理论刻画。我们前期工作发现，几何路由的贪婪转发模式在极端情况下存在重大局限，导致许多代表性算法的最坏性能远差于前人预期。本项目将首次对此问题进行系统的研究。内容包括：（1）从贪婪路由的短视性这个新角度，构造拓扑模型，为算法的理论和实验评估提供一个高强度、可控、易观察和分析的压力测试工具；（2）建立统一的几何路由算法理论评估框架，填补主要算法在可伸缩性理论上限方面的空白；（3）引入紧凑路由的元素，克服几何路由的短视性缺陷，产生具有理论保证的新型路由算法；（4）推进三维空间里高可扩展几何路由的研究。本项目的研究将为几何路由理论作出重要的补充，同时为无线多跳网络的设计提供更加深入的认识。

多跳无线网络作为下一代互联网的重要组成部分，近年来得到工业界和学术界的广泛关注。在大规模无线多跳网络中，如何利用有限的资源来完成网络内部的高可伸缩性的路由，成为一个重要的技术挑战。本项目对此问题进行系统的研究，主要完成了四个方面的研究工作。（1）设计了一个新的几何路由算法CGR，提出贪婪陷阱模型和几何路由优化方法；（2）探讨了无线传感器网络中凹点对网络几何处理的关键作用，设计了局部化的凹点提取算法，对网络几何路由的性能有显著的提升作用；（3）研究了三维传感器网络路由，提出一个新的可扩展的几何寻址和路由方案OnionMap，显著降低了路径延展；（4）研究了无线网络相关性接收问题，考虑不同接受节点的多样性路由，提出一种统一的传输开销估计指标，从而实际路由协议能更智能地进行策略选择。本项目的研究为多条无线网络路由理论作出了重要的补充，为无线多跳网络、三维传感器网络等领域提供新的认识。