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
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.