KIT | KIT-Bibliothek | Impressum | Datenschutz

Maximum Rigid Components as Means for Direction-Based Localization in Sensor Networks

Katz, Bastian; Gaertler, Marco; Wagner, Dorothea

Abstract:
Many applications in sensor networks require positional
information of the sensors. Recovering node positions is closely
related to graph realization problems for geometric graphs.
Here, we address the case where nodes have angular information.
Whereas Bruck et al. proved that the corresponding realization
problem together with unit-disk-graph-constraints is NP-hard
[2], we focus on rigid components which allow both efficient
identification and fast, unique realizations.
Our technique allows to identify maximum rigid components in
graphs with partially known rigid components using a reduction
to maximum flow problems. This approach is analyzed for the
two-dimensional case, but can easily be extended to higher
dimensions.

Open Access Logo


Volltext §
DOI: 10.5445/IR/1000005767
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Forschungsbericht
Jahr 2006
Sprache Englisch
Identifikator ISSN: 1432-7864
urn:nbn:de:swb:90-57679
KITopen-ID: 1000005767
Verlag Universität Karlsruhe, Karlsruhe
Serie Interner Bericht. Fakultät für Informatik, Universität Karlsruhe ; 2006,17
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page