TY - GEN
T1 - Fault-tolerant relay node placement in wireless sensor networks
T2 - IEEE INFOCOM 2007: 26th IEEE International Conference on Computer Communications
AU - Zhang, Weiyi
AU - Xue, Guoliang
AU - Misra, Satyajayant
PY - 2007
Y1 - 2007
N2 - 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.
AB - 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.
KW - Survivable relay placement
KW - Wireless sensor networks
UR - http://www.scopus.com/inward/record.url?scp=34548357224&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=34548357224&partnerID=8YFLogxK
U2 - 10.1109/INFCOM.2007.193
DO - 10.1109/INFCOM.2007.193
M3 - Conference contribution
AN - SCOPUS:34548357224
SN - 1424410479
SN - 9781424410477
T3 - Proceedings - IEEE INFOCOM
SP - 1649
EP - 1657
BT - Proceedings - IEEE INFOCOM 2007
Y2 - 6 May 2007 through 12 May 2007
ER -