A survey on coverage and connectivity issues in wireless sensor networks

A wireless sensor network (WSN) is composed of a group of small power-constrained nodes with functions of sensing and communication, which can be scattered over a vast region for the purpose of detecting or monitoring some special events. The first challenge encountered in WSNs is how to cover a monitoring region perfectly. Coverage and connectivity are two of the most fundamental issues in WSNs, which have a great impact on the performance of WSNs. Optimized deployment strategy, sleep scheduling mechanism, and coverage radius cannot only reduce cost, but also extend the network lifetime. In this paper, we classify the coverage problem from different angles, describe the evaluation metrics of coverage control algorithms, analyze the relationship between coverage and connectivity, compare typical simulation tools, and discuss research challenges and existing problems in this area.     

无线传感器网络节点部署问题研究

节点部署是无线传感器网络(W SNs)研究的一个基本问题。合理的节点部署方式有助于提高网络工作效率,优化利用网络资源。针对与节点部署相关的覆盖、连通、能耗三方面基本问题,对现有主要研究成果进行了分类和比较,讨论了三者之间的关系,总结性地提出并分析了网络覆盖和连通性能的评价标准。     

无线传感器网络中基于异构节点的覆盖控制算法

研究了无线传感器网络中基于异构节点的优化覆盖控制问题.异构无线传感器网络由两类能力不同的节点组成,包括普通节点和超级节点.对普通节点采用基于状态轮转的覆盖控制算法,对超级节点采用基于路由表的转发策略.通过两类节点的协作使得网络达到覆盖与连通的目的.模拟结果表明,在具有相同初始能量的情况下,该算法与SHHN-HS算法相比能够延长网络生命期.     

基于连通性的无线传感器网络覆盖优化算法

针对无线传感器网络(WSNs)的覆盖优化和连通性问题,提出了一种基于连通性的WSNs覆盖优化算法(CC-BCBS).在二维监测区域内,CC-BCBS以传感器节点间的通信半径作为限制条件,只对连通的传感器节点进行Voronoi图划分,根据节点对应泰森多边形的覆盖情况构造盲区图,将盲区重心作为候选优化位置,使节点尽可能最大化覆盖监测区域.节点通信半径影响着区域覆盖的冗余度,故针对划分时可能出现的3种不同连通情况,给出了相应措施.仿真结果表明:CC-BCBS在覆盖率,分布均匀性,平均连通个数与连通率方面相比BCBS等算法有明显优势.     

无线传感器网络的拓扑控制研究*

讨论了拓扑控制的目标,利用随机图理论研究了无线传感器网络拓扑控制的模型及代表性算法;基于网络结构的不同,分析和比较了无线传感器网络中各种拓扑控制机制的特征;深层剖析了无线传感器网络拓扑控制与连通、调度之间的关系;最后对拓扑控制亟待解决的问题进行了总结和展望。     

Reliable networks with unreliable sensors

Wireless sensor networks (WSNs) deployed in hostile environments suffer from a high rate of node failure. We investigate the effect of such failure rate on network connectivity. We provide a formal analysis that establishes the relationship between node density, network size, failure probability, and network connectivity. We show that large networks can maintain connectivity despite a significantly high probability of node failure. We derive mathematical functions that provide lower bounds on network connectivity in WSNs. We compute these functions for some realistic values of node reliability, area covered by the network, and node density, to show that, for instance, networks with over a million nodes can maintain connectivity with a probability exceeding 95% despite node failure probability exceeding 53%.     

基于WSNs的部分覆盖应用的节点唤醒机制

无线传感网络WSNs(Wireless Sensor Networks)已广泛应用于各类领域.然而,由于能量有限,提高传感节点能效是一项挑战工作.休眠调度策略是保存能量、延长网络寿命的有效策略.此外,多数WSNs应用并不要求100％的覆盖.为此,提出面向部分覆盖应用的节点唤醒机制,且标记为PCLA.PCLA机制引用学习自动机去合理地唤醒节点,而其他节点休眠,进而延长网络寿命.首先,唤醒部分节点构成主干网,然后,再利用这些节点的邻居去满足网络覆盖要求.实验数据表明,与同类机制相比,提出的PCLA机制能够有效地满足部分覆盖要求,并且在活动节点数和网络寿命方面也具有较好的性能.     

基于CVT模型的无线传感器网络覆盖优化

针对目前无线传感器网络(WSNs)节点随机部署时覆盖率低的不足,提出了一种质心化的Voronoi图(CVT)模型和圆覆盖结合的方法用于网络覆盖的优化方法.将网络覆盖优化问题简化,转化为每个WSNs节点各自覆盖对应Voronoi多边形区域的优化问题,降低了问题的复杂性,不仅使得WSNs的节点部署和区域划分更加合理,同时使得网络覆盖范围更佳.实验结果表明:模型能够有效提高WSNs的覆盖率,提供了更优的网络通信服务.     

