Optimal Strategies for Computing Symmetric Boolean Functions in Collocated Networks

Download Now Date Added: Nov 2009
Format: PDF

The authors address the problem of finding optimal strategies for computing Boolean symmetric functions. They consider a collocated network, where each node's transmissions can be heard by every other node. Each node has a Boolean measurement and they wish to compute a given Boolean function of these measurements with zero error. They allow for block computation to enhance data fusion efficiency, and determine the minimum worst-case total bits to be communicated to perform the desired computation. They restrict attention to the class of symmetric Boolean functions, which only depend on the number of 1s among the n measurements.