  We consider collocated wireless sensor networks, where each node has a
Boolean measurement and the goal is to compute a given Boolean function of
these measurements. We first consider the worst case setting and study optimal
block computation strategies for computing symmetric Boolean functions. We
study three classes of functions: threshold functions, delta functions and
interval functions. We provide exactly optimal strategies for the first two
classes, and a scaling law order-optimal strategy with optimal preconstant for
interval functions. We also extend the results 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.
  Next, we consider the case where nodes measurements are random and drawn from
independent Bernoulli distributions. We address the problem of optimal function
computation so as to minimize the expected total number of bits that are
transmitted. In the case of computing a single instance of a Boolean threshold
function, we show the surprising result that the optimal order of transmissions
depends in an extremely simple way on the values of previously transmitted
bits, and the ordering of the marginal probabilities of the Boolean variables.
  The approach presented can be generalized to the case where each node has a
block of measurements, though the resulting problem is somewhat harder, and we
conjecture the optimal strategy. We further show how to generalize to a pulse
model of communication. One can also consider the related problem of
approximate computation given a fixed number of bits. In this case, the optimal
strategy is significantly different, and lacks an elegant characterization.
However, for the special case of the parity function, we show that the greedy
strategy is optimal.
