Zero-error function computation in sensor networks

We consider the problem of data harvesting in wireless sensor networks. A designated collector node seeks to compute a function of the sensor measurements. For a directed graph G = (V ,¿) on the sensor nodes, we wish to determine the optimal encoders on each edge which achieve zero-error block computation of the function at the collector node. Our goal is to characterize the rate region in R^|¿|. We start with the two node problem, and determine a necessary and sufficient condition for the encoder that yields the optimal alphabet, from which we then calculate the minimum worst case and average case complexity. We then extend this result to trees and derive a necessary and sufficient condition for the encoder on each edge. The further extension of these results to directed acyclic graphs is not immediate. 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. Finally, we consider a collocated network of nodes with a specified order of transmission. We determine a necessary and sufficient condition for each encoder which is based on the transmissions received, and show that the average case complexity of computing a type-threshold function is ¿(1), in comparison to the worst case complexity of ¿(log n).