有效的覆盖洞检测算法基于简化的撕裂复杂的无线传感器网络

文摘

网络中覆盖漏洞的出现会导致传输链接被断开,从而导致减少数据的准确性。及时覆盖漏洞的检测可以有效地提高网络服务质量。与其他报道孔检测算法相比,算法基于复杂撕裂检测精度高的优点没有节点位置信息,但是高复杂性。提出了一种有效的覆盖洞检测算法基于简化撕裂复杂的高复杂性来解决这个问题。首先,图兰定理结合程度和聚类系数的概念在一个复杂的网络节点进行分类;此外,冗余节点确定规则是为了睡眠冗余节点。其次,根据完全图的概念,冗余边删除规则旨在删除多余的边缘。以上两个步骤的基础上,撕裂复杂有效地简化。最后,从循环的角度,边界循环过滤和减少规则旨在实现检测的无线传感器网络覆盖洞。相比HBA和树型覆盖洞检测算法,仿真结果表明,该孔检测算法复杂度低、精度高,检测精度的孔面积高达99.03%。

1。介绍

物联网的深入应用到社会生活形式的智能城市和互联网的车辆。作为一个潜在的物联网技术,无线传感器网络(网络)由大量的传感器节点部署在监测区域全面感知、获取、传输信息对象,适用于智能交通(1)、事件检测(2),环境监测3)等。这些实际应用了网络的服务质量有很高的要求。覆盖率是一个重要的指标来评估网络的服务质量(4],许多学者作出了贡献的改进和优化。在[5),一个深刻的和全面的总结和分类数据fusion-based覆盖优化问题和技术提供了针对克服当前的解决方案中存在的缺点。覆盖率之间的比例法、网络密度、派生和信噪比(6),数据融合显示显著提高传感报道利用传感器之间的协作。然而,一些原因导致损失的报道在网络不可避免的,如随机部署位置修改,和能量耗尽的节点。因此,数据丢失或无法投递的信息就会出现在原始网络的发现区域,这降低了网络的服务质量。发现地区被称为覆盖漏洞(7]。漏洞的出现不仅破坏通信链路,降低了数据的准确性(8),但也加剧了传输孔附近的边界节点的负担,导致孔的扩张范围(9]。因此,发现和定位网络中的覆盖洞是至关重要的,确保网络服务的质量。

现有的孔检测算法大致可以分为以下三个类别:几何方法,概率方法和拓扑的方法。几何方法利用节点的位置信息和相应的几何工具,如泰森多边形法图和检测孔的德劳内三角剖10- - - - - -16]。虽然这个方法可以准确识别覆盖洞,获得准确的传感器节点的位置信息是非常昂贵和困难的。因此,这种方法是不切实际的。概率统计方法[的位置信息是不重要的17- - - - - -19];然而,均匀分布的节点或节点密度高是一个必要条件。与此同时,很难准确地检测覆盖漏洞。拓扑方法(20.- - - - - -22)经常使用节点之间的连通性信息探测孔没有节点的位置信息和保证检测精度。然而,这些算法的复杂性总是高,效率低。因此,本文提出了一种有效的覆盖洞检测算法的基础上,简化复杂撕裂属于拓扑方法。该算法降低了算法的复杂性,保证检测精度。本文的主要贡献如下:(1)冗余节点睡觉。结合图兰定理和度和聚类系数的概念在一个复杂的网络,我们把内部网络中的节点分为两类,即确定性节点和非确定性的节点;冗余节点确定规则是用于睡觉的冗余节点在一个分布式的方式(2)删除多余的优势。结合完全图的概念,我们提出一个方法来识别冗余边,可以简化设置在网络边缘。通过节点和边的简化,撕裂复杂的网络模型可以简化高效、迅速(3)孔检测和循环边界识别。基于简化网络结构,检测孔的方法提出了从循环的角度。同时,边界边缘识别的方法,错误的边界边的定义,给出边界循环识别和减少规则

本文的其余部分组织如下:部分2介绍了相关的工作。部分3介绍了系统模型和相关概念的定义。撕裂的简化过程复杂将部分执行4,包括识别冗余节点和冗余边。部分5确定了洞。部分6评估算法通过仿真实验的准确性。最后,部分7总结了纸。

2。相关的工作

研究覆盖漏洞分为两部分,分别覆盖孔检测和覆盖洞修复。本文主要研究覆盖洞检测算法。现有的覆盖洞检测算法大致可以分为三个类别:几何方法、概率方法和拓扑的方法。

2.1。几何方法

