Barrier coverage with line-based deployed mobile sensors

Barrier coverage of a wireless sensor network is a critical issue in military and homeland security applications, aiming to detect intruders that attempt to cross the deployed region. While a range of problems related to barrier coverage have been investigated, little effort has been made to explore the effects of different sensor deployment strategies and mechanisms to improve barrier coverage of a wireless sensor network after it is deployed. In this paper we study the barrier coverage of a line-based sensor deployment strategy and explore how to exploit sensor mobility to improve barrier coverage. We first establish a tight lower bound for the existence of barrier coverage under the line-based deployment. Our results show that the barrier coverage of the line-based deployment significantly outperforms that of the Poisson model when the random offsets are relatively small compared to the sensor’s sensing range. To take advantage of the performance of line-based deployment, we further devise an efficient algorithm to relocate mobile sensors based on the deployed line so as to improve barrier coverage. The algorithm finds barrier gaps and then relocates mobile sensors to fill the gaps while at the same time balancing the energy consumption among mobile sensors. Simulation results show that the algorithms can effectively improve the barrier coverage of a wireless sensor network for a wide range of deployment parameters. Therefore, in wireless sensor network applications, the coverage goal, possible sensor deployment strategies, and sensor mobility must be carefully and jointly considered. The results obtained in this paper will provide important guidelines and insights into the deployment and performance of wireless sensor networks for barrier coverage.     

On Connected Multiple Point Coverage in Wireless Sensor Networks

We consider a wireless sensor network consisting of a set of sensors deployed randomly. A point in the monitored area is covered if it is within the sensing range of a sensor. In some applications, when the network is sufficiently dense, area coverage can be approximated by guaranteeing point coverage. In this case, all the points of wireless devices could be used to represent the whole area, and the working sensors are supposed to cover all the sensors. Many applications related to security and reliability require guaranteed k-coverage of the area at all times. In this paper, we formalize the k-(Connected) Coverage Set (k-CCS/k-CS) problems, develop a linear programming algorithm, and design two non-global solutions for them. Some theoretical analysis is also provided followed by simulation results.     

Efficient Sensor Deployment Control Schemes and Performance Evaluation for Obstacle and Unknown Environments

Deployment is a fundamental issue for wireless sensor networks (WSNs). A well-designed deployment control method not only directly influences the number of deployed sensors, but also influences on data accuracy and network topology. Three widely discussed deployment methods are random deployment, deterministic deployment and deployment by graphic theory. Most related works have focused on the maximal deployment area problem, but few studies have considered efficient methods to solve the k-coverage problem. Moreover, such methods have high time complexity, making them unsuitable for k-covered sensor deployment. To achieve scalable and efficient deployment, this study presents two new topology deployment methods, namely the slow-start method (SSM) and square-encircled method (SEM). The proposed deployment methods can yield k-covered scenarios with minimal overlapping areas, by three different coverage sensors. SSM and SEM are without needing to pre-analyze unknown or unsafe environments when deploying a k-coverage area. Deploying and satisfying each layer until k layers are obtained requires guaranteeing k coverage. The proposed methods have time complexities of O(n ²), making them suitable for WSNs. Moreover, this study first presents nine Construct Performance Evaluation (CPE) factors to evaluate the total costs of a WSN. Finally, this study evaluates the total deployment costs through CPE factors, and analyzes their performance. The simulation results clearly indicate the efficiency and effectiveness of the proposed deployment methods.

CWSC: Connected k-coverage working sets construction algorithm in wireless sensor networks

One of the most important issues for wireless sensor networks is to get a long network lifetime without affecting either communication connectivity or sensing coverage. Many sensors that are deployed randomly in a dense sensor network in a redundant way waste a lot of energy. One effective way to save energy is to let only a subset of sensors work at any given time. In this paper, we mainly consider such a problem. Selecting the minimum number of connected sensor nodes that can provide k-coverage (k ≥ 1), i.e., selecting a subset S of working sensors, such that almost every point in the sensing region can be covered by at least k sensors and the sensors in S can form a connected communication subgraph. We propose a connected k-coverage working sets construction algorithm (CWSC) based on Euclidean distance to k-cover the sensing region while minimizing the number of working sensors. CWSC can produce different coverage degrees according to different applications, which can enhance the flexibility of the sensor network. Simulation results show that the proposed algorithm, which can conserve energy and prolong the lifetime of the sensor network, is better than the previous algorithms.     

