Open AccessExact and approximate algorithms for clustering problem in wireless sensor networks
Author(s) -
Yarinezhad Ramin,
Hashemi Seyed Naser
Publication year - 2020
Publication title -
iet communications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.355
H-Index - 62
eISSN - 1751-8636
pISSN - 1751-8628
DOI - 10.1049/iet-com.2019.0510
Subject(s) - wireless sensor network , cluster analysis , scalability , computer science , algorithm , upper and lower bounds , computational complexity theory , cluster (spacecraft) , load balancing (electrical power) , wireless , mathematics , computer network , artificial intelligence , telecommunications , mathematical analysis , geometry , database , grid
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 2 O ( k / log k ) + O ( n ) , 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 W [ 1 ] ‐ hard when the number of the cluster heads is selected as the parameter.