无线传感器网络连通忌覆盖问题及其解决方案综述

覆盖控制是无线传感器网络的一个基本问题,通过对网络空间资源的优化分配,来更好地完成环境感知和有效传输等任务。作为覆盖控制理论的研究热点之一,连通k覆盖问题研究如何从随机部署的大量传感器节点中选择一部分节点激活,使得任意监测目标都被至少k个不同的活跃节点同时覆盖,而且所有活跃节点都是通信连通的。本文分析了无线传感器网络中连通k覆盖问题的系统模型和算法评价指标,介绍了一些典型的近似算法并对其进行了分析和比较,最后进行了总结和展望。     

无线传感器网络的连通覆盖临界条件分析

连通与覆盖控制作为无线传感器网络中两个最基本的问题,取决于网络配置及节点的传播距离,反映了网络的感知质量与资源的优化分配。为了用最优化数量的传感器节点来改善和确保网络的连通与覆盖,在分析现有研究成果的基础上,提出了满足渐进连通覆盖的临界充分条件及必要条件。理论分析及仿真实验均表明,提出的临界条件更紧凑和规则化,有助于对无线传感器网络进行更细致的研究。     

异构无线传感器网络中覆盖度和连通度的研究

覆盖度和连通度研究是无线传感器网络中的关键问题。以往研究背景为同构无线传感器网络,这样可以简化问题,但随着问题的深入,不得不考虑异构节点覆盖。系统地对异构无线传感器网络进行了分类,提出了感知异构和通信异构结合的无线传感器网络下的异构节点感知模型,其次分析了两类异构节点之间的覆盖度的计算,最后分析了异构网络的单连通和重连通。此外实现了大量的仿真实验,得出了节点数量和单连通、重连通的概率曲线。     

无线传感器网络的覆盖和连通研究

节点配置是无线传感器网络研究的核心问题之一。为实现传感器节点的配置,随机散布方式被广泛地采用。主要研究了无线传感器网络节点随机配置的完全覆盖和连通问题。通过对网络完全覆盖和连通的分析,给出完全覆盖概率、检测半径和节点数目之间的定量关系;分析了参数对配置的影响,对比高斯分布和均匀分布的配置特性,以指导传感器网络的节点放置。提出了完全覆盖径向连通的配置方案来优化传感器节点数目,从而降低网络的配置代价。最后,利用模拟仿真试验来评定结论。     

无线传感器网络一维区域的覆盖研究*

无线传感器网络覆盖问题的研究应综合考虑感知覆盖、通信覆盖和连通覆盖三个方面,建立适合不同监测空间的节点覆盖模型。讨论了无线传感器网络一维区域的覆盖问题,对无线传感器网络中一维直线区域出现的问题进行分析,讨论了均匀分布情况下的节点覆盖概率和覆盖数的计算方法,仿真实验表明节点感知半径是影响节点覆盖率和覆盖数的主要因素。     

无线传感器网络中基于Voronoi图的覆盖和连通综合配置协议

着重研究无线传感器网络随机部署下的覆盖和连通问题的解决方案,尤其是当无线传感器节点的通信半径Rc与感应半径Rs之比小于2时的解决方案.本文提出了无线传感器网络中一个基于Voronoi图的覆盖和连通的综合配置协议(VIP).该协议采用了一种分布式节点冗余判断算法以判断无线传感器网络中节点的冗余性,并让节点据此来对自身进行相应的职能调度.该协议能够在Rc/Rs为任意值时保证网络的覆盖和连通性能.本文还将该协议进行了推广,使得该协议能够满足覆盖度和连通度动态变化的要求,保证网络的k-度覆盖和k-度连通.     

无线传感器网络覆盖和连通问题概述

覆盖和连通是无线传感器网络中两个密切相关的基本问题,直接影响着网络性能和网络任务完成的质量。文章给出了传感器节点的感知模型,从不同角度对覆盖问题进行了分类,阐述了覆盖控制算法的评价指标,介绍了覆盖问题和连通问题的典型算法,最后对覆盖和连通问题的研究方向进行了展望。     

无线传感网络中覆盖保持的K-连通子集构造算法

构造无线传感网络中具有连通覆盖特性的节点子集是实现网络休眠调度、延长网络生命周期的关键技术之一,具有重要的研究意义.已有的研究大多侧重于k覆盖节点子集构造问题,由于k覆盖子集在一定条件下便满足k连通,故人们对k连通子集的构造问题研究较少,但通过构造k覆盖节点子集来实现k连通会耗费过多的节点,代价较大.因此,本文提出一个直接构造k连通1覆盖节点子集的算法-CPC,能够用较少的节点构造出一个既能满足网络的覆盖特性又能够满足k-连通特性的节点子集,使得在任意k-1个节点发生故障时,网络能够仍然保持连通.本文还对算法的正确性进行了严格证明,并通过仿真实验与相关算法进行了性能比较.结果表明,与已有的k覆盖算法相比,CPC算法能够节省约55%的节点数.     

