OVERVIEW

Good routing protocols in sensor networks need to be robust, economic and scalable. Geographical routing protocols possess these desired properties. Yet, geographical routing protocols are highly dependent on the availability of the localization systems, which is still an area of active research. On the other hand, it may also be desirable for sensor network applications to know the locations of the source of the data. In absence of the localization systems, short- or mid-term sensor networks deployment may have to find a way to manually map the sensor nodes to their locations. One natural way to accomplish this is to assign hierarchical location identifier to each sensor node. For example, the Habitat Monitoring Test-bed deployed in James Reserve has a map showing the location of the clusters of the sensor nodes, like Meadow, Live Oak Forest etc. The sensor nodes within an area, say Meadow, are organized and treated as one unit. As the example shows, these hierarchical location identifiers, which are two-level in our example, usually contain rich information about the physical location of the sensor nodes. Furthermore, nodes within one cluster are usually physically located near each other, and thus can communicate with each other within the cluster. Our project is aimed to make use of the hierarchical location identifiers to construct scalable structured routing and rendezvous-based primitives.
The scalable structured routing using hierarchical location identifies can:

• Provide basic routing primitives such as unicasting, multicasting and anycasting in sensor networks. Multicasting could be area-oriented or a logical group oriented, e.g. all the sensor nodes equipped with weather sensor boards.
• Provide rendezvous primitives, which support rendezvous using random hashing, or rendezvous using data-locality preserving hashing.
• Routing primitives can be flexible enough to act as the underlying data-centric routing function for systems like TinyDB and Tiny-Diffusion.
• Rendezvous primitives can be used to build data-centric storage systems similar to systems like GHT and DIM.
• Routing and Rendezvous primitives could be used as support layer for any application which does not require precise geographical location information, one such example is triggering system.

The challenges of the project include:

• The routing algorithm must be able to be easily integrated into other applications, so it should consume the limited resources such as memory, code space and bandwidth etc. as less as possible.
• The algorithms should be robust to the mislabeling of the nodes, or failures of the sensor nodes.
• The rendezvous primitives should be consistent under the dynamics of the sensor networks.
• The system should either be self-healing (i.e. auto re-labeling) or provide administrative tools for error detection and reconfiguration of the sensor network in a deployed sensor network.

APPROACHes

Our approach uses these hierarchical location identifiers to construct scalable routing tables. For example, in the sensor network shown in the Figure 1, by running hierarchical identifier routing, node 2.2.1's routing table will contain one entry to the whole area 1, one entry to area 3 and one entry to its sibling area 2.1 in addition to one entry for the other nodes in the same area like 2.2.2 and 2.2.3. So, assuming the hierarchy of the network is appropriately designed, the size of the routing table can grow logarithmically with network size.

This approach imposes several challenges:

• Scalability: Here the main challenge is how to do aggregation of the routing table, in order that the size of the routing table is as small as possible. The basic idea is to build a hierarchically aggregated map of the sensor network based on a modified DSDV.
• Robustness: Although in sensor network deployment, sensor nodes which are organized in one cluster should be able to be connected within the cluster, errors like mislabeling and failures always happen and break the hierarchical connectivity assumption. Our routing protocol should be able to identify the mislabeling and failures and continue to work under the problematic circumstances. Our approach uses partition repair.
• Random-Hashing: The aim of the hashing is to provide a function to provide the routing to a specific node when a keyed address of the destination is provided such that the routing algorithm can be used as the underlying routing function for data-centric storage such as GHT. The approach we used here is to hash the key as a hierarchical location identifier.
• Data-Locality Preserving Hashing: For some data-centric storage systems, one desired feature is that the data is stored in a locality-preserving way. In other words, similar nodes store similar data. Data-locality preserving hashing provides a mapping from multi-dimensional data space to the nodes, such that the hyper-rectangles contiguous in data space is owned by nodes contiguous in topological space.
• Tree-based version: In applications where base station is available, a tree-based version of the routing algorithm rooted at the base station is desirable. The basic approach is to make full use of the property of the single tree to build an aggregated routing tree.

SYSTEMS / EXPERIMENTS

Using the approaches described above, we have developed a general version of scalable routing algorithms using hierarchical location identifiers and the routing and rendezvous-based primitives in ns-2 and TinyOS. To evaluating the efficacy of the routing and rendezvous-based primitives for data-centric systems, we also implemented a simplified One-Phase-Pull version of Diffusion with geocasting, a simplified DHT with same function as GHT and a version of DIM in ns-2 platform. We compared the performance of these data-centric systems on our routing scheme and on geographical routing scheme GPSR plus flooding.  Figure 2 shows that Diffusion over our routing support layer is comparable to that over GPSR. Figures 3 and 4 show that the performance of DHT and DIM using our routing and rendezvous primitives outperforms that of GPSR. The main reason for that is GPSR would incur perimeter traversal and in some pathological case even the outer-perimeter traversal of the network, which degrades its performance dramatically, Further, our data-locality preserving hashing actually preserves more data locality than its equivalent using geographical information. Finally, we evaluate the effect of dynamics by simulating the sequential node failure and node recovery for each node in the network. Figure 5 and Figure 6 shows that churn incurred by node failure is well contained locally.

ACCOMPLISHMENTS

We have tested the correctness of the scheme using simulation and evaluated the performance using both simulation and small-scale experiments.

FUTURE DIRECTIONS

We intend to build our algorithms as a routing layer for systems such as TinyDiffusion and TinyDB.

Before we do this, however, we will need to conduct experiments on a moderate sized testbed using Mica2 motes to:

• Calibrate parameters such as lifetime, advertising periods.
• Study the effectiveness of different path metric to data-centric abstraction.
• Study the effect of the dynamics, such as packet losses, node failures, movements, mislabeling and relabeling etc.
• Conduct experiments on real deployed sensor networks.
• Improve and evaluate the robustness of the routing and rendezvous primitives.
• Extend to support shared-tree multicasting, triggering etc.

PEOPLE

FACULTY

Prof. Ramesh Govindan
Prof. Scott Shenker (UCB)

GRADUATE STUDENTS

Fang Bian