Nalanda

Citation: Intanagonwiwat, C., Govindan, R., and Estrin, D. 2000. Directed diffusion: a scalable and robust communication paradigm for sensor networks. In Proceedings of the 6th Annual international Conference on Mobile Computing and Networking (Boston, Massachusetts, United States, August 06 - 11, 2000). MobiCom ‘00. ACM, New York, NY, 56-67. DOI= http://doi.acm.org/10.1145/345910.345920

This paper describes the general concept of directed diffusion for requesting, and retrieving, data from sensor networks. In such a system, users express an interest in certain kinds of data, and this interest then diffuses across the network towards the nodes most capable of responding, and is then relayed back along the same paths, a smaller set of which may be reinforced by the sensor network itself.

Tasks, or interests, are defined as a set of name/value pairs, along with a specification of the region of the network from which data is to be retrieved. Interests are periodically broadcast by the node to which a user connects, called the sink node, initially at a long interval, to probe the network for the existence of nodes which match the interest. Every nodes maintains an interest cache, with gradients on each interest pointing back to the node from which the interest was received and specifying a data rate.

Nodes, starting with the sink, initially broadcast interests to all their neighbours at a relatively low rate. As the sink starts receiving data, it selectively reinforces particualr neighbours, by resending the interest to them with a higher specified data rate. Nodes in turn perform the same process of reinforcement, selecting neighbours based on matches in their data cache to the interest. In addition, neighbour node selection is affected by the delay to respond to an interest: neighbours with lower delays are preferred. As the conditions along paths vary, data rates may also be lowered for negative reinforcement to remove a path from the preferred set.

The approach described here operates based only on local knowledge, which seems an important consideration for networks with power-constrained nodes. The authors suggest, as evaluated more completely in the other reading for today, that intermediate processing of data may yield even greater benefits.

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.