Abstracts - 2006
Robust Distributed Network Localization and Uncertainty Estimation
David Moore, John Leonard, Daniela Rus & Seth Teller
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.
Our objectives for an effective localization algorithm are that it must be:
Our algorithm  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 . 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.
Robust localization is a valuable tool for the development of low-cost sensor networks for use in location-aware applications and ubiquitous networking . 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.
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 shows the four phases of the algorithm which are as follows:
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.
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.
Our TinyOS implementation of the algorithm and simulation resources have been made freely available for other researchers.
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.
 David Moore, John Leonard, Daniela Rus and Seth Teller. Robust Distributed Network Localization and Uncertainty Estimation. Under review.
 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.
 Seth Teller, Jiawen Chen, and Hari Balakrishnan. Pervasive pose-aware applications and infrastructure. IEEE Computer Graphics and Applications, pp. 14–18, July/August 2003.