A routing algorithm for wireless sensor networks based on clustering and an fpt-approximation algorithm

摘要

Clustering sensor nodes is an effective method for routing in Wireless Sensor Networks (WSNs), which maximizes the network lifetime and reduces the energy consumption. However, in a clustered-WSN, the Cluster Heads (CHs) bear a higher load compared to the other nodes, which leads to their earlier death. Therefore, minimizing the maximum load of the CHs is an important problem, which is called the Load Balanced Clustering Problem (LBCP). LBCP is an NP-hard problem and the best-known approximation factor for this problem is 1.5. Moreover, it has been shown that there is no polynomial-time approximation algorithm that solves this problem with a better approximation factor. In this paper, we propose a Fixed Parameter Tractable (FPT) approximation algorithm with an approximation factor of 1.2 for LBCP. We also propose an energy-efficient and energy-balanced routing algorithm for routing between the CHs and the sink. The simulation results show that the proposed algorithm is practical for large-scale WSNs and performs better than the other similar algorithms. (C) 2019 Elsevier Inc. All rights reserved.