文献综述（或调研报告）：
无线传感器网络作为一个新兴的领域已经吸引了大量的关注，在覆盖空洞检测方面也取得了不少成果。目前的覆盖空洞检测算法可以大致分为以下三类：基于节点位置，基于节点间距离和基于节点间连通性。
1．基于节点位置的空洞检测算法
基于节点位置的空洞检测算法需要利用节点的精确位置信息，利用计算几何等工具来检测无线传感器网络中存在的覆盖空洞。文献[4]提出了一种基于计算几何的分布式算法，通过无线传感器节点间的相互通信寻找节点的1跳和2跳邻居节点，然后计算传感器节点的两个相邻的邻居节点与该传感器节点构成的三角形的外接圆圆心，通过判断该圆心的位置以及三角形的形状判断该传感器节点是否为覆盖空洞边界节点。文献[5]提出了一种集中式的基于Voronoi图的覆盖空洞边界检测算法，该算法首先构造整个网络的Voronoi图，然后通过比较传感器节点的感知半径与该节点到对应的Voronoi多边形顶点的距离的大小来判断节点是否处于覆盖空洞边界。该算法是一种集中式算法，算法需要收集每个节点的位置信息并构造Voronoi图，因此节点时间复杂度高和网络通信量大。文献[6]提出了一种基于圆搜索的分布式覆盖空洞检测算法，该算法运用了邻居节点拓扑结构和圆周覆盖的基本原理，建立了被测节点与邻居节点的距离与象限关系排序表，用快速搜索算法检覆盖空洞边界节点。该算法仅需节点的1跳邻居节点检测网络中的覆盖空洞边界，减少了节点间的通信量，但算法在计算过程中需要传感器节点感知圆周上所有的弧参与判断，算法在节点的邻居节点数目多的时候，执行时间较长，收敛速度慢，效率较低。
2. 基于节点间距离的空洞检测算法
在大型的无线传感器网络中，想要获得每个节点的精确位置信息几乎是不可能的，无线传感器节点得到自己位置信息的代价是巨大的，而且无线传感器定位算法产生的积累误差会导致无线传感器节点计算的地理位置信息不准确，影响基于节点位置的覆盖空洞检测算法的精确性[7]。由于缺少精确且经济适用的定位方案，在未知节点位置条件下的覆盖检测方案，即无坐标方案，取得了许多成果。
文献[8]研究了传感器网络中节点感知半径与连通性间的关系，提出并证明了一个基础性结论：当节点的通信半径至少为感知半径的两倍时，覆盖即意味着连通性。文献[9]中将这一结论扩展至k覆盖的情况。文献[7][10]中提出了圆周覆盖的概念，并证明了在不存在两个节点位于完全相同位置的情况下，当且仅当目标区域内的每个内部节点的感知边界都被k覆盖，目标区域才是k覆盖的。文献[7]证明了保证覆盖空洞检测精确性的必要条件是节点的通信半径至少为感知半径的两倍，并在此条件下提出了一种与分布信息无关的1-覆盖空洞检测算法，即段序列算法。此方案主要包含三步。首先，某一节点执行段序列算法，找到所有与目标节点感知周相交的节点，计算每一段相交圆弧的长度；之后建立目标节点的r-map坐标系，筛选出一组互不重复、包含，且不存在一段圆弧属于另两段圆弧并集情况的段序列，最后检查目标节点的圆周是否被这一组段序列完全覆盖，以此来判定其圆周覆盖情况。若存在节点的某一段圆弧未被任何其他节点圆周覆盖的情况，则这一节点肯定与空洞相邻。算法通过对目标区域内的所有内部节点执行以上过程来检测区域内的空洞。文献[11]使用降维的方法，提出了一种利用邻居节点间的距离信息来验证d维目标区域是否为k覆盖的检验算法。
文献[12]提出了两种局部化空洞检测算法，基于LVP（Localized Voronoi polygon）的空洞检测算法和基于NEP（neighbor embracing polygon）的空洞检测算法。其中，第一种基于LVP的算法是对基于Voronoi图空洞检测方案的改进，此方案需要相邻节点间的位置和方向信息，可以在传感器节点任意分布的情况下检测出覆盖空洞。第二种基于NEP的检测算法仅需知道相邻节点的方向信息，但也因为如此，该算法仅能找到覆盖边界中的凸点，不能识别出所有的边界节点。文献[13]提出利用Delaunay三角剖分（Delaunay triangulation）来检测覆盖空洞，首先利用节点间距离信息将目标区域进行Delaunay三角剖分，得到一些三角形，这些三角形的顶点代表传感器节点，然后对每个三角形，判断其内部是否被其顶点对应的传感器节点的感知范围覆盖，如果覆盖，则该三角形内不存在覆盖空洞，反之则存在。
3．基于节点间连通性的空洞检测算法
在许多实际应用中，想要得到节点间精确的距离信息比较困难，因此不借助节点位置和节点间距离信息，仅利用节点间连通信息的无线传感器网络覆盖研究引起了国内外研究人员的广泛兴趣。文献[14]首次提出利用代数拓扑中的同调理论（Homology theory）检测覆盖空洞，即通过两种单纯复形，Cech复形和Rips复形对传感器网络进行建模。其中Cech复形可以反映网络覆盖质量的精确信息，但是构造Cech复形需要利用节点的精确位置信息，而且计算复杂。Rips复形较容易构建，可以通过内部节点间通信来获得网络的连通性信息，作者通过构建Rips复形进行空洞检测，但文中所提算法是集中式的，难以用于大规模传感器网络中。文献[15]提出了一种通过构造无线传感器网络对应的Rips复形并计算该Rips复形的同调群来得到网络覆盖特性的方法。首先通过拉普拉斯算子计算无线传感器网络Rips复形的1阶同调群生成元；然后提出利用1阶同调群生成元来定位无线传感器网络的覆盖空洞是一个优化问题，最后阐述了如何使用次梯度算法解决这个优化问题。文献[16]中作者说明了Cech复形和Rips复形的关系，将覆盖空洞分为三角空洞与非三角空洞两类，并利用Rips复形提出了一种分布式的基于同调理论的覆盖空洞检测算法，该算法基本能够找到所有的非三角形空洞。文献[17]提出将无线传感器网络分成一些子网，保证每个子网中不包含覆盖空洞或者只包含1个覆盖空洞，然后在包含覆盖空洞的子网中对覆盖空洞进行进一步定位，直至找到覆盖空洞的边界。
以上是毕业论文文献综述，课题毕业论文、任务书、外文翻译、程序设计、图纸设计等资料可联系客服协助查找。
