Search:

Sensor Self-Localization

Summary

In this project we have implemented a robust distributed received signal strength (RSS)-based localization algorithm on a testbed network of wireless (Crossbow mica2) sensors. We have deployed the testbed in indoor and outdoor settings and demonstrated robust performance and errors on the order of, or even less than, 1 meter. We are currently adding features to speed the deployment time of the system when it is installed in new environments.

Motivation

Many wireless sensor networks applications, such as environmental monitoring, animal tracking, locating positions of articles in a large warehouse, geographical routing, and security 'panic button', require automatic location estimation. Using GPS-enabled devices is generally not an option due to cost and energy concerns and its limitation to outdoor environments. Enabling self-localization of wireless sensors is a desirable alternative. Each sensor estimates its relative position with respect to its closest neighbors, and then sensors collaboratively calculate a global map of the network.

In our implementation, each sensor measures received signal strength (RSS) of the messages it overhears. From RSS, a sensor calculates distance, assuming a d^{-n_p} large-scale path loss model [Rappaport 96]. According to this model, the mean received power at a distance d, \bar{P}(d) (dBm) is given as:

\bar{P}(d) = \Pi_0 - 10n_p \log \frac{d}{\Delta_0}

where \Pi_0 is the mean received power in dBm at a reference distance \Delta_0, and n_p is the path loss exponent (2 in free space). The received power between two sensor nodes i and j, P_{i,j}, is then modeled as a log-normal random variable,

P_{i,j} \sim \mathcal{N}\left(\bar{P}(d_{i,j}) , \sigma_{dB}^2 \right)
,

where \sigma_{dB} is the standard deviation of the shadowing loss. Before deployment in a new type of environment, a measurement set must used to estimate the constants \{n_p,\Pi_0\}.

Given these models, the maximum likelihood estimator (MLE)of distance given P_{i,j} is

\delta_{i,j}^{MLE} = \Delta_0 10^{\frac{P_0-P_{i,j}}{10n_p}}
.

Algorithm specification and implementation

We have implemented a Gossip version of the Distributed Weighted Multi-Dimensional Scaling (dwMDS) algorithm proposed in [Costa 04, Costa 06] in the sensor network testbed (of mica2 sensors). The contribution of this project is a TinyOS/NesC embedded program dwMDS which implements the proposed algorithm. The specifications of our implementation are:

• True Distributed Operation: No laptop or central processor is used in the self-localization process.
• Synchronization: Nodes synchronize to the fastest neighbor clock
• Periodicity: Nodes operate periodically, with each period divided into two parts:
1. Silent Period: Time to change frequency and update dwMDS calculations
2. Transmission Period: Time for sensors to transmit one packet, and to listen for their neighbors' packets. A TDMA MAC protocol enables interference-free reception.
• RSS data: Nodes send measured RSS values and the node ID of its eight nearest neighbors.
• Coordinate Data: Nodes also send two independent coordinate estimates, the "best" estimate and an "alternate" estimate (which can swapped with the best estimate).
• Packet Reception: Nodes record the RSS, transmitter node ID, and current frequency of each received packet. Later, nodes calculate the average RSS over frequency and time. Each node also records what its neighbors measure for the RSS of its own transmissions, enabling reciprocal averaging.
• Frequency Hopping: The frequency band of mica2 is divided into 14 different slots separated by 2 MHz, greater than the coherence bandwidth of the channel. Sensor nodes hop over these frequency bands in a predetermined order.

As indicated above, the variance of fading is reduced by three types of averaging:

1. Frequency averaging: The RSS values collected at 14 different frequency slots are (dB) averaged.
2. Time averaging: Multiple measurements over time are averaged.
3. Reciprocal averaging: Both p_{i,j} and p_{j,i} are averaged.

Results

An initial test involved placing 36 nodes in a 6 by 6 grid, deployed over a 6.7 by 6.7 meter area, on a grassy lawn. The measurement area is shown in Figure 1.

 Fig 1: Photo of initial test area.

The nodes estimated their location with an RMS location error of 55.3 cm [1]. Figure 2 shows the estimated sensor positions (X) compared to the actual sensor positions (O). The four sensors in the corners were used as reference devices (which had been given a priori their known positions).

 Fig 2: Initial test results, estimated locations (X) compared to actual locations (O).

Demonstration

We further demonstrated our implementation of dwMDS algorithm in SenSys'06, Boulder, CO, Nov. 1-3, 2006 [Patwari 06]. The nodes were arranged in a square area, with reference devices in the corners of the area. The nodes were placed on boxes, which were filled with packing peanuts. Since each node calculates its own coordinate but only has three LEDs as output, we divided the grid area into 8 areas and use LEDs (R Y G) to encode the area in which its coordinate estimate falls.

 Fig 3: The 8 areas into which the deployed sensor grid is divided

Current Research and Development:

It has been observed that RSS measurements in mica2 nodes are non-linear due to RSSI circuit saturation characteristics. Current work is making the algorithm and implementation more robust to the variations in TX power. Further, we are investigating distributed network estimation of the constants \{n_p,\Pi_0\} at deployment, so that no separate measurements are necessary to model a new environment. Future updates will be posted here.

Code Availability

TinyOS/NesC code used in the demonstration is available by email to the contributors.

Contributors

• Neal Patwari
• Piyush Agrawal