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.     

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.     

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.     

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.     

Optimal 3-Coverage with Minimum Separation Requirements for Ubiquitous Computing Environments

Sensors have been increasingly used for many ubiquitous computing applications such as asset location monitoring, visual surveillance, and human motion tracking. In such applications, it is important to place sensors such that every point of the target area can be sensed by more than one sensor. Especially, many practical applications require 3-coverage for triangulation, 3D hull building, and etc. Also, in order to extract meaningful information from the data sensed by multiple sensors, those sensors need to be placed not too close to each other—minimum separation requirement. To address the 3-coverage problem with the minimum separation requirement, our recent work  (Kim et al. 2008) proposes two heuristic methods, so called, overlaying method and TRE-based method, which complement each other depending on the minimum separation requirement. For these two methods, we also provide mathematical analysis that can clearly guide us when to use the TRE-based method and when to use the overlaying method and also how many sensors are required. To make it self-contained, in this paper, we first revisit the two heuristic methods. Then, as an extension, we present an ILP-based optimal solution targeting for grid coverage. With this ILP-based optimal solution, we investigate how much close the two heuristic methods are to the optimal solution. Finally, this paper discusses the impacts of the proposed methods on real-deployed systems using two example sensor systems. To the best of our knowledge, this is the first work that systematically addresses the 3-coverage problem with the minimum separation requirement.     

Potential position node placement approach via oppositional gravitational search for fulfill coverage and connectivity in target based wireless sensor networks

Wireless Sensor Network (WSN) has appeared as a powerful technological platform with tremendous and novel applications. Now-a-days, monitoring and target tracking are the most major application in WSNs. In target based WSN, coverage and connectivity are the two most important issues for definite data forwarding from every target to a remote base station. An NP entire issue is to find least number of potential or possible locations to set sensor nodes gratifying both coverage and connectivity from a given a group of target points. In this article, we propose an Oppositional Gravitational Search algorithm (OGSA) based approach to solve this problem. This approach helps that the sensor nodes are prone to failure, the proposed system provides l-coverage to all targets and n-connectivity to each sensor node. This OGSA based system is presented with agent representation, derivation of efficient fitness function along with the usual Gravitational Search algorithm operators. The approach is simulated broadly with various scenarios of Wireless Sensor Network. The experimentation results are compared with some relevant existing algorithms to demonstrate the efficiency of the proposed approach.     

Barrier coverage with wireless sensors

When a sensor network is deployed to detect objects penetrating a protected region, it is not necessary to have every point in the deployment region covered by a sensor. It is enough if the penetrating objects are detected at some point in their trajectory. If a sensor network guarantees that every penetrating object will be detected by at least k distinct sensors before it crosses the barrier of wireless sensors, we say the network provides k-barrier coverage. In this paper, we develop theoretical foundations for k-barrier coverage. We propose efficient algorithms using which one can quickly determine, after deploying the sensors, whether the deployment region is k-barrier covered. Next, we establish the optimal deployment pattern to achieve k-barrier coverage when deploying sensors deterministically. Finally, we consider barrier coverage with high probability when sensors are deployed randomly. The major challenge, when dealing with probabilistic barrier coverage, is to derive critical conditions using which one can compute the minimum number of sensors needed to ensure barrier coverage with high probability. Deriving critical conditions for k-barrier coverage is, however, still an open problem. We derive critical conditions for a weaker notion of barrier coverage, called weak k-barrier coverage.     

Flow-balanced routing for multi-hop clustered wireless sensor networks

Power efficiency and coverage preservation are two important performance metrics for a wireless sensor network. However, there is scarcely any protocol to consider them at the same time. In this paper, we propose a flow-balanced routing (FBR) protocol for multi-hop clustered wireless sensor networks that attempts to achieve both power efficiency and coverage preservation. The proposed protocol consists of four algorithms, one each for network clustering, multi-hop backbone construction, flow-balanced transmission, and rerouting. The proposed clustering algorithm groups several sensors into one cluster on the basis of overlapping degrees of sensors. The backbone construction algorithm constructs a novel multi-level backbone, which is not necessarily a tree, using the cluster heads and the sink. Furthermore, the flow-balanced routing algorithm assigns the transferred data over multiple paths from the sensors to the sink in order to equalize the power consumption of sensors. Lastly, the rerouting algorithm reconstructs the network topology only in a place where a head drops out from the backbone due to the head running out of its energy. Two metrics called the network lifetime and the coverage lifetime are used to evaluate the performance of FBR protocol in comparison with previous ones. The simulation results show that FBR yields both much longer lifetime and better coverage preservation than previous protocols. For example, FBR yields more than twice network lifetime and better coverage preservation than a previous efficient protocol, called the coverage-preserving clustering protocol (CPCP) [18], when the first sensor dies and the network coverage is kept at 100%, respectively.     

