Abstract-Two fundamental functions of the sensor nodes in a wireless sensor network are to sense its environment and to transmit sensed information to a basestation. One approach to prolong sensor network lifetime is to deploy some relay nodes whose main function is to communicate with the sensor nodes, other relay nodes, and the basestations. It is desirable to deploy a minimum number of relay nodes to achieve certain connectivity requirement. In this paper, we study four related fault-tolerant relay node placement problems, each of which has been previously studied only in some restricted form. For each of them, we discuss its computational complexity and present a polynomial time O(1)-approximation algorithm with a small approximation ratio. When the problem reduces to a previously studied form, our algorithm either improves the previous best algorithm or reduces to the previous best algorithm. Keywords: Survivable relay placement, wireless sensor networks. A wireless sensor network (WSN) consists of many lowcost and low-power sensor nodes (SNs) [1] . There has been extensive research on energy aware routing [4, 10, 13, 16, 27] , improvement in lifetime [12, 21, 24, 26] , and survivability [20] . Since energy consumption is proportional to d κ for transmitting over distance d, where κ is a constant in the interval [2, 4], long distance transmission in WSNs is costly. To prolong network lifetime while meeting certain network specifications, researchers have proposed to deploy in a WSN a small number of costly, but more powerful relay nodes (RNs) whose main function is to communicate with the SNs and other RNs [2, 5, 9, 12, 14, 18, 19, 23, 26] . This is the subject of study of this paper. We first review prior works on single-tiered relay node placement, where both SNs and RNs participate in packet forwarding. Cheng et al. [5] proposed to deploy a minimum number of RNs in a WSN so that between every pair of SNs, there is a path consisting of RNs and/or SNs where each hop of the path is no longer than the common transmission range r > 0 of the SNs. This problem is equivalent to the Steiner minimum tree with minimum number of Steiner points and bounded edge length problem (SMT-MSPBEL), defined by Lin and Xue in the study of amplifier placement in optical networks [17] , where they proved the problem is NPhard and presented a minimum spanning tree (MST) based 5-approximation algorithm. In [3], Chen et al. proved that the Lin-Xue algorithm is a 4-approximation algorithm. They also presented a 3-approximation algorithm. In [5], Cheng et al. presented a faster 3-approximation algorithm. In [2], Bredin et al. extended the relay node placement problem studied in [3, 5,
Zhang and Misra REF study four related faulttolerant relay node placement problems and offer a constant polynomial time complexity.
Fault-Tolerant Relay Node Placement in Wireless Sensor Networks: Problems and Algorithms
IEEE INFOCOM 2007 - 26th IEEE International Conference on Computer Communications
IEEE INFOCOM 2007 - 26th IEEE International Conference on Computer Communications
Computer Science