几何方法利用节点的位置信息或节点之间的相对距离,结合相应的几何工具(比如泰森多边形法图和德劳内三角剖)来识别漏洞。在[12),介绍了树的概念定位和描述覆盖漏洞;因此,可以确定相应的孔的位置和形状,以及孔的大小。然而,邻居节点的相对位置信息必须清楚。在[13),提出了一种算法基于德劳内三角剖,结合虚拟edge-based帮助检测方法在无线传感器网络覆盖洞。与现有的基于树的方法相比,该算法有助于检测准确的覆盖洞的大小和节点的坐标信息,产生额外的费用。在[23),每个节点被认为是在一个洞边界的基础上当地的泰森多边形法图;然而,移动传感器必须用来构造一个混合传感器网络使用静态传感器。在[24),泰森多边形法基于图表的筛选策略提出了屏蔽边界节点和覆盖漏洞得到的确切位置根据虚拟edge-based孔位置的策略。高检测精度是保证通过考虑覆盖洞的形状不规则,并提供更准确的信息覆盖洞修复,但每个节点的具体位置信息必须在这个方法。在[25),一个方法提出了基于德劳内检测覆盖洞没有节点的坐标信息;然而,不能给孔的全局视图。

2.2。概率方法

均匀分布的节点和节点密度高,覆盖漏洞可以从统计发现在网络属性。一个算法确定一个区域的边界节点结构在26),但高密度节点是必需的。假设节点之间的连接是由单位圆盘图模型(27),和一个线性时间算法来识别漏洞的边界。但该算法不能区分两个洞,接近对方。在[28),移动和异构无线传感器网络的覆盖范围研究,和泊松部署方案下的覆盖问题,讨论了二维随机游走迁移模型。覆盖率将提高流动性。然而,覆盖范围将被忽略。

2.3。拓扑方法