无线传感器网络中连通问题的容错性分析

在确定部署的无线传感器网络中,由于节点本身的脆弱性及应用环境的恶劣性,在部署及研究分析网络时应该考虑到网络节点出错的因素.当网络连通概率和网络规模给定时,网络节点的出错概率应在多大的范围之内;在给定的网络规模和节点出错概率下,网络的覆盖与连通情况如何,这些都是本文分析研究的内容.本文首先定义了一个比较规范的三角形(Triangular)模型,研究了在确定部署情况下,网络节点出错的概率与网络的覆盖概率之间的关系,然后借助"k阶子网"的概念分析了Triangular网络的连通容错性,最后通过模拟试验,对前面通过理论分析计算出的传感器网络连通概率的下界和节点出错概率的上界的可信性进行验证,同时将Triangular拓扑的网络与网格状网络进行比较.     

无线传感器网络k点连通可靠性的研究

无线传感器网络的出现引起了人们的广泛关注,由于无线传感器网络的节点不是预先定位而是随机撒放,那么如何保证一定区域内的传感器节点在满足连通可靠性要求的情况下连结成一张网络?而若干次随机抛撒所形成网络的连通度的平均值与网络的节点个数、节点的通讯半径之间又有何关系?通过计算机仿真模拟试验,给出了网络的k(k>0)连通度概率分布曲线;引入了连通度的数学期望概念来描述若干次抛撒所形成网络的连通度k的平均值,给出了其随网络节点个数、节点通讯半径变化的回归方程;给出了无线传感器网络k点连通概率曲线和3点连通的经验公式;分析了边界节点对网络连通度的影响.这些对无线传感器网络节点个数和节点通讯半径的选择、系统冗余设计等都具有重要的指导意义或参考价值.     

基于静态和移动传感器的WSN的k-覆盖研究

针对无线传感器网络的k-覆盖问题进行了研究。首先定义一个表征网络覆盖效率的过度提供因子,并在此基础上对静态传感器网络和全移动传感器网络的k-覆盖问题进行分析,得到这两种情形下的过度提供因子以及全移动传感器网络中移动传感器的最大移动距离;进而提出一种由静态传感器和少量移动传感器构成的混合网络结构,并得到了这种网络结构下不依赖于网络大小的k-覆盖以及调度移动传感器移动的分布式移动调度算法,从而实现有效覆盖。仿真结果表明,提出的混合网络结构不仅能够实现精确的k-覆盖,而且相比于其他k-覆盖算法,有更高的覆盖率。     

有向传感器网络中基于概率感知模型的最小连通k覆盖集算法

无线传感器网络的基本问题之一是,网络节点如何利用有限的能量对人们所关注的物理世界进行满意的监测,这可抽象为最小连通k覆盖集问题。传统的最小连通k覆盖集问题是基于确定型全向感知模型的,该模型过于理想化,不能适用于复杂的应用环境,也不能应用于有向传感器网络中。针对上述局限,本文提出了有向传感器网络中基于概率感感知模型的最小连通k覆盖集问题（MCKS）,并指出这是NP难问题;设计了基于0-1整数规划和最小生成树的集中式近 BDA）,分别证明两种算法最终得到的是MCKS问题的可行解,并分析了算法的时间复杂度、性能比和通信复杂度。通过仿真实验并与ILP算法和BGA算法进行比较的结果表明： 在基于概率感知模型的条件下,IPA和CBDA能够有效实现有向传感器网络中的连通k覆盖,并且激活节点数目较少,网络寿命延长。     

Distributed Deployment Schemes for Mobile Wireless Sensor Networks to Ensure Multilevel Coverage

One of the research issues in wireless sensor networks (WSNs) is how to efficiently deploy sensors to cover an area. In this paper, we solve the k-coverage sensor deployment problem to achieve multi-level coverage of an area I. We consider two sub-problems: k-coverage placement and distributed dispatch problems. The placement problem asks how to determine the minimum number of sensors required and their locations in I to guarantee that I is k-covered and the network is connected; the dispatch problem asks how to schedule mobile sensors to move to the designated locations according to the result computed by the placement strategy such that the energy consumption due to movement is minimized. Our solutions to the placement problem consider both the binary and probabilistic sensing models, and allow an arbitrary relationship between the communication distance and sensing distance of sensors. For the dispatch problem, we propose a competition-based and a pattern-based schemes. The former allows mobile sensors to bid for their closest locations, while the latter allows sensors to derive the target locations on their own. Our proposed schemes are efficient in terms of the number of sensors required and are distributed in nature. Simulation results are presented to verify their effectiveness.     

