OVERVIEW

Routing in large scale sensor networks needs to be scalable with good performance. Though geographical routing is quite scalable, the requirement of the location information and its poor performance in real dynamic sensor networks motivate the exploration of other alternatives.

Based on the observation that deployments of wireless sensor networks without access to accurate location information will manually configure location information in network nodes in order to assign spatial context to sensor reading and these location names are often hierarchically organized, we show that we could make use of these hierarchical location names to design a scalable routing scheme called HLR. HLR provides a variety of primitives including unicast, scoped anycast and broadcast, as well as various forms of scalable rendezvous which can be used to implement most data-centric routing and storage schemes proposed in the literature.

HLR is a scalable routing, yet its performance relies on the techniques used for path selection. Since the communication of wireless sensor networks is notorious, several techniques to improve reliability of communication are proposed, which include link-level retransmission(ARQ), blacklisting(rejecting bad links) and routing using a metric that inproves path reliability. It is unknown how there techniques will interact with each other. To improve the performance of scalable routing in large scale sensor networks, we carefully explored the interaction between these techniques.

APPROACHes

Our approach for hierarchical routing uses hierarchical locations to construct scalable routing tables. 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. We proposed a hierarchical aggregated mapping of the sensor network based on a simple DSDV routing protocol.
• Robustness: Although in sensor network deployment, sensor nodes which are organized in one cluster should be connected within the cluster, errors like mislabeling and failures always happen and break the hierarchical connectivity assumption. We proposed error-handling to ensure the robustness of the protocol.
• Random-Hashing: The aim of  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.
• 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.

Our approach for performance measurement is understanding the impact of three different reliability techniques used in wireless sensor networks: (a) Per-hop retransmission (often called ARQ at the MAC layer), (b) Blacklisting, a technique that prevents low quality links from being considered for path selection, (c) using link and path metric to select the best paths to the destination.

These three mechanisms are not mutually exclusive; each approaches the problem of improving end-to-end reliability in a different way. However, to our knowledge, there is no literature that systematically compares these techniques across a range of parameters, both individually and in combination. In this paper, we conduct such a systematic study. This study is complicated by the fact that the parameter space is rather large each technique can be used with different settings and thresholds. We use simulation to explore the space thoroughly, then validate selected simulation results through testbed experiments.

SYSTEMS / EXPERIMENTS

Using the approach described for hierarchical routing, 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 evaluate 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.

For our performance study of reliability techniques for wireless data delivery, we conducted a simulation study of the three techniques to systematically explore the parameter space of each mechanism and combinations of the mechanisms. We conduct our simulations using diffusion release 3.2.0 as a process-level simulator. Packets are sent between nodes as UDP packets. Between each pair of nodes all packets are subject to probabilistic loss as a function of distance based on propagation profiles from Mica1-based empirical data.

To validate our simulation results we conducted experiments on an 18-node testbed. In our 18-node Stargate  testbed, we configured one node to function as a source, one as a sink, and 16 nodes as relays. A Mica-2 node attached to each Stargate was used for radio communication. We adjusted the radio transmit power on the mote such that each node has 5-15 neighbors. This setting provides a rich network connectivity, which makes available numerous possible paths between the source and the sink. The motes run TinyOS, but with S-MAC as the MAC layer.  The following figure shows the testbed deployment map on the 11th floor of ISI. Gray boxes are relay nodes. The black circle (top-right) is a source node. The black box (bottom-left) is a sink node.

During our performance study, we made the observation that the ML (minimum-latency) metric, together with blacklisting and retransmissions is able to achieve comparable reliability at lower overhead than ETX with retransmissions. Essentially, blacklisting enables ML to finds paths that have moderate reliability, and retransmissions on these paths improves path reliability. The following figure compares leading protocol combinations and also includes unenhanced protocol (ML with no retransmission and blacklisting) to provide a basis for comparison. The label (n,b%,m) stands for a protocol combination that uses n retransmissions, a blacklisting threshold of b% and m routing metric.

ACCOMPLISHMENTS

In our study of hierarchical routing, we  tested the correctness of the scheme using simulation and evaluated the performance using both simulation and small-scale experiments.

The main contribution of our performance study is identification of several key results: One is that per-hop retransmissions is a necessary addition to any other mechanism if reliable data delivery is a goal. Additional interactions between the services are more subtle. First, in a multi-hop network, either blacklisting or reliability metrics like ETX can provide consistent high-reliability paths when added to ARQ. Second, at higher deployment densities, blacklisting has a lower routing overhead than ETX. But at lower densities, blacklisting becomes less stable as the network partitions. These results are consistent across both simulation and testbed experiments. We describe these results in the context of sensor networks; they are also applicable to multi-hop ad hoc networks.

FUTURE DIRECTIONS

 We intend to add our hierarchical routing 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.

In our performance study, while we explored the tradeoffs and properties of different reliability mechanisms, we haven’t investigated the impact of temporal variation in link quality on reliability metric. Further, we found some differences between testbed and simulation results which we were not able to explain. This will require a more detailed MAC level instrumentation.

HISTORICAL PROJECTS

Metric-Based Routing
Scalable Structured Routing

PEOPLE

Fang Bian (USC)
Omprakash Gnawal (USC)
Mark Yarvis (Intel)
Xin Li (USC)
John Heidemann
Ramesh Govindan (USC)
Scott Shenker (ICSI)
Deborah Estrin (UCLA)