TAG: a Tiny AGgregation Service for Ad-Hoc Sensor Networks

This paper presents TAG, a distributed aggregation scheme for wireless sensor networks. Many applications of ad-hoc mote networks require the execution of declarative queries to extract meaningful information from collected data. TAG provides an efficient alternative to centralized data processing mechanisms as it reduces communication requirements and hence bandwidth consumption. Essentially, sensor nodes are organized in a routing tree structure with a root base station serving as the data processing interface to the end user. This tree structure exploits the broadcast nature of radio transmission by maintaining level information at each node - even if a sensor node loses communication with its parent, it can detect a new parent by overhearing messages from the next higher layer in the routing tree. Upon applying the query locally and aggregating results from its children, each node routes data back to the root via its parent.

One appeal of the TAG service is the use of simple SQL-style queries. The concept is also somewhat resemblant of the distributed Map-Reduce implementation of a full inverted index. In that scenario, a query can be efficiently processed by distributing the work across many mappers, each dealing with a small subset of the text base. The primary concern that came to mind while reading this paper was the effect of disconnected nodes or lost messages. The authors answer this quite thoroughly with a caching solution. This paper addresses many issues inherent in sensor networks and certainly belongs in the syllabus.