Fault-tolerant design of wireless sensor networks with directional antennas

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.