Improved approximation algorithms for connected sensor cover

Wireless sensor networks have recently posed many new system building challenges. One of the main problems is energy conservation since most of the sensors are devices with limited battery life and it is infeasible to replenish energy via replacing batteries. An effective approach for energy conservation is scheduling sleep intervals for some sensors, while the remaining sensors stay active providing continuous service. In this paper we consider the problem of selecting a set of active sensors of minimum cardinality so that sensing coverage and network connectivity are maintained. We show that the greedy algorithm that provides complete coverage has an approximation factor no better than Ω(log n), where n is the number of sensor nodes. Then we present algorithms that provide approximate coverage while the number of nodes selected is a constant factor far from the optimal solution. Finally, we show how to connect a set of sensors that already provides coverage.     

On coverage issues in directional sensor networks: A survey

The coverage optimization problem has been examined thoroughly for omni-directional sensor networks in the past decades. However, the coverage problem in directional sensor networks (DSN) has newly taken attraction, especially with the increasing number of wireless multimedia sensor network (WMSN) applications. Directional sensor nodes equipped with ultrasound, infrared, and video sensors differ from traditional omni-directional sensor nodes with their unique characteristics, such as angle of view, working direction, and line of sight (LoS) properties. Therefore, DSN applications require specific solutions and techniques for coverage enhancement. In this survey article, we mainly aim at categorizing available coverage optimization solutions and survey their problem definitions, assumptions, contributions, complexities and performance results. We categorize available studies about coverage enhancement into four categories. Target-based coverage enhancement, area-based coverage enhancement, coverage enhancement with guaranteed connectivity, and network lifetime prolonging. We define sensing models, design issues and challenges for directional sensor networks and describe their (dis)similarities to omni-directional sensor networks. We also give some information on the physical capabilities of directional sensors available on the market. Moreover, we specify the (dis)advantages of motility and mobility in terms of the coverage and network lifetime of DSNs.     

Energy-efficient top-k query evaluation and maintenance in wireless sensor networks

Top-k query in a wireless sensor network is to identify k sensors with the highest sensor readings. Since sensors usually are powered by energy-limited batteries, a fundamental problem associated with top-k query evaluation in such a network is to maximize network lifetime, which poses great challenges due to the unique characteristics of sensor networks. In this paper, we first propose a novel filter-based algorithm for top-k query evaluation, which is able to filter out a fractional amount of data from network-wide transmission. We then develop an online algorithm for answering time-dependent top-k queries with different values of k through the dynamic maintenance of a materialized view that consists of historical top-k results. We finally conduct extensive experiments by simulations to evaluate the performance of the proposed algorithms using real sensing data sets. Experimental results show that the proposed algorithms outperform a well known existing algorithm significantly, and the network lifetime delivered by the proposed optimal quantile algorithm is at least 142 % times longer than that by an existing algorithm.     

Coverage and Connectivity-Based 3D Wireless Sensor Deployment Optimization

The wireless sensor network technology of Internet of Things (IoT) senses, collects and processes the data from its interconnected intelligent sensors to the base station. These sensors help the IoT to understand the environmental change and respond towards it. Thus sensor placement is a crucial device of IoT for efficient coverage and connectivity in the network. Many existing works focus on optimal sensor placement for two dimensional terrain but in various real-time applications sensors are often deployed over three-dimensional ambience. Therefore, this paper proposes a vertex coloring based sensor deployment algorithm for 3D terrain to determine the sensor requirement and its optimal spot and to obtain 100% target coverage. Further, the quality of the connectivity of sensors in the network is determined using Breadth first search algorithm. The results obtained from the proposed algorithm reveal that it provides efficient coverage and connectivity when compared with the existing methods.

     

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.

CASMOC: a novel complex alliance strategy with multi-objective optimization of coverage in wireless sensor networks