拓扑方法使用拓扑属性(如连接信息)来识别一个洞的边界节点的确切位置。在[29日),组合拉普拉斯算子是正确的工具来计算分布式同源组。虽然分布式孔检测可以执行,但孔不能准确定位。在[20.),分布式算法通过使用单纯复形和组合拉普拉斯算子获得网络的拓扑属性,而验证在传感器网络覆盖洞的存在没有任何指标信息。但孔边界无法找到准确,因为撕裂复杂不能总是检测覆盖漏洞。在[21],洞首先被定义为三角形,nontriangular漏洞研究使用的准确性撕裂复杂检测漏洞的时候,和一个connectivity-based分布式nontriangular洞洞检测算法,这是更适合疏的传感器网络。根据文献[21),下一个三角形的洞面积的百分比不同比率的通信半径和传感半径是研究(22,准确地检测孔与撕裂的条件复杂。同时,同源的分布式覆盖洞检测方法提出了nontriangular洞,不能检测出所有的洞,复杂性高。撕裂越平面复杂,越有利,这将是漏洞的检测;因此,撕裂的快速和有效的简化复杂的能有效降低算法的复杂性。

最上面的覆盖洞检测方法利用二进制传感器模型;与此同时,一些其他模型也提出了反映感应能力和检测覆盖漏洞。在[30.),一个新的自信的信息覆盖率(CIC)模型提出了重建领域,其目标是获得重建地图的一些物理现象的属性与给定的重建质量对整个传感器领域,包括抽样点,而不是采样。在[31日],LCHD LCHDRL方案提出了解决和研究本地化自信的信息覆盖洞(LCICHD)发现的目标检测问题出现的位置和数量在物联网的基础上覆盖洞中投模型。两个有效的启发式中投孔检测算法包括冠心病没有考虑节点的剩余能量和其他CHDRE把节点的剩余能量考虑提出了(32)地址和自信的信息覆盖洞检测问题研究(CICHD)中投的基础模型。EECICHD节能中投孔检测方案,充分利用放射性核素和传感器的内部空间相关性的合作感知能力提高中投孔检测效率,提出了(33]。然而,上述算法总是工作在一个集中的方式,不适合大规模监测领域。与此同时,这些算法连续感应区域分割成一系列重建网格检查存在的漏洞。发现黑洞的边界是由图像处理的算法。

根据上述分析,本文提出了一种有效的覆盖洞检测算法的基础上,简化撕裂复杂,设计的节点和边删除规则首先有效简化复杂撕裂,使撕裂复杂接近整平,然后从循环的角度识别漏洞在网络的基础上简化撕裂复杂结构。本文中的算法检测孔连续感应区域,网络准确的边界没有图像处理;因此,采用二进制传感器模型网络中每个节点。

3所示。系统模型和相关概念的定义

3.1。系统模型

传感器节点部署在一个二维平面。目标区域内的节点位于内部节点随机分布,和其他节点均匀分布在目标区域的外边界,确保完全覆盖边界节点。不知道具体的位置信息,每个节点和节点可以确定内部节点或不是基于一个初始设置。其他一些条件设置如下:(1)节点同构,通信范围( )和传感范围( )每个节点都是平等的, (2)一个二进制传感器网络中采用为每个节点模型(3)每个节点都有一个惟一的ID(4)网络连接,如图1

3.2。相关概念的定义

3.2.1之上。定义相关的同源性理论

定义1(单纯型)。给定一个顶点组和一个正整数 ,一个 - - - - - -单纯形是一个随机的子集 点 ,在哪里 和 ; 设置的维单形(22]。如图21-simplex 0-simplex是一个顶点,是一个优势,2-simplex是一个三角形,3-simplex包含内部是一个四面体。所有单形组成的 顶点形成的表面 - - - - - -单纯形。

定义2(单纯复形)。单纯复形的一系列单形部分和单纯复形的表面形式。单形必须满足两个条件如下:(1)中的每个单纯形表面单纯复形必须是单纯复形表面,(2)任何两个单形的交集和的表面吗和 。单纯复形的维度定义为最大的维度中包含任何单工单纯复形。

定义3(撕裂复杂)。给定一个有限点集和固定半径在 ,撕裂复杂( )的是一个抽象的单纯复形的 - - - - - -单形是由 点 。中任意两个节点之间的距离小于固定半径 。
假设 是一组传感器节点位置和 是一组传感器节点的传感范围,在哪里代表的位置 - - - - - -th节点和 。如图3,撕裂复杂的基础上可以形成上述定义当顶点集包含六个顶点。

定义4(三角孔和nontriangular孔(21])。洞中存在三角形不完全覆盖的传感器节点被称为三角孔;另一个洞被称为nontriangular洞。
如图3报道,有两个洞形成的网络节点2,3,5,6,节点3、4和5,分别。然而,只有形成的孔节点2,3,5,6,可以撕裂检测到的复杂。

3.2.2。图论相关定义

一个无向图的顶点集组成 和一个无向边集 表示为 。一些定义的基础上给出无向图如下。

定义5(邻接矩阵)。两个节点的相邻关系,如果两个节点之间的边存在;否则,他们不相邻。为方便计算,一个邻接矩阵可以用来描述无向图的两个节点之间的关系 。假设有顶点的图 ,然后 。

定义6(子图)。图可以表示为 。 的子图 ,和被称为父图的如果 和 ,叫 。

3.2.3。定义相关的复杂网络理论

度和聚类系数的参数参与本研究定义如下。

定义7(程度)。的程度节点的1-hop邻居节点的数量,取决于它的邻接矩阵,可以被定义为哪一个 在哪里当节点= 1和节点是直接连接;否则,等于0。是网络中节点的总数。

定义8(聚类系数)。聚类系数节点的边的数量之间的比例是和的总数可能边缘之间的直接连接邻居节点,它描述了紧张和聚合网络中的节点。可以被定义为 在哪里 。

节点度反映了节点的能力与周围建立直接连接节点,也就是说,你的邻居节点的数量,而聚类系数提出了边缘连接在邻居节点,也就是说,反映了节点之间的紧张。

4所示。撕裂复杂的简单化

一个高效的分布式nontriangular洞洞检测算法为设计在这一节中。至于三角孔、三角孔的面积比小于0.06%,当网络节点通信半径的比值之间的覆盖半径是√3和2(包括√3和2);即三角孔在网络可以忽略14]。孔检测时将更有效率和更容易撕裂复杂趋于平面化;因此,它是至关重要的,以简化撕裂复杂有效降低算法的复杂性。摘要决心规则冗余节点和冗余边删除规则构造使撕裂复杂平面,然后,孔可以有效地检测到。该算法包括以下三个部分:(1)冗余节点睡觉,(2)冗余边删除,和(3)孔检测和边界识别。前两个步骤被视为撕裂的简化过程复杂,过程如图4。

的 - - - - - -单纯形 的一部分 - - - - - -单纯形 如果 。因此,节点和边缘的一部分吗 ,边缘 是三角形的一部分吗 ,和边的邻居节点吗 。 是一组包含边缘节点 ,和是一组2-simplices包含节点 。

定义9(循环)。一个循环是图的子图吗如果每个节点在循环只有两个邻国。循环的长度用,其边缘的数量吗 。所有的循环图是用 ,和三角形的集合循环图用 。三角循环的长度是三。

定义10(邻居图)。你的邻居节点集在图用 ,和你的邻居图的节点在图用 。你的邻居图的节点集是由节点的邻居节点 。

