Exact and approximate algorithms for clustering problem in wireless sensor networks

摘要

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) $2O(k/log& x2061;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]mbox {-}{m hard} $W[1]-hard when the number of the cluster heads is selected as the parameter.