Computer Science – Information Theory
Scientific paper
2010-04-30
Computer Science
Information Theory
Accepted to 2010 IEEE International Symposium on Information Theory
Scientific paper
In this paper, we address the scenario where nodes with sensor data are connected in a tree network, and every node wants to compute a given symmetric Boolean function of the sensor data. We first consider the problem of computing a function of two nodes with integer measurements. We allow for block computation to enhance data fusion efficiency, and determine the minimum worst-case total number of bits to be exchanged to perform the desired computation. We establish lower bounds using fooling sets, and provide a novel scheme which attains the lower bounds, using information theoretic tools. For a class of functions called sum-threshold functions, this scheme is shown to be optimal. We then turn to tree networks and derive a lower bound for the number of bits exchanged on each link by viewing it as a two node problem. We show that the protocol of recursive innetwork aggregation achieves this lower bound in the case of sumthreshold functions. Thus we have provided a communication and in-network computation strategy that is optimal for each link. All the results can be extended to the case of non-binary alphabets. In the case of general graphs, we present a cut-set lower bound, and an achievable scheme based on aggregation along trees. For complete graphs, the complexity of this scheme is no more than twice that of the optimal scheme.
Kowshik Hemant
Kumar Ravi P.
No associations
LandOfFree
Optimal computation of symmetric Boolean functions in Tree networks 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 computation of symmetric Boolean functions in Tree networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal computation of symmetric Boolean functions in Tree networks will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-388695