A study on one‐dimensional k‐coverage problem in wireless sensor networks

In this paper, we study the one‐dimensional coverage problem in a wireless sensor network (WSN) and consider a network deployed along a one‐dimensional line according to a Poisson distribution. We analyze three important parameters that are related to the problem, i.e., expected k‐coverage proportion, full k‐coverage probability, and partial k‐coverage probability, and derive mathematical models that describe the relationships between the node density in the network and these parameters. The purpose is to calculate or estimate the node density required for achieving a given coverage probability, which is useful in the deployment of a one‐dimensional network for many applications. We first analyze the expected k‐coverage proportion, then analyze the full k‐coverage probability for k = 1 and the lower bound to the full k‐coverage probability for k > 1, and finally analyze the partial k‐coverage probability for k = 1 and give a brief discussion of the partial k‐coverage probability for k > 1. The mathematical models are validated through simulation. Copyright © 2011 John Wiley & Sons, Ltd.     

Optimal barrier coverage for critical area surveillance using wireless sensor networks

Intrusion detection using barrier coverage is one of many applications existed in wireless sensor networks. The main purpose of using barrier coverage is to monitor the borders of a specific area against the intruders that are trying to penetrate this critical area by ensuring the total coverage with a low cost and extending the lifetime of the network, many solutions have been proposed in the literature in order to solve the coverage problem in wireless sensor networks, which became a vital field of research. In this paper, we present a new technique based on geometric mathematical models, in order to guarantee the total coverage of our deployed barriers with a minimum possible number of sensors. The idea is to calculate the number of sensors adequate to cover a barrier before deployment. We then formulate the problem to minimize the number of sensors to be deployed to properly cover a barrier; the calculation makes it possible to solve this problem in polynomial using our own heuristic. Additionally, we propose a new mechanism for ensuring a fault‐tolerant network by detecting the faulty sensors and select other suited sensors to close the existing gaps inside the barriers and detecting the sensors whose energy is low before the failure. The obtained simulation results prove the effectiveness of the proposed algorithms.     

Effective sensor deployment based on field information coverage in precision agriculture

Coverage is an importance issue in wireless sensor networks. In this work, we first propose a novel notion of information coverage, which refers to the coverage efficiency of field information covered by deployed sensor nodes. On the basis of information coverage, we consider an optimization problem of how to partition the given field into multiple parcels and to deploy sensor nodes in some selected parcels such that the field information covered by the deployed sensor nodes meets the requirement. First, we develop two effective polynomial‐time algorithms to determine the deployed locations of source nodes for information 1‐coverage and q‐coverage of the field, respectively, without consideration of communication, where information q‐coverage implies that the field information in terms of information point is covered by at least q source nodes. Also, we prove the upper bound in the theoretical for the approximate solution derived by our proposed method. Second, another polynomial‐time algorithm is presented for deriving the deployed locations of relay nodes. In the theoretical, this proposed algorithm can achieve the minimized number of relay nodes. Further, the related information 1‐coverage algorithms are applied in our wireless sensor network‐based automatic irrigation project in precision agriculture. Experimental results show the major trade‐offs of impact factors in sensor deployment and significant performance improvements achieved by our proposed method. Copyright © 2013 John Wiley & Sons, Ltd.     

Expected k-coverage in wireless sensor networks

We are concerned with wireless sensor networks where n sensors are independently and uniformly distributed at random in a finite plane. Events that are within a fixed distance from some sensor are assumed to be detectable and the sensor is said to cover that point. In this paper, we have formulated an exact mathematical expression for the expected area that can be covered by at least k out of n sensors. Our results are important in predicting the degree of coverage a sensor network may provide and in determining related parameters (sensory range, number of sensors, etc.) for a desired level of coverage. We demonstrate the utility of our results by presenting a node scheduling scheme that conserves energy while retaining network coverage. Additional simulation results have confirmed the accuracy of our analysis.     

Coverage by randomly deployed wireless sensor networks

One of the main applications of wireless sensor networks is to provide proper coverage of their deployment regions. A wireless sensor network k-covers its deployment region if every point in its deployment region is within the coverage ranges of at least k sensors. In this paper, we assume that the sensors are deployed as either a Poisson point process or a uniform point process in a square or disk region, and study how the probability of the k-coverage changes with the sensing radius or the number of sensors. Our results take the complicated boundary effect into account, rather than avoiding it by assuming the toroidal metric as done in the literature.     

