Fault-tolerant relay node placement in wireless sensor networks: Formulation and approximation

Bin Hao, Jian Tang, Guoliang Xue

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

118 Scopus citations

Abstract

A two-tiered network model has been proposed recently for prolonging lifetime and improving scalability in wireless sensor networks. This two-tiered network is a cluster-based network. Relay nodes are placed in the playing field to act as cluster heads and to form a connected topology for data transmission in the higher tier. They are able to fuse data packets from sensor nodes in their clusters and send them to sinks through wireless multi-hop paths. However, this model is not fault-tolerant as the network may be disconnected if a relay node fails. In this paper, we formulate and study a fault-tolerant relay node placement problem in wireless sensor networks. In this problem, we want to place a minimum number of relay nodes to the playing field of a sensor network such that (1) each sensor node can communicate with at least two relay nodes and (2) the network of the relay nodes is 2-connected. We present a polynomial time approximation algorithm for this problem and prove the worst-case performance given by our algorithm is bounded within O(D log n) times of the size of an optimal solution, where n is the number of sensor nodes in the network, D is the (2, 1) - Diameter of the network formed by a sufficient set of possible positions for relay nodes.

Original languageEnglish (US)
Title of host publication2004 Workshop on High Performance Switching and Routing, HPSR 2004
Pages246-250
Number of pages5
StatePublished - Jun 22 2004
Externally publishedYes
Event2004 Workshop on High Perfomance Switching and Routing, HPSR 2004 - Phoenix, AZ, United States
Duration: Apr 19 2004Apr 20 2004

Publication series

NameIEEE Workshop on High Performance Switching and Routing, HPSR

Other

Other2004 Workshop on High Perfomance Switching and Routing, HPSR 2004
Country/TerritoryUnited States
CityPhoenix, AZ
Period4/19/044/20/04

Keywords

  • Fault-tolerance
  • Relay node placement
  • Wireless sensor network

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint

Dive into the research topics of 'Fault-tolerant relay node placement in wireless sensor networks: Formulation and approximation'. Together they form a unique fingerprint.

Cite this