Optimal Computation of Symmetric Boolean Functions in Collocated Networks
Academic Article

 Overview

 Research

 Identity

 Additional Document Info

 View All

Overview
abstract

We consider collocated wireless sensor networks, where each node's transmissions can be heard by every other node. Each node has a Boolean measurement and the goal of the network is to compute a given Boolean function of these measurements. We first consider the worst case setting and study optimal block computation strategies for computing symmetric Boolean functions. We study three classes of functions: threshold functions, delta functions and interval functions. We provide optimal strategies for the first two classes, and a scaling law orderoptimal strategy with optimal preconstant for interval functions. We extend the results to the case of integer measurements and certain integervalued functions. Next, we address the problem of minimizing the expected total number of bits that are transmitted when node measurements are random and drawn from independent Bernoulli distributions. In the case of computing a single instance of a Boolean threshold function, the problem reduces to one of determining the optimal order in which the nodes should transmit. We show that the optimal order of transmissions depends in an extremely simple way on the values of previously transmitted bits and the ordering of the marginal probabilities of the Boolean variables according to the kth least likely rule: At any transmission, the node that transmits is the one that has the kth least likely value of its Boolean variable, where k reduces by one whenever a node transmits a one. Initially the value of k is (n +1Threshold). Interestingly, the order of transmissions does not depend on the exact values of the probabilities of the Boolean variables. In the case of identically distributed measurements, we further show that the averagecase complexity of block computation of a Boolean threshold function is O(θ), where θ is the threshold. We further show how to generalize to a pulse model of communication. One can also consider the related problem of approximate computation given a fixed number of bits. For the special case of the parity function, we show that the greedy strategy is optimal. © 19832012 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

Sequential Decisionmaking
Identity
Digital Object Identifier (DOI)
Additional Document Info
start page
end page
volume
issue