Providing and finding k‐road‐coverage efficiently in wireless sensor networks

In this paper, we study k‐road‐coverage problems in wireless sensor networks (WSNs). Assume there is a 2‐dimensional area Ω with a given road map = (V,E) where E contains all road segments and V consists of all intersection points on Ω. The first question we study is about ‘sensor deployment’, i.e., how to deploy a minimum number of sensor nodes on Ω such that each path (each road segment) on is k‐covered when all sensor nodes have the same sensing range. When sensors can only be deployed in a set of discrete locations, we propose an efficient method with the approximation ratio 6 + ϵ for the special case where k = 1 and O(k) generally. If sensors can be deployed in arbitrary locations, we propose an efficient method with the approximation ratio 24 + ϵ when k = 1 and O(k) generally. The second question we study is about ‘path query’, i.e., how to find the k‐covered path or k‐support path connecting any given source/destination pair of points on the road map . Basically, given any source/destination pair of points S and D, we present two algorithms which can efficiently find a k‐covered path connecting S and D and a k‐supported path connecting S and D, respectively. Copyright © 2010 John Wiley & Sons, Ltd.     

An Integrated Approach to Sensor Role Selection

Many sensor network applications require consistent coverage of the region in which they are deployed over the course of the network lifetime. However, because sensor networks may be deployed randomly, node distribution and data redundancy in some regions of the network may be lower than in others. The sensors in the sparsest regions should be considered more critical to the sensor network application since their removal would likely result in unmonitored regions in the environment. For this reason, sensors in the more densely deployed regions should be considered more favorable as candidates to route the traffic of other nodes in the network. In this work, we propose several coverage-aware routing costs that allow traffic to be routed around the sparsely deployed regions so that the coverage of the environment can remain high for a long lifetime. We also propose an integrated route discovery and sensor selection protocol called DAPR that further lengthens network lifetime by jointly selecting routers and active sensors, again with the goal of minimizing the use of sensors in sparsely covered areas. Simulation results show the effectiveness of our approach in extending network lifetime nearly to the extent that can be reached using a centralized approach based on global network knowledge.     

Adaptive cost efficient deployment strategy for homogeneous wireless camera sensors

Availability of low cost low power camera sensors is likely to make possible applications that may otherwise have been infeasible. In this paper we investigate a cost efficient camera sensor deployment strategy based on random deployment of homogeneous sensors to monitor and/or surveillance a region of interest. We assume that there are costs associated with the sensors as well as with the deployments and our goal is to minimize the total cost while satisfying the desired coverage requirement. We consider two cases which assume the sensing field is obstacle free or with obstacles, and we develop analytical methods to derive the expected coverage of a single sensor as well as the joint coverage for a given number of homogenous camera sensors. Following this we propose an adaptive sensor deployment strategy, which deploys different number of sensors in each iteration, based on our analytical method. We then evaluate the expected cost of our deployment strategy by deriving expressions for the number of deployments and the number of sensors deployed during each deployment as a function of the probability distributions of joint coverage by sensors. We carry out simulation studies to validate the analytical results. Simulation studies are also used to demonstrate that our deployment strategy leads to near optimal values of sensors and deployments and hence achieves the overall low cost.     

Enhanced algorithms for deploying the minimum sensors to construct a wireless sensor network having full coverage of critical square grids

With the rapid technological development of sensors, many applications have been designed to use wireless sensor networks to monitor a certain area and provide quality-of-service guarantees. Therefore, the coverage problem had an important issue for constructing wireless sensor networks. Recently, a coverage problem of constructing a minimum size wireless sensor network to fully cover critical squares in a sensor field, termed CRITICAL-SQUARE-GRID COVERAGE, has received much attention. CRITICAL-SQUARE-GRID COVERAGE is shown to be NP-Complete, and an approximation algorithm, termed Steiner-tree-based critical grid covering algorithm (STBCGCA), is proposed accordingly. In STBCGCA, a sensor is selected to cover critical squares only if at least one of the critical squares is fully covered by the sensor. However, a critical square grid can be cooperatively covered by two or more sensors; that is, one sensor covers one part of the critical square, and the other sensors cover the other part of the critical square. This motivates us to propose two efficient algorithms based on STBCGCA, termed critical-grid-partitioned (CGP-STBCGCA) and reference-point-covered (RPC-STBCGCA), that select sensors that can cooperatively cover critical squares in an attempt to minimize the size of the wireless sensor network. The theoretical analysis shows that sensors deployed by CGP-STBCGCA and RPC-STBCGCA can form a connected wireless sensor network that fully covers all critical grids. In addition, a performance guarantee for CGP-STBCGCA is provided. Simulation results show that the ratio of the average number of deployed sensors in STBCGCA to that in CGP-STBCGCA and RPC-STBCGCA in about 90 % of the cases was between 1.08 and 2.52 for CRITICAL-SQUARE-GRID COVERAGE.     

