This paper presents TAG, an aggregation service suitable for Ad-Hoc Sensor Networks. In a centralized approach the sensed data from all the nodes in the network is passed to the base station for further processing, however, TAG will have the nodes to process the sensed data locally, performing an aggregation function as the data is passed between nodes. This allows for a great reduction in the communication overhead and energy savings.
At start up, TAG will configure the network in the form of a tree structure, so each node ends up being either a leaf node or a node with children (parent node). The root of the tree talks directly to the base station. When data from the nodes is requested, every node will receive the data query (distribution phase). Then, every node will sense its parameter (temperature, light, magnetic field, acceleration, sound, power, etc), perform the aggregation function (MAX, MIN, COUNT, AVG, SUM, MEDIAN, HISTOGRAM, etc), and send the data to its parent node for further processing. This data measurement, processing and propagation will continue until the root is reached (collection phase). At that point, the final hop from the root to the base station will contain the final value of the query and no further processing will be necessary.
In the centralized approach, the data from every node requires to complete the whole path to the base station which adds up, and typically makes the nodes close to the base station to exhaust its batteries. TAG, however, will require only one hop per link, flowing from the leaf nodes all the way up to the root. This accounts for the communication and energy consumption reduction mentioned before.
Some optimizations have been made to reduce even more the communication necessary to complete the queries. For example, Hypothesis testing: nodes hear neighbors and can decide not to transmit if they know that will not contribute to the aggregate function (i.e. having a value under MAX, does not contribute to the final value); The SQL HAVING clause reduces communication by discarding data via comparisons like <,>,<>,etc; Other techniques overcome data loss, for example Caching: parent nodes will remember records from their children and use them whenever their links to its children are lost.
Experimentation shows that the communication overhead can be reduced by ~50% when comparing TAG to a centralized approach (even without applying the optimizations mentioned).
The nodes used by TAG are full fledged computers called motes. They run an operating system called TinyOS. The queries use the SQL syntax, which result very easy to use unlike low level languages like C. In this way, many professionals of different disciplines can write declarative queries in a short time.
Having used TinyOS operating system, the authors have come with a novel idea of simple SQL query based technique to aggregate the data which will make the protocol light weight to be handled buy the motes. Their experimental results also show that TAG can perform better compared to the centralized aggregation technique.
ReplyDeleteI liked the idea of using a decentralized query processing approach, as this greatly reduces the number of transmissions and hence prolongs the network lifetime. This also helps reduce congestion and contention issues in the network. Moreover, using a common declarative interface which is SQL-like promotes the usability of the approach.
ReplyDeleteTAG realizes a distributed query aggregation scheme that is sensitive to resource constraints and can cope with lossy communication of WSN.I liked TAG mainly for two reasons. One is communication reduction which is important for power and contention. And other is continuous stream of results.
ReplyDeleteI like that they did this specifically for nodes running TinyOS. Its good that they have some "real" world results. A lot of papers don't go this far into experimentation so that's refreshing to see.
ReplyDelete