无线传感器网络中应用鲁洛三角形的k度覆盖算法

覆盖问题是无线传感器网络中的基本问题之一。着重考虑无线传感器网络在随机部署节点情况下的多重覆盖问题,提出一种应用鲁洛三角形的k度覆盖算法RTCA(Reuleaux triangle-based k-coverage algorithm)。RTCA把每个传感器节点的覆盖圆划分成6个相同的双弧形区域,根据网络覆盖度要求,调度这些区域内的节点状态来实现k度覆盖监测区域。仿真实验结果表明,RTCA在保证网络覆盖质量要求的同时能够有效地减少活跃节点的数量,延长网络的生存时间。未来还可以对该算法做进一步推广,以较容易地判断异构无线传感器网络的多重覆盖。     

基于立方体剖分的传感器网络快速三维k-覆盖判定算法

提出了一种传感器网络中基于立方体剖分的三维k 覆盖快速判定算（CP-RTCDA）和三维最大k 覆盖问题的快速求解算法（CP-RTMCDA）。算法首先把感兴趣区域剖分为立方体区域，从而将复杂的空间区域覆盖问题转化为简单的立方体区域覆盖问题。理论分析与仿真实验表明, 针对具有n个节点的传感器网络, 新算法的计算时间复杂度为O(n)，远低于已有算法O(n3logn)的计算时间复杂度。     

三维水下传感网相异k-覆盖改进虚拟力算法

水下传感器的覆盖控制研究对于合理分配网络的空间资源,更好地完成环境感知、信息获取任务以及提高网络生存能力都具有重要的意义.实际情况中,水下监测区域往往需要不均匀的覆盖.现有的研究偏重于“事件驱动”概念,但不同区域的不同k-覆盖需求并未得到重视.针对UWSNs 相异k-覆盖需求区域的覆盖优化部署这一研究方向,基于浮标、锚、与浮标通过有线电缆连接通信的水下传感器模型,分析了相异k-覆盖需求区域所需的节点数下限,提出了一种基于相异k-覆盖需求的改进虚拟力算法k-ERVFA(k-equivalent radius virtual force algorithm).仿真实验结果表明,相比经典的虚拟力算法,在相同最大迭代次数和相同节点数的情况下,该算法在牺牲1-覆盖需求区域的1-覆盖率仅1.21%~3.89%的情况下,能够同比提高相应区域的2-、3-覆盖率分别达到17.42%~44.3%和28.95%~49.53%,取得了很好的部署效果,说明了k-ERVFA 算法的正确性与有效性.     

无线传感器网络中一种分布式冗余检测算法

无线传感器网络覆盖控制中现有的大部分冗余检测算法都是针对节点感知半径相同的同构网络的,无法应用于异构网络.提出一种保持网络k级覆盖的适应异构传感器网络的分布式冗余检测算法.该算法根据节点的冗余分布特性设计了有效覆盖邻居选取,通过有效覆盖邻居感知半径关系及交点处的覆盖程度判断检测冗余.仿真表明:算法中有效覆盖邻居选取的设计,大大降低了节点执行冗余计算的时间,算法的运行效率较高;算法在异构WSN中性能优异,冗余检测彻底、充分,有益于节省节点能量,延长网络生存时间.     

带时延约束的连通目标覆盖最大化生命周期问题

在无线传感器网络中,如何确保网络服务质量（如覆盖、连通）同时最大化网络生命周期是研究的热点和难点.在延时敏感的应用（如火灾、爆炸等灾害监测）中,传感器节点必须在有限的时间内传送它们的数据到汇聚节点.为了研究这种应用下的连通目标覆盖,提出了一种带时延约束的连通目标覆盖问题(DCCTC).首先,将DCCTC建模成为限高的最大覆盖树问题(HLMCT),并证明它是NP-Complete的.然后,设计了一种快速启发式算法HLCWGC求解HLMCT问题.仿真实验和理论证明,HLCWGC在时延约束下获得的网络生命周期比已有的算法要好.具有较高的应用价值和理论意义.     

基于矩形分区覆盖的节点确定部署策略

针对井下无线传感器网络k（k=2）重覆盖问题,提出一种基于矩形分区覆盖的节点确定部署策略。采用矩形分区覆盖部署方式,在只给出网络规模和节点感应半径的条件下,求出网络所需最少节点个数和节点间距。理论分析和仿真实验表明,该策略不仅能够满足井下无线传感器网络的覆盖度要求,而且比等腰三角形分区覆盖部署和线形部署节省约7%的节点数目,网络平均路由跳数约为等腰三角形部署和线形部署的1/2。