Name
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 paper, 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 maximal vertex subsets in non-GGR graphs whose relative positions are fixed. And this strategy works in any dimension. In the language of structural rigidity theory, our approach corresponds to calculating the ap- proximate kernel of a generic stress matrix for the given graph and distance data. To make our algorithm suitable for real-world application, we also present (i) various techniques for improv- ing the robustness of the algorithm in the presence of measurement noise (ii) an algorithm for detecting maximal subsets of graph vertices whose relative positions are fixed in any generic real- ization 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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1145/1921621.1921630 | ACM Transactions on Sensor Networks (TOSN) |
Keywords | Field | DocType |
structural rigidity theory,novel algorithm,optimisation,localization,np-hard graph realization problem,relative position,sensor network localization,distance data,algorithm robustness,rigidity theory,ggr subgraphs,non-ggr graph,arbitrary generically globally rigid graphs,sensor perturbation,sensor networks,globally linked,certain subsets,rigid graph,certain vertex subsets,generic stress matrix,approximate kernel,perturbed distance data,graph theory,wireless sensor networks,graph vertex,graphs,generic global rigidity,performance,stress,noise measurement,robustness,theory,noise reduction,kernel,sensor network,algorithm,noise | Graph theory,Kernel (linear algebra),Topology,Discrete mathematics,Structural rigidity,Vertex (geometry),Matrix (mathematics),Computer science,Robustness (computer science),Wireless sensor network,Graph realization problem,Distributed computing | Journal |
Volume | Issue | ISSN |
7 | 4 | 1550-4859 |
Citations | PageRank | References |
11 | 0.79 | 20 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yuanchen Zhu | 1 | 20 | 1.37 |
| Steven J. Gortler | 2 | 4205 | 366.17 |
| Dylan Thurston | 3 | 82 | 4.69 |