无线传感器网络中路由相关的若干问题的研究

论文摘要

无线传感器网络综合了传感器技术、嵌入式计算技术、分布式信息处理技术和无线通信技术，能够协作地实时监测、感知和采集各种环境或监测对象的信息，并对其进行处理，传送到这些信息的用户。无线传感器网络是计算机科学技术的一个新的研究领域，具有十分广阔的应用前景，引起了学术界和工业界的高度重视。目前，无线传感器网络中的许多相关技术内容仍然处于探索阶段，比如：路由算法、能源管理、数据安全性、QoS保证等问题。只有解决好这些技术问题，无线传感器网络才能真正发挥其潜在的巨大作用。因此，本文从分析无线传感器网络的路由模型与算法的角度进行探讨，作了一些有益的尝试，主要研究工作反映在以下五个方面：1、详细探讨了无线传感器网络的QoS问题，并在无线传感器网络整体框架基础上分析了无线传感器网络系统的各层的QoS性能需求。2、研究了延迟约束的能量有效路由问题。给出了该问题的严格定义；基于背包问题的NP完全性证明了延迟约束的能量有效路由问题也是NP-Complete的；设计了该问题的一种集中式求解近似算法；证明了该算法求出的解的一些性质，并基于该算法给出了一个分布式的实现；实验结果表明：该近似算法的近似程度较高，所需运行时间较少，优于SAR。3、在分析无线传感器节点各通信状态能量消耗的基础上，定义了扩展的非确定有限状态机，它把属性附加到状态和事件上，用属性值表示系统的数据并参与计算，而系统的动态行为由连通状态来描述；提出采用扩展的非确定有限状态机作为计算节点剩余能量预测值的模型，并设计了基于剩余能量预测的路由算法，该算法不需要额外的机制来维护邻节点的剩余能量信息；实验结果表明：与Gossiping协议相比，本文提出的算法能延长网络的寿命。4、在层次路由模型的研究中，以延迟约束作为分簇的条件，提出了延迟约束的层次路由模型；基于顶点覆盖问题的NP完全性证明了求延迟约束的簇首产生模型的最优解的问题也是NP-Complete的；设计了集中式的贪婪的簇首选择近似算法；分析了该近似算法的近似程度和时间复杂性；设计了簇成员的分布式分配算法，并借助实验比较了三种指派簇成员的策略，探讨了网络属性对相对不平衡因子的影响。5、研究了链路流调度模型。即在确定节点间路由的基础上，给定一个源和目的节点对的集合{（si，ti）}，怎样在传输层上对从源到目的的数据流进行调度，以使带宽资源得到充分的利用，而问题的约束条件是节点之间可能存在信道干扰。本文研究了无线传感器网络的信道干扰模型，在此基础上给出了链路流调度模型的形式化描述，基于顶点着色问题的NP完全性证明了求链路流调度模型最优解的问题也是NP-Complete的；设计了链路流调度问题的集中式近似算法；分析了该近似算法的近似程度；给出了调度算法的分布式实现以及算法可能产生的标记冲突数目的一个上界，分析了算法的执行时间。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• §1.1.研究背景
• 1.1.1.对无线传感器网络的认识
• 1.1.2.无线传感器网络的概念
• 1.1.3.无线传感器节点
• 1.1.4.无线传感器网络的特点
• 1.1.5.无线传感器网络性能的考察指标
• §1.2.研究现状
• 1.2.1.目前开展的研究项目
• 1.2.2.硬件层研究的问题
• 1.2.3.通信层研究的问题
• 1.2.4.数据层研究的问题
• 1.2.5.应用层研究的问题
• §1.3.本文的研究内容和成果
• §1.4.本文的组织结构
• 第二章 无线传感器网络路由问题研究与本文的研究基础
• §2.1.典型路由协议
• 2.1.1.泛洪协议
• 2.1.2.闲聊协议
• 2.1.3.SPIN协议
• 2.1.4.定向扩散协议
• 2.1.5.GPSR协议
• 2.1.6.LEACH协议
• 2.1.7.PEGASIS协议
• 2.1.8.SAR协议
• §2.2.无线传感器网络路由协议分类方法
• §2.3.典型路由协议比较
• §2.4.路由协议研究小结
• §2.5.本文的研究基础
• 2.5.1.计算复杂性理论
• 2.5.2.无线传感器网络的拓扑表示
• 2.5.3.拓扑仿真环境
• 第三章 无线传感器网络的QoS问题研究
• §3.1.IP网络QoS问题
• §3.2.无线传感器网络QoS的理解
• §3.3.无线传感器网络QoS的定义
• §3.4.无线传感器网络Qos的研究
• §3.5.本章小结
• 第四章 延迟约束的能量有效路由问题研究
• §4.1.延迟约束的能量有效路由问题的形式化描述
• §4.2.延迟约束的能量有效路由问题的难解性分析
• §4.3.延迟约束的能量有效路由问题求解
• 4.3.1.DCE2问题的一种集中式求解算法
• 4.3.2.DCE2问题求解算法的分布式实现
• §4.4.实验比较
• DCE2Routing算法性能比较'>4.4.1.Approximate_DCE2Routing算法性能比较
• DCE2Routing与SAR的比较'>4.4.2.Approximate_DCE2Routing与SAR的比较
• DCE2Routing算法的影响'>4.4.3.网络的属性对Approximate_DCE2Routing算法的影响
• §4.5.本章小结
• 第五章 基于能量预测的路由模型与算法
• §5.1.无线传感器节点各状态的能量消耗分析
• §5.2.剩余能量预测模型
• 5.2.1.非确定性有限状态机的扩展
• 5.2.2.预测能量的计算
• §5.3.基于剩余能量预测的路由算法
• §5.4.实验比较
• §5.5.本章小结
• 第六章 延迟约束的层次路由模型与算法
• §6.1.层次路由协议
• §6.2.延迟约束的簇首产生模型
• 6.2.1.模型描述
• 6.2.2.模型的难解性证明
• 6.2.3.簇首产生模型的集中式求解
• 6.2.4.簇成员的分布式分配算法
• §6.3.实验比较
• 6.3.1.指派簇成员的策略的比较
• 6.3.2.网络属性对相对不平衡因子的影响
• §6.4.本章小结
• 第七章 链路流调度模型与算法
• §7.1.相关工作
• §7.2.无线信道干扰模型
• §7.3.无线传感器网络链路流调度模型
• 7.3.1.模型的形式化描述
• 7.3.2.模型的难解性证明
• §7.4.调度算法
• 7.4.1.链路流调度问题的集中式算法
• 7.4.2.算法的分布式实现
• §7.5.本章小结
• 第八章 研究总结与展望
• §8.1.研究总结
• §8.2.研究展望
• 致谢
• 参考文献
• 作者在学期间取得的学术成果