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.
The performance of sensor networks is limited by both sensing resources and non-sensing resources such as communications, computation, and power. One set of results has been obtained by considering the limitations that communications requirements impose on a sensor network. @cite_1 extends the results in @cite_6 to account for the different traffic models that arise in a sensor network. @cite_34 studies network transport capacity for the case of regular sensor networks. @cite_32 studies the impact of computational constraints and power on the communication efficiency of sensor networks. @cite_36 has considered the interaction between transmission rates and power constraints. Another set of results has been obtained by extending results from compression to sensor networks. Distributed source coding @cite_11 , @cite_19 provides limits on the compression of separately encoded correlated sources. @cite_10 applies these results to sensor networks. @cite_40 provides an overview of this area of research.
@cite_36 @cite_1 @cite_32 @cite_6 @cite_19 @cite_40 @cite_34 @cite_10 @cite_11
2188872234 2076399305 2109004672 2137775453 2150412388 2162404506 2120855076 2139519968 2099213070
In this paper we study the transport capacity of a data-gathering wireless sensor network under different communication organizations. In particular, we consider using a flat as well as a hierarchical clustering architecture to realize many-to-one communications. The capacity of the network under this many-to-one data-gathering scenario is reduced compared to random one-to-one communication due to the unavoidable creation of a point of traffic concentration at the data collector receiver. We introduce the overall throughput bound of λ = W n per node, where W is the transmission capacity, and show under what conditions it can be achieved and under what conditions it cannot. When those conditions are not met, we constructively show how λ = Θ(W n) is achieved with high probability as the number of sensors goes to infinity. We also show how the introduction of clustering can improve the throughput. We discuss the trade-offs between achieving capacity and energy consumption, how transport capacity might be affected by considering in-network processing and the implications this study has on the design of practical protocols for large-scale data-gathering wireless sensor networks. Motivated by limited computational resources in sensor nodes, the impact of complexity constraints on the communication efficiency of sensor networks is studied. A single-parameter characterization of processing limitation of nodes in sensor networks is invoked. Specifically, the relaying nodes are assumed to "donate" only a small part of their total processor time to relay other nodes information. The amount of donated processor time is modelled by the node's ability to decode a channel code reliably at given rate R. Focusing on a four node network, with two relays, prior work for a complexity constrained single relay network is built upon. In the proposed coding scheme, the transmitter sends a broadcast code such that the relays decode only the "coarse" information, and assist the receiver in removing ambiguity only in that information. Via numerical examples, the impact of different power constraints in the system, ranging from per node power bound to network wide power constraint is explored. As the complexity bound R increases, the proposed scheme becomes identical to the recently proposed achievable rate by Gupta & Kumar (2003). Both discrete memoryless and Gaussian channels are considered. When n identical randomly located nodes, each capable of transmitting at W bits per second and using a fixed range, form a wireless network, the throughput spl lambda (n) obtainable by each node for a randomly chosen destination is spl Theta (W spl radic (nlogn)) bits per second under a noninterference protocol. If the nodes are optimally placed in a disk of unit area, traffic patterns are optimally assigned, and each transmission's range is optimally chosen, the bit-distance product that can be transported by the network per second is spl Theta (W spl radic An) bit-meters per second. Thus even under optimal circumstances, the throughput is only spl Theta (W spl radic n) bits per second for each node for a destination nonvanishingly far away. Similar results also hold under an alternate physical model where a required signal-to-interference ratio is specified for successful receptions. Fundamentally, it is the need for every node all over the domain to share whatever portion of the channel it is utilizing with nodes in its local neighborhood that is the reason for the constriction in capacity. Splitting the channel into several subchannels does not change any of the results. Some implications may be worth considering by designers. Since the throughput furnished to each user diminishes to zero as the number of users is increased, perhaps networks connecting smaller numbers of users, or featuring connections mostly with nearby neighbors, may be more likely to be find acceptance. Let (X_ k , Y_ k ) ^ _ k=1 be a sequence of independent drawings of a pair of dependent random variables X, Y . Let us say that X takes values in the finite set X . It is desired to encode the sequence X_ k in blocks of length n into a binary stream of rate R , which can in turn be decoded as a sequence X _ k , where X _ k X , the reproduction alphabet. The average distortion level is (1 n) ^ n _ k=1 E[D(X_ k , X _ k )] , where D(x, x ) 0, x X , x X , is a preassigned distortion measure. The special assumption made here is that the decoder has access to the side information Y_ k . In this paper we determine the quantity R (d) , defined as the infimum ofrates R such that (with > 0 arbitrarily small and with suitably large n )communication is possible in the above setting at an average distortion level (as defined above) not exceeding d + . The main result is that R (d) = [I(X;Z) - I(Y;Z)] , where the infimum is with respect to all auxiliary random variables Z (which take values in a finite set Z ) that satisfy: i) Y,Z conditionally independent given X ; ii) there exists a function f: Y Z X , such that E[D(X,f(Y,Z))] d . Let R_ X | Y (d) be the rate-distortion function which results when the encoder as well as the decoder has access to the side information Y_ k . In nearly all cases it is shown that when d > 0 then R (d) > R_ X|Y (d) , so that knowledge of the side information at the encoder permits transmission of the X_ k at a given distortion level using a smaller transmission rate. This is in contrast to the situation treated by Slepian and Wolf [5] where, for arbitrarily accurate reproduction of X_ k , i.e., d = for any >0 , knowledge of the side information at the encoder does not allow a reduction of the transmission rate. In recent years, sensor research has been undergoing a quiet revolution, promising to have a significant impact throughout society that could quite possibly dwarf previous milestones in the information revolution. Realizing the great promise of sensor networks requires more than a mere advance in individual technologies. It relies on many components working together in an efficient, unattended, comprehensible, and trustworthy manner. One of the enabling technologies in sensor networks is the distributed source coding (DSC), which refers to the compression of the multiple correlated sensor outputs that does not communicate with each other. DSC allows a many-to-one video coding paradigm that effectively swaps encoder-decoder complexity with respect to conventional video coding, thereby representing a fundamental concept shift in video processing. This article has presented an intensive discussion on two DSC techniques, namely Slepian-Wolf coding and Wyner-Ziv coding. The Slepian and Wolf coding have theoretically shown that separate encoding is as efficient as joint coding for lossless compression in channel coding. We study network capacity limits and optimal routing algorithms for regular sensor networks, namely, square and torus grid sensor networks, in both, the static case (no node failures) and the dynamic case (node failures). For static networks, we derive upper bounds on the network capacity and then we characterize and provide optimal routing algorithms whose rate per node is equal to this upper bound, thus, obtaining the exact analytical expression for the network capacity. For dynamic networks, the unreliability of the network is modeled in two ways: a Markovian node failure and an energy based node failure. Depending on the probability of node failure that is present in the network, we propose to use a particular combination of two routing algorithms, the first one being optimal when there are no node failures at all and the second one being appropriate when the probability of node failure is high. The combination of these two routing algorithms defines a family of randomized routing algorithms, each of them being suitable for a given probability of node failure. Distributed nature of the sensor network architecture introduces unique challenges and opportunities for collaborative networked signal processing techniques that can potentially lead to significant performance gains. Many evolving low-power sensor network scenarios need to have high spatial density to enable reliable operation in the face of component node failures as well as to facilitate high spatial localization of events of interest. This induces a high level of network data redundancy, where spatially proximal sensor readings are highly correlated. We propose a new way of removing this redundancy in a completely distributed manner, i.e., without the sensors needing to talk, to one another. Our constructive framework for this problem is dubbed DISCUS (distributed source coding using syndromes) and is inspired by fundamental concepts from information theory. We review the main ideas, provide illustrations, and give the intuition behind the theory that enables this framework.We present a new domain of collaborative information communication and processing through the framework on distributed source coding. This framework enables highly effective and efficient compression across a sensor network without the need to establish inter-node communication, using well-studied and fast error-correcting coding algorithms. Correlated information sequences ,X_ -1 ,X_0,X_1, and ,Y_ -1 ,Y_0,Y_1, are generated by repeated independent drawings of a pair of discrete random variables X, Y from a given bivariate distribution P_ XY (x,y) . We determine the minimum number of bits per character R_X and R_Y needed to encode these sequences so that they can be faithfully reproduced under a variety of assumptions regarding the encoders and decoders. The results, some of which are not at all obvious, are presented as an admissible rate region R in the R_X - R_Y plane. They generalize a similar and well-known result for a single information sequence, namely R_X H (X) for faithful reproduction.