Fault-tolerant design of wireless sensor networks with directional antennas

Shahrzad Shirazipourazad, Arunabha Sen, Subir Bandyopadhyay

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


A tree structure is often used in wireless sensor networks to deliver collected sensor data to a sink node. Such a tree can be built using directional antennas as they offer considerable advantage over the omni-directional ones. A tree is adequate for data gathering from all sensor nodes as long as no node in the tree fails. Since the connectivity of the tree is one, failure of any one node disconnects the tree and may disable the sink node from collecting data from some of the sensor nodes. In this paper we study the problem of enhancing the fault tolerance capability of a data gathering tree by adding a few additional links so that the failure of any one sensor would not disconnect the tree. Assuming that the addition of each link to the tree involves some cost, we study the problem of least-cost augmentation of the tree, so that even after failure of a single node, all the surviving nodes will remain connected to the sink node. We prove that the least-cost tree augmentation problem is NP-complete. Moreover, we provide an approximation algorithm with performance bound of two. The experimental evaluations of the algorithm demonstrate that the approximation algorithm performs even better in practice and almost always produces near-optimal solution.

Original languageEnglish (US)
Title of host publicationDistributed Computing and Networking - 14th International Conference, ICDCN 2013, Proceedings
Number of pages15
StatePublished - Dec 1 2013
Event14th International Conference on Distributed Computing and Networking, ICDCN 2013 - Mumbai, India
Duration: Jan 3 2013Jan 6 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7730 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other14th International Conference on Distributed Computing and Networking, ICDCN 2013

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Fault-tolerant design of wireless sensor networks with directional antennas'. Together they form a unique fingerprint.

Cite this