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.     

WSN Deployment and Localization Using a Mobile Agent

To address the problem the sensors were typically deployed in fixed positions, but the robots can be used to calibrate, deploy and maintain the surrounding wireless sensor network (WSN) in disaster relief applications, a novel framework was proposed to obtain a wide coverage of the unknown environment by the sensors, which can help the robot during the disaster recovery activities, for the concurrent deployment and localization of a WSN by means of a mobile robot. During the mission, the robot explored an unknown environment, and was equipped with both proprioceptive sensors, range finders and wireless antennas. Moreover, the robot carried a set of nodes, and it can deploy them while exploring the unknown environment. Variou experimental results showd the proposed algorithm can outperform trilateration method in unknown environment exploration and network coverage problems.     

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.     

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.     

Static wireless sensor networks deployment using an improved binary PSO

A major issue in designing wireless sensor networks is the deployment problem. Indeed, many performances of the sensor network, such as coverage, are determined by the number and locations of deployed sensors. This paper reviews existing deterministic deployment strategies and devises a modified binary particle swarm optimization, which adopts a new position updating procedure for a faster convergence and exploits the abandonment concept to avoid some drawbacks such as premature convergence. The devised approach combines, in a meaningful way, the characteristics of the binary particle swarm optimization with the wireless sensor networks deployment requirements in order to devise a lightweight and efficient sensor placement algorithm. The effectiveness and efficiency of the proposed approach are evaluated through extensive simulations. The obtained results show that the proposed algorithm outperforms the state‐of‐the‐art approaches, especially in the case of preferential coverage. Copyright © 2015 John Wiley & Sons, Ltd.     

P&;P: an asynchronous and distributed protocol for mobile sensor deployment

The use of wireless mobile sensors is of great relevance for a number of strategic applications devoted to monitoring critical areas where sensors can not be deployed manually. Mobile sensors can adapt their position on the basis of a local evaluation of coverage, thus permitting an autonomous deployment. Several algorithms have been proposed to deploy mobile sensors over an area of interest. The applicability of these approaches largely depends on a proper formalization of rigorous rules to coordinate sensor movements, solve local conflicts and manage possible failures of communications and devices. In this paper we introduce P&P, a communication protocol that permits a correct and efficient coordination of sensor movements in agreement with the Push & Pull algorithm. We deeply investigate and solve the problems that may occur when coordinating asynchronous local decisions in the presence of an unreliable transmission medium and possibly faulty devices such as in the typical working scenario of mobile sensor networks. Simulation results show the performance of our protocol under a range of operative settings, including conflict situations and irregularly shaped target areas. Furthermore, a performance comparison between the P&P protocol and one of the best solutions based on the virtual force approach, shows the superiority of our proposal in terms of deployment time, message exchanges and energy consumption.     

Exploiting Reactive Mobility for Collaborative Target Detection in Wireless Sensor Networks

Recent years have witnessed the deployments of wireless sensor networks in a class of mission-critical applications such as object detection and tracking. These applications often impose stringent Quality-of-Service requirements including high detection probability, low false alarm rate, and bounded detection delay. Although a dense all-static network may initially meet these Quality-of-Service requirements, it does not adapt to unpredictable dynamics in network conditions (e.g., coverage holes caused by death of nodes) or physical environments (e.g., changed spatial distribution of events). This paper exploits reactive mobility to improve the target detection performance of wireless sensor networks. In our approach, mobile sensors collaborate with static sensors and move reactively to achieve the required detection performance. Specifically, mobile sensors initially remain stationary and are directed to move toward a possible target only when a detection consensus is reached by a group of sensors. The accuracy of final detection result is then improved as the measurements of mobile sensors have higher Signal-to-Noise Ratios after the movement. We develop a sensor movement scheduling algorithm that achieves near-optimal system detection performance under a given detection delay bound. The effectiveness of our approach is validated by extensive simulations using the real data traces collected by 23 sensor nodes.     

Impact of Interference on Coverage in Wireless Sensor Networks

