Exact and approximate algorithms for clustering problem in wireless sensor networks
Ramin Yarinezhad, Seyed Naser Hashemi · IET Communications · 2019
Clustering is an effective method for improving the network lifetime and the overall scalability of a wireless sensor network. The problem of balancing the load of the cluster heads is called load‐balanced clustering problem (LBCP), which is an NP‐hard problem. In this study, the authors use parameterised complexity to cope with this NP‐hard problem. The authors show that LBCP can be solved by a k ‐additive approximation algorithm with a running time of , where k is an upper bound on the maximum load assigned to the cluster heads and n is the input size. Also, LBCP is FPT with respect to the maximum load of the sensor nodes and the number of sensor nodes. The authors propose an fpt‐algorithm with respect to these parameters for this problem. In addition, they prove that LBCP is when the number of the cluster heads is selected as the parameter.