In many sensor network applications, one is interested only in computing some relevant \textit{function} of the sensor measurements. In this thesis, we study optimal strategies for in-network computation and communication in such wireless sensor networks. We begin by considering a directed graph $G = (\mathcal{V},\mathcal{E})$ on the sensor nodes, with a designated collector node, where the goal is to characterize the rate region in $\mathbf{R}^{|\mathcal{E}|}$, i.e., the set of vector rates for which there exist feasible encoders and decoders which achieve zero-error computation for large enough block length. For directed tree graphs, we determine a necessary and sufficient condition for each edge that yields the optimal alphabet, from which we then calculate the minimum worst case and average case complexity. For general directed acyclic graphs, we provide an outer bound on the rate region by finding the disambiguation requirements for each cut, and describe examples where this outer bound is tight. Next, we consider undirected tree networks, where each node has an integer measurement, and all nodes want to compute a symmetric Boolean function. For a class of functions called sum-threshold functions, we derive an optimal strategy which minimizes the worst-case number of bits exchanged on each edge. In the case of general graphs, we present a cut-set lower bound, and an achievable scheme based on aggregation along trees. For complete graphs, the complexity of this scheme is no more than twice that of the optimal scheme. We then turn to a collocated network of nodes, where each node has a Boolean measurement and we wish to compute a symmetric Boolean function of these measurements with zero error. Our objective is to determine the minimum worst-case total number of bits to be communicated to perform the desired computation. We define three classes of functions, namely threshold functions, delta functions and interval functions. We provide exactly optimal strategies for the first two classes, and an order-optimal strategy with optimal preconstant for interval functions. Using these results, we can characterize the complexity of computing percentile type functions. The results also extend to the case of integer measurements and certain integer-valued functions. We use lower bounds from communication complexity theory, and provide an achievable scheme using information theoretic tools. In the collocated network scenario, minimizing the average case complexity presents a variety of interesting problems. We show that the average case complexity of computing a Boolean threshold function of i.i.d. measurements, with threshold $\theta$, is $O(\theta)$, in comparison to the worst case complexity of $\Omega(\log n)$, where $n$ is the number of nodes. In the case of independent but not identically distributed measurements, we show that the optimal order of transmissions is determined by a surprisingly simple rule that depends in a trivial way on the values of the previously transmitted bits and the ordering, but not the exact values of the marginal probabilities. The approach presented can be generalized to the case of block computation, and to alternate models of communication. We also determine the optimal strategy when the number of bits to be communicated is fixed, and one wants to minimize the conditional entropy of the parity function.Finally, we consider the problem of determining the connectivity of a random graph by sequentially sampling edges. We present optimal strategies for determining connectivity in series graphs, parallel graphs, series-parallel graphs and parallel-series graphs. In the case of general graphs, we consider the related problem of finding a certificate for connectivity, and conjecture the optimal strategy.
PDF
download
878987797
028-85220240
