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

117 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
CountryUnited 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