In this paper, we study optimal radar deployment for intrusion detection, with focus on network coverage. In contrast to the disk-based sensing model in a traditional sensor network, the detection range of a bistatic radar depends on the locations of both the radar transmitter and radar receiver, and is characterized by Cassini ovals. Furthermore, in a network with multiple radar transmitters and receivers, since any pair of transmitter and receiver can potentially form a bistatic radar, the detection ranges of different bistatic radars are coupled and the corresponding network coverage is intimately related to the locations of all transmitters and receivers, making the optimal deployment design highly non-trivial. Clearly, the detectability of an intruder depends on the highest SNR received by all possible bistatic radars. We focus on the worst-case intrusion detectability, i.e., the minimum possible detectability along all possible intrusion paths. Although it is plausible to deploy radars on a shortest line segment across the field, it is not always optimal in general, which we illustrate via counter-examples. We then present a sufficient condition on the field geometry for the optimality of shortest line deployment to hold. Further, we quantify the local structure of detectability corresponding to a given deployment order and spacings of radar transmitters and receivers, building on which we characterize the optimal deployment to maximize the worst-case intrusion detectability. Our results show that the optimal deployment locations exhibit a balanced structure. We also develop a polynomial-time approximation algorithm for characterizing the worse-case intrusion path for any given locations of radars under random deployment.
Worst-case coverage has been first studied in @cite_3 for a traditional sensor network. Polynomial-time algorithms are devised to find maximum breach and maximum support paths between two locations. An efficient algorithm is proposed in @cite_2 to solve the best-coverage problem raised in @cite_3 . In @cite_15 , efficient algorithms are developed to find the minimum exposure path in sensor networks. Localized algorithms are designed in @cite_7 to solve the minimum exposure path problem. A new coverage measure that captures both the best and worst-case coverage is studied in @cite_11 . The deployment problem to improve the maximal breach path is considered by @cite_5 @cite_0 . Barrier coverage is an intimately related problem to worst-case coverage. The concept of weak and strong barrier coverage has been introduced in @cite_8 , where critical condition of weak barrier coverage is obtained for random deployment. The critical condition of strong barrier coverage is derived in @cite_13 using percolation theory. An effective metric of barrier coverage quality is proposed in @cite_9 . @cite_10 studies constructing barrier by sensors with limited mobility after initial deployment. A novel full-view coverage model is proposed in @cite_14 for constructing barrier in camera sensor networks.
@cite_14 @cite_7 @cite_8 @cite_10 @cite_9 @cite_3 @cite_0 @cite_2 @cite_5 @cite_15 @cite_13 @cite_11
2156174635 2011532811 2125242971 1506634844 2167477163 1960247298 1967174914 2045870157 2028589023 1591006909 2092860475 1988777116 1965274367 2301250350 2068735295 1755547434 2568372686 1530465016 2217656054 1603500658
In this paper, we propose and evaluate algorithms for solving the worst-case-coverage deployment problem in ad-hoc wireless sensor net works. The worst-case-coverage deployment problem is to deploy additional sensors in the wireless sensor field to optimize the worst-case coverage. We derive a duality theorem that reveals the close relation between the maximum breach path and the minimum Delaunay cut. The duality theorem is similar to the well-known max-flow-mm-cut theorem in the field of network optimization. The major difference lies in the fact that the object function we study in this paper is nonlinear rather than linear. Based on the duality theorem, we propose an efficient dual algorithm to solve the worst- case-coverage deployment problem. In addition, we propose a genetic algorithm for deploying a number of additional sensors simultaneously. We use analytical proofs and simulation results to justify the usage of the proposed approaches Proposing a new approach to barrier coverage in wireless sensor network.Modeling barrier coverage with stochastic edge-weighted graph.Finding an optimal solution for the network stochastic edge-weighted coverage graph.Comparing the performance of the proposed method with the greedy and optimal methods. Barrier coverage is one of the most important applications of wireless sensor networks. It is used to detect mobile objects are entering into the boundary of a sensor network field. Energy efficiency is one of the main concerns in barrier coverage for wireless sensor networks and its solution can be widely used in sensor barrier applications, such as intrusion detectors and border security. In this work, we take the energy efficiency as objectives of the study on barrier coverage. The cost in the present paper can be any performance measurement and normally is defined as any resource which is consumed by sensor barrier. In this paper, barrier coverage problem is modeled based on stochastic coverage graph first. Then, a distributed learning automata-based method is proposed to find a near optimal solution to the stochastic barrier coverage problem. The stochastic barrier coverage problem seeks to find minimum required number of sensor nodes to construct sensor barrier path. To study the performance of the proposed method, computer simulations are conducted. The simulation results show that the proposed algorithm significantly outperforms the greedy based algorithm and optimal method in terms of number of network barrier paths. We study the problem of achieving maximum barrier coverage by sensors on a barrier modeled by a line segment, by moving the minimum possible number of sensors, initially placed at arbitrary positions on the line containing the barrier. We consider several cases based on whether or not complete coverage is possible, and whether non-contiguous coverage is allowed in the case when complete coverage is impossible. When the sensors have unequal transmission ranges, we show that the problem of finding a minimum-sized subset of sensors to move in order to achieve maximum contiguous or non-contiguous coverage on a finite line segment barrier is NP-complete. In contrast, if the sensors all have the same range, we give efficient algorithms to achieve maximum contiguous as well as non-contiguous coverage. For some cases, we reduce the problem to finding a maximum-hop path of a certain minimum (maximum) weight on a related graph, and solve it using dynamic programming. Barrier coverage in visual camera sensor networks (visual barrier coverage) has important real-world applications like battlefield surveillance, environmental monitoring, and protection of government property. Cost-effective deployment, a fundamental issue of visual barrier coverage, considers how to deploy the fewest camera sensors along the barrier to detect intruders (e.g., capture faces) with desirable performance. Existing visual barrier coverage approaches like full-view coverage require numerous camera sensors for capturing intruders' faces deterministically for any trajectory and facing angle. However, intruders' trajectories and facing angles are bounded and deterministic intruder detection requires many camera sensors for rare intrusion cases. Certain practical applications can tolerate limited intrusion mis-detection given budget limitations. This paper proposes local face-view barrier coverage, a novel concept that achieves statistical barrier coverage in camera sensor networks leveraging intruders' trajectory lengths l along the barrier and head rotation angles δ. Using (l, δ) and other parameters, we derive a rigorous probability bound for intruder detection for local face-view barrier coverage via a feasible deployment pattern. Our detection probability bound and deployment pattern can guide practical camera sensor network deployments with camera sensor budgets. Extensive evaluations show that local face-view barrier coverage requires up to 50 fewer camera sensors than full-view barrier coverage. Sensor networks not only have the potential to change the way we use, interact with, and view computers, but also the way we use, interact with, and view the world around us. In order to maximize the effectiveness of sensor networks, one has to identify, examine, understand, and provide solutions for the fundamental problems related to wireless embedded sensor networks. We believe that one of such problems is to determine how well the sensor network monitors the instrumented area. These problems are usually classified as coverage problems. There already exist several methods that have been proposed to evaluate a sensor network's coverage.We start from one of such method and provide a new approach to complement it. The method of using the minimal exposure path to quantify coverage has been optimally solved using a numerical approximation approach. The minimal exposure path can be thought of as the worst-case coverage of a sensor network. Our first goal is to develop an efficient localized algorithm that enables a sensor network to determine its minimal exposure path. The theoretical highlight of this paper is the closed-form solution for minimal exposure in the presence of a single sensor. This solution is the basis for the new and significantly faster localized approximation algorithm that reduces the theoretical complexity of the previous algorithm. On the other hand, we introduce a new coverage problem - the maximal exposure path - which is in a sense the best-case coverage path for a sensor network. We prove that the maximal exposure path problem is NP-hard, and thus, we provide heuristics to generate approximate solutions.In addition, we demonstrate the effectiveness of our algorithms through several simulations. In the case of the minimal single-source minimal exposure path, we use variational calculus to determine exact solutions. For the case of maximal exposure, we use networks with varying numbers of sensors and exposure models. This paper addresses the coverage breach problem in wireless sensor networks with limited bandwidths. In wireless sensor networks, sensor nodes are powered by batteries. To make efficient use of battery energy is critical to sensor network lifetimes. When targets are redundantly covered by multiple sensors, especially in stochastically deployed sensor networks, it is possible to save battery energy by organizing sensors into mutually exclusive subsets and alternatively activating only one subset at any time. Active nodes are responsible for sensing, computing and communicating. While the coverage of each subset is an important metric for sensor organization, the size of each subset also plays an important role in sensor network performance because when active sensors periodically send data to base stations, contention for channel access must be considered. The number of available channels imposes a limit on the cardinality of each subset. Coverage breach happens when a subset of sensors cannot completely cover all the targets. To make efficient use of both energy and bandwidth with a minimum coverage breach is the goal of sensor network design. This paper presents the minimum breach problem using a mathematical model, studies the computational complexity of the problem, and provides two approximate heuristics. Effects of increasing the number of channels and increasing the number of sensors on sensor network coverage are studied through numerical simulations. Overall, the simulation results reveal that when the number of sensors increases, network lifetimes can be improved without loss of network coverage if there is no bandwidth constraint; with bandwidth constraints, network lifetimes may be improved further at the cost of coverage breach. Barrier coverage is a critical issue in wireless sensor networks for various battlefield and homeland security applications. The goal is to effectively detect intruders that attempt to penetrate the region of interest. A sensor barrier is formed by a connected sensor cluster across the entire deployed region, acting as a "trip wire" to detect any crossing intruders. In this paper we study how to efficiently improve barrier coverage using mobile sensors with limited mobility. After the initial deployment, mobile sensors can move to desired locations and connect with other sensors in order to create new barriers. However, simply moving sensors to form a large local cluster does not necessarily yield a global barrier. This global nature of barrier coverage makes it a challenging task to devise effective sensor mobility schemes. Moreover, a good sensor mobility scheme should efficiently improve barrier coverage under the constraints of available mobile sensors and their moving range. We first explore the fundamental limits of sensor mobility on barrier coverage and present a sensor mobility scheme that constructs the maximum number of barriers with minimum sensor moving distance. We then present an efficient algorithm to compute the existence of barrier coverage with sensors of limited mobility, and examine the effects of the number of mobile sensors and their moving ranges on the barrier coverage improvement. Both the analytical results and performance of the algorithms are evaluated via extensive simulations. 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. Global barrier coverage that requires much fewer sensors than full coverage, is known to be an appropriate model of coverage for movement detection applications such as intrusion detection. However, it has been proved that given a sensor deployment, sensors can not locally determine whether the deployment provides global barrier coverage, making it impossible to develop localized algorithms, thus limiting its use in practice. In this paper, we introduce the concept of local barrier coverage to address this limitation. Motivated by the observation that movements are likely to follow a shorter path in crossing a belt region, local barrier coverage guarantees the detection of all movements whose trajectory is confined to a slice of the belt region of deployment. We prove that it is possible for individual sensors to locally determine the existence of local barrier coverage, even when the region of deployment is arbitrarily curved. Although local barrier coverage does not always guarantee global barrier coverage, we show that for thin belt regions, local barrier coverage almost always provides global barrier coverage. To demonstrate that local barrier coverage can be used to design localized algorithms, we develop a novel sleep-wakeup algorithm for maximizing the network lifetime, called Localized Barrier Coverage Protocol (LBCP). We show that LBCP provides close to optimalenhancement in network lifetime, while providing global barrier coverage most of the time. It outperforms an existing algorithm called Randomized Independent Sleeping (RIS) by up to 6 times. Coverage is a central issue in the design of wireless sensor networks. There are many measures for coverage, based on what aspect of surveillance quality we wish to address. Designing a network that achieves desired standards in terms of the measure chosen is a non-trivial problem. In this paper we take the Maximal Breach Path measure and formulate the sensor-network design problem as a geometric optimisation problem. We present improved polynomial time algorithms for computing the aforesaid measure for a given sensor network. Also, as a first step toward solving the optimisation problem posed in this paper, we present a geometric transformation on a given configuration of sensors that brings the maximal breach to a “local optimal” – in the sense that the resulting breach is the best we can get keeping the topology of the starting configuration intact. We consider the k-barrier coverage problem, that is, the problem of deploying sensors on a border or perimeter to ensure that any intruder would be detected by at least k sensors. With random deployment of sensors, there is always a chance of gaps in coverage, thereby necessitating multiple rounds of deployment. In this paper, we study multi-round wireless sensor deployment on a border modeled as a line segment. We present two different classes of deployment strategies: complete and partial. In complete strategies, in every round, sensors are deployed over the entire border segment, while in partial strategies, sensors are deployed over only some part(s) of the border. First, we analyze the probability of k-coverage for any complete strategy as a function of parameters such as length of barrier to be covered, the width of the intruder, the sensing range of sensors, as well as the density of deployed sensors. Second, we propose two specific deployment strategies - Fixed-Density Complete and Fixed-Density Partial - and analyze the expected number of deployment rounds and expected total number of deployed sensors for each strategy. Next, we present a model for cost analysis of multi-round sensor deployment and calculate, for each deployment strategy, the expected total cost as a function of problem parameters and density of sensor deployment. Finally we find the optimal density of sensors in each round that minimizes the total expected cost of deployment for each deployment strategy. We validate our analysis by extensive simulation results. In this paper, we study the problem of moving @math n sensors on a line to form a barrier coverage of a specified segment of the line such that the maximum moving distance of the sensors is minimized. Previously, it was an open question whether this problem on sensors with arbitrary sensing ranges is solvable in polynomial time. We settle this open question positively by giving an @math O(n2logn) time algorithm. For the special case when all sensors have the same-size sensing range, the previously best solution takes @math O(n2) time. We present an @math O(nlogn) time algorithm for this case; further, if all sensors are initially located on the coverage segment, our algorithm takes @math O(n) time. Also, we extend our techniques to the cycle version of the problem where the barrier coverage is for a simple cycle and the sensors are allowed to move only along the cycle. For sensors with the same-size sensing range, we solve the cycle version in @math O(n) time, improving the previously best @math O(n2) time solution. Deploying wireless sensor networks to provide guaranteed barrier coverage is critical for many sensor networks applications such as intrusion detection and border surveillance. To reduce the number of sensors needed to provide guaranteed barrier coverage, we propose multi-round sensor deployment which splits sensor deployment into multiple rounds and can better deal with placement errors that often accompany sensor deployment. We conduct a comprehensive analytical study on multi-round sensor deployment and identify the tradeoff between the number of sensors deployed in each round of multi-round sensor deployment and the barrier coverage performance. Both numerical and simulation studies show that, by simply splitting sensor deployment into two rounds, guaranteed barrier coverage can be achieved with significantly less sensors comparing to single-round sensor deployment. Moreover, we propose two practical solutions for multi-round sensor deployment when the distribution of a sensor's residence point is not fully known. The effectiveness of the proposed multi-round sensor deployment strategies is demonstrated by numerical and simulation results. Barrier coverage in Wireless Sensor Networks (WSNs) is an important research issue as intruder detection is the main purpose of deploying wireless sensors over a specified monitoring region. In WSNs, excessive volume and variety of sensor data are generated, which need to be analyzed for accurate measurement of the image in terms of width and resolution. In this paper, a three layered big data analytic architecture is designed to analyze the data generated during the construction of the barrier and detection of the intruder using camera sensors. Besides, a cloud layer is designed for storing the analyzed data to study the behavior of the intruder. In order to minimize the number of camera sensors for constructing the barrier, algorithms are designed to construct the single barrier with limited node mobility and the barrier path Quality of Sensing (QoS) is maintained with a minimum number of camera sensors. Simulation results show that our algorithms can construct 100 of the barrier with fewer number of camera sensors and average data processing time can be reduced by using parallel servers even if for larger size of data. Constructing sensor barriers to detect intruders crossing a randomly-deployed sensor network is an important problem. Early results have shown how to construct sensor barriers to detect intruders moving along restricted crossing paths in rectangular areas. We present a complete solution to this problem for sensors that are distributed according to a Poisson point process. In particular, we present an efficient distributed algorithm to construct sensor barriers on long strip areas of irregular shape without any constraint on crossing paths. Our approach is as follows: We first show that in a rectangular area of width w and length l with w = Ω(log l), if the sensor density reaches a certain value, then there exist, with high probability, multiple disjoint sensor barriers across the entire length of the area such that intruders cannot cross the area undetected. On the other hand, if w = o(log l), then with high probability there is a crossing path not covered by any sensor regardless of the sensor density. We then devise, based on this result, an efficient distributed algorithm to construct multiple disjoint barriers in a large sensor network to cover a long boundary area of an irregular shape. Our algorithm approximates the area by dividing it into horizontal rectangular segments interleaved by vertical thin strips. Each segment and vertical strip independently computes the barriers in its own area. Constructing "horizontal" barriers in each segment connected by "vertical" barriers in neighboring vertical strips, we achieve continuous barrier coverage for the whole region. Our approach significantly reduces delay, communication overhead, and computation costs compared to centralized approaches. Finally, we implement our algorithm and carry out a number of experiments to demonstrate the effectiveness of constructing barrier coverage. Sensor networks are ubiquitously used for detection and tracking and as a result covering is one of the main tasks of such networks. We study the problem of maximizing the coverage lifetime of a barrier by mobile sensors with limited battery powers, where the coverage lifetime is the time until there is a breakdown in coverage due to the death of a sensor. Sensors are first deployed and then coverage commences. Energy is consumed in proportion to the distance traveled for mobility, while for coverage, energy is consumed in direct proportion to the radius of the sensor raised to a constant exponent. We study two variants which are distinguished by whether the sensing radii are given as part of the input or can be optimized, the fixed radii problem and the variable radii problem. We design parametric search algorithms for both problems for the case where the final order of the sensors is predetermined and for the case where sensors are initially located at barrier endpoints. In contrast, we show that the variable radii problem is strongly NP-hard and provide hardness of approximation results for fixed radii for the case where all the sensors are initially co-located at an internal point of the barrier. Given n points in a circular region C in the plane, we study the problem of moving these points to the boundary of C to form a regular n-gon such that the maximum of the Euclidean distances traveled by the points is minimized. These problems find applications in mobile sensor barrier coverage of wireless sensor networks. The problem further has two versions: the decision version and optimization version. In this paper, we present an O(nlog2 n) time algorithm for the decision version and an O(nlog3 n) time algorithm for the optimization version. The previously best algorithms for these two problem versions take O(n 3.5) time and O(n 3.5logn) time, respectively. A by-product of our techniques is an algorithm for dynamically maintaining the maximum matching of a circular convex bipartite graph; our algorithm performs each vertex insertion or deletion on the graph in O(log2 n) time. This result may be interesting in its own right. A set of sensors establishes barrier coverage of a given line segment if every point of the segment is within the sensing range of a sensor. Given a line segment I, n mobile sensors in arbitrary initial positions on the line (not necessarily inside I) and the sensing ranges of the sensors, we are interested in finding final positions of sensors which establish a barrier coverage of I so that the sum of the distances traveled by all sensors from initial to final positions is minimized. It is shown that the problem is NP complete even to approximate up to constant factor when the sensors may have different sensing ranges. When the sensors have an identical sensing range we give several efficient algorithms to calculate the final destinations so that the sensors either establish a barrier coverage or maximize the coverage of the segment if complete coverage is not feasible while at the same time the sum of the distances traveled by all sensors is minimized. Some open problems are also mentioned. We consider several variations of the problems of covering a set of barriers (modeled as line segments) using sensors that can detect any intruder crossing any of the barriers. Sensors are initially located in the plane and they can relocate to the barriers. We assume that each sensor can detect any intruder in a circular area centered at the sensor. Given a set of barriers and a set of sensors located in the plane, we study three problems: the feasibility of barrier coverage, the problem of minimizing the largest relocation distance of a sensor (MinMax), and the problem of minimizing the sum of relocation distances of sensors (MinSum). When sensors are permitted to move to arbitrary positions on the barrier, the problems are shown to be NP-complete. We also study the case when sensors use perpendicular movement to one of the barriers. We show that when the barriers are parallel, both the MinMax and MinSum problems can be solved in polynomial time. In contrast, we show that even the feasibility problem is NP-complete if two perpendicular barriers are to be covered, even if the sensors are located at integer positions, and have only two possible sensing ranges. On the other hand, we give an O(n 3 2) algorithm for a natural special case of this last problem. Monitoring and surveillance are important aspects in modern wireless sensor networks. In applications of wireless sensor networks, it often asks for the sensors to quickly move from the interior of a specified region to the region's perimeter, so as to form a barrier coverage of the region. The region is usually given as a simple polygon or even a circle. In comparison with the traditional concept of full area coverage, barrier coverage requires fewer sensors for detecting intruders, and can thus be considered as a good approximation of full area coverage. In this paper, we present an O(n2.5 log n) time algorithm for moving n sensors to the perimeter of the given circle such that the new positions of sensors form a regular n-gon and the maximum of the distances travelled by mobile sensors is minimized. This greatly improves upon the previous time bound O(n3.5 log n). Also, we describe an O(n4) time algorithm for moving n sensors, whose initial positions are on the perimeter of the circle, to form a regular n-gon such that the sum of the travelled distances is minimized. This solves an open problem posed in [2]. Moreover, our algorithms are simpler and have more explicit geometric flavor.