基于图嵌入的无线传感器网络几何路由算法研究-计算机应用技术专业论文.docx

Nanjing University of Aeronautics and Astronautics The Graduate School College of Computer Science and Technology Research on Geometric Routing Algorithms based on Graph Embedding in Wireless Sensor Networks A Thesis in Computer Science and Technology by Zhang Lei Advised by Prof. Wang Lisong Submitted in Partial Fulfillment of the Requirements for the Degree of Master of Engineering December, 2011 承诺书 本人声明所呈交的硕士学位论文是本人在导师指导下进 行的研究工作及取得的研究成果。除了文中特别加以标注和致 谢的地方外，论文中不包含其他人已经发表或撰写过的研究成 果，也不包含为获得南京航空航天大学或其他教育机构的学位 或证书而使用过的材料。 本人授权南京航空航天大学可以将学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。 （保密的学位论文在解密后适用本承诺书） 作者签名： 日 期： 南京航空航天大学硕士学位论文 南京航空航天大学硕士学位论文 基于图嵌入的无线传感器网络几何路由算法研究 基于图嵌入的无线传感器网络几何路由算法研究 i i PAGE PAGE iv 摘 要 几何路由协议可以为无线传感器网络提供高效、可扩展的路由。基于节点虚拟位置的几何 路由协议是其中一个崭新分支，此类协议中的网络节点不需要知道预定义的地理坐标，位置信 息通过图嵌入的方法获得，路由根据图嵌入得到的虚拟坐标进行，从而有效降低节点定位所带 来的能耗。路由算法是路由协议的核心，过去的相关算法主要缺陷在于节点虚拟坐标表示的复 杂性，给传感器网络带来了无法忍受的存储开销。目前，Schnyder 几何路由算法可有效解决这 一问题，使几何路由变得简单高效，但 Schnyder 几何路由算法建立在严格的数学结构之上，当 网络拓扑结构动态变化时（特别是节点失效），算法将不再适用。本文针对这一问题展开研究， 主要研究了基于图嵌入的几何路由算法，解决了节点失效问题。 本文在 Schnyder 几何路由算法的基础上，研究并提出了容忍网络节点失效的几何路由算法。 首先，针对 3-连通平面图和平面三角剖分图中节点失效问题，提出简单高效的贪婪-指南针双模 路由算法为消息的传递指明方向。接着提出用二次嵌入的方法可保证节点失效后的网络仍有 100%的消息可达率：针对 3-连通平面图拓扑模型中的节点失效问题，提出基于图 st-定向的树 路由算法，该算法继承了 Schnyder 几何路由算法中节点坐标表示的简洁性；针对平面三角剖分 图拓扑模型中区域节点失效引起的“空洞”问题，使用基于 Ricci 流的共形映射算法将带有不 规则形状“空洞”的网络映射为带有圆形“空洞”的圆盘，从而保证网络中不存在局部最小点， 使贪婪几何路由能够顺利进行。 针对于本文设计的几何路由算法，通过仿真实验和对实验结果的分析，可以看到，本文研 究和设计的几何路由算法可以有效解决几何路由算法中的节点失效问题。 关键词：无线传感器网络，几何路由算法，图嵌入，Schnyder 嵌入，节点失效，共形映射 ABSTRACT 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 routing protocol, in which the sensors do not need to know the predefined geographic coordinates, the locations which routing is based on are obtained from the graph embedding method instead, and the energy consumption caused by localization is then reduced effectively. The routing algorith