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

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

基于动态联盟机制的无线传感器网络任务分配问题研究

微机电系统、先进传感器、无线通信及现代网络等技术的进步，推动了无线传感器网络的产生和发展。集数据采集、处理、无线传输等功能于一体的无线传感器网络扩展了人们的信息获取能力，将逻辑上的信息世界与真实物理世界融合在一起，将改变人类与物理世界的交互方式。 任务分配就是在无线传感器节点协同过程中，确定由哪些节点来完成特定的任务。针对不同的应用领域，需要不同的任务分配方案与之适应，才能得到最佳的资源利用率和检测性能。无线传感器网络是一种分布式网络，需要多个节点协同执行检测任务，因此任务分配问题既是无线传感器网络的基本问题，也是无线传感器网络应用的基础。动态联盟机制是一种事件触发的任务分配机制，对动态环境的适应性相对较好，适用于动态性要求相对较高的目标追踪等无线传感器网络应用领域。 本文针对基于动态联盟机制的无线传感器网络的任务分配问题展开研究。论文的主要工作如下： 综合论述了无线传感器网络的任务分配问题的研究内容、特性和研究现状等。 针对节点能量和能力严格受限的问题，提出了一种基于拍卖的动态联盟组建机制。首先，将拍卖方法引入了动态联盟的组建过程，简化了动态联盟的组建，提高了动态联盟的结盟成功率，在更加有效地利用网络能量资源的同时提升了网络性能。而后，在选择拍卖标的时，综合考虑了节点剩余能量和通信能量消耗，提升了无线传感器网络的生命周期。 针对动态联盟的组织维护和能量均衡性问题，提出了一种基于协商的动态联盟成员更新机制。当动态联盟的成员能量消耗达到一定程度时，采用基于协商的机制对动态联盟成员进行更新，以增强系统能量消耗的均衡性，从而延长网络的生命周期。 针对任务影响区域不断变化的问题，给出了一种基于资源预留的动态联盟检测区域更新机制，以适应对动态联盟的动态性的要求。首先加入了联盟覆盖范围和休眠盟员的概念，以消除针对同一任务的检测传感器节点的冗余，进一步降低网络执行任务期间的能量消耗。而后又加入动态联盟的更新机制，以消除联盟衔接期间网络对任务的暂时“失明”，保证动态联盟执行任务时的连续性，从而在一定程度上保证网络的检测性能。 针对多动态联盟间的协同问题，提出了基于分布式约束满足的多联盟协同机制。根据多个目标经过无线传感器网络监控区域时的任务分配需求，提出了一种基于分布式约束满足的多动态联盟协同机制，建立了基于动态联盟机制的任务分配问题的分布式约束满足模型，采用分布式随机算法进行求解，可以针对未知数量的目标追踪进行分布式的动态协同任务分配，有效解决了动态联盟间的协同问题，从而降低网络的能量消耗，节省网络资源。 总之，论文对基于动态联盟机制的无线传感器网络任务分配问题进行了研究和探讨，旨在对无线传感器网络的应用起到一定的推动作用。

用于工业过程监测的无线传感器网络路由协议研究

