Optimal Function Computation in Directed and Undirected Graphs
Academic Article

 Overview

 Research

 Identity

 Additional Document Info

 View All

Overview
abstract

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 innetwork 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. Depending on the application, there could be a designated collector node, or every node might want to compute the function. 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 zeroerror 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 sumthreshold functions and determine the minimum worst case total number of bits to be exchanged on each edge. The optimal strategy involves recursive innetwork 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. © 2012 IEEE.
author list (cited authors)

Kowshik, H., & Kumar, P. R.
citation count
publication date
publisher
published in
Research
keywords

Communication Complexity

Function Computation

Innetwork Computation
Identity
Digital Object Identifier (DOI)
Additional Document Info
start page
end page
volume
issue