论文部分内容阅读
在大规模传感器网络中,系统能量和网络拥塞问题一直是制约整个网络发挥其效能的关键因素。出于成本制约的考虑,大规模传感器节点的布放一般来说是随机和静态的,因此可能会出现大量的冗余节点。如何寻找这些冗余节点并控制它们进入休眠状态是网络拓扑控制需要解决的问题。在设计拓扑控制方案时,除了满足区域的覆盖性、网络的连通性之外,其拓扑结构的平面性、稀疏性、节点度的有界性、较小的网络扩张系数等等,都是期望具有的性质。本文研究了大规模随机布放的静态传感器网络中的拓扑控制问题和障碍覆盖问题,主要工作内容如下:(1)提出了一个新的平面图结构。该结构称为“稀疏Delaunay三角划分”(Sparse Delaunay Triangulation),简写为SparseDT。本文证明了它的一些优良特性,包括其渐近连通性和更好的网络扩张系数;给出了构造SparseDT的分布式算法。(2)提出了传感器网络的双障碍覆盖(Double Barrier Coverage)问题。即如果一个传感器网络能够保证任何目标在它的穿越路径上某一点会被两个不同的传感器同时检测到,我们称这个网络提供了双障碍覆盖。本文在SparseDT结构的基础上,设计了简单有效的分布式算法;分析了构造障碍所需活动传感器的数量;给出了解决类似的K覆盖障碍问题的集中式算法。(3)提出了一个简单的拓扑控制协议。该协议称为“收敛的SparseDT”(Convergent SparseDT)。它可以很好的控制活动传感器节点的密度;保证了监控区域的渐近完全覆盖性和拓扑结构的渐近连通性;大大减少了额外的通信和计算开销。本文还对此协议的收敛性和运行时刻性能进行了概率分析。(4)在NS2模拟器上实现了收敛的SparseDT拓扑控制协议和双障碍覆盖算法。协议的实现考虑了运行能耗和网络拥塞的问题;设计了消息响应机制和节点调度机制;构造了NS2所不具备的简单感应模型。模拟实验结果与协议和算法的理论分析充分吻合。本文的主要贡献和创新为:(1)首次提出的双障碍覆盖问题,与以前仅用单条或多条路径来构造障碍相比,能够更有效地检测到高速穿越障碍区域的入侵目标。(2)所提出的SparseDT拓扑结构具有良好的网络性能和分布式构造特性,与已有的分布式Delauny三角划分构造算法相比,在计算和通信复杂度上都有显著改进。(3)所设计的收敛的SparseDT拓扑控制协议采用了势场理论和虚拟势场的技术。这种连续的动态优化技术运用到离散的静态传感器网络的拓扑控制领域中,是一个大胆的尝试。