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

The paper describes a data aggregation service, called TAG, that operates on TinyOS. It argues that aggregation is such central functionality in WSN that it should be structured as a service. This justifies its existence within the end-to-end arguments. It incorporates SQL as user frontend for the service. This is nice because it leverages the data aggregation research that has been done in the database community. 

It has a small section on the taxonomy of aggregates. It briefly classifies some aggregate functions based on their characteristics. I would like to see more on how this info is applied. Maybe a type checker of the query compiler can take advantage of the info and prevent user from abusing the service. Or, more possibly, a query optimizer use these extra info to specialize a given aggregate function. 

The basic mechanism of TAG is to arrange a hierarchical routing structure (like a tree) for each user query. The tree is then used to propagate and aggregate data from bottom-up, where the root is the node interacting with the user. At each level of the tree, nodes can use "epoch" to set up sampling intervals and perform the query-specific aggregation. The paper acknowledges that the sampling intervals is timing imprecise, influenced by timing jitter and many other timing problems. The author thus only assumes vague timing semantics.

One problem with having a tree structure is fault tolerance. A tree inherently is prone to single point of failure. If a node higher up in the hierarchy failed, much data is lost compared to the failure of lower node. Also, security is a concern. A malicious node can pretend to be very near the root and have great influence on the aggregate result.

The SQL interface is a nice idea because it gives more flexibility for application usage compare to the traditional way of hard-coding in a single app. In-network aggregation minimizes message exchange. However, the challenge seems to be on reliability. How much confidence can we put into the data extracted from the network using TAG, given its limitation on the sampling rate? 

Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks (USC)

The paper presents a new approach to wireless routing called directed diffusion. The idea is borrowed somewhat from the reaction-diffusion model in biology. It's link-based protocal where nodes interact locally with neighbors. The protocol design assumes particular application semantics, so it's not build for all apps. In particular, it allows information sink nodes to send out "interest" messages. These are queries for specific info from the network. 

The whole process of communication is a iteration of three steps: interest notification, gradient establishment, and reinforcement. Gradient is a tuple of data rate and direction. It's implemented by keeping states in the intermediate nodes with event entries, which basically tells the nodes where to forward a particular packet to. It's a on-demand routing protocol. However, the nodes have a choice of dropping or aggregating the packets. Reinforcement is the control mechanism to adjust the gradient. Positive reinforcement increase the communication rate, while negative reinforcement stops or decrease the comm. rate. Also, the interest request has a expiration field which specifies the duration of the comm.

The paper didn't address the problem of congestion, which i think would be a big problem for their protocol. Can it scale up to thousands of nodes, especially for randomly distributed network? The root problem is because they uses real-time to do the control for their protocol. Temporarily congestion creates timing jitters that would lead to improper reinforcement. 

Mobility is also a concern. The author suggests that the localized comm. helps the protocol adjust to dynamic topology more efficiently. However, it seems everytime a node moves would require setting up the gradients all over; otherwise, you can't guarantee the packet will get to the sink. In this case, out-dated gradients would die off on their own because of timeouts. However, it seems you still need to set up new gradients to make sure there is a path from the source to sink.

The protocol isn't described as clearly as it should be. There is a lot of cross-layer design, which violates the end-to-end principle. The idea is novel but doesn't look like it's cleanly engineered. The performance results isn't too meaningful when you take congestion of the formula. It is not clear what is gained here. It's not a loss if we skip this paper next semester.

A High-Throughput Path Metric for Multi-Hop Wireless Routing (MIT '03)

Minimum hop count is not a good metric to choose a route. First, one high-loss link along a route would create major delay and congestion. This causes retransmission and timeout which leads to decrease in overall network throughput. However, these links may be suitable for sending routing packets instead of data packets. Min hopcount is also bad when it chooses arbitrarily among multiple "equivelant" routes. It mostly likely pick a suboptimal one. Having a metric that is more refined than hop count helps to increase throughput.

ETX is one metric specification. It predicts for each link the expected transmission count per packet. Then it picks the route that has the least combined ETX count. It approximates the ETX by sending a periodic probe (every 1 sec). By dividing the actual received probes by the number sent, you get the delivery ratio. The inverse of it is ETX. It's very simple to understand and easy to implement. It adds very little to the routing states.

ETX has its own limitations. It only interacts and reacts to mobility as good as it updates the routing states, which is delayed by WST (weighed settling time). The main essense of using transmission count is a step further than hop count; however, it doesn't go into the size of packets. It would more ideal to have something like ETX/bit.

The paper presents a simple understandable routing algorithm and implementation. It makes a argument and brings attention to the problem of min hop count. Although it would be nice to see a more comprehensive paper on routing metrics, this paper is a pretty good introduction.