定义11(图兰定理)。图有最多如果边缘图是一个简单的图节点,也没有完全图在图子图,代表了 - - - - - -完整的图: 当 和 。

推断12。必须有一个完全图在图作为一个如果一个简单的图子图与节点包含至少 边缘。也就是说,必须有一个完全图在图子图当 和图至少包含 边缘。

推理13。网络中的每个内部节点是否满足下列条件: 然后,必须有一个三角形循环在该节点的邻居图;否则,它是不确定是否一个三角形循环在该节点的邻居图。节点的度 , 节点的聚类系数吗 ,和 。

证明。根据定义8, 如果一个节点的程度大于或等于3(也就是说,至少有三个节点的邻居节点的图 ),和节点的聚类系数满足 。因此,必须有在你的邻居节点的图的子图推理的基础12。

定义14(确定和nondetermined节点)。内部节点是一个决定如果有一个三角形环在其邻居节点图;否则,内部节点是一个nondetermined节点。

定义15(冗余节点判定规则)。每个内部节点确定网络中冗余节点如果邻国图满足以下两个条件:(1)节点的邻居图连接和(2)都可以三角循环(也就是说,每个循环的长度是三个)。

证明。为了证明的正确性冗余节点确定规则,有必要确认没有创建或新洞没有黑洞合并的过程中执行删除冗余节点。(1)如果该节点的删除导致新洞的出现,形成的循环的边界边孔必须在你的邻居图节点的这意味着有一个循环,不能分析 。上述情况是违反规则。因此,冗余节点的删除不会创建新的漏洞(2)如果删除冗余节点导致两个洞的合并,你的邻居图节点的不能连接,这是违反规则。因此,冗余节点的删除不会引起合并的两个洞

4.1。冗余节点睡眠

由于边界节点部署在手动目标区域的边界,只有内部网络中的节点执行的过程冗余节点睡觉。冗余节点睡眠的过程如下:

步骤16。每个节点广播两个构造其1-simplices你好消息,2-simplices, 3-simplices撕裂复杂形式。每个节点广播第一个广播消息ID,和每个节点获得所有1-hop邻国的ID。每个节点继续播放第二个你好消息包含1-hop邻国的id。所有节点获得(1-simplices)当他们收到他们的邻居节点列表。(2-simplices)将获得当这些节点收到他们的邻居的邻居列表,和3-simplices时形成一个邻居节点的单纯形。

步骤17。计算和的节点。内部网络中的节点分为两类,获得了确定节点集和nondetermined节点集之间的关系的基础上和的节点。

18步。是否确定节点中的所有节点集满足冗余节点确定规则。如果节点满足规则,每个节点决定应判断是否满意,是否冗余节点确定规则节点的聚类系数大于 ;如果它有,睡眠决定节点最大的是谁的聚类系数和满足冗余节点确定规则和移动节点的所有邻居节点的集和 ,分别。否则,睡眠节点和移动节点的所有邻居节点的集和 ,分别。

步骤19。确定nondetermined中的所有节点的节点集满足冗余节点确定规则。如果节点满足规则,每个nondetermined节点应该确定冗余节点确定规则是否满意,是否节点的聚类系数大于 ;如果它有,睡眠nondetermined节点最大的是谁的聚类系数和满足冗余节点确定规则和移动节点的所有邻居节点的 。否则,睡眠节点和移动节点的所有邻居节点的 。

20步。重复步骤17步19直到没有网络中节点需要睡觉。

删除节点满足冗余节点确定规则不会影响网络结构。同时,节点的聚类系数特征的紧密性和聚合网络中的节点,节点的聚类系数越大,越接近之间的连接节点和邻居。因此,节点与大聚类系数将优先删除而不影响网络结构。

4.2。删除多余的边缘

定义21(边删除规则)。节点 , , ,和形成一个完全图,和是对角线边缘。一个边缘可以删除冗余之间的边缘和 。

证明。如图5(一个)、节点 , , ,和形成一个完全图,没有漏洞和是对角线边缘。没有孔时生成唯一的边缘或删除,如图的效果是什么5 (b)和5 (c)。然而,孔边缘时生成和同时删除,如在图5 (d)。

推理22。假设边缘是一个对角优势的完全图,边缘可以删除多余的边缘,如果所有生成的2-simplices优势在完整的图形。

