中文摘要：

当前的传感器网络已发展至千节点级规模。在这类网络中，如何利用极为有限的节点资源实现点对点（近似）最短路径路由是一个基础问题。现有工作对于此类网络的理论阐述尚不够完全，实现也不知是否已达到最优。本项目拟在紧凑路由（Compact Routing）理论的框架下，考察在常数路径延展（Stretch）约束下，节点在最坏情况下需要的最少状态/消息开销，以及如何设计算法实现或靠近这个最优点。具体研究内容包括（1）建立体现网络布局几何特征的新型网络模型，并探讨常数延展约束下节点开销的下界；（2）提出一种新的概念近似可贪婪路由组件，研究基于该概念的网络划分方法；（3）研究新型的网络贪婪嵌入方法；（4）设计完整的路由协议，并通过试验床和仿真进行性能评价。本项目的研究将为紧凑路由理论作出重要的补充，同时将提供新的算法设计思想，为传感器网络乃至更广泛的无线多跳网络设计带来更深入的认识。

结论摘要：

围绕无线传感器网络的高效路由关键问题，本项目产生了以下几项成果（1） 面向几何路由的最小网络分割方法。在无线传感器网络的几何路由中，消息默认按照如下贪婪的方式进行转发当前节点常常将消息转发至距离目标节点最近的邻居节点。虽然贪婪路由简捷且有效，但由于几何路由中局部最小情况的存在，单靠贪婪路由的策略不能够保证成功的消息传送。而为了避免节点陷入局部最小，需要节点维护额外的非本地状态或者需要采取一些其他的辅助措施。我们研究了在复杂网络中，仅利用最少量的全局信息来进行贪婪路由。特别的，探讨了在保证成功的贪婪路由的前提下，将给定网络分解为最少数量的可贪婪路由分量（GRC）的问题。通过近似连续域中可贪婪路由区域（GRR）的概念和完整地给出GRR 的几何特性及路由特性，提出了一些简单的近似算法解决了前述的GRC 的问题。仿真结果表明，在连续域中，路由伸展值小于7；且在一些真实的网络中，路由伸展值接近1。该文发表在IEEE/ACM Transaction on Networking, 2012。（2）传感器网络的凸分区算法。该项工作考虑的是网络中的内凹部分会对贪婪几何转发造成干扰，是导致几何路由性能下降的主要因素，因此提出将网络进行凸分区，而在众分区之上利用一种全局的结构来抽象网络。工作的挑战是如何只利用连接信息来完成分区，这涉及到凹角的判定和划分。在此基础上，设计了一种混合的路由算法。实验展示性能比经典的路由方法有显著提高。工作发表在ACM Transaction on Sensor Networks, 2013. （3）基于连接信息的复杂拓扑三维传感器网络定位算法。通过一种新颖的凹点判断方法，排除被凹点扭曲的路径，对多边定位算法进行矫正。方法显示对网络节点的定位能够达到较高的精度。定位结果能够为几何路由提供直接的支持。