Maintaining Intruder Detection Capability in a Rectangular Domain with Sensors

In order to detect intruders that attempt to pass through a rectangular domain, sensors are placed at nodes of a regular spaced grid laid out over the rectangle. An intruder that steps within the sensing range of a sensor will be detected. It is desired that we prevent potential attacks in either one-dimension or two-dimensions. A one-dimensional attack succeeds when an intruder enters from the top (North) side and exits out the bottom (South) side of the domain without being detected. Preventing attacks in two dimensions requires that we simultaneously prevent the intruder from either entering North and exiting South or entering East (left side) and exiting West (right side) undetected. Initially, all of the sensors are working properly and the domain is fully protected, i.e., attacks will be detected, in both dimensions (assuming the grid points are such that neighboring sensors have overlapping sens- ing ranges and include all four boundaries of the domain). Over time, the sensors may fail and we are left with a subset of working sensors. Under these conditions we wish to (1) determine if one or two-dimensional at- tack detection still persists and (2) if not, restore protection by adding the least number of sensors required to ensure detection in either one or two dimensions. Ideally, the set of currently working sensors would provide some amount of fault-tolerance. In particular, it would be advantageous if for a given k, the set of sensors maintains protection (in one or two-dimensions) even if up to k of the sensors fail. This leads to the problems of (1) deciding if a subset of the sensors provides protection with up to k faults and (2) if not, finding the minimum number of grid points to add sensors to in order to achieve k fault-tolerance. In this paper, we provide algorithms for deciding if a set sensors provides k-fault tolerant protection against attacks in both one and two dimen- sions, for optimally restoring k-fault tolerant protection in one dimension and for restoring protection in two dimensions (optimally for k = 0 and approximately otherwise).