导　　师： 王立松

学科专业： H1203

授予学位： 硕士

作　　者： ;

机构地区： 南京航空航天大学

摘　　要： 几何路由协议可以为无线传感器网络提供高效、可扩展的路由。基于节点虚拟位置的几何路由协议是其中一个崭新分支，此类协议中的网络节点不需要知道预定义的地理坐标，位置信息通过图嵌入的方法获得，路由根据图嵌入得到的虚拟坐标进行，从而有效降低节点定位所带来的能耗。路由算法是路由协议的核心，过去的相关算法主要缺陷在于节点虚拟坐标表示的复杂性，给传感器网络带来了无法忍受的存储开销。目前，SCHNYDER几何路由算法可有效解决这一问题，使几何路由变得简单高效，但SCHNYDER几何路由算法建立在严格的数学结构之上，当网络拓扑结构动态变化时（特别是节点失效），算法将不再适用。本文针对这一问题展开研究，主要研究了基于图嵌入的几何路由算法，解决了节点失效问题。
本文在SCHNYDER几何路由算法的基础上，研究并提出了容忍网络节点失效的几何路由算法。首先，针对3-连通平面图和平面三角剖分图中节点失效问题，提出简单高效的贪婪-指南针双模路由算法为消息的传递指明方向。接着提出用二次嵌入的方法可保证节点失效后的网络仍有100%的消息可达率：针对 3-连通平面图拓扑模型中的节点失效问题，提出基于图 ST-定向的树路由算法，该算法继承了SCHNYDER几何路由算法中节点坐标表示的简洁性；针对平面三角剖分图拓扑模型中区域节点失效引起的“空洞”问题，使用基于 RICCI 流的共形映射算法将带有不规则形状“空洞”的网络映射为带有圆形“空洞”的圆盘，从而保证网络中不存在局部最小点，使贪婪几何路由能够顺利进行。
针对于本文设计的几何路由算法，通过仿真实验和对实验结果的分析，可以看到，本文研究和设计的几何路由算法可以有效解决几何路由算法中的节点失效问题。

关 键 词： 无线传感器网络 几何路由算法 图嵌入 嵌入 节点失效 共形映射

分 类 号： [TP393]

领　　域： [自动化与计算机技术] [自动化与计算机技术]