基于垂直采样的水下三维传感网覆盖算法

针对水下环境的三维传感器网络节点随机部署时存在覆盖率低的问题,设计一种基于垂直采样的水下三维传感网络覆盖算法,用于提高水下三维传感器网络覆盖率和连通性.垂直采样算法首先对三维监测区域进行垂直平面采样,然后再对该平面进行直线采样,把三维空间的覆盖问题转化为多平面内的直线覆盖优化问题,达到对整个三维网络覆盖优化的目的.仿真结果表明,在100 m×100 m×100 m的三维监测水域,垂直采样算法比三维随机部署策略可提高约4%~28%的覆盖率,在节点数为40时对覆盖率的提升程度最大.     

Metaheuristics for maximization of obstacles constrained area coverage in heterogeneous wireless sensor networks

Wireless Sensor Networks (WSNs) collect and transfer environmental data from a predefined field to a base station to be processed and analyzed. A major problem in designing WSNs is coverage maximization, in which a given number of sensor nodes must be deployed in a way that maximizes area coverage of a given network, without violating practical constraints. This is a known NP-hard problem and thus requires metaheuristic approaches for practical problem sizes.Two metaheuristics, namely Genetic Algorithm and Particle Swarm Optimization are proposed to tackle this problem. Our new contributions include a partial use of heuristic initialization, new fitness function, modified virtual force algorithm, addition of a uniform deceleration to the calculation of inertia weight and addition of the influence of sub-populations’ head individuals. The proposed algorithms are comprehensively experimented and compared with the current state-of-the-art for the equivalent problem without obstacles. Experimental results not only suggest which algorithms should be applied to which cases, but also provide insights into parameter settings, effects of heuristic initialization and effects of virtual force algorithm in each case. These conclusions are meaningful for our future research on obstacles constrained area coverage problems related to connectivity and lifetime of WSNs.     

基于CDS的水下声音无线传感器网络节点部署方案研究

由于难以访问三维水下环境,所以要实现水下声音无线传感器网络(UAWSNs)最大覆盖且传感器自主部署,难度很大。如果还要保证最终网络的连通性,则问题更为复杂。提出一种只需把传感器随机部署到水面上的UWASNs完全分布式节点部署算法,目的是使初始网络成为可和水面基站进行通信的三维网络同时实现最大覆盖。具体思路是确定初始网络的连通支配集,然后调整具体支配节点所有相邻支配节点和被支配节点的深度,以尽量降低节点覆盖重叠现象,同时保证与支配节点的连通性。仿真结果表明:无论传输和传感范围比如何,网络连通性均可保证,且覆盖范围性能与覆盖感知部署算法相近。     

Connectivity and coverage maintenance in wireless sensor networks

One of the main design challenges for wireless sensor networks (WSNs) is to obtain long system lifetime without sacrificing system original performance such as communication connectivity and sensing coverage. A large number of sensor nodes are deployed in redundant fashion in dense sensor networks, which lead to higher energy consumption. We propose a distributed framework for energy efficient connectivity and coverage maintenance in WSNs. In our framework, each sensor makes self-scheduling to separately control the states of RF and sensing unit based on dynamic coordinated reconstruction mechanism. A novel energy-balanced distributed connected dominating set algorithm is presented to make connectivity maintenance; and also a distributed node sensing scheduling is brought forward to maintain the network coverage according to the surveillance requirements. We implemented our framework by C++ programming, and the simulation results show that our framework outperforms several related work by considerably improving the energy performance of sensor networks to effectively extend network lifetime.     

Quantifying connectivity in wireless sensor networks with grid-based deployments

Measuring network connectivity under grid-based deployment in 3D space is a challenging problem in wireless sensor networks (WSNs). Solving such a problem becomes an even more intricate task with realistic deployment factors such as placement uncertainty and hindrances to wireless communication channels. While much work has been published on optimizing connectivity, only a few papers have addressed such realistic aspects which cause severe connectivity problems in practice. In this paper, we introduce a novel grid-based deployment metric, called Average Connectivity Percentage in order to characterize the deployed network connectivity when sensor placements are subject to random errors around their corresponding grid locations. A generic approach is proposed to assess and evaluate the proposed metric. This generic approach is independent of the grid-shape, random error distributions, and different environment-based channel characteristics. We apply the generic approach in two practical deployment scenarios: the grid-based deployment with bounded uniform errors and with unbounded normal errors. In both cases, the average connectivity percentage is computed numerically and verified via extensive simulations. Based on the numerical results, quantified effects of positioning errors and grid edge length on the average connectivity percentage are outlined.     

C3: an energy-efficient protocol for coverage,connectivity and communication in WSNs

