TY - GEN

T1 - Fault-tolerant relay node placement in wireless sensor networks

T2 - 2004 Workshop on High Perfomance Switching and Routing, HPSR 2004

AU - Hao, Bin

AU - Tang, Jian

AU - Xue, Guoliang

PY - 2004/6/22

Y1 - 2004/6/22

N2 - 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.

AB - 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.

KW - Fault-tolerance

KW - Relay node placement

KW - Wireless sensor network

UR - http://www.scopus.com/inward/record.url?scp=2942525470&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=2942525470&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:2942525470

SN - 0780383753

SN - 9780780383753

T3 - IEEE Workshop on High Performance Switching and Routing, HPSR

SP - 246

EP - 250

BT - 2004 Workshop on High Performance Switching and Routing, HPSR 2004

Y2 - 19 April 2004 through 20 April 2004

ER -