Constrained Relay Node Placement in Wireless Sensor Networks to Meet Connectivity and Survivability Requirements

Abstract

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 and survivability requirements. We study constrained versions of the relay node placement problem, where relay nodes can only be placed at a subset of candidate locations. In the connected relay node placement problem, we want to place a minimum number of relay nodes to ensure the connectivity of the sensor nodes and the base stations. In the survivable relay node placement problem, we want to place a minimum number of relay nodes to ensure the biconnectivity of the sensor nodes and the base stations. 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.