证明。如果所有2-simplices产生的优势在完全图,那么其他顶点的所有2-simplices包括边缘可以生成至少一个另一个2-simplex;也就是说,没有洞边缘时将被创建被删除。如图6(一),边缘是一个对角的边缘完全图由顶点 , , ,和 。所有2-simplices产生的优势是 , , , ,和 ,这是在完全图由顶点 , , ,和 。顶点和也可以生成另一个2-simplex ; 不是在任何完全图,顶点不能生成其他2-simplices。然后,生成一个新的洞边缘被删除,如图6 (b)同样,在图6 (c),边缘是一个对角的边缘完全图由顶点 , , ,和 。所有2-simplices产生的优势是 , ,Δv_一个v_cv_e, ,和这是在完全图由顶点 , , ,和 ,和顶点和也可以生成另一个2-simplex 。 是在完全图由顶点 , , ,和 ,和顶点也可以生成另一个2-simplex 。现在,没有孔边缘时将生成被删除,如图6 (d)。总之,推理22是证明。

冗余的过程中边删除图所示7。首先,所有完整的图形在网络;然后,每个完全图的对角线边缘确定并依次放入队列。最后,确定每个对角优势根据推理可以删除22。撕裂的简化复杂的继续,如果网络中冗余节点的存在后,冗余删除边。自是2-simplex没有必要简化,因此,完整的图是只考虑最大单纯复形。

5。孔检测和边界识别

孔可以确定为边界循环由几个边界简化网络的边缘。因此,孔识别工作可以分为以下两个步骤:减少边界循环边界识别和循环。

5.1。边界循环识别

发现循环有利于识别边界的边界边。撕裂复杂平面网络简化后,边界边,最多一个邻居节点。因此,边界边的洞可以确定的数量的邻居节点网络的优势。例如,邻居节点的边的数量是同一节点的邻居节点的数量吗和 。内部节点之间的不同和边界节点时识别边界边。因此,节点加权的情况下,边界节点形成一个边界边的重量是2,和节点组成的洞被称为边界节点。(1)两个节点的权重是2,如果两个节点形成一个边缘和边缘的邻居节点的数目为零,两个节点在哪里边界节点(2)两个节点的权重是2,如果两个节点形成一个边,边的邻居节点的数量不超过1,其中一个节点是一个边界节点,另一个是一个内部节点(3)两个节点的权重是2,如果两个节点形成一个边,边的邻居节点的数量不超过1,两个节点内部节点(4)除了节点(1),(2)和(3),其他节点的重量是1

节点的重量2形式的优势就是确定边界边。然而,一些边缘不是边界边缘形成一个洞,这些边缘被称为假边界边,需要删除。

定义23 (false边界边缘)。边界边称为虚假边界边如果这条边的邻居节点分布的对面的边缘。
错误的边界被删除后,其余边界边界形成的循环回路。然而,并非所有的边界循环覆盖漏洞。因此,有必要来过滤循环的边界。

定义24(边界循环过滤规则)。循环的边界将被删除,如果它满足下列三个条件。(1)循环的长度是3。(2)循环的长度是4和循环的两个不相邻节点的邻居节点。(3)两个不相邻节点的邻居节点在循环回路的长度大于4,和其他节点循环分布的对面两个不相邻节点的边组成。

证明。(1)循环是一个三角形,当循环的长度是3。三角形孔被忽略在这项研究中,和nontriangular漏洞将被识别。(2)循环的两个不相邻节点的邻居节点在一个三角循环回路的长度是4;第一个规则的基础上,满足的边界条件2需要删除。(3)如图8(一个)边界环的长度是5;和和和是不相邻的邻居节点。中的所有节点周期分布的一侧连接图等8 (b);如果有一个直接的联系和 ,不确定,确定循环覆盖的内部节点;中的所有节点周期分布的对面,如在图的连接8 (c);如果有一个直接的联系和 ,一定周期覆盖着一个节点;即循环不是洞的边界。

5.2。边界循环减少

边界循环过滤后,其余边界循环可能仍然没有洞的最短路径或多个周期包含相同的孔。因此,有必要定义一个循环减少规则缩短循环的边界。

定义25(循环减少规则)。(1)检查循环的面积是否由直接连接比原来的小环,如果节点和但不相邻的邻居节点在循环。如果是,直接连接节点和缩短边界循环,如图9(一个)。(2) , ,和在循环三个相邻节点,节点是相同的三个节点的邻居节点。检查是否循环的面积和周长都小于原来的循环,当节点取而代之的是节点吗 。如果是,该节点是用来代替节点组建一个新的循环,如图9 (b)。

6。模拟和分析

6.1。算法仿真

孔检测准确性和复杂性是重要的指标来衡量算法和比较算法的性能评估在这一节中。同时,睡眠冗余节点,删除冗余的优势,和孔检测和边界识别进一步分析该算法的性能进行评估。仿真中使用的参数设置如下:100传感器节点部署在目标区域 ,包括80内部节点随机部署和边界节点手动部署在目标区域的边界。每个边界节点有两个邻居边界节点,两个相邻的边界节点之间的距离是20米。每个传感器节点的覆盖半径10 m和通信半径20米。

