Wireless ad hoc networks of battery-powered microsensors are proliferating rapidly and transforming how information is gathered and processed, and how we affect our environment. The limited energy of those sensors poses the challenge of using such systems in an energy efficient manner to perform various activities. In many of these activities, a basic step is that of a sensor sending a data set to a base station. Since communication drains sensor energy fast, reducing the amount of bits transmitted can lead into substantial energy savings.

We consider the problem of communicating a given set S of elements from a universe in a way that transmits substantially fewer bits, with a very small computation overhead at the sender. We present an approach that utilizes Bloom filters to construct a small footprint signature for S, from which candidates for S are computed. Our approach trades some practical computation cost and a small precision loss at the receiver (base station), which is anyway resource rich, for reducing the number of bits transmitted. The precision loss stems from the fact that the recovered set at the receiver may include false positive(s).

We experimentally show that our approach substantially reduces the number of bits transmitted, while still having practical receiver running times and few false positive errors. Moreover, we show that our approach can utilize application-dependent characteristics to further reduce false positives, or even eliminate them as in our experiments with topology gathering and energy map gathering, without noticeable increase in running times.