The Sextant Framework
Sextant is a comprehensive framework for node and event localization in wireless networks.
Many critical applications for wireless networks require determining the physical location of nodes and events in the network. For instance, determining the location of cellphone users, without recourse to energy-intensive GPS-receivers, is a long-standing problem of interest to industry. Similarly, a canonical problem in sensor networks is to determine the location of an event, such as a chemical spill.
Sextant extracts geographic information from cheap, already-present wireless links and can use this information to infer node and event location with high accuracy. Sextant operates by setting up a system of relative geographic constraints among the network participants based on network connectivity and solving this system in a distributed and efficient manner with the aid of absolute position information provided by a small number of landmarks. A landmark is a node whose absolute position is known; Sextant landmarks can be cheap static nodes whose positions are fixed, or they may be mobile nodes equipped with dedicated hardware, such as GPS. We show that the same unified framework can be used to determine both node and event location, and further, show that event localization can be used to improve the fidelity of node location estimates.
There has been much previous work on node localization and event detection. Sextant differentiates itself from this body of work in several ways. First, it does not assume uniform transmission radii (i.e. a unit disk graph) or symmetric connectivity; instead it extracts geographic constraints from the link layer based on a novel, realistic constraint extraction model that accomodates the large percentage of unidirectional links and non-uniform coverage areas encountered in practice. These constraints lead to non-convex solutions, which are typically much more accurate, though more complex, than schemes limited to convex embeddings. They also naturally support event detection with heterogeneous sensors. Second, Sextant explicitly represents node and locations in an expressive manner, using probability distributions over areas defined through Bezier curves. In contrast with much previous work that represented location estimates as points, representing areas explicitly vastly improves localization accuracy, and Bezier curves greatly reduce the amount of space required to represent complex, non-convex areas. Third, Sextant can perform localization even in the presence of approximate information. In contrast with some past work that required landmark nodes in the one-hop neighborhood in order to perform node localization, Sextant can derive accurate constraints even from nodes whose position is not precisely known, and use these estimates to refine the position estimates of other nodes.
Sextant has been deployed and tested Mica-2 motes, handheld PDAs and laptops. The algorithm is practical enough to be deployed on motes, and robust enough to handle non-uniform behavior encountered in real networks.