但是。冗余节点睡眠

睡觉冗余节点不仅简化了复杂撕裂,也有利于检测漏洞在网络没有合并,创建新的漏洞。图1最初的网络图,图吗10 ()是冗余节点的网络图第一轮后睡觉。节点睡眠率是9%。原来的孔扩大在图10 ();然而,没有新的黑洞合并或出现。本文的算法将缩短循环后的边界。

6.1.2。删除多余的边缘

边删除规则提出了删除多余的边缘和简化复杂撕裂没有合并和漏洞的出现。通常情况下,网络中冗余节点仍然存在冗余边被删除后,如红色节点图10 (b);然后,撕裂的简化复杂仍在继续。最后简化复杂撕裂如图10 (c)中,孔的数量仍然但总面积增加。一般来说,最简单的网络结构可以经过两轮的简化和实现冗余节点的状态如图睡觉11;冗余节点的两轮后10节点睡眠睡觉,睡在第二轮和一个节点。

6.1.3。孔检测和边界识别

孔检测分为两个步骤:减少边界循环边界识别和循环。该算法首先发现边界节点和形式的边界边组成的边界节点,如图12(一个)。然而,一些边界边发现等漏洞的边界并不是真正的红色线段图12 (b)。因此,一些边界边删除通过定义错误的边界边,如图12 (c)。但是一些边界循环并不是真实的黑洞的边界。如图12 (d)与红色,循环的长度是4。属于红圈的两个不相邻节点的邻居节点,符合第二条规则的冗余循环减少规则。因此,一些边界循环需要删除冗余循环规则,结果如图12 (e)。最后,边界循环缩短如图12 (f)。

6.2。算法性能评估

6.2.1。算法的复杂性

洞在大规模场景的检测需要低复杂度和更高的效率。因此,算法的复杂性是一个重要的指标来评估覆盖孔检测的效率。本部分分析了该算法的复杂性。冗余节点睡眠阶段,检查是否满足冗余节点的节点确定规则首先,然后检查是否该节点的聚类系数是最大的邻居节点之间可以被删除,所以这个阶段的算法复杂性 ,在哪里表示网络中节点的数量。阶段的冗余边删除,找到所有完成图形组成的每个节点首先然后判断所有2-simplices由每个对角优势的完整的图形。因此,这个阶段的复杂性 ,在哪里代表每条边的邻居节点的数量。

孔检测过程分为两个步骤:减少边界循环边界识别和循环。循环边界识别阶段,节点加权形成边界边缘首先根据邻居节点的边的数量,和算法复杂性 。然后,删除错误的边界边根据邻居节点的分布边界和边界形成循环,所以小于最严重的复杂性 ,了。最后,在过滤的过程中边界循环,检查是否有两个不相邻节点的邻居节点的循环是必需的。如果是这样,它必须检查是否循环中的其他节点分布在对面的线段由这两个节点,所以最糟糕的算法的复杂性 ,在哪里孔的数量,在循环的节点数量, ,和 。减少边界循环阶段,检查是否有两个不相邻节点的邻居节点的循环以及常见的三个相邻节点的邻居节点是否存在,所以最糟糕的复杂性 。因此,孔检测的算法复杂性 。

总之,算法的复杂性 ,和细节如表所示1,在那里代表每条边的邻居节点的数量。众所周知,HBA (22)的复杂性和树洞检测算法12)的复杂性 ,在哪里是每个节点的邻居节点的数量。因此,该算法复杂度最低。

6.2.2。检测精度

