Research Abstracts - 2006

Robust Distributed Network Localization and Uncertainty Estimation

David Moore, John Leonard, Daniela Rus & Seth Teller

Overview

The goal of our research is to design and implement a distributed algorithm for localizing nodes in a sensor network. That is, compute the 2D or 3D position of each node in some coordinate system. We formulate the problem as the two-dimensional graph realization problem shown in Figure 1: given a planar graph with approximately known edge lengths, recover the Euclidean position of each vertex up to a global rotation, translation, and possible reflection. This formulation is applicable to the localization of sensor networks in which each node can estimate the distance to its neighbors, but no absolute position reference such as GPS or fixed anchor nodes is available.

Figure 1 An example of solving the localization problem for range-only measurements.

Our objectives for an effective localization algorithm are that it must be:

• Distributed, Scalable, and Tolerant of Mobility.
• Aware of Uncertainty, so that every position estimate has a corresponding covariance estimate.
• Independent of Beacons of Anchors, such that the algorithm localizes nodes relative to each other even when no references to a global coordinate system are available. However, when anchors are available, they will be seamlessly integrated into the algorithm to improve the localization results.
• Robust, so noise in the input measurements translates predictably into noise in the output localization, without realizing any gross geometry errors.

Our algorithm [1] satisfies the first three objectives by splitting the large optimization problem into smaller subproblems that can be computed by individual nodes with minimal communication. These subproblems are solved in a node's local coordinate system and do not require any global position information from anchor nodes. The number of such subproblems is equal to the number of nodes in the network, so assuming constant node density and communications radius, the total amount of computation will scale linearly with the size of the network. Furthermore, since the subproblems can be solved in parallel, the total computation time is fixed regardless of network size or extent. Once this computation is complete, the local coordinate systems can be optionally related to some global coordinate system using anchor nodes if they are available. The length of time for this final operation depends on communications efficiency and the density of anchor nodes.

Robustness, the fourth objective, is achieved by performing optimization only on subproblems with a good initial estimate. Such an estimate is obtained by localizing nodes in regions constructed from robust quadrilaterals, a novel concept that we first presented in [2]. Localization based on robust quads attempts to prevent incorrect realizations of flip ambiguities that would otherwise corrupt localization computations. Furthermore, the criteria for testing robustness can be adjusted to cope with arbitrary amounts of measurement noise in the system. The drawback of our approach is that under conditions of low node connectivity or high measurement noise, the algorithm may be unable to localize a useful number of nodes. However, poor geometric conditions can often be compensated for by anchor nodes, which our algorithm can use after-the-fact to enhance localization results.

Purpose

Robust localization is a valuable tool for the development of low-cost sensor networks for use in location-aware applications and ubiquitous networking [3]. Reliable position information can be used by higher level applications such as person or object tracking within an environment, autonomous robot navigation, or novel human-computer interfaces. An inexpensive, scalable localization system is desirable to make existing sensor networks location-aware with minimal changes.

The majority of previous research on network localization assumes that some nodes have prior knowledge of their position, either from manual initialization or an outside data source such as GPS. These anchor nodes are then used as a reference point when estimating the position of other nodes. Our algorithm seeks to eliminate the requirement for anchor nodes, allowing complete mobility and ease of deployment. Also often overlooked in previous research is the detrimental effect of measurement noise on localization results. We explicitly keep track of measurement noise and purposefully avoid ambiguities, allowing us to compute an uncertainty estimate for all localized coordinates.

Approach

We define a node's neighbors to be those nodes that have direct bidirectional communications and ranging capability to it. Depending on the type of ranging mechanism used by the network, these two conditions may always be satisfied together. A cluster is a node and its set of neighbors.

Figure 2 The four phases of our localization algorithm.

Figure 2 shows the four phases of the algorithm which are as follows:

Phase I. Cluster Localization

Each node considers itself the origin of its own local coordinate system and roughly localizes its immediate neighbors. Localization is performed incrementally by trilaterating those nodes that participate in a graph of successive robust trilaterations.

Phase II. Cluster Optimization

The positions of a cluster's nodes are optimized using non-linear least squares, using the positions from Phase I as an initial estimate. This optimization redistributes error evenly among the constraints and, as a side effect, produces covariances for the estimated node positions. These covariances depend on both geometry and noise in the underlying distance measurements.

Phase III. Inter-Cluster Transformation

Neighboring clusters find the coordinate transform and covariance between their respective local coordinate systems using non-linear least squares. These quantities can be used to estimate the position and covariance of any node reachable through multiple hops as long as a transformation is available at each hop.

Phase IV. Anchor Node Inclusion

Any node that knows its global position a priori introduces that information into the algorithm to refine the positions of nearby nodes. Adding this information also has the effect of placing the localization results within some known, global coordinate system.

Results

We have tested our algorithm on both large-scale simulated networks and small-scale physical networks in order to evaluate its performance under varying amounts of noise, node connectivity, mobility, and environment shapes. Localization results for a simulated network are shown in Figure 3, consisting of a simple two-dimensional square region with an obstruction in the middle. 200 nodes are placed uniformly and randomly in the region and each node can measure the distance to any within a specified radius. Gaussian noise with fixed variance is added to all distance measurements. The network is localized in the global coordinate system using three anchor nodes.

Figure 3 Our localization algorithm applied to a simulated network of 200 nodes. Blue ellipses depict the covariance estimate of each localized node and red lines indicate the error from ground truth. The dashed circle indicates the maximum communications radius.

For physical experiments, we make use of a platform for sensor network experimentation, the Cricket location-support system, also developed at MIT. Crickets are equipped with a microprocessor, a Radio Frequency (RF) transmitter and receiver, and an ultrasonic transducer and receiver. Inter-node distances can be computed to an accuracy of approximately 1 centimeter by measuring the Time of Arrival (ToA) of an ultrasound pulse. The on-board microprocessor of a Cricket is sufficiently powerful to implement our localization algorithm on-board using TinyOS, enabling a truly distributed sensor network. Figure 4 shows a video of the network localization in action on a real sensor network.

Figure 4 A video (click to play) showing the real-time localization of a sensor network, including the tracking of a mobile robot with the same algorithm.

Our TinyOS implementation of the algorithm and simulation resources have been made freely available for other researchers.

Research Support

This work was funded by a grant from Project Oxygen and supported in part by a National Science Foundation Graduate Research Fellowship. Additional funding was provided in part by the Institute for Security Technology Studies (ISTS) at Dartmouth College, NSF award 0225446, ONR awards N00014-01-1-0675, N00014-02-C-0210, and N00014-03-1-0879, and DARPA TASK program award F30602-00-2-0585.

References:

[1] David Moore, John Leonard, Daniela Rus and Seth Teller. Robust Distributed Network Localization and Uncertainty Estimation. Under review.

[2] David Moore, John Leonard, Daniela Rus and Seth Teller. Robust Distributed Network Localization with Noisy Range Measurements. In Proceeedings of the Second ACM Conference on Embedded Networked Sensor Systems (SenSys '04), pp. 50–61, Baltimore, MD, November 2004.

[3] Seth Teller, Jiawen Chen, and Hari Balakrishnan. Pervasive pose-aware applications and infrastructure. IEEE Computer Graphics and Applications, pp. 14–18, July/August 2003.