基于图论的无线传感器网络拓扑控制方法研究

传感器技术、通信技术和计算机技术的飞速发展，孕育了具有现代意义的无线传感器网络，带来了一项新的信息革命。无线传感器网络的出现改变了人与自然的交互方式，其应用领域已经深入到了社会生活的各个方面。 无线传感器网络是一种测控网络，网络设计一般侧重网络的节能性、生命周期的延长、网络的扩展性等方面。对于网络拓扑控制来说，由于网络中节点数量众多、能力有限，网络的拓扑结构相当复杂，同时节点易失效也导致了网络拓扑结构的频繁变化，所以拓扑控制是无线传感器网络中重要的研究问题。本文基于图论中的理论知识，对无线传感器网络中的拓扑控制进行了研究，主要内容和研究成果包括以下几个方面。  论述了无线传感器网络拓扑控制问题研究的基本内容、分类、评价指标，并且指出了前人研究的成果的不足之处。  为了对无线传感器网络中节点进行功率控制，以单位圆盘图为模型构造了一个几何支撑图结构。此支撑图满足连通性、平面性、t-支撑图以及稀疏性，并且构造此支撑图的通信开销相对于其它支撑图构造算法大大降低。  针对无线传感器网络中没有基础结构的特点，利用连通支配集理论构造了无线传感器网络的虚拟骨干结构，从而把无线传感器网络映射成一个层次型的骨干结构。  基于修剪策略提出了一种极小连通支配集构造算法。算法又分为集中式和分布式两个版本。集中式算法中不仅考虑了节点的度、节点id，还综合考虑了节点的剩余能量，从而平衡了网络中节点的能量消耗，延长了算法的稳定运行时间，减少了拓扑结构重构的频率，有利于延长网络的生存时间。分布式算法中，节点根据两条邻居信息，采用了一种本地化的启发式搜索策略，从而降低了整个算法的信息复杂度。此外，这种基于修剪策略的构造算法实现方法非常简单，且够在算法运行的任何时刻得到一个可行的解。  基于极大独立集技术提出了一种启发式的极小连通支配集构造算法。在求解极大独立集过程中只需要根据节点和一跳邻居节点之间的信息确定极大独立集，在求解连通集时，根据独立节点的性质采用了本地化的启发式算法，从而提高了算法的性能，构造算法的信息复杂度也相对较低。仿真结果表明，构造算法在整个过程中所需要的通信开销大大降低，从而节省了节点的能量，有利于延长网络的生存时间。  根据无线传感器网络中节点易失效的特点，提出了一个容错的虚拟骨干构造算法。算法基于极大独立集构造方法，首先构造一个连通支配集，然后基于本地化信息得到一个支配度为k的冗余连通支配集，最后再使用协商和贪心策略使得连通支配集的连通度为m，从而得到一个m-连通k-支配集。仿真结果表明算法信息复杂度低，构造算法所需要的数据通信量降低。 本文基于图论知识，针对无线传感器网络的特点，对无线传感器网络的拓扑结构控制方法进行了研究，各项研究成果可以为无线传感器网络设计者提供一些有益的指导。