PinPoint Spatial Location Protocols

The development of an efficient lightweight mechanism for determining the spatial layout of a wireless network of nodes has proven elusive. Existing approaches (GPS, acoustic, infrared, radio, etc.) either have poor accuracy and range or are very expensive (e.g. differential GPS) and may require elaborate infrastructure support. PinPoint Technology provides an accurate, rapid, and inexpensive solution to this problem. Specifically, it allows a set of wireless nodes distributed in 3D space to rapidly and accurately determine both the propagation delay between every pair of nodes, and the relative clock drift and offset between every pair of nodes. This, in turn, allows calculation of the inter-node distances, and thus the spatial layout of the nodes, as well as the local clock times at other nodes, and hence the ability to carry out precise synchronized actions. The techniques are based on a novel way of integrating clocks and timers with UHF communications, together with the use of time-based protocols. These time-based protocols (protocols that rely on explicit real-time state) allow a flexible TDMA scheduling of all resources, from UHF media to application. Initial results show that our methods can, with nominal hardware, determine locations to an accuracy of a few centimeters and determine clock differences to an accuracy of a nanosecond. With our current protocols, a set of one hundred nodes within UHF range of each other can learn of their inter-node propagation delays and clock attributes in a few seconds; it would take a few tens of seconds for a set of one thousand nodes. The protocol can be periodically repeated either to reduce errors or to track moving nodes. Speeds of 50 mph can be easily accommodated. The PinPoint method is currently the subject of an NSF ITR proposal, in which we envision applying the technique to

• Geo-location and movement tracking: Given the location of three nodes and their distance to a fourth node, the location of the fourth node can be easily determined by any node possessing this information. This can be used for location determination in sensor networks, for E911 positioning in cellular networks, smart vehicles, location-based routing in ad-hoc networks, etc.
• Ad-Hoc networking: A set of nodes with accurate current estimates of remote node clocks can use flexible TDMA rather than the less efficient CSMA/CA to share the wireless media (the latter being the only currently feasible approach in the absence of a base station). In addition, flexible TDMA in multi-hop wireless networks can be used with current techniques in higher layers (e.g. DSDV in routing, mobile IP, etc), though the most dramatic increases in efficiency can be achieved by extending the time-based approach into the network and transport layers.
• Temporal tomography: By surrounding an object with PinPoint nodes and analyzing the addition delays incurred by signals reflected from or going through the object, one can map the internal and external reflecting surfaces and composition of the object by knowing the speed of waves in different media. To do this at the fine-scale of medical imaging of the human body, picosecond resolution is needed. We propose a ``verniering'' technique that yields the required accuracy while maintaining a cost advantage over current intensity-based approaches such as CAT scans.