Lifetime Constrained Relay Node Placement in WSNs: A Cluster-Based Approximation Algorithm

摘要

The lifetime of Wireless Sensor Networks (WSNs) is significantly shortened by the energy hole problem that is caused by the many-to-one communication pattern adopted by most WSNs. Various approaches have been designed to solve the energy hole problem, and this paper considers improving the energy efficiency by deploying additional relays, which is called the Lifetime Constrained Relay Node Placement (LCRNP) problem. To address the NP-hardness of the LCRNP problem, this paper proposes a Cluster-based Approximation Algorithm (CAA) that first groups the sensors into different clusters in which the lifetime constraint can be ignored and sensors are close to each other, and then builds network connectivity for each cluster. Next, the Augmented CAA is designed based on the CAA to further improve network lifetime by building addition paths for the relays prone to suffer heavy traffic loads. Unlike existing works, we prove that the proposed algorithms can guarantee polynomial time complexities and explicit approximation ratios. Finally, the efficiency of the proposed algorithms is verified through extensive simulations.