Localization and Synchronization

A sensor reading is rarely useful without information about when and where it was made. Imagine if we didn't know the location of a weather station where a preciptation measurement was made, or its timestamp. In this case, the best a weather man could do is to tell us that it was raining at some point, somewhere!

Sensor nodes, whose sole purpose is to sense the world around them and process that information with the help of their neighbors, also need to know their location in time and space. However, localizing sensor nodes can be more difficult than localizing weather stations because there may be thousands of small, identical sensor nodes deployed randomly over an area. It would be too time consuming for someone to go through and locate each of them by hand. Instead, sensor nodes must determine their position entirely on their own by monitoring their sensor readings and collaborating with their neighbors. Furthermore, as nodes determine their location, they must also synchronize their clocks with the clocks on other nodes so that the network shares a common time base. These problems of localization and synchronization are current subjects of research on the Pushpin Computing platform.

We have studied several techniques for localizing sensor nodes including lateration, spectral graph drawing, and mesh relaxation. Our algorithms use distance constraints that are measurements to global sensor events. An example of a global sensor event would be a lightning strike and a thunderclap in a thunderstorm. Each node in the network can measure its distance to this event by measuring the time between when it sees the lightning and hears the thunder, and divides that by the speed of sound. We generate similar events in our network using a hybrid camera-flash/ultasound transmitter device called the pinger. These signals are detected with the ultrasound time-of-flight sensor module. Using a simplo lateration implementatin (which is essentially triangulation), we have been able to demonstrate localization error of merely 4-cm (with a standard deviation of approx. 3-cm) in the Pushpin hardware testbed.

Papers:

• [PDF] Michael Broxton, Master of Engineering thesis proposal, 2004.

Videos:

• [MOV] A video showing Pushpin localization using lateration. First, three points of correspondence are created by triggering the Pinger at different locations. After each Ping, the Pushpin nearest to the Ping is chosen as an anchor node in a distributed, ad-hoc election and its position is computed using simple right triangle equalities. Once three events and three anchors exist, the remaining nodes are localized using lateration. To demonstrate that the nodes are correctly localized, the nodes participate in a distributed display task in which they animate an imaginary vertical line moving from -x to +x in the coordinate system. Nodes to the left of the line color themselves red, while nodes to the right of the line color themselves green.