RELAY DEPLOYMENT ALGORITHMS IN WIRELESS SENSOR NETWORKS: A SURVEY

Wireless Sensor Networks (WSNs) are subject to failures. Even though reliable routing protocols for WSNs exist and are well-understood, the physical network topology must ensure that alternate routes with an acceptable length to the sinksare in fact available when failures occur. This requires a sensor network deployment to be planned with an objective of ensuring some measure of robustness in the topology, so that when failures do occur the protocols can continue to offer reliable delivery. To ensure that sensor nodes have sufficient paths, it may be necessary to add a number of additional relay nodes, which do not sense, but only forward data from other nodes. In this paper, we review a range of existing algorithms to deploy relay nodes for fault tolerance. We classify the state-of-the-art relay placement algorithms based on routing structures, connectivity requirements, deployment locations, and fault-tolerant requirements.