Sensor Network Localization Using Sensor Perturbation

DSpace/Manakin Repository

Sensor Network Localization Using Sensor Perturbation

Show simple item record Zhu, Yuanchen Gortler, Steven J. Thurston, Dylan 2012-09-25T19:04:15Z 2011
dc.identifier.citation Zhu, Yuanchen, Steven J. Gortler and Dylan Thurston. 2011. Sensor network localization using sensor perturbation. ACM Transactions on Sensor Networks 7(4): 36. en_US
dc.identifier.issn 1550-4859 en_US
dc.identifier.issn 1550-4867 en_US
dc.description.abstract Sensor network localization is an instance of the NP-Hard graph realization problem. Thus, methods used in practice are not guaranteed to find the correct localization, even if it is uniquely determined by the input distances. In this article, we show the following: if the sensors are allowed to wiggle, giving us perturbed distance data, we can apply a novel algorithm to realize arbitrary Generically Globally Rigid graphs (GGR), or certain vertex subsets in non-GGR graphs whose relative positions are fixed (which include vertex sets of GGR subgraphs). And this strategy works in any dimension. In the language of structural rigidity theory, our approach corresponds to calculating the approximate kernel of a generic stress matrix for the given graph and distance data. To make our algorithm suitable for real-world applications, we also present: (i) various techniques for improving the robustness of the algorithm in the presence of measurement noise; (ii) an algorithm for detecting certain subsets of graph vertices whose relative positions are fixed in any generic realization of the graph and robustly localizing these subsets of vertices, (iii) a strategy for reducing the number of measurements needed by the algorithm. We provide simulation results of our algorithm. en_US
dc.description.sponsorship Engineering and Applied Sciences en_US
dc.language.iso en_US en_US
dc.publisher Association for Computing Machinery en_US
dc.relation.isversionof doi:10.1145/1921621.1921630 en_US
dc.relation.hasversion en_US
dc.relation.hasversion en_US
dash.license OAP
dc.subject algorithm en_US
dc.subject performance en_US
dc.subject theory en_US
dc.subject generic global rigidity en_US
dc.subject globally linked en_US
dc.subject localization en_US
dc.subject rigidity theory en_US
dc.subject sensor networks en_US
dc.subject sensor perturbation en_US
dc.title Sensor Network Localization Using Sensor Perturbation en_US
dc.type Journal Article en_US
dc.description.version Accepted Manuscript en_US
dc.relation.journal ACM Transactions on Sensor Networks en_US Gortler, Steven J. 2012-09-25T19:04:15Z

Files in this item

Files Size Format View
Zhu_SensorNetwork.pdf 198.5Kb PDF View/Open

This item appears in the following Collection(s)

  • FAS Scholarly Articles [6463]
    Peer reviewed scholarly articles from the Faculty of Arts and Sciences of Harvard University

Show simple item record


Search DASH

Advanced Search