This paper demonstrates fundamental limits of sensor networks for detection problems where the number of hypotheses is exponentially large. Such problems characterize many important applications including detection and classification of targets in a geographical area using a network of seismic sensors, and detecting complex substances with a chemical sensor array. We refer to such applications as large-scale detection problems. Using the insight that these problems share fundamental similarities with the problem of communicating over a noisy channel, we define the “sensing capacity” and lower bound it for a number of sensor network models. The sensing capacity expression differs significantly from the channel capacity due to the fact that for a fixed sensor configuration, codewords are dependent and nonidentically distributed. The sensing capacity provides a bound on the minimal number of sensors required to detect the state of an environment to within a desired accuracy. The results differ significantly from classical detection theory, and provide an intriguing connection between sensor networks and communications. In addition, we discuss the insight that sensing capacity provides for the problem of sensor selection.
In Section we introduce a sensor network model that accounts for contiguity in a sensor's field of view. Contiguity is an essential aspect of many classes of sensors. For example, cameras observe localized regions and seismic sensors sense vibrations from nearby targets. We demonstrate sensing capacity bounds that account for such sensors by extending results about Markov types @cite_20 , and use convex optimization to compute these bounds. The first result in Section assumes the state of the environment is modeled as a one-dimensional vector. In Section we extend this result to the case where the state of the environment is modeled as a two-dimensional grid. While a one-dimensional vector can model sensor network applications such as border security and traffic monitoring, results about two dimensions significantly increase the type of applications described by our models.
@cite_20
2154518298
The method of types is one of the key technical tools in Shannon theory, and this tool is valuable also in other fields. In this paper, some key applications are presented in sufficient detail enabling an interested nonspecialist to gain a working knowledge of the method, and a wide selection of further applications are surveyed. These range from hypothesis testing and large deviations theory through error exponents for discrete memoryless channels and capacity of arbitrarily varying channels to multiuser problems. While the method of types is suitable primarily for discrete memoryless models, its extensions to certain models with memory are also discussed.