微电子、无线通信、自动控制和人工智能等领域的技术进步，推动了无线传感器网络的发展。无线传感器网络改变了人与自然的交互方式，是二十一世纪最具影响的IT技术之一，在军事、环境、医疗、家庭、工业和其它领域有广阔的应用前景。 路由协议是目前传感器网络研究的重要内容，协议设计与网络应用密切相关。在工业无线监测应用中，路由协议设计的主要目标是提高可靠性和降低节点能耗；而传统网络路由协议设计的首要任务是提供高质量的数据服务。这些不同导致传统网络的路由协议不能直接应用于工业过程监测网络。论文针对工业无线监测应用的需求和特点展开研究工作，主要包括以下几方面内容。 论述了工业无线传感器网络路由协议设计所面临的挑战性问题，系统地总结了已有研究成果与不足，具体分析了在工业过程监测环境下无线传感器网络的特点和路由需要重点解决的问题。 分析了工业过程监测应用对传感器网络的路由需求，并实地测试了工厂车间环境下的信道质量。 针对这些工业应用的实际需求，提出了在减少协议开销、降低协议能耗的同时提高数据传输可靠性的路由机制，以满足不同现场设备对数据路由的需求。 针对工业过程监测网络中的上行数据量大且具有周期性的特点，提出了一种基于链路质量估计的逐跳多径路由协议。该协议使数据在每一跳的转发过程中都有多条路径可以使用，在提高转发成功率的同时避免了端到端多路径机制带来的大量开销。 针对工业过程监测应用中下行数据量少且具有非周期性的特点，提出了基于分布式编址算法的主动路由协议。该协议中，传感器节点分配到下行地址之后就可以计算出下一跳转发地址，从而避免了采用基于广播转发的方式，大大减少了路由开销。同时，单播转发的下行数据不会引发“广播风暴”，减轻了对网络中周期性上行数据转发的影响。 针对手持设备所具有的移动性、数据量少和通信不频繁的特点，设计了面向移动设备的低开销按需路由协议。该协议只在手持设备有远程连接需求的时候才建立主路由，然后按需延长，避免手持设备每移动一次就要重新进行路由发现。此外，在路由发现环节利用了已经建立好的主动路由，通过单播方式转发路由发现报文，不但大幅减少了协议开销，同时也保证了所选路由的高质量。 为了测试本文提供的路由协议在工厂车间内的实际效果，构建了一个工作在2.4GHz上的验证系统。该验证系统以网络层的可靠性机制为基础，通过在链路层采用TDMA机制、FDMA机制和在传输层重传等机制的配合，达到了较高的报文传输可靠性，证明本文提出的路由协议能够满足工业过程监测应用的需要。

面向目标跟踪的无线传感器网络部署与定位问题研究

微机电系统、先进传感器、无线通信及现代网络等技术的进步，推动了无线传感器网络的产生和发展。集数据采集、处理、无线传输等功能于一体的无线传感器网络扩展了人们的信息获取能力，将逻辑上的信息世界与真实物理世界融合在一起，将改变人类与物理世界的交互方式。 无线传感器网络具有许多挑战性的研究课题，其中部署与定位是无线传感器网络应用的基础问题。部署就是在一定区域内通过适当的策略放置传感器节点以满足某种特定需求，它决定了网络对目标的检测能力。定位在无线传感器网络中包括两层含义：节点定位和目标定位。节点定位是目标定位的前提，会影响目标跟踪的精度。论文面向应用于目标跟踪的无线传感器网络，围绕部署与定位问题展开研究。 论文分别综述了无线传感器网络部署问题、定位问题和目标跟踪问题的研究内容、评价标准、算法分类和研究现状。 从信息覆盖的角度研究满足给定指标的确定性部署问题，提出一种基于检测融合的确定性部署策略。首先采用奈曼-皮尔逊准则融合单元网格内所有传感器节点的检测信息，实现正方形和正三角形两种单元网格的高效覆盖。然后分别给出对应的监测区域网格划分方法，从而确定监测区域需要的传感器节点数量以及放置的具体位置。使用相同数量的传感器节点，基于检测融合的部署策略可以获得更大的覆盖范围，也就是在保证一定感知性能的情况下减少了成本。 针对无线电干涉定位系统的多径效应抑制问题，分别从理论和实验的角度分析多径效应对无线电干涉测距的影响，然后根据多径信号的物理特性，从理论上推导了镜反射的多径误差数学模型，在此基础之上进行无线电干涉定位系统的多径误差分析，讨论了衰减因子、传感器节点天线高度和水平距离等多径参数对多径误差的影响。通过仿真计算和分析可知，衰减因子对多径误差的大小起着决定性作用，而多径误差在定位空间上分布的复杂程度，随着天线高度的增加而增加，同衰减因子无关。 无线电干涉测距技术获取的干涉距离是两个发送节点和两个接收节点间距离的线性组合值。针对以节点间距离作为输入的传统定位算法，无法直接利用上述干涉距离进行定位的问题，提出一种基于改进粒子群优化的定位方法。借鉴遗传算法中变异的思想，在每次迭代时对更新过的粒子位置进行微扰，以维持种群的活性。利用干涉距离的实验数据，分析比较了遗传算法和改进粒子群优化在无线电干涉定位系统节点定位问题中的性能。实验结果表明，两种定位方法都能在有限的进化代数内找到节点坐标的近似值，但是基于改进粒子群优化的定位方法的平均耗费时间，远远小于基于遗传算法的定位方法，具有更高的优化效率。 针对具有簇-树型网络拓扑结构的无线传感器网络，首先给出集中式粒子滤波跟踪算法实现的具体步骤，然后提出两种分布式粒子滤波跟踪算法。综合考虑信息收益和参与协作的资源消耗，两种分布式算法分别采用不同的准则来选择参与跟踪的传感器节点。为了系统地比较跟踪算法的性能，给出跟踪精度、通信开销、能量开销和跟踪反应时间等各项指标的定义，进而构建了综合性能评价体系。通过仿真，量化比较了三种跟踪算法的性能。结果表明，两种分布式算法能够在损失很少跟踪精度的同时，大幅度减少通信开销、能量开销和跟踪反应时间。最后，仿真分析了传感器节点覆盖密度和检测阈值对跟踪算法性能的影响。 总之，论文对无线传感器网络的部署问题、定位问题和目标跟踪问题进行了研究和探讨，旨在对无线传感器网络的应用起到一定的促进作用。

