  We consider the problem of information aggregation in sensor networks, where
one is interested in computing a function of the sensor measurements. We allow
for block processing and study in-network function computation in directed
graphs and undirected graphs. We study how the structure of the function
affects the encoding strategies, and the effect of interactive information
exchange.
  We begin by considering a directed graph G = (V, E) on the sensor nodes,
where the goal is to determine the optimal encoders on each edge which achieve
function computation at the collector node. Our goal is to characterize the
rate region in R^{|E|}, i.e., the set of points for which there exist feasible
encoders with given rates which achieve zero-error computation for
asymptotically large block length. We determine the solution for directed
trees, specifying the optimal encoder and decoder for each edge. 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 address the scenario where nodes are connected in an undirected tree
network, and every node wishes to compute a given symmetric Boolean function of
the sensor data. Undirected edges permit interactive computation, and we
therefore study the effect of interaction on the aggregation and communication
strategies. We focus on sum-threshold functions, and determine the minimum
worst-case total number of bits to be exchanged on each edge. The optimal
strategy involves recursive in-network aggregation which is reminiscent of
message passing. In the case of general graphs, we present a cutset lower
bound, and an achievable scheme based on aggregation along trees. For complete
graphs, we prove that the complexity of this scheme is no more than twice that
of the optimal scheme.
