Abstract:
Determining node and event locations is a canonical task for many wireless network applications. Yet dedicated infrastructure for determining position information is expensive, energyconsuming, and simply unavailable in many deployment scenarios. This paper presents an accurate, cheap and scalable framework, called Sextant, for determining node position and event location in sensor networks. Sextant operates by setting up and solving a system of geographic constraints based on connectivity information from the underlying communication network. Sextant achieves high accuracy by enabling nonconvex constraints to be used to refine position estimates. It represents position estimates as potentially noncontiguous collections of points. This general representation enables Sextant to use _negative information_, that is, information on where a node or event is not located, to refine location estimates. Sextant unifies both node and event detection within the same general framework. It can provide high precision without dedicated localization hardware by aggressively extracting constraints from the link layer, representing areas precisely with Bézierenclosed polygons and probability distributions, and using event detection to refine node position estimates. A compact representation and a fully distributed implementation make the framework practical for resourcelimited devices. The framework has been implemented, deployed and tested on laptops, PDAs and Mica2 motes. Physical experiments show that a large number (98%) of the nodes in a network can determine their positions based on a small number (30%) of landmark nodes and that a large number (90%) of events can be located with low median error.
(a)
(b)
(c)
Figure 1: Use of Bézier curves to represent the area (a) enclosed by a circle, (b) common to two circles, (c) inside one circle but outside another. Control points are represented by filled dots, and the curves by solid lines. Bézier curves provide a precise and compact representation for areas commonly encountered during localization.
Figure 2: Wireless transmission coverage region of a MICA2 mote, shown at center. Area is nonconvex with holes. The boxplot on the left shows the distribution of internode distances for wireless onehop neighbors. The boxplot on the right shows the internode distance distribution for nonneighbors. The substantial overlap motivates conservatively extracting two separate constraints based on r and R.
Figure 3: Illustration of key terms. Node B has estimated location set E_{B}. It can determine its maximal wireless coverage region M_{B}^{W} by taking the union of all circles of radius R centered in E_{B}, and its assured wireless coverage region A_{B}^{W} by taking the intersection of circles of radius r.
P(G_{i}) = γ 
⎛ ⎜ ⎜ ⎝ 

P(G_{i}  D_{B}) 
⎞ ⎟ ⎟ ⎠ 
⎛ ⎜ ⎜ ⎝ 

P(G_{i}  ¬D_{B}) 
⎞ ⎟ ⎟ ⎠ 
P(G_{i}  D_{B})  = 


P(G_{i}  ¬D_{B})  = 

This document was translated from L^{A}T_{E}X by H^{E}V^{E}A.