Team for Research in
Ubiquitous Secure Technology

Citation
Saikat Guha, Rohan Murty, Emin Gun Sirer. "Sextant: A Unified Node and Event Localization Framework Using Non-Convex Constraints". Proceedings of The International Symposium on Mobile Ad Hoc Networking and Computing (Mobihoc), The International Symposium on Mobile Ad Hoc Networking and Computing (Mobihoc), May, 2005.

Abstract
Determining node and event locations is a canonical task for many wireless network applications. Yet dedicated infrastructure for determining position information is expensive, energy-consuming, 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 non-convex 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´ezier-enclosed 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 resource-limited devices. The framework has been implemented, deployed and tested on laptops, PDAs and Mica-2 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

Electronic downloads

• sextant.pdf · application/pdf · 210 kbytes

• HTML

  Saikat Guha, Rohan Murty, Emin Gun Sirer. <a
  href="http://www.truststc.org/pubs/181.html"
  >Sextant: A Unified Node and Event Localization Framework
  Using Non-Convex Constraints</a>, Proceedings of The
  International Symposium on Mobile Ad Hoc Networking and
  Computing (Mobihoc), The International Symposium on Mobile
  Ad Hoc Networking and Computing (Mobihoc), May, 2005.

• Plain text

  Saikat Guha, Rohan Murty, Emin Gun Sirer. "Sextant: A
  Unified Node and Event Localization Framework Using
  Non-Convex Constraints". Proceedings of The
  International Symposium on Mobile Ad Hoc Networking and
  Computing (Mobihoc), The International Symposium on Mobile
  Ad Hoc Networking and Computing (Mobihoc), May, 2005.

• BibTeX

  @inproceedings{GuhaMurtySirer05_SextantUnifiedNodeEventLocalizationFrameworkUsingNonConvex,
      author = {Saikat Guha and Rohan Murty and Emin Gun Sirer},
      title = {Sextant: A Unified Node and Event Localization
                Framework Using Non-Convex Constraints},
      booktitle = {Proceedings of The International Symposium on
                Mobile Ad Hoc Networking and Computing (Mobihoc)},
      organization = {The International Symposium on Mobile Ad Hoc
                Networking and Computing (Mobihoc)},
      month = {May},
      year = {2005},
      abstract = {Determining node and event locations is a
                canonical task for many wireless network
                applications. Yet dedicated infrastructure for
                determining position information is expensive,
                energy-consuming, 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 non-convex
                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´ezier-enclosed 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
                resource-limited devices. The framework has been
                implemented, deployed and tested on laptops, PDAs
                and Mica-2 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},
      URL = {http://www.truststc.org/pubs/181.html}
  }
  

Posted by Kelly Patwell on 13 Feb 2007.
For additional information, see the Publications FAQ or contact webmaster at www truststc org.