Cost-Based Distributed Joins in Sensor Networks
Svilen Mihaylov, Sudipto Guha, Zack Ives

As sensor networks become increasingly sophisticated,
a key operation will be to support monitoring and event detection
by integrating heterogeneous data across multiple
device types, e.g., to combine RFID and video frame data
when an object is in view. The fundamental primitive in
such efforts is an in-network join of samples from different
collections of devices, based not only on physical properties
(e.g., proximity) but also logical ones (e.g., identifiers).
We study the problem of performing joins over a sensor
network, when sensor data is abstracted as tables that
change over time and there is a limited structure governing
which nodes may join with others. We develop techniques
for establishing communication, placing the join computation
within the network, and cost modeling and optimization.
Compared to the naive approach of joining values at
the root, our algorithms provide significantly better power
distribution, fault tolerance, and performance.