TY - JOUR
T1 - Constrained relay node placement in wireless sensor networks
T2 - Formulation and approximations
AU - Misra, Satyajayant
AU - Hong, Seung Don
AU - Xue, Guoliang
AU - Tang, Jian
N1 - Funding Information:
Manuscript received July 16, 2008; revised March 20, 2009; approved by IEEE/ACM TRANSACTIONS ON NETWORKING Editor M. Liu. First published November 24, 2009; current version published April 16, 2010. This work was supported in part by NSF Grants 0901451 and 0830739 and ARO Grant W911NF-04-1-0385. The information reported here does not reflect the position or the policy of the federal government. This is an extended and enhanced version of the paper [23] that appeared in IEEE INFOCOM 2008.
PY - 2010/4
Y1 - 2010/4
N2 - One approach to prolong the lifetime of a wireless sensor network (WSN) is to deploy some relay nodes to communicate with the sensor nodes, other relay nodes, and the base stations. The relay node placement problem for wireless sensor networks is concerned with placing a minimum number of relay nodes into a wireless sensor network to meet certain connectivity or survivability requirements. Previous studies have concentrated on the unconstrained version of the problem in the sense that relay nodes can be placed anywhere. In practice, there may be some physical constraints on the placement of relay nodes. To address this issue, we study constrained versions of the relay node placement problem, where relay nodes can only be placed at a set of candidate locations. In the connected relay node placement problem, we want to place a minimum number of relay nodes to ensure that each sensor node is connected with a base station through a bidirectional path. In the survivable relay node placement problem, we want to place a minimum number of relay nodes to ensure that each sensor node is connected with two base stations (or the only base station in case there is only one base station) through two node-disjoint bidirectional paths. For each of the two problems, we discuss its computational complexity and present a framework of polynomial time O(1)-approximation algorithms with small approximation ratios. Extensive numerical results show that our approximation algorithms can produce solutions very close to optimal solutions.
AB - One approach to prolong the lifetime of a wireless sensor network (WSN) is to deploy some relay nodes to communicate with the sensor nodes, other relay nodes, and the base stations. The relay node placement problem for wireless sensor networks is concerned with placing a minimum number of relay nodes into a wireless sensor network to meet certain connectivity or survivability requirements. Previous studies have concentrated on the unconstrained version of the problem in the sense that relay nodes can be placed anywhere. In practice, there may be some physical constraints on the placement of relay nodes. To address this issue, we study constrained versions of the relay node placement problem, where relay nodes can only be placed at a set of candidate locations. In the connected relay node placement problem, we want to place a minimum number of relay nodes to ensure that each sensor node is connected with a base station through a bidirectional path. In the survivable relay node placement problem, we want to place a minimum number of relay nodes to ensure that each sensor node is connected with two base stations (or the only base station in case there is only one base station) through two node-disjoint bidirectional paths. For each of the two problems, we discuss its computational complexity and present a framework of polynomial time O(1)-approximation algorithms with small approximation ratios. Extensive numerical results show that our approximation algorithms can produce solutions very close to optimal solutions.
KW - Approximation algorithms
KW - Connectivity and survivability
KW - Relay node placement
KW - Wireless sensor networks (WSNs)
UR - http://www.scopus.com/inward/record.url?scp=77951115837&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77951115837&partnerID=8YFLogxK
U2 - 10.1109/TNET.2009.2033273
DO - 10.1109/TNET.2009.2033273
M3 - Article
AN - SCOPUS:77951115837
SN - 1063-6692
VL - 18
SP - 434
EP - 447
JO - IEEE/ACM Transactions on Networking
JF - IEEE/ACM Transactions on Networking
IS - 2
M1 - 5340573
ER -