The quality of surveillance is dependent on the sensing coverage of a wireless sensor network. In the present paper, we examine how interference affects the coverage of a wireless sensor network. The coverage fraction and required number of sensors for randomly deployed and well-planned deployed wireless sensor networks in the presence of interferers are computed. The required number of sensors to achieve higher level of coverage increases drastically for randomly distributed sensor nodes where the interference effect is high. In the case of well-planned distributed sensor network, required sensors increases linearly as interference effects become more pronounced. Algorithms for computing the required number of sensors to obtain the desired level of coverage in the presence of non-uniform interference is presented. The simulation results suggest that the coverage per subregion and coverage per sensor approaches towards, the improvement achieved is constant. The sensor saving ratio is independent of the level of the desired coverage provided the coverage per subregion is larger than or equal to the coverage per sensor.     

A distributed self-deployment algorithm for the coverage of mobile wireless sensor networks

This letter addresses a coverage problem through the use of a self-deployed mobile wireless sensor network. We propose a distributed motion coordination algorithm for the mobile sensors to autonomously form a sensor barrier between two given landmarks to achieve the barrier coverage. The algorithm is developed based on some simple rules that are computationally efficient and require less communication overhead.     

An Energy Efficient Barrier Coverage Algorithm for Wireless Sensor Networks

Intrusion detection is one of the most important applications of wireless sensor networks. When mobile objects are entering into the boundary of a sensor field or are moving cross the sensor field, they should be detected by the scattered sensor nodes before they pierce through the field of sensor (barrier coverage). In this paper, we propose an energy efficient scheduling method based on learning automata, in which each node is equipped with a learning automaton, which helps the node to select best node to guarantee barrier coverage, at any given time. To apply our method, we used coverage graph of deployed networks and learning automata of each node operates based on nodes that located in adjacency of current node. Our algorithm tries to select minimum number of required nodes to monitor barriers in deployed network. To investigate the efficiency of the proposed barrier coverage algorithm several computer simulation experiments are conducted. Numerical results show the superiority of the proposed method over the existing methods in term of the network lifetime and our proposed algorithm can operate very close to optimal method.     

Three-dimensional and two-dimensional deployment analysis for underwater acoustic sensor networks

Underwater sensor networks find applications in oceanographic data collection, pollution monitoring, offshore exploration, disaster prevention, assisted navigation, and tactical surveillance. In this paper, deployment strategies for two-dimensional and three-dimensional communication architectures for underwater acoustic sensor networks are proposed, and a mathematical deployment analysis for both architectures is provided. The objective is to determine the minimum number of sensors to be deployed to achieve optimal sensing and communication coverage, which are dictated by application requirements; provide guidelines on how to choose the optimal deployment surface area, given a target body of water; study the robustness of the sensor network to node failures, and provide an estimate of the number of redundant sensor nodes to be deployed to compensate for potential failures.     

General Network Lifetime and Cost Models for Evaluating Sensor Network Deployment Strategies

In multihop wireless sensor networks that are often characterized by many-to-one (convergecast) traffic patterns, problems related to energy imbalance among sensors often appear. Sensors closer to a data sink are usually required to forward a large amount of traffic for sensors farther from the data sink. Therefore, these sensors tend to die early, leaving areas of the network completely unmonitored and reducing the functional network lifetime. In our study, we explore possible sensor network deployment strategies that maximize sensor network lifetime by mitigating the problem of the hot spot around the data sink. Strategies such as variable-range transmission power control with optimal traffic distribution, mobile-data-sink deployment, multiple-data-sink deployment, nonuniform initial energy assignment, and intelligent sensor/relay deployment are investigated. We suggest a general model to analyze and evaluate these strategies. In this model, we not only discover how to maximize the network lifetime given certain network constraints but also consider the factor of extra costs involved in more complex deployment strategies. This paper presents a comprehensive analysis on the maximum achievable sensor network lifetime for different deployment strategies, and it also provides practical cost-efficient sensor network deployment guidelines.     

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.     

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.     

无线传感器网络中基于区域通信覆盖的节点定位投放算法

针对无线传感器网络中传感器节点投放分布对投放区域有效通信信号覆盖的影响,该文提出了一种基于通信覆盖的分布式投放概率覆盖(DDCP)算法。在保证投放精度的前提下,该算法根据传感器节点在投放区域中位置的不确定性以及信号衰减特性,建立信号覆盖模型,并通过概率优化获取传感器节点的最佳投放位置和投放数目。这样改善了区域通信覆盖,同时提高了投放效率和节省网络资源。通过仿真比较了在不同定位投放方法下的各相关性数据,验证了该算法实现高效投放的优越性和正确性。     

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.     

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.

     

