Relay Placement Approximation Algorithms for k-Connectivity in Wireless Sensor Networks

Abstract

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 k-connected. The problem is NP-hard. We develop algorithms that find close to optimal solutions for both edge and vertex connectivity. For k-connectivity between sensor nodes, we prove the algorithms have an approximation ratio of O(k2) for vertex connectivity and O(k) for edge connectivity. 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 prove that the algorithms for k-connectivity between sensor and relay nodes have an approximation ratio of O(k3) for vertex connectivity and O(k2) for edge connectivity.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 2006
Accession Number
ADA455438

Entities

People

  • Abhishek Kashyap
  • Mark Shayman
  • Samir Khuller

Organizations

  • University of Maryland

Tags

Communities of Interest

  • Energy and Power Technologies
  • Materials and Manufacturing Processes
  • Sensors

DTIC Thesaurus Topics

  • Algorithms
  • Computer Science
  • Detectors
  • Engineering
  • Equations
  • Fault Tolerance
  • Guarantees
  • Information Operations
  • Mathematics
  • Network Topology
  • Networks
  • Sensor Networks
  • Terminals
  • Three Dimensional
  • Topology
  • Universities
  • Wireless Sensor Networks

Fields of Study

  • Computer science

Readers

  • Computer Networking
  • Graph Algorithms and Convex Optimization.