Fault-tolerant relay node placement in wireless sensor networks: Formulation and approximation

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.