传感器网络中不依赖节点位置信息的节点调度覆盖算法

摘要

在不能获取节点精确位置信息的条件下，现有的基于分组的节点调度算法不能保证各个组内的传感器节点均匀分布在目标区域，在目标区域中某些小区域若节点分布过于密集，会增加该区域的通信冲突和数据冗余，而分布过于稀疏又会导致传感器节点不能对目标区域进行有效监控，并会降低网络的连通性。基于以上原因，本文首先建立了极大相似分布的数学模型，证明该问题属于NP-难问题。其次，引入节点的虚拟坐标的概念，用来替代节点实际的位置坐标。在此基础上，提出了极大相似分布的两种近似求解算法。与节点位置无关的集中式节点调度覆盖算法和分布式节点调度覆盖算法。传感器节点利用虚拟坐标信息进行分组，在不需要节点位置信息的条件下，使得各个组内的传感器节点较为均匀地分布在目标区域。算法分析和仿真实验表明，本文提出的这两种算法在覆盖率和目标区域的监视偏差度等性能上均优于随机调度覆盖协议。