This project focuses on new paradigms for robust aggregation in sensor
networks.
Previous approaches for computing
duplicate-sensitive aggregates in sensor networks (e.g., in TAG) have
used a tree overlay topology, in order to conserve energy and to avoid
double-counting sensor readings. However, a tree topology is not
robust against node and communication failures, which are common in
sensor networks. Synopsis Diffusion is a new approach to
in-network aggregation that combines energy-efficient multi-path
routing schemes with techniques that avoid double-counting. We have
developed a formal framework for decoupling message routing from
aggregation, enabling energy-efficient but robust routing of
intermediate values during aggregation. We show how the insights from
the formal framework enable adaptive routing without expending energy
on acknowledgement messages. As a result, the new approach achieves
significantly more accurate aggregate answers at minimal energy cost.
Recently, we have extended his work by using the tree-based approach
where network conditions are good and when accumulated values are
small (so that message loss does not have a large impact on the
aggregate answer) and the more robust synopsis diffusion approach
otherwise. This approach, called tributary-delta, can yield
significantly more accurate answers for the same energy cost compared
with using either approach alone. The resulting aggregation topology
has an analogy to a river flowing to a gulf, where the aggregation
initially proceeds along trees (akin to tributaries) and then switches
to multi-path when obstacles are encountered (akin to the delta at the
mouth of the river). We have developed techniques for dynamically
adjusting the balance between tributaries and deltas, as well as novel
algorithms for finding frequently occurring values in a sensor network
and for other aggregates.
For publications, see the IrisNet Project publications web page.