Abstract
A tree structure is often used in wireless sensor networks to deliver 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 if no node fails. We study the problem of enhancing the fault tolerance of a data gathering tree by adding additional links so that failure of a sensor or a pair of adjacent sensors would not disconnect the tree. We prove that the least-cost tree augmentation problem is NP-complete and provide approximation algorithms one for single node failure and the other for a pair of adjacent node failure, with performance bounds of two and four respectively.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 258-271 |
| Number of pages | 14 |
| Journal | Pervasive and Mobile Computing |
| Volume | 13 |
| DOIs | |
| State | Published - Aug 2014 |
Keywords
- Directional antenna
- Region based fault
- Tree connectivity augmentation problem
ASJC Scopus subject areas
- Software
- Information Systems
- Hardware and Architecture
- Computer Science Applications
- Computer Networks and Communications
Fingerprint
Dive into the research topics of 'Fault-tolerant design of wireless sensor networks with directional antennas'. Together they form a unique fingerprint.Cite this
- APA
- Standard
- Harvard
- Vancouver
- Author
- BIBTEX
- RIS