TAG: A Tiny Aggregation Service for Ad-Hoc Sensor Networks

Madden, Franklin, Hellerstein, Hong

sensor networks tag aggregation databases continuous queries

@inproceedings{madden:osdi-2002,
  title={{TAG}: A Tiny Aggregation Service for Ad-Hoc Sensor Networks},
  author={Samuel Madden and Michael J. Franklin and
          Joseph M. Hellerstein and Wei Hong},
  booktitle={5th Symposium on Operating Systems Design and Implementation},
  month={December 9--11},
  year={2002},
  pages={131--146},
}

TAG presents a scheme for efficiently spreading aggregate readings (averages, counts, etc) through a network of low-power, limited CPU sensor nodes. Key to the design is construction of a routing tree to the gateway, pushing queries out to all nodes, collecting values from children, and propagating aggregates up. A number of optimizations are included, limiting communication when unnecessary. The query language is a restricted form of SQL, with similar justifications based on ease of application writing. The paper includes a worthwhile section summarizing capabilities of representative motes. Interestingly, aggregating results up the tree, and assigning intervals for this to happen, both increases bandwidth and decreases information loss. The former is a result of decreased contention versus a centralized scheme. The latter is a product of single data units traveling one-hop before being included in an aggregate. The paper also presents a classification scheme defining different types of aggregation functions, the properties of which can in turn be used to apply varying optimizations and delivery schemes.

Some optimizations of interest include snooping---dropping messages if unnecessary, such as when a higher MAX is reported by a peer---and redundant messages---splitting linearly decomposable aggregates into several parts sent along multiple routes to the root. The simulation model used in most of the evaluations is weak, not accounting for either transmit or processing time, contention, etc. However, it sufficiently motivates the enabled comms savings.

No explicit provision is included for reliable delivery. This might have an adverse effect in many settings, and it's not clear that at least some support could not be provided relatively cheaply.

Of interest is the idea used here and in other sensor papers that point-to-point routing is not only difficult for such nodes, but it is also not necessary for many applications and systems (i.e. when all data is pushed toward a gateway). Something to explore might be the idea that even on more powerful networks/devices, some applications and systems, especially those with very few or very many nodes, might similarly dispense w/ point-to-point routing.

An extension of this work might be to look at aggregation and service composition with more complex operatiors. Many of the same ideas might be applicable even if the nodes aren't operating on simple numerical data but rather complex objects such as pictures and maps.