Chain-based barrier coverage in WSNs: toward identifying and repairing weak zones

Barrier coverage constructs a sensing barrier for detecting intruders crossing a belt region. Recent studies mostly focus on efficient algorithms to guarantee barrier coverage, with little consideration on the collaboration between individual nodes. Observing that in many situations, sensors naturally fall into several clusters (or components), for example when the sensors are deployed uniformly at random with a relatively low density, or when random sensors go down as a result of energy exhaustion, we propose to use chain as a basic scheduling unit for sensing and communication. A chain is a set of sensors whose sensing areas overlap with each other, and it can be extracted from a cluster. We present a distributed algorithm, named BARRIER, to provide barrier coverage with a low communication overhead for the wireless sensor networks (WSNs). The algorithm is able to detect weak zones that are often found in an initial deployment of a WSN, and repair them by adding an appropriate number of sensors. Theoretic analysis and simulations show that, compared with a representative previous algorithm, BARRIER significantly reduces the communication overhead and reparation cost in terms of number of sensors.     

一种改进的虚拟力重定位覆盖增强算法

在移动无线传感网络(MWSN)的部署问题中最关键的是如何提供最大的区域覆盖范围。针对现有的覆盖控制算法存在覆盖率不理想、部署效率低、能耗过高的问题,该文提出了一种高效部署策略。第1阶段利用Voronoi图获得整个网络的覆盖孔,检测Voronoi多边形内的未覆盖区域,并提供虚拟力驱动传感器移动,同时采用动态调整策略改变移动步长,从而减少能量损耗;第2阶段提出一种检测机制,利用Delaunay三角网检测传感器之间的局部覆盖孔并进行修复。仿真结果表明,该算法在提高网络覆盖率的同时加快了收敛速度,为部署移动无线传感网络提供了新的解决思路。     

Extremal properties of three-dimensional sensor networks with applications

We analyze various critical transmitting/sensing ranges for connectivity and coverage in three-dimensional sensor networks. As in other large-scale complex systems, many global parameters of sensor networks undergo phase transitions. For a given property of the network, there is a critical threshold, corresponding to the minimum amount of the communication effort or power expenditure by individual nodes, above (respectively, below) which the property exists with high (respectively, a low) probability. For sensor networks, properties of interest include simple and multiple degrees of connectivity/coverage. First, we investigate the network topology according to the region of deployment, the number of deployed sensors, and their transmitting/sensing ranges. More specifically, we consider the following problems: assume that n nodes, each capable of sensing events within a radius of r, are randomly and uniformly distributed in a 3-dimensional region R of volume V, how large must the sensing range R/sub SENSE/ be to ensure a given degree of coverage of the region to monitor? For a given transmission range R/sub TRANS/, what is the minimum (respectively, maximum) degree of the network? What is then the typical hop diameter of the underlying network? Next, we show how these results affect algorithmic aspects of the network by designing specific distributed protocols for sensor networks.     

Deployment of a mobile wireless sensor network with k-coverage constraint: a cellular learning automata approach

Deployment of a wireless sensor network is a challenging problem, especially when the environment of the network does not allow either of the random deployment or the exact placement of sensor nodes. If sensor nodes are mobile, then one approach to overcome this problem is to first deploy sensor nodes randomly in some initial region within the area of the network, and then let the sensor nodes to move around and cooperatively and gradually increase the covered section of the area. Recently, a cellular learning automata-based deployment strategy, called CLA-DS, is introduced in literature which follows this approach and is robust against inaccuracies which may occur in the measurements of sensor positions or in the movements of sensor nodes. Despite its advantages, this deployment strategy covers every point within the area of the network with only one sensor node, which is not enough for applications with k-coverage requirement. In this paper, we extend CLA-DS so that it can address the k-coverage requirement. This extension, referred to as CLA-EDS, is also able to address k-coverage requirement with different values of k in different regions of the network area. Experimental results have shown that the proposed deployment strategy, in addition to the advantages it inherits from CLA-DS, outperforms existing algorithms such as DSSA, IDCA, and DSLE in covering the network area, especially when required degree of coverage differs in different regions of the network.     

