Robust Distributed Sensor Network Localization
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 relative to each other. We formulate the problem as the two-dimensional graph realization problem: 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.
We introduce the notion of robust quadrilaterals in order to label certain subgraphs as rigid and uniquely localizable even when the network as a whole may not have a unique realization. We propose a distributed algorithm that finds robust subgraphs of the input graph, and solves for position estimates by connecting these subgraphs in a way that is tolerant to distance measurement noise. Our algorithm runs in linear time with the number of nodes in the network, assuming all nodes have O(1) neighbors. The algorithm handles arbitrary measurement noise by adjusting its robustness parameters. In addition to the node positions, the algorithm also computes error bounds for each position estimate so that the algorithm and user are fully aware of any localization uncertainty. An implementation of the algorithm is demonstrated to produce accurate localizations for a variety of graphs, including those arising from real-world node placement strategies .
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.
At a high level, our network localization algorithm works as follows. Each node measures distances to neighboring nodes and then shares these measurements with its neighbors. We then find all sets of four nodes that are fully connected by distance measurements and are "well-spaced" such that even in the presence of measurement noise, their relative positions are unambiguous. We adopt this 4-vertex quadrilateral as the smallest subgraph that can be uniquely realized, and define it as robust. Additional 4-vertex quads can be "chained" to the original quad if they have 3 nodes in common with it. This approach allows each chained quad to localize its fourth node based on the 3 known positions common to the two quads. Figure 1 depicts an illustrative run of our algorithm.
A key innovation of this paper is the use of the 4-vertex robust quadrilateral as a means to tolerate noise, enabling our algorithm to compute unique realizations for graphs that might otherwise be ambiguous. Another important feature of our algorithm is that each cluster (consisting of a node and its neighbors) is localized in its own coordinate system. Clusters can then be connected by chaining coordinate transformations in an on-line fashion to localize nodes several hops apart.
We have tested our algorithm on both large-scale simulated networks and medium-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 2, consisting of a simple two-dimensional square region 15 meters on a side. One hundred nodes are placed uniformly and randomly in the region and each node can measure the distance to any node within a specified distance. Gaussian noise with a fixed variance is added to all distance measurements.
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 3 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.
Our future research will focus on two main areas: Physical realization of a practical self-localizing sensor network and greater understanding of the error characteristics in such a network. In the first area, we are collaborating with other research groups at MIT to pursue the use of Ultrawideband (UWB) radio for an accurate and scalable sensor network ranging capability. The second area of future research is being pursued through a more rigorous application of probability theory to our algorithm. Lastly, a useful extension of this work is use robustness as a means to compute the optimal placement of additional nodes so that network deployment may be motivated for maximum localization accuracy.
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 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.