Wireless Sensor Networks (WSNs) have become an integral part of various industries and applications. However, frequent link interruptions and network unreliability caused by electromagnetic interferences may lead to high delay and packet loss, posing a challenge in achieving high reliability and stability in WSNs. In this paper, we propose an algorithm called Improved Cover-based 2-Connected Node Placement (IC2NP) to solve the Delay Constrained Relay Node Placement (DCRNP) problem in WSNs. The algorithm aims to build at least two node-disjoint paths meeting the hop constraint between each sensor and the sink by deploying certain relay nodes (RNs). IC2NP provides a feasible solution with a time complexity of O(N^4) and an approximation ratio guaranteed to be O(ln n). Through extensive simulations, we validate that IC2NP outperforms the existing method in terms of success rate, deployment budget, and running time. This paper also summarizes related work on the Relay Node Placement (RNP) problem and previous research on the DCRNP problem.
Open-access article — free to read and share.
Continental Scholarly Publications applies rigorous double-blind peer review to every submission. Our expert editorial board ensures your work meets the highest standards of scholarship before reaching an international readership.