University of Illinois Urbana-Champaign

Localization of Sparse Sensor Networks Using Layout Information

Sundresh, Sameer; Kwon, YoungMin; Mechitov, Kirill; Kim, Wooyoung; Agha, Gul A.

Content Files
Localization of Sparse Sensor Networks Using Layout Information.pdf

Permalink

https://hdl.handle.net/2142/10973

Description

Title
Localization of Sparse Sensor Networks Using Layout Information
Author(s)
  • Sundresh, Sameer
  • Kwon, YoungMin
  • Mechitov, Kirill
  • Kim, Wooyoung
  • Agha, Gul A.
Issue Date
2005-03
Keyword(s)
sensor networks
Date of Ingest
2009-04-17T16:19:19Z
Abstract
Localization is the process by which sensor networks associate spatial position information with individual sensors' measurements. While manual surveying is sufficient for small-scale prototypes, it is too time-consuming and costly for the large-scale deployments anticipated in the near future. Our experiments with medium-scale outdoor sensor network deployments show that sparsity of ranging measurements is a key factor limiting the accuracy of localization; often, several solutions are equally consistent with the data. Fortunately, layout information can usually be obtained at little extra cost; for example, if it is used to guide the deployment process, or by analyzing a photograph of the network. We have developed an algorithm based on subgraph isomorphism which uses the known layout information in conjunction with ranging measurements to find a family of localization solutions for a sensor network deployment. Although subgraph isomorphism is in general NP-complete, the more specific cases that occur in real-world scenarios are usually tractable. Experiments with a 50-node network show that our algorithm is very efficient in practice.
Type of Resource
text
Genre of Resource
Technical Report
Permalink
http://hdl.handle.net/2142/10973
Copyright and License Information
You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the University of Illinois at Urbana-Champaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s).

Owning Collections

Research and Tech Reports - Computer Science PRIMARY