Back to Search
Start Over
Relay placement for fault tolerance in wireless networks in higher dimensions
- Source :
-
Computational Geometry . May2011, Vol. 44 Issue 4, p206-215. 10p. - Publication Year :
- 2011
-
Abstract
- Abstract: In this paper we consider the problem of adding the smallest number of additional (relay) nodes to a network of static nodes with limited communication range so that the induced communication graph is 2-connected (we consider both edge and vertex connectivity). The problem is NP-hard. We develop algorithms that find close to optimal solutions for both edge and vertex connectivity. We prove the algorithms have an approximation ratio of 2M for nodes distributed in a d-dimensional Euclidean space, where M is the maximum node degree of a Minimum Spanning Tree in d dimensions using Euclidean metrics. In addition, our methods extend with the same approximation guarantees to a generalization when the locations of relays are required to avoid certain polygonal regions (obstacles). [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 09257721
- Volume :
- 44
- Issue :
- 4
- Database :
- Academic Search Index
- Journal :
- Computational Geometry
- Publication Type :
- Academic Journal
- Accession number :
- 57533384
- Full Text :
- https://doi.org/10.1016/j.comgeo.2010.11.002