An improved algorithm for delay constrained relay node deployment in wireless sensor networks

Given that Delay Constrained Relay Node Placement (DCRNP) problem is getting more and more attention in time-critical domains, this paper proposes an Improved Greedy-based Selection Algorithm (IGSA) to tackle such problem under delay and budget constraints. IGSA first employs communication cost matrix and Dijkstra's algorithm to detect whether the problem is solvable, then selects the amount and locations of deployed relay nodes (RNs) layer by layer by continuously calling the greedy coverage algorithm until all sensors have a feasible path to the sink under a preset delay constraint, and finally removes redundant RNs to reach the approximate optimal solution. Extensive simulations show that our approach can save 15%-30% of deployed RNs than the Two-phase Set-Covering-based Algorithm (TSCA), which is the state-of-the-art algorithm for the DCRNP problem, only with a slight sacrifice of solving time. Meanwhile, Ad Hoc On-Demand Distance Vector (AODV) routing protocol is applied to further examine the performance of the deployment results solved by TSCA and IGSA, respectively. Results show that every RN deployed by IGSA is involved in data forwarding, while IGSA deploys leisure RNs which do not participate in the data forwarding. Besides, compared with TSCA, the network formed by IGSA has lower network delay in the data transmission process, and the energy consumption of the central node and throughput of the two topologies are almost at the same level.