OVERVIEW

Routing protocols in a sensor network perform a basic service: given a set of available links, pick the best link towards a destination. One strategy to enhance the quality of the selected path is to restrict the set of available links to high quality links thereby avoiding an inclusion of a poor quality link in the path. We call this strategy Blacklisting. Another strategy is taking into account the quality of each link and iteratively searching for the best path in the network. We call this approach metric-based routing.

Blacklisting is simple and efficient but is dependent on the designers ability to select a good threshold a priori. A reliability metric can be used to identify better routes in the system but needs to continuously update the forwarding path as more reliable paths are discovered. We have systematically compared these strategies by measuring efficiency and overhead. The study will be relevant to single destination distance vector type protocols such as One-Phase-Pull in Directed Diffusion.

APPROACHes

Traditionally, in a single destination distance vector-like protocol, the sink sends a query to the network. The nodes in the network maintain state regarding the direction of propagation of the query. When a source with the right data responds to the query, this state is used to direct the response back to the sink. All the nodes maintain the direction of propagation of query based only on the first query received. Thus the system is making a routing decision based on latency of the links. If a link is fast, a node will receive query from that link first, and data will be forwarded along that path.

With the aforementioned approach, it is likely that the system gets stuck with bad links because the latency metric prefers long hops over short ones, and long hops are likely to be unreliable ones. To enhance the quality of forwarding paths formed, one can think of blacklisting the bad links and not using them while making routing decision. This would translate to ignoring the queries received through bad links.

An alternative effort to enhance the quality of paths uses a reliability metric to discover high quality paths in the network. We call this approach metric-based routing. In this approach, the nodes, when they receive a query, immediately form a forwarding path regardless of the quality of the link. The nodes update the metric field in the query to include the reliability information for the previous hop and broadcast it to the network. When a node receives a copy of the query it has previously seen, it compares the metric value in the query with the metric value of the currently active forwarding path. If the new path is better, the node updates its active forwarding path and propagates the new discovery to the network. This mechanism is similar to a relaxation technique and is used to continuously discover and adopt better paths. The metric based approach has a potential to cause too much update traffic as it discovers better routes and this is a cause of concern.

SYSTEMS / EXPERIMENTS

We have implemented these approaches in Diffusion, and conducted a systematic study of their comparative ability to increase the reliability of packet delivery:

• Using blacklisting to avoid selecting poor-quality links.
• Using link-layer retransmissions to improve reliability.
• Using a path reliability metric (metric-based routing) to select highly reliable cost.

Our experiments revealed several qualitative tradeoffs between the different approaches. Metric-based approach is good because it finds the best path. But it incurs more update traffic while establishing the route. It also selects long paths which could end up increasing the overhead while forwarding data from sources to the sink. A less-discussed approach is blacklisting unreliable links and running a simple protocol on this pruned set of links. This system is simpler. The overhead during interest flooding is small. However, there is a concern that a network might get partitioned. It favors long hops, also does not discriminate between good and mediocre links. This could result in paths with low reliability. A popular alternative to tame unreliable communication medium is retransmission. A concern here is too much wasted work if we are retransmitting on a bad link.

Our study found, surprisingly that, a combination of these three approaches works best. Specifically, using a metric like ETX, together with a moderate black-listing threshold, and one link-layer retransmission gives high reliability, good path length performance, while keep overheads low. The following graphs depict the performance of our scheme:

ACCOMPLISHMENTS

We built a Diffusion filter that selects path based on metric information. We built and tested TinyOS modules to sample, encode, propagate, and make decisions based on link metrics. We have completed our simulation study and are currently validating these simulations on a real-testbed.

FUTURE DIRECTIONS

Our goal is to implement our mechanism for metric-based path selection in Tiny Diffusion and test out this implementation perhaps on the ESS testbed.

PEOPLE

FACULTY

Dr. John Heidemann
Prof. Ramesh Govindan

GRADUATE STUDENTS

Omprakash Gnawali

INDUSTRY PARTNERS

Mark Yarvis (Intel)