面向数据收集的无线传感器网络节点部署问题研究

随着MEMS、无线通信、自动控制和人工智能等技术的快速发展，无线传感器网络引起了学术界的极大关注。它的出现改变了人与自然界的交互方式，其应用领域将会深入到社会生活的各个方面。 节点部署问题是无线传感器网络研究的基本问题之一。在无线传感器网络的某些实际应用中，节点部署通常采用人工部署方式，为满足网络的节能性、可靠性、实时性等性能需求，需要额外部署一些节点。为限制网络布设成本，要对这些新增加的节点进行有针对性地部署。基于这种应用环境，论文对面向数据收集的无线传感器网络节点部署问题展开研究工作，主要的研究内容与成果包括以下几个方面。 论述了无线传感器网络节点部署问题的研究内容、分类和评价体系，系统地总结了前人的研究成果和不足。 为改善网络的连通性和满足网络生命期需求，提出了一种启发式的两阶段中继节点部署策略。第一阶段的部署确保了网络连通性；第二阶段部署，结合负载平衡的路由协议，满足了网络的生命期需求。仿真结果表明该方法在满足上述性能需求的前提下，最大限度地减少了需要部署的中继节点数目。 针对网络中簇首选择不合理导致数据收集成本过高的问题，提出了面向数据收集成本最优化的簇首节点选择算法。当网络状态一定时，簇首节点的优化选择问题是一类组合优化问题。论文首先提出了基于小规模网络的全局最优化的簇首节点选择算法（BFM）。针对BFM算法复杂度高的缺点，进而提出了基于大规模网络的启发式的簇首节点选择算法，该算法可以在较短时间内得到问题的次优解。 考虑网络簇首的容量限制和最大簇半径限制，把簇首节点的优化部署问题形式化为整数规划问题。提出两种启发式的簇首优化部署策略：基于K-平均的簇首部署策略和基于K-平均与模拟退火混合算法的簇首部署策略。前者适用于网络运行时的动态部署，后者适用于网络投入使用前的规划部署。仿真结果表明，分簇后的网络在满足上述限制的情况下，最大限度地延长了网络生命期。 有针对性的节点部署离不开网络状态监测，为使网络状态监测不过多占用网络资源，提出了一种高效的网络状态监测机制。通过对节点编码并在节点间建立起一个逻辑层次簇结构，利用各个子簇状态数据的相似性和编码的连续性，实现了网内无损聚合。该监测机制使得网络状态信息的收集，在不丢失数据细节信息的情况下，数据通信量大大减少。 本论文的研究仅为无线传感器网络中的规划部署问题提供了一个框架，尚未形成一个完整可行的网络规划部署系统。各项研究成果可以为无线传感器网络设计者、方案提供者以及无线传感器网络应用的系统集成，提供一些有益的指导。