Relay placement for higher order connectivity in wireless sensor networks

Abhishek Kashyap*, Samir Khuller, Mark Shayman

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

113 Scopus citations


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.

Original languageEnglish (US)
Title of host publicationProceedings - INFOCOM 2006
Subtitle of host publication25th IEEE International Conference on Computer Communications
StatePublished - 2006
EventINFOCOM 2006: 25th IEEE International Conference on Computer Communications - Barcelona, Spain
Duration: Apr 23 2006Apr 29 2006

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X


OtherINFOCOM 2006: 25th IEEE International Conference on Computer Communications


  • Approximation algorithms
  • Fault-tolerant topology design
  • Relay placement
  • Sensor networks

ASJC Scopus subject areas

  • General Computer Science
  • Electrical and Electronic Engineering


Dive into the research topics of 'Relay placement for higher order connectivity in wireless sensor networks'. Together they form a unique fingerprint.

Cite this