Nalanda

Citation: S. Madden, M.F. Hellerstein, and W. Hong, “TAG: A Tiny AGgregation Service for Ad-Hoc Sensor Networks,” Proc. 5th Usenix Symp. Operating Systems Design and Implementation, Usenix Assoc., 2002, pp. 131–146.

Since the data extracted from sensor networks is often in the form of summaries, or aggregations, this paper makes the argument that aggregation of data should be considered, and made available, as a core service on sensor networks. TAG, an aggregation service for ad hoc networks based on the TinyOS platform is presented and evaluated.

The two essential features of TAG are a declarative data collection language, inspired by SQL, and the mechanisms for distribution and aggregation of queries across the sensor network, keeping in mind power, time and other constraints, as well as lossy links. The use of a high level language for data collection allows a number of end-to-end optimizations which result in lower data demands on the network, and easier recovery from data losses in the aggregation process. A classification is presented of different types of aggregate functions, with interesting implications for the processing requirements and sensitivity to network losses, for different kinds of aggregates.

One of the decisions taken for design of the routing protocol is to use only symmetric links; asymmetric links are blacklisted. The authors state that this is a common decision in wireless ad hoc networks, but I am not clear as to why this would be so. TAG uses a tree-based routing scheme, with periodic announcements to keep the tree up-to-date. The number of messages transmitted by a node obviously has significant effects on power consumption, which is why the authors make the argument that it therefore makes sense to process data within the network, a trade-off of power consumed due to aggregation-related processing against that consumed due to message transmission. To minimize transmissions, parents in the routing tree aggregate data from children, received over parent-specified time intervals, before passing it up the tree. In contrast, a centralized aggregation mechanism would require parents to forward every message received from children as-is.

In simulations, it is demonstrated that TAG, at worst, approximates the behaviour of centralized approaches in terms of the number of messages transmitted. At best, with aggregation functions which return single, or small sets, values, it results in an order of magnitude reduction in the number of messages transmitted.

I found this paper was useful in how it made me think about the ways in which application layer abstractions (the query interface) could be optimized in different ways (aggregation functions) over the functioning of a network.