网络覆盖是无线传感器网络(WSNs,Wireless Sensor Networks)中的一个基本问题,它反映了传感器网络对目标区域的监控程度,在很大程度上影响着网络所能提供的服务质量(QoS,Quality of Service)。在大多数WSNs应用中,要求目标区域被传感器节点完全覆盖,而在节点定位以及对网络容错能力有较高要求的应用场景中,往往要求目标区域被k(k≥1)重覆盖。然而,在现实应用中,传感器节点的随机部署、能量耗尽及节点被破坏等因素很容易造成覆盖空洞的产生,因此,研究k-覆盖空洞检测问题具有重要的理论意义和应用价值。本学位论文针对节点位置信息未知的无线传感器网络,对其k-覆盖空洞检测算法进行了深入研究。论文分别基于相邻节点间的距离信息和节点间连通信息,提出了两种k-覆盖空洞检测算法,并通过仿真分析了所提算法的性能。论文的主要贡献如下:(1)提出了一种基于相邻节点间距离信息的k-覆盖空洞检测算法。首先,提出一种1-覆盖空洞检测算法,算法由边界线段检测和边界圆周检测两部分组成。然后,扩展算法至k-覆盖空洞场景。通过在已被节点覆盖的目标区域内寻找一独立覆盖的节点子集,并休眠该集合内的节点,使得网络覆盖度减去1。重复1-覆盖空洞检测算法,发现更高阶的覆盖空洞。迭代上述步骤k-1次,可以发现所有k-覆盖空洞的边界线段和边界圆周。最后,将所提算法与基于节点位置的覆盖空洞检测算法进行对比,仿真结果显示,所提算法可以精确检测99%以上的覆盖空洞。(2)利用同调理论中的Rips复形对无线传感器网络建模,提出了一种高效的单纯复形简化算法。在不改变网络拓扑特性的基础上,分别提出针对点和边的删除准则。在网络对应的Rips复形中,根据相应的判断准则依次发现并删去能够被删除的点和边,直至没有新的点和边可以被删除为止。执行算法后,网络对应的Rips复形趋于平面化,降低了单纯复形的计算复杂度。(3)将同调理论应用于无线传感器网络的k重覆盖方面,针对非三角形空洞,提出了一种基于连通信息的k-覆盖空洞检测算法。首先,构建网络对应的Rips复形,在不改变网络中覆盖空洞数量和大小的条件下,通过删除部分节点简化Rips复形,发现1-覆盖空洞的边界圆周。然后,扩展算法至k-覆盖空洞场景。利用所提的单纯复形简化算法,在已被节点覆盖的目标区域内寻找一独立覆盖的子单纯复形,休眠该复形中的节点使网络覆盖度减去1。迭代1-覆盖空洞检测和覆盖度递减算法k-1次,发现所有非三角形k-覆盖空洞的边界圆周。最后,将所提算法与基于节点位置的覆盖空洞检测算法进行对比,仿真结果显示,所提算法可以准确检测95%以上的非三角形覆盖空洞。