Beacon Vector Routing: towards scalable point-to-point routing in sensor networks

CS294-1 Deeply Embedded Network Systems

Fall 2003
Rodrigo Fonseca
Instructor: prof. David Culler

Final Report

[PDF]

Abstract

In some applications of wireless sensor networks (WSN), it may be desirable for a node to reach another arbitrary node in the network. One such motivating application is the Data Centric approach to storage (DCS), in which data is stored -- and accessed -- by name in the network, in what constitutes a distributed hash table.

We are looking into a scalable solution for point-to-point routing, which don't rely on on-demand flooding, and has small state maintenance requirements, depending on the local neighborhood of a node rather than on the size of the graph. Geographic routing has these characteristics, although it relies on the nodes knowing their coordinates in space. Our approach, Beacon Vector Routing, uses a similar greedy algorithm for choosing next-hops, but does not use geographic coordinates. Instead, a coordinate system is build in which each node knows its distance (in network hops) to a set of reference nodes. When given a destination (a vector of distances), a node chooses as its next-hop the neighbor with the closest distances to the reference nodes.

We evaluate the performance and route characteristics of our algorithm in three separate settings: in a high level simulator, that allows deep investigation of algorithmic aspects in large networks; in a detailed TinyOS simulator that allows for the controlled analysis of the effects of loss and congestion; and on a real deployement on mica motes in an experimental test bed. Preliminary results show algorithm performs well in terms of scalability and length of paths in relation to shortest paths, and we shall present some results in this direction.

Related work