On Enhancing Fault Tolerance of Virtual Backbone in a Wireless Sensor Network with Unidirectional Links

Ravi Tiwari () and My T. Thai ()
Additional contact information
Ravi Tiwari: University of Florida
My T. Thai: University of Florida

A chapter in Sensors: Theory, Algorithms, and Applications, 2012, pp 3-18 from Springer

Abstract: Abstract A wireless sensor network (WSN) is a collection of energy constrained sensor node forming a network which lacks infrastructure or any kind of centralized management. In such networks, virtual backbone has been proposed as the routing infrastructure which can alleviate the broadcasting storm problem occurring due to consistent flooding performed by the sensor node, to communicate their sensed information. As the virtual backbone nodes needs to carry other nodes’ traffic, they are more subject to failure. Hence, it is desirable to construct a fault tolerant virtual backbone. Most of recent research has studied this problem in homogeneous networks. In this chapter, we propose solutions for efficient construction of a fault tolerant virtual backbone in a WSN where the sensor nodes have different transmission ranges. Such a network can be modeled as a disk graph (DG), where link between the two nodes is either unidirectional or bidirectional. We formulate the fault tolerant virtual backbone problem as a k-Strongly Connected m-Dominating and Absorbing Set (k, m) SCDAS problem. As the problem is NP-hard, we propose an approximation algorithm along with the theoretical analysis and conjectured its approximation ratio.

Keywords: Virtual Backbone; Disk Graph (DG); Sensor Nodes; Transmission Range; Augmenting Path (search for similar items in EconPapers)
Date: 2012
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:spochp:978-0-387-88619-0_1

Ordering information: This item can be ordered from
http://www.springer.com/9780387886190

DOI: 10.1007/978-0-387-88619-0_1

Access Statistics for this chapter

More chapters in Springer Optimization and Its Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().