Push &; Pull: autonomous deployment of mobile sensors for a complete coverage

Mobile sensor networks are important for several strategic applications devoted to monitoring critical areas. In such hostile scenarios, sensors cannot be deployed manually and are either sent from a safe location or dropped from an aircraft. Mobile devices permit a dynamic deployment reconfiguration that improves the coverage in terms of completeness and uniformity. In this paper we propose a distributed algorithm for the autonomous deployment of mobile sensors called Push & Pull. According to our proposal, movement decisions are made by each sensor on the basis of locally available information and do not require any prior knowledge of the operating conditions or any manual tuning of key parameters. We formally prove that, when a sufficient number of sensors are available, our approach guarantees a complete and uniform coverage. Furthermore, we demonstrate that the algorithm execution always terminates preventing movement oscillations. Numerous simulations show that our algorithm reaches a complete coverage within reasonable time with moderate energy consumption, even when the target area has irregular shapes. Performance comparisons between Push & Pull and one of the most acknowledged algorithms show how the former one can efficiently reach a more uniform and complete coverage under a wide range of working scenarios.     

A pragmatic approach to area coverage in hybrid wireless sensor networks

Success of Wireless Sensor Networks (WSN) largely depends on whether the deployed network can provide desired area coverage with acceptable network lifetime. This paper seeks to address the problem of determining the current coverage achieved by the non‐deterministic deployment of static sensor nodes and subsequently enhancing the coverage using mobile sensors. We identify three key elements that are critical for ensuring effective area coverage in Hybrid WSN: (i) determining the boundary of the target region and evaluating the area coverage (ii) locating coverage holes and maneuvering mobile nodes to fill these voids, and (iii) maintaining the desired coverage over the entire operational lifetime of the network. We propose a comprehensive solution that addresses all of the aforementioned aspects of the area coverage, called MAPC (mobility assisted probabilistic coverage). MAPC is a distributed protocol that operates in three distinct phases. The first phase identifies the boundary nodes using the geometric right‐hand rule. Next, the static nodes calculate the area coverage and identify coverage holes using a novel probabilistic coverage algorithm (PCA). PCA incorporates realistic sensing coverage model for range‐based sensors. The second phase of MAPC is responsible for navigating the mobile nodes to plug the coverage holes. We propose a set of coverage and energy‐aware variants of the basic virtual force algorithm (VFA). Finally, the third phase addresses the problem of coverage loss due to faulty and energy depleted nodes. We formulate this problem as an Integer Linear Program (ILP) and propose practical heuristic solutions that achieve similar performance as that of the optimal ILP solution. A guiding principle in our design process has been to ensure that the MAPC can be readily implemented in real‐world applications. We implemented the boundary detection and PCA algorithm (i.e., Phase I) of the MAPC protocol on off‐the‐shelf sensor nodes and results show that the MAPC can successfully identify boundary nodes and accurately determine the area coverage in the presence of real radio irregularities observed during the experiments. Extensive simulations were carried out to evaluate the complete MAPC protocol and the results demonstrate that MAPC can enhance and maintain the area coverage, while reducing the total energy consumption by up to 70% as compared with the basic VFA. Copyright © 2010 John Wiley & Sons, Ltd.     

Leveraging data fusion to improve barrier coverage in wireless sensor networks

Intruder detection and border surveillance are amongst the most promising applications of wireless sensor networks. Barrier coverage formulates these problems as constructing barriers in a long-thin region to detect intruders that cross the region. Existing studies on this topic are not only based on simplistic binary sensing model but also neglect the collaboration employed in many systems. In this paper, we propose a solution which exploits the collaboration of sensors to improve the performance of barrier coverage under probabilistic sensing model. First, the network width requirement, the sensor density and the number of barriers are derived under data fusion model when sensors are randomly distributed. Then, we present an efficient algorithm to construct barriers with a small number of sensors. The theoretical comparison shows that our solution can greatly improve barrier coverage via collaboration of sensors. We also conduct extensive simulations to demonstrate the effectiveness of our solution.