Localization of Sparse Sensor Networks Using Layout Information
Sundresh, Sameer; Kwon, YoungMin; Mechitov, Kirill; Kim, Wooyoung; Agha, Gul A.
- Localization of Sparse Sensor Networks Using Layout Information
- Sundresh, Sameer
- Kwon, YoungMin
- Mechitov, Kirill
- Kim, Wooyoung
- Agha, Gul A.
- Issue Date
- sensor networks
- 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
- 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).
Edit Collection Membership