Coverage is a significant performance indicator of wireless sensor networks. Data redundancy in k-coverage raises a set of issues including network congestion, coverage reduction, energy inefficiency, among others. To address these issues, this paper proposes a novel algorithm called complex alliance strategy with multi-objective optimization of coverage (CASMOC) which could improve node coverage effectively. This paper also gives the proportional relationship of the energy conversion function between the working node and its neighbors, and applies this relationship in scheduling low energy mobile nodes, thus achieving energy balance of the whole network, and optimizing network resources. The extensive simulation results demonstrate that CASMOC could not only improve the quality of network coverage, but also mitigate rapid node energy consumption effectively, thereby extending the life cycle of the network significantly.     

Approximation algorithms for deployment of sensors for line segment coverage in wireless sensor networks

The coverage problem in wireless sensor networks deals with the problem of covering a region or parts of it with sensors. In this paper, we address the problem of covering a set of line segments with minimum number of sensors. A line segment ? is said to be 1-covered if it intersects the sensing region of at least one among the sensors distributed in a bounded rectangular region R. We assume that the sensing radius of each sensor is uniform. The problem of finding the minimum number of sensors needed to 1-cover each member in a given set of line segments in R is NP-hard. We propose two constant factor approximation algorithms and a PTAS (polynomial time approximation scheme) for the problem for 1-covering a set of axis-parallel line segments. We also show that a PTAS exists for 1-covering a set of arbitrarily oriented line segments in R where the lengths of the line segments are bounded within a constant factor of the sensing radius of each sensor. Finally, we propose a constant factor approximation algorithm for k-covering axis-parallel line segments such that sensors maintain a minimum separation among them.     

A Learning Automata-Based Solution to the Priority-Based Target Coverage Problem in Directional Sensor Networks

In recent years, directional sensor networks composed of directional sensors have attracted a great deal of attention due to their extensive applications. The main difficulties associated with directional sensors are their limited battery power and restricted sensing angle. Moreover, each target may have a different coverage quality requirement that can make the problem even more complicated. Therefore, satisfying the coverage quality requirement of all the targets in a specific area and maximizing the network lifetime, known as priority-based target coverage problem, has remained a challenge. As sensors are often densely deployed, organizing the sensor directions into several cover sets and then activating these cover sets successively is a promising solution to this problem. In this paper, we propose a learning automata-based algorithm to organize the directional sensors into several cover sets in such a way that each cover set can satisfy coverage quality requirement of all the targets. In order to verify the performance of the proposed algorithm, several simulations were conducted. The obtained results showed that the proposed algorithm was successful in extending the network lifetime.     

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.     

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.     

Cluster head election techniques for coverage preservation in wireless sensor networks

Coverage preservation is one of the basic QoS requirements of wireless sensor networks, yet this problem has not been sufficiently explored in the context of cluster-based sensor networks. Specifically, it is not known how to select the best candidates for the cluster head roles in applications that require complete coverage of the monitored area over long periods of time. In this paper, we take a unique look at the cluster head election problem, specifically concentrating on applications where the maintenance of full network coverage is the main requirement. Our approach for cluster-based network organization is based on a set of coverage-aware cost metrics that favor nodes deployed in densely populated network areas as better candidates for cluster head nodes, active sensor nodes and routers. Compared with using traditional energy-based selection methods, using coverage-aware selection of cluster head nodes, active sensor nodes and routers in a clustered sensor network increases the time during which full coverage of the monitored area can be maintained anywhere from 25% to 4.5×, depending on the application scenario.     

Fault-tolerant monitor placement for out-of-band wireless sensor network monitoring

Monitoring a sensor network to quickly detect faults is important for maintaining the health of the network. Out-of-band monitoring, i.e., deploying dedicated monitors and transmitting monitoring traffic using a separate channel, does not require instrumenting sensor nodes, and hence is flexible (can be added on top of any application) and energy conserving (not consuming resources of the sensor nodes). In this paper, we study fault-tolerant out-of-band monitoring for wireless sensor networks. Our goal is to place a minimum number of monitors in a sensor network so that all sensor nodes are monitored by k distinct monitors, and each monitor serves no more than w sensor nodes. We prove that this problem is NP-hard. For small-scale network, we formulate the problem as an Integer Linear Programming (ILP) problem, and obtain the optimal solution. For large-scale network, the ILP is not applicable, and we propose two algorithms to solve it. The first one is a ln(kn) approximation algorithm, where n is the number of sensor nodes. The second is a simple heuristic scheme that has much shorter running time. We evaluate our algorithms using extensive simulation. In small-scale networks, the latter two algorithms provide results close to the optimal solution from the ILP for relatively dense networks. In large-scale networks, the performance of these two algorithms are similar, and for relatively dense networks, the number of monitors required by both algorithms is close to a lower bound.