
Research
Abstracts  2006 
Robust Distributed Network Localization and Uncertainty EstimationDavid Moore, John Leonard, Daniela Rus & Seth TellerOverviewThe 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 twodimensional 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 [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 afterthefact to enhance localization results. PurposeRobust localization is a valuable tool for the development of lowcost sensor networks for use in locationaware 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 humancomputer interfaces. An inexpensive, scalable localization system is desirable to make existing sensor networks locationaware 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. ApproachWe 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:
ResultsWe have tested our algorithm on both largescale simulated networks and smallscale 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 twodimensional 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 locationsupport system, also developed at MIT. Crickets are equipped with a microprocessor, a Radio Frequency (RF) transmitter and receiver, and an ultrasonic transducer and receiver. Internode distances can be computed to an accuracy of approximately 1 centimeter by measuring the Time of Arrival (ToA) of an ultrasound pulse. The onboard microprocessor of a Cricket is sufficiently powerful to implement our localization algorithm onboard 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. Research SupportThis 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 N000140110675, N0001402C0210, and N000140310879, and DARPA TASK program award F306020020585. 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 poseaware applications and infrastructure. IEEE Computer Graphics and Applications, pp. 14–18, July/August 2003. 

