Relay node placement in wireless sensor networks

A wireless sensor network (WSN) is composed of many low cost sensor nodes that can perform sensing, simple computation, and short range communications. To maximize the life time of a WSN, relay nodes are placed to perform communication. In the single-tiered relay node placement problem, the sensor nodes can also participate in the forwarding of the packets of other nodes. In the two-tiered relay node placement problem, only the relay nodes forwards the packets from other nodes. In this talk, we will present the state of the art in the area of relay node placement, ranging from coverage to connectivity and to survivability, and from unconstrained problem to constrained problem. In most cases, efficient approximation algorithms are known.