Connectivity maintenance and coverage preservation in wireless sensor networks

In wireless sensor networks, one of the main design challenges is to save severely constrained energy resources and obtain long system lifetime. Low cost of sensors enables us to randomly deploy a large number of sensor nodes. Thus, a potential approach to solve lifetime problem arises. That is to let sensors work alternatively by identifying redundant nodes in high-density networks and assigning them an off-duty operation mode that has lower energy consumption than the normal on-duty mode. In a single wireless sensor network, sensors are performing two operations: sensing and communication. Therefore, there might exist two kinds of redundancy in the network. Most of the previous work addressed only one kind of redundancy: sensing or communication alone. Wang et al. [Intergrated Coverage and Connectivity Configuration in Wireless Sensor Networks, in: Proceedings of the First ACM Conference on Embedded Networked Sensor Systems (SenSys 2003), Los Angeles, November 2003] and Zhang and Hou [Maintaining Sensing Coverage and Connectivity in Large Sensor Networks. Technical report UIUCDCS-R-2003-2351, June 2003] first discussed how to combine consideration of coverage and connectivity maintenance in a single activity scheduling. They provided a sufficient condition for safe scheduling integration in those fully covered networks. However, random node deployment often makes initial sensing holes inside the deployed area inevitable even in an extremely high-density network. Therefore, in this paper, we enhance their work to support general wireless sensor networks by proving another conclusion: “the communication range is twice of the sensing range” is the sufficient condition and the tight lower bound to ensure that complete coverage preservation implies connectivity among active nodes if the original network topology (consisting of all the deployed nodes) is connected. Also, we extend the result to k-degree network connectivity and k-degree coverage preservation.     

Scheduling sensor activity for information coverage of discrete targets in sensor networks

In this paper, we study the problem of scheduling sensor activity to cover a set of targets with known locations such that all targets can be monitored all the time and the network can operate as long as possible. A solution to this scheduling problem is to partition all sensors into some sensor covers such that each cover can monitor all targets and the covers are activated sequentially. In this paper, we propose to provide information coverage instead of the conventional sensing disk coverage for target. The notion of information coverage is based on estimation theory to exploit the collaborative nature of geographically distributed sensors. Due to the use of information coverage, a target that is not within the sensing disk of any single sensor can still be considered to be monitored (information covered) by the cooperation of more than one sensor. This change of the problem settings complicates the solutions compared to that by using a disk coverage model. We first define the target information coverage (TIC) problem and prove its NP‐completeness. We then propose a heuristic to approximately solve our problem. Simulation results show that our heuristic is better than an existing algorithm and is close to the upper bound when only the sensing disk coverage model is used. Furthermore, simulation results also show that the network lifetime can be significantly improved by using the notion of information coverage compared with that by using the conventional definition of sensing disk coverage. Copyright © 2008 John Wiley & Sons, Ltd.     

Multi-objective Binary Reinforced Cuckoo Search Algorithm for Solving Connected Coverage target based WSN with Critical Targets

In the stream of WSN, covering the targets using sensors and communication among the sensors to forward the data packets is a prime challenge due to the sparse target locations. Dedicated sensors lead more installation cost and significant amount of maintenance needs to be charged. Coverage of multiple targets by few sensors leads to network failure in case if any sensor runs out of power. Targets in sparse region also should be considered into account while sensing the environment. Hence in this paper, an effective multi-objective connected coverage target based WSN algorithm is proposed namely Multi-Objective Binary Cuckoo Search algorithm. The proposed model also handles the critical targets in the given sensing region. The algorithms hold the potentiality to handle minimized sensor deployment, maximized coverage and connectivity cost simultaneously. The proposed model is compared with the state of art algorithms to prove its significance. Two dedicated simulation region is developed in a large scale to examine the efficiency of the proposed algorithm. The results shows the significance of the proposed model over existing algorithms.