Scalable Structured Routing

Overview

Good routing protocols in sensor networks need to be robust, economic and scalable. Geographical routing protocols own these desired properties. Yet, geographical routing protocols are highly dependent on the preciseness of the localization systems, which is still in active research. On the other hand, it may also be desirable for the applications using sensor networks to acquire 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, the 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 in sensor network.

The scalable structured routing using hierarchical location identifies can:

• Provide unicasting, multicasting in sensor network. Multicasting could be area-oriented or a logical group oriented, e.g. all the sensor nodes equipped with weather sensor boards.
• Extend the functions in other data-centric routing like Diffusion.
• Provide the underling routing function for the data-centric storage systems like GHT.
• Can be easily extended to support other data-centric storage functions such as multi-dimensional index for range queries.

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 routing algorithm should be robust to the mislabeling of the nodes, or failures of the sensor nodes. Approaches 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 based 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. The main approach is to make the connected subset obtain an unified ID during the routing. 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 underling routing function for data-centric storage such as GHT. The approach we used here is to hash the key as a hierarchical location identifier. Tree-based version: In applications where base station is available, 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.

People

• Fang Bian
• Ramesh Govindan
• Scott Shenker