Computer Science – Information Theory
Scientific paper
2011-05-02
Computer Science
Information Theory
submitted to IEEE Transactions on Information Theory, April 2011
Scientific paper
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.
Kowshik Hemant
Kumar Ravi P.
No associations
LandOfFree
Optimal Function Computation in Directed and Undirected Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Optimal Function Computation in Directed and Undirected Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal Function Computation in Directed and Undirected Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-426538