Skip Header NavigationIntranet 
CENTER FOR EMBEDDED NETWORKED SENSINGContactDirectionsEmploymentEventsNews
HomeAbout UsResearchEducationResourcesPeople

Research Project


Generalized software tools: Routing Algorithms--Centroute

Technology > Systems Infrastructure Area Projects > Generalized software tools: Routing Algorithms--Centroute

On this page: Overview | Approach | Systems/Experiments | Accomplishments | Future Directions | People

Overview

Centroute is a mote routing protocol that is built specifically to address the needs of Mote Herding and heterogeneous sensor networks in particular.  The resource constraints on the mote platform often constrain their spatial and temporal views. As a result, decisions made on a mote often must be based on limited information, even assuming complete message reception. On the other hand, the microserver is a resource-rich platform and as such can make decisions with higher accuracy than the resource-constrained mote platform.  Centroute is a centralized tree-based routing protocol, in that all control decisions are made in a single point, the microserver (which is also the root of the tree). The protocol uses source routing in addition to a centralized decision point in order to avoid loops. In addition, only constant state is kept on the motes themselves (information about their parent) so the protocol scales well with increasing network density (in contrast, protocols that maintain neighbor lists on each mote have scalability issues when density increases). Centroute is able to maintain higher than 99% connectivity in medium or high-density networks while incurring a low overhead.

Approach

Tree-based routing is widely used in sensor networks, where all nodes construct a multi-hop routing tree to a centralized root (or gateway or sink). MintRoute [22] and Directed Diffusion [13] are two routing protocols that are often used in sensor networks. The Multihop routing protocol which is part of the ESS deployment at James Reserve [26] combines a simplified Diffusion and MintRoute. Each of these protocols uses a distance-vector-like routing algorithm to determine routes back to the sink, and employs link estimation and neighbor tables to dynamically discover the topology of the wireless network. Recent experiences with the ESS deployment have uncovered several underlying issues that stem from the aforementioned properties of those routing algorithms combined with the resource constraints of the mote platform. Those issues are: (a) neighbor-table overflow, (b) count-to-infinity and (c) routing loops. These issues are examples of distributed decision-making on the motes that is based on incomplete and potentially, stale, data. In contrast, CentRoute shifts all decision making to the sink. CentRoute addresses the problems described above: since it runs on a microserver with megabytes of memory, neighbor table size is not a limitation. Since all path selection and routing decisions are made centrally, different motes will not come to different decisions that can lead to inconsistencies. We conducted a number of simulations to show that these approaches in CentRoute are successful at providing high network connectivity and reducing the number of loops.

Systems/Experiments

Using simulation as well as testbed experiments, we show that Centroute indeed achieves its goals of low control overhead and scalability.

 Network Connectivity

First we look at how well each routing protocol maintains connectivity to the sink. We study how connectivity varies as we change the network density by increasing the simulated radio range.

Figure 1: Network connectivity percentage as a function of mote neighbor density for CentRoute, MintRoute and Multihop. Table 1: Average loop occurrence probability as a function of density for CentRoute, MintRoute and Multihop.

Figure 1: Network connectivity percentage as a function of mote neighbor density for CentRoute, MintRoute and Multihop.
Table 1:
Average loop occurrence probability as a function of density for CentRoute, MintRoute and Multihop.

Control Overhead

The control overhead of the routing algorithms is the transmission overhead incurred by their operation as well as their memory usage on the mote.

Figure 2: Per-mote byte overhead as a function of mote neighbor density for CentRoute, MintRoute and Multihop. Table 2: Mote RAM and ROM usage in bytes for CentRoute, MintRoute and Multihop.

Figure 2: Per-mote byte overhead as a function of mote neighbor density for CentRoute, MintRoute and Multihop.
Table 2: Mote RAM and ROM usage in bytes for CentRoute, MintRoute and Multihop.

Figure 2 shows that CentRoute incurs the highest overhead when neighbor density is low; however, overhead decreases rapidly in medium and high densities.

In terms of memory usage (Table 2), CentRoute incurs the lowest overhead; in addition, RAM overhead doesn’t increase with the neighborhood size, compared to the other 2 protocols.

Summary

Based on all our routing experiments we feel that the CentRoute foundation service has achieved its design goals. By centralizing the routing decisions on the microserver and removing per-neighbor state on motes CentRoute manages to scale well with increasing neighbor density as well as avoid loops while at the same time incurring a low overhead. However, the centralized property of CentRoute is not well suited for sparse networks with long path lengths. The reason is due to the overhead associated with transmitting all the control data back to a single point in addition to the expensive repair mechanism is invoked more frequently.

Accomplishments

One Technical Report:

Thanos Stathopoulos, Lewis Girod, John Heidemann, and Deborah Estrin
Mote Herding for Tiered Wireless Sensor Networks
CENS Technical Report #58 , December 7 2005.

Future Directions

We are planning to use CentRoute as a routing protocol for the mote-like radio. The formed mote network will be used as a multihop “paging channel” whose goal will be to wake up the microserver nodes on-demand. The selection of specific nodes that will be awakened will depend on the network topology, as the goal is to create an end-to-end path from the source node to the final destination.

People