Figure 1(a): initial state of sensors
NOTE: The Center for Mobile Computing is no longer active, and this web site represents a historical view of its activities from 1996-2008. Although there is still mobile-computing research underway at Dartmouth, we no longer update this web site. Please contact David Kotz with any inquiries about the CMC.
[About CMC] [Partners] [Projects] [Papers] [People] [News]
Michael G. Corr and C. M. Okino
March 2001
For further information on geographical information used as an addressing and routing methodology, visit: http://actcomm.dartmouth.edu/~mgcorr/
Overview
The goal of this research project is to develop a sensor module and corresponding network routing scheme for the application of distributed data acquisition networks. Specifically, we consider a network of sensors capable of obtaining, processing, and forwarding data to a central and potentially distant location. Such a network can be used to monitor events such as brush fires, hazardous chemical spills, and violent storms. The concept of independent and distributed collection and processing of sensor data in a geographically distributed topology is defined as a Distributed Smart Sensor Network (DSSN). In this research, we introduce a novel approach of addressing each module purely by its acquired GPS position. Each sensor unit uses a GPS receiver to acquire its current position at a regular interval. The unit's position, within some threshold factor, is then used to identify the unit, analogous to an IP address. Sensor units use their newly acquired address as an identifier for routing and communicating among each other. This idea differs from IP addressing in that the address is not fixed, since it will change as the unit's location changes. To demonstrate the value of this concept, consider the scenario where a number of sensors are scattered in the ocean, gathering localized temperature readings. Due to uncontrollable environmental affects, the sensor network topology is volatile. Therefore, information gathered by the sensors should be location dependent, not identity dependent. As an example, Figure 1(a) depicts data being collected in the shaded region occupied originally by sensor B. After some time, sensor A occupies sensor B's coordinates as depicted in Figure 1(b). This repositioning of the units is transparent to Home due to the geographical nature of the sensor identification.
Figure 1(a): initial state of sensors
Figure 1(b): after sensors have drifted
The Sensor Modules
The smart sensor modules are all identical, in terms of both hardware and software. The homogeneous design eliminates inherent hierarchical dependencies between sensor modules. These modules are composed of fundamental functional blocks that are primarily commercial-off-the-shelf (COTS) parts. Each unit as shown in Figure 2, is equipped with an off-the-shelf microprocessor, RF transceiver, GPS receiver, and sensor. The modular design reduces development cost and time (off-the-shelf parts are readily available and fairly inexpensive), and allows easy replacement or enhancement to meet specific mission goals (e.g. change type of sensor, or replace an RF FM modulation unit with a low power RF spread spectrum unit to minimize the effect of RF jamming and detection). This idea allows for reusability and "reconfigurability" of the same sensors for multiple missions.
Figure 2: Smart Sensor Module
The GAaRP Algorithm
In this section, we briefly describe our routing protocol, GAaRP (Geographical Addressing and Routing Protocol). The routing protocol involves initial acquisition of a GPS position, followed by an RF signal message used to "ignite" communication with modules in RF range. Once a module negotiates and establishes a valid route, the module announces this new route to other modules within RF range. This procedure is repeated in a radial fashion until the entire network is configured relative to a Home position. A cost-function algorithm determines optimal routes based on radial distance, angular difference between multiple candidate routes, number of hops to a Home destination, and number of available slots through the routing node. Link routes are continuously updated on a fixed interval basis.
The development of the GAaRP algorithm takes into account the inherent characteristics of a typical sensor unit: the units have limited power since they run off batteries; the sensor units have limited memory (RAM) and program space (ROM); and transmission ranges are limited thus requiring the ability to forward information in a hop-by-hop manner through several units before reaching an intended destination.
The routing protocol also takes into account the unique characteristics of a typical network in which these sensor units will be deployed: the network is primarily used for data acquisition, not for communication; the network consists of many small sensor units with only one or few central Home terminals; when collecting data from the network, a user (Home) is concerned with geographically where the data comes from and not specifically who it comes from; all sensor data is localized; and the network is polarized (i.e. data communication is one way, from unit to Home while control communication flows the other way, from Home to unit).
Current Results
Recent field-testing of the sensor modules and the GAaRP algorithm involved 6 modules with one used as a Home module. Acquisition times for GPS locations are shown in Figure 3(a). Routing times obtained for the single hop case by varying the number of competing modules are depicted in Figure 3(b).
Figure 3(a): GPS acquisition times
Figure 3(b): Single Hop, Multiple Nodes
Preliminary tests for the multiple-hop scenario indicate that incremental route times decrease as the network approaches a completed routing topology. Specifically, as more sensor units establish routes, the remaining units have a greater chance of establishing a link, thus reducing their individual setup times. In no case was a sensor unit left without a route.
Summary
The project involves extensive field-testing of off-the-shelf equipment, integrated with an innovative routing protocol. Currently, six prototype modules have been placed together with some level of self-routing connectivity tested. Initial results convey a good understanding of the characteristics of the protocol, although there is a need for further optimization and testing to prove the GAaRP protocol as a useful and effective ad-hoc routing scheme.
For further information on geographical information used as an addressing and routing methodology, visit: http://actcomm.dartmouth.edu/~mgcorr/
This research was partially supported by National Science Foundation grant CCR-98113744, Air Force Office of Scientific Research Multidisciplinary University Research Initiative Grant F49620-97-1-0382, and DARPA Contract F30602-98-2-0107.