导　　师： 王立松

学科专业： 081203

授予学位： 硕士

作　　者： ;

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

摘　　要： 几何路由协议可以为无线传感器网络提供高效、可扩展的路由。基于节点虚拟位置的几何路由协议是其中一个崭新分支，此类协议中的网络节点不需要知道预定义的地理坐标，位置信息通过图嵌入的方法获得，路由根据图嵌入得到的虚拟坐标进行，从而有效降低节点定位所带来的能耗。路由算法是路由协议的核心，过去的相关算法主要缺陷在于节点虚拟坐标表示的复杂性，给传感器网络带来了无法忍受的存储开销。目前，Schnyder几何路由算法可有效解决这一问题，使几何路由变得简单高效，但Schnyder几何路由算法建立在严格的数学结构之上，当网络拓扑结构动态变化时（特别是节点失效），算法将不再适用。本文针对这一问题展开研究，主要研究了基于图嵌入的几何路由算法，解决了节点失效问题。 本文在Schnyder几何路由算法的基础上，研究并提出了容忍网络节点失效的几何路由算法。首先，针对3-连通平面图和平面三角剖分图中节点失效问题，提出简单高效的贪婪-指南针双模路由算法为消息的传递指明方向。接着提出用二次嵌入的方法可保证节点失效后的网络仍有100/%的消息可达率：针对3-连通平面图拓扑模型中的节点失效问题，提出基于图st-定向的树路由算法，该算法继承了Schnyder几何路由算法中节点坐标表示的简洁性；针对平面三角剖分图拓扑模型中区域节点失效引起的“空洞”问题，使用基于Ricci流的共形映射算法将带有不规则形状“空洞”的网络映射为带有圆形“空洞”的圆盘，从而保证网络中不存在局部最小点，使贪婪几何路由能够顺利进行。 针对于本文设计的几何路由算法，通过仿真实验和对实验结果的分析，可以看到，本文研究和设计的几何路由算法可以有效解决几何路由算法中的节点失效问题。 Geometric routing protocols provide efficient and scalable routing for wireless sensor networks.A new branch of geometric routing protocols is called virtual coordinate-based geometric routingprotocol, in which the sensors do not need to know the predefined geographic coordinates, thelocations which routing is based on are obtained from the graph embedding method instead, and theenergy consumption caused by localization is then reduced effectively. The routing algorithm is thesoul of routing protocol. The main drawback of related works is that the represent of virtualcoordinates is not succinct, which can not be standed in sensor networks because of the overhead ofmemory. At present, Schnyder geometric routing algorithm can solve this problem and make thegeometric routing simple and efficiency. The drawback of Schnyder geometric routing algorithm isthat the algorithm is based on strict mathematical structure, this means when the network topologychanges dynamically/(especially when node failure/), the algorithm will no longer apply. This problemis researched in this thesis, which mainly concludes research on geometric routing algorithms basedon graph embedding and solves the problem of node failure. Based on Schnyder geometric routing algorithm, geometric routing algorithms which tolerancenode failure are proposed in this thesis. First, for topology models of3-connected planar graphs andplane triangulations, a simple and efficient algorithm which is called Greedy-Compass Double ModeRouting Algorithm is proposed, this algorithm can direct message delivery. Then, to provide100/%message delivery rate, secondary embedding methods are used in this thesis. For topology models of3-connected planar graphs, Tree Routing Algorithm based on graph st-orientation is proposed, thealgorithm inherites the succinctness of nodes represent in Schnyder geometric routing algorithm. Inorder to solve the "hole" problem caused by nodes failure in topology models of plane triangulations,a Conformal Mapping Algorithm based on Ricci flows is used to map the network with irregularshape holes to the unit disk with circular holes, the algorithm guarantees that local minimum will notexist in the network and greedy forwarding will never get stuck. For geometric routing algorithms proposed above, simulation experiments and analyses onexperimental results are carried out. The results show that geometric routing algorithms proposed inthis thesis can solve the problem of node failure effectively.

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

分 类 号： [TP212.9 TN929.5]

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