检测精度是评价算法的另一个重要指标。HBA算法检测精度定义为检测孔的数量比孔的总数;同时,树洞检测方法定义的比率估计孔尺寸实际孔尺寸。相比之下,孔数的检测精度,检测孔面积的准确性更有利于修复漏洞。因此,检测精度定义为方程(5在这项研究中。 在哪里代表的实际面积,代表孔的面积算法,检测到的代表了孔检测精度。根据方程(5),该算法的准确性为99.03%。

基于上述两个指标,表2得出结论,该算法的性能优于HBA的检测方法和基于树洞。

7所示。结论

摘要撕裂复杂构造往往是平面通过一个简化的过程,这使得覆盖洞检测算法复杂度较低,精度高。在简化的过程中,首先,结合图兰定理和概念的程度和复杂网络聚类系数定义两种类型的节点(节点和nondetermined确定节点)和睡眠冗余节点根据冗余节点确定规则;然后,利用完全图的概念推导出边删除规则删除多余的边缘。最后,网络中的漏洞检测到循环的角度。仿真结果表明,该检测孔面积的精度是99.03%和复杂性 。检测覆盖漏洞在3 d空间将集中在我们进一步研究检测效率的改善。

数据可用性

测试数据,仿真数据,该方法用于支持本研究的发现可以从相应的作者。该算法在新状态,因此,算法中使用的数据的访问是受限制的。

的利益冲突

作者宣称没有利益冲突有关的出版。

确认

这项研究的部分资金由吉林省优秀青年人才基金会(批准号20190103052 jh)和青年基金会长春科技大学(批准号QN2017013)。

引用

1. 低k·s·m·c·r·Talampas“无线传感器网络的智能交通应用程序:一项调查,”工业无线传感器网络:应用程序、协议和标准,页47 - 77,CRC出版社,2013年。视图:出版商的网站|谷歌学术搜索
2. e . Ould-Ahmed-Vall b·h·费里·g·f·莱利,“分布式容错事件检测使用异构无线传感器网络,”IEEE移动计算,11卷,不。12日,第2007 - 1994页,2012年。视图:出版商的网站|谷歌学术搜索
3. f . m . Al-Turjman h . s .,和m . a . Ibnkahla”高效部署针对环境监测的无线传感器网络应用中,“计算机通信,36卷,不。2、135 - 148年,2013页。视图:出版商的网站|谷歌学术搜索
4. s . Meguerdichian f .高级m . Potkonjak m·b·斯利瓦斯塔瓦,“特别的无线传感器网络覆盖问题,”诉讼IEEE INFOCOM 2001。计算机通讯大会上。二十IEEE计算机和通信协会的年度联合会议(猫。No.01CH37213)安克雷奇,页1380 - 1387年,正义与发展党,美国,2001。视图:出版商的网站|谷歌学术搜索
5. 江邓x, y, l·t·杨,林m, l .易和m . Wang“基于数据融合的异构传感器网络覆盖优化:一项调查,“信息融合52卷,第105 - 90页,2019年。视图:出版商的网站|谷歌学术搜索
6. r, g, b . Liu j . Wang, x贾庆林,“利用数据融合来提高无线传感器网络的覆盖范围,”IEEE / ACM交易网络,20卷,不。2、450 - 462年,2012页。视图:出版商的网站|谷歌学术搜索
7. 汗,h·莫达,h . Merabti”概述无线传感器网络的漏洞,”《第11届研究生研讨会上的融合通信、网络和广播,2010年。视图:谷歌学术搜索
8. p .刘纪麟r·彼得森和d·罗斯,“在传感器网络,发现洞”IEEE学报》研讨会上无所不知的空间:机器人控制,2007年。视图:谷歌学术搜索
9. j . f . Li郑,张,“地理hole-bypassing转发协议对无线传感器网络来说,“专业的沟通,5卷,不。6,737 - 744年,2011页。视图:出版商的网站|谷歌学术搜索
10. t.w。唱,c。杨:“Voronoi-based覆盖无线定向传感器网络的改善方法,”网络和计算机应用》杂志上,39卷,不。1,第213 - 202页,2014。视图:出版商的网站|谷歌学术搜索
11. H.-C。妈,p·库马尔Sahoo, Y.-W。陈”,基于计算几何的分布式无线传感器网络覆盖洞检测协议,”网络和计算机应用》杂志上,34卷,不。5,1743 - 1756年,2011页。视图:出版商的网站|谷歌学术搜索
12. w·李和y . Wu”树型覆盖孔检测和治疗方法在无线传感器网络中,“计算机网络卷。103年,33-43,2016页。视图:出版商的网站|谷歌学术搜索
13. a . Soundarya诉桑德拉让,“一个高效的算法在无线传感器网络覆盖孔检测和治疗,”2017年1日国际会议上电子、材料工程和纳米技术(IEMENTech)2017年,页1 - 5,加尔各答,印度。视图:出版商的网站|谷歌学术搜索
14. p . Kumar Sahoo蔡明俊。蒋介石,S.-L。吴”,一个高效的分布式覆盖孔检测的无线传感器网络协议,”传感器,16卷,不。3,p。386年,2016年。视图:出版商的网站|谷歌学术搜索
15. y Bejerano”,覆盖验证没有位置信息,”IEEE移动计算,11卷,不。4、631 - 643年,2012页。视图:出版商的网站|谷歌学术搜索
16. g . s . Kasbekar y Bejerano, s . Sarkar”一生和保险担保通过分布式coordinate-free传感器激活,“IEEE / ACM交易网络,19卷,不。2、470 - 483年,2011页。视图:出版商的网站|谷歌学术搜索
17. p . j . Si c·d·吴y z, z,和l . Cheng”一个洞在无线传感器网络检测和重新部署战略,”信息与计算科学杂志》上,8卷,不。13日,2577 - 2585年,2011页。视图:谷歌学术搜索
18. x m .赵k . j .毛f·杨,w . Wang,问:陈,“检测传感研究基于OGDC覆盖洞算法对无线传感器网络来说,“《计算机信息系统,8卷,不。20日,第8568 - 8561页,2012年。视图:谷歌学术搜索
19. j·w·张,s w·李,李问:y, y . c . Liu和n . n .吴”覆盖洞恢复算法在异构无线传感器网络感知概率,”《计算机信息系统,10卷,不。7,2983 - 2990年,2014页。视图:谷歌学术搜索
20. a . Tahbaz-Salehi和a . Jadbabaie“分布式覆盖验证在没有位置信息的传感器网络,”IEEE自动控制,55卷,不。8,1837 - 1849年,2010页。视图:出版商的网站|谷歌学术搜索
21. f .严、p·马丁斯和l . Decreusefond”Connectivity-based检测在无线传感器网络中分布式覆盖洞,”IEEE - GLOBECOM 2011全球电信会议美国,页1 - 6,休斯顿,德克萨斯州,2011。视图:出版商的网站|谷歌学术搜索
22. f ., a·韦尔·马丁斯和l . Decreusefond“同源检测在无线传感器网络中分布式覆盖洞,”IEEE / ACM交易网络,23卷,不。6,1705 - 1718年,2015页。视图:出版商的网站|谷歌学术搜索
23. g . g . Wang曹、p·伯曼和t . f . la门”招标协议部署移动传感器,”IEEE移动计算》第六卷,没有。5,563 - 576年,2007页。视图:出版商的网站|谷歌学术搜索
24. y, x, z . Wang和h·刘,“基于虚拟边缘检测算法在无线传感器网络覆盖洞,”2013年IEEE无线通信和网络会议(WCNC),第1492 - 1488页,上海,中国,2013。视图:出版商的网站|谷歌学术搜索
25. 裘c和h沈”Delaunay-based coordinate-free机制完全覆盖在无线传感器网络中,“IEEE并行和分布式系统,25卷,不。4、828 - 839年,2014页。视图:出版商的网站|谷歌学术搜索
26. s . p . Fekete a . Kroeller d·费斯s费舍尔和c . Buschmann”于社区的拓扑识别在传感器网络中,计算机科学,卷3121,不。2,18日至19日,2004页。视图:谷歌学术搜索
27. 凡克和c·克莱恩,”孔检测或:几何隐藏在连接多少?“在学报》第二十二届研讨会上计算几何——SCG 06年塞多纳,页377 - 385年,阿兹,美国,2006年。视图:出版商的网站|谷歌学术搜索
28. 吴x,汉族,y、x王”覆盖率和能源消耗控制在移动异构无线传感器网络,”IEEE自动控制,卷。58岁的没有。4、975 - 988年,2013页。视图:出版商的网站|谷歌学术搜索
29. 答:默罕默德和m . Egerstedt”控制在网络拓扑,使用高阶拉普拉斯算子”第17届国际研讨会学报》网络和系统的数学理论《京都议定书》,页1024 - 1038年,日本,2006年。视图:谷歌学术搜索
30. l . b . Wang x邓,w . Liu Yang和h c .曹国伟”覆盖在传感器网络领域重建自信的信息,“IEEE无线通信,20卷,不。6,74 - 81年,2013页。视图:出版商的网站|谷歌学术搜索
31. d . l .咦,x邓,m . Wang叮,和y王,“本地化自信在物联网信息覆盖洞检测放射性污染监测,“IEEE访问5卷,第18674 - 18665页,2017年。视图:出版商的网站|谷歌学术搜索
32. 邓l .咦,x, z邹,d .丁和l·t·杨,“自信的信息覆盖洞检测传感器网络对铀尾矿监测、”杂志的并行和分布式计算,第118卷,第1部分,页57 - 66,2018。视图:出版商的网站|谷歌学术搜索
33. 邓x l·t·杨,l, m . Wang和z朱,“检测自信的信息覆盖洞工业物联网:节能的角度来看,“IEEE通讯杂志卷,56号9日,第73 - 68页,2018年。视图:出版商的网站|谷歌学术搜索

版权

版权©2020年京张等。这是一个开放分布式下文章知识共享归属许可,它允许无限制的使用、分配和复制在任何媒介,提供最初的工作是正确引用。