TY - GEN

T1 - Relay placement for higher order connectivity in wireless sensor networks

AU - Kashyap, Abhishek

AU - Khuller, Samir

AU - Shayman, Mark

PY - 2006/12/1

Y1 - 2006/12/1

N2 - Sensors typically use wireless transmitters to communicate with each other. However, sensors may be located in a way that they cannot even form a connected network (e.g, due to failures of some sensors, or loss of battery power). In this paper we consider the problem of adding the smallest number of additional (relay) nodes so that the induced communication graph is 2-connected1. The problem is N-P-hard. In this paper we develop O(1)-approximation algorithms that find close to optimal solutions in time O((kn)2) for achieving k-edge connectivity of n nodes. The worst case approximation guarantee is 10, but the algorithm produces solutions that are far better than this bound suggests. We also consider extensions to higher dimensions, and the scheme that we develop for points in the plane, yields a bound of 2dM ST where dM ST is the maximum degree of a minimum-degree 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). We also prove that if the sensors are uniformly and identically distributed in a unit square, the expected number of relay nodes required goes to zero as the number of sensors goes to infinity.

AB - Sensors typically use wireless transmitters to communicate with each other. However, sensors may be located in a way that they cannot even form a connected network (e.g, due to failures of some sensors, or loss of battery power). In this paper we consider the problem of adding the smallest number of additional (relay) nodes so that the induced communication graph is 2-connected1. The problem is N-P-hard. In this paper we develop O(1)-approximation algorithms that find close to optimal solutions in time O((kn)2) for achieving k-edge connectivity of n nodes. The worst case approximation guarantee is 10, but the algorithm produces solutions that are far better than this bound suggests. We also consider extensions to higher dimensions, and the scheme that we develop for points in the plane, yields a bound of 2dM ST where dM ST is the maximum degree of a minimum-degree 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). We also prove that if the sensors are uniformly and identically distributed in a unit square, the expected number of relay nodes required goes to zero as the number of sensors goes to infinity.

KW - Approximation algorithms

KW - Fault-tolerant topology design

KW - Relay placement

KW - Sensor networks

UR - http://www.scopus.com/inward/record.url?scp=39049124783&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=39049124783&partnerID=8YFLogxK

U2 - 10.1109/INFOCOM.2006.273

DO - 10.1109/INFOCOM.2006.273

M3 - Conference contribution

AN - SCOPUS:39049124783

SN - 1424402212

SN - 9781424402212

T3 - Proceedings - IEEE INFOCOM

BT - Proceedings - INFOCOM 2006

T2 - INFOCOM 2006: 25th IEEE International Conference on Computer Communications

Y2 - 23 April 2006 through 29 April 2006

ER -