TY - JOUR
T1 - Relay placement for fault tolerance in wireless networks in higher dimensions
AU - Kashyap, Abhishek
AU - Khuller, Samir
AU - Shayman, Mark
N1 - Funding Information:
✩ This research was partially supported by AFOSR under grant F496200210217, NSF under grant CNS-0435206, NSF CCF-0430650, NSF CNS-0519554. A preliminary version of this work (containing approximation analysis for networks in Euclidean plane) was published in Kashyap et al. (2006) [15]. The work was also published in first author’s Ph.D. thesis (Kashyap, 2006) [14]. * Corresponding author. E-mail addresses: [email protected] (A. Kashyap), [email protected] (S. Khuller), [email protected] (M. Shayman).
PY - 2011/5
Y1 - 2011/5
N2 - 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).
AB - 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).
KW - Fault tolerance
KW - Network connectivity
UR - http://www.scopus.com/inward/record.url?scp=78751641738&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=78751641738&partnerID=8YFLogxK
U2 - 10.1016/j.comgeo.2010.11.002
DO - 10.1016/j.comgeo.2010.11.002
M3 - Article
AN - SCOPUS:78751641738
SN - 0925-7721
VL - 44
SP - 206
EP - 215
JO - Computational Geometry: Theory and Applications
JF - Computational Geometry: Theory and Applications
IS - 4
ER -