Overview

The goal of this research is to develop the foundations for creating physical embeddings with mobile networks of robots and sensors. Specifically, we are developing power and communication efficient robust methods for localization of mobile sensors. Most currently employed localization techniques rely on the network having a certain number of beacons or "anchors" of known location. This requires tedious setup or the use of GPS to get precise node location. GPS, however, is not available in many of the areas of interest such as indoors or underwater. The methods we are developing localize nodes in mobile sensor networks without the use of anchors which removes the requirement for GPS-like devices. We use, for example, MIT Crickets [1] which support inter-node ranging by timing the difference in flight time of RF and ultra-sound which allows us to localize nodes in a distributed manner.

Robust Localization

Traditional localization methods, such as least squares minimization and simple multilateration, frequently fail to accurately localize nodes due to flip or flex ambiguities. We avoid these types of problems by extending the idea of robust localization developed by Moore et al. [2] in two dimensions to three dimensions. As seen in the figure below, if we have all of the inter-node distances but do not use the measurement CD, then there are two realizations of D, namely D and D'.

If the measurement CD is ignored then there is an alternate realization of D, namely D'. Similarly, if the distance CD nearly equal to CD' (within measurement errors), then we cannot localize D.

This type of error can be avoided by requiring that we know and use all inter-node distances. However, what we find is that if the measurement CD is close to CD' (within measurement errors), we will again be unable to correctly localize D. Since we are working with real systems this measurement error must be taken into account, something that traditional localization methods fail to do.

Our technical approach relies on the use of robust hexahedron, where robustness can be formulated as a geometric condition on the angles and side lengths. Given a robust hexahedron we are guaranteed to localize all of its vertices. The trade-off is that not all of the nodes in the system will be localized. Our approach is fully distributed and supports partial mobility of nodes. A moving node requires at least four static nodes during localization. We are currently looking at how to characterize the performance of our algorithm when there are multiple moving nodes. Additionally, we plan on developing robust localization algorithms that work in environments with predominately moving nodes.

Test System

We will be using and testing our localization methods on Shady, a robotic sunshade [3]. Shady is being developed to act as a sunshade for a large wall-window in a lab workspace. In order to accurately and dynamically shade an area (such as a computer monitor) the robot must know its own location on the window, the location to be shaded, and the position of the sun. The location of Shady and the area to be shaded can be determined using our localization methods.

This real world test of this system will have many challenges that will test the limits of our robust localization method. The environment is cluttered with many partitions which will interfere with the ranging mechanism. Additionally, as the shading robot is a robot that may be used in other areas of the Stata Center the localization system will have to be robust enough to work without having to carefully place the nodes. Finally, the effects of nodes in motion will need to be further explored as some of the nodes will be moving.

Research Support

Oxygen, NSF, Boeing, and Intel.

References:

[1] Nissanka B. Priyantha, Anit Chakraborty and Hari Balakrishnan. The Cricket location-support system. Mobile Computing and Networking. pp. 32--43. 2000.

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

[3] Carrick Detweiler, Alex Hornstein, Keith Kotay, Peter Osagie, Daniela Rus, Paulina Varshavskaya, Iuliu Vasilescu, Marsette A. Vona, Justin Werfel, and Yeoreum Yoon. Shady: A Robotic Sunshade. In CSAIL Research Abstracts, 2005.