Screenshot of the sensor network simulator that was used in testing the spanning algorithms.

Introduction and Background

This joint Distant Focus/University of Illinois project was sponsored by DARPA through the SensIT program. In June of 2002, Dr. Rick Morrison (Distant Focus Corporation) and Professor Bruce Hajek (University of Illinois at Urbana-Champaign) renewed an investigation of distributed large-scale network routing problems that had been initiated by Professor Hajek and a former graduate student. The goal of this program was to code the algorithm and investigate performance through a study of the simulation and through visualizing its operation.

One problem for future large-scale sensor arrays will be to determine a network routing mechanism that does not expend substantial resources (e.g. processing power and communications bandwidth.) We assume for the moment that large-scale is defined as upwards of 10³ to 10⁶ heterogeneous sensors operating without local centralized control. We are thus examining an algorithm that is distributed across all nodes of the network. The basic operation of the algorithm is to efficiently establish a set of node centers that span the network, where each center covers a region of nodes out to a distance of r hops, and then determines shortest distance routing between these centers.

The figure to the right shows the display and control panels for the simulation near the completion stage of the covering algorithm. Cyan patches show overlapping regions with magenta squares representing the associated center nodes.

Algorithm Simulation

Here are a few details about the simulation. The code was written in Python with Linux being the target OS. The primary reason for this choice is that the author (Morrison) felt that the code could be quickly developed in this language and, if needed, specific elements could be transcribed to C to provide additional performance. In addition, python has an image processing library and is available on many workstation architectures, as is the graphical interface - Tkinter. Finally, python can be incorporated into web documents.

This animation example shows how routing information grows about a single potential center. Red pixels mark where "Announce" messages are being processed, while blue pixels show the advance of 'Detect' messages that eventually determine when the local area has settled to a stable solution. The covered nodes are highlighted in cyan, while either white or magenta designates the settled center node.

Algorithm Animation

Click on image to see animation (2MB) or view the 9MB or full size 21MB animation.

A regular 2D grid of network nodes is operating the covering algorithm with the detection phase. The grid is 50x50 and the maximum distance from a center to the edge of its covering is 10. White pixels designate the centers that have settled (i.e. are permanently established.) Click on the image to download the full animated GIF graphic and watch the network grow. One word of caution - the size of these GIF animations are fairly large, so if you do not have a high bandwidth interconnection then extreme patience is required.