无线传感器网络几何路由技术研究

论文摘要

传感器网络是一种由低功耗设备组成、用于在无人照看的情况下监测野外情况的网络。传感器网络可以用于环境检测、跟踪、设施保卫。路由算法和拓扑控制是无线传感器网络的关键性问题。路由算法决定了无线传感器网络的通信效率,拓扑控制决定了网络的底层拓扑。而路由算法的性能直接与底层拓扑相关。本文主要针对无线传感器网络的路由问题和拓扑控制问题进行了深入研究。几何路由协议非常适合无线传感器网络。这类协议利用节点的地理位置信息提供高效、可扩展的路由。在无线传感器网络中,节点分布在一定的地理区域内,节点间是否能够直接通信由它们之间的距离决定,因此几何路由协议符合无线传感器网络的特点。小型而便宜的卫星定位接收机（OPS）的可用性和无GPS的定位算法的研究使得在无线传感器网络中应用几何路由协议成为可能。本文在分析现有几何路由协议存在的问题的基础上,提出了转发矩形限制的贪心面路由协议CGFR。CGFR协议包括拓扑控制层和几何路由层两个层次。协议的目标是在保证分组转发的可达性,并在此前提下减少分组通过的路径长度。拓扑控制算法是CGFR协议的基础,其目的是构造满足几何路由协议要求的底层拓扑,并提高几何路由协议的性能。拓扑控制算法的基本思想是用局部算法构造网络拓扑的平面t-支撑图,使得任意两个节点在拓扑控制算法生成的拓扑中的最短路径长度不超过无拓扑控制的拓扑中的最短路径常数的t倍。由于生成的拓扑满足平面性,因此可以保证几何路由算法的分组可达性。由于生成的拓扑是t-支撑图,因此为减少分组通过的路径长度提供了可能性。拓扑控制算法分为静态拓扑控制算法和动态拓扑控制算法。静态拓扑控制算法用于节点动态不变化的网络。动态拓扑算法以静态算法为基础,在节点动态加入和退出网络时,维护网络拓扑是平面t-支撑图。几何路由算法是CGFR协议的核心,其目的保证分组可达性的前提下高效地转发分组。几何路由算法包括贪心路由算法CGR、面路由算法CFR和贪心面路由算法CGFR。贪心路由算法CGR的基本思想是用转发矩形限制选择转发节点的范围,以减少分组通过的路径长度。本文证明了,CGR算法通过的路径长度和跳步数不超过理想网络中路径长度和跳步数的常数倍。模拟实验表明,转发矩形降虽然低了转发的成功率,但是保证了路由长度的有界性。面路由算法CFR在保持面算法保证分组可达性的特性的基础上,通过使用类似二分查找的方法避免了纯面算法近似广播算法的高开销。模拟实验表明,CFR算法的开销低于现有的纯面路由算法的开销。贪心面路由算法CGFR结合了CGR算法和CFR算法的优点,既保证了分组转发的可达性,又减少了分组通过的路由长度。本文证明了,CGFR算法的开销与最优几何路由算法的开销是同一个量级。模拟实验表明,CGFR算法的开销低于现有的保证可达性的几何路由算法。几何路由协议的研究对无线传感器网络的应用将起到重要的推动作用。然而对无线传感器网络的研究还处于起步阶段,为使之实用化还需付出更多努力。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 无线传感器网络简介
• 1.1.1 概念和特点
• 1.1.2 应用背景
• 1.2 研究内容和研究现状
• 1.2.1 研究内容
• 1.2.2 研究现状
• 1.3 论文的组织结构
• 1.4 论文的主要贡献
• 第二章 相关技术与相关研究工作
• 2.1 拓扑控制技术
• 2.1.1 平面式拓扑控制
• 2.1.2 基于分簇算法的层次式拓扑控制
• 2.2 几何路由算法
• 2.2.1 贪心几何路由算法
• 2.2.2 保证可达性的几何路由算法
• 2.3 小结
• 第三章 转发矩形限制的几何路由协议框架
• 3.1 概述
• 3.2 问题描述与模型假设
• 3.3 CGFR协议设计思路
• 3.4 拓扑控制算法
• 3.4.1 静态拓扑控制算法
• 3.4.2 动态拓扑控制算法
• 3.5 几何路由算法
• 3.5.1 贪心路由算法
• 3.5.2 面路由算法
• 3.5.3 贪心面路由算法
• 3.6 小结
• 第四章 静态拓扑控制算法
• 4.1 概述
• 4.2 记号与定义
• 4.2.1 记号
• 4.2.2 t-支撑图（t-spanner）
• 4.2.3 相关研究
• 4.3 AUDel图
• 4.4 构造AUDel图的局部算法
• 4.5 模拟
• 4.5.1 几种拓扑图的总边数比较
• 4.5.2 比较算法的通信开销
• 4.6 小结
• 第五章 动态拓扑控制算法
• 5.1 概述
• 5.2 动态拓扑控制算法——DynCAUDel算法
• 5.2.1 数据结构
• 5.2.2 算法的初始化构造部分
• 5.2.3 算法的动态维护部分
• 5.2.4 算法的性能分析
• 5.3 动态拓扑控制算法——DynECAUDel
• 5.3.1 数据结构
• 5.3.2 算法的初始化构造部分
• 5.3.3 算法的动态维护部分
• 5.3.4 算法的性能分析
• 5.4 小结
• 第六章 转发矩形限制的贪心路由算法
• 6.1 问题描述
• 6.1.1 概述
• 6.1.2 路由算法性能的度量
• 6.2 转发矩形限制的贪心路由算法
• 6.2.1 转发矩形限制的贪心路由算法
• 6.2.2 算法分析
• 6.3 模拟与分析
• 6.3.1 模拟平台
• 6.3.2 模拟程序设计
• 6.3.3 模拟参数设置
• 6.3.4 两种算法下欧式支撑因子比较
• 6.3.5 两种算法下网络支撑因子比较
• 6.3.6 两种算法的成功转发率的比较
• 6.4 小结
• 第七章 转发矩形限制的面路由算法
• 7.1 概述
• 7.2 问题描述
• 7.2.1 网络模型和假设
• 7.3 转发矩形限制的面路由算法CFR
• 7.3.1 获知拓扑信息
• 7.3.2 算法描述
• 7.3.3 算法分析
• 7.4 模拟与分析
• 7.4.1 模拟平台
• 7.4.2 模拟程序设计
• 7.4.3 模拟参数
• 7.4.4 欧式支撑因子比较
• 7.4.5 网络支撑因子比较
• 7.5 小结
• 第八章 转发矩形限制的贪心面路由算法
• 8.1 概述
• 8.2 贪心面路由算法CGFR
• 8.3 分析与模拟
• 8.3.1 模拟平台
• 8.3.2 模拟程序设计
• 8.3.3 模拟参数
• 8.3.4 欧式支撑因子比较
• 8.3.5 网络支撑因子比较
• 8.4 小结
• 结束语
• 致谢
• 参考文献
• 作者在学期间取得的学术成果