  The Delay Constrained Relay Node Placement (DCRNP) problem in Wireless Sensor
Networks (WSNs) aims to deploy minimum relay nodes such that for each sensor
node there is a path connecting this sensor node to the sink without violating
delay constraint. As WSNs are gradually employed in time-critical applications,
the importance of the DCRNP problem becomes noticeable. For the NP-hard nature
of DCRNP problem, an approximation algorithm-Set-Covering-based Relay Node
Placement (SCA) is proposed to solve the DCRNP problem in this paper. The
proposed SCA algorithm deploys relay nodes iteratively from sink to the given
sensor nodes in hops, i.e., in the $k$th iteration SCA deploys relay nodes at
the locations that are $k$ hops apart from the sink. Specifically, in each
iteration, SCA first finds the candidate deployment locations located within 1
hop to the relay nodes and sensor nodes, which have already been connected to
the sink. Then, a subset of these candidate deployment locations, which can
guarantee the existence of paths connecting unconnected sensor nodes to the
sink within delay constraint, is selected to deploy relay nodes based on the
set covering method. As the iteration of SCA algorithm, the sensor nodes are
gradually connected to the sink with satisfying delay constraint.
  The elaborated analysis of the approximation ratio of SCA algorithm is given
out, and we also prove that the SCA is a polynomial time algorithm through
rigorous time complexity analysis. To evaluate the performance of the proposed
SCA algorithm, extensive simulations are implemented, and the simulation
results show that the SCA algorithm can significantly save the deployed relay
nodes comparing to the existing algorithms, i.e., at most 31.48% deployed relay
nodes can be saved due to SCA algorithm.
