text: 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.
  @cite_14: 
  @cite_7: 
  @cite_8: 
  @cite_10: 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.
  @cite_9: Sensors may fail due to various reasons such as heat, malicious activity, environmental hazards, extended use, and lack of power. As more and more sensors fail, certain desired properties such as barrier coverage will diminish and eventually fall below a desired level. In such a case, the network will have to be repaired. It is therefore desirable to have mechanisms to monitor network properties. In this paper, we are interested in measuring the quality of barrier coverage. In the literature, researchers only consider whether or not a sensor network provides barrier coverage. This is equivalent to measuring its quality as either 0 or 1. We believe quality of barrier coverage is not binary and propose a metric for measuring it. If the measured quality is short of a desired value, we further identify all local regions that need to be repaired. The identified regions are minimum in the sense that if one of them is not repaired then the resulting network will still be short of quality. We also discuss how to actually repair a region.
  @cite_3: 
  @cite_0: 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.
  @cite_2: 
  @cite_5: 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
  @cite_15: 
  @cite_13: 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.
  @cite_11: 
summary: 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.