Localization of Sparse Sensor Networks Using Layout Information

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

Permalink

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

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

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

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