Date Added: Feb 2010
In a wireless sensor network, short range multi-hop transmissions are preferred to prolong the network lifetime due to super-linear nature of energy consumption with communication distance. It has been proposed to deploy some relay nodes such that the sensors can transmit the sensed data to a nearby relay node, which in turn delivers the data to the base stations. In general, the relay node placement problems aim to meet certain connectivity and/or survivability requirements of the network by deploying a minimum number of relay nodes. In this paper, the authors study two-tiered constrained relay node placement problems, where the relay nodes can only be placed at some pre-specified candidate locations.