The lower layer of ubiquitous and pervasive systems consists of wireless ad hoc and sensor networks. In wireless sensor networks (WSNs), sensors consume most of their energy in data transmission and idle listening. Hence, efficient usage of energy can be ensured by improved protocols for topology control (i.e., coverage and connectivity), sleep scheduling, communication, and aggregation and compression of data. Though several protocols have been proposed for this purpose, they are not energy-efficient. We propose an integrated and energy-efficient protocol for Coverage, Connectivity, and Communication (C3) in WSNs. The C3 protocol uses received signal strength indicator to divide the network into virtual rings, defines clusters with clusterheads more probably at alternating rings, defines dings that are rings inside a cluster and uses triangular tessellation to identify redundant nodes, and communicates data to sink through clusterheads and gateways. The proposed protocol strives for near-optimal deployment, load balancing, and energy-efficient communication. Simulation results show that the C3 protocol ensures partial coverage of more than 90 % of the total deployment area, ensures one connected network, and facilitates energy-efficient communication while expending only one-fourth of the energy compared to other related protocols such as the coverage and connectivity protocol, and the layered diffusion-based coverage control.     

Learning automata-based algorithms for finding cover sets in wireless sensor networks

Wireless sensor networks (WSNs) have been widely used in different applications. One of the most significant issues in WSNs is developing an efficient algorithm to monitor all the targets and, at the same time, extend the network lifetime. As sensors are often densely deployed, employing scheduling algorithms can be considered a promising approach that is able ultimately to result in extending total network lifetime. In this paper, we propose three learning automata-based scheduling algorithms for solving target coverage problem in WSNs. The proposed algorithms employ learning automata (LA) to determine the sensors that should be activated at each stage for monitoring all the targets. Additionally, we design a pruning rule and manage critical targets in order to maximize network lifetime. In order to evaluate the performance of the proposed algorithms, extensive simulation experiments were carried out, which demonstrated the effectiveness of the proposed algorithms in terms of extending the network lifetime. Simulation results also revealed that by a proper choice of the learning rate, a proper trade-off could be achieved between the network lifetime and running time.     

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

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

基于能量感知的无线传感器网络拓扑演化

针对无线传感器网络中能源效率的问题,引入复杂网络理论的研究方法,提出基于能量感知无线传感器网络拓扑动态演化模型。在建模过程中考虑到无线传感器网络拓扑变化与节点的度数和剩余能量密切相关,而且网络中节点和链路是有增有减的动态行为,利用连续场理论推导出此模型具有无标度的特征,无标度网络对于节点的随机故障具有较高的鲁棒性。数值计算与实验仿真结果显示,算法可以有效地改善整个网络的结点均衡能耗。     

无线传感器网络三维表面k覆盖多连通部署方法*

无线传感器网络中覆盖连通问题是基本且重要的问题,三维表面作为无线传感器网络中的一种特殊情形,对应于现实世界中的山体,为了解决这类与实际应用密切相关的问题,提出了三维表面k覆盖多连通部署方法。该方法结合三维表面的地形特征,首先在目标区域自由选择网格大小进行划分,接着在各网格之间建立多连通关系,再通过方向梯度概率感知模型在网格内先构造k覆盖集,然后利用最小生成树算法构造连通图,最后找出关节点构造双连通图。大量仿真实验表明,该方法能够对目标区域进行完全覆盖和连通,并且能保证网络的健壮性。     

无线传感器网络服务质量的随机控制策略

为使网络具有给定的感知范围或覆盖率,必须保证WSN传感器具有一定空间密度,因此网络中活动的传感器数量可作为QoS的一种度量[1]。在这种定义下,提出两种QoS控制方法,基于贪心算法的集中式控制方法和基于寿命的分布式随机控制方法。如果传感器能够存储运行状态信息或每隔一段时间能够交换节点寿命信息,前者可以获得最优的网络寿命;后者则通过交换初始传感器节点寿命,利用平均寿命信息随机调度活动的节点,从而延缓存活节点数的降低。仿真结果证实了这两种方法的有效性。     

Relay node placement in structurally damaged wireless sensor networks via triangular steiner tree approximation

Wireless sensor networks (WSNs) have many applications which operate in hostile environments. Due to the harsh surroundings, WSNs may suffer from a large scale damage that causes many nodes to fail simultaneously and the network to get partitioned into multiple disjoint segments. In such a case, restoring the network connectivity is very important in order to avoid negative effects on the applications. In this paper, we pursue the placement of the least number of relay nodes to re-establish a strongly connected network topology. The problem of finding the minimum count and the position of relay nodes is NP-hard and hence we pursue heuristics. We present a novel three-step algorithm called FeSTA which is based on steinerizing appropriate triangles. Each segment is represented by a terminal. Each subset of 3 terminals forms a triangle. Finding the optimal solution for a triangle (i.e. connecting 3 segments) is a relatively easier problem. In the first step, FeSTA finds the best triangles and form islands of segments by establishing intra-triangle connectivity. Then in the second, disjoint islands of segment are federated. In the final step, the steinerized edges are optimized. The performance of FeSTA is validated through simulation.